热门标签
热门文章
- 1Jenkins 连接 Gitlab 实现 push 代码 自动构建_jenkins git push
- 2GitHub 无法访问？这里有神器级解决方案_github 访问不了
- 3静态路由、默认路由、浮动路由原理及综合实验_路由综合实验原理
- 4正交匹配追踪方法源码 Matlab —— 求解矩阵最小化问题_正交匹配追踪算法源代码
- 5SpringBoot结合Mybatis使用_springboot引入mybatis依赖
- 6Web前端开发学习笔记_web前端笔记
- 7【毕业设计】基于SSM的进存销管理系统 - spring mvc java web_基于ssm的进销存管理系统
- 8双网卡teamviewer linux,钉钉远程打卡2019实践录
- 9visibroker的corba接口_borland visibroker
- 10软件供应链安全：寻找最薄弱的环节
当前位置: article > 正文
数据结构——双向链表的实现
作者：IT小白 | 2024-04-15 07:38:52
赞
踩
数据结构——双向链表的实现
一、双向链表的结构
带头双向循环链表
注意：这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严
谨，但是为了更好的理解就直接称为单链表的头节点。
带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的”
“哨兵位”存在的意义：
遍历循环链表避免死循环。
二、实现双向链表
创建双向链表的项目
List.h 定义双向链表的结构，声明相关的函数
List.c 实现双向链表声明的函数
test.c 测试代码
双向链表的结构
List.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LTDateType; //定义双向链表结点的结构 typedef struct ListNode { LTDateType date; struct ListNode* next; struct ListNode* prev; }LTNode; //声明双向链表中提供的方法 //初始化 //void LTInit(LTNode** pphead); LTNode* LTInit(); //打印 void LTPrint(LTNode* phead); //插入数据之前，链表必须初始化为只有一个结点的情况下 // 不改变哨兵位的位置，因此传一级指针即可 //尾插 void LTPushBack(LTNode* phead, LTDateType x); //头插 void LTPushFront(LTNode* phead, LTDateType x); //尾删 void LTPopBack(LTNode* phead); //头删 void LTPopFront(LTNode* phead); //查找 LTNode* LTFind(LTNode* phead, LTDateType x); //在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDateType x); //删除pos结点 void LTErase(LTNode* pos); //销毁 void LTDesTroy(LTNode* phead);
- 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
申请结点
//申请结点
LTNode* LTBuyNode(LTDateType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
node->date = x;
node->next = node->prev = node;
return node;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
初始化
这里有两种实现方法
//初始化
//void LTInit(LTNode** pphead)
//{
// //给双向链表创建一个哨兵位
// *pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
打印
//打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->date);
pcur = pcur->next;
}
printf("\n");
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
注意：插入数据之前，链表必须初始化为只有一个结点的情况下
不改变哨兵位的位置，因此传一级指针即可
尾插
//尾插
void LTPushBack(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead phead->prev newnode
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
头插
//头插
void LTPushFront(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead newnode phead->next
newnode->prev = phead;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
尾删
//尾删
void LTPopBack(LTNode* phead)
{
//链表必须有效并且链表不能为空（只有一个哨兵位）
assert(phead && phead->next != phead);
LTNode* del = phead->prev;
//phead del->prev del
del->prev->next = phead;
phead->prev = del->prev;
//删除del结点
free(del);
del = NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
头删
//头删
void LTPopFront(LTNode* phead)
{
//链表必须有效并且链表不能为空（只有一个哨兵位）
assert(phead && phead->next != phead);
LTNode* del = phead->next;
//phead del del->next
del->next->prev = phead;
phead->next = del->next;
//删除del结点
free(del);
del = NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
查找
//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{
assert(phead && phead->next != phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->date == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
在pos位置之后插入数据
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDateType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
newnode->prev = pos;
newnode->next = pos->next;
pos->next->prev = newnode;
pos->next = newnode;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
删除pos结点
//删除pos结点
void LTErase(LTNode* pos)
{
assert(pos);
//pos->prev pos pos->next
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
销毁
//销毁
void LTDesTroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
三、所有源代码
List.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int LTDateType; //定义双向链表结点的结构 typedef struct ListNode { LTDateType date; struct ListNode* next; struct ListNode* prev; }LTNode; //声明双向链表中提供的方法 //初始化 //void LTInit(LTNode** pphead); LTNode* LTInit(); //打印 void LTPrint(LTNode* phead); //插入数据之前，链表必须初始化为只有一个结点的情况下 // 不改变哨兵位的位置，因此传一级指针即可 //尾插 void LTPushBack(LTNode* phead, LTDateType x); //头插 void LTPushFront(LTNode* phead, LTDateType x); //尾删 void LTPopBack(LTNode* phead); //头删 void LTPopFront(LTNode* phead); //查找 LTNode* LTFind(LTNode* phead, LTDateType x); //在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDateType x); //删除pos结点 void LTErase(LTNode* pos); //销毁 void LTDesTroy(LTNode* phead);
- 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
List.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" //申请结点 LTNode* LTBuyNode(LTDateType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc fail!"); exit(1); } node->date = x; node->next = node->prev = node; return node; } //初始化 //void LTInit(LTNode** pphead) //{ // //给双向链表创建一个哨兵位 // *pphead = LTBuyNode(-1); //} LTNode* LTInit() { LTNode* phead = LTBuyNode(-1); return phead; } //打印 void LTPrint(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { printf("%d->", pcur->date); pcur = pcur->next; } printf("\n"); } //尾插 void LTPushBack(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = LTBuyNode(x); //phead phead->prev newnode newnode->prev = phead->prev; newnode->next = phead; phead->prev->next = newnode; phead->prev = newnode; } //头插 void LTPushFront(LTNode* phead, LTDateType x) { assert(phead); LTNode* newnode = LTBuyNode(x); //phead newnode phead->next newnode->prev = phead; newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; } //尾删 void LTPopBack(LTNode* phead) { //链表必须有效并且链表不能为空（只有一个哨兵位） assert(phead && phead->next != phead); LTNode* del = phead->prev; //phead del->prev del del->prev->next = phead; phead->prev = del->prev; //删除del结点 free(del); del = NULL; } //头删 void LTPopFront(LTNode* phead) { //链表必须有效并且链表不能为空（只有一个哨兵位） assert(phead && phead->next != phead); LTNode* del = phead->next; //phead del del->next del->next->prev = phead; phead->next = del->next; //删除del结点 free(del); del = NULL; } //查找 LTNode* LTFind(LTNode* phead, LTDateType x) { assert(phead && phead->next != phead); LTNode* pcur = phead->next; while (pcur != phead) { if (pcur->date == x) { return pcur; } pcur = pcur->next; } return NULL; } //在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDateType x) { assert(pos); LTNode* newnode = LTBuyNode(x); //pos newnode pos->next newnode->prev = pos; newnode->next = pos->next; pos->next->prev = newnode; pos->next = newnode; } //删除pos结点 void LTErase(LTNode* pos) { assert(pos); //pos->prev pos pos->next pos->next->prev = pos->prev; pos->prev->next = pos->next; free(pos); pos = NULL; } //销毁 void LTDesTroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; while (pcur != phead) { LTNode* next = pcur->next; free(pcur); pcur = next; } free(phead); phead = NULL; }
- 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
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" //测试代码 void test() { //测试初始化 /*LTNode* plist = NULL; LTInit(&plist);*/ LTNode* plist = LTInit(); //测试尾插 LTPushBack(plist, 1); LTPrint(plist); LTPushBack(plist, 2); LTPrint(plist); LTPushBack(plist, 3); LTPrint(plist); LTPushBack(plist, 4); LTPrint(plist); //测试头插 /*LTPushFront(plist, 8); LTPushFront(plist, 7); LTPushFront(plist, 6); LTPushFront(plist, 5); LTPrint(plist);*/ //测试尾删 /*LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist);*/ //测试头删 /*LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist);*/ //测试查找 /*LTNode* find = LTFind(plist, 4); if (find == NULL) { printf("找不到！\n"); } else { printf("找到了！\n"); }*/ //测试在pos位置之后插入数据 /*LTNode* find = LTFind(plist, 4); LTInsert(find, 88); LTPrint(plist);*/ //测试删除pos结点 /*LTNode* find = LTFind(plist, 2); LTErase(find); LTPrint(plist); find = NULL;*/ //测试销毁 LTDesTroy(plist); plist = NULL; } int main() { test(); 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/426548
推荐阅读
相关标签
