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

【数据结构】第三节:单链表

前言 

本篇要求掌握的C语言基础知识:指针、结构体

目录

前言 

单链表

概念

对比链表和顺序表

创建链表

实现单链表

准备工作

 打印链表

 创建节点并初始化

尾插

二级指针的调用

尾插代码 

头插

尾删

头删

查找(返回节点) 

 在指定位置(pos)之前插入数据

在指定位置(pos)之后插入数据

删除pos节点

删除pos之后的节点 

销毁链表


单链表

概念

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

对比链表和顺序表

顺序表

        1) 占用一大片连续内存空间

        2) 不需要额外空间存储逻辑关系,总空间需求最少

        4) 可顺序访问,支持随机访问

        5) 在C语言中,通过数组实现

        6) 数据元素的插入和删除操作通过移动元素完成

链表

        1) 不要求占用连续内存空间

        2) 不仅要存储数据,还要存储数据之间的关系,故总空间需求较大

        3) 通过指针反映逻辑关系

        4) 逻辑连续,物理可不连续

        5) 只可顺序访问,不支持随机访问

        6) 存在标记:头指针

        7) 数据元素的插入和删除操作通过修改指针完成:定位插入点/删除点的直接前驱/后

        从上文可以得知与顺序表不同的是,链表⾥的每节"⻋厢"都是独⽴申请下来的空间,我们称之为“结点/节点” ,节点的组成主要有两个部分:当前节点要保存的数据和保存下⼀个节点的地址(指针变量)。

创建链表

//创建节点
typedef int SLTDataType;typedef struct SLNode
{SLTDataType data;//数据域struct SLNode* next;//指针域
}SLTNode;//创建节点
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node4->data = 4;//链接节点
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;//尾指针置空

        其中数据域用于存放数据,指针域用于存放下一个结点的地址。上面的链表是手动创建节点,只是为了展示链表的形成,后续创建和链接单链表可以通过函数实现。

实现单链表

准备工作

在工程中一共包含三个文件

  • 定义文件SLNode.h:定义函数和结构体,头文件:stdio.h、stdlib.h、assert.h
  • 实现文件SLNode.c:实现函数具体功能,头文件:SLNode.h
  • 测试文件test.c:测试每一部分代码的正确性,头文件:SLNode.h

        在开始之前我们需要定义一个指向为空的结构体类型的节点(SLNode*)plist,作为链表的头节点。

SLNode* plist = NULL;

 打印链表

//打印
void SLTprint(SLTNode* phead)
{SLNode* pcur = phead;while (pcur != NULL){printf("%d ", pcur->data);pcur = pcur->next;}printf("\n");
}

 创建节点并初始化

//创建节点并初始化
SLNode* SLTbuyNode(SLTDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));//创建新节点if (newnode == NULL){perror("malloc fail!");exit(1);//表示非正常退出}newnode->data = x;newnode->next = NULL;return newnode;
}

尾插

二级指针的调用

        从这一部分开始就涉及到了二级指针传参的问题,在对单链表进行尾插时,如果此时头节点plist指向为空(即该单链表为空),就需要在函数内部改变头指针的指向,指向新插入的节点。

        这里举一个简单的例子,假如我要实现一个交换两个整形数据的函数,应该如何实现?

void Exchange(int a,int b)
{int tmp=a;a=b;tmp=b;
}

        如果仅仅将两个整形作为参数是无法成功的,因为在主函数中调用Exchange时在栈帧中又开辟了一块地址不同于主函数的函数栈帧,以上"传值调用"仅仅将形参里的内容进行交换,在函数执行结束时所占据的空间会被释放,同时形参也会因为被销毁而无法对实参产生影响。

        如果想要"形参影响实参",就要把"传值调用"改为"传址调用",即将变量的地址作为参数传给函数,对应的函数参数应为指针类型。

void Exchange(int* a,int* b)
{int* tmp=*a;*a=*b;*tmp=*b;
}

        这样就实现了交换两个数据的操作。

        同理,想要在函数内部改变一级头指针plist的指向,应该把plist的地址传入,用二级指针接收,也就是"传址调用",如果只传递一级指针(即链表的头指针),无法直接修改它所指向的地址,因为在函数内部对指针的修改不会影响到函数外部,最终只是将形参指针的指向改变而无法对实参造成影响。为了实现对链表头指针的修改,需要传递指向指针的指针,这样在函数内部就可以修改指针所指向的地址,从而改变链表的头指针。

 来一张图解释二级指针

总结:只要头指针发生改变就需要用到二级指针

尾插代码 

void SLTpushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTbuyNode(x);if (*pphead == NULL)//链表为空{*pphead = newnode;}else{SLNode* ptail = *pphead;while (ptail->next != NULL)//遍历链表找到尾节点{ptail = ptail->next;}ptail->next = newnode;}
}

头插

       与尾插同理,头指针的指向发生改变,需要借助二级指针

void SLTpushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTbuyNode(x);newnode->next = *pphead;//*pphead是指向第一个节点的指针*pphead = newnode;
}

尾删

void SLTpopBack(SLTNode** pphead)
{assert(pphead && *pphead);//*pphead为空说明整个链表为空if ((*pphead)->next == NULL)//链表中只有一个节点{free(*pphead);*pphead = NULL;}else{SLTNode* ptail = *pphead;SLTNode* prev = *pphead;while (ptail->next != NULL){prev = ptail;//prev指向的是尾节点的前一个节点ptail = ptail->next;}free(ptail);prev->next = NULL;//prev成为新的尾节点ptail = NULL;}
}

头删

void SLTpopFront(SLTNode** pphead)
{assert(pphead && *pphead);if ((*pphead) == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* p = *pphead;//此时p指向的是头节点*pphead = (*pphead)->next;free(p);p = NULL;}
}

查找(返回节点) 

SLNode* SLTfind(SLTNode* phead, SLTDataType x)
{assert(phead);SLNode* pcur = phead;while (pcur != NULL){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;//没有找到返回NULL
}

 在指定位置(pos)之前插入数据

void SLTinsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead && pos);SLTNode* pcur = *pphead;SLNode* newnode = SLTbuyNode(x);if (pos == *pphead){SLTpushFront(pphead, x);}else{while (pcur->next != pos)//遍历到pos节点的前驱节点{pcur = pcur->next;}newnode->next = pos;pcur->next = newnode;}
}

在指定位置(pos)之后插入数据

void SLTinsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLNode* newnode = SLTbuyNode(x);if (pos->next == NULL)//如果pos是尾节点{pos->next = newnode;newnode->next = NULL;}else{SLNode* pafter = pos->next;//pcur是pos的后继节点newnode->next = pafter;pos->next = newnode;}
}

         在这里不调用二级指针的原因是头指针无需改变,需要改变的时pos节点内部next指针的指向,而对于next指针来说,pos指向的时next所在的节点,所以pos可以直接访问这个黑点,从而改变next的指向,换句话pos相对于next来说就是二级指针

删除pos节点

void SLTerase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead && pos && pphead);if (pos->next == NULL)//如果pos是尾节点{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = NULL;free(pos);pos = NULL;}else if (*pphead == pos)//如果pos是头节点{SLTNode* next = (*pphead)->next;free(*pphead);(*pphead) = next;}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

删除pos之后的节点 

void SLTeraseAfter(SLTNode* pos)
{assert(pos->next && pos);SLTNode* next = pos->next;pos->next = pos->next->next;free(next);next = NULL;
}

销毁链表

void SLTdestroy(SLTNode** pphead)
{assert(*pphead && pphead);SLTNode* pcur = *pphead;while (pcur != NULL){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

相关文章:

【数据结构】第三节:单链表

前言 本篇要求掌握的C语言基础知识:指针、结构体 目录 前言 单链表 概念 对比链表和顺序表 创建链表 实现单链表 准备工作 打印链表 创建节点并初始化 尾插 二级指针的调用 尾插代码 头插 尾删 头删 查找(返回节点) 在指定位…...

Python中操作Excel表对象并打包为脚本

一、准备工作 pip install pandas pip install openpyxl pip install pyinstaller 数据表格: 数据表下载 二、执行写入操作 import pandas as pd # pyinstaller --onefile attendance_records_score.py # 打包 # 读取源Excel文件(假设源表有列A…...

Python学习笔记23 - 目录操作

os模块操作目录相关函数 os.path模块操作目录相关函数 案例1 —— 列出指定目录下的所有.py文件 案例2 —— walk()...

今天你学langchain了吗?

langchain的重重难关 学习langchain也有一段时间了,从最初的0.0339版本到现在的稳定版本,langchain走了很长的路.在学习的路上也遇到了很多的困难. api_key难关 学习langchain最大的困难就是openai的API_KEY,国内无法申请到官方账号,申请到了也无法进行充值.好在有几美元的免…...

插值算法-代码实现

1、 import java.util.HashMap; import java.util.Map;public class Interpolation {public static void main(String[] args) {// 定义给定的 XML 字段值Map<String, double[]> xmlValues new HashMap<>();xmlValues.put("faceSize", new double[]{10…...

113.PyQt5_QtPrintSupport_打印操作

我 的 个 人 主 页&#xff1a;&#x1f449;&#x1f449; 失心疯的个人主页 &#x1f448;&#x1f448; 入 门 教 程 推 荐 &#xff1a;&#x1f449;&#x1f449; Python零基础入门教程合集 &#x1f448;&#x1f448; 虚 拟 环 境 搭 建 &#xff1a;&#x1f449;&…...

在vue中使用bing map 的小demo

1.注意事项&#xff08;关于经纬度&#xff09; 如果不转换成WGS84 标准的经纬度 bing map会报错 如果要在 Bing Maps 中使用中国地区的经纬度&#xff0c;需要先将其转换为 WGS84 标准的经纬度。你可以使用第三方的坐标转换服务&#xff0c;或者使用相关的 JavaScript 库进行…...

基于uni-app的埋点sdk设计

一、统计app激活状态 在App.vue 中 利用onShow生命周期验证 或者操作 onShow: function () { uni.showToast({ title: onShow }) }, 二、页面级别的统计 &#xff08;进入页面、停留时长、手机系统信息、网络状态、页面路径、标题&#xff09; 需要收集的数据 { &quo…...

Python学习笔记(三)

一、使用朴素贝叶斯制作鸢尾花数据模型 from sklearn.preprocessing import StandardScaler from sklearn.naive_bayes import MultinomialNB from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split from sklearn.feature_extraction…...

Python办公自动化之Excel做表自动化:全网最全,看这一篇就够了!

0 Python Excel库对比 我们先来看一下python中能操作Excel的库对比&#xff08;一共九个库&#xff09;&#xff1a; 1 Python xlrd 读取 操作Excel 1.1 xlrd模块介绍 &#xff08;1&#xff09;什么是xlrd模块&#xff1f; python操作excel主要用到xlrd和xlwt这两个库&…...

【学习笔记】R语言入门与数据分析1

数据分析 数据分析的过程&#xff1a; 数据采集 数据存储 数据分析 数据挖掘 数据可视化 进行决策 数据挖掘 数据量大 复杂度高&#xff0c;容忍一定的误差限 追求相关性而非因果性 数据可视化 直观明了 R语言介绍 R是免费的&#xff08;开源软件、扩展性好&#xff09;…...

MyBatis-Spring整合

引入Spring之前需要了解mybatis-spring包中的一些重要类&#xff1b; http://www.mybatis.org/spring/zh/index.html 什么是 MyBatis-Spring&#xff1f; MyBatis-Spring 会帮助你将 MyBatis 代码无缝地整合到 Spring 中。 知识基础 在开始使用 MyBatis-Spring 之前&#x…...

资深亚马逊运营实战技巧:跨境电商6大选品法

1、工具选品法 比如店雷达&#xff0c; 通过大数据分析工具选出来利基产品或者通过工具选出来利基的市场&#xff0c;然后再通过分析市场来得到产品。 以女装为例&#xff0c;通过大数据分析&#xff0c;全方位对市场需求、款式、质量等进行多维度判断&#xff0c;其中SKU销量…...

bugku-web-需要管理员

页面源码 <html> <head> <meta http-equiv"Content-Type" content"text/html; charsetUTF-8"> <title>404 Not Found</title> </head> <body> <div idmain><i> <h2>Something error:</h2…...

STM32之FreeRTOS移植

1.FreeRTOS的移植过程是将系统需要的文件和代码进行移植和裁剪&#xff0c;其移植的主要过程为&#xff1a; &#xff08;1&#xff09;官网上下载FreeRTOS源码&#xff1a;https://www.freertos.org/ &#xff08;2&#xff09;移植文件夹&#xff0c;在portable文件夹中只需…...

SpringBoot实用开发(十四)-- 消息(Message)的简单认识

目录 1.消息的概念 2.Java处理消息的标准规范 3.JMS 4.AMQP 5.MQTT 1.消息的概念 广义角度来说,消息其实就是信息,但是和信息又有所不同。信息通常被定义为一组数据,而消息除了具有数据的特征之外,还有...

【Spring Boot 源码学习】SpringApplication 的 run 方法核心流程介绍

《Spring Boot 源码学习系列》 SpringApplication 的 run 方法核心流程介绍 一、引言二、往期内容三、主要内容3.1 run 方法源码初识3.2 引导上下文 BootstrapContext3.3 系统属性【java.awt.headless】3.4 早期启动阶段3.5 准备和配置应用环境3.6 打印 Banner 信息3.7 新建应用…...

如何保证消息不丢失?——使用rabbitmq的死信队列!

如何保证消息不丢失?——使用rabbitmq的死信队列&#xff01; 1、什么是死信 在 RabbitMQ 中充当主角的就是消息&#xff0c;在不同场景下&#xff0c;消息会有不同地表现。 死信就是消息在特定场景下的一种表现形式&#xff0c;这些场景包括&#xff1a; 消息被拒绝访问&am…...

html、css、京东移动端静态页面,资源免费分享,可作为参考,提供InsCode在线运行演示

CSDN将我上传的免费资源私自变成VIP专享资源&#xff0c;且作为作者的我不可修改为免费资源&#xff0c;不可删除&#xff0c;寻找客服无果&#xff0c;很愤怒&#xff0c;&#xff08;我发布免费资源就是希望大家能免费一起用、一起学习&#xff09;&#xff0c;接下来继续寻找…...

头歌-机器学习 第13次实验 特征工程——共享单车之租赁需求预估

第1关&#xff1a;数据探索与可视化 任务描述 本关任务&#xff1a;编写python代码&#xff0c;完成一天中不同时间段的平均租赁数量的可视化功能。 相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a; 读取数据数据探索与可视化 读取数据 数据保存在./step1/…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...