一 概述
1
2
3
| 1.什么是双向循环链表
2.双向循环链表的应用场景
3.双向循环链表示例
|
二 什么是双向循环链表
一、单链表通过首尾连接可以构成单向循环链表
二、双向链表也可以进行首尾连接，构成双向循环链表
三 双向循环链表的应用场景
1
2
3
4
| 当需要 "循环往复" 地遍历表中数据时，就需要使用双向循环链表。
例如，约瑟夫环问题有多种玩法，每次顺时针报数后，下一轮可以逆时针报数，然后再顺时针......，
一直到剩下最后一个人。解决这个问题就需要使用双向循环链表结构。
|
四 双向循环链表示例
一、创建双向循环链表只需在创建完成双向链表的基础上，将首尾节点进行双向连接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| // 创建双向循环链表
line* initLine(line * head){
head=(line*)malloc(sizeof(line));
head->prior=NULL;
head->next=NULL;
head->data=1;
line * list=head;
for (int 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}数据的双向循环链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #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){
head=(line*)malloc(sizeof(line));
head->prior=NULL;
head->next=NULL;
head->data=1;
line * list=head;
for (int 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
*/
|
五 参考