【数据结构】双向链表专题

目录

1.双向链表的结构

2.双向链表的实现

2.1初始化

以参数的形式初始化链表： 

以返回值的形式初始化链表：

2.2尾插

2.3打印

2.4头插

2.5尾删

2.6头删

2.7查找

2.8在指定位置之后插入数据​编辑

2.9删除pos节点

2.10销毁

3.整理代码

3.1 List.h

3.2 List.c

3.3 Test.c

1.双向链表的结构

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在那里“放哨”。

“哨兵位”存在的意义： 遍历循环链表避免死循环。

2.双向链表的实现

不带头节点的单链表为空链表的判条件：head=NULL，因为head本来指向链表的第一个节点，如果head为NULL，说明链表没有节点，为空链表。

而带头结点的单链表为空链表的判定条件：head->next=NULL;

双向链表为空链表的判定条件：链表中只剩下一个头结点。

2.1初始化

申请节点函数

LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;//自己指向自己
	return node;
}

以参数的形式初始化链表： 

开始的时候创建一个空链表，LTNode* plist = NULL;我们要对空链表进行初始化，保证让链表只有一个头结点（哨兵位），为我们后续插入操作做准备。由于要改变plist的指向，所以传二级指针。

void LTInit(LTNode** pphead)
{
	//给双向链表创建一个哨兵位
	*pphead = LTBuyNode(-1);//哨兵位里面不需要有值，为了调用申请节点函数，传一个值-1好了
}

以返回值的形式初始化链表：

初始化可以不传递二级指针，以返回值的形式返回哨兵位，调用完LTInit函数后，plist指针接收其返回值：LTNode* plist = LTInit();

LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

2.2尾插

void LTPushBack(LTNode* phead, LTDataType x)//不改变哨兵位的地址，传一级指针即可
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;//注意：这两行代码不能颠倒位置
}

2.3打印

void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

2.4头插

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

	newnode->next->prev = newnode;
	phead->next = newnode;//注意：这两行代码不能颠倒位置
}

2.5尾删

void LTPopBack(LTNode* phead)
{
	//链表必须有效且链表不能为空(只有一个哨兵位)
	assert(phead && phead->next!=phead);
	LTNode* del = phead->prev;
	//phead del->prev del
	del->prev->next = phead;
	phead->prev = del->prev;
	//删除del节点
	free(del);
	del = NULL;
}

2.6头删

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

2.7查找

LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

2.8在指定位置之后插入数据

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

2.9删除pos节点

为了保持接口的一致性，这里传的是一级指针，对形参的修改不影响实参，pos置为空不影响find , find此时是野指针，所以调用完 LTERase 函数后要手动将find置为空（find=NULL;）

void LTErase(LTNode* pos)
{
	assert(pos);
	// pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	//删除pos节点
	free(pos);
	pos = NULL;
}

2.10销毁

同样为了保持接口的一致性，这里也传一级指针，对形参的修改不影响实参，phead置为空不影响实参plist，所以调用完 LTDesTroy 函数后要手动将plist置为空（plist=NULL;）

void LTDesTroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur指向phead,而phead还没有被销毁
	free(phead);
	phead = NULL;
}

3.整理代码

3.1 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;


//初始化
//void LTInit(LTNode** pphead);//以二级指针形式初始化
LTNode* LTInit();//以返回值形式初始化
//打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead,LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//销毁
void LTDesTroy(LTNode* phead);

3.2 List.c

#include"List.h"
//申请节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->data = x;
	node->next = node->prev = node;//自己指向自己
	return node;
}

//初始化
//以返回值形式初始化
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

//以二级指针形式初始化
//void LTInit(LTNode** pphead)
//{
//	*pphead = LTBuyNode(-1);
//}

//打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

//尾插
void LTPushBack(LTNode* phead, LTDataType x)//不改变哨兵位的地址，传一级指针即可
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead phead->prev newnode
	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;//注意：这两行代码不能颠倒位置
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead newnode phead->next
	newnode->next = phead->next;
	newnode->prev = phead;

	newnode->next->prev = newnode;
	phead->next = newnode;//注意：这两行代码不能颠倒位置
}

//尾删
void LTPopBack(LTNode* phead)
{
	//链表必须有效且链表不能为空(只有一个哨兵位)
	assert(phead && phead->next!=phead);
	LTNode* del = phead->prev;
	//phead del->prev del
	del->prev->next = phead;
	phead->prev = del->prev;
	//删除del节点
	free(del);
	del = NULL;
}

//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);
	LTNode* del = phead->next;
	//phead del del->next
	phead->next = del->next;
	del->next->prev = phead;
	//删除del节点
	free(del);
	del = NULL;
}

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	//pos newnode pos->next
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;

}

//删除pos节点
void LTErase(LTNode* pos)
{	
	assert(pos);
	// pos->prev pos pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	//删除pos节点
	free(pos);
	pos = NULL;
}

//销毁
void LTDesTroy(LTNode* phead)
{
	assert(phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	//此时pcur指向phead,而phead还没有被销毁
	free(phead);
	phead = NULL;
}

3.3 Test.c

#include"List.h"
void ListTest01()
{  	
	//传二级指针形式初始化
	/*LTNode* plist = NULL;
	LTInit(&plist); */

	//以返回值形式初始化
	LTNode* plist = LTInit();

	//尾插
	LTPushBack(plist, 1);
	LTPushBack(plist, 2);	
	LTPushBack(plist, 3);
	LTPrint(plist);//打印

	//头插
	LTPushFront(plist,4);	
	LTPushFront(plist,5);			
	LTPrint(plist);//打印

	//尾删
	LTPopBack(plist);
	LTPrint(plist);//打印

	//头删
	LTPopFront(plist);
	LTPrint(plist);//打印

	//查找
	LTNode* find = LTFind(plist,4);
	
	//删除pos节点
	LTErase(find);
	LTPrint(plist);//打印
	find = NULL;//手动置空

	//销毁		
	LTDesTroy(plist);
	plist = NULL;//手动置空
}
int main()
{
	ListTest01();
	return 0;
}

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

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

相关文章

Unity笔记：ScrollRect代码阅读

Unity笔记：ScrollRect代码阅读

大体流程 Unity Docs - UGUI | Class ScrollRect 总的说 自身不负责Rebuild&#xff0c;设置脏之后交由LayoutRebuilder注册到CanvasUpdateRegistry里待rebuild的集合在固定时机统一Rebuild。自身只在Prelayout和Postlayout做一下数据准备和数据更新 自身的ICanvasElement.…
阅读更多...
Visual Studio配置opencv环境

Visual Studio配置opencv环境

&#xff08;1&#xff09;打开属性页面&#xff08;鼠标放在解决方案上&#xff0c;点击右键会有一个属性选项弹出&#xff09; &#xff08;2&#xff09;配置opencv的include和opencv2路径&#xff0c;具体路径和版本根据自己电脑配置 &#xff08;3&#xff09;配置opencv…
阅读更多...
OpenAI o1预览模型发布：推理能力更强 可达理科博士生水准

OpenAI o1预览模型发布：推理能力更强 可达理科博士生水准

今日凌晨&#xff0c;OpenAI正式推出了OpenAI o1预览模型。 对于复杂推理任务而言&#xff0c;新模型代表着人工智能能力的崭新水平&#xff0c;其特点就是会在回答之前花更多时间进行思考&#xff0c;就像人类思考解决问题的过程一样。 OpenAI曾解释过&#xff0c;2023年发布…
阅读更多...
卡车配置一键启动无钥匙进入手机控车

卡车配置一键启动无钥匙进入手机控车

‌ 卡车智能一键启动无钥匙进入手机控车&#xff0c;通过手机应用程序与汽车内置硬件、软件的无线通信&#xff0c;实现对汽车的远程控制‌。 卡车改装一键启动的步骤包括安装门把手的感应装置、拆卸仪表台和门板&#xff0c;取出内部的待接线束&#xff0c;并将一键启动…
阅读更多...
ip地址a段b段c段是什么意思

ip地址a段b段c段是什么意思

在互联网的世界里&#xff0c;每一个设备都需要一个独特的标识符来相互识别和通信&#xff0c;这就是IP地址。IP地址不仅仅是一串数字&#xff0c;它背后隐藏着网络的组织结构和设备的连接方式。本文将深入探讨IP地址中的A段、B段、C段的含义&#xff0c;以及它们在网络通信中的…
阅读更多...
VSCode创建项目和编译多文件

VSCode创建项目和编译多文件

前言 在刚安装好VSCode后&#xff0c;我简单尝试了仅main.cpp单文件编译代码&#xff0c;没有问题&#xff0c;但是当我尝试多文件编译时&#xff0c;就出现了无法识别cpp文件。 内容 创建项目 首先点击左上角“文件”&#xff1b;在菜单中选择“打开文件夹”&#xff1b;在…
阅读更多...
建材家居家具电器整站网站打包下载预览图及地址二

建材家居家具电器整站网站打包下载预览图及地址二

木质装饰材料网站模板_建材家居家具电器类下载有预览图在博客首页.zip 响应式高端品牌建材陶瓷瓷砖网站模板_建材家居家具电器类下载有预览图在博客首页.zip 响应式创意家居网站模板_建材家居家具电器类下载有预览图在博客首页.zip 木纹地板墙砖类网站模板_建材家居家具电器…
阅读更多...
极狐GitLab CI/CD 作业一直处于等待状态，如何解决？

极狐GitLab CI/CD 作业一直处于等待状态，如何解决？

本分分享 GitLab CI/CD Job 不工作的的故障排查方法&#xff1a;当 GitLab Runner 不接受 Job&#xff0c;Job 一直处于等待状态&#xff0c;如何解决此问题。 极狐GitLab 为 GitLab 在中国的发行版&#xff0c;中文版本对中国用户更友好。极狐GitLab 支持一键私有化部署&…
阅读更多...
加密与安全_ sm-crypto 国密算法sm2、sm3和sm4的Java库

加密与安全_ sm-crypto 国密算法sm2、sm3和sm4的Java库

文章目录 Presm-crypto如何使用如何引入依赖 sm2获取密钥对加密解密签名验签获取椭圆曲线点 sm3sm4加密解密 Pre 加密与安全_三种方式实现基于国密非对称加密算法的加解密和签名验签 sm-crypto https://github.com/antherd/sm-crypto 国密算法sm2、sm3和sm4的java版。基于js…
阅读更多...
linux入门到实操-4 linux系统网络配置、连接测试、网络连接模式、修改静态IP、配置主机名

linux入门到实操-4 linux系统网络配置、连接测试、网络连接模式、修改静态IP、配置主机名

教程来源&#xff1a;B站视频BV1WY4y1H7d3 3天搞定Linux&#xff0c;1天搞定Shell&#xff0c;清华学神带你通关_哔哩哔哩_bilibili 整理汇总的课程内容笔记和课程资料&#xff08;包含课程同版本linux系统文件等内容&#xff09;&#xff0c;供大家学习交流下载&#xff1a;…
阅读更多...
QML学习三：qml设计器报错 Line: 0: The Design Mode requires a valid Qt kit

QML学习三：qml设计器报错 Line: 0: The Design Mode requires a valid Qt kit

开发环境&#xff1a;Qt 6.5.3 LTS 1、Qt 6.5.3 LTS 2、Pyside6 3、Python 3.11.4 4、win11 默认不打开设计器的时候可以看到我们默认是有Python的环境&#xff0c;而且点击运行是可以运行的。但是当打开qml设计器时提示下面这个错误&#xff0c;提示需要一个可用的套件。 …
阅读更多...
通信工程学习：什么是ASON自动交换光网络

通信工程学习：什么是ASON自动交换光网络

ASON&#xff1a;自动交换光网络 ASON&#xff08;Automatically Switched Optical Network&#xff09;&#xff0c;即自动交换光网络&#xff0c;是一种在选路和信令控制下完成自动交换功能的新一代光网络。它代表了未来智能光网络发展的主流方向&#xff0c;是下一代智能光传…
阅读更多...
论文笔记：基于LLM和多轮学习的漫画零样本角色识别与说话人预测

论文笔记：基于LLM和多轮学习的漫画零样本角色识别与说话人预测

整理了ACM MM2024 Zero-Shot Character Identification and Speaker Prediction in Comics via Iterative Multimodal Fusion&#xff09;论文的阅读笔记 背景模型框架实现细节 模型数据集实验可视化消融实验 背景 最近读到一篇新文章&#xff0c;主要是做漫画中的零样本角色识…
阅读更多...
Java并发：互斥锁，读写锁，Condition，StampedLock

Java并发：互斥锁，读写锁，Condition，StampedLock

3&#xff0c;Lock与Condition 3.1&#xff0c;互斥锁 3.1.1&#xff0c;可重入锁 锁的可重入性&#xff08;Reentrant Locking&#xff09;是指在同一个线程中&#xff0c;已经获取锁的线程可以再次获取该锁而不会导致死锁。这种特性允许线程在持有锁的情况下&#xff0c;可…
阅读更多...
如何在 Selenium 中获取网络调用请求？

如何在 Selenium 中获取网络调用请求？

引言 捕获网络请求对于理解网站的工作方式以及传输的数据至关重要。Selenium 作为一种 Web 自动化工具，可以用于捕获网络请求。本文将讨论如何使用 Selenium 在 Java 中捕获网络请求并从网站检索数据。 我们可以使用浏览器开发者工具轻松捕获网络请求或日志。大多数现代 Web…
阅读更多...
【iOS】UIViewController的生命周期

【iOS】UIViewController的生命周期

UIViewController的生命周期 文章目录 UIViewController的生命周期前言UIViewController的一个结构UIViewController的函数的执行顺序运行代码viewWillAppear && viewDidAppear多个视图控制器跳转时的生命周期pushpresent 小结 前言 之前对于有关于UIViewControlller的…
阅读更多...
MySQL：bin log

MySQL：bin log

redo log 它是物理日志&#xff0c;记录内容是“在某个数据页上做了什么修改”&#xff0c;属于 InnoDB 存储引擎。 而 binlog 是逻辑日志&#xff0c;记录内容是语句的原始逻辑&#xff0c;类似于“给 ID2 这一行的 c 字段加 1”&#xff0c;属于MySQL Server 层。 不管用什…
阅读更多...
学习平台|基于java的移动学习平台系统小程序(源码+数据库+文档)

学习平台|基于java的移动学习平台系统小程序(源码+数据库+文档)

学习平台|学习平台系统|在线学习平台系统小程序 目录 基于java的移动学习平台系统小程序 一、前言 二、系统设计 三、系统功能设计 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#xff1a;✌️大厂码…
阅读更多...
C++奇迹之旅：快速上手Priority_queue的使用与模拟实现

C++奇迹之旅：快速上手Priority_queue的使用与模拟实现

文章目录 &#x1f4dd;priority_queue的介绍和使用&#x1f320; priority_queue的介绍&#x1f309;priority_queue的使用 &#x1f320;仿函数的使用&#x1f320;C语言有趣的模仿push_back&#x1f320;priority_queue的模拟实现&#x1f6a9;总结 &#x1f4dd;priority_q…
阅读更多...
java重点学习-集合（List）

java重点学习-集合（List）

七 集合&#xff08;List&#xff09; 7.1 复杂度分析 7.2 数组 1.数组(Array)是一种用连续的内存空间存储相同数据类型 数据的线性数据结构。 2.数组下标为什么从0开始 寻址公式是:baseAddressi*dataTypeSize&#xff0c;计算下标的内存地址效率较高 3.查找的时间复杂度 随机(…
阅读更多...
最新文章

Copyright @ 2022~2023