-
数据结构——带头双向循环链表
呀哈喽，我是结衣。
前言
说到链表前面我们讲了单链表，但是链表可不止一种，要分类的话。链表可以分为带头或不带头，单向或双向，循环或者不循环，也就是说链表一共应该是有8种结构的，我们上次讲的链表就是不带头单向不循环链表。是链表中结构最简单的一种。
我们在来简单的解释一下两种链表把
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。链表的实现
前边讲了那么多，最重要的还是要自己能把链表给实现了。下面就是实现的教学了。
创建不同文件
创建3个文件，分别要实现的功能为函数的声明，函数的定义，以及测试。目的是方便后续的增删查改。
结构体的创建
prev表示上一个节点，next表示下一个节点。
函数的声明
和单链表的函数声明差不多，都是头删，头插，尾插，尾删，打印等等…
我们先函数的声明先写完，后面再对他们挨个实现。#define _CRT_SECURE_NO_WARNINGS #include#include #include typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos); - 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
写完函数声明接下来就是函数的实现了。
函数的实现
函数的实现写在list.c文件里面
我们先来讲头节点的创建。头节点是链表的头部且不会存储有效的数据。头节点的创建
// 创建返回链表的头结点. ListNode* ListCreate() { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); head->data = -1;//可以随便存一个数据，在后续的操作中不会用到头节点的数据。 head->prev = head; head->next = head;//prev和next都要指向本身，以实现循环。 return head; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
写完头节点的创建，我们还要写一个打印函数，为了让后续的操作更加直观。
打印函数的实现
// 双向链表打印 void ListPrint(ListNode* pHead) { ListNode* cur = pHead->next; printf("phead"); while (cur != pHead) { printf("%d<=>", cur->data); cur = cur->next; } printf("phead\n"); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
cur!=pHead，目的是为了不打印头节点。
下面我们要写一个插入函数，才能直观的观察。所以我们接下来写尾插函数。尾插函数的实现
画图解释// 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* newnode = CreatNode(x); ListNode* cur = pHead; ListNode* tail = pHead->prev; tail->next = newnode; newnode->prev = tail; cur->prev = newnode; newnode->next = cur; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
写到尾插函数，我们又要写一个新节点的创建函数
ListNode* CreatNode(LTDataType x) { ListNode* newnode = (ListNode* )malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
欧克，写完了开始打印测试。
看上去是成功了，那就说明没什么问题了，有问题后续再检查。头插函数的实现
尾插写完当然就是头插了。
画图解释// 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* newnode = CreatNode(x); ListNode* cur = pHead; ListNode* next = pHead->next; cur->next = newnode; newnode->prev = cur; newnode->next = next; next->prev = newnode; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
接下来测试看看。
依旧没有问题。尾删函数的实现
删除后要记得free哦
// 双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead->next != pHead);//当只有头节点时报错 ListNode* cur = pHead; ListNode* tail = pHead->prev; cur->prev = tail->prev; tail->prev->next = cur; free(tail); tail = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
测试
我们先删一些，再全部删完，再多删一个分别测试。
从这三张图片我们也可以看出来，代码是没有问题的。（在这里我悄悄改了一下打印函数的代码，看出来了吗？）头删函数的实现
要记得free哦
// 双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead->next != pHead); ListNode* first = pHead->next; pHead->next = first->next; first->next->prev = pHead; free(first); first = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
下面再测试一下，有没有问题。
同样也是没有问题的。销毁函数的实现
为什么就到销毁了呢？当然是想把剩下的指定位置的增删查改当成作业咯。
// 双向链表销毁 void ListDestory(ListNode* pHead) { ListNode* cur = pHead->next; while (cur != pHead) { ListNode* next = cur->next; free(cur); cur = NULL; cur = next; } //最后free pHead free(pHead); pHead = NULL; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
就这样结束咯。
下面我们把代码都贴出来，（也包括查找函数和指定位置的增删查改函数）代码
list.h
#define _CRT_SECURE_NO_WARNINGS #include#include #include typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* prev; struct ListNode* next; }ListNode; // 创建返回链表的头结点. ListNode* ListCreate(); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos); - 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
list.c
#define _CRT_SECURE_NO_WARNINGS #include "list.h" ListNode* CreatNode(LTDataType x) { ListNode* newnode = (ListNode* )malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } // 创建返回链表的头结点. ListNode* ListCreate() { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); head->data = -1;//可以随便存一个数据，在后续的操作中不会用到头节点的数据。 head->prev = head; head->next = head;//prev和next都要指向本身，以实现循环。 return head; } // 双向链表打印 void ListPrint(ListNode* pHead) { ListNode* cur = pHead->next; printf("phead<=>"); while (cur != pHead) { printf("%d<=>", cur->data); cur = cur->next; } printf("phead\n"); } // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* newnode = CreatNode(x); ListNode* cur = pHead; ListNode* tail = pHead->prev; tail->next = newnode; newnode->prev = tail; cur->prev = newnode; newnode->next = cur; } // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* newnode = CreatNode(x); ListNode* cur = pHead; ListNode* next = pHead->next; cur->next = newnode; newnode->prev = cur; newnode->next = next; next->prev = newnode; } // 双向链表尾删 void ListPopBack(ListNode* pHead) { assert(pHead->next != pHead);//当只有头节点时报错 ListNode* cur = pHead; ListNode* tail = pHead->prev; cur->prev = tail->prev; tail->prev->next = cur; free(tail); tail = NULL; } // 双向链表头删 void ListPopFront(ListNode* pHead) { assert(pHead->next != pHead); ListNode* first = pHead->next; pHead->next = first->next; first->next->prev = pHead; free(first); first = NULL; } // 双向链表销毁 void ListDestory(ListNode* pHead) { ListNode* cur = pHead->next; while (cur != pHead) { ListNode* next = cur->next; free(cur); cur = NULL; cur = next; } //最后free pHead free(pHead); pHead = NULL; } // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x) { ListNode* cur = pHead->next; if (x == -1) { return NULL; } while (cur != pHead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { ListNode* newnode = CreateNode(x); ListNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } // 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = 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
test.c
#define _CRT_SECURE_NO_WARNINGS #include "list.h" void test1() { ListNode* head = ListCreate();//头节点的创建 ListPushBack(head, 1); ListPushBack(head, 2); ListPushBack(head, 3); ListPushBack(head, 4); ListPrint(head); ListPushFront(head, 5); ListPushFront(head, 6); ListPushFront(head, 7); ListPrint(head); }void test2() { ListNode* head = ListCreate();//头节点的创建 ListPushBack(head, 1); ListPushBack(head, 2); ListPushBack(head, 3); ListPushBack(head, 4); ListPrint(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPopFront(head); ListPrint(head); } int main() { test2(); 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
完
-
相关阅读:
〈西游记〉中所有插曲、主题曲
Java项目——表白墙（前后端连接+数据库存储）
01 【基础语法与基本数据类型】
microk8s拉取pause镜像卡住
概率论中的几个重要悖论问题
axios入门
03Java基础语法：注释/关键字/字面量/变量
计算机毕业设计springboot+vue+elementUI汽车车辆充电桩管理系统
Docker简介
SpringBoot配置外部Tomcat项目启动流程源码分析（上）
- 原文地址：https://blog.csdn.net/2303_79015671/article/details/134390236
