【数据结构】单链表（一）

上一篇【数据结构】顺序表-CSDN博客  我们了解了顺序表，但是呢顺序表涉及到了一些问题，比如，中间/头部的插入/删除，时间复杂度为O(N);增容申请空间、拷贝、释放旧空间会有不小的消耗；增容所浪费的空间... 我们如何去解决这些问题？本篇介绍另一个数据结构——链表

1. 链表的概念及结构

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

链表大概是什么样的呢？看下图

链表是由一个一个的节点组成，再顺序表中，数据是连续存放的，我们想找到下一个数据顺着前一个数据找就行了，而链表中数据存放空间是不连续的，所以我们就需要一个指针来保存下一个节点的地址，所以，我们如果要定义链表，只需要定义链表的节点结构就行了

(在【C语言】结构体详解-CSDN博客 的1.3 结构体的自引用 中介绍过)

struct SListNode
{
	int data;//数据
	struct SListNode* next;//下一个数据的地址
};

和上一篇一样，创建一个头文件，两个源文件

 也是一样，在头文件SList.h中定义单链表的结构，并对类型和结构体改名

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int Type; 
//定义节点结构
typedef struct SListNode
{
	Type data;
	struct SListNode* next;
}SLNode;

我们先创建几个节点，在test.c中实现

#include "SList.h" //包含头文件
void SListtest1()
{
	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//创建节点1
	node1->data = 1;//赋值

	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));//创建节点2
	node2->data = 2;//赋值

	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));//创建节点3
	node3->data = 3;//赋值

	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));//创建节点4
	node4->data = 4;//赋值
}
int main()
{
	SListtest1();
	return 0;
}

虽然我们创建好了节点，但是这几个节点现在还不能互相找到，所以我们接下来要将这几个节点连接起来，怎么连接？存下一个节点的地址

void SListtest1()
{
	SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));//创建节点1
	node1->data = 1;//赋值
	SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));//创建节点2
	node2->data = 2;//赋值
	SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));//创建节点3
	node3->data = 3;//赋值
	SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));//创建节点4
	node4->data = 4;//赋值
	//将四个节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
}

现在就构成了一个链表，有了这个简单的链表，我们来写一个函数打印一下里面的数据

链表的打印

在SList.h中进行函数的声明

void SLPrint(SLNode* ps);//打印

参数是链表的节点的地址 

在SList.c中进行函数的实现

#include "SList.h"
void SLPrint(SLNode* ps) //打印
{
	SLNode* pcur = ps;//pcur指向当前链表的第一个节点
}

要打印当然就要循环遍历，写一个while循环，判断条件为pcur，不为NULL进入循环 

void SLPrint(SLNode* ps) //打印
{
	SLNode* pcur = ps;//pcur指向当前链表的第一个节点
	while (pcur) //判断第一个节点是否为NULL
	{
     //....
	}
}

 进入循环后打印内容

void SLPrint(SLNode* ps) //打印
{
	SLNode* pcur = ps;//pcur指向当前链表的第一个节点
	while (pcur)
	{
		printf("%d->", pcur->data);//打印内容
	}
}

打印完一个数据后，要把下一个节点值部分的地址给pcur ，也就是pcur要存node2中2的地址，此时pcur不再指向node1，指向了node2

void SLPrint(SLNode* ps) //打印
{
	SLNode* pcur = ps;//pcur指向当前链表的第一个节点
	while (pcur)
	{
		printf("%d->", pcur->data);//打印内容
		pcur = pcur->next;//指向下一个节点
	}
	printf("NULL\n");
}

在test.c中测试

测试时我们不直接传链表的第一个节点node1，而是再定义一个结构体指针plist去指向node1，让plist作为参数传过去

    SLNode* plist = node1;
	SLPrint(plist);

虽然有点多此一举，但这样会让我们的代码更完善 

运行结果

 2.链表的插入

实际使用链表的时候我们不会像上面那样一个一个创建，初始时候是一个空链表，会跟顺序表类似进行空间开辟然后插入数据

2.1空间申请创建节点

插入数据前依旧是要判断空间够不够

在SList.h中进行函数的声明

SLNode* SLBuyNode(Type x);//申请空间创建节点

返回值是节点的地址，参数就是要插入的数据

在SList.c中进行函数的实现

SLNode* SLBuyNode(Type x)//申请空间创建节点
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL) //空间申请失败
	{
		perror("malloc");
		return 1;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2.2 尾插

在SList.h中进行函数的声明

void SLPushBack(SLNode** ps, Type x);//尾插

参数是链表的节点地址，是一个二级指针，和要插入的数据

我们要给函数传地址，这样形参的改变才能影响实参，对参数的理解如下，这很重要，这里提前展示将要在test.c中测试用的部分代码 

在SList.c中进行函数的实现

尾插要先找到尾节点，再将尾节点和新节点连接起来 ，此时node4的地址部分就不再是NULL 而是新节点的地址

代码如何实现呢 ？先找尾节点

void SLPushBack(SLNode* ps, Type x)//尾插
{
	SLNode* ptail = ps;//定义尾节点，开始时指向头节点
	while (ptail->next != NULL)//遍历链表数据，找尾节点
	{
		ptail = ptail->next;
	}
	//跳出循环后ptail指向尾节点
}

然后我们直接调用创建节点的函数，放在找尾节点前面，最后赋值

void SLPushBack(SLNode* ps, Type x)//尾插
{
	SLNode* newnode = SLBuyNode(x);//申请空间创建节点
	SLNode* ptail = ps;//定义尾节点，开始时指向头节点
	while (ptail->next != NULL)//遍历链表数据，找尾节点
	{
		ptail = ptail->next;
	}
	//跳出循环后ptail指向尾节点
	ptail->next = newnode;//直接赋值
}

 但是呢，链表在没有赋值的时候是空链表，所以我们要讨论空链表的情况，如果是空链表，直接让ps指向新节点newnode，所以最终的代码如下

void SLPushBack(SLNode** pps, Type x)//尾插
{
	assert(pps);//pps不可以为NULL
	SLNode* newnode = SLBuyNode(x);//申请空间创建节点
	if (*pps == NULL) //*pps可以为NULL，表示空链表
	{
		*pps = newnode;
	}
	else //非空链表
	{
		SLNode* ptail = *pps;//定义尾节点，开始时指向头节点
		while (ptail->next)//遍历链表数据，找尾节点
		{
			ptail = ptail->next;
		}
		//跳出循环后ptail指向尾节点
		ptail->next = newnode;//直接赋值
	}
}

我们再来看test.c中测试的代码

void SListtest2()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLPrint(plist);//打印
}
int main()
{
	//SListtest1();
	SListtest2();
	return 0;
}

多插入几个数据，运行看结果，插入成功

2.3 头插

 在SList.h中进行函数的声明

void SLPushHead(SLNode** pps, Type x);//头插

同样的，参数也是一个二级指针，还有要插入的数据

在SList.c中进行函数的实现

我们需要做两件事，一个是将newnode和原本的首节点连接在一起，另一件事是*pps要指向新的首节点 

 链表不为NULL时，代码如下

void SLPushHead(SLNode** pps, Type x)//头插
{
	assert(pps);//pps不能为NULL
	SLNode* newnode = SLBuyNode(x);//申请空间创建节点
	newnode->next = *pps;
	*pps = newnode;
}

当链表为NULL时，分析一下

当前代码也可以实现

在test.c中测试

void SListtest2()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPushBack(&plist, 3);
	SLPushBack(&plist, 4);
	SLPrint(plist);//打印
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPushHead(&plist, 8);
	SLPrint(plist);//打印
}

看一下运行结果

3.链表的删除

删除数据，链表就不能为空，不然删啥呢?

 3.1 尾删

在SList.h中进行函数的声明

void SLPopBack(SLNode** pps);//尾删

在SList.c中进行函数的实现

很显然，首先就是找尾节点，找到尾节点之后直接释放吗？node4释放后node3->next里面依然存放着node4的地址，但此时指向的空间已经没了，此时的指针就成了一个野指针 ，所以我们还要将被释放节点的前一个节点的指针置空

所以我们还要找尾节点的前一个节点

void SLPopBack(SLNode** pps)//尾删
{
	assert(pps && *pps);//pps和链表都不能为空
	SLNode* prev = *pps;//定义尾节点前一个节点
	SLNode* ptail = *pps;//定义尾节点
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	//此时找到了尾节点和尾节点前一个节点
	free(ptail);//释放尾节点
	ptail = NULL;//置空
	prev->next = NULL;//置空尾节点前一个节点
}

如果这个链表只有一个节点呢，这个代码可行吗？来分析一下

我们把节点释放并置空后，prev->next就不存在了，函数最后一句代码就不能实现，所以，当链表里只有一个节点时，直接释放就行了

void SLPopBack(SLNode** pps)//尾删
{
	assert(pps && *pps);//pps和链表都不能为空
	if ((*pps)->next == NULL)//链表只有一个节点
	{
		free(*pps);//释放节点
		*pps = NULL;//置空
	}
	else //链表不止一个节点
	{
		SLNode* prev = *pps;//定义尾节点前一个节点
		SLNode* ptail = *pps;//定义尾节点
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//此时找到了尾节点和尾节点前一个节点
		free(ptail);//释放尾节点
		ptail = NULL;//置空
		prev->next = NULL;//置空尾节点前一个节点
	}
}

在test.c中测试

void SListtest2()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPrint(plist);//打印
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLPopBack(&plist);//尾删
	SLPrint(plist);//打印
}

看下结果，尾删成功

3.2 头删

在SList.h中进行函数的声明

void SLPopHead(SLNode** pps);//头删

在SList.c中进行函数的实现

我们要删除头节点，跟删除尾节点不一样，如果我们把首节点释放掉，还能找到首节点里的next吗？不能，不能的话就找不到第二个节点以及剩下的节点

我们应该先把下一个节点的信息存储起来

SLNode* Next = (*pps)->next;//存节点

 然后把原头节点释放

free(*pps);

最后让*pps指向新的头节点

*pps = Next;

所以代码如下

void SLPopHead(SLNode** pps)//头删
{
	assert(pps && *pps);//pps和链表都不能为空
	SLNode* Next = (*pps)->next;//存节点
	free(*pps);
	*pps = Next;
}

当链表只有一个节点时，分析一下，上面的代码也是可以完成的

我们在test.c中测试一下

void SListtest2()
{
	SLNode* plist = NULL;//空链表
	SLPushBack(&plist, 1);//尾插
	SLPushBack(&plist, 2);
	SLPrint(plist);//打印
	SLPushHead(&plist, 6);//头插
	SLPushHead(&plist, 7);
	SLPrint(plist);//打印
	SLPopBack(&plist);//尾删
	SLPrint(plist);//打印
	SLPopHead(&plist);//头删
	SLPrint(plist);//打印
}

下篇我们再继续介绍更多内容，拜拜~

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

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

相关文章

IOS虚拟键盘弹出后，弹窗的按钮点击不起作用，不会触发click事件

IOS虚拟键盘弹出后，弹窗的按钮点击不起作用，不会触发click事件

背景 讨论区项目的回复框&#xff0c;使用的是Popup和TextArea做&#xff0c;布局如下图&#xff0c;希望键盘弹出时候&#xff0c;回复框可以紧贴键盘&#xff0c;这点实现起来比较简单&#xff0c;监听resize事件&#xff0c;动态修改popup的这题内容的top值即可&#xff0c…
阅读更多...
ONERugged车载平板电脑厂家丨工业车载电脑优势体现丨3年质保

ONERugged车载平板电脑厂家丨工业车载电脑优势体现丨3年质保

作为现代社会中必不可少的出行工具&#xff0c;汽车不仅仅是代步工具&#xff0c;更是我们生活中的重要一部分。而在如此多功能的汽车内&#xff0c;一款高可靠性、适应不同行业应用的车载平板电脑成为了当下的热门选择。ONERugged车载平板电脑以其卓越的品质和强大的功能而备受…
阅读更多...
自动化 单元测试Test

自动化 单元测试Test

XCTest测试框架(单元测试XCTests、性能测试XCPPerformanceTests、用户界面测试XCUItests) 单元测试XCTests&#xff1a;测试应用中事件或逻辑是否预期工作。 用户界面测试XCUItests&#xff1a;测试用户与应用的UI交互(如点击按钮、滑动屏幕)。 性能测试XCPPerformanceTests&am…
阅读更多...
电池电量监测系统设计 单片机+LabVIEW+Matlab+Protues+Keil程序

电池电量监测系统设计 单片机+LabVIEW+Matlab+Protues+Keil程序

目录 前言 提供 软件 系统展示 1.放电试验及其处理 2.硬件系统原理图 3.下位机程序 4.显示 5.上位机界面 6.上位机程序 7.文档 资料下载地址&#xff1a;电池电量监测系统设计 单片机LabVIEWMatlabProtuesKeil程序 前言 这套系统首先使用Matlab分析获得了电压…
阅读更多...
【opencv】示例-essential_mat_reconstr.cpp 从两幅图像中恢复3D场景的几何信息

【opencv】示例-essential_mat_reconstr.cpp 从两幅图像中恢复3D场景的几何信息

导入OpenCV的calib3d, highgui, imgproc模块以及C的vector, iostream, fstream库。定义了getError2EpipLines函数&#xff0c;这个函数用来计算两组点相对于F矩阵&#xff08;基础矩阵&#xff09;的投影误差。定义了sgn函数&#xff0c;用于返回一个双精度浮点数的符号。定义了…
阅读更多...
系统架构设计图

系统架构设计图

首先明确应用架构的定义&#xff0c;从百度百科上即可了解到何为应用架构&#xff1a; 应用架构&#xff08;Application Architecture&#xff09;是描述了IT系统功能和技术实现的内容。应用架构分为以下两个不同的层次&#xff1a; 企业级的应用架构&#xff1a;企业层面的应…
阅读更多...
git bash用法-批量修改文件名

git bash用法-批量修改文件名

在win系统上安装git bash可以使用命令行模式操作&#xff0c;比较方便 1.原始文件名 2.代码 for file in *3utr*; do mv "$file" "$(echo "$file" | sed s/3utr/5utr/)"; done3.修改后的文件名
阅读更多...
基于FPGA的HDMI设计导航页面

基于FPGA的HDMI设计导航页面

FPGA使用HDMI更多时候用于传输图像数据&#xff0c;并不会传输音频数据&#xff0c;因此以下文章均采用DVI接口协议&#xff0c;HDMI与DVI的视频传输协议基本一致&#xff0c;区别也很小。 首先需要了解HDMI的来源&#xff0c;以及物理接口类型以及引脚信号&#xff0c;最后对几…
阅读更多...
自动化测试-web（弹窗/滚动条/鼠标/等待等操作）

自动化测试-web（弹窗/滚动条/鼠标/等待等操作）

一、弹窗 为什么要处理弹窗&#xff1f; 如果页面操作过程中&#xff0c;有弹窗出现&#xff0c;不处理&#xff0c;无法继续对页面操作。 弹窗类型&#xff1a; js原生弹窗&#xff1a; 警告框、输入框、提示框&#xff0c;这些必须处理 如何处理&#xff1a; 1&#xff0…
阅读更多...
HarmonyOS实战开发-设备管理合集（非系统特性）

HarmonyOS实战开发-设备管理合集（非系统特性）

介绍 本示例集合设备管理相关&#xff08;非系统特性&#xff09;不需要复杂功能展示的模块&#xff0c;展示了各个模块的基础功能&#xff0c;包含&#xff1a; ohos.batteryInfo (电量信息)ohos.charger (充电类型)ohos.deviceInfo (设备信息)ohos.power (系统电源管理)oho…
阅读更多...
Windows上面搭建Flutter Android运行环境

Windows上面搭建Flutter Android运行环境

Flutter Android环境搭建 电脑上面安装配置JDK电脑上下载安装Android Studio电脑上面下载配置Flutter Sdk &#xff08;避坑点一&#xff09;下载SDK配置对应的环境变量 到path 电脑上配置Flutter国内镜像运行 flutter doctor命令检测环境是否配置成功创建运行Flutter项目&…
阅读更多...
openssl3.2 - exp - zlib

openssl3.2 - exp - zlib

文章目录 openssl3.2 - exp - zlib概述笔记命令行实现程序实现备注 - 压缩时无法base64压缩时无法带口令压缩实现 - 对buffer进行压缩和解压缩测试效果工程实现main.cppCOsslZlibBuffer.hCOsslZlibBuffer.cpp总结END openssl3.2 - exp - zlib 概述 客户端和服务端进行数据交换…
阅读更多...
数据库的负载均衡，高可用实验

数据库的负载均衡，高可用实验

一 高可用负载均衡集群数据库实验 1.实验拓扑图 2.实验准备(同一LAN区段)&#xff08;ntp DNS&#xff09; 客户端&#xff1a;IP&#xff1a;192.168.1.5 下载&#xff1a;MariaDB 负载均衡器&#xff1a;IP&#xff1a;192.168.1.1 下载&#xff1a;keepalived ipvsadm I…
阅读更多...
鸿蒙实战开发-如何实现选择并查看文档与媒体文件

鸿蒙实战开发-如何实现选择并查看文档与媒体文件

介绍 应用使用ohos.file.picker、ohos.multimedia.mediaLibrary、ohos.file.fs 等接口&#xff0c;实现了picker拉起文档编辑保存、拉起系统相册图片查看、拉起视频并播放的功能。 效果预览 使用说明&#xff1a; 在首页&#xff0c;应用展示出最近打开过的文档信息&#xf…
阅读更多...
【JavaWeb】Servlet与过滤器

【JavaWeb】Servlet与过滤器

目录 ServletServlet做了什么JSP与Servlet的关系主要Servlet API介绍如何创建ServletServlet中主要方法ServletRequestServletResponseServletConfig Servlet生命周期Servlet创建Servlet部署与运行 ServletConfig类ServletConfig类的三大作用 ServletContext类ServletContext类…
阅读更多...
Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之八 简单视频素描效果

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之八 简单视频素描效果

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之八 简单视频素描效果 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之八 简单视频素描效果 一、简单介绍 二、简单指定视频某片段快放效果实现原理 三、简单指定视频某…
阅读更多...
web安全学习笔记（9）

web安全学习笔记（9）

记一下第十三课的内容。 准备工作&#xff1a;在根目录下创建template目录&#xff0c;将login.html放入其中&#xff0c;在该目录下新建一个reg.html。在根目录下创建一个function.php 一、函数声明与传参 PHP中的函数定义和其他语言基本上是相同的。我们编辑function.php …
阅读更多...
stm32f103c8t6学习笔记（学习B站up江科大自化协）-看门狗【WDG】

stm32f103c8t6学习笔记（学习B站up江科大自化协）-看门狗【WDG】

硬件部分 一、看门狗简介 看门狗-WDG&#xff08;watchdog&#xff09; 看门狗可以监控程序的运行状态&#xff0c;当程序因为设计漏洞、硬件故障、电磁干扰等原因&#xff0c;出现卡死或跑飞现象时&#xff0c;看门狗能及时复位程序&#xff0c;避免程序陷入长时间的罢工状态…
阅读更多...
相机参数的意义

相机参数的意义

相机标定的意义&#xff1a; 相机标定&#xff1a;使用带有pattern的标定板来求解相机参数的过程&#xff1b;用一个简化的数学模型来代表复杂的三维到二维的成像过程&#xff1b;相机参数包括&#xff1a;相机内参&#xff08;焦距等&#xff09;&#xff0c;外参&#xff08…
阅读更多...
为什么需要SOCKS代理？

为什么需要SOCKS代理？

在数字化时代&#x1f310;&#xff0c;随着网络安全威胁的不断演进和增加&#xff0c;保护个人隐私和数据安全成为了互联网用户的一大挑战&#x1f6e1;️。在寻求增强在线安全和隐私的解决方案时&#xff0c;SOCKS代理成为了一个关键的技术工具&#x1f511;。本文旨在详细探…
阅读更多...
最新文章

Copyright @ 2022~2023