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

《数据结构：单链表》

news 来源：原创 2025/7/14 21:02:14

“希望就像星星，或许光芒微弱，但永不熄灭。”

博主的个人gitee：https://gitee.com/friend-a188881041351

一.概念与结构

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

单链表由一系列节点组成，每个节点包含两部分：

数据部分：存储实际的数据。
指针部分：存储指向下一个节点的指针。

单链表的特点是：

每个节点通过指针连接到下一个节点。

除了最后一个节点外，每个节点都有一个后继节点。

单链表的头节点（头指针）是链表的入口。

二.单链表的定义

1.链表的组成

链表是由节点构成的。链表中每个结点都是独立申请的（即需要插入数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

2.链表的性质

链式机构在逻辑上是连续的，在物理结构上不⼀定连续。
结点⼀般是从堆上申请的。
从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续。

3.单链表的定义

typedef int SLTDataType;
typedef struct SListNode 
{SLTDataType data;struct SListNode* next;//指向下一个结点的指针
}SLTNode;

当我们想要保存⼀个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个结点的地址（当下⼀个结点为空时保存的地址为空）。

当我们想要从第⼀个结点走到最后⼀个结点时，只需要在当前结点拿上下一个结点的地址就可以了。

三.单链表的操作（增、删、查、改）

先在"List.h"中：

//phead：头（首）结点
void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDestroy(SLTNode** pphead);

先写前置函数方便接下来的代码编写：

//向操作系统申请一个新节点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

1.单链表插入元素

a.头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

b.尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，phead直接指向newnode结点if (*pphead == NULL){*pphead = newnode;}else {   //链表不为空，找尾结点，将尾结点和新节点连接起来SLTNode* ptail = *pphead;while (ptail->next)//等价于ptail->next != NULL{ptail = ptail->next;}ptail->next = newnode;}
}

c.在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);//pos就是头结点if (pos == *pphead){//头插SLTPushFront(pphead, x);}else {SLTNode* newnode = SLTBuyNode(x);//pos在头结点之后--->找pos前驱节点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev newnode  posnewnode->next = pos;prev->next = newnode;}
}

d.在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

2.单链表删除元素

a.尾删

void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead);//只有一个结点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else {SLTNode* prev = NULL;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}//prev ptailprev->next = NULL;free(ptail);ptail = NULL;}
}

b.头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

c.删除指定位置的数据

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && pos);//要删除的结点刚好就是头结点---头删if (pos == *pphead){SLTPopFront(pphead);}else {//prevSLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}

d.删除指定位置之后的数据

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

3.单链表查找元素

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//未找到return NULL;
}

4.链表的销毁

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

如有错误，恳请指正.

《数据结构：单链表》

“希望就像星星，或许光芒微弱，但永不熄灭。” 博主的个人gitee：https://gitee.com/friend-a188881041351 一.概念与结构链表是一种物理存储上非连续、非顺序的存储结构，数据元素的顺序逻辑是通过链表中的指针链接次序实现的。单…...

编程日记 2025/7/14 21:02:14

RedHatLinux(2025.3.22)

1、创建/www目录，在/www目录下新建name和https目录，在name和https目录下分别创建一个index.htm1文件，name下面的index.html 文件中包含当前主机的主机名，https目录下的index.htm1文件中包含当前主机的ip地址。 （1&…...

编程日记 2025/7/14 20:58:00

C++异常处理完全指南：从原理到实战

文章目录异常的基本概念基本异常抛出与捕获多类型异常捕获异常重新抛出异常安全异常规范（noexcept）栈展开与析构标准库异常总结异常的基本概念异常是程序运行时发生的非预期事件（如除零、内存不足）。C通过try、catch和throw提…...

编程日记 2025/7/14 20:44:08

Oracle 19C 备份

在 Oracle 19c 中，备份数据库通常使用 RMAN（Recovery Manager） 工具，它是 Oracle 提供的官方备份和恢复工具。以下是通过 RMAN 备份 Oracle 19c 数据库的详细步骤和命令。一、RMAN 基本概念 RMAN 是 Oracle 的备份和恢复工具&am…...

编程日记 2025/7/14 20:54:11

深入理解MySQL聚集索引与非聚集索引

在数据库管理系统中，索引是提升查询性能的关键。MySQL支持多种类型的索引，其中最基础也是最重要的两种是聚集索引和非聚集索引。本文将深入探讨这两种索引的区别，并通过实例、UML图以及Java代码示例来帮助您更好地理解和应用它们。一、概念…...

编程日记 2025/7/14 20:57:13

用Python打造智能宠物：强化学习的奇妙之旅

友友们好！我是Echo_Wish，我的的新专栏《Python进阶》以及《Python！实战！》正式启动啦！这是专为那些渴望提升Python技能的朋友们量身打造的专栏，无论你是已经有一定基础的开发者，还是希望深入挖掘Python潜力的爱好者，这里都将是你不可错过的宝藏。在这个专栏中，你将会…...

编程日记 2025/7/14 20:47:07

OGG故障指南：OGG-01163 Bad column length (xxx) specified for column

报错 OGG-01163 Bad column length (xxx) specified for column AAA in table OWNER.TABLE, maximum allowable length is yyy原因源端修改了字段长度。虽然源端和目标端的长度已经通过DDL语句修改到一致，在extract进程未重启的情况下，生成的trail文…...

编程日记 2025/7/14 12:36:36

XML标签格式转换为YOLO TXT格式

针对的是多边形（<polygon>）来描述对象的边界，而不是传统的矩形框（<bndbox>） import xml.etree.ElementTree as ET import os from pathlib import Path# 解析VOC格式的XML文件，提取目标框的标…...

编程日记 2025/7/14 20:59:57

Java的string默认值

在Java中，String类型的默认值取决于其定义和实例化的方式。以下是关于String默认值的详细说明未实例化的String变量‌ 如果定义一个String变量但未对其进行实例化（即未使用new关键字或直接赋值），其默认值为:ml-search[null]。这…...

编程日记 2025/7/14 20:58:00

侯捷 C++ 课程学习笔记：C++ 中引用与指针的深度剖析

目录一、引言二、引用与指针的基本概念 （一）引用 （二）指针三、引用与指针的区别 （一）定义与初始化 （二）内存空间与 NULL 值 （三）自增操作 …...

编程日记 2025/7/14 20:49:50

llamafactory微调效果与vllm部署效果不一致如何解决

在llamafactory框架训练好模型之后，自测chat时模型效果不错，但是部署到vllm模型上效果却很差这实际上是因为llamafactory微调时与vllm部署时的对话模板不一致导致的。对应的llamafactory的代码为而vllm启动时会采用大模型自己本身设置的对话模板信息…...

编程日记 2025/7/14 20:59:01

欢乐力扣：合并两个有序链表

文章目录 1、题目描述2、思路 1、题目描述合并两个有序链表。将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。在这里插入图片描述 2、思路参考官方题解，简单来说就是不断调整链表指针的指向，让…...

编程日记 2025/7/14 20:56:24

访问者模式_行为型_GOF23

访问者模式访问者模式（Visitor Pattern）是一种行为型设计模式，核心思想是将算法与对象结构分离，使得在不修改现有对象结构的前提下，可以动态添加新的操作。这类似于“医生查房”——医生（访问者&#xff…...

编程日记 2025/7/14 20:48:05

排序算法2-选择排序

目录 1.常见排序算法 2.排序算法的预定函数 2.1交换函数 2.2测试算法运行时间的函数 2.3已经实现过的排序算法 3.选择排序算法的实现 3.1直接选择排序 3.2堆排序 4.下讲预告 1.常见排序算法前面一讲已经讲解了插入排序，这一讲我将讲解选择排序，…...

编程日记 2025/7/14 20:57:59

openwrt24.10.0版本上安装istoreOS的屏幕监控插件

lcdsimple 插件支持在软路由下面显示统计信息到 HDMI 或者 VGA 上。手动安装方法： 保证 quickstart 版本大于 0.9.7 安装 lcdsimple 具体方法： opkg update is-opkg install quickstart opkg install lcdsimple 手动下载 QUICKSTART 跟 LCD SIMPL…...

编程日记 2025/7/14 20:51:30

内网服务器无法通过公网地址访问映射到公网的内网服务

内网服务器无法通过公网地址访问映射到公网的内网服务问题现象问题原因解决方法总结前几天遇到一个网络问题，在这里做下记录，希望能帮助到有相同问题的朋友。问题现象网络拓扑如上所示，服务器1和服务器2在同一内网，网段均为1…...

编程日记 2025/7/14 20:43:06

基于Web的交互式智能成绩管理系统设计

目录摘要绪论一、应用背景二、行业发展现状三、程序开发的重要意义四、结语 1 代码 2 数据初始化模块 3 界面布局模块 4 核心功能模块 5 可视化子系统 6 扩展功能模块 7 架构设计亮点功能总结一、核心数据管理二、智能分析体系三、可视化系统四、扩…...

编程日记 2025/7/14 20:55:33

从虚拟现实到可持续设计：唐婉歆的多维创新之旅

随着线上线下融合逐渐成为全球家居与建材行业的发展趋势,全球市场对高品质、个性化家居和建材产品的需求稳步攀升,也对设计师提出更高的要求。在这一背景下,设计师唐婉歆将以产品设计师的身份,正式加入跨国企业AmCan 美加集团,投身于备受行业瞩目的系列设计项目。她将负责Showr…...

编程日记 2025/7/14 20:57:14

PHP MySQL 预处理语句

PHP MySQL 预处理语句引言在PHP中与MySQL数据库进行交互时，预处理语句是一种非常安全和高效的方法。预处理语句不仅可以防止SQL注入攻击，还可以提高数据库查询的效率。本文将详细介绍PHP中预处理语句的用法，包括其基本概念、语法、优势以及在实际开发中的应用。预处理…...

编程日记 2025/7/14 20:49:50

基于飞腾/龙芯+盛科CTC7132全国产交换机解决方案

产品介绍盛科CTC7132,内置ARM-Cortex A53 主频1.2GHz；支持24个千兆电口，24个万兆光口（850nm多模），1个千兆管理网口，1个管理串口；支持1个百兆健康管理网口：用于设备端口状态、电压、…...

编程日记 2025/7/14 20:52:31

Vue动态添加或删除DOM元素：购物车实例

Vue 指令系列文章：《Vue插值：双大括号标签、v-text、v-html、v-bind 指令》《Vue指令：v-cloak、v-once、v-pre 指令》《Vue条件判断：v-if、v-else、v-else-if、v-show 指令》《Vue循环遍历：v-for 指令》《Vue事件处理：v-on 指令》《Vue表单元素绑定：v-model 指令》…...

编程日记 2025/7/14 20:59:57

深入理解Agentic Workflows

本文来源：https://weaviate.io/blog/what-are-agentic-workflows 这篇文章将带你深入理解AI Agent、Agentic AI、Agentic Workflows、Agentic Architectures等概念，非常值得推荐。一、什么是 AI Agents？ AI Agents 是结合了大模型进行推理和…...

编程日记 2025/7/11 10:48:31

深入理解：阻塞IO、非阻塞IO、水平触发与边缘触发

深入理解：阻塞IO、非阻塞IO、水平触发与边缘触发在网络编程和并发处理中，理解不同的 I/O 模型和事件通知机制至关重要。本文将深入探讨阻塞IO（Blocking IO）、非阻塞IO（Non-Blocking IO）、水平触发&#x…...

编程日记 2025/7/12 10:59:45

deepseek 技术的前生今世：从开源先锋到AGI探索者

一、引言：中国AI领域的“超越追赶”样本 DeepSeek（深度求索）作为中国人工智能领域的代表性企业，自2023年创立以来，凭借开源生态、低成本技术路径与多模态创新，迅速从行业新秀成长为全球AI竞赛中的关键力量…...

编程日记 2025/7/8 2:01:47

合规+增效正也科技携智能营销产品出席中睿论坛

正也科技作为医药数字化领域的标杆企业，受邀参展第二届中睿医健产业企业家年会暨第十三届中睿医药新春论坛，本次论坛以“合力启新程”为主题，吸引了800多位医药健康企业的董事长、总经理参与，并通过主论坛、分论坛、路演等形式探讨…...

编程日记 2025/6/30 12:27:42

Python小练习系列 Vol.5：数独求解（经典回溯 + 剪枝）

🧠 Python小练习系列 Vol.5：数独求解（经典回溯剪枝） 🧩 数独不仅是益智游戏，更是回溯算法的典范！本期我们将用 DFS 剪枝的方式一步步求解一个标准 9x9 数独。 🧩 一、题目描述 …...

编程日记 2025/7/9 14:26:10

基于kafka的分布式日志收集平台项目（续）

#第一个容易错的地方上次做到测试集群的创建topic时出现了错误具体错误是配置信息出错了，然后报错如下： #现在来具体警戒哪些地方要特别注意： ### node.id 和listeners 和advertised.listeners这三行是每一台机器（每个节点&…...

编程日记 2025/7/7 20:28:20

C++运算符重载、类的转换构造函数和类型转换函数的基础练习

练习1：（困难） 建立一个矩阵类，可以完成指定的操作或运算。说明： （1）、矩阵为2行3列，基类型为整型； （2）、操作或运算：初始化&…...

编程日记 2025/7/10 16:05:55

第一天 Linux驱动程序简介

目录一、驱动的作用二、裸机驱动 VS linux驱动 1、裸机驱动 2、linux驱动三、linux驱动位于哪里？ 四、应用编程 VS 内核编程 1、共同点 2、不同点五、linux驱动分类 1、字符设备 2、块设备 3、网络设备六、Linux驱动学习难点与误区 1、学习难点 …...

编程日记 2025/7/11 15:03:04

408 计算机网络知识点记忆（1）

前言本文基于王道考研课程与湖科大计算机网络课程教学内容，系统梳理核心知识记忆点和框架，既为个人复习沉淀思考，亦希望能与同行者互助共进。（PS：后续将持续迭代优化细节） 核心知识记忆点计算机网络&a…...

编程日记 2025/7/10 4:48:47

scala简介和基础语法

Scala简介 Scala 是一门多范式（multi-paradigm）的编程语言，设计初衷是要集成面向对象编程和函数式编程的各种特性。 Scala 运行在 Java 虚拟机上，并兼容现有的 Java 程序。Scala 源代码被编译成 Java 字节码，所以它可…...

编程日记 2025/7/10 19:22:19

[特殊字符] Hyperlane：Rust 高性能 Web 框架的终极选择 [特殊字符]

🔥 Hyperlane：Rust高性能Web框架的终极选择 🔥 📈 性能封神：32万QPS碾压群雄在1000并发压测中，Hyperlane以307,568.90 req/s的恐怖QPS稳居Rust生态第一，甚至超越Tokio框架！开启Kee…...

编程日记 2025/7/14 18:06:43

树莓派超全系列文档--(13)如何使用raspi-config工具其二

如何使用raspi-config工具其二 raspi-configPerformance optionsOverclockGPU memoryOverlay file systemFan Localisation optionsLocaleTime zoneKeyboardWLAN country Advanced optionsExpand filesystemNetwork interface namesNetwork proxy settingsBoot orderBootloader…...

编程日记 2025/7/14 11:22:09