🎃 前言
本人是西安邮电大学计科专业的一个普通学生，以下是本人对于带头双向循环链表的理解。
先上图
带头双向循环链表的 头节点（head）不存数据,因为如果数据是char类型的话，存放的数据多了 ，怎么表示？表示不了啊
🍺带你理解链表
如果大家对于链表还不是很熟悉的话，请点击传送门，那里有对于单链表的简单解释👉 传送门
🎄结构体创建结点
prev：指向上一个结点
next：指向下一个结点
1
2
3
4
5
6
7
| typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
DataType data;
}ListNode;
|
✨各个函数的实现：
🚋申请空间：
1
2
3
4
5
6
7
8
9
10
| ListNode* BuyNewNode( DataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
assert(newnode);
newnode->data = x;
newnode->next = newnode;
newnode->prev = newnode;
return newnode;
}
|
🚓寻找结点
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
| ListNode* Find(ListNode* phead, DataType x)
{
assert(phead->next != phead);
ListNode* pos = NULL;
ListNode* cur = phead->next;
while(cur!=phead)
{
if (cur->data==x)
{
pos = cur;
break;
}
cur = cur->next;
}
if(pos)
{
printf("找到！\n");
}
else
{
printf("没找到\n");
}
return pos;
}
|
🚒在指定结点之前插入
这个很重要，头插尾插都能用到
1
2
3
4
5
6
7
8
9
10
11
| void Insert(ListNode* pos, DataType x)
{
assert(pos);
ListNode* newnode = BuyNewNode(x);
ListNode* head = pos->prev;
head->next = newnode;
newnode->prev = head;
newnode->next = pos;
pos->prev = newnode;
}
|
🚈删除指定结点
1
2
3
4
5
6
7
8
9
10
| void Erease(ListNode* pos)
{
ListNode* Prev = pos->prev;
ListNode* Next = pos->next;
Prev->next = Next;
Next->prev = Prev;
free(pos);
pos = NULL;
}
|
🚍头插
头插就是在第一个结点前插入，第一个结点就是 phead->next
1
2
3
4
5
6
| void PushFront(ListNode* phead, DataType x)
{
ListNode* pos = phead->next;
Insert(pos, x);
}
|
🚇尾插
尾插就是在最后结点插入，也就是在phead之前插入
1
2
3
4
5
6
| void PushBack(ListNode* phead, DataType x)
{
ListNode* pos = phead;
Insert(pos, x);
}
|
🚃头删
头删就是删除phead->next
1
2
3
4
5
6
| void PopFront(ListNode* phead, DataType x)
{
ListNode* pos = phead->next;
Erease(pos);
}
|
🦽尾删
尾删就是删除phead->prev
1
2
3
4
5
6
| void PopBack(ListNode* phead, DataType x)
{
ListNode* pos = phead->prev;
Erease(pos);
}
|
🚂计算链表结点个数
1
2
3
4
5
6
7
8
9
10
11
12
13
| int Size(ListNode* phead)
{
assert(phead);
int sum = 0;
ListNode* cur = phead->next;
while (cur!=phead)
{
sum++;
cur = cur->next;
}
return sum;
}
|
🚒打印链表
1
2
3
4
5
6
7
8
9
10
11
12
| void Print(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
|
🍕 销毁链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void Destory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
ListNode* Next = cur->next;
free(cur);
cur = Next;
}
free(phead);
phead = NULL;
}
|
⚽完整代码：
🎎 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
| #pragma once
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DataType;
typedef struct ListNode
{
struct ListNode* prev;
struct ListNode* next;
DataType data;
}ListNode;
typedef struct ListNode ListNode;
ListNode* BuyNewNode(DataType x);
void PushFront(ListNode* phead,DataType x);
void PushBack(ListNode* phead, DataType x);
void PopFront(ListNode* phead);
void PopBack(ListNode* phead);
void Insert(ListNode* pos,DataType x);
void Erease(ListNode* pos);
ListNode* Find(ListNode* phead, DataType x);
void Print(ListNode* phead);
int Size(ListNode* phead);
void Destory(ListNode* phead);
|
🎨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
| #define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
ListNode* BuyNewNode( DataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
assert(newnode);
newnode->data = x;
newnode->next = newnode;
newnode->prev = newnode;
return newnode;
}
void PushFront(ListNode* phead, DataType x)
{
ListNode* pos = phead->next;
Insert(pos, x);
}
void PushBack(ListNode* phead, DataType x)
{
ListNode* pos = phead;
Insert(pos, x);
}
void PopFront(ListNode* phead, DataType x)
{
ListNode* pos = phead->next;
Erease(pos);
}
void PopBack(ListNode* phead, DataType x)
{
ListNode* pos = phead->prev;
Erease(pos);
}
ListNode* Find(ListNode* phead, DataType x)
{
assert(phead->next != phead);
ListNode* pos = NULL;
ListNode* cur = phead->next;
while(cur!=phead)
{
if (cur->data==x)
{
pos = cur;
break;
}
cur = cur->next;
}
if(pos)
{
printf("找到！\n");
}
else
{
printf("没找到\n");
}
return pos;
}
void Insert(ListNode* pos, DataType x)
{
assert(pos);
ListNode* newnode = BuyNewNode(x);
ListNode* head = pos->prev;
head->next = newnode;
newnode->prev = head;
newnode->next = pos;
pos->prev = newnode;
}
void Erease(ListNode* pos)
{
ListNode* Prev = pos->prev;
ListNode* Next = pos->next;
Prev->next = Next;
Next->prev = Prev;
free(pos);
pos = NULL;
}
void Print(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int Size(ListNode* phead)
{
assert(phead);
int sum = 0;
ListNode* cur = phead->next;
while (cur!=phead)
{
sum++;
cur = cur->next;
}
return sum;
}
void Destory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur!=phead)
{
ListNode* Next = cur->next;
free(cur);
cur = Next;
}
free(phead);
phead = NULL;
}
|
🧨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
| #define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
void Test1()
{
ListNode* plist = BuyNewNode(0);
PushFront(plist, 1);
PushFront(plist, 2);
PushFront(plist, 3);
PushBack(plist, 4);
Print(plist);
ListNode* pos= Find(plist,2);
Insert(pos, 200);
Print(plist);
PopFront(plist);
Print(plist);
PopBack(plist);
Print(plist);
printf("%d\n",Size(plist));
Destory(plist);
}
int main(void)
{
Test1();
return 0;
}
|
💖test.c的运行结果
🎉结语
如果这篇文章有帮助的话请给我点个免费的赞呗。
如果有什么问题可以在评论区提问。
