初阶数据结构 - 【单链表】
目录
前言:
1.概念
链表定义
结点结构体定义
结点的创建
2.链表的头插法
动画演示
代码实现
3.链表的尾插
动画演示
代码实现
4.链表的头删
动画演示
代码实现
5.链表的尾删
动画演示
代码实现
6.链表从中间插入结点
动画演示
代码实现
7.从单链表中删除任意结点
动画演示
代码实现
8.销毁链表
动画演示
代码实现
完整代码
前言:
前面我们已经把顺序表的优点和缺点讲了,那么这篇文章就是单链表的这种数据结构的实现和理解。
1.概念
链表定义

链表是一种离散存储的数据结构,它只有一个指针域,下一个指针保存着前一个数据的地址;像链子一样串起来的结构就叫做单链表。
n个节点离散分配, 彼此通过指针相连每个节点只有一个前驱节点,每个节点只有一个后续节点。首节点没有前驱节点,尾节点没有后续节点。
结点结构体定义
struct ListNode {DataType data; //数据域struct ListNode*next; //指针域
}ListNode;
结点的创建
为链表创建新结点并分配内存,把传进来的值赋给data, next置为空指针,并返回新结点。
ListNode *ListCreateNode(DataType data) {ListNode *node = (ListNode *) malloc ( sizeof(ListNode) );if (node == NULL){perror("malloc");exit(-1);}node->data = data;node->next = NULL;return node;
}
2.链表的头插法
动画演示
链表的头插有两种情况 : 1.如果链表为空 ,执行头部插入 2.链表不为空,需要找到链表的头再进行插入
情况 1的处理
当前是空链表,插入之后成为头结点。
情况 2
当前链表不为空,则需要找到当前头结点,让新结点指向头结点;头结点再指向新结点。
代码实现
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}
3.链表的尾插
动画演示
代码实现
1. 如果当前链表为空 ,那么尾插 等于 头插
2. 如果当前链表不为空,则需要找到最后一个结点,让最后一个结点的指针指向新结点,新结点再指向尾结点、
void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{// 找尾节点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
4.链表的头删
函数接口
void SListPopFront(SLTNode** pphead)
动画演示
代码实现
1.如果当前链表是空的,不用删
2. 如果当前链表还有结点,则继续删。
void SListPopFront(SLTNode** pphead)
{assert(*pphead != NULL);//if (*pphead == NULL)// return;SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
5.链表的尾删
函数接口:
void SListPopBack(SLTNode** pphead)
动画演示
代码实现
1. 链表内只有一个结点的情况,将当前结点的指针置为NULL,再释放当前结点。最后置空
2.如果链表内有多个结点存在,则需要遍历链表找到尾结点,然后释放尾结点;最后将指针置为NULL,防止空指针异常。
void SListPopBack(SLTNode** pphead)
{assert(*pphead);// 1、只有一个节点// 2、多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{/*SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;*/SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}
6.链表从中间插入结点
在第 i 个结点后面插入一个数据,数据值为 v
规则说明:
Head 为链表头,并且头结点内有数据
i >= 0
动画演示
代码实现
先分析情况
1.如果当前链表为空,则链表不需要删除。
2.如果链表不为空,则需要让新结点指向要插入的结点,再让前一个结点指向新结点。
ListNode *ListInsertNode(ListNode *head, int i, DataType v) {ListNode *pre, *aft, *vtx; // (1) 插入完毕后, pre -> vtx -> aft int j = 0; // (2) 定义一个计数器,当 j == i 时,表明找到要插入的位置 pre = head; // (3) 从链表头开始while(pre && j < i) { // (4) 如果还没有到链表尾,或者没有找到插入位置则继续循环 pre = pre->next; // (5) 游标指针指向它的后继结点 ++j; // (6) 计数器加 1 }if(!pre) { return NULL; // (7) 元素个数不足,无法找到给定位置,返回 NULL }vtx = ListCreateNode(v); // (8) 创建一个值为 v 的鼓孤立结点 aft = pre->next; // (9) - (11) 为了串成 pre -> vtx -> aft vtx->next = aft; // (10)pre->next = vtx; // (11)return vtx; // (12) 返回插入的那个结点
}
7.从单链表中删除任意结点
删除任意结点跟任意位置插入结点的思路是一致的,只是反着来。
动画演示
代码实现
分情况讨论
1.如果当前链表为空,不需要删除
2.不为空,先找到要删除结点的前一个结点,让前一个结点指向要删除的结点的后一个结点,然后释放要删除结点的内存,再让后一个结点的指针指向前一个结点.
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SListPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
8.销毁链表
函数接口:
void ListDestroyList(ListNode **pHead)
动画演示
代码实现
1.链表为空,不删除。
2.链表不为空,遍历链表释放结点,最后指针置空。
void ListDestroyList(ListNode **pHead) { // (1) 这里必须用二级指针,因为删除后需要将链表头置空,普通传参无法影响外部变量; ListNode *head = *pHead; // (2) 给链表头解引用; while(head) { // (3) 如果链表非空,则继续循环; head = ListDeleteNode(head, 0); // (4) 产出链表头部,并且返回 后继结点; ListPrint(head);}*pHead = NULL; // (5) 将链表头置空
}
完整代码
#include "SList.h"void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{// 找尾节点SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SListPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);// 1、只有一个节点// 2、多个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{/*SLTNode* tailPrev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){tailPrev = tail;tail = tail->next;}free(tail);tailPrev->next = NULL;*/SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}void SListPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead != NULL);//if (*pphead == NULL)// return;SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pos);assert(pphead);// 头插if (pos == *pphead){SListPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}
}// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SListPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}// 单链表在pos位置之后插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);/*SLTNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;*/// 不在乎链接顺序SLTNode* newnode = BuySListNode(x);SLTNode* next = pos->next;// pos newnode nextpos->next = newnode;newnode->next = next;
}// 分析思考为什么不删除pos位置?
void SListEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL)return;SLTNode* del = pos->next;//pos->next = pos->next->next;pos->next = del->next;free(del);del = NULL;
}
相关文章:

初阶数据结构 - 【单链表】
目录 前言: 1.概念 链表定义 结点结构体定义 结点的创建 2.链表的头插法 动画演示 代码实现 3.链表的尾插 动画演示 代码实现 4.链表的头删 动画演示 代码实现 5.链表的尾删 动画演示 代码实现 6.链表从中间插入结点 动画演示 代码实现 7.从单…...

第五周作业、第一次作业(1.5个小时)、练习一
一、创建servlet的过程没有太多好说的,唯一需要注意的就是:旧版本的servlet确实需要手动配置web.xml文件,但是servlet2.5以后,servlet的配置直接在Java代码中进行注解配置。我用的版本就不再需要手动去配置web.xml文件了,所以我只…...

【正点原子FPGA连载】 第三十三章基于lwip的tftp server实验 摘自【正点原子】DFZU2EG_4EV MPSoC之嵌入式Vitis开发指南
第三十三章基于lwip的tftp server实验 文件传输是网络环境中的一项基本应用,其作用是将一台电子设备中的文件传输到另一台可能相距很远的电子设备中。TFTP作为TCP/IP协议族中的一个用来在客户机与服务器之间进行文件传输的协议,常用于无盘工作站、路由器…...
蓝桥冲刺31天之316
如果生活突然向你发难 躲不过那就迎面而战 所谓无坚不摧 是能享受最好的,也能承受最坏的 大不了逢山开路,遇水搭桥 若你决定灿烂,山无遮,海无拦 A:特殊日期 问题描述 对于一个日期,我们可以计算出年份的各个…...

说一个通俗易懂的PLC工程师岗位要求
你到了一家新的单位,人家接了一套新的设备,在了解设备工艺流程之后,你就能决定用什么电气元件,至少95%以上电气原件不论你用过没用过都有把握拍板使用,剩下5%,3%你可以先买来做实验,这次不能用&…...
今年还能学java么?
“Java很卷”、“大家不要再卷Java了”,经常听到同学这样抱怨。但同时,Java的高薪也在吸引越来越多的同学。不少同学开始疑惑:既然Java这么卷,还值得我入行吗? 首先先给你吃一颗定心丸:现在选择Java依然有…...
ajax学习1
不刷新页面的情况下,向服务端发送请求,异步的js和XMLajax不是新的编程语言,只是把现有标准组合到一起使用的新方式...
一题多解-八数码(万字长文)
16 张炜皓 (ζ͡顾念̶) LV 5 1 周前 在做这道题前,先来认识一下deque双端队列 C STL 中的双端队列 题目连接 使用前需要先引入 头文件。 #include; STL 中对 deque 的定义 // clang-format off template< class T, class Allocator std::allocator class d…...

九种跨域方式实现原理(完整版)
前言 前后端数据交互经常会碰到请求跨域,什么是跨域,以及有哪几种跨域方式,这是本文要探讨的内容。 一、什么是跨域? 1.什么是同源策略及其限制内容? 同源策略是一种约定,它是浏览器最核心也最基本的安…...

fighting
目录Mysqlgroup by和 distinct哪个性能好java觉得Optional类怎么样isEmpty和isBlank的用法区别使用大对象时需要注意什么内存溢出和内存泄漏的区别及详解SpringResource和Autowired的起源既生“Resource”,何生“Autowired”使用Autowired时为什么Idea会曝出黄色警告…...
网络安全日志监控管理
内部安全的重要性 无论大小,每个拥有IT基础设施的组织都容易发生内部安全攻击。您的损失等同于黑客的收益:访问机密数据、滥用检索到的信息、系统崩溃,以及其他等等。专注于网络外部的入侵是明智的,但同时,内部安全也…...

线程池的使用:如何写出高效的多线程程序?
目录1.线程池的使用2.编写高效的多线程程序Java提供了Executor框架来支持线程池的实现,通过Executor框架,可以快速地创建和管理线程池,从而更加方便地编写多线程程序。 1.线程池的使用 在使用线程池时,需要注意以下几点ÿ…...

React 架构流程概览
React 架构流程概览 文章目录React 架构流程概览启动React项目流程分析各部分解析调度器协调器渲染器总结启动React项目 启动项目,并打开 Performance 面板 流程分析 首先找到入口函数 整个 render 下面的调用栈就是首屏渲染要执行的流程。 render 过程大致分为…...

【Linux】进程管理之kill、killall、pkill
一、kill 命令 Linux 中的 kill 命令用来终止指定的进程的运行,是 Linux 下进程管理的常用命令。通常,终止一个前台进程可以使用 CtrlC 键,但是,对于一个后台进程就须用 kill 命令来终止,那就需要先使用 ps、pidof、ps…...

LSTM从入门到精通(形象的图解,详细的代码和注释,完美的数学推导过程)
先附上这篇文章的一个思维导图什么是RNN按照八股文来说:RNN实际上就是一个带有记忆的时间序列的预测模型RNN的细胞结构图如下:softmax激活函数只是我举的一个例子,实际上得到y<t>也可以通过其他的激活函数得到其中a<t-1>代表t-1时…...

19.特殊工具与技术
文章目录特殊工具与技术19.1控制内存分配19.1.1重载new和deleteoperator new接口和operator delete接口malloc函数与free函数19.1.2定位new表达式显式的析构函数调用19.2运行时类型识别(run-time type identification, RTTI)19.2.1dynamic_cast运算符指针类型的dynamic_cast引用…...

518. 零钱兑换 II ——【Leetcode每日一题】
518. 零钱兑换 II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 3…...
django DRF请求访问频率限制
Django REST framework(DRF)提供了一个throttle_classes属性,可以用于限制API的访问频率。它可以防止恶意用户发送大量请求以消耗服务器资源。使用throttle_classes属性,需要在settings.py中配置REST_FRAMEWORK:REST_F…...
二分查找创新性总结
LeetCode题目 704.二分查找35.搜索插入位置69.x 的平方根367.有效的完全平方数34.在排序数组中查找元素的第一个和最后一个位置 二分查找适用范围 可随机访问的数据结构数据已经有序要查找的值只有一个 上述的前四题都可直接使用二分查找,第五题要求查找上限和下限&…...

Java Web 实战 13 - 多线程进阶之 synchronized 原理以及 JUC 问题
文章目录一 . synchronized 原理1.1 synchronized 使用的锁策略1.2 synchronized 是怎样自适应的? (锁膨胀 / 升级 的过程)1.3 synchronized 其他的优化操作锁消除锁粗化1.4 常见面试题二 . JUC (java.util.concurrent)2.1 Callable 接口2.2 ReentrantLock2.3 原子类2.4 线程池…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...

C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...

Unity UGUI Button事件流程
场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...

五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...