数据结构——双向链表的实现

文章目录

  • 一、双向链表的结构
  • 二、实现双向链表
    • 创建双向链表的项目
    • 双向链表的结构
    • List.h
    • 申请结点
    • 初始化
    • 打印
    • 尾插
    • 头插
    • 尾删
    • 头删
    • 查找
    • 在pos位置之后插入数据
    • 删除pos结点
    • 销毁
  • 三、所有源代码
    • List.h
    • List.c
    • test.c

一、双向链表的结构

带头双向循环链表
在这里插入图片描述

注意：这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严
谨，但是为了更好的理解就直接称为单链表的头节点。
带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的”

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

二、实现双向链表

创建双向链表的项目

在这里插入图片描述
List.h 定义双向链表的结构，声明相关的函数
List.c 实现双向链表声明的函数
test.c 测试代码

双向链表的结构

在这里插入图片描述

在这里插入图片描述

List.h

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

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

//声明双向链表中提供的方法

//初始化

//void LTInit(LTNode** pphead);
LTNode* LTInit();

//打印
void LTPrint(LTNode* phead);

//插入数据之前，链表必须初始化为只有一个结点的情况下
// 不改变哨兵位的位置，因此传一级指针即可

//尾插
void LTPushBack(LTNode* phead, LTDateType x);

//头插
void LTPushFront(LTNode* phead, LTDateType x);

//尾删
void LTPopBack(LTNode* phead);

//头删
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDateType x);

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDateType x);

//删除pos结点
void LTErase(LTNode* pos);

//销毁
void LTDesTroy(LTNode* phead);

申请结点

//申请结点
LTNode* LTBuyNode(LTDateType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->date = x;
	node->next = node->prev = node;
	return node;
}

初始化

这里有两种实现方法
在这里插入图片描述

//初始化
//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}

打印

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

注意：插入数据之前，链表必须初始化为只有一个结点的情况下
不改变哨兵位的位置，因此传一级指针即可

尾插

//尾插
void LTPushBack(LTNode* phead, LTDateType 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, LTDateType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead  newnode   phead->next  
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->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
	del->next->prev = phead;
	phead->next = del->next;
	//删除del结点
	free(del);
	del = NULL;
}

查找

//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{
	assert(phead && phead->next != phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->date == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

在pos位置之后插入数据

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

删除pos结点

//删除pos结点
void LTErase(LTNode* pos)
{
	assert(pos);
	//pos->prev  pos  pos->next
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	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;
	}
	free(phead);
	phead = NULL;
}

三、所有源代码

List.h

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

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

//声明双向链表中提供的方法

//初始化

//void LTInit(LTNode** pphead);
LTNode* LTInit();

//打印
void LTPrint(LTNode* phead);

//插入数据之前，链表必须初始化为只有一个结点的情况下
// 不改变哨兵位的位置，因此传一级指针即可

//尾插
void LTPushBack(LTNode* phead, LTDateType x);

//头插
void LTPushFront(LTNode* phead, LTDateType x);

//尾删
void LTPopBack(LTNode* phead);

//头删
void LTPopFront(LTNode* phead);

//查找
LTNode* LTFind(LTNode* phead, LTDateType x);

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDateType x);

//删除pos结点
void LTErase(LTNode* pos);

//销毁
void LTDesTroy(LTNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

//申请结点
LTNode* LTBuyNode(LTDateType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	node->date = x;
	node->next = node->prev = node;
	return node;
}

//初始化
//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{
	LTNode* phead = LTBuyNode(-1);
	return phead;
}


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

//尾插
void LTPushBack(LTNode* phead, LTDateType 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, LTDateType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);
	//phead  newnode   phead->next  
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->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
	del->next->prev = phead;
	phead->next = del->next;
	//删除del结点
	free(del);
	del = NULL;
}

//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{
	assert(phead && phead->next != phead);
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->date == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	LTNode* newnode = LTBuyNode(x);
	//pos  newnode  pos->next
	newnode->prev = pos;
	newnode->next = pos->next;
	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;

	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;
	}
	free(phead);
	phead = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"
//测试代码
void test()
{
	//测试初始化
	/*LTNode* plist = NULL;
	LTInit(&plist);*/
	LTNode* plist = LTInit();

	//测试尾插
	LTPushBack(plist, 1);
	LTPrint(plist);
	LTPushBack(plist, 2);
	LTPrint(plist);
	LTPushBack(plist, 3);
	LTPrint(plist);
	LTPushBack(plist, 4);
	LTPrint(plist);

	//测试头插
	/*LTPushFront(plist, 8);
	LTPushFront(plist, 7);
	LTPushFront(plist, 6);
	LTPushFront(plist, 5);
	LTPrint(plist);*/

	//测试尾删
	/*LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);
	LTPopBack(plist);
	LTPrint(plist);*/

	//测试头删
	/*LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);
	LTPopFront(plist);
	LTPrint(plist);*/

	//测试查找
	/*LTNode* find = LTFind(plist, 4);
	if (find == NULL)
	{
		printf("找不到！\n");
	}
	else
	{
		printf("找到了！\n");
	}*/

	//测试在pos位置之后插入数据
	/*LTNode* find = LTFind(plist, 4);
	LTInsert(find, 88);
	LTPrint(plist);*/

	//测试删除pos结点
	/*LTNode* find = LTFind(plist, 2);
	LTErase(find);
	LTPrint(plist);
	find = NULL;*/

	//测试销毁
	LTDesTroy(plist);
	plist = NULL;
}

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

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

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

相关文章

数据交换格式

数据交换格式

一、什么是数据交换格式 在计算机的不同程序之间&#xff0c;或者不同的编程语言之间进行交换数据&#xff0c;也需要一种大家都能听得懂得‘语言’&#xff0c;这就是数据交换格式&#xff0c;它通过文本以特定的形式来进行描述数据。 二、常用的几种数据交换格式 客户端常…
阅读更多...
图像处理ASIC设计方法 笔记17 连通域的图像标记算法

图像处理ASIC设计方法 笔记17 连通域的图像标记算法

目录 （一）主要环节图像初步标记 -等价表初始化与等价关系记录 -整理等价表 -图像标记代换 -（二）详细算法步骤：1 等价表的操作：2 整理等价表：3 图像标记代换：连通域的图像标记算法有若干步骤，除了图像初步标记，还有等价表初始化、等价关系记录、整理等价表、图像标记代…
阅读更多...
【C++】深度解析---赋值运算符重载（小白一看就懂！！）

【C++】深度解析---赋值运算符重载（小白一看就懂！！）

目录 一、前言 二、 运算符重载 &#x1f34e;运算符重载 ① 概念引入 ② 语法明细 ③ 练习巩固 ④ 代码展示 &#x1f347;赋值运算符重载 ① 语法说明及注意事项 ② 默认的赋值运算符重载 ③ 值运算符不能重载成全局函数&#xff01; 三、总结 四、共勉 一、前言…
阅读更多...
前端console用法分享

前端console用法分享

console对于前端人员来讲肯定都不陌生&#xff0c;相信大部分开发者都会使用console来进行调试&#xff0c;但它能做的绝不仅限于调试。 最常见的控制台方法 作为开发者&#xff0c;最常用的 console 方法如下&#xff1a; 控制台打印结果&#xff1a; 今天我分享的是一些 co…
阅读更多...
Qt快速入门（MV架构之TableView + QStandardItemModel + 自定义代理小案例）

Qt快速入门（MV架构之TableView + QStandardItemModel + 自定义代理小案例）

Qt快速入门&#xff08;MV架构之TableView QStandardItemModel 自定义代理小案例&#xff09; 关于MV架构的简单介绍 在Qt框架中&#xff0c;代理&#xff08;Delegate&#xff09;、模型&#xff08;Model&#xff09;和视图&#xff08;View&#xff09;之间的关系构成了…
阅读更多...
jvisualVM分析jvm内存使用快照dump

jvisualVM分析jvm内存使用快照dump

服务发生内存溢出&#xff0c;就需要查看服务器上Java服务的jvm堆内存使用情况&#xff0c;可以使用dump命令生成dump文件&#xff0c;然后下载到本地&#xff0c;然后使用jvisualVM工具打开&#xff0c;即可实现可视化分析。 生成dump文件常用的两种方式&#xff1a; 第一种…
阅读更多...
linux fixmap分析

linux fixmap分析

本文基于Linux-4.19.125&#xff0c; ARM V7&#xff0c;dual core, MMU采用2级页表&#xff08;未开启LPAE&#xff09;。 1 为什么需要fixmap Linux内核启动过程中&#xff0c;经过汇编阶段后&#xff0c;mmu功能已经开启&#xff0c;后续只能通过虚拟地址来访问DDR&#x…
阅读更多...
RAG应用开发实战02-相似性检索的关键 - Embedding

RAG应用开发实战02-相似性检索的关键 - Embedding

1 文本Embedding 将整个文本转化为实数向量的技术。 Embedding优点是可将离散的词语或句子转化为连续的向量&#xff0c;就可用数学方法来处理词语或句子&#xff0c;捕捉到文本的语义信息&#xff0c;文本和文本的关系信息。 ◉ 优质的Embedding通常会让语义相似的文本在空…
阅读更多...
Linux 添加启动服务--Service

Linux 添加启动服务--Service

1&#xff0c;服务配置service文件 Service 服务的实际作用是开启后自动启动服务&#xff0c;运行一些不须要登录的程序&#xff0c;任务。 实例1、上电自动连接WIFI热点 1.1 新建.service文件 /etc/systemd/system/wificonnect.service [Unit] DescriptionService [wifico…
阅读更多...
记录linux从0部署java项目（宝塔）

记录linux从0部署java项目（宝塔）

目录 一、安装宝塔可视化界面 二、部署前端 三、部署后端 1、配置并连接Mysql数据库 2、配置并连接redis 3、安装jdk 这里先记录一个安装后遇到的问题 安装openJDK 四、检查 一、安装宝塔可视化界面 宝塔面板下载&#xff0c;免费全能的服务器运维软件 运行安装脚本 安…
阅读更多...
MySQL 社区版 安装总结

MySQL 社区版 安装总结

很早就安装过MySQL&#xff0c;没有遇到过什么问题&#xff0c;直接next就行了&#xff0c;这次在新电脑上安装却遇到了一些问题&#xff0c;记录一下。 安装的是MySQL社区版&#xff0c;下载地址是www.mysql.com&#xff0c;进入后选择DOWNLOAD页面&#xff0c;选择MySQL Com…
阅读更多...
基本的数据类型在16位、32位和64位机上所占的字节大小

基本的数据类型在16位、32位和64位机上所占的字节大小

1、目前常用的机器都是32位和64位的&#xff0c;但是有时候会考虑16位机。总结一下在三种位数下常用的数据类型所占的字节大小。 数据类型16位(byte)32位(byte)64位(byte)取值范围char111-128 ~ 127unsigned char1110 ~ 255short int / short222-32768~32767unsigned short222…
阅读更多...
HarmonyOS实战开发-自定义通知角标、如何设定应用的桌面图标角标的功能。

HarmonyOS实战开发-自定义通知角标、如何设定应用的桌面图标角标的功能。

介绍 本示例主要展示了设定应用的桌面图标角标的功能&#xff0c;使用ohos.notificationManager 接口&#xff0c;进行桌面角标的设置&#xff0c;通知的发送&#xff0c;获取等。 效果预览 使用说明 在使用本应用时&#xff0c;需安装并启动仿桌面应用&#xff1b;在主界面…
阅读更多...
LeetCode 57—— 插入区间

LeetCode 57—— 插入区间

阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 第一步&#xff0c;我们先寻找新区间和原始区间列表的重叠部分。 假设新区间为 [ x 1 , x 2 ] [x_1, x_2] [x1​,x2​]&#xff0c;原始区间列表中的其中一个区间为 [ y 1 , y 2 ] [y_1, y_2] [y1​,y2​]&…
阅读更多...
PostgreSQL入门到实战-第三十弹

PostgreSQL入门到实战-第三十弹

PostgreSQL入门到实战 PostgreSQL教程网站官网地址PostgreSQL概述更新计划 PostgreSQL教程网站 https://www.postgresqltutorial.com/ 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://www.postgresql.org/PostgreS…
阅读更多...
【数据工具】ArcGIS批量出图工具箱

【数据工具】ArcGIS批量出图工具箱

工具下载链接&#xff1a;数据下载链接 我们在使用Arcgis制图的过程中&#xff0c;经常会遇到需要大量出图的情况&#xff0c;如何将做好的图批量导出jpg是一件令人头疼的问题。 今天小编就给大家分享俩个ArcGIS批量出图的工具箱&#xff0c;一个可以批量导出图层为jpg&#…
阅读更多...
运筹说 第112期 | M/M/s等待制排队模型

运筹说 第112期 | M/M/s等待制排队模型

通过上期学习&#xff0c;大家已经了解了排队论中的一些基本概念&#xff0c;以及生灭过程和Poisson过程。 那么本期小编将基于这些基本原理&#xff0c;为大家介绍M/M/s混合制排队模型&#xff0c;包括单服务台模型和多服务台模型&#xff0c;介绍模型的概念以及推导过程等内容…
阅读更多...
PoE 技术

PoE 技术

1 PoE 技术产生背景 随着 WLAN 、 VoIP 、网络视频监控等新业务的飞速发展，大量的无线 LAN 访问点、 IP 电话、 IP 网络摄像头等基于 IP 的终端出现在工业现场。这些设备通常数量众多、位置特殊 、 布线复杂、设备取电困难，其实施部署不仅消耗大量人力物力，…
阅读更多...
【数据结构与算法】搜索算法（深度优先搜索 DFS和广度优先搜索 BFS）以及典型算法例题

【数据结构与算法】搜索算法（深度优先搜索 DFS和广度优先搜索 BFS）以及典型算法例题

目录 搜索算法&#xff08;深度优先搜索DFS和广度优先搜索BFS&#xff09;以及典型算法例题深度优先搜索 &#xff08;Depth First Search 简称 DFS&#xff09;DFS 的设计步骤深度优先搜索&#xff08;DFS&#xff09;算法例题例题一&#xff1a;N皇后问题例题二&#xff1a;路…
阅读更多...
FreeRTOS学习 -- FreeRTOSConfig.h介绍

FreeRTOS学习 -- FreeRTOSConfig.h介绍

一、FreeRTOSConfig.h文件 FreeRTOS 的系统配置文件为 FreeRTOSConfig.h&#xff0c;在此配置文件中可以完成 FreeRTOS 的裁剪和配置。 FreeRTOS 的配置基本是通过在 FreeRTOSConfig.h 中使用“#define”这样的语句来定义宏定义实现的。在 FreeRTOS 的官方 demo 中&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023