【数据结构】带头双向循环链表的实现及链表顺序表的区别

目录

一、带头双向循环链表接口实现

连接关系：

创建哨兵位（表头）：

头插——头删：

尾插——尾删：

查找——打印：

指定位置pos前插入，删除pos位置：

链表销毁：

二、快速实现“链表”

三、链表和顺序表的区别：

四、整体代码：

一、带头双向循环链表接口实现

连接关系：

实现这个链表最重要的就是理清楚连接关系：这里我给出两个动图，模拟这个关系

插入：

删除：

创建哨兵位（表头）：

这里我们可以用两种方法，一种是采取二级指针的方法，另一种是直接创建一个表头，然后把表头地址返回去，这里我们采用第二种：

//创建新节点
ListNode* CreateNewNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->_data = x;
	newnode->_next = NULL;
	newnode->_prev = NULL;
	return newnode;
}
// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* head = CreateNewNode(-1);
	head->_prev = head;
	head->_next = head;
	return head;
}

头插——头删：

头插:

头插的时候，我们保存好链表第一个有效节点的地址，然后插入，记得把连接关系连接清楚

头删:

头删的时候，记得保存好，第二个节点的地址，记得把表头与第二节点的连接关系连接清楚

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode = CreateNewNode(x);
	ListNode* second = pHead->_next;
	pHead->_next = newnode;
	newnode->_prev = pHead;
	newnode->_next = second;
	second->_prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next != pHead);
	ListNode* first = pHead->_next;
	ListNode* second = first->_next;
	pHead->_next = second;
	second->_prev = pHead;
	free(first);
	first = NULL;
}

尾插——尾删：

尾插：

保存好当前尾节点的地址，注意搞清楚头节点，尾节点，新节点的连接关系

尾删:

保存好最后两个节点的位置，注意连接清楚头节点和倒数第二个节点

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* newnode= CreateNewNode(x);
	ListNode* tail = pHead->_prev;
	newnode->_next = pHead;
	newnode->_prev = tail;
	tail->_next = newnode;
	pHead->_prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next != pHead);
	ListNode* tail = pHead->_prev;
	ListNode* tailPrev = tail->_prev;
	pHead->_prev = tailPrev;
	tailPrev->_next = pHead;
	free(tail);
	tail = NULL;
}

查找——打印：

注意：

循环从哨兵位的下一个节点开始，直到等于哨兵位结束

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		if (cur->_data == x)
			return cur;
		cur = cur->_next;
	}
	return NULL;
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur!=pHead)
	{
		printf("%d <-> ", cur->_data);
		cur = cur->_next;
	}
	printf("NULL\n");
}

指定位置pos前插入，删除pos位置：

pos前插入： 

保存好pos前一个位置的地址，连接清楚就行了

删除pos位置：

保存好pos前后的位置，连接清楚就行了

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = CreateNewNode(x);
	ListNode* prev = pos->_prev;
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = pos;
	pos->_prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->_prev;
	ListNode* next = pos->_next;
	prev->_next = next;
	next->_prev = prev;
	free(pos);
	pos = NULL;
}

链表销毁：

这一个要从哨兵位的下一个节点开始，循环直到不等于哨兵位结束：

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		ListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	free(pHead);
}

二、快速实现“链表”

学了带头双向循环链表之后，我们可以快速实现一个简单链表：

大多数接口其实都是不变的，但是有4个接口可以简化，那就是头插——头删——尾插——尾删；

这两个接口可以复用insert接口和erase接口：这四个接口连接关系是比较麻烦的，省去了这几个麻烦的，其他的接口就会很快写出来，大大节省了时间：

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//ListNode* newnode= CreateNewNode(x);
	//ListNode* tail = pHead->_prev;
	//newnode->_next = pHead;
	//newnode->_prev = tail;
	//tail->_next = newnode;
	//pHead->_prev = newnode;

	ListInsert(pHead,x);
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	//assert(pHead->_next != pHead);
	//ListNode* tail = pHead->_prev;
	//ListNode* tailPrev = tail->_prev;
	//pHead->_prev = tailPrev;
	//tailPrev->_next = pHead;
	//free(tail);
	//tail = NULL;

	ListErase(pHead->_prev);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//ListNode* newnode = CreateNewNode(x);
	//ListNode* second = pHead->_next;
	//pHead->_next = newnode;
	//newnode->_prev = pHead;
	//newnode->_next = second;
	//second->_prev = newnode;

	ListInsert(pHead->_next, x);
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	//assert(pHead->_next != pHead);
	//ListNode* first = pHead->_next;
	//ListNode* second = first->_next;
	//pHead->_next = second;
	//second->_prev = pHead;
	//free(first);
	//first = NULL;

	ListErase(pHead->_next);
}

三、链表和顺序表的区别：

顺序表空间连续支持下标访问使得我们在排序，访问等很多场景下都是很高效的

链表的合理利用空间使我们对空间的管理更合理

四、整体代码：

SList.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;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"

//创建新节点
ListNode* CreateNewNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->_data = x;
	newnode->_next = NULL;
	newnode->_prev = NULL;
	return newnode;
}
// 创建返回链表的头结点.
ListNode* ListCreate()
{
	ListNode* head = CreateNewNode(-1);
	head->_prev = head;
	head->_next = head;
	return head;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		ListNode* next = cur->_next;
		free(cur);
		cur = next;
	}
	free(pHead);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur!=pHead)
	{
		printf("%d <-> ", cur->_data);
		cur = cur->_next;
	}
	printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//ListNode* newnode= CreateNewNode(x);
	//ListNode* tail = pHead->_prev;
	//newnode->_next = pHead;
	//newnode->_prev = tail;
	//tail->_next = newnode;
	//pHead->_prev = newnode;

	ListInsert(pHead,x);
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	//assert(pHead->_next != pHead);
	//ListNode* tail = pHead->_prev;
	//ListNode* tailPrev = tail->_prev;
	//pHead->_prev = tailPrev;
	//tailPrev->_next = pHead;
	//free(tail);
	//tail = NULL;

	ListErase(pHead->_prev);
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	//ListNode* newnode = CreateNewNode(x);
	//ListNode* second = pHead->_next;
	//pHead->_next = newnode;
	//newnode->_prev = pHead;
	//newnode->_next = second;
	//second->_prev = newnode;

	ListInsert(pHead->_next, x);
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	//assert(pHead->_next != pHead);
	//ListNode* first = pHead->_next;
	//ListNode* second = first->_next;
	//pHead->_next = second;
	//second->_prev = pHead;
	//free(first);
	//first = NULL;

	ListErase(pHead->_next);
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		if (cur->_data == x)
			return cur;
		cur = cur->_next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = CreateNewNode(x);
	ListNode* prev = pos->_prev;
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = pos;
	pos->_prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->_prev;
	ListNode* next = pos->_next;
	prev->_next = next;
	next->_prev = prev;
	free(pos);
	pos = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void test()
{
	ListNode* plist = ListCreate();

	ListPushBack(plist,1);
	ListPushBack(plist,2);
	ListPushBack(plist,3);
	ListPushBack(plist,4);
	ListPushBack(plist,5);

	ListPrint(plist);

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);

	ListPrint(plist);

	ListPushFront(plist,6);
	ListPushFront(plist,7);
	ListPushFront(plist,8);
	ListPushFront(plist,9);
	ListPushFront(plist,10);

	ListPrint(plist);

	ListPopFront(plist);
	ListPopFront(plist);
	ListPopFront(plist);

	ListPrint(plist);

	printf("%d\n", ListFind(plist, 6)->_data);

	ListPrint(plist);

	ListInsert(ListFind(plist,6), 99);
	ListInsert(ListFind(plist,7), 88);

	ListPrint(plist);

	ListErase(ListFind(plist, 99));
	ListErase(ListFind(plist, 88));

	ListPrint(plist);


	ListDestory(plist);
	plist = NULL;
}
int main()
{
	test();

	return 0;
}

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

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

相关文章

39 - 电影评分（高频 SQL 50 题基础版)

39 - 电影评分（高频 SQL 50 题基础版)

39 - 电影评分 (selectu.name as results fromMovieRating m left join Users u on m.user_idu.user_id GROUP BYm.user_id order by count(*) desc,u.name asc limit 1) union all (selectm1.title as results fromMovieRating m left join Movies m1 on m.movie_idm1.movie…
阅读更多...
SQL实现UUIDv7

SQL实现UUIDv7

当我们选择数据库的主键类型时&#xff0c;通常会考虑自增数字或者 UUID。但是这两种类型都有优缺点&#xff0c;自增字段简单有序&#xff0c;性能良好&#xff0c;最大的问题是无法保证全局唯一性&#xff0c;分布式场景受限&#xff1b;UUID 具有全局唯一性&#xff0c;适合…
阅读更多...
fastadmin框架修改前端时间戳格式的时区

fastadmin框架修改前端时间戳格式的时区

一、上传文件 将 moment-timezone-with-data.js 和 moment-timezone-with-data.min.js 文件上传到项目的 \public\assets\libs\moment\ 文件夹中。 二、配置中引入文件 在 \public\assets\js\require-backend.js 文件中增加所引入文件的配置： moment-timezone-with-data: …
阅读更多...
ITSG、COST-G、Tongji和WHU Level-2数据产品读取绘图（Matlab）

ITSG、COST-G、Tongji和WHU Level-2数据产品读取绘图（Matlab）

数据介绍&#xff1a; ICGEM International Center for Global Gravity Field Models (gfz-potsdam.de) ITSG 2018&#xff1a;Institute of Geodesy at Graz University of Technolog&#xff08;格拉茨理工大学大地测量研究所&#xff09; 2018版本&#xff0c;最高60阶球谐…
阅读更多...
深度之眼（二十六）——神经网络基础知识（一）

深度之眼（二十六）——神经网络基础知识（一）

文章目录 一、前言二、神经网络与多层感知机2.1 人工神经元2.2 人工神经网络2.3 多层感知机2.4 激活函数 一、前言 看了下课程安排&#xff0c;自己还是没安排好&#xff0c;刚刚捋清了一下思路。 基础&#xff1a;python、数理 认识&#xff1a;神经网络基础、opencv基础、py…
阅读更多...
加速科技Flash存储测试解决方案 全面保障数据存储可靠性

加速科技Flash存储测试解决方案 全面保障数据存储可靠性

Flash存储芯片 现代电子设备的核心数据存储守护者 Flash存储芯片是一种关键的非易失性存储器&#xff0c;作为现代电子设备中不可或缺的核心组件&#xff0c;承载着数据的存取重任。这种小巧而强大的芯片&#xff0c;以其低功耗、可靠性、高速的读写能力和巨大的存储容量&…
阅读更多...
C Tips: 举例说明在 Visual C++ 中忽略 C4996 编译警告的几种方法

C Tips: 举例说明在 Visual C++ 中忽略 C4996 编译警告的几种方法

C4996 编译警告非常常见&#xff0c;经常发生在程序调用了类似于strcpy这样的不够安全的函数时。例如以下代码在 Visual C 的默认工程设置中会引起 C4996 编译警告&#xff1a; void foo() {char filename[MAX_PATH];strcpy(filename, "D:\\Pub\\Test\\1.dat"); }编…
阅读更多...
Springboot小型仪器公司生产管理系统-计算机毕业设计源码031853

Springboot小型仪器公司生产管理系统-计算机毕业设计源码031853

摘 要 本论文主要论述了如何使用java语言开发一个Springboot小型仪器公司生产管理系统&#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;采用B/S架构&#xff0c;面向对象编程思想进行项目开发。在引言中&#xff0c;作者将论述小型仪器公司生产管理系统…
阅读更多...
数据结构——带头双向循环链表（c语言实现）

数据结构——带头双向循环链表（c语言实现）

目录 1.单链表和双向链表对比 2.双向链表实现 2.1 创建新节点 2.2 链表初始化 2.3 尾插 2.4 头插 2.5 尾删 2.6 头删 2.7 查找 2.8 指定位置后插入数据 2.9 删除指定节点 2.10 销毁链表 2.11 打印链表 前言&#xff1a; 我们在前几期详细地讲解了不带头单…
阅读更多...
【C#】找不到属性集方法。get只读属性用了反射设置setValue肯定报错

【C#】找不到属性集方法。get只读属性用了反射设置setValue肯定报错

欢迎来到《小5讲堂》 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 背景 找不到属性集方法。get只读属性用了反射设置setValue肯定报错 报错…
阅读更多...
OpenCv形态学（一）

OpenCv形态学（一）

目录 形态学转换 结构元素 腐蚀 膨胀 开运算 闭运算 形态学梯度 顶帽 黑帽 图像轮廓 查找轮廓 绘制轮廓 形态学转换 形态变换是一些基于图像形状的简单操作。通常在二值图像上执行。它需要两个输入&#xff0c;一个是我们的原始图像&#xff0c;第二个是决定操作性…
阅读更多...
推荐系统(LLM去偏?) | (WSDM24)预训练推荐系统:因果去偏视角

推荐系统(LLM去偏?) | (WSDM24)预训练推荐系统:因果去偏视角

::: 大家好&#xff01;今天我分享的文章是来自威斯康星大学麦迪逊分校和亚马逊AWS AI实验室的最新工作&#xff0c;文章所属领域是推荐系统和因果推理&#xff0c;作者针对跨域推荐中的偏差问题提出了一种基于因果去偏的预训练推荐系统框架PreRec。 ::: 原文&#xff1a;Pre-t…
阅读更多...
2024年敏捷开发管理工具10大精选

2024年敏捷开发管理工具10大精选

国内外主流的十大敏捷开发管理系统&#xff1a;PingCode、Tapd、OpenProject、Jira、ClickUp、Monday.com、Wrike、Taiga、Tuleap、Redmine。 敏捷开发已成为软件开发领域的一种标准实践&#xff0c;有效的管理工具是其成功实施的关键。本文将探讨在2024年&#xff0c;哪些敏捷…
阅读更多...
迁移学习——CycleGAN

迁移学习——CycleGAN

CycleGAN 1.导入需要的包2.数据加载&#xff08;1&#xff09;to_img 函数&#xff08;2&#xff09;数据加载&#xff08;3&#xff09;图像转换 3.随机读取图像进行预处理&#xff08;1&#xff09;函数参数&#xff08;2&#xff09;数据路径&#xff08;3&#xff09;读取文…
阅读更多...
基于redisson实现tomcat集群session共享

基于redisson实现tomcat集群session共享

目录 1、环境 2、修改server.xml 3、修改context.xml 4、新增redisson配置文件 5、下载并复制2个Jar包到Tomcat Lib目录中 6、 安装redis 7、配置nginx负载均衡 8、配置测试页面 9、session共享测试验证 前言&#xff1a; 上篇中&#xff0c;Tomcat session复制及ses…
阅读更多...
观测云 VS 开源自建

观测云 VS 开源自建

观测云是一款面向全技术栈的监控观测一体化产品方案&#xff0c;具备强大而丰富的功能&#xff0c;目标是帮助最终用户提升监控观测的能力&#xff0c;化繁为简&#xff0c;轻松的构建起完整的监控观测体系。同时能够帮助整个企业的开发技术团队从统一的观测能力上获得完整的收…
阅读更多...
ONLYOFFICE 文档开发者版 8.1：API 更新

ONLYOFFICE 文档开发者版 8.1：API 更新

随着版本 8.1 新功能的发布&#xff0c;我们更新了编辑器、文档生成器和插件的 API&#xff0c;并添加了 Office API 板块。阅读下文了解详情。 ​ ONLYOFFICE 文档是什么 ONLYOFFICE 文档是一个功能强大的文档编辑器&#xff0c;支持处理文本文档、电子表格、演示文稿、可填写…
阅读更多...
探索ChatGPT在程序员日常工作的多种应用

探索ChatGPT在程序员日常工作的多种应用

引言 在现代科技迅猛发展的今天&#xff0c;人工智能的应用已经深入到我们生活和工作的各个方面。作为程序员&#xff0c;我们时常面临大量繁杂的任务&#xff0c;从代码编写、错误调试到项目管理和团队协作&#xff0c;每一项都需要花费大量的时间和精力。近年来&#xff0c;…
阅读更多...
算法与数据结构——时间复杂度详解与示例（C#，C++）

算法与数据结构——时间复杂度详解与示例（C#，C++）

文章目录 1. 算法与数据结构概述2. 时间复杂度基本概念3. 时间复杂度分析方法4. 不同数据结构的时间复杂度示例5. 如何通过算法优化来提高时间复杂度6. C#中的时间复杂度示例7. 总结 算法与数据结构是计算机科学的核心&#xff0c;它们共同决定了程序的性能和效率。在实际开发中…
阅读更多...
大模型产品的“命名经济学”：名字越简单，产品越火爆？

大模型产品的“命名经济学”：名字越简单，产品越火爆？

文 | 智能相对论 作者 | 陈泊丞 古人云&#xff1a;赐子千金&#xff0c;不如教子一艺&#xff1b;教子一艺&#xff0c;不如赐子一名。 命名之妙&#xff0c;玄之又玄。 早两年&#xff0c;大模型爆火&#xff0c;本土厂商在大模型产品命名上可谓下足了功夫&#xff0c;引…
阅读更多...
最新文章

Copyright @ 2022~2023