双向链表（带头双向循环链表）的实现

ops/2024/11/15 0:38:04/

前言：前面实现的单向链表，全称是不带头单向不循环链表。这里实现带头双向不循环链表，比单向链表好实现一点。

目录

链表的分类

单向链表与双向链表的比较：

 双向链表的节点的定义：

多文件实现：

List.h来看一下需要实现的函数接口：

List.c的各个函数的实现：

创建节点的函数：

链表的初始化：

尾插：

头插：

打印链表：

尾删： 

头删：

查找

插入（在指定位置之后插入）：

删除指定位置的数据：

销毁链表：

实现双链表的全部源码：

List.h：

List.c：

test.c的主要功能是测试个接口，所以这里的代码仅供参考哦！

结语：

链表的分类

将是否带头，单向还是双向，是否循环，随机组合一共有八种类型，只要会写不带头单向不循环链表和带头双向循环链表这两个链表，其他的链表实现起来就简单多了。

单向链表与双向链表的比较：

单向链表双向链表
是否带头不带头带头（有哨兵位）
单向还是双向单向双向
是否循环不循环循环

逻辑图解比较：

 双向链表的节点的定义：

typedef int LTTypeData;
typedef struct ListNode
{LTTypeData data;struct ListNode* prev;struct ListNode* next;
}LTNode;

prev指向前一个节点

next指向下一个节点

data存储数据

为什么tydef一个新的数据类型是为了方便以后修改存储的数据类型。

多文件实现：

文件名称负责的功能
List.h链表的定义，需要用到库里的头文件的包含，链表需要实现函数的声明。
List.c链表函数的实现
test.c测试接口（这里大家可以自己测，自己写）

这里的建议是每写一个接口就测试一个接口，省得全写完在测试，有一堆麻烦，还没开始解决麻烦，就先把自己的心态搞崩了。

List.h来看一下需要实现的函数接口：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTTypeData;
typedef struct ListNode
{LTTypeData data;struct ListNode* prev;struct ListNode* next;
}LTNode;//初始化链表
void LTInite(LTNode** pphead);
//尾插
void LTPushBack(LTNode* phead, LTTypeData x);
//头插
void LTPushFront(LTNode* phead, LTTypeData x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//打印链表中的数据
void LTPrint(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTTypeData x);
//在指定位置之后插入
void LTInsert(LTNode* pos, LTTypeData x);
//删除指定位置的数据
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);

List.c的各个函数的实现：

因为会频繁的创建新的节点，这里直接将创建新的节点分装成一个函数。

创建节点的函数：

LTNode* LTBuyNode(LTTypeData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}

注意这里创建出的节点的next和prev指针都指向自己。

图解：

链表的初始化：

void LTInite(LTNode** pphead)
{assert(pphead);//链表不能无效*pphead = LTBuyNode(-1);
}

这里*pphead指向的节点为头结点（哨兵位），哨兵位的数据为无用的数据。

尾插：

void LTPushBack(LTNode* phead, LTTypeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

为什么参数是一级指针而不是二级指针？

在单链表时尾插需要传二级指针是因为需要改变指针变量phead的值；而在双向链表中有哨兵位，改变的是哨兵位的prev和next指针的值，所以不需要传二级指针。

注意修改顺序：先改newnode的prev和next，再改原链表的尾节点的next（指向新的节点）和头节点的prev（指向新的节点）

 图解：

注意这里2和3不能调换顺序，如果调换顺序，那么prev->next就找不到原来链表的尾节点了。

头插：

void LTPushFront(LTNode* phead, LTTypeData x)
{assert(phead);//防止链表无效LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

 注意：还是顺序问题：最后两句不能调换顺序，否则，phead->next就指向的不是原链表的第一个节点，就找不到原链表的第一个节点了。

打印链表：

void LTPrint(LTNode* phead)
{assert(phead);//防止链表无效LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

这里注意循环结束的标志：

当pcur指向哨兵位时，循环结束。

看一下打印效果：

#include "List.h"
void test1()
{LTNode* plist = NULL;LTInite(&plist);LTPushBack(plist, 1);LTPrint(plist);LTPushBack(plist, 2);LTPrint(plist);LTPushBack(plist, 3);LTPrint(plist);LTPushFront(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);
}
int main()
{test1();
}

效果展示： 

尾删： 

void LTPopBack(LTNode* phead)
{//链表不能为空，不能无效assert(phead && phead->next != NULL);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

这里需要修改的链表的地方：尾节点的前一个节点的next和头节点的prev

步骤图解：

注意：这里需要保存下尾节点的地址，防止到最后释放的时候找不到。

头删：

void LTPopFront(LTNode* phead)
{assert(phead && phead->next != NULL);LTNode* del = phead->next;del->next->prev = del->prev;phead->next = del->next;free(del);del = NULL;
}

 跟尾删一样，需要注意的一点就是，需要创建一个新的变量（del）存储需要删除的节点的地址。

查找：

LTNode* LTFind(LTNode* phead, LTTypeData x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

注意下循环结束的条件：跟上面的打印函数一样，需要遍历一遍链表。

返回值：如果没找到返回NULL，找到了就返回那个节点的地址。

插入（在指定位置之后插入）：

void LTInsert(LTNode* pos, LTTypeData x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

注意：最后两句的顺序不能交换。这里的原因上面的头插尾插的原因一样，若交换就找不到pos指向的节点的下一个节点。

删除指定位置的数据：

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

这里没啥好注意的 。

销毁链表：

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = phead->next;while (pcur!=phead){next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

注意：这里用到前后指针：防止释放完一个节点找不到之后的节点。

最后哨兵位释放，因为这里传的是一级指针不会修改test.c 文件中的phead的值，所以调用完该函数后，需要手动的将test.c中的phNULL.

那么,这里为什么不传二级指针呢？

保证接口的一致性，所以传的二级指针。

实现双链表的全部源码：

List.h：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTTypeData;
typedef struct ListNode
{LTTypeData data;struct ListNode* prev;struct ListNode* next;
}LTNode;//初始化链表
void LTInite(LTNode** pphead);
//尾插
void LTPushBack(LTNode* phead, LTTypeData x);
//头插
void LTPushFront(LTNode* phead, LTTypeData x);
//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//打印链表中的数据
void LTPrint(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTTypeData x);
//在指定位置之后插入
void LTInsert(LTNode* pos, LTTypeData x);
//删除指定位置的数据
void LTErase(LTNode* pos);
//销毁链表
void LTDestroy(LTNode* phead);

List.c：

#include "List.h"LTNode* LTBuyNode(LTTypeData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}
void LTInite(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);
}void LTPushBack(LTNode* phead, LTTypeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}void LTPushFront(LTNode* phead, LTTypeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}void LTPopFront(LTNode* phead)
{assert(phead && phead->next != NULL);LTNode* del = phead->next;del->next->prev = del->prev;phead->next = del->next;free(del);del = NULL;
}void LTPopBack(LTNode* phead)
{assert(phead && phead->next != NULL);LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTTypeData x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}void LTInsert(LTNode* pos, LTTypeData x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = phead->next;while (pcur!=phead){next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

test.c的主要功能是测试个接口，所以这里的代码仅供参考哦！

#include "List.h"
void test1()
{LTNode* plist = NULL;LTInite(&plist);LTPushBack(plist, 1);LTPrint(plist);LTPushBack(plist, 2);LTPrint(plist);LTPushBack(plist, 3);LTPrint(plist);LTPushFront(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTNode* find = LTFind(plist, 4);//if (find == NULL)//	printf("没找到\n");//else//	printf("找到了\n");//LTInsert(find, 5);//LTPrint(plist);//LTErase(find);//LTPrint(plist);//LTDestroy(plist);//plist = NULL;
}
int main()
{test1();return 0;
}

结语：

继单链表后的又一个数据结构的实现。

cheers！


http://www.ppmy.cn/ops/5736.html

相关文章

[阅读笔记16][Orca-2]Teaching Small Language Models How to Reason

[阅读笔记16][Orca-2]Teaching Small Language Models How to Reason

接下来是Orca-2&#xff0c;这篇是微软在23年11月发表的论文&#xff0c;在Orca-1的基础上又进行了一些改进。 作者希望教会Orca-2各种推理策略&#xff0c;例如逐步思考、回忆然后回答、先回忆再推理再回答、直接生成回答等等策略。并且Orca-2应该能针对不同任务应该使用最合适…
阅读更多...
js生成pdf

js生成pdf

js生成pdf html->img->pdf 下载依赖 npm install html2canvas npm install jspdf引入依赖 import html2canvas from "html2canvas" import jsPDF from jspdf;代码 const A4_WIDTH 595.28 const A4_HEIGHT 841.89 //参数 html(dom) imgsrc(封面可不加&am…
阅读更多...
从0到1实现RPC | 接入Apollo配置中心

从0到1实现RPC | 接入Apollo配置中心

一、代码实现 添加依赖 添加apollo客户端的依赖和spring配置相关依赖 添加监听器 通过实现ApplicationContextAware接口&#xff0c;获取Spring上下文。 使用ApolloConfigChangeListener注解监听命名空间rpc-demo-provider.yaml和默认的application.properties。 监听逻辑…
阅读更多...
用户的流失预测分析

用户的流失预测分析

项目背景 随着电信行业的持续发展&#xff0c;运营商们开始更加关注如何扩大他们的客户群体。研究表明&#xff0c;获取新客户所需的成本要远高于保留现有客户的成本。因此&#xff0c;在激烈的竞争中&#xff0c;保留现有客户成为了一个巨大的挑战。在电信行业中&#xff0c;…
阅读更多...
UE 录屏自动化上传阿里云OSS

UE 录屏自动化上传阿里云OSS

前言 最近在做一个功能&#xff0c;然后就发现了一个很有趣的东西&#xff0c;虽然在一定程度上属于偷懒&#xff0c;但是在一些短频快的应用中还是很适用的&#xff0c;下面我就针对于这个测试做一些简单的分享&#xff0c;希望帮助到大家&#xff0c;在实际的开发中获得一些灵…
阅读更多...
数据仓库作业五：第8章 关联规则挖掘

数据仓库作业五：第8章 关联规则挖掘

目录 第8章 关联规则挖掘作业题 第8章 关联规则挖掘 作业题 1、设4-项集 X { a , b , c , d } X\{a,b,c,d\} X{a,b,c,d}&#xff0c;试求出由 X X X 导出的所有关联规则。 解&#xff1a; 首先生成项集的所有非空真子集。这包括&#xff1a; { a } , { b } , { c } , {…
阅读更多...
[Java基础揉碎]集合

[Java基础揉碎]集合

目录 集合的理解和好处 数组 集合的理解和好处 继承图 ​编辑 简单实例 Collection接口和常用方法 1) add:添加单个元素 2) remove:删除指定元素 3) contains:查找元素是否存在 4) size:获取元素个数 5) isEmpty:判断是否为空 ​编辑 6) clear:清空 7) addAll:添…
阅读更多...
【Spring进阶系列丨第十篇】基于注解的面向切面编程(AOP)详解

【Spring进阶系列丨第十篇】基于注解的面向切面编程(AOP)详解

文章目录 一、基于注解的AOP1、配置Spring环境2、在beans.xml文件中定义AOP约束3、定义记录日志的类【切面】4、定义Bean5、在主配置文件中配置扫描的包6、在主配置文件中去开启AOP的注解支持7、测试8、优化改进9、总结 一、基于注解的AOP 1、配置Spring环境 <dependencie…
阅读更多...
最新文章

Copyright @ 2022~2023