23.链式存储结构--循环链表

一.循环链表引入

我们学习了单链表的相关知识和算法，发现学习循环链表就轻松了很多，那么什么是循环链表？

在单链表中我们只存储了向后的指针，到达尾标志就停止了。我们可以通过一个结点找到后结点，但是无法找到前结点了。

如果我们将尾结点的指针域指向头结点，一个单链表就形成了一个环，这种链表叫循环链表。（主要解决单链表的问题：从任意结点出发，可以访问到链表的全部结点）（我们的环线地铁，不管你从哪一站上车，都能从整个环线的任意位置下车）

 

二.循环链表关键知识点

循环链表不一定要有头结点，但是为了使空链表和非空链表处理一致，通常加一个头结点。

单链表通过p->next ==NULL 来判断链表是否结束

循环链表 p->next ==头结点 来判断链表是否结束

 

三.单向循环链表

单向循环链表就是在单链表的基础上，将尾结点的指针域指向了头结点，形成了一个环，很好理解。

举个应用的例子，理解一下和单链表的异同就可以了

实现结点数目指定为N的单向循环链表，要求包含头结点（发现并没什么新知识点）

linklist list_create()
{
	linklist H,r,p;
	int n,i;
loop:
	printf("please input n:");
	scanf("%d",&n);
	if(n<0)
	{
		printf("please input:n>0\n");
		goto loop;
	}
	if((H=(linklist)malloc(sizeof(listnode)))==NULL)
	{
		printf("malloc failed!\n");
		return H;
	}
	H->data = 1;
	H->next = H;
	r=H; //上面这么多步骤就先做了一些输入参数的判断和创建了一个只有头结点的单链表
	
	for(i=2;i<=n;i++)  //实现了一个尾结点的插入，r跟屁虫总是指向尾结点
	{
		if((p=(linklist)malloc(sizeof(listnode)))==NULL){
			printf("malloc failed\n");
			return NULL;
		}
		p->data = i;
		r->next = p;
		r=p;
	}
	p->next = H; //循环链表的特殊之处，形成环

	return H;
}

 

四.双向循环链表

虽然通过循环链表，能够找到上一结点，但是需要再遍历一遍，很费时间，于是出现了双向链表。

双向链表（在单链表基础上在增加一个前驱结点的指针域）

typedef int data_t; //方便替换数据类型
typedef struct node{
    data_t data; //数据域
struct node *prior;//指向上一个结点
    struct node *next;//指针域，指向下一个结点 
}dlistnode;

 

双向循环链表

双向链表在求长度，查找元素，获取元素等和单链表相同，操作一个方向的指针就好。

但是双向链表在获得遍历的同时，插入和删除也要费劲一点，需要更改两个指针的变量。

1.插入操作（注意操作步骤）

有了顺序就很好做操作了，q = p->next

s->prior = p

s->next = q

q->prior = s

p->next = s

 

2.删除操作

删除就更简单了

H = p->prior

q =p->next

则

H->next = q

q->prior = H

 

其他的一些操作和单链表是很相似的，理解一下就行了

3.双向循环链表的创建（只有头结点）

if((H=(dlistnode *)malloc(sizeof(dlistnode)))==NULL)
{
    puts("malloc failed");
    return NULL;
}
H->prior = H; //自己指向自己
H->next = H;

4.双向循环链表的遍历

void dlist_show(dlistnode* H)
{
	dlistnode *p;
	p=H->next;
	while(p!=H)  //表示循环链表结束
	{
		printf("%d ",p->data);
		p=p->next;
	}
}

 

5.通过编号查找

dlistnode* dlist_get(dlistnode *H,int pos)
{
	int i=-1;
	dlistnode *p=H;

	if(pos <0){
		puts("pos < 0,invalid!");
		return NULL;
	}
	while(i<pos){
		p=p->next;
		i++;
		if(p==H){
			puts("pos > length,invalid");
			return NULL;
		}
	}
	return p;
}