前言
关于链表这一块，写了多篇博客，学习了顺序表、单链表、及其一些练习题
顺序表：传送门：顺序表
链表OJ：传送门：链表OJ
今天，我又来水一水博客， 介绍关于双链表。
带头双向循环链表的结构
实际上，单链表也存在一个比较大的缺陷：
1.不能从后往前遍历
2.无法找到前驱
除了单链表之外，我们自然还有双向链表，我们要说的就是带头双向循环链表，简单理解为：带头结点的，有两个方向的。循环的。结构图如下：
结构虽然比较复杂，但是极大方便我们找结点，比如可以直接找到尾结点，然后再进入相关的操作。实际代码的操作将会比单链表简单，极为方便，这里不做过多说明，直接上手代码
代码操作
我们直奔主题，进入代码实现的操作，之前的操作如果理解了，那我相信这个对于你来说肯定是不难的。下面直接给出源码：
List.h
|
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
|
#pragma once#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <assert.h>#include <stdbool.h>typedef int LTDataType;//带头双向循环--最优链表结构，在任意位置插入删除数据都是O（1）typedef struct listNode{ struct ListNode* next; struct ListNode* prev; LTDataType data;}ListNode;//初始化ListNode*ListInit();//销毁void ListDestory(ListNode* phead);//打印void ListPrint(ListNode* phead);//尾插void ListPushBack(ListNode* phead, LTDataType x);//头插void ListPushFront(ListNode* phead, LTDataType x);//头删void ListPopFront(ListNode* phead);//尾删void ListPopBack(ListNode* phead);ListNode* ListFind(ListNode* phead, LTDataType x);//在pos位置之前插入xvoid ListInsert(ListNode* pos, LTDataType x);//删除pos位置的值void ListErase(ListNode* pos); |
List.c
|
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
|
#include "List.h"//开辟一个新结点ListNode* BuyListNode(LTDataType x){ ListNode* newnode =(ListNode*)malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode;}//初始化ListNode* ListInit(){ ListNode*phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead;}//销毁void ListDestory(ListNode* phead){ assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL;}//打印void ListPrint(ListNode* phead){ ListNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n");}//尾插void ListPushBack(ListNode* phead, LTDataType x){ assert(phead); ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode;}//头插void ListPushFront(ListNode* phead, LTDataType x){ assert(phead); ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); newnode->next = first; first->prev = newnode; phead->next = newnode; newnode->prev = phead;}//头删void ListPopFront(ListNode* phead){ assert(phead); assert(phead->next != phead); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL;}//尾删void ListPopBack(ListNode* phead){ assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; prev->next = phead; phead->prev = prev; free(tail); tail = NULL;}ListNode* ListFind(ListNode* phead, LTDataType x){ assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL;}//在pos位置之前插入xvoid ListInsert(ListNode* pos, LTDataType x){ assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode;}//删除pos位置的值void ListErase(ListNode* pos){ assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos);} |
Test.c
|
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
|
#include "List.h"void TestList1(){ ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 0); ListPushFront(plist, -1); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListPopBack(plist); ListPrint(plist);}void TestList2(){ ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListNode* pos = ListFind(plist, 3); if (pos) { pos->data *= 10; printf("找到了,并且*10\n"); } else { printf("没找到\n"); } ListPrint(plist); ListInsert(pos, 300); ListPrint(plist); ListErase(pos); ListPrint(plist);}int main(){ TestList2(); return 0;} |
到此这篇关于C语言手把手带你掌握带头双向循环链表的文章就介绍到这了,更多相关C语言带头双向循环链表内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/weixin_60478154/article/details/124092194
