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

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

目录

链表的分类

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

 双向链表的节点的定义：

多文件实现：

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！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/557533.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

B007-二维数组方法

B007-二维数组方法

目录 二维数组一维数组回顾二维数组定义与创建二维数组的遍历二维数组堆栈图特殊的char数组 方法main方法认识自定义方法调用同类中方法调用不同类中方法方法的参数方法的返回值方法签名方法重载 二维数组 一维数组回顾 二维数组定义与创建 二维数组的遍历 /*** 二维数组:* …
阅读更多...
230元的通配符证书是最便宜的吗

230元的通配符证书是最便宜的吗

随着互联网的发展&#xff0c;越来越多的人认为需要保护用户在网站中传输的数据&#xff0c;因此各个数字证书颁发机构颁发各种数字证书来为网站传输信息进行加密。其中通配符SSL证书是比较受欢迎的一款域名数字证书&#xff0c;这款SSL证书可以用一张证书保护主域名以及主域名…
阅读更多...
为什么选择TikTok直播专线而不是节点？

为什么选择TikTok直播专线而不是节点？

TikTok直播已成为许多商家的重要营销手段&#xff0c;而网络质量作为营销直播效果的关键因素&#xff0c;使得商家们开始应用TikTok直播专线。虽然与节点相比&#xff0c;专线的价格稍高&#xff0c;但更多商家都倾向于选择TikTok直播专线。那么&#xff0c;为什么TikTok直播更…
阅读更多...
Nginx内存池相关源码剖析（一）总览

Nginx内存池相关源码剖析（一）总览

剖析nginx的内存池源码&#xff0c;讲解原理实现以及该内存池设计的应用场景 介绍 Nginx内存池是Nginx为了优化内存管理而引入的一种机制。在Nginx中&#xff0c;每个层级&#xff08;如模板、TCP连接、HTTP请求等&#xff09;都会创建一个内存池进行内存管理。当这些层级的…
阅读更多...
5款开源、美观、强大的WPF UI组件库

5款开源、美观、强大的WPF UI组件库

前言 经常看到有小伙伴在DotNetGuide技术社区微信交流群里提问&#xff1a;WPF有什么好用或者好看的UI组件库&#xff1f;,今天大姚给大家分享5款开源、美观、强大、简单易用的WPF UI组件库。 WPF介绍 WPF 是一个强大的桌面应用程序框架&#xff0c;用于构建具有丰富用户界面…
阅读更多...
mysql 5.7分组报错问题 Expression #1 of ORDER BY clause is not in GROUP BY clause

mysql 5.7分组报错问题 Expression #1 of ORDER BY clause is not in GROUP BY clause

解决方案&#xff1a; select version(), sql_mode;SET sql_mode(SELECT REPLACE(sql_mode,ONLY_FULL_GROUP_BY,)); 完美的解决方案是&#xff1a; 1 show variables like "sql_mode"; 2 3 set sql_mode; 4 set sql_modeNO_ENGINE_SUBSTITUTION,STRICT_TRANS_TABL…
阅读更多...
编程新手必看，Python3中数据结构知识点及语法学习总结（21）

编程新手必看，Python3中数据结构知识点及语法学习总结（21）

介绍&#xff1a;在Python3中&#xff0c;数据结构是组织和存储数据的有效方式&#xff0c;它们对于编写高效且可维护的代码至关重要。以下是对Python中常见内置数据结构的介绍&#xff1a; 字典&#xff08;Dictionaries&#xff09;&#xff1a; 字典在Python中是一个非常核…
阅读更多...
跟TED演讲学英文：How AI can save our humanity by Kai-Fu Lee

跟TED演讲学英文：How AI can save our humanity by Kai-Fu Lee

How AI can save our humanity Link: https://www.ted.com/talks/kai_fu_lee_how_ai_can_save_our_humanity Speaker: Kai-Fu Lee Date: April 2018 文章目录 How AI can save our humanityIntroductionVocabularyTranscriptSummary后记 Introduction AI is massively trans…
阅读更多...
抖音爆火的产品都具备哪些特点，该如何选品？

抖音爆火的产品都具备哪些特点，该如何选品？

抖音的崛起给许多创业者带来了商机&#xff0c;很多人选择在抖音开设小店。 对于拥有自己的小店的商家来说&#xff0c;如何提升商品曝光率是非常重要的。 而抖音选品广场就是一个非常好的平台。 抖音选品广场是抖音的一个分区&#xff0c;专门展示各种有特色的商品&#xf…
阅读更多...
【若依前后端分离】仪表盘绘制

【若依前后端分离】仪表盘绘制

示例&#xff1a; 代码&#xff1a; InstrumentPanel.vue组件 <template><div><!-- 在这里放置你的图表组件 --><div ref"echarts" style"width: 100%; height: 400px;"></div></div> </template><script&g…
阅读更多...
2024中国国际中医药健康服务博览会（7月深圳中医药展）

2024中国国际中医药健康服务博览会（7月深圳中医药展）

聚焦中医国粹&#xff0c;助力健康中国 2024第五届中国国际中医药健康服务&#xff08;深圳&#xff09;博览会 暨粤港澳大湾区中医药高质量发展大会 邀请函 时间&#xff1a;2024年7月31日-8月2日 地址:深圳会展中心&#xff08;福田&#xff09; 支持单位&#xff…
阅读更多...
(2022级）成都工业学院数据库原理及应用实验四： SQL简单查询

(2022级）成都工业学院数据库原理及应用实验四： SQL简单查询

写在前面 1、基于2022级软件工程/计算机科学与技术实验指导书 2、成品仅提供参考 3、如果成品不满足你的要求&#xff0c;请寻求其他的途径 运行环境 window11家庭版 Navicat Premium 16 Mysql 8.0.36 实验要求 在实验三的基础上完成下列查询&#xff1a; 1、查询所有…
阅读更多...
react 响应式栅格布局

react 响应式栅格布局

遇到一个小问题 , 有很多的下拉框放在了一行的盒子里 用到了栅格思路 , 但响应式处理屏幕时候右侧的按钮会覆盖掉样式 之前我的思路是子绝父相 , 将按钮定在最右侧 , 按钮和下拉框都在同一盒子中 , 且做了栅格处理没想到还是会覆盖解决 : 后来我用到了 margin-left: auto 来让…
阅读更多...
vue3 echarts 图表主题切换

vue3 echarts 图表主题切换

我主要是用了localStorage和composable来实现的。 先创建composable文件夹存储composable的操作方法&#xff1b; 在App.vue文件里面&#xff0c;先将主题数据存储在localStorage里面&#xff1b; 主题切换 图表theme包更换 为什么要用composable呢&#xff1f; 单纯的使用…
阅读更多...
记录——FPGA的学习路线

记录——FPGA的学习路线

文章目录 一、前言二、编程语言2.1 书籍2.2 刷题网站2.3 仿真工具 三、基础知识3.1 专业基础课3.2 fpga相关专业知识 四、开发工具五、动手实验 一、前言 也不是心血来潮想学习fpga了&#xff0c;而是祥哥还有我一个国科大的同学都在往fpga这个方向走 并且看过我之前文章的同…
阅读更多...
上位机图像处理和嵌入式模块部署（树莓派4b实现固件主流程）

上位机图像处理和嵌入式模块部署（树莓派4b实现固件主流程）

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 软件开发一般有软件需求、架构设计和详细设计、软件测试这四个部分。软件需求和软件测试都比较好理解&#xff0c;前者是说要实现哪些功能&#xf…
阅读更多...
【Java】常见锁策略 CAS机制 锁优化策略

【Java】常见锁策略 CAS机制 锁优化策略

前言 在本文会详细介绍各种锁策略、CAS机制以及锁优化策略 不仅仅局限于Java&#xff0c;任何和锁相关的话题&#xff0c;都可能会涉及到下面的内容。 这些特性主要是给锁的实现者来参考的. 普通的程序猿也需要了解一些, 对于合理的使用锁也是有很大帮助的 文章目录 前言✍一、…
阅读更多...
户外旅行摄影手册，旅游摄影完全攻略

户外旅行摄影手册，旅游摄影完全攻略

一、资料前言 本套旅游摄影资料&#xff0c;大小295.47M&#xff0c;共有9个文件。 二、资料目录 《川藏线旅游摄影》杨桦.彩印版.pdf 《户外摄影指南》(Essential.Guide.to.Outdoor.photography.amateur)影印版.pdf 《旅行摄影大师班》(英)科尼什.扫描版.PDF 《旅行摄影…
阅读更多...
vue快速入门（三十三）scoped解决组件样式冲突

vue快速入门（三十三）scoped解决组件样式冲突

注释很详细&#xff0c;直接上代码 上一篇 新增内容 scoped解决样式冲突的用法 源码 MyHeader.vue <!-- 用于测试全局注册组件 --> <template><div id"myHeader"><h1>又可以愉快的学习啦</h1></div> </template><scri…
阅读更多...
C++初阶学习第一弹——C++入门（上）

C++初阶学习第一弹——C++入门（上）

前言&#xff1a; 很高兴&#xff0c;从今天开始&#xff0c;我们就要步入C的学习了&#xff0c;在这之前我们已经对C语言有了不错的了解&#xff0c;对数据结构也有了一些自己的认识&#xff0c;今天开始&#xff0c;我们就进入这个新的主题的学习——C 目录 一、C的发展即其特…
阅读更多...
最新文章

Copyright @ 2022~2023