链表的实现（文末附完整代码）

链表的概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
我们在上一篇文章所学习的顺序表是连续存储的
例如：
顺序表就好比火车上的一排座位，是连续的
而链表就好比是火车的各节车厢，中间有东西将其互相连接的
在这里插入图片描述
链表的基本结构图如下：
有一个指针指向下一个节点
在这里插入图片描述

链表的概念及结构

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
链表可以是单向和双向，循环和不循环，带头和不带头，这样一组合，就会出现八种类型的列表
单向的列表如下：
在这里插入图片描述
双向列表：
相比较单向，双向的增删查改较为容易，他会自带一个prev的节点，能顾标记当前节点的前一个节点
在这里插入图片描述
循环列表：
其实循环列表就是最后一个节点指向了开头节点
在这里插入图片描述
带头和不带头：
头节点我们可以称其为哨兵位，它是不会在链表中存储有效的数据的
在这里插入图片描述
其实八种链表我们最常用的只有两种：
无头单向非循环链表：
在这里插入图片描述
带头双向循环列表：
在这里插入图片描述

  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构
  2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是后面的学习中你会发现其实他是比较简单的

链表的实现

首先我们要了解的就是单链表的实现：
头文件如下：

#include<stdio.h>
#include<assert.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** plist);

新节点的创建：
我们要创建一个节点，首先就是要为他动态开辟一个空间
然后再将这个新节点newnode的值赋予x，并且将他的next置为空，然后函数返回这个节点

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

链表的打印：
打印链表是我们可以用一个符号->来代替空格，但是链表实际上是没有这个符号的
我们可以首先定义cur，从链表的第一个节点开始遍历，知道cur为空时，就不会打印了，并且打印一次cur的data，cur要等于cue的next

void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

单链表的尾插：
这里我们要注意的是要记得用二级指针，因为当链表为空时，我们要改变的是节点的地址，而我们要改变地址，就要用地址的地址，也就是二级指针
首先，需要插入一个节点我们要做的就是创建一个新节点，我们之前定义了的一个函数直接使用
然后我们创建一个tail指针，让他从链表的第一个位置开始遍历，一直遍历到最后一个节点，此时令tail的next等于newnode即可

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	/*assert(*pplist);*///链表为空时可以尾插
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

单链表的头插：
头插比较简单，我们直接将新节点的next等于链表的第一个节点即可，也就是*pplist，我们传进来的是**pplist，是节点地址的地址，所以我们需要解引用一次才能将地址给newnode的next

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

单链表的尾删：
尾删的情况我们要分为两种：
1.只有一个节点时：
只有一个节点时我们直接free掉这个节点，其次为了防止野指针，我们要将其置空
2.当有多个节点时：
我们创建一个tail和prev，然后用循环将tail遍历到最后一个节点，循环的终止条件时tail->next为空，条件满足时就将tail赋予prev，当跳出循环时，prev就是尾节点的前一个节点，我们直接将tail给free掉，将其置空，这样尾节点就被删除了
在这里插入图片描述

void SListPopBack(SListNode** pplist)
{
	assert(*pplist);//链表为空时不能再删，暴力检查 
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pplist;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

单链表的头删：
头删就很简单了，首先定义一个tail存入第一个节点的位置，然后将第一个节点的位置移动到他的next，注意记得将临时存储第一个节点位置的指针给free掉，避免出现野指针的问题

void SListPopFront(SListNode** pplist)
{
	assert(*pplist);//链表为空时不能再删，暴力检查
	SListNode* tail = *pplist;
	*pplist = (tail)->next;
	free(tail);
}

节点的查找：
节点的查找也比较容易，直接用while循环遍历，如果cur的data和x相等，就返回cur，否则就是没有这个节点，返回null

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur->next)
	{
		if (cur->data == x)
		{
			return cur;
			//break;
		}
		cur = cur->next;
	}
	return NULL;
}

在一个节点之后插入节点：
需要插入节点首先要做的就是创建一个新节点
然后首先要做的是将newnode的next连接到要插入位置pos的next
再将pos的next置为newnode
这里注意，位置不能颠倒，不然newnode的next就找不到了
在这里插入图片描述

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

删除一个节点之后的节点：
要删除节点之后的一个节点，首先这个节点之后一定要有一个节点，所以要对pos->next进行断言
我们将pos->next存储到next中，然后将pos->next直接指向next->next即可，也就是把pos->next=pos->next->next
在这里插入图片描述

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	//pos->next = pos->next->next;
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

单链表的销毁：
直接将pplist置空即可

void SListDestroy(SListNode** pplist)
{
	SListNode* node = *pplist;
	node = NULL;
	free(node);
}

好了，今天的分享到这里就结束了，感谢大家的支持！
完整代码如下：

SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	/*assert(*pplist);*///链表为空时可以尾插
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SListNode* tail = *pplist;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

void SListPopBack(SListNode** pplist)
{
	assert(*pplist);//链表为空时不能再删，暴力检查 
	//SListNode* tail = pplist;
	//while (tail->next->next)
	//{
	//	tail = tail->next;
	//}
	//free(tail->next);
	//tail->next = NULL;
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pplist;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

void SListPopFront(SListNode** pplist)
{
	assert(*pplist);//链表为空时不能再删，暴力检查
	SListNode* tail = *pplist;
	*pplist = (tail)->next;
	free(tail);
}

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur->next)
	{
		if (cur->data == x)
		{
			return cur;
			//break;
		}
		cur = cur->next;
	}
	return NULL;
}

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}


void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	//pos->next = pos->next->next;
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

void SListDestroy(SListNode** pplist)
{
	SListNode* node = *pplist;
	node = NULL;
	free(node);

}

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

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

相关文章

LabVIEW中如何在网络上使用远程VI服务器

LabVIEW中如何在网络上使用远程VI服务器

LabVIEW中如何在网络上使用远程VI服务器 如何在网络上使用远程VI服务器&#xff1f; 解答: 首先&#xff0c;需要在远程的计算机上打开一个在VI服务器上的LabVIEW应用程序的引用。这可以通过“Open ApplicationReference“函数实现。然后用“Open VI Reference”函数打开一个…
阅读更多...
VulnHub Prime_Series_Level-1

VulnHub Prime_Series_Level-1

一、信息收集 1.nmap扫描 ┌──(root&#x1f480;kali)-[~/桌面] └─# arp-scan -l┌──(root&#x1f480;kali)-[~/桌面] └─# nmap -sS -A -p- 192.168.103.202发现开放了22和80端口 2.web页面 打开80端口的web页面&#xff0c;是一张静态的图片&#xff0c;没什么价…
阅读更多...
Optimal Multimodal Travelway Design for an Urban Street Network

Optimal Multimodal Travelway Design for an Urban Street Network

方法 作者未提供代码
阅读更多...
Linux文件系统(1)

Linux文件系统(1)

Linux文件系统(1) &#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;Linux &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 本博客主要内容从系统层面重新认识我们的文件系统 文…
阅读更多...
java的类和继承构造

java的类和继承构造

一些小技巧 类和对象 什么是类&#xff0c;对象&#xff0c;方法&#xff1f; 在下面的 Java 代码中&#xff0c;定义了一个名为 Person 的类&#xff0c;并提供了构造方法来初始化对象的属性。类中定义了 eat、sleep 和 work 三个方法&#xff0c;用于表示人的行为。在 main 方…
阅读更多...
为什么Android 手机这么慢？如何提高 Android 手机的运行速度

为什么Android 手机这么慢？如何提高 Android 手机的运行速度

速印机&#xff08;理想、荣大等&#xff09;、复印机&#xff08;夏普、东芝、理光、佳能、震旦等全系列&#xff09;、打印机、扫描仪、传真机、多媒体教学一体机、交互式电子白板、报警器材、监控、竞业达监考设备及其它监考设备、听力考试设备、特种安防设备维护及维修。吴…
阅读更多...
JavaScript_动态表格_添加功能

JavaScript_动态表格_添加功能

1、动态表格_添加功能.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>动态表格_添加功能</title><style>table{border: 1px solid;margin: auto;width: 100%;}td,th{text-align: ce…
阅读更多...
Django 基于ORM的CURD、外键关联，请求的生命周期

Django 基于ORM的CURD、外键关联，请求的生命周期

文章目录 基于ORM进行的CURDORM外键关联Django请求的生命周期流程图 基于ORM进行的CURD 本质上就是通过面向对象的方式&#xff0c;对数据库的数据进行增、删、改、查。 这里将会将我们之前所有内容结合到一起&#xff0c;首先确保基于上序操作已经建立好了UserInfo表&#xff…
阅读更多...
odoo16 库存初始化 excel导入问题2

odoo16 库存初始化 excel导入问题2

产品导入模板： excel内容: 导入测试 查看可能的值，发现没有ml，在计量单位中增加ml选项（不选创建，知道为什么不，仔细想想，创建不知ml是什么单位） 位置不能在此导入，故取消 测试正常 导入成功 总结：产品导入时，位置无法指定，只建产品名称，计量单位，采购单位，
阅读更多...
自定义Graph Component：1.1-JiebaTokenizer具体实现

自定义Graph Component：1.1-JiebaTokenizer具体实现

JiebaTokenizer类继承自Tokenizer类&#xff0c;而Tokenizer类又继承自GraphComponent类&#xff0c;GraphComponent类继承自ABC类&#xff08;抽象基类&#xff09;。本文使用《使用ResponseSelector实现校园招聘FAQ机器人》中的例子&#xff0c;主要详解介绍JiebaTokenizer类…
阅读更多...
python工具CISCO ASA设备任意文件读取

python工具CISCO ASA设备任意文件读取

​python漏洞利用 构造payload&#xff1a; /CSCOT/translation-table?typemst&textdomain/%2bCSCOE%2b/portal_inc.lua&default-language&lang../漏洞证明&#xff1a; 文笔生疏&#xff0c;措辞浅薄&#xff0c;望各位大佬不吝赐教&#xff0c;万分感谢。 免…
阅读更多...
golang Copier 数据复制

golang Copier 数据复制

Copier I am a copier, I copy everything from one to another Copier是golang实现的&#xff0c;实现不同数据结构之间数据复制的工具包 github地址 使用方法 以User和Employee之间相互复制为例 使用的版本为 v0.3.5 入门 package mainimport ("fmt""git…
阅读更多...
DevChat 初探之 RBAC 模型的实现

DevChat 初探之 RBAC 模型的实现

今天我们来尝试一款编程辅助助手 DevChat, 看能不能提升咱们的日常编程效率。作为一款编程助手&#xff0c;我们来看看它与 Copilot, CodeWhisperer 同领域产品的一些区别和特色。定个小目标&#xff0c;通过 DevChat 实现一个简单的 RBAC 模型&#xff0c;小试牛刀一下&#x…
阅读更多...
Acer宏碁Aspire A715-75G笔记本工厂模式原厂Windows10预装OEM系统2004带恢复功能

Acer宏碁Aspire A715-75G笔记本工厂模式原厂Windows10预装OEM系统2004带恢复功能

下载链接&#xff1a;https://pan.baidu.com/s/1nJFd25lElc1VAPf_RqSDYA?pwdd05h 提取码&#xff1a;d05h 原装出厂系统自带所有驱动、Office办公软件、出厂主题壁纸、系统属性Acer宏基专属的LOGO标志、 Acer Care Center、Quick Access等预装程序 所需要工具&#xff1a…
阅读更多...
kubenetes-kubelet组件

kubenetes-kubelet组件

一、kubelet架构 每个节点都运行一个kubelet进程&#xff0c;默认监听10250端口&#xff0c;kubelet作用非常重要&#xff0c;是节点的守护神。 接收并执行 master发来的指令。管理Pod及Pod中的容器。每个kubelet进程会在API Server 上注册节点自身信息&#xff0c;定期向mast…
阅读更多...
mysql讲解2 之事务 索引 以及权限等

mysql讲解2 之事务 索引 以及权限等

系列文章目录 mysql 讲解一 博客链接 点击此处即可 文章目录 系列文章目录一、事务1.1 事务的四个原则1.2 脏读 不可重复读 幻读 二、索引三,数据库用户管理四、mysql备份 一、事务 1.1 事务的四个原则 什么是事务 事务就是将一组SQL语句放在同一批次内去执行 如果一个SQ…
阅读更多...
常见后缀名总结 为你指点迷津

常见后缀名总结 为你指点迷津

相信在日常的学习和工作中&#xff0c;大家一定会遇到各种各样的文件类型&#xff0c;他们的后缀名类型各不相同&#xff0c;诸多陌生的文件格式经常让大家不知道他们存在于电脑的意义&#xff0c;想删又没法删&#xff0c;想执行又无法执行。 今天&#xff0c;学长就带领大家一…
阅读更多...
笔记：AI量化策略开发流程-基于BigQuant平台（二）

笔记：AI量化策略开发流程-基于BigQuant平台（二）

五、模型训练股票预测 完成了数据处理&#xff0c;接下来就可利用平台集成的各算法进行模型训练和模型预测啦。本文将详细介绍“模型训练”、“模型预测”两大模块操作、原理。 模型训练和模型预测是AI策略区别于传统量化策略的核心&#xff0c;我们通过模型训练模块利用训练…
阅读更多...
c语言练习11周（6~10）

c语言练习11周（6~10）

输入任意字串&#xff0c;将串中除了首尾字符的其他字符升序排列显示&#xff0c;串中字符个数最多20个。 题干 输入任意字串&#xff0c;将串中除了首尾字符的其他字符升序排列显示&#xff0c;串中字符个数最多20个。输入样例gfedcba输出样例gbcdefa 选择排序 #include<s…
阅读更多...
每日一题(LeetCode)----数组--长度最小的子数组

每日一题(LeetCode)----数组--长度最小的子数组

每日一题(LeetCode)----数组–长度最小的子数组 1.题目&#xff08; 209.长度最小的子数组&#xff09; 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] &…
阅读更多...
最新文章

Copyright @ 2022~2023