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

DS线性表之单链表的讲解和实现(2)

文章目录

  • 前言
  • 一、链表的概念
  • 二、链表的分类
  • 三、链表的结构
  • 四、前置知识准备
  • 五、单链表的模拟实现
    • 定义头节点
    • 初始化单链表
    • 销毁单链表
    • 打印单链表
    • 申请节点
    • 头插数据
    • 尾插数据
    • 头删数据
    • 尾删数据
    • 查询数据
    • 在pos位置之后插入数据
    • 删除pos位置之后的数据
  • 总结


前言

  本篇的单链表完全来说是单向不带头单链表,这种和另外一种链表(双向带头循环链表)使用最广泛,我们只要对它们两个有所了解即可

  正文开始!


一、链表的概念

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

二、链表的分类

在这里插入图片描述

三、链表的结构

  就如同下图一样,一节一节,前面连着后面就是链表的一种表现
在这里插入图片描述
在这里插入图片描述
同时我们也发现以下几点:

  1. 从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
  2. 节点一般都是在上申请出来的
  3. 从堆上申请空间,两次申请得到的内存可能连续,也可能不连续

物理结构:数据实际存储在内存中的结构;
逻辑结构:想象出来的结构

四、前置知识准备

在正式开始实现之前,我希望你有以下认识:

  1. 实现部分接口需要通过二级指针接受实参:原因在于我们需要可以修改实参(而形参只是实参的一份拷贝,要想修改实参,必须得传指针,同样若实参本来就是指针,那么就要传指针的指针,即二级指针),而是实参为一级指针时(同样是传递地址),需要使用二级指针进行接受,否则获得临时拷贝,不会影响到实参。修改实参的情况,比如一开始为空,在插入时需将头指针存储在有效结点的的地址上,需要改变实参的值
  2. 单链表的初始化:这里实现链表,没有必要进行初始化,初始化对于一开始就要开辟的空间有初始化的需求,表示多个节点通过地址链接在一起,那么只需要开辟新节点的时候,初始化下就行了(有哨兵位需要初始化)
  3. 二级指针断言:二级指针存放的是头节点的地址,头节点的地址为空,那么还有什么意义呢?

五、单链表的模拟实现

定义头节点

//单链表节点
//根据定义需要存储一个数据和一个指向下一个结点的指针
typedef int SLDataType;//定义数据类型,可以根据需要更改,typedef一下就很方便
typedef struct SList
{SLDataType data;    //数据域 存储数据struct SList* next; //指针域 存储指向下一个结点的指针
}SList;

请注意,这里不能在节点内就单独用SList来定义next指针,因为这时候还没有typedef成功呢,还在节点内部

初始化单链表

因为创建一个变量实质是给变量开辟一块内存空间,但是这块内存空间可能有遗留的数据,所以在创建变量之后需要进行初始化,而数据域我们也不清楚到底该传那个,随便传个0就行,但是指针域就必须置空了,否则就是野指针

void SListInit(SList* phead)
{assert(phead);     //防止传入空指针,传入则报错phead->data = 0;   //将数据初始化为0phead->next = NULL;//将结点指针初始化为NULL
}

销毁单链表

有开辟内存,自然而然的就有还回内存,即销毁单链表

在这里插入图片描述

void SListDestroy(SList* phead)
{assert(phead);SList* cur = phead; //为了能在后序找到头结点,所以新创建一个变量指向头结点while (cur != NULL){SList* next = cur->next;free(cur);cur = next;}
}

我们不妨来想想为什么是传一级指针即可,首先,我们这里是为了销毁内存,虽然说形参的这个节点指针和实参的节点指针地址不一样,但是所存的节点都是同一个节点!,所以可以直接传指针,有因为我们说链表在物理上是不连续的,所以得通过指针跳着跳着一个个销毁

打印单链表

在这里插入图片描述
同样的,我们只要传一级指针就可以了,且通过指针来跳转

void SListPrint(SList* phead)
{assert(phead);SList* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

申请节点

在插入中使用相当频繁,所以我们再对此单独实现一个函数,使得代码更加的结构化
在这里插入图片描述
请注意,指针并不单独开空间,它起到的更多是一个中间人的作用,通过指针来控制

SList* BuySeqList(SLDataType x)
{SList* pnewNode = (SList*)malloc(sizeof(SList));//动态开辟一个单链表类型大小if (pnewNode == NULL)//动态开辟的内存不一定成功,所以需要判断{printf("malloc fail\n");exit(-1);}//内存开辟成功则把数据赋值到指定位置pnewNode->data = x;pnewNode->next = NULL;return newnode;
}

头插数据

在这里插入图片描述

void SListPushFront(SList** pphead, SLDataType x)
{SList* newnode = BuySeqList(x);newnode->next = *pphead;*pphead = newnode;
}

尾插数据

在这里插入图片描述

void SListPushBack(SList** pphead, SLDataType x)
{SList* newnode = BuySeqList(x);if (*pphead == NULL) // 没有节点的时候{*pphead = newnode;}else // 有节点的时候{SList* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

头删数据

void SListPopFront(SList** pphead)
{assert(*pphead);//头结点不为空则有数据SList* head = (*pphead)->next;free(*pphead);*pphead = head;
}

在这里插入图片描述

尾删数据

void SListPopBack(SList** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SList* tail = *pphead;SList* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

在这里插入图片描述

查询数据

找到则返回当前当前数据结点地址,没找到则返回空地址
在这里插入图片描述

SList* SListFind(SList* phead, SLDataType x)
{assert(phead);SList* cur = phead;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

在pos位置之后插入数据

在这里插入图片描述

void SListInsertAfter(SList* pos, SLDataType x)
{assert(pos);SList* newnode = BuySeqList(x);SList* next = pos->next;pos->next = newnode;newnode->next = next;
}

删除pos位置之后的数据

在这里插入图片描述

void SListEraseAfter(SList* pos)
{assert(pos);assert(pos->next);//判断pos之后是否有数据,没数据则报错SList* next = pos->next->next;free(pos->next);pos->next = next;
}

总结

  链表可以说是CS学生遇到的第二个劝退点了(第一个是指针),它是我们所学知识的一个集成展现,需要我们对前面知识的充分掌握,所以对计算机来说,知识比较连贯,这也是学习它比较难受的地方

相关文章:

DS线性表之单链表的讲解和实现(2)

文章目录 前言一、链表的概念二、链表的分类三、链表的结构四、前置知识准备五、单链表的模拟实现定义头节点初始化单链表销毁单链表打印单链表申请节点头插数据尾插数据头删数据尾删数据查询数据在pos位置之后插入数据删除pos位置之后的数据 总结 前言 本篇的单链表完全来说是…...

LeetCode 73 Set Matrix Zeroes 题目解析和python代码

题目: Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s. You must do it in place. Example 1: Input: matrix [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]] Example 2: Input: matrix …...

鸿蒙--WaterFlow 实现商城首页

目录结构 ├──entry/src/main/ets // 代码区 │ ├──common │ │ ├──constants │ │ │ └──CommonConstants.ets // 公共常量类 │ │ └──utils │ │ └──Logger.ets // 日志打印类 │ ├──entryability │ │ └──EntryAbility.ets // 程序入口…...

QT 中如何保存matlab 能打开的.mat数据矩阵!

Windows 上安装并使用 MATIO 库来保存 MATLAB 格式的 .mat 文件,需要进行以下步骤: 1. 下载并安装 CMake MATIO 使用 CMake 构建项目,因此你需要先安装 CMake。 前往 CMake 官网下载适用于 Windows 的安装程序并安装。 2. 下载 MATIO 库源…...

菱形继承(多继承)

1. 什么是菱形继承 也就是多继承,C独有的特性。 2. 菱形继承有什么问题? (1)存在内存浪费,多存一份父类的父类。 (2)容易造成二义性(不知道修改哪一个基本属性)。 3. 如…...

【功能安全】什么是Aspice?

背景 如何设计开发一个符合功能安全的模块,大多都是按照Aspice的规范去做。所以理解Aspice就很重要。 什么是Aspice 英文全称:Automotive Software Process Improvement Capability dEtermanition ASPICE4.0文档 汽车软件过程改进及能力评定&#xf…...

基于SpringBoot的国家基础信息管理功能的设计与实现

目录 前言 一、标准信息参考 1、信息来源 二、后台基础信息的维护管理 1、实体类和Mapper类 2、业务层和控制层设计 3、前端界面实现 三、管理页面效果 1、列表管理界面 2、国家信息调整 四、总结 前言 在之前的博客中,我们基于GeoTools工具实现了全球各个…...

Python酷库之旅-第三方库Pandas(145)

目录 一、用法精讲 656、pandas.Timestamp.resolution属性 656-1、语法 656-2、参数 656-3、功能 656-4、返回值 656-5、说明 656-6、用法 656-6-1、数据准备 656-6-2、代码示例 656-6-3、结果输出 657、pandas.Timestamp.second属性 657-1、语法 657-2、参数 6…...

最懂生活的年轻人,都在喝十元奶茶

文 | 螳螂观察 作者 | 如意 以前的打工人,总把二三十的高价奶茶当成身份的象征,喝上了高价奶茶才能叫做在生活中富养自己。 只是,到盘开支的时候,打工人才猛然发觉,动辄二三十一杯的奶茶,不知不觉刮走了…...

MinIO 学习订阅服务

MinIO 的入门非常简单 — 只需几个简单的命令和一个 100 MB 的小二进制文件,您就可以立即启动并运行一个功能性开发环境。但是,为了在生产规模上利用 MinIO 的全部功能,我们鼓励专业人士更多地了解 MinIO 的广泛功能。我们推出了 MinIO 学习订…...

【D3.js in Action 3 精译_029】3.5 给 D3 条形图加注图表标签(上)

当前内容所在位置(可进入专栏查看其他译好的章节内容) 第一部分 D3.js 基础知识 第一章 D3.js 简介(已完结) 1.1 何为 D3.js?1.2 D3 生态系统——入门须知1.3 数据可视化最佳实践(上)1.3 数据可…...

用python做一个简单的画板

一,画板的介绍 画板(Paint Board)是一个提供用户绘图、涂鸦和创作的平台。现代数字画板通常是由软件程序实现的,具有多种功能。以下是画板的一些主要特征和功能: 1. 基本绘图工具 画笔和铅笔:用户可以选…...

根据传入的文件流链接实现前端下载

后端传入一个下载的url,实现点击按钮,下载文件。 方式一: 通过window.open(“URL”, _blank) 方式 PS:会打开一个新的页面 import React from react;const DownloadButton () > {// window.open("URL", "_…...

大数据新视界 --大数据大厂之大数据环境下的零信任安全架构:构建可靠防护体系

💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...

基于springboot的高校招生系统(含源码+sql+视频导入教程+文档+PPT)

👉文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 基于springboot的高校招生系统1拥有两种角色:管理员和用户 管理员:学生管理、专业管理、报名管理、录取通知管理、招生公告管理等 用户:登录注册、报…...

【C++设计模式】行为型模式:观察者模式

文章目录 行为型模式:观察者模式 行为型模式:观察者模式 观察者模式定义了一种一对多的依赖关系:它让一个主题(被观察者)对象关联多个观察者对象,并且当主题对象的状态发生变化时,它会主动通知…...

本篇5K,立志最细,FreeRtos中的信号量Semaphore教程详解!!!

前言:本篇教程,参考韦东山,开发文档,连接放在最后 目录 Semaphore基本概念 二值信号量(Binary Semaphore) 计数信号量(Couting Semaphore) 互斥信号量(Mutex&…...

【Postman】接口测试工具使用

干就完啦 Postman发送get请求案例1: Postman发送post请求案例2 Postman发送其他请求Postman测试实战 学习目标:能够使用Postman发送get/post/put/delete请求并获取响应结果 Postman发送get请求 首先postman是一款接口调试工具,支持win&…...

springboot 整合 rabbitMQ(1)

目录 一、MQ概述 二、MQ的优势和劣势 三、常见的MQ产品 RabbitMQ使用步骤 第一步:确保rabbitmq启动并且可以访问15672 第二步:导入依赖 第三步:配置 auto自动确认 manual手工确认(推荐使用!可以防止消息丢失&a…...

Appium Device Farm安装教程

环境要求:Appium version ≥ 2.4.X 安装appium npm install -g appium2.11.3 如果安装提示如下问题 npm error code EEXIST npm error syscall rename npm error path /Users/wan/.npm/_cacache/tmp/d5787519 npm error dest /Users/wan/.npm/_cacache/content-…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...