双向循环链表,先来说说双向链表,双向链表也叫双链表,是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点.而循环链表之前也有说过,单链表中就是让最后一个结点的指针指向第一个结点就能构成一个循环链表,这里其实也是一样的,只不过多了一步,让第一个结点的前驱指向最后一个结点就行了,(这里介绍的是带头结点的双向循环链表,所以用第一个结点和头结点来区分两者).下面直接看看怎么创建一个带头结点的双向循环链表吧.
1 #include<stdio.h> 2 #include<stdlib.h> 3 struct data 4 { 5 int num; 6 struct data *front; //指向它之前的结点 7 struct data *next; //指向它之后的结点 8 }; 9 int main() 10 { 11 int n=1; 12 struct data *p,*p1,*head; 13 p=head=(struct data *)malloc(sizeof(struct data)); //创建一个带头结点的双向循环链表 14 p->next=NULL; //开始的时候把指向前面的和后面的指针都置为空 15 p->front=NULL; 16 p1=(struct data *)malloc(sizeof(struct data)); //创建新结点,向链表中添加数据 17 p1->num=1; 18 while(n<=10) 19 { 20 n++; 21 p->next=p1; //让前一个结点p的尾指针指向这个结点p1 22 p1->front=p; //这个结点的头指针指向前一个结点 23 p=p1; //p1变为p 24 p1=(struct data *)malloc(sizeof(struct data)); //创建新的结点p1,给其赋值并重复上面的循环 25 p1->num=n; 26 } 27 p->next=head->next; //最后,由于是带头结点的双循环链表,所以要让最后一个结点的尾指针指向head之后的那个结点 28 head->next->front=p; //让head之后的那个结点的头指针指向尾结点 29 free(p1); 30 return 0; 31 32 }
双向循环链表可以随时访问任何一个结点的前一个结点,所以,用来查找会很方便.它的删除和添加和单链表的操作差不多,只不过需要注意,有两个指针域,要分别让他们重新指向新的结点.还有一点需要注意,就是如果要删除的结点是第一个结点的话,需要让头结点重新指向.来一小段代码吧
1 while(1) //循环寻找需要删除的结点 2 { 3 if(p->num==5) //寻找的条件 4 { 5 if(head->next==p) //判断删除的结点是不是第一个结点 6 { 7 head->next=p->next; //如果是第一个结点,让头结点指向它之后的结点 8 } 9 p->front->next=p->next; //当前结点的前一个结点为p->front,让它指向当前结点的下一个结点p->next 10 p->next->front=p->front; //让当前结点p的下一个结点p->next的前驱指向它的前一个结点p->front;这样就删掉了这个结点 11 break; 12 } 13 p=p->next; 14 15 }
OK,好好加油! ! ! ^_^