【数据结构】无头+单向+非循环链表（SList）（增、删、查、改）详解

news/2024/4/24 8:49:39/文章来源:https://blog.csdn.net/weixin_74531333/article/details/131964384

一、链表的概念及结构

1、链表的概念

之前学习的顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，而链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，可以实现更加灵活的动态内存管理。

 注：之所以引出链表，是因为顺序表存在一些缺点。

  • 顺序表在中间 / 头部的插入和删除，需要挪动很多数据，时间复杂度为 O(N)，效率低下。
  • 增容需要申请新空间，拷贝数据，释放旧空间。消耗不小。
  • 增容一般是一次增长 2 倍，那就一定会造成空间浪费。例如当前的容量为 100，满了以后增容到 200，这时再继续插入 5 个数据，后面不再插入，那么就浪费了 95 个数据空间。

2、链表的组成

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：

  1. 数据域：存储数据元素。
  2. 指针域：存储下一个结点地址。

3、链表的结构

（1）链表的物理结构（现实中）

（2）链表的逻辑结构（想象中）

 注：

  • 链式结构在逻辑上是连续的，但在物理上不一定连续。
  • 现实中的结点一般都是从堆上申请出来的。
  • 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

 二、无头+单向+非循环链表的接口实现

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

1、创建文件

  • test.c（主函数、测试顺序表各个接口功能）
  • SList.c（单链表接口函数的实现）
  • SList.h（单链表的类型定义、接口函数声明、引用的头文件）

2、SList.h 头文件代码

// SList.h
// 无头+单向+非循环链表增删查改实现
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int SLTDateType;typedef struct SListNode
{SLTDateType data; // 数据域struct SListNode* next; // 指针域
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 销毁单链表中所有节点
void SListDestory(SListNode** pphead)
// 单链表打印
void SListPrint(SListNode* phead);
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pphead);
// 单链表头删
void SListPopFront(SListNode** pphead);
// 单链表查找
SListNode* SListFind(SListNode* phead, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 求单链表长度
int SListSize(SListNode* phead);
// 单链表判空
bool SListEmpty(SListNode* phead);

三、在 SList.c 中实现各个接口函数

1、动态申请一个节点

// 动态申请一个节点
SListNode* BuyListNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));newnode->data = x;newnode->next = NULL;return newnode;
}

2、销毁（释放）所有节点

// 销毁单链表中所有节点
void SListDestory(SListNode** pphead)
{assert(pphead);SListNode* cur = *pphead;while (cur){SListNode* next = cur->next;free(cur); // 释放节点cur = next;}*pphead = NULL;
}

注：assert() 放在函数里面检查参数，一方面是为了安全，另一方面是为了防止其他人在调用该函数时，出现不正确的使用，导致错误传入参数，这样可以及时提醒到他。所以写代码时一定要考虑到其他人不正确的使用该函数时的场景，以此避免不必要的麻烦。 

3、单链表打印

// 单链表打印
void SListPrint(SListNode* phead)
{// 不需要断言 -- 空链表也可以打印SListNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

4、单链表尾插

// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{SListNode* newnode = BuySListNode(x);  //动态申请一个节点if (*pphead == NULL) // 单链表中没有节点时{*pphead = newnode; // plist指向新节点}else // 单链表中已经有节点时{SListNode* tail = *pphead;while (tail->next != NULL) // 找到单链表中的最后一个节点{tail = tail->next;}tail->next = newnode; // 最后一个节点的next指向新节点}
}
  错误写法❌：

（传一级指针的值，用一级指针接收）指针传值，相当于把 plist 指针变量的值拷贝给 phead，给 phead 赋值 newnode，phead 的改变不会影响 plist。

// 错误写法：
// 单链表尾插
void SListPushBack(SListNode* phead, SLTDateType x)
{SListNode* newnode = BuySListNode(x);  //动态申请一个节点if (phead == NULL) // 单链表中没有节点时{phead = newnode; // plist指向新节点}else // 单链表中已经有节点时{SListNode* tail = phead; // 找到尾节点while (tail->next != NULL) // 找到单链表中的最后一个节点{tail = tail->next;}tail->next = newnode; // 最后一个节点的next指向新节点}
}

因为当链表为空时，我们需要改变 plist 的指向，使其指向第一个节点。而初始 plist 和 phead 都指向 NULL，调用函数后，phead 指向了新的节点，而 plist 还是指向 NULL 的。

 解决方法：

plist 是指向第一个节点的指针，想要在函数中改变 plist 的值（指向），必须要把 plist 指针的地址 作为实参传过去，形参用二级指针接收，这样在函数中对二级指针解引用得到 plist 的值，就可以改变 plist 的值（指向）了。

  • 单链表为空时，plist 直接指向新节点。
  • 单链表不为空时，先找到单链表的尾节点，然后将尾节点的 next 指向新节点。

5、单链表头插

// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{assert(pphead);SListNode* newnode = BuyListNode(x); // 动态申请一个节点newnode->next = *pphead; // 新节点的next指针指向plist指向的位置*pphead = newnode; // plist指向头插的新节点
}

6、单链表尾删

// 单链表的尾删
void SListPopBack(SListNode** pphead)
{assert(pphead);assert(*pphead); //链表为空就无法再进行尾删了// 温柔处理方式/*if (*pphead == NULL){return;}*/// 粗暴处理方式assert(*pphead);if ((*pphead)->next == NULL) // 链表一个节点{free(*pphead);*pphead = NULL;}else // 链表中有多个节点{// 写法一：/* SListNode* prev = NULL;SListNode* tail = *pphead;while(tail->next != NULL) // 找到链表的尾节点的上一个节点{prev = tail;tail = tail->next;}free(tail); // 删除尾节点tail = NULL;prev->next = NULL;  // 置空 *///写法二：SListNode* tail = *pphead;while (tail->next->next != NULL) // 找到链表的尾节点的上一个节点{tail = tail->next;}free(tail->next); // 删除尾节点tail->next = NULL; // 置空}
}

  •  单链表只有一个节点时，删除节点，plist 指向 NULL。
  • 单链表有多个节点时，先找到单链表尾节点的上一个节点，删除尾节点，然后将该节点的 next 指向 NULL。
  • 因为可能要改变外部 plist 的指向，所以用二级指针接收指针 plist 的地址。

7、单链表头删

// 单链表头删
void SListPopFront(SListNode** pphead)
{assert(pphead);assert(*pphead); // 链表为空就无法再进行头删了/*if (*pphead == NULL){return;}else{SListNode* next = (*pphead)->next;free(*pphead);*pphead = next;}*/SListNode* cur = *pphead; // 保存头节点的地址*pphead = cur->next; // plist指向头节点的下一个节点free(cur); // 删除头节点
}

注：因为可能要改变外部 plist 的指向，所以用二级指针接收指针 plist 的地址。 

8、单链表查找指定值的节点

// 单链表查找
SLTNode* SListFind(SListNode* phead, SLTDataType x)
{SListNode* cur = phead;while (cur){if (cur->data == x){return cur; // 找到了 返回该节点的地址}else{cur = cur->next;}}return NULL; // 未找到，返回NULL
}

9、单链表在pos位置之后插入x

// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos); // pos位置不能为空SListNode* newnode = BuySListNode(x); // 动态申请一个节点newnode->next = pos->next; // 新节点的next指针指向pos位置后一个节点pos->next = newnode; // pos位置的next指向新节点
}

为什么不在pos位置之前插入？
  • 单链表不适合在 pos 位置之前插入，因为需要遍历链表找到 pos 位置的前一个节点，时间复杂度为O(N)。
  • 单链表更适合在 pos 位置之后插入，如果在后面插入，只需要知道 pos 位置即可，简单得多。
  • C++ 官方库里面单链表给的也是在之后插入。

10、单链表删除指定pos位置之后的节点

// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos); // pos位置不能为空assert(pos->next); // pos位置不能是尾节点SListNode* next = pos->next; // 保存pos位置的后一个节点pos->next = pos->next->next;free(next); // 释放pos位置的后一个节点
}

为什么不删除pos位置？
void SListErase(SListNode** pphead, SLTNode* pos) // O(N)
{assert(pphead);assert(pos);if (*pphead == pos){/* *pphead = pos->next;free(pos); */SListPopFront(pphead);}else{SListNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);//pos = NULL;}
}
  • 删除 pos 位置同样需要传入单链表的二级指针。
  • 单链表不适合在 pos 位置插入，因为需要遍历链表找到 pos 位置的前一个节点，以改变其指向，时间复杂度大。

11、求单链表长度

// 求单链表长度
int SListSize(SListNode* phead)
{int size = 0;SListNode* cur = phead;while (cur){size++;cur = cur->next;}return size;
}

12、判断单链表是否为空

// 单链表判空
bool SListEmpty(SListNode* phead)
{// 写法一：return phead == NULL;// 写法二：//return phead == NULL ? true : false;
}

四、代码整合

// SList.c
#include "SList.h"// 动态申请一个节点
SListNode* BuyListNode(SLTDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));newnode->data = x;newnode->next = NULL;return newnode;
}// 销毁单链表中所有节点
void SListDestory(SListNode** pphead)
{assert(pphead);SListNode* cur = *pphead;while (cur){SListNode* next = cur->next;free(cur); // 释放节点cur = next;}*pphead = NULL;
}// 单链表打印
void SListPrint(SListNode* phead)
{SListNode* cur = phead;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{SListNode* newnode = BuySListNode(x);  //动态申请一个节点if (*pphead == NULL) // 单链表中没有节点时{*pphead = newnode; // plist指向新节点}else // 单链表中已经有节点时{SListNode* tail = *pphead;while (tail->next != NULL) // 找到单链表中的最后一个节点{tail = tail->next;}tail->next = newnode; // 最后一个节点的next指向新节点}
}// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDataType x)
{assert(pphead);SListNode* newnode = BuyListNode(x); // 动态申请一个节点newnode->next = *pphead; // 新节点的next指针指向plist指向的位置*pphead = newnode; // plist指向头插的新节点
}// 单链表的尾删
void SListPopBack(SListNode** pphead)
{assert(pphead);assert(*pphead); //链表为空就无法再进行尾删了assert(*pphead);if ((*pphead)->next == NULL) // 链表一个节点{free(*pphead);*pphead = NULL;}else // 链表中有多个节点{SListNode* tail = *pphead;while (tail->next->next != NULL) // 找到链表的尾节点的上一个节点{tail = tail->next;}free(tail->next); // 删除尾节点tail->next = NULL; // 置空}
}// 单链表头删
void SListPopFront(SListNode** pphead)
{assert(pphead);assert(*pphead); // 链表为空就无法再进行头删了SListNode* cur = *pphead; // 保存头节点的地址*pphead = cur->next; // plist指向头节点的下一个节点free(cur); // 删除头节点
}// 单链表查找
SLTNode* SListFind(SListNode* phead, SLTDataType x)
{SListNode* cur = phead;while (cur){if (cur->data == x){return cur; // 找到了 返回该节点的地址}else{cur = cur->next;}}return NULL; // 未找到，返回NULL
}// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos); // pos位置不能为空SListNode* newnode = BuySListNode(x); // 动态申请一个节点newnode->next = pos->next; // 新节点的next指针指向pos位置后一个节点pos->next = newnode; // pos位置的next指向新节点
}// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{assert(pos); // pos位置不能为空assert(pos->next); // pos位置不能是尾节点SListNode* next = pos->next; // 保存pos位置的后一个节点pos->next = pos->next->next;free(next); // 释放pos位置的后一个节点
}// 求单链表长度
int SListSize(SListNode* phead)
{int size = 0;SListNode* cur = phead;while (cur){size++;cur = cur->next;}return size;
}// 单链表判空
bool SListEmpty(SListNode* phead)
{// 写法一：return phead == NULL;
}

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

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

相关文章

SpringBoot项目连接数据库

SpringBoot项目连接数据库

1、找到applications.yml&#xff0c;如下图 2、写入代码 server:port: 9494spring:datasource:driver-class-name: com.mysql.cj.jdbc.Driverurl: jdbc:mysql://localhost:3306/自己的数据库表名?serverTimezoneGMT%2b8username: rootpassword: root
阅读更多...
[C语言] 数组

[C语言] 数组

1. 一维数组的创建和初始化 2. 一维数组的使用 3. 一维数组在内存中的存储 4. 二维数组的创建和初始化 5. 二维数组的使用 6. 二维数组在内存中的存储 7. 数组越界 8. 数组作为函数参数 9. 数组的应用实例 1 &#xff1a;三子棋 10. 数组的应用实例 2 &#…
阅读更多...
Spring Tool Suite 4

Spring Tool Suite 4

参考&#xff1a;Spring tool suite4 安装及配置_springtoolsuite4_猿界零零七的博客-CSDN博客 下载&#xff1a;Spring | Tools 将下载的JAR进行解压两次&#xff0c;直至解压出contents中的sts 双击启动 第一次打开需要指定工作区文件夹 配置Maven的config 安装插件
阅读更多...
Pytorch学习笔记1：张量+训练参数传入与处理+制作训练集

Pytorch学习笔记1：张量+训练参数传入与处理+制作训练集

文章目录 Pytorch中张量的一些常见函数最基础也最常见的方法关于Indexing, Slicing, Joining, Mutating Ops&#xff08;索引、切片、聚合、旋转&#xff09;随机种子torch.bernoulli(input)torch.normaltorch.rand(size)torch.randn(size)torch.randperm(n) Python--argparse-…
阅读更多...
Hexo+GithubPages免费搭建个人博客网站

Hexo+GithubPages免费搭建个人博客网站

HexoGithubPages免费搭建个人博客网站 目录 一、前言二、Github配置 新建同名仓库配置Pages 三、安装Hexo四、配置hexo-deployer-git五、访问六、发布文章七、安装主题 一、前言 我之前开了好几年的云服务器了&#xff0c;实际上使用场景并不是很多&#xff0c;感觉有点浪费…
阅读更多...
什么叫前后端分离？为什么需要前后端问题？解决了什么问题？

什么叫前后端分离？为什么需要前后端问题？解决了什么问题？

单体架构出现的问题 引出&#xff1a;来看一个单体项目架构的结构 通过上述可以看到单体架构主要存在以下几点问题&#xff1a; 开发人员同时负责前端和后端代码开发&#xff0c;分工不明确开发效率低前后端代码混合在一个工程中&#xff0c;不便于管理对开发人员要求高(既会前…
阅读更多...
网络层中一些零碎且易忘的知识点

网络层中一些零碎且易忘的知识点

异构网络&#xff1a;指传输介质、数据编码方式、链路控制协议以及数据单元格式和转发机制不同&#xff0c;异构即物理层和数据链路层均不同RIP、OSPF、BGP分别是哪一层的协议&#xff1a; -RIPOSPFBGP所属层次应用层网络层应用层封装在什么协议中UDPIPTCP 一个主机可以有多个I…
阅读更多...
Manjaro KDE 22.1.3vmware无法复制文件

Manjaro KDE 22.1.3vmware无法复制文件

Wayland 是 X11 的现代替代品&#xff0c;几十年来 X11 一直是 Linux 上的默认窗口系统。 Wayland 是一种通信协议&#xff0c;定义 X Window 显示服务器和客户端应用程序之间的消息传递。 软件还不兼容 使用X11即可
阅读更多...
HCIP重发布实验

HCIP重发布实验

目录 实验要求&#xff1a; 步骤一&#xff1a;拓扑设计IP地址规划 拓扑设计 R1 R2 R3 R4 发布路由 R1 R2 R3 R4 双向重发布 在R2和R4 上进行 R2 R4 检查R1 修改开销值选路 择优选择去4.0网段的路径 测试&#xff1a;​编辑 择优选择去32网段的路径 测试&…
阅读更多...
Stable Diffusion 开源模型 SDXL 1.0 发布

Stable Diffusion 开源模型 SDXL 1.0 发布

关于 SDXL 模型&#xff0c;之前写过两篇&#xff1a; Stable Diffusion即将发布全新版本Stable Diffusion XL 带来哪些新东西&#xff1f; 一晃四个月的时间过去了&#xff0c;Stability AI 团队终于发布了 SDXL 1.0。当然在这中间发布过几个中间版本&#xff0c;分别是 SDXL …
阅读更多...
Codeforces算法心得——A. Escalator Conversations

Codeforces算法心得——A. Escalator Conversations

大家好&#xff0c;我是晴天学长&#xff0c;今天开始尝试一些外国的题目了&#xff0c;不得不说&#xff0c;创新性挺高的&#xff0c;然后是全英文&#xff0c;也可以练练英文的水平&#xff0c;后面我会持续的更新的&#xff01;加油&#xff01;&#x1f4aa;&#x1f4aa;…
阅读更多...
【Java】使用JDBC操作MySQL 8（快速入门+详解）

【Java】使用JDBC操作MySQL 8（快速入门+详解）

文章目录 1. JDBC概述2. JDBC快速入门2.1 下载驱动jar包2.2 数据准备2.3 创建工程2.4 编写代码 3. JDBC API详解3.1 DriverManager3.2 Connection3.2.1 获取执行SQL对象3.2.1 管理事务 3.3 Statement3.3.1 执行DML语句3.3.2 执行DDL语句 3.4 ResultSet3.4.1 ResultSet对象方法3…
阅读更多...
python下的control库使用

python下的control库使用

文章目录 control的官方网站函数示例强迫响应forced_response control的官方网站 函数示例 强迫响应forced_response import numpy as np import os import sys import control as ctrl import matplotlib.pyplot as pltdef lim_x(x, lim0):res 0if x > lim:res 1else:…
阅读更多...
FL Studio 21官方中文版功能介绍及2023最新下载详细图文安装激活教程。FL Studio 21需要系统配置要求

FL Studio 21官方中文版功能介绍及2023最新下载详细图文安装激活教程。FL Studio 21需要系统配置要求

FL Studio 21版本更新现已发布&#xff0c;在这次更新中优化了很多功能&#xff0c;但这些现在都不重要&#xff0c;FL Studio21版本的这次更新中令人瞩目的更新莫过于对简体中文版的支持了。以前FL Studio只有英文版&#xff0c;想要用上中文版只有用汉化包&#xff0c;而且有…
阅读更多...
数字化新时代，VR全景拍摄与制作

数字化新时代，VR全景拍摄与制作

导语&#xff1a; 随着科技的飞速发展&#xff0c;数字化图片正在引领新的时代潮流。在这个数字化图片的新时代&#xff0c;VR全景拍摄与制作技术正以其独特的特点和无限的优势&#xff0c;成为数字影像领域的一颗璀璨明星。让我们深入了解VR全景拍摄与制作的特点和优势&#…
阅读更多...
QT：手动实现登录框

QT：手动实现登录框

要求&#xff1a; 1、登录窗口更改标题、图标 2、设置固定尺寸、并给定一定的透明度 #include "mainwindow.h"MainWindow::MainWindow(QWidget *parent): QMainWindow(parent) {this->setFixedSize(800,650); //设置固定尺寸qDebug()<<this->windowT…
阅读更多...
线性代数(应用篇)：第五章:特征值与特征向量、第六章:二次型

线性代数(应用篇)：第五章:特征值与特征向量、第六章:二次型

文章目录 第5章 特征值与特征向量、相似矩阵(一) 特征值与特征向量1.定义2.性质3.求解(1)具体型矩阵试根法、多项式带余除法&#xff1a;三阶多项式分解因式 (2)抽象型矩阵 (二) 相似1.矩阵相似(1)定义(2)性质 2.相似对角化(1)定义(2)相似对角化的条件&#xff08;n阶矩阵A可相…
阅读更多...
Java的标记接口（Marker Interface）

Java的标记接口（Marker Interface）

Java中的标记接口&#xff08;Marker Interface&#xff09;是一个空接口&#xff0c;接口内什么也没有定义。它标识了一种能力&#xff0c;标识继承自该接口的接口、实现了此接口的类具有某种能力。 例如&#xff0c;jdk的com.sun.org.apache.xalan.internal.xsltc.trax.Temp…
阅读更多...
aardio - 关于 loadcode 和 loadcodex 的用法

aardio - 关于 loadcode 和 loadcodex 的用法

关于 loadcode 和 loadcodex 的用法&#xff0c;资料较少&#xff0c;我简单写了几种用法&#xff0c;作为抛砖引玉。 大家还有其他使用技巧&#xff0c;请跟帖&#xff1a; import consoletest1 /** myTestFunc1 function(){ return myFunc1; } **/ loadcodex(test1); co…
阅读更多...
【业务功能篇60】Springboot + Spring Security 权限管理 【终篇】

【业务功能篇60】Springboot + Spring Security 权限管理 【终篇】

4.4.7 权限校验扩展 4.4.7.1 PreAuthorize注解中的其他方法 hasAuthority&#xff1a;检查调用者是否具有指定的权限&#xff1b; RequestMapping("/hello")PreAuthorize("hasAuthority(system:user:list)")public String hello(){return "hello Sp…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站