作者：解学武

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

双向循环链表的创建

创建双向循环链表，只需在创建完成双向链表的基础上，将其首尾节点进行双向连接即可。

C 语言实现代码如下：

//创建双向循环链表
line* initLine(line * head) {
    int i = 0;
    line * list = NULL;
    head = (line*)malloc(sizeof(line));
    head->prior = NULL;
    head->next = NULL;
    head->data = 1;
    list = head;
    for (i = 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;
    return head;
}

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

#include <stdio.h>
#include <stdlib.h>
typedef struct line {
    struct line * prior;
    int data;
    struct line * next;
}line;

line* initLine(line * head);
void display(line * head);
int main() {
    line * head = NULL;
    head = initLine(head);
    display(head);
    return 0;
}
//创建双向循环链表
line* initLine(line * head) {
    int i = 0;
    line * list = NULL;
    head = (line*)malloc(sizeof(line));
    head->prior = NULL;
    head->next = NULL;
    head->data = 1;
    list = head;
    for (i = 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;
    return head;
}

//输出链表的功能函数
void display(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

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。