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

news/2025/3/3 9:31:24/

单链表

概念

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

结点

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

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

图中指针变量 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.ppmy.cn/news/1576257.html

相关文章

# 【Unity】【游戏开发】赛车游戏中碰撞加速的实现方法

# 【Unity】【游戏开发】赛车游戏中碰撞加速的实现方法

背景 在赛车类游戏开发中，常常需要实现赛车在碰撞某些道具或对象后加速的功能。例如，当赛车经过加速带或碰撞加速道具时，速度会瞬间增加，使游戏更具动态性和可玩性。本文将介绍一种通用的实现方式，并分析其逻辑。 分析 加速的核心逻辑如下： 判断碰撞条件：检测赛车是否…
阅读更多...
Redis常见面试题大白话简答，关于认识Redis及其数据结构、线程模型和持久化

Redis常见面试题大白话简答，关于认识Redis及其数据结构、线程模型和持久化

前言 备战面试刷Redis面试题&#xff0c;觉得不能光看还得有输出&#xff0c;于是写文用大白话来回答面试题。 本文仅包括小林coding中Redis面试篇中关于认识Redis、Redis的数据结构、Redis线程模型和Redis持久化部分 写文果然是有助于理解的方式&#xff0c;感觉在倒逼自己…
阅读更多...
DockerでOracle Database 23ai FreeをセットアップしMAX_STRING_SIZEを拡張する手順

DockerでOracle Database 23ai FreeをセットアップしMAX_STRING_SIZEを拡張する手順

DockerでOracle Database 23ai FreeをセットアップしMAX_STRING_SIZEを拡張する手順 はじめに環境準備ディレクトリ作成Dockerコンテナ起動 データベース設定変更コンテナ内でSQL*Plus起動PDB操作と文字列サイズ拡張設定検証 管理者ユーザー作成注意事項まとめ 中文版请访问这里…
阅读更多...
1.2.3 使用Spring Initializr方式构建Spring Boot项目

1.2.3 使用Spring Initializr方式构建Spring Boot项目

本实战概述介绍了如何使用Spring Initializr创建Spring Boot项目&#xff0c;并进行基本配置。首先&#xff0c;通过Spring Initializr生成项目骨架&#xff0c;然后创建控制器HelloController&#xff0c;定义处理GET请求的方法hello&#xff0c;返回HTML字符串。接着&#xf…
阅读更多...
MATLAB分析与仿真白噪声

MATLAB分析与仿真白噪声

白噪声&#xff1a;使用 Matlab 进行仿真与分析 定义 一个具有恒定功率谱密度&#xff08;PSD&#xff09;函数的随机过程&#xff08;或信号&#xff09;被称为白噪声过程。 功率谱密度 功率谱密度函数&#xff08;PSD&#xff09;显示了每个频谱分量中包含的功率。例如&a…
阅读更多...
All in One: Multi-Task Prompting for Graph Neural Networks学习笔记

All in One: Multi-Task Prompting for Graph Neural Networks学习笔记

简介 主要研究了图神经网络&#xff08;GNN&#xff09;中多任务提示&#xff08;multi-task prompting&#xff09;的方法。文中讨论了传统的GNN“预训练与微调”方法和下游任务割裂&#xff0c;特别是在节点级&#xff08;node-level&#xff09;、边级&#xff08;edge-lev…
阅读更多...
大模型系列——专家混合模型 (MoE)快速指南

大模型系列——专家混合模型 (MoE)快速指南

大模型系列——专家混合模型 (MoE)快速指南 专家混合 (MoE) 已成为一种流行的提高 LLM 效率的架构组件。在这篇博文中，我们将探讨研究人员在实现专家完美混合的道路上所采取的步骤。 专家混合 (MoE) 已成为一种流行的提高 LLM 效率的架构组件。在这篇博文中，我们将探讨研究人…
阅读更多...
利用@WebMvcTest测试Spring MVC应用

利用@WebMvcTest测试Spring MVC应用

文章目录 1. WebMvcTest概述2. 创建Spring Boot项目3. 创建主页控制器类4. 准备图片素材5. 创建主页模板视图6. 主页控制器测试类 6.1 创建主页控制器测试类6.2 运行单元测试方法 7. 启动应用&#xff0c;查看结果 7.1 启动应用7.2 访问项目首页 8. 实战小结 1. WebMvcTest概…
阅读更多...
最新文章

Copyright @ 2022~2023