当前位置: 首页 > news >正文

数据结构(初阶)(三)----单链表

单链表

概念

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

结点

与顺序表不同的是,链表的结构类似于带车头的火车车厢,,链表的每个车厢都是独立申请下来的空间,每个车厢被叫做结点。

结点由当前结点要保存的数据保存下一个节点的地址(指针变量)。

图中指针变量 plist保存的是第⼀个结点的地址,我们称plist此时“指向”第⼀个结点,如果我们希望plist“指向”第⼆个结点时,只需要修改plist保存的内容为0x0012FFc8

链表中每个结点都是独⽴申请的(即需要插⼊数据时才去申请⼀块结点的空间),我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点

在这里插入图片描述

在这里插入图片描述

链表的性质

链表在逻辑上是连续的,在物理结构上不一定连续

结点一般是从堆上申请的

从堆上申请来的空间,是按照⼀定策略分配出来的,每次申请的空间可能连续,可能不连续

定义链表的结构实际上就是定义链表中结点结构

每个结点对应的结构体代码:

typedef int SLTDataType;//因为我们在事先并不确定数据的类型,所以需要定义一下
typedef truct SListNode
{SLTDataType data;//结点要保存的数据struct SListNode* next;//指向下一个结点的指针,定义的数据类型是结点类型
}SLTNode;//定义全局变量

当我们想要保存一个数据时,实际上是向操作系统申请一块内存,这块内存不仅要保存数据,也要保存指向下一个结点的地址(当下一个结点为NULL时,地址为NULL)

当我们想要从第一个节点走向最后一个结点时,只需要在当前结点拿上下⼀个结点的地址就可以了。

链表的打印

void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;//pcur存储的是当前的结点while (pcur)//等价于pcur != NULL{printf("%d-> ",pcur->data);pcur = pcur->next;}//走到这里,说明pcur == NULL,那么直接打印printf("NULL\n");
}

单链表的实现

创建三个文件分别是SList.h和SList.c和test.c

SList.h用来包含所需头文件,声明函数

SList.c用来定义函数,实现方法

test.c用来测试我们想要实现的功能

这里使用的是VS2022 win11环境

手动构造链表

SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>typedef int SLTDataType;//定义数据类型
typedef struct SListNode
{SLTDataType data;//定义下一个结点的地址,类型是struct SListNodestruct SListNode* next;
}SLTNode;//定义全局变量//打印链表
void SListPrint(SLTNode* phead);
SList.c
#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"//打印链表
void SListPrint(SLTNode* phead)
{//创建pcur存储phead的地址,直接用phead也可以//这里是因为再次使用第一个结点时,还可以找到,不会影响后续的使用SLTNode* pcur = phead;//判断当前结点是否为NULL,等价于pcur != NULLwhile (pcur){//结点不为NULL,打印当前节点数据printf("%d -> ",pcur->data);//将下一个结点的地址赋值给pcurpcur = pcur->next;}//走到这里说明pcur == NULL,直接打印NULLprintf("NULL\n");
}
test.c
#define _CRT_SECURE_NO_WARNINGS
#include"SList.h"//手动构造链表
void test1()
{//为结点申请内存,大小为结构体大小//node1来接收,类型为SLTNode*,其他同理SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));//在结点中放入要存储的数据node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;//在结点中放入指向下一个结点的地址,如果是尾结点,则为NULLnode1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//打印链表看看效果//将首结点的地址给plist,传给实现打印的函数SLTNode* plist = node1;SListPrint(plist);
}int main()
{test1();return 0;
}

单链表实现

尾插

//向操作系统申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}//成功newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
//其实在链表为NULL的情况下,不需要再改变头结点的内容,所以也可以使用SLTNode* pphead
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//向操作系统申请一个新结点SLTNode* newnode = SLTBuyNode(x);//链表为空,phead直接指向newNodeif (*pphead == NULL){*pphead = newnode;}//链表不为空,找尾节点,将尾节点和新节点连接起来else{SLTNode* ptail = *pphead;while (ptail->next != NULL){ptail = ptail->next;}//此时有:ptail->next == NULLptail->next = newnode;}
}

尾删

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

普遍情况是有多个结点,思路是:

1,找到尾结点

2,将尾结点的前驱结点置为空,再将尾结点释放并置空

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

特殊情况是,只有一个结点,思路是:

将唯一一个结点,也就是头结点释放并置空

//尾删
void SLTPopBack(SLTNode** phead)
{//二级指针不为空,链表不为空assert(phead && *phead);//在只有一个结点的情况下,prev = NULL,所以在下面对空指针的操作就是不合法的,//所以此时要分离出来,特殊处理,之后我们再测试assert断言就发挥了作用//注意*的优先级是低于->的,所以需要加上括号if ((*phead)->next == NULL){free(*phead);*phead = NULL;}//此时是结点个数大于一的情况else {SLTNode* prev = NULL;SLTNode* ptail = *phead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}

头插

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

头删

头删时,只需要将头结点的next结点保存起来,然后将原来的头结点释放,最后将next结点变成新的头结点即可。

//头删
void SLTPopFront(SLTNode** phead)
{assert(phead && *phead);//经过分析,在只有一个结点和多个结点的情况时,都是符合预期的,所以不必分离讨论SLTNode* next = (*phead)->next;free(*phead);*phead = next;}

查找

如果只是在链表中查找数据,那么就不会修改,只需传一级指针和要查找的数据,

而返回值则是所查找到的结点

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{//创建pcur来遍历链表SLTNode* pcur = phead;//当结点不为空,进入循环while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

指定位置pos之前插入

既然是插入数据,那么就要对链表进行修改,需要传址调用,要传二级指针,结点pos,和数据x

//指定位置pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);//如果pos的位置就是头结点,那么就相当于头插if (pos == *pphead){//头插SLTPushFront(pphead, x);}else{//创建新结点SLTNode* newnode = SLTBuyNode(x);//创建prev记录pos的前驱结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//此时找到了posnewnode->next = pos;prev->next = newnode;}
}

指定位置之后pos插入

//指定位置之后pos插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//在pos之后插入,就不需要知道头结点SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

指定位置删除

//指定位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);if (pos == *pphead){//头删SLTPopFront(pphead);}else {SLTNode* del = *pphead;while (del->next != pos){del = del->next;}del->next = pos->next;free(pos);pos == NULL;}	
}

指定位置之后删除

//指定位置之后删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* del = pos->next;pos->next = del->next;
}

销毁链表

//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

链表的分类

在这里插入图片描述
在这里插入图片描述

相关文章:

数据结构(初阶)(三)----单链表

单链表 概念 概念&#xff1a;链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构&#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 结点 与顺序表不同的是&#xff0c;链表的结构类似于带车头的火车车厢&#xff0c;&#xff0c;链表的每个车厢都是独立…...

ChatGPT与DeepSeek:AI语言模型的巅峰对决

目录 引言 一、ChatGPT 与 DeepSeek 简介 &#xff08;一&#xff09;ChatGPT &#xff08;二&#xff09;DeepSeek 二、技术原理剖析 &#xff08;一&#xff09;ChatGPT 技术原理 &#xff08;二&#xff09;DeepSeek 技术原理 &#xff08;三&#xff09;技术原理对比…...

DaoCloud 亮相 2025 GDC丨开源赋能 AI 更多可能

2025 年 2 月 21 日至 23 日&#xff0c;上海徐汇西岸&#xff0c;2025 全球开发者先锋大会以 “模塑全球&#xff0c;无限可能” 的主题&#xff0c;围绕云计算、机器人、元宇宙等多元领域&#xff0c;探讨前沿技术创新、应用场景拓展和产业生态赋能&#xff0c;各类专业论坛、…...

人工智能之数学基础:线性代数中矩阵的运算

本文重点 矩阵的运算在解决线性方程组、描述线性变换等方面发挥着至关重要的作用。通过对矩阵进行各种运算,可以简化问题、揭示问题的本质特征。在实际应用中,我们可以利用矩阵运算来处理图像变换、数据分析、电路网络等问题。深入理解和掌握矩阵的运算,对于学习线性代数以…...

(上)基于机器学习的图像识别——遥感图像分类(LeNet-5;AlexNet;VGGNet;GoogLeNet;ResNet)

遥感图像识别&#xff1a; 专业词汇&#xff1a; kernel&#xff1a;卷积 目录 遥感图像分类 1.1 LeNet-5 视频来源&#xff1a; 任务&#xff1a;使用什么网络实现遥感图像的分类 LeNet-5结构&#xff1a; 遥感图像分类 1.2 AlexNet&#xff08;冠军&#xff09; 视频…...

数据集笔记:NUSMods API

1 介绍 NUSMods API 包含用于渲染 NUSMods 的数据。这些数据包括新加坡国立大学&#xff08;NUS&#xff09;提供的课程以及课程表的信息&#xff0c;还包括上课地点的详细信息。 可以使用并实验这些数据&#xff0c;它们是从教务处提供的官方 API 中提取的。 该 API 由静态的…...

HTML元素,标签到底指的哪块部分?单双标签何时使用?

1. 标签&#xff08;Tag&#xff09; vs 元素&#xff08;Element&#xff09; 标签&#xff08;Tag&#xff09; 标签是 HTML 中用于定义元素的符号&#xff0c;用尖括号 < > 包裹。例如 <img> 是标签。元素&#xff08;Element&#xff09; 元素是由 标签 内容…...

基于ai技术的视频生成工具

一、通用型AI视频生成工具 腾讯智影 特点&#xff1a;支持数字人播报、文字转视频&#xff0c;提供免费模板和素材库&#xff0c;登录即送5分钟免费时长&#xff0c;每日签到可兑换额外额度。 限制&#xff1a;免费版分辨率较低&#xff0c;部分高级功能需付费。 LunaAI.vid…...

【Java 后端】Restful API 接口

Restful API 接口 REST&#xff1a;Representational State Transfer&#xff0c;表现层&#xff08;前端的视图页面和后端的控制层&#xff09;资源状态转移。 一种软件架构的风格&#xff08;格式&#xff09; RESTful 是目前最流行的互联网软件架构&#xff0c;如果一个架…...

Matlab地图绘制教程第2期—水陆填充图

上一期分享了海岸线图的绘制方法&#xff1a; 本着由浅入深的理念&#xff0c;本期再来分享一下水陆填充图的绘制方法。 先来看一下成品效果&#xff1a; 特别提示&#xff1a;Matlab地图绘制教程系列&#xff0c;旨在降低大家使用Matlab进行地图类科研绘图的门槛&#xff0c;…...

企业知识库搭建:14款开源与免费系统选择

本文介绍了以下14 款知识库管理系统&#xff1a;1.Worktile&#xff1b;2.PingCode&#xff1b;3.石墨文档&#xff1b; 4. 语雀&#xff1b; 5. 有道云笔记&#xff1b; 6. Bitrix24&#xff1b; 7. Logseq等。 在如今的数字化时代&#xff0c;企业和团队面临着越来越多的信息…...

【Linux系统】—— 冯诺依曼体系结构与操作系统初理解

【Linux系统】—— 冯诺依曼体系结构与操作系统初理解 1 冯诺依曼体系结构1.1 基本概念理解1.2 CPU只和内存打交道1.3 为什么冯诺依曼是这种结构1.4 理解数据流动 2 操作系统2.1 什么是操作系统2.2 设计OS的目的2.3 操作系统小知识点2.4 如何理解"管理"2.5 系统调用和…...

Android内存优化指南:从数据结构到5R法则的全面策略

目录 一、APP 内存限制 二、内存的三大问题 2.1、内存抖动(Memory Churn) 2.1.1 频繁创建短生命周期对象 2.1.2 系统API或第三方库的不合理使用 2.1.3 Handler使用不当 2.2、内存泄漏(Memory Leak) 2.2.1 静态变量持有Activity或Context引用 2.2.2 未取消的回调或…...

机器学习:线性回归,梯度下降,多元线性回归

线性回归模型 (Linear Regression Model) 梯度下降算法 (Gradient Descent Algorithm) 的数学公式 多元线性回归&#xff08;Multiple Linear Regression&#xff09;...

Linux上用C++和GCC开发程序实现两个不同MySQL实例下单个Schema稳定高效的数据迁移到其它MySQL实例

设计一个在Linux上运行的GCC C程序&#xff0c;同时连接三个不同的MySQL实例&#xff0c;其中两个实例中分别有两个Schema的表结构分别与第三实例中两个Schema个结构完全相同&#xff0c;同时复制两个实例中两个Schema里的所有表的数据到第三个实例中两个Schema里&#xff0c;使…...

RabbitMQ系列(一)架构解析

RabbitMQ 架构解析 RabbitMQ 是一个基于 AMQP 协议的开源消息中间件&#xff0c;其核心架构通过多组件协作实现高效、可靠的消息传递。以下是其核心组件与协作流程的详细说明&#xff1a; 一、核心组件与功能 Broker&#xff08;消息代理服务器&#xff09; RabbitMQ 服务端核…...

XSL 语言:XML 样式表的语言基础与应用

XSL 语言:XML 样式表的语言基础与应用 引言 XSL(Extensible Stylesheet Language)是一种专门用于XML文档样式的语言,它允许用户定义XML文档的格式、布局和外观。XSL是XML技术家族中的重要组成部分,与XML和XPATH等语言共同构成了处理和格式化XML文档的强大工具集。本文将…...

【计算机网络】常见tcp/udp对应的应用层协议,端口

TCP 和 UDP 对应的常见应用层协议 &#x1f4cc; 基于 TCP 的应用层协议 协议全称用途默认端口HTTPHyperText Transfer Protocol超文本传输协议80HTTPSHTTP Secure加密的超文本传输协议443FTPFile Transfer Protocol文件传输协议&#xff08;20 传输数据&#xff0c;21 控制连…...

ExpMoveFreeHandles函数分析和备用空闲表的关系

第一部分&#xff1a;ExpMoveFreeHandles和备用空闲表的关系 ULONG ExpMoveFreeHandles ( IN PHANDLE_TABLE HandleTable ) { ULONG OldValue, NewValue; ULONG Index, OldIndex, NewIndex, FreeSize; PHANDLE_TABLE_ENTRY Entry, FirstEntry; EXHAND…...

微服务学习(1):RabbitMQ的安装与简单应用

目录 RabbitMQ是什么 为什么要使用RabbitMQ RabbitMQ的安装 RabbitMQ架构及其对应概念 队列的主要作用 交换机的主要作用 RabbitMQ的应用 通过控制面板操作&#xff08;实现收发消息&#xff09; RabbitMQ是什么 RabbitMQ是一个开源的消息队列软件&#xff08;消息代理…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...