数据结构：双向带头链表

🕗 发布于 2024-10-15 17:51 数据结构 链表 c语言 开发语言 算法

概念与结构

双向带头链表，分开来就是双向、带头、链表
之前了解了单链表，他只能由上一个节点找到下一个节点，不能由这个节点找到上一个，这个就是单向。
双向就是它的每一个节点都有两个指针，分别为前指针与后指针，分别指向上一个和下一个节点。头节点的前指针指向尾节点，尾节点的后指针指向头节点（哨兵位）。
带头就是它默认有一个头，也就是哨兵位，他是不存放有效数据的。
具体的结构如图：
在这里插入图片描述
head：哨兵位
dn：有效节点
OK,话不多说，直接开始写代码。

链表实现

对小编个人来说，感觉比单链表还是要简单一些的。
因为一个一个详细介绍篇幅会太长，除了第一个函数以外，其他的就通过画图的方式来帮助理解代码，因为原理是相似的，所以就不再做过多文字介绍了。

源码链接：https://gitee.com/xiao-li-learning-c-language/c-language-exercisehomework/tree/master/10-11%E5%8F%8C%E5%90%91%E5%B8%A6%E5%A4%B4%E9%93%BE%E8%A1%A8/%E5%8F%8C%E5%90%91%E5%B8%A6%E5%A4%B4%E9%93%BE%E8%A1%A8

链表头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType val;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
LTNode* LTNodeInit();//链表初始化
bool LTEmpty(LTNode* phead);//检查是否只剩哨兵位
void LTNodePushBack(LTNode* phead, LTDataType x);//尾插
void LTNodePrint(LTNode* phead);//打印
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopBack(LTNode* phead);//尾删
void LTNodePopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);
//删除指定位置节点
void LTErase(LTNode* pos);
//销毁链表（包含哨兵位）
void LTDesTroy(LTNode** pphead);
void LTDesTroy2(LTNode* phead);//传一级，需要手动将plist置为NULL

链表初始化

初始化就是给我们的结构体赋一个初值，也就是让链表现有一个哨兵位。
这里我们要借助一个函数实现新链表的创建以及赋值
这里哨兵位的存放的是无效地址，我就用-1来代替这个无效数据。

LTNode* BuyNode(LTDataType x)//创建新节点
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
assert(newnode);
newnode->val = x;
newnode->next = newnode->prev = newnode;

return newnode;
}

LTNode* LTNodeInit()//为我们的链表创建哨兵位
{
LTNode* phead = BuyNode(-1);
return phead;
}

链表尾插

思路：
对链表尾插需要的数据有新节点、哨兵位的节点地址、原末尾节点的地址。
通过画图来遍历思考

在这里插入图片描述
如图，做标记的地方是我们代码要实现修改的地方，首先我们先修改新节点的两个指针，这样不会扰乱原链表。
将新节点的prev指向d3，将新节点的next指向head，形成环。
接下来将d3的next指向新节点，将head的prev指向新节点。
代码：

void LTNodePushBack(LTNode* phead,LTDataType x)
{
LTNode* newnode = BuyNode(x);//创建新节点
//新节点指针修改
newnode->next = phead;
newnode->prev = phead->prev;
//修改原末尾节点的next指向
phead->prev->next = newnode;
//修改哨兵位的prev指向
phead->prev = newnode;
}

链表头插

思路：
在这里插入图片描述

void LTPushFront(LTNode* phead, LTDataType x)
{
LTNode* newnode = BuyNode(x);//创建新链表
//修改新节点
newnode->next = phead->next;
newnode->prev = phead;
//原头节点修改
phead->next->prev = newnode;
//哨兵位修改
phead->next = newnode;
}

链表尾删

思路：
在这里插入图片描述
这里主要是修改哨兵位的前指针以及新尾节点的后指针，同时释放原尾节点。
注意：当链表只剩下哨兵位时，是不能再删除的。

代码：

bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next != phead;//判断下一个节点是不是自己，是自己就返回flase，不是就返回ture
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(LTEmpty(phead));//判断是否只剩下哨兵位
//暂存原末尾节点
LTNode* tmp = phead->prev;

phead->prev = phead->prev->prev;
phead->prev->next = phead;
free(tmp);
tmp = NULL;
}

链表头删

思路：
在这里插入图片描述

代码：

void LTNodePopFront(LTNode* phead)
{
assert(phead);
assert(LTEmpty(phead));//检查链表是否只剩下哨兵位

LTNode* tmp = phead->next;//暂存头节点地址
phead->next = phead->next->next;//让哨兵位指向第二个节点
phead->next->prev = phead;//让第二节点前指针指向哨兵位

free(tmp);//释放头节点
tmp = NULL;
}

寻找链表某个元素

思路：
从头节点也就是哨兵位的下一位开始循环，因为链表是循环的，当遍历到哨兵位时，就代表链表已经便利了一遍了。
代码：

LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);

LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->val == x)
{
return pcur;
}
pcur = pcur->next;
}

return NULL;
}

在某个位置之后插入节点

以在第二个节点之后插入为例
思路：
听过上面那个代码找到要插入数据的位置。
比如现在链表里面数据有1，2，3，4；
我要在2后面插入数据，就通过寻找元素2获取位置。
在这里插入图片描述
这样获取位置后就简单了，我们将该位置假设为哨兵位，是不是就跟头插的思路一样了。
代码：

void LTInsert(LTNode* pos, LTDataType x)
{
LTNode* newnode = BuyNode(x);//创建新节点
newnode->next = pos->next;//新节点指针修改
newnode->prev = pos;

pos->next->prev = newnode;//修改指定位置下一个位置的前指针，也就是图例d3
pos->next = newnode;//修改指定位置的后指针
}

删除指定位置节点

还是以删除d2为例
思路：在这里插入图片描述

这个就很简单了，我们通过寻找元素获取地址进行传参，因为这是双向链表，我们可以通过它找到他前后的节点进行修改，修改完后我们直接释放这个节点的空间就行。
代码：

void LTErase(LTNode* pos)
{
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}

销毁链表

从头节点遍历链表依次释放空间，然后释放哨兵位的空间，将指向哨兵位的指针置为NULL。

传参二级指针

void LTDesTroy(LTNode** pphead)
{
assert(pphead&&*pphead);
LTNode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
LTNode* tmp = pcur;
pcur = pcur->next;
free(tmp);
}
free(pcur);//这时pcur存放的就是哨兵位的地址
*pphead = NULL;//这里*pphead就是主程序里存放哨兵位地址的指针
pcur = NULL;
}

一级指针传参

因为一级指针传参只能通过这个指针找到所有的节点释放空间，但是无法对这个一级指针的实参进行修改，所以我们就需要在主程序里面对plist进行置空操作。

void LTDesTroy2(LTNode* phead)//传一级，需要手动将plist置为NULL
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* tmp = pcur;
pcur = pcur->next;
free(tmp);
}
free(pcur);
pcur = NULL;
}

打印链表有效数据

思路：
从头节点的位置进行遍历，依次打印有效数据，当指针回到哨兵位就结束循环。
代码：

void LTNodePrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
printf("plist->");
while (pcur!= phead)
{
printf("%d->", pcur->val);
pcur = pcur->next;
}
printf("plist->...\n");
}

代码测试

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include"list.h"

void test1()
{
LTNode* plist=LTNodeInit();
LTNodePrint(plist);
//LTNodePushBack(plist, 1);
LTPushFront(plist, 1);
LTNodePrint(plist);
//LTNodePushBack(plist, 2);
LTPushFront(plist, 2);
LTNodePrint(plist);
//LTNodePushBack(plist, 3);
LTPushFront(plist, 3);
LTNodePrint(plist);
//LTNodePushBack(plist, 4);
LTPushFront(plist, 4);
LTNodePrint(plist);

printf("\n");

LTNodePopFront(plist);
LTPopBack(plist);
LTNodePrint(plist);
LTNodePopFront(plist);
LTPopBack(plist);
LTNodePrint(plist);
LTPopBack(plist);
LTNodePopFront(plist);
LTNodePrint(plist);

LTNodePushBack(plist, 1);
LTNodePushBack(plist, 2);
LTNodePushBack(plist, 3);
LTNodePushBack(plist, 4);

LTNode* ret=LTFind(plist, 3);
if (ret)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
LTInsert(ret, 6);
LTNodePrint(plist);

LTDesTroy2(plist);
plist = NULL;

}
int main()
{
test1();
return 0;
}

在这里插入图片描述
结果如图，代码运行正常，plist是创建的哨兵位。

除了这些之外还有其他的一些可实现功能，这里就不再做过多介绍，基本原理都是差不多的。
谢谢各位观看，编写不易，赏赐一个三连吧。

原文地址：https://blog.csdn.net/qq_71391318/article/details/142865034

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【Kubernets】容器网络基础二：通讲CNI（Container Network Interface）容器网络接口实现方案
下一篇：Spring webflux

python对weedfs的操作
WeedFS（Weed File System）是一个开源的分布式文件系统，由Go语言编写，旨在解决海量文件存储和访问的问题。它采用了类似于Hadoop HDFS的分布式文件系统架构，但具有更高的性能
阅读更多2024-10-15
京存非编存储走进中央民族大学
京存高性能中央存储已成功应用于多所高校，以及非编剪辑和影视后期制作公司，如北京大学、北京外国语大学等知名高校，中国电影资料馆、可牛影视、猿人影视、天光创影等影视制作公司。它采用独立自主开发的RAID智
阅读更多2024-10-15
【系统架构设计师】专题：计算机网络考点梳理
TCP/IP是个协议族，主要包括因特网协议 (IP)、传输控制协议 (TCP)、用户数据报协议 (UDP)、虚拟终端协议 (TELNET)、文件传输协议 (FTP)、电子邮件传输协议 (S
阅读更多2024-10-15
2024.10.14 软考学习笔记
uml
阅读更多2024-10-15
初识CNN
3为一块,3个通道的矩阵分别与flter内积得到三个值，再相加，得到一个值后，再加上一个bias,然后输出，结果见上图，不同的通道filter不同，即一个filter是一个卷积内核，3。如图所示的是最
阅读更多2024-10-15
【Linux】进程--详细解释进程
1、运行：进程是pcb+对应的代码和数据有一个运行队列。
阅读更多2024-10-15
【最新华为OD机试E卷-支持在线评测】补种未成活胡杨(100分)多语言题解-(Python/C/JavaScript/Java/Cpp)
🍭 大家好这里是，一枚热爱算法的程序员💻 ACM金牌🏅️团队｜大厂实习经历｜多年算法竞赛经历✨ 本系列打算持续跟新的多语言AC题解🧩 大部分包含PythonCJavascriptJavaCpp
阅读更多2024-10-15
PL/SQL Developer如何连接Oracle数据库（汉化）
PL/SQL Developer是一种用于Oracle数据库开发的集成开发环境（IDE）。它提供了一个可视化的界面，使开发人员能够方便地编写、调试和执行PL/SQL代码。
阅读更多2024-10-15
int QSqlQuery::size() const
注意：对于非查询语句，将返回-1（isSelect()返回false）为了确定非查询语句影响的行数，使用numRowsAffected().（如果大小不能被决定或者数据库不支持报告查询的大小信息
阅读更多2024-10-15
Unity性能优化
当游戏开发使用传统的OPP（面向对象编程）面对大量的Game object时FPS会显著降低，而使用Dots（）性能依旧很好。
阅读更多2024-10-15