文章目录
- 双向循环带头节点链表 —— C语言
- 每博一文案
- 双向循环带头节点链表
- 双向循环带头节点链表的实现
- 双向循环带头节点链表的结构体定义
- 创建双向链表的节点
- 创建头节点
- 尾插法
- 打印链表
- 头插法
- 尾删法
- 头删法
- 查找第一个数值为 x 的节点的地址
- 在值为 x 的节点前插入数据
- 在把数值为 x 的节点删除
- 将第一个数值为 x 的节点修改
- 清空链表
- List.h 的完整代码
- List.c的完整代码：链表的功能集合
- Test.c 头文件，测试
- 最后
每博一文案
有些事即便到最后不如人意，但只要两个人相处的那些日子，没有太多遗憾，就已经足够了。
没有谁能一直陪着谁，遇见即使上上签，爱情不等于白头偕老，结果本身并无意义。
有意义的是，那些在平淡生活生出花儿的日子。
这世上并非每一件事都能分出对错，应该与不应该，有些事就是没有答案，
只有结果，无论结果怎样，希望你都能接受这最后的结局，折磨你的从来不是
谁的突然离去，而是你心存幻想的永远。
万事万物皆可治愈，
你为你不放过自己，如果相守太难，
那就祝你成也快乐，福也快乐，
见不见都快乐，拥不拥有都是幸福。
———————————— 一禅心灵庙语
双向循环带头节点链表
- 链表总的来说一共可以说是有 八 种的：
- 其中这八种中比较复杂的就是：双向带头节点循环链表 的结构了，虽然它是比较复杂的，但是使用代码实现起来我们会不知不觉的发现，它反而比较简单，设计到的实现的算法，并不是难以理解
- 双向带头节点循环链表 结构如下：
- 特殊的情况 ：只有头节点：空链表 的表示图：
- 空链表 ：它的 前驱 和 后继 存放的地址都是它 本身
- 我们用 物理地址 的方式去理解，不用什么所谓的逻辑结构什么 箭头 去理解：
- 所谓的 前驱 就是：存放着 前 一个节点的地址(指针)
- 所谓的 后继 就是：存放着 后 一个节点的地址(指针)
- 我认为就是通过物理上的角度，更容易理解，明白，其中的结构
双向循环带头节点链表的实现 双向循环带头节点链表的结构体定义
typedef int LTDataType; // 链表存放的数据类型
// 自定义链表的结构体类型
typedef struct ListNode
{
LTDataType data; // 链表的数值
struct ListNode* prev; // 链表的前驱节点的的地址
struct ListNode* next; // 链表的后继节点的地址
}ListNode;
- 注意事项:
我们在定义链表的结构体的时候，要带上对应的 指针(地址) (ListNode prev)*
不要写成了 (ListNode prev) ,少了一个指针的标识，其效果是不一样的，少了 指针的话，（结构体中套结构体了。“套中套” ，结构体中结构体，再再结构体中还有结构体）,先说其中一点，其该没有指针的结构体的 大小是多少 ，你可以知道吗？，是不是，不能知道多少？
而我们加上了，指针(地址) ，就不一样了，指针(地址) 的大小，32位 4个字节，64位 8个字节的大小，这些都是固定的。
头节点 不要作什么所谓的 记录数据个数，有些书籍上会，这么做是不合理的，因为: 当我们存放的数据类型是 char double 的时候，就是出现错误了，当我们存放的数据是 char 类型的时候，如果 头节点作为记录数据个数的话，问题就出现了 char 可以存放的最大的正整数是 127，同样如果我们存放的数据的类型是 double ，我们解引用记录类型是 double 这能行吗？
创建双向链表的节点
// 创建节点
static 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; // 前驱
phead->data = 0; // 头节点不存放数值
return phead;
}
尾插法
- 尾插法图示：
- 因为双向循环带头节点的特性：尾节点的地址 等于 头节点的前驱
- 我们不要直接使用原来的节点进行，拼接 ，而是使用临时拷贝进行拼接使用，这样就不用太在意拼接的顺序 而导致链表的丢失了
- 我们该可以使用关键字 const，对变量进行不可修改的限定提高，以及断言 assert 代码的安全性
// 尾插法
void ListPushBacck(ListNode* phead, const LTDataType x)
{
ListNode* newNode = BuyListNode(x); // 生成节点
ListNode* tail = phead->prev; // 尾节点
tail->next = newNode;
newNode->prev = tail;
newNode->next = phead;
phead->prev = newNode;
}
打印链表
- 注意: 是双向带头节点的循环链表，所以
- 其 头节点 是没有数值存放的，不要打印出来，是从 首节点 开始打印的；
- 循环遍历完的条件是 等于头节点 ，因为是循环链表吗？
- 链表为 空 ，断言就不用打印了
// 打印链表
void ListPrint(ListNode* phead)
{
assert(phead); // 链表不为空
ListNode* tail = phead->next; // 注意:是从首节点开始的，不是头节点
while (tail != phead) // 跳出循环的条件，
{
printf("%d ", tail->data);
tail = tail->next; // 移动节点
}
printf("n");
}
头插法
- 注意: 在进行 头插 的存在一个问题就是，如果插入改道，拼接 的顺序的出现了问题，可能会将整个链表丢失了，所以，为了避免这样的错误的发生，我们可以对节点的地址，进行 拷贝 复制一份，就不会因为顺序的原因：而导致链表丢失的问题了
- 头插法视图：
// 头插法
void ListPushFront(ListNode* phead, const LTDataType x)
{
assert(phead); // 链表不可以为空
ListNode* newNode = BuyListNode(x); // 生成节点
ListNode* cur = phead; // 头节点的拷贝
ListNode* phNext = phead->next; // 首节点的拷贝
cur->next = newNode;
newNode->prev = cur;
newNode->next = phNext;
phNext->prev = newNode;
}
尾删法
- 注意: 只剩 头节点 的时候，我们不可以把头节点给删除了，删除了头节点，我们还怎么插入数据呀！
- 空 链表不用，删除了
- 使用关键字 free 释放空间(内存)
- 尾删法 操作示图
// 尾删法
void ListPopBack(ListNode* phead)
{
assert(phead); // 空链表，不用删除
assert(phead->next != phead); // 头节点不可以删除
ListNode* tail = phead; // 头节点的拷贝
ListNode* coprBack = phead->prev; // 尾节点的拷贝
ListNode* prev = coprBack->prev;
prev->next = phead;
phead->prev = coprBack;
free(coprBack); // 释放内存空间
coprBack = NULL; // 手动置为 NULL;
}
头删法
- 同样 空 链表不用删除了
- 虽然字面意思是从头开始删除，但不是删除我们的 头节点 ，而是 首节点
- 注意: 当只剩 头节点 的时候，我们不可以把头节点给删除了，删除了头节点，我们还怎么插入数据呀！
- 使用关键字 free 释放空间(内存)
- 头删法 操作示图
// 头删法
void ListPopFront(ListNode* phead)
{
assert(phead); // 不为空链表
assert(phead->next != phead); // 头节点不可以删除
ListNode* tail = phead->next; // 首节点的的地址的拷贝
ListNode* copyPrev = tail->next;
phead->next = tail->next;
copyPrev->prev = phead;
free(tail); // 释放首节点的内存空间
tail = NULL; // 手动置为 NULL;
}
查找第一个数值为 x 的节点的地址
- 空 链表就不用找了
- 我们直接循环遍历该双向链表，判断
- 注意: 是从 首节点 开始，不是 头节点 开始的
- 循环的结束条件是：等于头节点
// 查找第一个数值为 x 的节点的地址
static ListNode* listFind(ListNode* phead, const LTDataType x)
{
assert(phead); // 链表不为 “空”
ListNode* cur = phead->next; // 首节点
while (cur != phead)
{
if (x == cur->data)
{
return cur; // 找到了，返回该地址
}
cur = cur->next; // 移动节点
}
return NULL; // 没有找到，返回 NULL;
}
在值为 x 的节点前插入数据
- 同样空链表不进行该操作
- 首先需要判断该数值 x 是否存在于链表中，在即可插入，不在，不用插入
- 该插入方法的操作示图
// 在值为 x 的节点前插入数据节点
void ListInsert(ListNode* pos, const LTDataType x, const LTDataType num)
{
if (listFind(pos, x) == NULL)
{
printf("不存在%d，不用找了", x);
}
ListNode* tail = listFind(pos, x); // 该节点的地址
ListNode* prev = tail->prev; // 该节点的前驱节点
ListNode* newNode = BuyListNode(num);
tail->prev = newNode;
newNode->next = tail;
prev->next = newNode;
newNode->prev = prev;
}
- 注意: 如果你没有，我上面的对原来的节点的地址，就行拷贝，复制 ，防止丢失，整个链表
- 就需要对插入的 顺序 进行规定，不要把链表丢了
- 插入顺序 的步骤：
在把数值为 x 的节点删除
- 同样空链表不进行该操作
- 首先需要判断该数值 x 是否存在于链表中，存在才可以被删除
- 删除方法 的示图：
// 删除值为 x 的节点
void ListErase(ListNode* pos, const LTDataType x)
{
if (NULL == listFind(pos, x))
{
printf("删除失败，%d不存在", x);
return;
}
ListNode* tail = listFind(pos, x); // 该节点的地址
ListNode* prevTail = tail->prev; // 该节点的前驱的拷贝，复制
ListNode* nextTail = tail->next; // 该节点的后继的拷贝，复制
prevTail->next = tail->next;
nextTail->prev = tail->prev;
free(tail); // 释放内存空间
tail = NULL; // 手动置为 NULL;
}
将第一个数值为 x 的节点修改
- 空链表，不用操作了
- 判断该数值的节点，是否存在，存在修改，不存在，不用改
// 将第一个数值为 x 的节点修改
void ListUpdate(ListNode* pos, const LTDataType x, const LTDataType num)
{
if (listFind(pos, x) == NULL)
{
printf("不用找了 %d,该数值不存在n", x);
return; // 停止执行
}
ListNode* tail = listFind(pos, x); // 该数值的节点的地址
tail->data = num; // 数值更新
}
清空链表
- 首先把首节点后面的一个释放
- 最后再把头节点释放
- 这里如果你先从头节点，删除了，整个链表就丢失了，所以，我们从首节点开始删除，最再删除头节点
// 清空链表
void ListDeatory(ListNode* phead)
{
assert(phead); // 空链表，不动
ListNode* cur = phead->next; // 首节点的拷贝
while (cur!= phead)
{
ListNode* tail = cur->next; // 拷贝复制
free(cur); // 释放该节点的内存空间
cur = tail ; // 移动节点
}
free(phead); // 最后释放头节点的内存空间
phead = NULL;
printf("清空成功");
}
List.h 的完整代码
#pragma once #include#include #include // 断言 #include typedef int LTDataType; typedef struct ListNode { LTDataType data; // 数据 struct ListNode* next; // 双链表的后继 struct ListNode* prev; // 双链表的前驱 }ListNode; extern void Test1(); // 测试的声明，声明使用 extern 代码好习惯 extern void Test2(); // 测试的声明 extern ListNode* ListInit(); // 创建头节点，就是所谓的哨兵 extern ListNode* BuyListNode(const LTDataType x); // 为双向循环链表，创建单节点，开辟空间 extern void ListPushBack( ListNode* phead, const LTDataType x); // 尾插法 extern void ListPrint(const ListNode* phead); // 打印双向循环链表 extern void ListPushFront(const ListNode* phead, const LTDataType x); // 头插法 extern void ListPopBack(const ListNode* phead); // 尾删法 extern void ListPopFront(const ListNode* phead); // 头删法 extern void ListInsert(const ListNode* pos, const LTDataType x, const LTDataType num); // 在值为 x 的节点前插入数据 extern void ListErase(const ListNode* pos, const LTDataType x); // 删除值为 x 的节点 extern void ListUpdate(const ListNode* pos, const LTDataType x, const LTDataType num); // 将第一个数值为 x 的节点修改 extern void ListDestory(const ListNode* phead); // 清空链表
List.c的完整代码：链表的功能集合
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
// 创建头节点，就是所谓的哨兵位
ListNode* ListInit()
{
ListNode* phead = BuyListNode(0);
phead->next = phead; // 头节点的前驱
phead->prev = phead; // 头节点的后继
phead->data = 0; // 头节点数值位置为空，啥也不放
return phead;
}
// 为双向循环链表，创建单节点，开辟空间
ListNode* BuyListNode(const LTDataType x)
{
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->next = NULL;
newNode->prev = NULL;
newNode->data = x;
return newNode;
}
// 尾插法，找到尾节点，注意循环插入
void ListPushBack(ListNode* phead,const LTDataType x)
{
ListNode* newNode = BuyListNode(x); // 生成节点
ListNode* tail = phead->prev; // 拷贝头节点，代替头节点的，移动，这样就不必在意顺序了
tail->next = newNode;
newNode->prev = tail;
newNode->next = phead;
phead->prev = newNode;
}
// 打印双向循环链表
void ListPrint(const ListNode* phead)
{
assert(phead); // 断言该链表不为“空”为空不用找了
ListNode* cur = phead->next; // 拷贝首节点，代替首节点的移动,注意 头节点不用打印，从首节点开始
while (cur != phead) // 判断遍历完
{
printf("%d ", cur->data);
cur = cur->next; // 移动节点
}
printf("n");
}
// 头插法
void ListPushFront(const ListNode* phead, const LTDataType x)
{
assert(phead); // 头节点，不可以为 “空”
ListNode* cur = phead; // 头节点的拷贝
ListNode* phNext = phead->next; // 首节点的拷贝
ListNode* newNode = BuyListNode(x); // 所需插入的节点的创建
cur->next = newNode;
newNode->prev = cur;
newNode->next = phNext;
phNext->prev = newNode;
}
// 尾删法
void ListPopBack(const ListNode* phead)
{
assert(phead); // 断言头节点不可以为空
assert(phead->next != phead); // 当只有头节点时不能删除
ListNode* tail = phead->prev; // 头节点的前驱就是尾节点
ListNode* prev = tail->prev; // 尾节点的前驱节点；
ListNode* copyPhead = phead; // 头节点的拷贝
prev->next = phead;
copyPhead->prev = prev;
free(tail); // 释放空间内存
tail = NULL; // 手动置为 NULL
}
// 头删法
void ListPopFront(const ListNode* phead)
{
assert(phead); // 头节点不能为空
assert(phead->next != phead); // 当只剩下头节点的时候，不能删除
ListNode* copyPhead = phead; // 头节点的拷贝
ListNode* tail = phead->next; // 首节点的拷贝
tail->prev = phead;
copyPhead->next = tail->next;
free(tail); // 释放节点，空间内存
tail = NULL; // 手动置为NULL
}
// 查找值为 x 的节点的地址
static ListNode* listFind(const ListNode* phead, const LTDataType x)
{
assert(phead); // 断言该链表的头节不为 “空”
ListNode* cur = phead->next; // 首节点开始
while (cur != phead)
{
if (x == cur->data)
{
return cur; // 找到了，返回该地址
}
cur = cur->next; // 移动节点
}
return NULL; // 没有找到，返回 NULL;
}
// 在值为 x 的节点前插入数据
void ListInsert(const ListNode* pos, const LTDataType x,const LTDataType num)
{
if (listFind(pos, x) == NULL)
{
printf("不用找了 %d，该数值不存在n",x);
return;
}
// 该节点的数值，存在
ListNode* tail = listFind(pos,x); // 该节点的地址
ListNode* prev = tail->prev; // 该节点位置的前驱节点的地址
ListNode* newNode = BuyListNode(num); // 创建节点
tail->prev = newNode;
newNode->next = tail;
prev->next = newNode;
newNode->prev = prev;
}
// 删除值为 x 的节点
void ListErase(const ListNode* pos,const LTDataType x)
{
if (listFind(pos, x) == NULL)
{
printf("不用找了 %d，该数值不存在n", x);
return;
}
ListNode* tail = listFind(pos, x); // 该节点的地址
ListNode* prevTail = tail->prev; // 该节点的前驱的地址
ListNode* nextTail = tail->next; // 该节点的后继的地址
prevTail->next = tail->next;
nextTail->prev = tail->prev;
free(tail); // 释放空间内存
tail = NULL; // 手动置为NULL
}
// 将第一个数值为 x 的节点修改
void ListUpdate(const ListNode* pos, const LTDataType x, const LTDataType num)
{
if (listFind(pos, x) == NULL)
{
printf("不用找了 %d，该数值不存在n", x);
return;
}
ListNode* tail = listFind(pos, x); // 该节点的地址
tail->data = num;
}
// 清空链表
void ListDestory(const ListNode* phead)
{
assert(phead); // 断言 头节点不为“空”
ListNode* cur = phead->next; // 首节点开始
while (cur != phead) // 循环遍历
{
ListNode* tail = cur->next;
free(cur);
cur = tail; // 移动指针
}
// 最后把首节点也删了
free(phead);
phead = NULL;
printf("删除成功");
}
Test.c 头文件，测试
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
int main()
{
Test1(); // 测试方法 一
Test2(); // 测试方法 二
return 0;
}
void Test1()
{
ListNode* pList = ListInit(0); // 创建定义头节点
ListPushBack(pList, 9); // 尾插法
ListPushBack(pList, 99); // 尾插法
ListPushBack(pList, 999); // 尾插法
ListPrint(pList); // 打印该双向循环链表
ListPushFront(pList, 100); // 头插法
ListPushFront(pList, 10); // 头插法
ListPrint(pList); // 打印该双向循环链表
ListPopBack(pList); // 尾删法
ListPopBack(pList); // 尾删法
ListPrint(pList); // 打印该双向循环链表
ListPopFront(pList); // 头删法
ListPopFront(pList); // 头删法
ListPrint(pList); // 打印该双向循环链表
}
void Test2()
{
ListNode* pList = ListInit(0); // 创建定义头节点
ListPushBack(pList, 9); // 尾插法
ListPushBack(pList, 99); // 尾插法
ListPushBack(pList, 999); // 尾插法
ListPrint(pList); // 打印该双向循环链表
ListInsert(pList, 9, 100); // 在值为 x 的节点前插入数据
ListInsert(pList, 999, 1000); // 在值为 x 的节点前插入数据
ListPrint(pList); // 打印该双向循环链表
ListInsert(pList, 9999, 10000); // 在值为 x 的节点前插入数据
ListPrint(pList); // 打印该双向循环链表
ListErase(pList, 9); // 删除值为 x 的节点
ListErase(pList, 100); // 删除值为 x 的节点
ListPrint(pList); // 打印该双向循环链表
printf("**********************n");
ListUpdate(pList, 99, 100); // 将第一个数值为 x 的节点修改
ListUpdate(pList, 1000, 9); // 将第一个数值为 x 的节点修改
ListPrint(pList); // 打印该双向循环链表
ListDestory(pList); // 清空链表
ListPrint(pList); // 打印该双向循环链表
}
最后
限于自身水平，其中存在的错误，希望大家给予指教，韩信点兵 —— 多多益善，谢谢大家，后会有期，江湖再见！
