数据结构基础：3.单链表的实现。

单链表的介绍和实现

  • 一.基本概念
    • 1.基本结构
    • 2.结构体节点的定义：
  • 二.功能接口的实现
    • 0.第一个节点：plist
    • 1打印链表
    • 2创建一个节点
    • 3.头插
    • 4.头删
    • 5.尾插
    • 6.尾删
    • 7.查找
    • 8.在pos之前插入x
    • 9.在pos之后插入x
    • 10.删除pos位置
    • 11.删除pos的后一个位置
    • 12.链表释放
  • 三.整体代码

一.基本概念

1.基本结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

逻辑结构：前面的叫做数据域，后面叫做指针域，指针是用来保存下一个节点的地址的。在逻辑上是这样连续的但是在实际的物理结构上面空间上不是连续的。请添加图片描述

物理结构：这些都是节点，在内存中是通过前一个节点保存后一个节点的地址这样的话就可以连续去寻找链表数据。
请添加图片描述

2.结构体节点的定义：

请添加图片描述

二.功能接口的实现

0.第一个节点：plist

如果我们想要创建好一个链表并且去使用他我们需要有这些节点并且通过结构体的成员变量去连接我们的这个结构体构成一个链表的状态因为我们的方向是单向的所以每一次使用的时候我们应该需要知道第一个节点的地址，并且第一个节点它在逻辑上必须处于链表的第一个位置，我们在进行接口的操作都是依赖于我们的第一个节点。（第一个节点如果要变化那么我们的在主函数中的第一个节点的地址就要变化）（地址的变化是需要传二级指针的）

请添加图片描述

1打印链表

打印链表只需要循环遍历一次链表的数据内容。（不需要对第一个节点的地址发生改变）

//打印链表
void SLTprint(SLTNode* plist)
{
	//循环遍历不去更改头所以不需要传二级指针

	//打印之前我们需要注意我们是否有数据打印
	//说明链表已经没有数值或者还没有节点数据
	assert(plist!=NULL);
	SLTNode* cur = plist;
	//一个节点的下一个是空就不打印数据了
	while (cur)
	{
		printf("%d->", cur->data);
		//循环的一个条件
		cur = cur->next;
	}
	printf("NULL\n");

}

2创建一个节点

一个新节点的创建需要注意一个参数和一个返回值，参数是我们的节点的数据值，返回的参数是这个节点的地址，因为我们只能通过存储地址的方式进行链表的连接。

//创建一个节点
SLTNode* BuySListNode(STLDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode*));
	if (newnode == NULL)
	{
		perror("malloc file\n");
		exit(-1);
		//开辟空间失败直接退出程序
	}
	//使用这个节点
	newnode->data = x;
	//因为这是一个新的节点我们的下一个数据还没有给它
	//它现在不需要去存储下一个节点的地址。
	newnode->next = NULL;
	return newnode;
}

3.头插

头插：我们的头节点每经过一次头插就要改变前面提过我们去使用链表的时候是需要第一个节点的指针的。这个指针如果改变是需要影响到接口外的实参的。（需要传二级指针改变）

//头插
//头插
void SLTpushfront(SLTNode** pphead, STLDatatype x)
{
	//插入一个数据需要一个新的节点
	SLTNode* newnode = BuySListNode(x);
	//是有数据，说明*pphead不是空。
	//如果直接改变第一个的地址那么。第二个数据就找不到了。
	newnode->next = *pphead;
	*pphead = newnode;
}

4.头删

头删需要把第一个节点给释放，原来的第二个作为新的头，需要对我们的第一个节点进行地址的改变（需要传二级指针）

void SLTpopfront(SLTNode** pphead)
{
	//删除数据如果没有数据就不去删除
	assert(*pphead != NULL);

	//不止一个数据，保存第二个节点的地址
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
	//释放老节点，拿到新节点
	*pphead = newhead;
}

5.尾插

不去修改第一个节点，可以传二级也可以传一级。

void SLTpushback(SLTNode** pphead, STLDatatype x)
{
	SLTNode* newnode = BuySListNode(x);
	//当没有数据的时候
	if (*pphead == NULL)
	{
		//对一个地址的修改
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		//下一个是NULL就是尾
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

6.尾删

有可能删除第一个所以需要传二级指针。

//尾删
void SLTpopback(SLTNode** pphead)
{
	assert(*pphead);

	//当链表中只剩下最后一个节点的时候，需要把头指针也制空。
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾
		SLTNode* cur = *pphead;
		SLTNode* prev = *pphead;
		while (cur->next != NULL)
		{
			//cur下一个是NULL说明现在的这个就是尾
			prev = cur;
			cur = cur->next;
		}
		//产生野指针的问题，确实释放了但是我们cur的前面一个指向的是一个野指针。
		free(cur);

		prev->next = NULL;
	}
}

7.查找

1.查找的区域不可以为空，返回一个节点地址。

SLTNode* SLTFind(SLTNode* phead, STLDatatype x)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
}

8.在pos之前插入x

1.如果pos是第一个位置相当于头插可以复用前面的代码也可以自己写一个。
2.有可能会改到头所以必须要传二级指针。

void SLTInsert(SLTNode** pphead, SLTNode* pos, STLDatatype x)
{
	SLTNode* newnode = BuySListNode(x);
	if (pos == *pphead)
	{
		SLTpushfront(pphead, x);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next!=pos)
		{
			cur=cur->next;
		}
		cur->next = newnode;
		newnode->next = pos;
	}
}

9.在pos之后插入x

void SLTInsertAfter(SLTNode* pos, STLDatatype x)
{
	SLTNode* newnode = BuySListNode(x);
	SLTNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

10.删除pos位置

// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		//头删
		SLTpopfront(pphead);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SLTNode* newhead = cur->next->next;
		free(pos);
		pos = NULL;
		cur->next = newhead;
	}
}

11.删除pos的后一个位置

// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos->next != NULL);
	if (pos->next->next == NULL)
	{
		free(pos->next);
		pos->next = NULL;
		pos->next = NULL;
	}
	else
	{
		SLTNode* next = pos->next->next;
		free(pos->next);
		pos->next = NULL;
		pos->next = next;
	}
	
}

12.链表释放

// 单链表的销毁
void SListDestroy(SLTNode** plist)
{
	assert(plist != NULL);
	//只需要释放不需要改变,所以一级就可以
	SLTNode* cur = *plist;
	while (cur->next!=NULL)
	{
		SLTNode* next = cur->next;
		cur->next = NULL;
		free(cur);
		cur = NULL;
		cur = next;
		SLTprint(cur);
	}
	cur->next = NULL;
	free(cur);
	cur = NULL;
	//原来的节点地址被释放，随机值但不是NULL
	*plist = NULL;
}

三.整体代码

#define _CRT_SECURE_NO_WARNINGS 1

#include"SLTNode.h"

//打印链表
void SLTprint(SLTNode* plist)
{
	//循环遍历不去更改头所以不需要传二级指针

	//打印之前我们需要注意我们是否有数据打印
	//说明链表已经没有数值或者还没有节点数据
	assert(plist!=NULL);
	SLTNode* cur = plist;
	//一个节点的下一个是空就不打印数据了
	while (cur)
	{
		printf("%d->", cur->data);
		//循环的一个条件
		cur = cur->next;
	}
	//实参是一个空指针但是存贮空指针的这个空间不是
	printf("NULL\n");

}
//创建一个节点
SLTNode* BuySListNode(STLDatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode*));
	if (newnode == NULL)
	{
		perror("malloc file\n");
		exit(-1);
		//开辟空间失败直接退出程序
	}
	//使用这个节点
	newnode->data = x;
	//因为这是一个新的节点我们的下一个数据还没有给它
	//它现在不需要去存储下一个节点的地址。
	newnode->next = NULL;
	return newnode;
}

//头插
void SLTpushfront(SLTNode** pphead, STLDatatype x)
{
	//插入一个数据需要一个新的节点
	SLTNode* newnode = BuySListNode(x);
	//是有数据，说明*pphead不是空。
	//如果直接改变第一个的地址那么。第二个数据就找不到了。
	newnode->next = *pphead;
	*pphead = newnode;
}

//头删
void SLTpopfront(SLTNode** pphead)
{
	//删除数据如果没有数据就不去删除
	assert(*pphead != NULL);

	//不止一个数据，保存第二个节点的地址
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	//释放老节点，拿到新节点
	*pphead = newhead;
}
//尾插
void SLTpushback(SLTNode** pphead, STLDatatype x)
{
	SLTNode* newnode = BuySListNode(x);
	//当没有数据的时候
	if (*pphead == NULL)
	{
		//对一个地址的修改
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		//下一个是NULL就是尾
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		cur->next = newnode;
	}
}
//尾删
void SLTpopback(SLTNode** pphead)
{
	assert(*pphead);

	//当链表中只剩下最后一个节点的时候，需要把头指针也制空。
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找尾
		SLTNode* cur = *pphead;
		SLTNode* prev = *pphead;
		while (cur->next != NULL)
		{
			//cur下一个是NULL说明现在的这个就是尾
			prev = cur;
			cur = cur->next;
		}
		//产生野指针的问题，确实释放了但是我们cur的前面一个指向的是一个野指针。
		free(cur);

		prev->next = NULL;
	}
}

SLTNode* SLTFind(SLTNode* phead, STLDatatype x)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
}

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, STLDatatype x)
{
	SLTNode* newnode = BuySListNode(x);
	if (pos == *pphead)
	{
		SLTpushfront(pphead, x);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next!=pos)
		{
			cur=cur->next;
		}
		cur->next = newnode;
		newnode->next = pos;
	}
}

// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, STLDatatype x)
{
	SLTNode* newnode = BuySListNode(x);
	SLTNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		//头删
		SLTpopfront(pphead);
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		SLTNode* newhead = cur->next->next;
		free(pos);
		pos = NULL;
		cur->next = newhead;
	}
}

// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos->next != NULL);
	if (pos->next->next == NULL)
	{
		free(pos->next);
		pos->next = NULL;
		pos->next = NULL;
	}
	else
	{
		SLTNode* next = pos->next->next;
		free(pos->next);
		pos->next = NULL;
		pos->next = next;
	}
	
}

// 单链表的销毁
void SListDestroy(SLTNode** plist)
{
	assert(plist != NULL);
	//只需要释放不需要改变,所以一级就可以
	SLTNode* cur = *plist;
	while (cur->next!=NULL)
	{
		SLTNode* next = cur->next;
		cur->next = NULL;
		free(cur);
		cur = NULL;
		cur = next;
		SLTprint(cur);
	}
	cur->next = NULL;
	free(cur);
	cur = NULL;
	//原来的节点地址被释放，随机值但不是NULL
	*plist = NULL;
}

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

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

相关文章

leetcode743. 网络延迟时间 floyd

leetcode743. 网络延迟时间 floyd

https://leetcode.cn/problems/network-delay-time/ 有 n 个网络节点，标记为 1 到 n。 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信…
阅读更多...
SpringBoot使用PropertiesLauncher加载外部jar包

SpringBoot使用PropertiesLauncher加载外部jar包

启用SpringBoot的PropertiesLauncher 使用SpringBoot的PropertiesLauncher可以优先加载外部的jar文件, 这样可以在程序运行前替换jar包, 官方文档: Launching Executable Jars 使用演示 建立一个SpringBoot工程, 工程中依赖一个叫自定义的utils包, 版本是1.0.0, 通过http接口…
阅读更多...
LiveGBS流媒体平台GB/T28181功能-支持轮巡播放分屏轮巡值守播放监控视频轮播大屏轮询播放

LiveGBS流媒体平台GB/T28181功能-支持轮巡播放分屏轮巡值守播放监控视频轮播大屏轮询播放

LiveGBS支持轮巡播放分屏轮巡值守播放监控视频轮播大屏轮询播放 1、背景2、分屏展示3、选择轮播通道4、配置轮播间隔(秒)5、点击开始轮播6、轮播停止及全屏7、搭建GB28181视频直播平台 1、背景 视频监控项目使用过程中，有时需要大屏值守，值守的时候多分…
阅读更多...
Sestra 实用教程（二）方程求解器

Sestra 实用教程（二）方程求解器

目 录 一、前言二、超单元分析三、惯性释放四、模态叠加法4.1 Eigenvalue solvers4.2 Static back substitution 五、模态综合法六、Master-Slave七、参考文献 一、前言 SESAM （Super Element Structure Analysis Module）是由挪威船级社（DNV-…
阅读更多...
mac m1安装Centos9

mac m1安装Centos9

先看结果（在mac M1 安装centos8 安装不成功的原因大部分是没有找到正确的系统） 由于Cnetos8 停服，现有mac m1 上能够按照的Centos8 并非由官方发布，因此寻找官方发布的能够在mac m1上安装的centos版本。 在YouTuBe上找到一个视频…
阅读更多...
redis突然变慢问题定位

redis突然变慢问题定位

CPU 相关：使用复杂度过高命令、数据的持久化，都与耗费过多的 CPU 资源有关 内存相关：bigkey 内存的申请和释放、数据过期、数据淘汰、碎片整理、内存大页、内存写时复制都与内存息息相关 磁盘相关：数据持久化、AOF 刷盘策略&…
阅读更多...
IntelliJ IDEA 2023.2 最新变化

IntelliJ IDEA 2023.2 最新变化

主要更新 AI Assistant 限定访问 Ultimate 在此版本中，我们为 IntelliJ IDEA 引入了一项重要补充 – AI Assistant。 AI Assistant 当前具备一组由 AI 提供支持的初始功能，提供集成式 AI 聊天，可以完成一些任务，例如自动编写文档…
阅读更多...
[JAVAee]定时器

[JAVAee]定时器

目录 定时器的含义 定时器的使用 定时器的解析 ①TaskQueue ​②TimerThread ③Timer 定时器的模拟实现 ①创建Task自定义类型 ②创建TimerThread类 ③Timer类 完整代码 定时器的含义 从名字上看,就是我们通俗理解的那个定时器.设置一定的时间,并在一定的时间后发生…
阅读更多...
01 矩阵（力扣）多源广度优先搜索 JAVA

01 矩阵（力扣）多源广度优先搜索 JAVA

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1 。 输入：mat [[0,0,0],[0,1,0],[0,0,0]] 输出：[[0,0,0],[0,1,0],[0,0,0]] 输入…
阅读更多...
代理模式--静态代理和动态代理

代理模式--静态代理和动态代理

1.代理模式 定义：代理模式就是代替对象具备真实对象的功能，并代替真实对象完成相应的操作并且在不改变真实对象源代码的情况下扩展其功能，在某些情况下，⼀个对象不适合或者不能直接引⽤另⼀个对象，⽽代理对象可以在客户…
阅读更多...
CentOS 8 错误: Error setting up base repository

CentOS 8 错误: Error setting up base repository

配置ip、掩码、网关、DNS VMware网关可通过如下查看 打开网络连接 配置镜像的地址 vault.centos.org/8.5.2111/BaseOS/x86_64/os/
阅读更多...
python 面向对象编程的特点 - 封装 - 继承(经典类、新式类) - 多态 - 静态方法、类方法 - 下划线的使用 - 回合制攻击游戏实验

python 面向对象编程的特点 - 封装 - 继承(经典类、新式类) - 多态 - 静态方法、类方法 - 下划线的使用 - 回合制攻击游戏实验

目录 面向对象编程的特点： 封装：封装是将数据和操作（方法）封装在一个对象中的能力 继承：继承是指一个类（子类）可以继承另一个类（父类）的属性和方法。 我们为什么需要继…
阅读更多...
PostgreSQL构建时间

PostgreSQL构建时间

– PostgreSQL构建时间 select make_timestamp(2023,7,27,7,34,16);
阅读更多...
Ubuntu—vi编辑器的使用一

Ubuntu—vi编辑器的使用一

vi编辑器 vi是Linux中最基本的编辑器。但vi编辑器在系统管理、服务器配置工作中永远都是无可替代的。 vi编辑器的使用 vi有以下三种模式 命令行模式 用户在用vi编辑文件时， 最初进入的是该模式。可以进行复制、粘贴等操作 插入模式 进行文件编辑， 按…
阅读更多...
Java的第十五篇文章——网络编程（后期再学一遍）

Java的第十五篇文章——网络编程（后期再学一遍）

目录 学习目的 1. 对象的序列化 1.1 ObjectOutputStream 对象的序列化 1.2 ObjectInputStream 对象的反序列化 2. 软件结构 2.1 网络通信协议 2.1.1 TCP/IP协议参考模型 2.1.2 TCP与UDP协议 2.2 网络编程三要素 2.3 端口号 3. InetAddress类 4. Socket 5. TCP网络…
阅读更多...
VMPWN的入门系列-2

VMPWN的入门系列-2

温馨提示： 文章有点长，图片比较多，请耐心阅读 实验四 VMPWN4 题目简介 这道题应该算是虚拟机保护的一个变种，是一个解释器类型的程序，何为解释器？解释器是一种计算机程序，用于解释和执行源代码。…
阅读更多...
PKG内容查看工具：Suspicious Package for Mac安装教程

PKG内容查看工具：Suspicious Package for Mac安装教程

Suspicious Package Mac版是一款Mac平台上的查看 PKG 程序包内信息的应用，Suspicious Package Mac版支持查看全部包内全部文件，比如需要运行的脚本，开发者，来源等等。 suspicious package mac使用简单，只需在选择pkg安…
阅读更多...
螺旋矩阵 II

螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1： 输入：n 3 输出：[[1,2,3],[8,9,4],[7,6,5]] 示例 2： 输入：n 1 输出&a…
阅读更多...
软工导论知识框架（二）结构化的需求分析

软工导论知识框架（二）结构化的需求分析

本章节涉及很多重要图表的制作，如ER图、数据流图、状态转换图、数据字典的书写等，对初学者来说比较生僻，本贴只介绍基础的轮廓，后面会有单独的帖子详解各图表如何绘制。 一.结构化的软件开发方法：结构化的分析、设计、…
阅读更多...
【并发编程】ForkJoinPool工作原理分析

【并发编程】ForkJoinPool工作原理分析

目录 前置内容课程内容一、由一道算法题引发的思考1.算法题2.什么是归并排序法 二、什么是Fork/Join框架1.基本介绍2.ForkJoinPool2.ForkJoinPool构造函数及参数解读3.任务提交方式4.工作原理图5.工作窃取6.和普通线程池之间的区别7.ForkJoinTask 学习总结 前置内容 Q1&#x…
阅读更多...
最新文章

Copyright @ 2022~2023