数据结构（初阶）（三）----单链表

单链表

概念

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

结点

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

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

图中指针变量 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;
}

链表的分类

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

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Deepseek 开源周第一天：FlashMLA

Deepseek 开源周第一天：FlashMLA

Deepseek 隆重开启开源周！第一天我们迎来了FlashMLA。我很高兴带大家了解这项创新，揭秘 FlashMLA 为何能成为 AI 和 GPU 优化领域的变革者。 Deepseek 开源周的热门话题有哪些？
阅读更多...
微软具身智能感知交互多面手！Magma：基于基础模型的多模态AI智能体

微软具身智能感知交互多面手！Magma：基于基础模型的多模态AI智能体

作者&#xff1a; Jianwei Yang, Reuben Tan, Qianhui Wu, Ruijie Zheng, Baolin Peng, Yongyuan Liang, Yu Gu, MuCai, SeonghyeonYe, JoelJang, Yuquan Deng, Lars Liden, Jianfeng Gao 单位&#xff1a;微软研究院&#xff0c;马里兰大学&#xff0c;威斯康星大学麦迪逊分校…
阅读更多...
解决Docker Desktop启动后Docker Engine stopped问题

解决Docker Desktop启动后Docker Engine stopped问题

一、问题描述 当我们更新了Docker Desktop后，在重新打开就显示【Docker Engine stopped（Docker引擎已经停止）】，无法正常使用Docker，如下图所示： 二、问题分析 1、检查电脑主板的CPU是否开启虚拟化； 2、需检查Docker所需的功能是否开启； 3、检查WSL是否匹配； Docker的…
阅读更多...
微信小程序：完善购物车功能，购物车主页面展示，详细页面展示效果

微信小程序：完善购物车功能，购物车主页面展示，详细页面展示效果

一、效果图 1、主页面 根据物品信息进行菜单分类&#xff0c;点击单项购物车图标添加至购物车&#xff0c;记录总购物车数量 2、购物车详情页 根据主页面选择的项&#xff0c;根据后台查询展示到页面&#xff0c;可进行多选&#xff0c;数量加减等 二、代码 1、主页面 页…
阅读更多...
微服务学习（2）：实现SpringAMQP对RabbitMQ的消息收发

微服务学习（2）：实现SpringAMQP对RabbitMQ的消息收发

目录 SpringAMQP是什么 为什么采用SpringAMQP SpringAMQP应用 准备springBoot工程 实现消息发送 SpringAMQP是什么 Spring AMQP是Spring框架下用于简化AMQP&#xff08;高级消息队列协议&#xff09;应用开发的一套工具集&#xff0c;主要针对RabbitMQ等消息中间件的集成…
阅读更多...
echarts柱状图不是完全铺满容器，左右两边有空白

echarts柱状图不是完全铺满容器，左右两边有空白

目录 处理前&#xff1a;echarts柱状图不是完全铺满容器&#xff0c;左右两边有空白处理前&#xff1a;通过调整 grid 组件配置处理后效果修改代码&#xff1a;1. 调整 grid 组件配置原理解决办法 2. 处理 xAxis 的 boundaryGap 属性原理解决办法 3. 调整 barMaxWidth 和 barMi…
阅读更多...
【K8S】Kubernetes 基本架构、节点类型及运行流程详解（附架构图及流程图）

【K8S】Kubernetes 基本架构、节点类型及运行流程详解（附架构图及流程图）

Kubernetes 架构 k8s 集群 多个 master node 多个 work nodeMaster 节点&#xff08;主节点&#xff09;&#xff1a;负责集群的管理任务&#xff0c;包括调度容器、维护集群状态、监控集群、管理服务发现等。Worker 节点&#xff08;工作节点&#xff09;&#xff1a;实际运…
阅读更多...
千峰React:案例二

千峰React:案例二

完成对html文档还有css的引入&#xff0c;引入一下数据&#xff1a; import { func } from prop-types import ./购物车样式.css import axios from axios import { useImmer } from use-immer import { useEffect } from reactfunction Item() {return (<li classNameacti…
阅读更多...
C语言【指针篇】（四）

C语言【指针篇】（四）

前言&#xff1a;正文1. 字符指针变量2. 数组指针变量2.1 数组指针变量是什么?2.2 数组指针变量怎么初始化 3. 二维数组传参的本质4. 函数指针变量4.1 函数指针变量的创建4.2 函数指针变量的使用4.3 两段有趣的代码4.3.1 typedef关键字 5. 函数指针数组6. 转移表 总结 前言&am…
阅读更多...
GitCode 助力 python-office：开启 Python 自动化办公新生态

GitCode 助力 python-office：开启 Python 自动化办公新生态

项目仓库&#xff1a;https://gitcode.com/CoderWanFeng1/python-office 源于需求洞察&#xff0c;打造 Python 办公神器 项目作者程序员晚枫在运营拥有 14w 粉丝的 B 站账号 “Python 自动化办公社区” 时&#xff0c;敏锐察觉到非程序员群体对 Python 学习的强烈需求。在数字…
阅读更多...
对话Stack Overflow，OceanBase CTO 杨传辉谈分布式数据库的“前世今生”

对话Stack Overflow，OceanBase CTO 杨传辉谈分布式数据库的“前世今生”

近日&#xff0c; OceanBase CTO 杨传辉受邀出席全球知名开发者论坛 Stack Overflow 的最新一期播客节目&#xff0c;与 Stack Overflow 高级内容创作官 Ryan Donovan 展开对话。双方围绕分布式数据库的可靠性、一致性保障、HTAP 架构以及 AI 时代分布式数据库的发展趋势等热点…
阅读更多...
小结：计算机网路中的性能指标小结

小结：计算机网路中的性能指标小结

发现B站的这套课程不错&#xff0c;开始学习并笔记之&#xff1a;计算机网络微课堂&#xff08;有字幕无背景音乐版&#xff09;_哔哩哔哩_bilibili 1) 速率 2) 带宽 3) 吞吐量 带宽1 Gb/s的以太网&#xff0c;代表其额定速率是1 Gb/s&#xff0c;这个数值也…
阅读更多...
seasms v9 注入漏洞 + order by注入+​information_schema​解决方法

seasms v9 注入漏洞 + order by注入+​information_schema​解决方法

目录 一、当注入时&#xff0c;information_schema被禁用的解决方法 1.通过sys库可以获取到表名和库名 2.通过无列名注入join获取列名 二、seasms v9 注入漏洞 三、order by注入 一、当注入时&#xff0c;information_schema被禁用的解决方法 information_schema数据库是My…
阅读更多...
FFmpeg-chapter2-C++中的线程

FFmpeg-chapter2-C++中的线程

1 常规的线程 一般常规的线程如下所示 // CMakeProject1.cpp: 定义应用程序的入口点。 //#include "CMakeProject1.h" #include <thread> using namespace std;void threadFunction(int index) {for (int i 0; i < 1000; i){std::cout << "Th…
阅读更多...
【华三】从零开始掌握SR技术：原理、架构与应用全解析

【华三】从零开始掌握SR技术：原理、架构与应用全解析

【华三】从零开始掌握SR技术&#xff1a;原理、架构与应用全解析 一、初识SR&#xff1a;路由技术的新革命1.1 传统网络的困扰&#xff1a;从真实案例看技术瓶颈1.1.1 企业网络运维之痛问题2&#xff1a;流量工程实现困难问题3&#xff1a;网络智能化缺失 1.2 SR的诞生意义&…
阅读更多...
CogBlobTool工具

CogBlobTool工具

CogBlobTool是一款专用于图像斑点检测于分析的 工具&#xff0c;通过灰度值阈值分割和特征过滤&#xff0c;帮助在复杂背景中提取目标区域&#xff0c;并计算几何属性。 效果图 注意&#xff1a;在这里只有一张图像可以不使用模板匹配工具 CogBlobTool工具的功能 斑点检测于…
阅读更多...
大模型应用案例 | 大模型+金融运维，擎创携手某证券创新运维能力新范式

大模型应用案例 | 大模型+金融运维，擎创携手某证券创新运维能力新范式

一、当大模型遇上金融运维&#xff1a;一场让告警处理“脱胎换骨”的变革 2022年底&#xff0c;ChatGPT的横空出世让AI技术彻底出圈&#xff1b;短短两年后&#xff0c;大模型已悄然潜入金融行业的“心脏地带”——运维系统。面对指数级暴增的告警信息、碎片化的处理流程&#…
阅读更多...
Linux三种网络方式

Linux三种网络方式

前言 发现运维啥都得会&#xff0c;这周就遇到了网络问题自己无法解决&#xff0c;因此痛定思痛学一下。 参考文献 你管这破玩意叫网络&#xff1f; 桥接模式、NAT模式、仅主机模式&#xff0c;原来是这样工作的 交换机 构成局域网&#xff0c;实现所有设备之间的通信。 …
阅读更多...
基于PHP和MySQL的用户登录注册系统实现

基于PHP和MySQL的用户登录注册系统实现

系统架构 系统采用前后端分离的架构&#xff0c;使用PHP作为后端语言&#xff0c;MySQL作为数据库。以下是系统的整体架构图&#xff1a; 这个架构图展示了系统的三个主要层次&#xff1a; 前端界面层&#xff1a;包含用户交互的三个页面&#xff08;注册、登录和欢迎页面&am…
阅读更多...
脚本无法获取响应主体（原因：CORS Missing Allow Credentials）

脚本无法获取响应主体（原因：CORS Missing Allow Credentials）

背景&#xff1a; 前端的端口号8080&#xff0c;后端8000。需在前端向后端传一个参数&#xff0c;让后端访问数据库去检测此参数是否出现过。涉及跨域请求&#xff0c;一直有这个bug是404文件找不到。 在修改过程当中不小心删除了一段代码&#xff0c;出现了这个bug&#xff0…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023