循环链表与双向链表

 

一、循环链表

　　循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

　　循环链表的运算与单链表的运算基本一致。所不同的有以下几点：

　　1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。

　　2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。 二、双向链表

　　双向链表其实是单链表的改进。

　　当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

　　在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。在c语言中双向链表结点类型可以定义为：

typedef struct node

{

int data; /*数据域*/

struct node *llink,*rlink; /*链域，*llink是左链域指针，*rlink是右链域指针*/

}JD;

　　当然，也可以把一个双向链表构建成一个双向循环链表。

　　双向链表与单向链表一样，也有三种基本运算：查找、插入和删除。

　　双向链表的基本运算：

　　1、查找

　　假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时，我们同样从表头结点往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，否则继续往后查，直到表尾。

下例就是应用双向循环链表查找算法的一个程序。

#include ＜stdio.h＞

#include ＜malloc.h＞

#define N 10

typedef struct node

{

　char name[20];

　struct node *llink,*rlink;

}stud;

stud * creat(int n)

{

　stud *p,*h,*s;

　int i;

　if((h=(stud *)malloc(sizeof(stud)))==NULL)

　{

　　printf("不能分配内存空间!");

　　exit(0);

　}

　h-＞name[0]=’\0’;

　h-＞llink=NULL;

　h-＞rlink=NULL;

　p=h;

　for(i=0;i＜n;i++)

　{

　　if((s= (stud *) malloc(sizeof(stud)))==NULL)

　　{

　　　printf("不能分配内存空间!");

　　　exit(0);

　　}

　　p-＞rlink=s;

　　printf("请输入第%d个人的姓名",i+1);

　　scanf("%s",s-＞name);

　　s-＞llink=p;

　　s-＞rlink=NULL;

　　p=s;

　}

　h-＞llink=s;

　p-＞rlink=h;

　return(h);

}

stud * search(stud *h,char *x)

{

　stud *p;

　char *y;

　p=h-＞rlink;

　while(p!=h)

　{

　　y=p-＞name;

　　if(strcmp(y,x)==0)

　　　return(p);

　　else p=p-＞rlink;

　}

　printf("没有查找到该数据!");

}

void print(stud *h)

{

　int n;

　stud *p;

　p=h-＞rlink;

　printf("数据信息为：\n");

　while(p!=h)

　{

　　printf("%s ",&*(p-＞name));

　　p=p-＞rlink;

　}

　printf("\n");

}

main()

{

　int number;

　char studname[20];

　stud *head,*searchpoint;

　number=N;

　clrscr();

　head=creat(number);

　print(head);

　printf("请输入你要查找的人的姓名:");

　scanf("%s",studname);

　searchpoint=search(head,studname);

　printf("你所要查找的人的姓名是:%s",*&searchpoint-＞name);

}

2、插入

　　对于双向循环链表，我们现在可以随意地在某已知结点p前或者p后插入一个新的结点。

　　假若s,p,q是连续三个结点的指针，若我们要在p前插入一个新结点r，则只需把s的右链域指针指向r，r的左链域指针指向s，r的右链域指针指向p，p的左链域指针指向r即可。

　　在p,q之间插入原理也一样。

　　下面就是一个应用双向循环链表插入算法的例子：

void insert(stud *p)

{

　char stuname[20];

　stud *s;

　if((s= (stud *) malloc(sizeof(stud)))==NULL)

　{

　　printf("不能分配内存空间!");

　　exit(0);

　}

　printf("请输入你要插入的人的姓名:");

　scanf("%s",stuname);

　strcpy(s-＞name,stuname);

　s-＞rlink=p-＞rlink;

　p-＞rlink=s;

　s-＞llink=p;

　(s-＞rlink)-＞llink=s;

}

3、删除

　　删除某个结点，其实就是插入某个结点的逆操作。还是对于双向循环链表，要在连续的三个结点s,p,q中删除p结点，只需把s的右链域指针指向q，q的左链域指针指向s，并收回p结点就完成了。

　　下面就是一个应用双向循环链表删除算法的例子：

void del(stud *p)

{

　(p-＞rlink)-＞llink=p-＞llink;

　(p-＞llink)-＞rlink=p-＞rlink;

　free (p);

}