链表之单链表

上一篇博客我们学习了线性表中的顺序表,这一篇博客让我们继续往下了解线性表的链表,链表分为好几种结构,活不多说,让我们开始学习吧!


目录

1.链表

2.链表的结构

3.单链表的实现


1.链表

1.概念:它是一种物理存储结构上非连续非顺序的存储结构,数据元素的逻辑顺序是通过链                表中的指针链接次序实现的。它在空间上,按需给空间,不要求物理空间的连续,                和顺序表不同,它头部和中间的数据的插入就不需要挪动数据。链表的实现是通过                指针的。

2.有些老铁可能不明白什么是物理结构,它就是在内存中实实在在的存储形式。

什么是不连续非顺序,我们画图来给大家解释一下:

在这些节点中间,我们可以插入新的节点,又是新的地址,所以说它不是按顺序走的。这些节点在内存中,可能这有一个节点,也可能那有一个节点,但它们彼此之间通过指针相连接,只要指针不断,就可以找到下一个节点。

3.链表只能一个一个诶个访问,只能从头找,因为一旦它找到下一个节点,它就不知道上一个节点的位置了(双向链表可以找到上一个,我们到了那个章节在继续学习)。这时,又显示出顺序表的好处了,因为它可以直接定位到要查找数据的位置,但是它会造成空间的浪费,所以说有好有坏,需要大家自己体会。

2.链表的结构

链表分为八种结构,在这里先给大家一个总体的框架,方便接下来的学习:

单链表,双链表,不带头链表,带头链表,循环链表,不循环链表,这六种链表构成了链表的八种结构,分别是:

1.单向不带头不循环链表

2.单向不带头循环链表

3.单向带头不循环链表

4.单向带头循环链表

5.双向不带头不循环链表

6.双向不带头循环链表

7.双向带头不循环链表

8.双向带头循环链表

我们今天在这里会实现第一种结构,单向不带头不循环链表,相信通过这个链表的实现,大家可以把2,3,4种结构都实现。

3.单链表的实现

现在我们来实现这个单链表,可以类比顺序表写,这一部分的代码都大差不差,具体要看怎么实现。

SList.h文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int ALTDataType;

//创建结构体,用来创建链表组成元素
typedef struct SListNode
{
	ALTDataType data;//链表数据
	struct SListNode* next;//链表指向下一个元素的指针,指向下一个节点的位置
}SLN;

//开辟空间来存入数据
SLN* BuySListNode(ALTDataType x);
//打印链表
void SListPrint(SLN* phead);
//头插
void sListPushFront(SLN** pphead, ALTDataType x);
//尾插
void sListPushBack(SLN** pphead, ALTDataType x);
//头删
void sListPopFront(SLN** pphead);
//尾删
void sListPopBack(SLN** pphead);
//查找链表
SLN* sListFind(SLN* phead, ALTDataType x);
//修改对应链表位置的数据
void sListModify(SLN* phead, SLN* pos, ALTDataType x, ALTDataType y);
//任意位置的插入,在pos位置的前一个位置插入
void sListInsert(SLN** pphead, SLN* pos, ALTDataType x);
//任意位置的删除
void sListErase(SLN** pphead, SLN* pos);
//销毁链表
void destorySList(SLN* phead);

SList.c文件

#include"SList.h"

//开辟空间来存入数据
SLN* BuySListNode(ALTDataType x)
{
	SLN* newnode = (SLN*)malloc(sizeof(SLN));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//打印链表
void SListPrint(SLN* phead)
{
	assert(phead);
	SLN* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

//头插
//想要头插,我们要把新节点的地址给到头节点,再把新节点定义为新的头节点
void sListPushFront(SLN** pphead, ALTDataType x)
{
	SLN* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾插
void sListPushBack(SLN** pphead, ALTDataType x)
{
	SLN* newnode = BuySListNode(x);
	//若一开始链表为空,我们直接插入一个新节点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//我们要创建一个变量,找到链表的尾端,从尾端插入
	SLN* tail = *pphead;
	while (tail->next)
	{
		tail = tail->next;
	}
	tail->next = newnode;//尾节点链接新节点
}

//头删
void sListPopFront(SLN** pphead)
{
	assert(*pphead);
	SLN* next = (*pphead)->next;//*小于->的优先级,编译器不通过
	free(*pphead);
	*pphead = NULL;
	*pphead = next;
}
//尾删
void sListPopBack(SLN** pphead)
{
	assert(*pphead);
	//当只有一个节点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLN* tail = *pphead;
	SLN* prev = NULL;
	while (tail->next)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	tail = NULL;
	prev->next = NULL;
}
//查找链表
SLN* sListFind(SLN* phead, ALTDataType x)
{
	assert(phead);
	SLN* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//修改对应链表位置的数据
void sListModify(SLN* phead, SLN* pos, ALTDataType x, ALTDataType y)
{
	pos = sListFind(phead, x);
	pos->data = y;
}
//任意位置的插入,在pos位置的前一个位置插入
void sListInsert(SLN** pphead, SLN* pos, ALTDataType x)
{
	if (pos == *pphead)
	{
		sListPushFront(pphead, x);
		return;
	}
	SLN* newnode = BuySListNode(x);
	SLN* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
}
//任意位置的删除,删除pos位置的值
void sListErase(SLN** pphead, SLN* pos)
{
	if (pos == *pphead)
	{
		sListPopFront(pphead);
		return;
	}
	SLN* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//销毁链表,这些空间,我们要一个一个释放,防止内存泄漏
void destorySList(SLN* phead)
{
	assert(phead);
	SLN* tail = phead->next;
	while (tail)
	{
		SLN* next = tail->next;
		free(tail);
		tail = NULL;
		tail = next;
	}
	free(phead);
	phead = NULL;
}

test.c文件

#include"SList.h"


void Test1()
{
	SLN* plist = NULL;
	SLN* pos = NULL;
	sListPushFront(&plist, 4);
	sListPushFront(&plist, 3);
	sListPushFront(&plist, 2);
	sListPushFront(&plist, 1);
	SListPrint(plist);

	sListPushBack(&plist, 5);
	sListPushBack(&plist, 6);
	sListPushBack(&plist, 7);
	sListPushBack(&plist, 8);
	SListPrint(plist);

	sListPopFront(&plist);
	sListPopFront(&plist);
	SListPrint(plist);

	sListPopBack(&plist);
	sListPopBack(&plist);
	SListPrint(plist);

	pos = sListFind(plist, 5);
	if (pos == NULL)
	{
		printf("找不到该数据\n");
	}
	else
	{
		printf("已找到该数据,现在进行修改\n");
		sListModify(plist, pos, 5, 50);
	}
	SListPrint(plist);

	pos = sListFind(plist, 50);
	if (pos == NULL)
	{
		printf("找不到该数据\n");
	}
	else
	{
		printf("已找到该数据,现在进行在pos前插入数据\n");
		sListInsert(&plist, pos, 20);
	}
	SListPrint(plist);

	pos = sListFind(plist, 20);
	if (pos == NULL)
	{
		printf("找不到该数据\n");
	}
	else
	{
		printf("已找到该数据,现在进行对pos位置数据的删除\n");
		sListErase(&plist, pos);
	}
	SListPrint(plist);

	destorySList(plist);
	printf("链表已销毁\n");
}
int main()
{
	Test1();
	return 0;
}

结果:大家下去还是要自己敲一遍代码,才能做到掌握


好了,今天的内容就是这些,我们下期再见铁汁们!

感谢品读!!!

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

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

相关文章

【QT入门】 自定义标题栏界面qss美化+按钮功能实现

往期回顾&#xff1a; 【QT入门】 鼠标按下和移动事件实现无边框窗口拖动-CSDN博客【QT入门】 设计实现无边框窗口拉伸的公用类-CSDN博客【QT入门】对无边框窗口自定义标题栏并实现拖动和拉伸效果-CSDN博客 【QT入门】 自定义标题栏界面qss美化按钮功能实现 一、最终效果 二、…

Linux简单介绍

Linux简单介绍 编译器VMware虚拟机Ubuntu——LinuxOS为什么使用LinuxOS&#xff1f; 目录结构Windows目录结构Linux操作系统home是不是家目录&#xff1f; Linux常用命令终端命令行提示符与权限切换命令tab 作用&#xff1a;自动补全上下箭头pwd命令ls命令mkdir命令touch命令rm…

Vue 大文件切片上传实现指南包会,含【并发上传切片,断点续传,服务器合并切片,计算文件MD5,上传进度显示,秒传】等功能

Vue 大文件切片上传实现指南 背景 在Web开发中&#xff0c;文件上传是一个常见的功能需求&#xff0c;尤其是当涉及到大文件上传时&#xff0c;为了提高上传的稳定性和效率&#xff0c;文件切片上传技术便显得尤为重要。通过将大文件切分成多个小块&#xff08;切片&#xff0…

小程序滑动删除组件+全选批量删除组件+附源码

小程序滑动删除组件全选批量删除组件附源码 说明 使用 uni-app、uview 组件开发&#xff0c;全端&#xff08;微信小程序、QQ小程序、抖音小程序等等&#xff09; 支持滑动删除组件、支持左滑删除、长按进入批量删除、全选删除、长按弹窗删除、 组件式开发&#xff0c;文章…

LabVIEW太赫兹波扫描成像系统

LabVIEW太赫兹波扫描成像系统 随着科技的不断发展&#xff0c;太赫兹波成像技术因其非电离性、高穿透性和高分辨率等特点&#xff0c;在生物医学、材料质量无损检测以及公共安全等领域得到了广泛的应用。然而&#xff0c;在实际操作中&#xff0c;封闭性较高的信号采集软件限制…

Leetcode 674. 最长连续递增序列

心路历程&#xff1a; 这道题和递增子序列的一样&#xff0c;由于题目中要求连续&#xff0c;实际上会让状态转移更加简单&#xff0c;因为候选的动作集合相当于更小了。 状态&#xff1a;nums的区间[0, i]&#xff0c;第i个元素和第i-1个元素的大小关系 动作&#xff1a;是否…

Vue3_2024_7天【回顾上篇watch常见的后两种场景】___续

Vue3中监听多条数据的两种使用 1.watch【使用上一章写法&#xff0c;监听两个属性&#xff0c;然后执行相应操作…】 2.watchEffect【相对于使用watch&#xff0c;watchEffect默认页面初始加载&#xff0c;有点类似加配置&#xff1a;立即执行 immediate】 代码&#xff1a; …

无熟人难办事?--迪米特法则

1.1 第一天上班 第一天上班&#xff0c;电脑安装工作但是安装的同事小张刚巧有事要忙&#xff0c;主管有事也出去了&#xff0c;没有人搭理。小张快下班的时候才回来&#xff0c;开始帮我装系统&#xff0c;加域&#xff0c;设置密码等。 1.2 无熟人难办事 管理上出了问题&a…

文献阅读:将条形码神经解剖学与空间转录分析相结合,可以识别投射神经元相关基因

文献介绍 「文献题目」 Integrating barcoded neuroanatomy with spatial transcriptional profiling enables identification of gene correlates of projections 「研究团队」 Anthony M. Zador&#xff08;美国冷泉港实验室&#xff09; 「发表时间」 2021-05-10 「发表期…

Rust---复合数据类型之枚举、数组

目录 枚举的使用Option 枚举数组的使用输出结果 枚举&#xff08;Enum&#xff09;&#xff1a;表示一个类型可以有多个不同的取值。枚举类型可以包含不同的变体&#xff08;variants&#xff09;&#xff0c;每个变体可以有不同的数据类型。 枚举的使用 enum Direction {Up,…

[QOpenGLWidget+QMouseEvent]实时绘制长方形

复现moho-打卡第1天 - 20240402 1.1--QOpenGLWidget中显示长方形 实现方法&#xff1a;顶点着色器中给定长方形的四个顶点数据&#xff0c;代码如下&#xff1a; // 顶点位置 GLfloat vertics[1][4][3] { {{mousePressPosX,mousePressPosY,0.0},{mousePressPosX,mouseMoveP…

hexo博客7:构建简单的多层安全防御体系

【hexo博客7】构建简单的多层安全防御体系 写在最前面理解全面安全策略的重要性防御常见的网络攻击1. SQL注入攻击2. 文件上传漏洞3. 跨站脚本攻击&#xff08;XSS&#xff09;4. 跨站请求伪造&#xff08;CSRF&#xff09;5. 目录遍历/本地文件包含&#xff08;LFI/RFI&#x…

CAN的协议层

CAN属于异步通讯&#xff0c;没有时钟信号线&#xff0c;连接在同一个总线网络中的各个节点会像串口异步通讯那样&#xff0c;节点间使用约定好的波特率进行通信&#xff0c;特别的&#xff0c;CAN还会使用“位同步”的方式来抗干扰&#xff0c;吸收误差&#xff0c;实现对总线…

Docker实战教程 第2章 Docker基础

3-1 Docker介绍 什么是Docker 虚拟化&#xff0c;容器 Docker 是一个开源的应用容器引擎&#xff0c;基于 Go 语言 并遵从Apache2.0协议开源。 Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后发布到任何流行的 Linux 机器上&…

【活动预告】SLMOps 系列(三)|SLMOps 的最后一公里 - 模型评估技巧

点击蓝字 关注我们 编辑&#xff1a;Alan Wang 排版&#xff1a;Rani Sun 2023年&#xff0c;Azure OpenAI Service 引领了 AI 2.0 时代的热潮&#xff0c;各行业企业都在 AI 模型的探索与应用中持续发力。相比复杂度更高的大模型&#xff0c;有时候轻量且高效的小模型&#xf…

【windows自带exe】使用`findstr.exe`来搜索包含某个字符串的文件

【windows自带exe】使用findstr.exe来搜索包含某个字符串的文件 写在最前面什么是findstr.exe?如何使用findstr.exe查找文件中的字符串&#xff1f;示例&#xff1a;查找JSP文件中包含"jsonp"的文件 注意事项小结 &#x1f308;你好呀&#xff01;我是 是Yu欸 &…

基于Python的简单颜色替换

当我们临时需要改变一个照片的颜色&#xff0c;使其符合我们想要的主题色时&#xff0c;对于不会PS的我就只能使用一下Python来实现这个简单的过程 比如我想要中国农大农学院的院徽&#xff0c;但在官网上提取出来的图片是白色的 而我想要符合农学主题的绿色&#xff0c;将图片…

go juc 线程中的子类

1.go test() 主死随从 package mainimport ("fmt""strconv""time" )func test() {for i : 1; i < 10; i {fmt.Println("hello " strconv.Itoa(i))//阻塞time.Sleep(time.Second)} } func main() {//开启协程go test()for i : 1; …

使用pip安装geopandas(24.4更新)

geopandas是我们用Python进行地理分析常用的库&#xff0c;在数据处理、分析、制图等场景中有着极为广泛的应用&#xff0c;但是在安装过程中会出现各种问题。​geopandas的安装方式有很多&#xff0c;今天我们选取较为简单的pip来进行geopandas的安装。 ​首先&#xff0c;我…

Java多态世界(day18)

多态&#xff1a;重写的方法调用和执行 1.静态绑定&#xff1a;编译器在父类中找方法&#xff0c;如&#xff1a; 上面的eat&#xff08;&#xff09;方法是先在父类中找方法&#xff0c;父类没有的话&#xff0c;就算子类有编译也会报错。&#xff08;如果引用方法在父类中存…