-
数据结构线性表之带头双向循环链表
各位读者们好久不见了，咋们接着上一期链表来，今天来实现一下链表最难的结构，同时也是实现起来最简单的结构——带头双向循环链表。话不多说，进入主题
前言
带头双向循环链表的概念与模型
上图链表每一个节点有3部分构成，next指针指向下一个节点，prev指针指向上一个节点，以及数值
最后一个节点的next指针指向哨兵位头节点head，head节点的prev指针指向最后一个节点知识点：
当链表只有一个head的哨兵位节点是，head的next指针与prev节点指针都指向head本身，所以我们可以直接进行增删查改的一系列操作，比单链表简单得多
实现带头双向循环链表
老规矩，一个DList.h头文件、一个DList.c源文件、一个test.c源文件，三个文件
DList.h头文件
该文件与之前一样，放函数的声明等内容
#pragma once #include#include #include #include //C语言使用bool类型判断真假时要用到该头文件 typedef int DLDataType;//重命名 typedef struct DListNode//结构体重命名 { DLDataType data; DLDataType* next; DLDataType* prev; }DLN; //下面是接口函数 DLN* DLNInit();//初始化 void DLNDelete(DLN* phead);//销毁空间 void DLNPrint(DLN* phead);//打印节点 void DLNPushback(DLN* phead,DLDataType x);//尾插 void DLNPushfront(DLN* phead, DLDataType x);//头插 bool DLNExist(DLN* phead);//判断链表是否只有哨兵位头节点 void DLNPopback(DLN* phead);//尾删 void DLNPopfront(DLN* phead);//头删 size_t DLNCount(DLN* phead);//链表有多少个有效数据节点 DLN* DLNFind(DLN* phead, DLDataType x);//查找节点 void DLNInsert(DLN* pos, DLDataType x);//任意位置插入 void DLNErase(DLN* pos);//任意位置删除 void DLNModify(DLN* pos, DLDataType x);//任意位置修改 - 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
test.c源文件
这里我把链表写成了一个菜单函数，把测试用例都屏蔽了，大家有兴趣可以把菜单函数屏蔽，测试每个接口函数
#define _CRT_SECURE_NO_WARNINGS #include"DList.h" //void Test1() //{ // DLN* phead = DLNInit();//初始化 // DLNPushback(phead, 1);//尾插 // DLNPushback(phead, 2); // DLNPushback(phead, 3); // DLNPushback(phead, 4); // DLNPushback(phead, 5); // DLNPrint(phead);//打印节点 // // DLNPushfront(phead, 10);//头插 // DLNPushfront(phead, 20); // DLNPushfront(phead, 30); // DLNPushfront(phead, 40); // DLNPushfront(phead, 50); // DLNPrint(phead);//打印节点 // // DLNPopback(phead);//尾删 // DLNPopback(phead); // DLNPopback(phead); // DLNPopback(phead); // //DLNPopback(phead); // //DLNPopback(phead); // DLNPrint(phead);//打印节点 // // DLNPopfront(phead);//头删 // DLNPopfront(phead); // DLNPopfront(phead); // DLNPrint(phead);//打印节点 // // DLNDelete(phead); // phead = NULL;//一级指针要在外面置空，里面置空phead是改变形参，不能改变实参 //} // // //void Test2() //{ // DLN* phead = DLNInit();//初始化 // DLNPushback(phead, 1);//尾插 // DLNPushback(phead, 2); // DLNPushback(phead, 3); // DLNPushback(phead, 4); // DLNPushback(phead, 5); // // DLNPushfront(phead, 10);//头插 // DLNPushfront(phead, 20); // DLNPushfront(phead, 30); // DLNPushfront(phead, 40); // DLNPushfront(phead, 50); // // DLNPrint(phead);//打印节点 // // printf("%zd\n", DLNCount(phead));//链表有多少个有效数据节点 // DLNDelete(phead); // phead = NULL; //} //void Test3() //{ // DLN* phead = DLNInit();//初始化 // DLNPushback(phead, 1);//尾插 // DLNPushback(phead, 2); // DLNPushback(phead, 3); // DLNPushback(phead, 4); // DLNPushback(phead, 5); // // DLNPushfront(phead, 10);//头插 // DLNPushfront(phead, 20); // DLNPushfront(phead, 30); // DLNPushfront(phead, 40); // DLNPushfront(phead, 50); // // DLNPrint(phead);//打印节点 // DLN* p = DLNFind(phead, 5);//查找节点 // DLNInsert(p, 100);//任意位置插入 // DLNPrint(phead);//打印节点 // // DLN* w = DLNFind(phead, 30);//查找节点 // DLNErase(w);//任意位置删除 // DLNPrint(phead);//打印节点 // // DLN* q = DLNFind(phead, 20);//查找节点 // DLNModify(q, 200);//任意位置修改 // DLNPrint(phead);//打印节点 // // DLNDelete(phead); // phead = NULL; //} void menu() { printf("-------------------------------\n"); printf("*******************************\n"); printf("***0、退出程序 5、打印节点***\n"); printf("***1、尾插节点 2、头插节点***\n"); printf("***3、尾删节点 4、头删节点***\n"); printf("***6、任意插入 7、任意删除***\n"); printf("***8、查找节点 9、修改节点***\n"); printf("*******************************\n"); printf("-------------------------------\n"); } int main() { DLN* phead = DLNInit();//初始化，接收哨兵位头节点的返回值，表示phead已经是一个哨兵位的头节点了 int n = 0; do { menu(); printf("请选择操作:"); scanf("%d", &n); int x = 0; int y = 0; switch (n) { case 1: printf("请输入尾插数据，以数据-1截止\n"); do { scanf("%d", &x); if (x == -1) { break; } DLNPushback(phead, x); } while (x != -1); break; case 2: printf("请输入头插数据，以数据-1截止\n"); do { scanf("%d", &x); if (x == -1) { break; } DLNPushfront(phead, x); } while (x != -1); break; case 3: DLNPopback(phead); break; case 4: DLNPopfront(phead); break; case 5: DLNPrint(phead); break; case 6: printf("请输入在什么节点前面插入，与插入节点值\n"); scanf("%d %d", &x, &y);//输入数据1——在哪一个节点前面插入，输入数据2——插入节点的值是多少 DLNInsert(DLNFind(phead, x), y); break; case 7: printf("请输入删除节点值\n"); scanf("%d", &x); DLNErase(DLNFind(phead, x)); break; case 8: printf("请输入查找节点值\n"); scanf("%d", &x); DLN* pos = DLNFind(phead, x); printf("%p\n", pos);//打印节点地址 break; case 9: printf("请输入要被修改的节点值，以及修改完的节点值\n"); scanf("%d %d", &x, &y); DLNModify(DLNFind(phead, x), y); break; case 0: DLNDelete(phead); phead = NULL;//手动置空 printf("退出程序\n"); break; default: printf("输入错误，请重新输入\n"); break; } } while (n); return 0; }- 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
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
不止有上面这些接口，光一个查找接口与其他接口结合就有好多种玩法，大家按照自己的想法来，但一定要控制好，以免出现内存泄漏等负面影响
DList.c源文件
这里就是链表各个函数接口的定义了
1、初始化
因为刚开始是没有头节点的，所以初始化要动态开辟一个头节点出来，并且是头节点的next和prev指针都指向自己
注意：这里因为改变了teat.c文件的phead指针，所以要使用二级指针，但是我上面直接让phead指针等于初始化之后指针，所以使用的是一级指针。我们前面的顺序表和单链表也可以这样来操作
DLN* DLNInit()//初始化 { DLN* head = (DLN*)malloc(sizeof(DLN)); if (head == NULL) { perror("malloc fail"); exit(-1); } head->next = head; head->prev = head; return head; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
这里的head就是开辟出来的哨兵位头节点，相信大家都能够理解这段代码，不是很难
2、打印节点数据
打印什么时候停下来呢？
因为这是带头循环链表，如果控制不当就会死循环了，这里我们只要定义一个指针从phead->next开始，也就是第一个数据开始走，走一下打印数据，循环往复，直到我们定义的指针等于phead，就相当于我们已经遍历完一遍链表了，就可以退出了void DLNPrint(DLN* phead)//打印节点 { assert(phead); DLN* cur = phead->next;//从第一个节点开始 printf("phead<=>"); while (cur != phead)//等于头节点就是循环完一次了 { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
3、销毁空间
这里销毁空间的结束判断与打印节点数据的方式是一样的，判断我们定义的指针循环是不是等于phead头节点
void DLNDelete(DLN* phead)//销毁空间 { assert(phead); DLN* cur = phead->next; while (cur != phead) { DLN* next = cur->next; free(cur); cur = next; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
4、扩容函数
DLN* Buylistnode(DLDataType x)//扩容 { DLN* newnode = (DLN*)malloc(sizeof(DLN)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
与之前的扩容无太大差别
5、尾插
void DLNPushback(DLN* phead, DLDataType x)//尾插 { assert(phead); DLN* newnode = Buylistnode(x); DLN* tail = phead->prev;//记录尾插之前的尾节点 phead->prev = newnode;//头节点的prev指向尾插节点 newnode->next = phead;//尾插节点的next指向头节点 newnode->prev = tail;//尾插节点的prev指向之前的尾节点 tail->next = newnode;//之前尾节点的next指向头节点，现在指向尾插节点 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
6、头插
void DLNPushfront(DLN* phead, DLDataType x)//头插 { assert(phead); DLN* newnode = Buylistnode(x); DLN* tail = phead->next;//记录第一个节点的地址 phead->next = newnode;//头节点原本指向第一个节点，现在头节点next指向头插节点 newnode->next = tail;//头插节点next指向原来第一个节点 newnode->prev = phead;//头插节点的prev指向头节点 tail->prev = newnode;//原来第一个节点的prev指向头插节点 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
7、判断链表是否只有头节点
bool DLNExist(DLN* phead)//判断链表是否只有哨兵位头节点 { assert(phead); return phead->next == phead;//直接返回，如果为真就表示只有头节点 }- 1
- 2
- 3
- 4
- 5
8、尾删节点
void DLNPopback(DLN* phead)//尾删 { //assert(phead &&(!DLNExist(phead))); assert(phead); assert(!DLNExist(phead));//如果DLNExist(phead)为真就表示只有头节点，！真就是假断言生效 DLN* tail = phead->prev;//记录尾节点 DLN* cur = tail->prev;//记录尾节点的前一个节点 cur->next = phead;//直接让尾节点的前一个节点next指向头节点 phead->prev = cur;//头节点的prev指向尾节点前一个节点 free(tail);//释放尾节点 tail = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
9、头删节点
void DLNPopfront(DLN* phead)//头删 { //assert(phead &&(!DLNExist(phead))); assert(phead); assert(!DLNExist(phead));//如果只有头节点，断言生效 DLN* tail = phead->next;//记录第一个节点 DLN* cur = tail->next;//记录第二个节点 phead->next = cur;//头节点next指向第二个节点 cur->prev = phead;//第二个节点prev指向头节点 free(tail);//释放第一个节点 tail = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
10、链表有效数据节点个数
就是来记录链表除了头节点还有多少个节点
与打印节点的方式一样
size_t DLNCount(DLN* phead)//链表有多少个有效数据节点 { assert(phead); DLN* cur = phead->next; size_t count = 0; while (cur != phead) { ++count; cur = cur->next; } return count; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
11、查找节点
这里也很简单，直接遍历，返回节点的地址
DLN* DLNFind(DLN* phead, DLDataType x)//查找节点 { assert(phead); DLN* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
12、任意位置插入节点
带头双向循环链表的插入一般都是前插
void DLNInsert(DLN* pos, DLDataType x)//任意位置插入 { assert(pos); DLN* newnode = Buylistnode(x); DLN* tail = pos->prev; tail->next = newnode; newnode->next = pos; newnode->prev = tail; pos->prev = newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
13、任意位置删除节点
void DLNErase(DLN* pos)//任意位置删除 { assert(pos); DLN* cur = pos->prev; DLN* tail = pos->next; cur->next = tail; tail->prev = cur; free(pos); pos = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
14、修改节点
直接修改即可
void DLNModify(DLN* pos, DLDataType x)//任意位置修改 { assert(pos); pos->data = x; }- 1
- 2
- 3
- 4
- 5
这里与单链表一样，可以用任意插入、删除来取代头插尾插，头撒尾删节点
DList.c代码
#define _CRT_SECURE_NO_WARNINGS #include"DList.h" DLN* DLNInit()//初始化 { DLN* head = (DLN*)malloc(sizeof(DLN)); if (head == NULL) { perror("malloc fail"); exit(-1); } head->next = head; head->prev = head; return head; } void DLNDelete(DLN* phead)//销毁空间 { assert(phead); DLN* cur = phead->next; while (cur != phead) { DLN* next = cur->next; free(cur); cur = next; } } void DLNPrint(DLN* phead)//打印节点 { assert(phead); DLN* cur = phead->next;//从第一个节点开始 printf("phead<=>"); while (cur != phead)//等于头节点就是循环完一次了 { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); } DLN* Buylistnode(DLDataType x)//扩容 { DLN* newnode = (DLN*)malloc(sizeof(DLN)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->next = NULL; newnode->prev = NULL; newnode->data = x; return newnode; } void DLNPushback(DLN* phead, DLDataType x)//尾插 { assert(phead); //DLN* newnode = Buylistnode(x); //DLN* tail = phead->prev;//记录尾插之前的尾节点 //phead->prev = newnode;//头节点的prev指向尾插节点 //newnode->next = phead;//尾插节点的next指向头节点 //newnode->prev = tail;//尾插节点的prev指向之前的尾节点 //tail->next = newnode;//之前尾节点的next指向头节点，现在指向尾插节点 DLNInsert(phead, x);//任意位置插入是前插，在phead前面插入就是尾插 } void DLNPushfront(DLN* phead, DLDataType x)//头插 { assert(phead); //DLN* newnode = Buylistnode(x); //DLN* tail = phead->next;//记录第一个节点的地址 //phead->next = newnode;//头节点原本指向第一个节点，现在头节点next指向头插节点 //newnode->next = tail;//头插节点next指向原来第一个节点 //newnode->prev = phead;//头插节点的prev指向头节点 //tail->prev = newnode;//原来第一个节点的prev指向头插节点 DLNInsert(phead->next, x);//在第一个节点前面插入就是头插 } bool DLNExist(DLN* phead)//判断链表是否只有哨兵位头节点 { assert(phead); return phead->next == phead;//直接返回，如果为真就表示只有头节点 } void DLNPopback(DLN* phead)//尾删 { //assert(phead &&(!DLNExist(phead))); //assert(phead); //assert(!DLNExist(phead));//如果DLNExist(phead)为真就表示只有头节点，！真就是假断言生效 //DLN* tail = phead->prev;//记录尾节点 //DLN* cur = tail->prev;//记录尾节点的前一个节点 //cur->next = phead;//直接让尾节点的前一个节点next指向头节点 //phead->prev = cur;//头节点的prev指向尾节点前一个节点 //free(tail);//释放尾节点 //tail = NULL; DLNErase(phead->prev); } void DLNPopfront(DLN* phead)//头删 { //assert(phead &&(!DLNExist(phead))); //assert(phead); //assert(!DLNExist(phead));//如果只有头节点，断言生效 //DLN* tail = phead->next;//记录第一个节点 //DLN* cur = tail->next;//记录第二个节点 //phead->next = cur;//头节点next指向第二个节点 //cur->prev = phead;//第二个节点prev指向头节点 //free(tail);//释放第一个节点 //tail = NULL; DLNErase(phead->next); } size_t DLNCount(DLN* phead)//链表有多少个有效数据节点 { assert(phead); DLN* cur = phead->next; size_t count = 0; while (cur != phead) { ++count; cur = cur->next; } return count; } DLN* DLNFind(DLN* phead, DLDataType x)//查找节点 { assert(phead); DLN* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void DLNInsert(DLN* pos, DLDataType x)//任意位置插入 { assert(pos); DLN* newnode = Buylistnode(x); DLN* tail = pos->prev; tail->next = newnode; newnode->next = pos; newnode->prev = tail; pos->prev = newnode; } void DLNErase(DLN* pos)//任意位置删除 { assert(pos); DLN* cur = pos->prev; DLN* tail = pos->next; cur->next = tail; tail->prev = cur; free(pos); pos = NULL; } void DLNModify(DLN* pos, DLDataType x)//任意位置修改 { assert(pos); pos->data = x; }- 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
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
总结
到这里为止链表我们就结束了，我们已经了解有多少链表了，至于怎么使用在什么场景使用就看大家遇到什么样的情况了，小编也不多讲，希望大家能够与小编一起共同进步吧，我们下期见！
-
相关阅读:
【数据结构】二叉树的链式结构及实现
这道题自己出的，有人会吗(我写了代码，有大佬帮我debug吗)
C语言sizeof函数解析
nginx
The import xxx.xxx.xxxx is never used
超越openmp通用核心的硬件
2023年中国云计算软件市场规模、市场结构及市场份额情况分析[图]
【JVM】——JVM中内存划分
基于JavaSwing开发企业进销存管理系统 中药材进销存管理+论文 毕业设计源码
L3-005 垃圾箱分布
- 原文地址：https://blog.csdn.net/kdjjdjdjjejje128/article/details/126119979
