初阶数据结构【3】--单链表（比顺序表还好的一种数据结构！！！）

本章概述

  • 前情回顾
  • 单链表
  • 实现单链表
  • 彩蛋时刻！！！

前情回顾

咱们在上一章博客点击：《顺序表》的末尾，提出了一个问题，讲出了顺序表的缺点——有点浪费空间。所以，为了解决这个问题，我们今天就要讲解链表，咱们在讲结构体的时候有提到过链表，链表的最大优点——一点空间也不浪费，用多少就开辟多少。在这里插入图片描述

单链表

  • 概念：一种在逻辑上成线性结构，在物理空间上不一定成线性结构的数据结构。因为链表是线性表的一种，所以在逻辑上成线性结构（从“ 链 ”字上就能猜到，在逻辑上成线性结构）。我们链表的开辟用的内存函数是malloc。知识点忘记的同学自行回顾：点击：《动态内存管理》。因为内存开辟是随机的，所以我们也不知道它会在内存的那一块区域开辟空间，这就导致开辟的空间可能是连续的，也可能不是连续的。所以，在物理空间上不一定成线性结构。在这里插入图片描述
  • 节点：每一个个独立，而且还能存放数据的空间被称为节点。数据结构是用来存储数据的，链表自然也是来存储数据的。存储数据就需要有空间，自然有malloc来给我们开辟空间。万事俱备，只欠东风！可是有想过一个问题吗？——malloc开辟的空间东一块，西一块的。它不像realloc那样开辟的连续空间（我们可以挨着挨着找到空间），它的空间是散乱的，不连续的。那么，我们该怎样进行数据的存储，而且还能找到一个一个的数据呢？我们可以在这个节点内部划分两部分，一部分用来存储我们想要存储的数据，另一部分部分用来存储下一个节点的地址（因为我们的节点空间是用nalloc开辟的，所以每个节点自然就有个地址）。这就需要用到结构体了，进行链表的结构展示：
typedef int SLDatatype ;
typedef struct  Sqlist
{
		SLDatatype data;	//存放数据，这里假设存放整型类型
		struct Sqlist* next;   //存放下一个节点的地址
}SLND;		  //定义节点类型

这样我们就能通过地址找到下一个节点了，以此类推，我们就能顺次找到各个节点，找到数据了。如图所示：在这里插入图片描述
当我们不想再存储数据时，要给最后一个节点的next指针赋值NULL（下一个节点为NULL，就相当于没有下一个节点），就表示到此结束了。

  • 链表的性质：
    • 1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续。
    • 2、结点⼀般是从堆上申请的。
    • 3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续。
  • 链表的打印：我们讲过了节点的存储结构了，我们可以通过next指针，找到下一个节点，然后就能打印我们想要的数据了。
  • 直观体验链表：我们先给大家直观感受一下链表，让大家有个感觉，我们就按照上面的结构图进行展示：
#define  _CRT_SECURE_NO_WARNINGS	1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLDatatype;
typedef struct Sqlist
{
	SLDatatype data;
	struct Sqlist* next;
}SLND;

void my_printf(SLND* ps)
{
	assert(ps);
	while (ps)
	{
		printf("%d->", ps->data);
		ps = ps->next;
	}
	printf("NULL");
}
void test()
{
	SLND* plist=NULL;  //创立一个带头指针，用来牵引后面的链表，就像火车头一样
	SLND* node1 = (SLND*)malloc(sizeof(SLND));   //创立3个节点
	SLND* node2 = (SLND*)malloc(sizeof(SLND));
	SLND* node3 = (SLND*)malloc(sizeof(SLND));

	node1->data = 1;  //分别对3个节点·进行·数据的存储
	node2->data = 2;
	node3->data = 3;

	node1->next = node2;  //每个节点的next的指针指向下一个节点的地址
	node2->next = node3;
	node3->next = NULL;

	plist = node1;
	my_printf(plist);
}
int main()
{
	test();
	return 0;
}

结果运行图：在这里插入图片描述
我们的指针plist就是个牵引的作用，就像高铁一样，没有高铁头车厢照样能跑，就是不美观，没有它也可以正常访问链表。有了它就是逻辑上和美观上要舒服很多。如图所示：在这里插入图片描述

实现单链表

和顺序表一样，我们也是创建3个文件: Sqlist .h ， Sqlist.c和test .c文件。具体的原因个顺序表一样的。接下来我直接给大家展示代码，我会在注释中详细讲解的。

  • Sqlist.h:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SListDatatype;
typedef struct SListNode
{
	SListDatatype data;
	struct SListNode* next;
}SLND;

SLND* SListFind(SLND* phead, SListDatatype x);//找对应的节点
SLND* SLTButnode(SListDatatype x);//申请新的节点
void my_printf(SLND* phead); //·打印链表信息

void SListpushback(SLND** pphead, SListDatatype x); //尾插
void SListpopback(SLND** pphead);//尾删

void SListpushFront(SLND** pphead, SListDatatype x); //头插
void SListpopFront(SLND** pphead);//头删

void SListrdFrontpush(SLND** pphead, SLND* find, SListDatatype x);//在任意节点之前插入数据
void SListrdBackpush(SLND* find, SListDatatype x);//在任意节点之后插入数据

void SListposePop(SLND* phead, SLND* pose); //删除指定节点
void SListDestry(SLND** pphead); //销毁链表
  • Sqlist.c:
#include "SList.h"
//打印链表信息
void my_printf(SLND* phead)   //打印信息，便于我们看信息的输出
{
	SLND* pcur = phead;
	while (pcur)
	{
		printf("%d-> ",pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n"); //第N+1个为空====没有链表
}
SLND * SLTButnode(SListDatatype x)	//申请新空间，返回新空间地址，便于咱们找到新空间插入数据
{
	SLND* newnode = (SLND*)malloc(sizeof(SLND));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);		//若开辟失败就直接退出程序，也可以写成 return 1;
	}
	else{
		newnode->data = x;  	//走到这里就开辟成功，进行初始化
		newnode->next = NULL;
	}
		return newnode;
}
void SListpushback(SLND** pphead, SListDatatype x) //尾插数据
{
	assert(pphead);  //检查传递的指针是否为空指针
	SLND* newnode = SLTButnode(x);
	if (*pphead==NULL)  
	{
		*pphead = newnode;	//如果起始没有节点，先创立个节点
	}
	else{
		SLND* ptail = *pphead;
		while (ptail->next)      //遍历节点，找到最后一个节点的next为空的情况，跳出循环
		{
			ptail = ptail->next;  
		}
		ptail->next = newnode;  //走到这里说明找到了最后一个节点，在此之后插入新的节点
	}
}
void SListpopback(SLND** pphead) //尾删数据
{
	assert(pphead&&*pphead);  //检查传递的指针是否为空指针   
	SLND* ptail = *pphead;  //我们把起始节点的地址给ptail，用ptail进行遍历数据，去寻找最后的尾节点
	SLND* prev = NULL;   //prev是用来记录尾节点前一个节点，不记录的话，就会随着我们删除最后一个节点而丢失信息
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	free(ptail);  //找到最后一个节点，进行空间释放
	ptail = NULL;  //释放后要置空，防止产生野指针
}
void SListpushFront(SLND**pphead,SListDatatype x) //头插数据
{
	assert(pphead);  //判断传递的地址是否为空指针
	SLND* newnode = SLTButnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SListpopFront(SLND**pphead)//头删
{
	assert(pphead&&*pphead);	//判断传递的地址是否为空指针
	SLND*next = (*pphead)->next;
	free(*pphead);  //释放头节点
	*pphead = next;  //释放头节点后，要使得plist指向第二个节点
}
SLND* SListFind(SLND*phead,SListDatatype x) //找对应的节点
{
	assert(phead); 	//判断传递的地址是否为空指针
	while (phead)
	{
		if (phead->data == x)
			return phead;    //找到目标节点，就返回目标节点的地址
		phead = phead->next;
	}
	return NULL;  //没找到就返回空指针
}
void SListrdFrontpush(SLND**pphead,SLND*find,SListDatatype x)//在任意节点之前插入数据
{
	assert(pphead&&*pphead);		//判断传递的地址是否为空指针
	if (*pphead == find)    //任意位置刚好是头节点时，相当于头插数据
		SListpushFront(pphead, x); //头插数据
	else {
		SLND*newnode= SLTButnode(x);//申请新的节点
		SLND* prev = NULL;
		SLND* ptail = *pphead;
		while (ptail!= find)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = newnode;  //指定位置之前的节点的next指针指向要插入的新节点
		newnode->next = ptail;		//这个新节点的next指针指向下一个节点
	}
}
void SListrdBackpush( SLND* find, SListDatatype x)//在任意节点之后插入数据
{
	assert(find);		//判断传递的地址是否为空指针
	SLND* newnode = SLTButnode(x);
	newnode->next = find->next;  //新节点的next指针指向下一个节点
	find->next = newnode;		//新节点之前的节点next指针指向这个新节点
}
void SListposePop(SLND**pphead, SLND* pose) //删除指定节点
{
	assert(*pphead&&pose);		//判断传递的地址是否为空指针
	if(pose==*pphead)		//当删除的节点是头节点时，就相当于头删
		SListpopFront(pphead);//头删
	else
	{
		SLND* prev = NULL;	
		SLND* ptail = *pphead;
		while (ptail != pose)		//遍历节点，找到目标节点
		{
			prev = ptail;
			ptail = ptail->next;
		}
		SLND* next = ptail->next;	
		prev->next = next;
		free(ptail);  //删除指定的节点
		ptail = NULL;    //置空指针，防止发生野指针
	}
}

//链表的销毁和顺序表不一样
void SListDestry(SLND**pphead) //链表的销毁不像顺序表那样直接释放内存就欧克，因为每个
{							//节点都是独立的，所以我们需要去遍历每个节点去销毁
	assert(*pphead);		//判断传递的地址是否为空指针
	SLND* prev = NULL;
	SLND* ptail = *pphead;
	while (ptail->next) //一直遍历到最后一个节点才结束
	{
		prev = ptail;
		ptail = ptail->next;
		free(prev); //每遍历一个节点就释放
		prev = NULL;  //置空指针防止产生野指针
	}
	ptail = NULL;		//置空指针防止产生野指针
	*pphead = NULL;	//置空指针防止产生野指针
}
  • test.h
#define  _CRT_SECURE_NO_WARNINGS	1
#include "SList.h"
void test()
{		//这里给大家演示一下尾插数据，其它功能大家可以自行尝试一下
	SLND* plist = NULL;
	SListpushback(&plist,1);//尾插
	SListpushback(&plist,2);//尾插
	SListpushback(&plist,3);//尾插
	SListpushback(&plist,4);//尾插
	my_printf(plist);
}

int main()
{
	test();
	return 0;
}

结果运行图：在这里插入图片描述

彩蛋时刻！！！

歌曲：《All Falls Down》听会儿歌曲放松一下呗！！！
在这里插入图片描述
每章一句：道路是曲折的，前途是光明的！感谢你能看到这里，点赞+关注+收藏+转发是对我最大的鼓励，咱们下期见！！！

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

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

相关文章

Java项目-基于springboot框架的线上买菜系统项目实战(附源码+文档)

Java项目-基于springboot框架的线上买菜系统项目实战(附源码+文档)

作者&#xff1a;计算机学长阿伟 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、ElementUI等&#xff0c;“文末源码”。 开发运行环境 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBoot、Vue、Mybaits Plus、ELementUI工具&#xff1a;IDEA/…
阅读更多...
WebGL编程指南 - 高级变换与动画基础

WebGL编程指南 - 高级变换与动画基础

学习使用一个矩阵变换库&#xff0c;该库封装了矩阵运算的数学细节。快速上手使用该矩阵库&#xff0c;对图形进行复合变换。在该矩阵库的帮助下&#xff0c;实现简单的动画效果。 矩阵变换库&#xff1a;cuon-matrix.js OpenGL中的函数&#xff1a; 书中 cuon-matrix.js 函数…
阅读更多...
go jwt 用户登录和返回用户信息 token ----important!!!

go jwt 用户登录和返回用户信息 token ----important!!!

1.每一行代码都有详细注释&#xff0c;解释了其功能和作用。这些注释可以帮助你理解代码如何工作&#xff0c;特别是在处理用户登录、生成 JWT、验证 JWT 和返回用户信息的过程中。 package main // 指定这个文件是一个可执行程序import ("fmt" …
阅读更多...
SSRF-利用dict协议-攻击redis

SSRF-利用dict协议-攻击redis

1.靶场准备&#xff1a; CTFHub-技能树-Web-SSRF-Redis协议 蚁剑AntSword 2.简述&#xff1a; 2.1 SSRF 服务器端请求伪造&#xff0c;存在一个url参数&#xff0c;一般用于图片上传、网页重定向等&#xff0c;我们可以控制url参数&#xff0c;去访问内网服务器的敏感内容…
阅读更多...
运用AI实践｜如何从AI工具提升工作效率实践

运用AI实践｜如何从AI工具提升工作效率实践

文章目录 引言关于1024这个数值Python 语言获取算法代码Java语言获取算法代码其他语言获取算法代码1024 的用途和功能总结 &#x1f4eb; 作者简介&#xff1a;「六月暴雪飞梨花」&#xff0c;专注于研究Java&#xff0c;就职于科技型公司后端工程师 &#x1f3c6; 近期荣誉&am…
阅读更多...
FPGA学习(6)-基础语法参数化设计阻塞与非阻塞

FPGA学习(6)-基础语法参数化设计阻塞与非阻塞

目录 1.两种参数化不改变源文件&#xff0c;只改仿真文件的值 2.参数化设计实现模块的重用 2.1不用参数化方法 2.1.1源文件 2.1.2仿真文件 2.1.3仿真波形及实验 2.2 用参数方法 2.2.1调用之前写的led灯闪烁模块&#xff0c;在本源函数中&#xff0c;例化4次调用之前的模…
阅读更多...
Nginx15-Lua扩展模块

Nginx15-Lua扩展模块

零、文章目录 Nginx15-Lua扩展模块 1、ngx_lua模块概念 淘宝开发的ngx_lua模块通过将lua解释器集成进Nginx&#xff0c;可以采用lua脚本实现业务逻辑&#xff0c;由于lua的紧凑、快速以及内建协程&#xff0c;所以在保证高并发服务能力的同时极大地降低了业务逻辑实现成本。…
阅读更多...
ECharts饼图-饼图纹理，附视频讲解与代码下载

ECharts饼图-饼图纹理，附视频讲解与代码下载

引言&#xff1a; 在数据可视化的世界里&#xff0c;ECharts凭借其丰富的图表类型和强大的配置能力&#xff0c;成为了众多开发者的首选。今天&#xff0c;我将带大家一起实现一个饼图图表&#xff0c;通过该图表我们可以直观地展示和分析数据。此外&#xff0c;我还将提供详…
阅读更多...
信号（二）【信号的产生】

信号（二）【信号的产生】

目录 1. 键盘组合键2. kill 命令3. 系统调用4. 异常5. 软件条件6. Term 和 Core 的区别 本篇文章介绍五种信号产生的方式&#xff0c;键盘组合键、kill 命令、系统调用、代码异常&#xff08;进程异常&#xff09;、软件条件来产生信号。 1. 键盘组合键 信号&#xff08;一&a…
阅读更多...
商汤科技十周年公布新战略，将无缝集成算力、模型及应用

商汤科技十周年公布新战略，将无缝集成算力、模型及应用

10月18日&#xff0c;恰逢商汤科技十周年庆典&#xff0c;“2024商汤十周年国际论坛&#xff1a;迈向AI 2.0共融新时代”在香港科学园成功举办。 据「TMT星球」了解&#xff0c;来自全球的行业领袖、政府代表、AI专家共聚于此&#xff0c;共同探讨AI行业的未来。 活动上&…
阅读更多...
Linux隐藏权限介绍

Linux隐藏权限介绍

隐藏权限概览 在Linux系统中&#xff0c;有时即便是以root用户身份&#xff0c;你也可能遇到无法修改特定文件的情况。这种限制往往源自chattr命令的应用&#xff0c;该命令用于为文件或目录设置“隐藏权限”&#xff0c;即底层属性&#xff0c;以增强系统安全性。值得注意的是…
阅读更多...
Standard IO

Standard IO

为了提高可移植性&#xff0c;将通用IO接口经过再封装就形成了标准IO&#xff0c;标准IO不仅适用于Unix环境&#xff0c;也兼容非Unix环境&#xff0c;这也是为什么说我们应该尽可能的使用标准IO&#xff0c;通用IO通过文件描述符fd来与文件交互&#xff0c;为了以示区分&#…
阅读更多...
极氪MIX：一台只有你想不到，没有它做不到的“家用神车”

极氪MIX：一台只有你想不到，没有它做不到的“家用神车”

了解极氪品牌的朋友应该都知道 极氪一直都在尝试打破目前汽车或者生活的一些现状 更愿意创造一些破界、超前的产品 比如说将家庭城市通勤、假日露营、自驾旅行、户外垂钓、朋友相聚等多场景融入一个空间的极氪MIX 这款车突破了SUV或MPV车型形态的固有限制 前悬仅 865mm&am…
阅读更多...
【ArcGIS Pro实操第八期】绘制WRF三层嵌套区域

【ArcGIS Pro实操第八期】绘制WRF三层嵌套区域

【ArcGIS Pro实操第八期】绘制WRF三层嵌套区域 数据准备ArcGIS Pro绘制WRF三层嵌套区域Map-绘制三层嵌套区域更改ArcMap地图的默认显示方向指定数据框范围 Map绘制研究区Layout-布局出图 参考 本博客基于ArcGIS Pro绘制WRF三层嵌套区域&#xff0c;具体实现图形参考下图&#x…
阅读更多...
Centos安装Nginx 非Docker

Centos安装Nginx 非Docker

客户的机器属于 Centos7 系列&#xff0c;由于其较为陈旧&#xff0c;2024开始众多镜像和软件源都已失效。此篇文章将详细记录在 Centos7 操作系统上从零开始安装 Nginx 的整个流程。 本文Nginx是安装在/usr/local/nginx下 详细步骤如下&#xff1a; 准备Nginx安装包&#x…
阅读更多...
安防监控摄像头图传模组，1公里WiFi无线传输方案，监控新科技

安防监控摄像头图传模组，1公里WiFi无线传输方案，监控新科技

在数字化浪潮汹涌的今天&#xff0c;安防监控领域也迎来了技术革新的春风。今天&#xff0c;我们就来聊聊这一领域的产品——摄像头图传模组&#xff0c;以及它如何借助飞睿智能1公里WiFi无线传输技术&#xff0c;为安防监控带来未有的便利与高效。 一、安防监控的新篇章 随着…
阅读更多...
程序员适合玩的游戏：《人力资源机器》提升编程思维【Human Resource Machine】

程序员适合玩的游戏：《人力资源机器》提升编程思维【Human Resource Machine】

程序员适合玩的游戏&#xff1a;《人力资源机器》提升编程思维【Human Resource Machine】 在当今这个技术日新月异的时代&#xff0c;编程已经成为一门不可或缺的技能。对于程序员来说&#xff0c;不仅需要扎实的专业知识&#xff0c;还需要不断锻炼逻辑思维和解决问题的能力…
阅读更多...
用.NET开发跨平台应用程序采用 Avalonia 与MAUI如何选择

用.NET开发跨平台应用程序采用 Avalonia 与MAUI如何选择

Avalonia是一个强大的框架&#xff0c;使开发人员能够使用.NET创建跨平台应用程序。它使用自己的渲染引擎绘制UI控件&#xff0c;确保在Windows、macOS、Linux、Android、iOS和WebAssembly等不同平台上具有一致的外观和行为。这意味着开发人员可以共享他们的UI代码&#xff0c;…
阅读更多...
RNN、LSTM 与 Bi-LSTM

RNN、LSTM 与 Bi-LSTM

一. RNN 循环神经网络&#xff08;Recurrent Neural Network, RNN&#xff09;是深度学习领域一类具有内部自连接的神经网络能够学习复杂的矢量到矢量的映射。 最大特点&#xff1a;前面的序列数据可以用作后面的结果预测中。 一个简单的循环神经网络结构&#xff0c;其结构包…
阅读更多...
如何写一个视频编码器演示篇

如何写一个视频编码器演示篇

先前写过《视频编码原理简介》&#xff0c;有朋友问光代码和文字不太真切&#xff0c;能否补充几张图片&#xff0c;今天我们演示一下&#xff1a; 这是第一帧画面&#xff1a;P1&#xff08;我们的参考帧&#xff09; 这是第二帧画面&#xff1a;P2&#xff08;需要编码的帧&…
阅读更多...
最新文章

Copyright @ 2022~2023