双向循环链表C语言详解 [复制链接]

我们知道，单链表通过首尾连接可以构成单向循环链表，如图1所示：

图1单向循环链表示意图

同样，双向链表也可以进行首尾连接，构成双向循环链表。如图2所示：

图2双向循环链表示意图

当问题中涉及到需要"循环往复"地遍历表中数据时，就需要使用双向循环链表。例如，前面章节我们对约瑟夫环问题进行了研究，其实约瑟夫环问题有多种玩法，每次顺时针报数后，下一轮可以逆时针报数，然后再顺时针......一直到剩下最后一个人。解决这个问题就需要使用双向循环链表结构。

创建双向循环链表，只需在创建完成双向链表的基础上，将其首尾节点进行双向连接即可。C语言实现代码如下：

//创建双向循环链表line*initLine(line*head){head=(line*)malloc(sizeof(line));head-prior=NULL;head-next=NULL;head-data=1;line*list=head;for(inti=2;i=3;i++){line*body=(line*)malloc(sizeof(line));body-prior=NULL;body-next=NULL;body-data=i;list-next=body;body-prior=list;list=list-next;}//通过以上代码，已经创建好双线链表，接下来将链表的首尾节点进行双向连接list-next=head;head-prior=list;returnhead;}

通过向main函数中调用initLine函数，就可以成功创建一个存储有{1,2,3}数据的双向循环链表，其完整的C语言实现代码为：

#includestdio.h#includestdlib.htypedefstructline{structline*prior;intdata;structline*next;}line;line*initLine(line*head);voiddisplay(line*head);intmain(){line*head=NULL;head=initLine(head);display(head);return0;}//创建双向循环链表line*initLine(line*head){head=(line*)malloc(sizeof(line));head-prior=NULL;head-next=NULL;head-data=1;line*list=head;for(inti=2;i=3;i++){line*body=(line*)malloc(sizeof(line));body-prior=NULL;body-next=NULL;body-data=i;list-next=body;body-prior=list;list=list-next;}//通过以上代码，已经创建好双线链表，接下来将链表的首尾节点进行双向连接list-next=head;head-prior=list;returnhead;}//输出链表的功能函数voiddisplay(line*head){line*temp=head;//由于是循环链表，所以当遍历指针temp指向的下一个节点是head时，证明此时已经循环至链表的最后一个节点while(temp-next!=head){if(temp-next==NULL){printf("%d\n",temp-data);}else{printf("%d-",temp-data);}temp=temp-next;}//输出循环链表中最后一个节点的值printf("%d",temp-data);}

程序输出结果如下：

1-2-3