【数据结构】双链表

【数据结构】双链表

  • 一. 前言
  • 二. 带头双向链表接口实现
      • 1.准备工作
      • 2. 创建一个节点
  • 三. 初始化
      • 4. 打印
      • 5. 尾插
      • 6. 尾删
      • 7. 头插
      • 8. 头删
      • 9. 计算节点个数
      • 10. 查找数据
      • 11. 在任意位置插入数据
      • 12. 在任意位置删除数据
      • 13. 销毁
  • 四. 如何10分钟内完成一个完整双链表

在这里插入图片描述

一. 前言

 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

在这里插入图片描述

二. 带头双向链表接口实现

1.准备工作

 由于实际开发项目中，项目的实现都是采用模块化的方式实现。所以博主在这也采用了模块化的方式。
在这里插入图片描述

#pragma once

typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* next;//下一个节点指针
	struct ListNode* prev;//上一个节点指针
	LTDataType data;//数据域
}LTNode;

为了后续函数功能实现过程中数据类型书写方便性，我们将struct ListNode重命名为LTNode。
同时后续好修改数据域类型，我们将数据域类型int重命名为LTDataType.

2. 创建一个节点

不管是后续插入数据还是初始化，我们都先要创建一个节点来存储数据。
所以我们在这设计了一个相关函数，从而避免大量重复的工作。

代码实现：

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}

三. 初始化

初始化时，我们支持需要创建一个节点作为哨兵位，并将两个指针同时指向自己即可。

代码实现：

LTNode* LTInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

4. 打印

打印比较简单。但需要注意我们是从哨兵位的下一个节点开始打印。

代码实现：

void LTPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;//哨兵位下一个节点
	printf("phead<=>");
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

5. 尾插

带头双链表的尾插比较简单。
我们通过哨兵位向前访问即可得到尾节点。在插入数据即可。

代码实现：

void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* tail = phead->prev;//尾节点
	LTNode* newnode = BuyLTNode(x);//要插入节点
	//插入
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

6. 尾删

【代码思路】：尾删首先要判断是否还有节点可删。若有，找到尾节点以及尾节点的前一个结点。在释放尾节点，并将新的尾节点和哨兵位链接起来即可。

代码实现：

void LTPopBack(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);//还有节点可删

	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);

	tailPrev->next = phead;
	phead->prev = tailPrev;
}

7. 头插

要实现头插，首先要强调是插到哨兵位的后面。
【代码思路】：直接将哨兵位，哨兵位的下一个节点以及新节点链接起来即可。

代码实现：

void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	LTNode* tail = phead->next;
	LTNode* newnode = BuyLTNode(x);

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = tail;
	tail->prev = newnode;
}

8. 头删

【代码思路】：头删和尾删一样，需要是否还有节点可删。若还有元素可删，需要保存哨兵位后面两个节点first、second。再释放掉first后，将哨兵位和second链接起来。

代码实现：

void LTPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead != phead->next);

	LTNode* first = phead->next;
	LTNode* second = first->next;
	free(first);

	phead->next = second;
	second->prev = phead;
}

9. 计算节点个数

【代码思路】：首先保存哨兵位的下一个节点。然后开始向后遍历访问，每次个数加1，直到某节点的下一个节点指向哨兵位为止。

代码实现：

int LTSize(LTNode* phead)
{
	LTNode* cur = phead->next;
	int count = 0;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

Tips:

  • 可能有部分学者已经注意到或在一些书籍上看到过以下思路：哨兵位的数据域是随机值，是否可以将它用于记录节点个数。每次进行增删查改等操作时，对其进行加1/减1。不仅更加方便得知节点个数，同时还避免该接口的实现。
  • 在这里博主不在这建议这样做，又或者说大部分情况是不能这样做的。原因在于：我们在本篇博客中，数据域为整型，可以用于记录节点个数大下。但在实际开发过程中，数据域可能存储的是浮点数或结构体什么的，那上述思路将导致结果错误。

10. 查找数据

【代码思路】：查找数据，从哨兵位的下一个节点开始，遍历查找。找到返回数据地址，否则返回空指针。

代码实现：

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

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

11. 在任意位置插入数据

【代码思路】：首先需要强调的是，不管是链表还是顺序表，插入数据默认都是前插，在这里也一样。插入数据、插入位置节点、以及前一个结点链接起来即可。
我们直接将

代码实现：

void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}

12. 在任意位置删除数据

【代码思路】：将该位置前一个和后一个节点链接起来后，再将该位置节点释放。

代码实现：

void LTErase(LTNode* pos)
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	free(pos);

	posPrev->next = posNext;
	posNext->prev = posPrev;
}

13. 销毁

由于上述节点都是动态开辟的，使用往后需要销毁，释放内存。

代码实现：

void LTDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

四. 如何10分钟内完成一个完整双链表

在实际开发过程中，我们一般实现实现任意位置插入删除接口的。然后在头插/删和尾插/删等接口中，调用上述两个接口，从而快速达到目的。

List.h:

#pragma once

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

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

LTNode* BuyLTNode(LTDataType x);//创建节点

LTNode* LTInit();//初始化
void LTPrint(LTNode* phead);//打印

//在pos之前插入x
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置节点
void LTErase(LTNode* pos);

void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删

int LTSize(LTNode* phead);//节点大小
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTDestory(LTNode* phead);//销毁

List.c:

#include "List.h"


LTNode* BuyLTNode(LTDataType x)//创建节点
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->next = NULL;
	newnode->prev = NULL;
	newnode->data = x;
	return newnode;
}


LTNode* LTInit()//初始化
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}


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


void LTInsert(LTNode* pos, LTDataType x)//任意位置插入
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = BuyLTNode(x);

	posPrev->next = newnode;
	newnode->prev = posPrev;

	newnode->next = pos;
	pos->prev = newnode;
}

void LTErase(LTNode* pos)//任意位置删除
{
	assert(pos);

	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	free(pos);

	posPrev->next = posNext;
	posNext->prev = posPrev;
}


void LTPushBack(LTNode* phead, LTDataType x)//尾插
{
	assert(phead);
	LTInsert(phead, x);
}


void LTPopBack(LTNode* phead)//尾删
{
	assert(phead);
	assert(phead != phead->next);
	LTErase(phead->prev);
}


void LTPushFront(LTNode* phead, LTDataType x)//头插
{
	assert(phead);
	LTInsert(phead->next, x);
}


void LTPopFront(LTNode* phead)//头删
{
	assert(phead);
	assert(phead != phead->next);
	LTErase(phead->next);
}


int LTSize(LTNode* phead)//节点大小
{
	LTNode* cur = phead->next;
	int count = 0;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}


LTNode* LTFind(LTNode* phead, LTDataType x)//查找数据
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}


void LTDestory(LTNode* phead)//销毁
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}

在这里插入图片描述
在这里插入图片描述

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

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

相关文章

通达OA SQL注入漏洞【CVE-2023-4165】

通达OA SQL注入漏洞【CVE-2023-4165】

通达OA SQL注入漏洞【CVE-2023-4165】 一、产品简介二、漏洞概述三、影响范围四、复现环境POC小龙POC检测工具: 五、修复建议 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损…
阅读更多...
元宇宙时代超高清视音频技术白皮书关于流媒体协议和媒体传输解读

元宇宙时代超高清视音频技术白皮书关于流媒体协议和媒体传输解读

流媒体协议 元宇宙业务场景对流媒体传输的实时性和互动性提出了更高的要求&#xff0c;这就需要在传统的 RTMP、SRT、 HLS 等基础上增加实时互动的支持。实时互动&#xff0c;指在远程条件下沟通、协作&#xff0c;可随时随地接入、实时地传递虚实融合的多维信息&#xff0c;身…
阅读更多...
uni-app日期选择器

uni-app日期选择器

写个简单的日期选择器&#xff0c;还没搞样式&#xff0c;所以有点丑 大概长这样吧 首先是这个picker选择器&#xff0c;mode选择日期&#xff0c;end是写一个范围前日期&#xff0c;:end就是这个日期是动态变化的&#xff0c;还有change函数 <template><view>&l…
阅读更多...
Mybatis 初识

Mybatis 初识

目录 1. MyBatis入门 1.1 MyBatis的定义 1.2 MyBatis的核心 MyBatis的核心 JDBC 的操作回顾 1.3 MyBatis的执行流程 MyBatis基本工作原理 2. MyBatis的使用 2.1 MyBatis环境搭建 2.1.1 创建数据库和表 2.1.2 添加MyBatis框架支持 老项目添加MyBatis 新项目添加MyBatis 2.1.3 设…
阅读更多...
iphone拷贝照片中间带E自动去重软件，以及java程序如何打包成jar和exe

iphone拷贝照片中间带E自动去重软件，以及java程序如何打包成jar和exe

文章目录 一、前提二、问题描述三、原始处理方式四、程序处理4.1 java程序如何打包exe4.1.1 首先打包jar4.1.2 开始生成exe4.1.3 软件使用方式 4.2 更换图标4.2.1 更换swing的打包jar图标4.2.2 更换exe图标 4.3 如何使生成的exe在没有java环境的电脑上运行4.3.1 Inno Setup打包…
阅读更多...
uniapp的uview-plus组件库的导入

uniapp的uview-plus组件库的导入

uniapp的vue3中使用uview-plus组件库。在插件市场中找到该组件并点击如下所示绿色按钮&#xff0c;弹出弹窗选择要导入的项目后&#xff0c;就会在uni_modules文件中生成如下文件内容 关于插件的下载区别&#xff0c;可参考&#xff1a;https://uniapp.dcloud.net.cn/compone…
阅读更多...
VSCode如何设置高亮

VSCode如何设置高亮

一、概述 本文主要介绍在 VSCode 看代码时&#xff0c;怎样使某个单词高亮显示&#xff0c;主要通过以下三步实现&#xff1a; 安装 highlight-words 插件 配置 highlight-words 插件 设置高亮快捷键F8 工作是嵌入式开发的&#xff0c;代码主要是C/C的&#xff0c;之前一直用…
阅读更多...
uniapp 扩展组件 uni-forms 的表单验证之 validateFunction 只响应一次

uniapp 扩展组件 uni-forms 的表单验证之 validateFunction 只响应一次

uniapp 扩展组件 uni-forms 的表单验证之 validateFunction 只响应一次 问题代码官方说明参考资料 问题代码 直接从官方示例中复制过来改的。为了演示 <template><view><uni-forms ref"form" :modelValue"formData" :rules"rules&qu…
阅读更多...
day 0815

day 0815

计算文件有多少行&#xff1f; 2.文件的拷贝
阅读更多...
Java中有哪些可以用于日期和时间的API?

Java中有哪些可以用于日期和时间的API?

从Java 8开始&#xff0c;java.time包提供了新的日期和时间API&#xff0c;新增的API严格区分了时刻、本地日期、本地时间&#xff0c;并且&#xff0c;对日期和时间进行运算更加方便。主要涉及的类型有以下几类&#xff1a; LocalDate&#xff1a;不包含具体时间的日期。 Lo…
阅读更多...
ArcGIS入门操作手册

ArcGIS入门操作手册

一.ArcGIS安装过程 参考本人博客&#xff1a;保姆级Arcgis安装图文安装教程_追忆苔上雪的博客-CSDN博客 二.ArcGIS植被指数计算 (1)使用工具&#xff1a;栅格计算器 打开软件&#xff0c;右侧搜索栅格计算器打开&#xff0c;要是搜索栏不小心叉掉找不到了&#xff0c;可以通…
阅读更多...
初识结构体

初识结构体

文章目录 目录1. 结构体类型的声明1.1 结构的基础知识1.2 结构的声明1.3 结构成员的类型1.4 结构体变量的定义和初始化 2. 结构体成员的访问3. 结构体传参 目录 结构体类型的声明结构体初始化结构体成员访问结构体传参 1. 结构体类型的声明 1.1 结构的基础知识 结构是一些值的…
阅读更多...
可白嫖的4家免费CDN，并测试其网络加速情况（2023版）

可白嫖的4家免费CDN，并测试其网络加速情况（2023版）

网站加载速度优化过程中&#xff0c;不可避免的会用上CDN来加速资源的请求速度。但是市面上的CDN资源几乎都是要收费的&#xff0c;而且价格还不便宜&#xff0c;对于小公司站长来讲&#xff0c;这将是一笔不小的开销。不过还是有一些良心公司给我们提供了免费的资源&#xff0…
阅读更多...
私密相册管家-加密码保护私人相册照片安全

私密相册管家-加密码保护私人相册照片安全

App Store史上最安全、最强大、最卓越的私密相册App&#xff01;再也不用担心私密照片视频被别人看见了&#xff01;
私密相册为你提供多重密码保护机制、简单便捷的照片存储空间&#xff0c;完美地将你的私密照片远离一切恶意偷窥者的窥探&#xff01; 【产品功能】
 √ 支…
阅读更多...
【Pytorch：nn.Embedding】简介以及使用方法：用于生成固定数量的具有指定维度的嵌入向量embedding vector

【Pytorch：nn.Embedding】简介以及使用方法：用于生成固定数量的具有指定维度的嵌入向量embedding vector

文章目录 1、nn.Embedding2、使用场景 1、nn.Embedding 首先我们讲解一下关于嵌入向量embedding vector的概念 1&#xff09;在自然语言处理NLP领域&#xff0c;是将单词、短语或其他文本单位映射到一个固定长度的实数向量空间中。嵌入向量具有较低的维度&#xff0c;通常在几…
阅读更多...
两天入门Linux、搭建Spring环境 第一天

两天入门Linux、搭建Spring环境 第一天

一、Linux简介 1.什么是Linux 一个操作系统&#xff0c;未来公司里面会用到、接触的新操作系统。 2.为什么学Linux (1)个人职务需要&#xff0c;肯定会接触到Linux (2)职业发展&#xff0c;以后的发展肯定需要掌握Linux的许多使用方法 3.学哪些内容 (1)Linux基本介绍 (2)…
阅读更多...
Prometheus入门

Prometheus入门

Prometheus(普罗米修斯) 是一种 新型监控告警工具,Kubernetes 的流行带动了 Prometheus 的应用。 全文参考自 prometheus 学习笔记(1)-mac 单机版环境搭建[1] Mac 上安装 Prometheus brew install prometheus 安装路径在 /usr/local/Cellar/prometheus/2.20.1, 配置文件在 /usr…
阅读更多...
Qt 之 QPushButton,信号与槽机制

Qt 之 QPushButton,信号与槽机制

文章目录 前言一、QPushButton二、信号与槽机制总结 前言 一、QPushButton 当我们开发基于Qt框架的图形用户界面&#xff08;GUI&#xff09;应用程序时&#xff0c;经常需要在界面上添加按钮来实现用户交互。Qt提供了一个名为 QPushButton 的类作为按钮控件的实现。QPushButt…
阅读更多...
题解 | #1002.Shortest path# 2023杭电暑期多校9

题解 | #1002.Shortest path# 2023杭电暑期多校9

1002.Shortest path 签到题 记忆化搜索 题目大意 给定一个正整数 n n n &#xff0c;可以对其进行以下操作&#xff1a; 如果 n n n 能被 3 3 3 整除&#xff0c;则可以使 n n / 3 nn/3 nn/3 ;如果 n n n 能被 2 2 2 整除&#xff0c;则可以使 n n / 2 nn/2 nn/2 …
阅读更多...
探索Java中的静态变量与实例变量：存储区域、生命周期以及内存分配方式的区别

探索Java中的静态变量与实例变量：存储区域、生命周期以及内存分配方式的区别

文章目录 静态变量实例变量不可变对象静态变量和实例变量有什么区别&#xff1f;静态变量实例变量 Object 类都有哪些公共方法&#xff1f;Java 创建对象有哪几种方式&#xff1f;ab 与 a.equals(b) 有什么区别&#xff1f;总结 &#x1f389;欢迎来到Java面试技巧专栏~探索Jav…
阅读更多...
最新文章

Copyright @ 2022~2023