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

初阶数据结构 - 【单链表】

目录

前言:

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;
}

 

相关文章:

初阶数据结构 - 【单链表】

目录 前言&#xff1a; 1.概念 链表定义 结点结构体定义 结点的创建 2.链表的头插法 动画演示 代码实现 3.链表的尾插 动画演示 代码实现 4.链表的头删 动画演示 代码实现 5.链表的尾删 动画演示 代码实现 6.链表从中间插入结点 动画演示 代码实现 7.从单…...

第五周作业、第一次作业(1.5个小时)、练习一

一、创建servlet的过程没有太多好说的&#xff0c;唯一需要注意的就是&#xff1a;旧版本的servlet确实需要手动配置web.xml文件&#xff0c;但是servlet2.5以后,servlet的配置直接在Java代码中进行注解配置。我用的版本就不再需要手动去配置web.xml文件了&#xff0c;所以我只…...

【正点原子FPGA连载】 第三十三章基于lwip的tftp server实验 摘自【正点原子】DFZU2EG_4EV MPSoC之嵌入式Vitis开发指南

第三十三章基于lwip的tftp server实验 文件传输是网络环境中的一项基本应用&#xff0c;其作用是将一台电子设备中的文件传输到另一台可能相距很远的电子设备中。TFTP作为TCP/IP协议族中的一个用来在客户机与服务器之间进行文件传输的协议&#xff0c;常用于无盘工作站、路由器…...

蓝桥冲刺31天之316

如果生活突然向你发难 躲不过那就迎面而战 所谓无坚不摧 是能享受最好的&#xff0c;也能承受最坏的 大不了逢山开路&#xff0c;遇水搭桥 若你决定灿烂&#xff0c;山无遮&#xff0c;海无拦 A&#xff1a;特殊日期 问题描述 对于一个日期&#xff0c;我们可以计算出年份的各个…...

说一个通俗易懂的PLC工程师岗位要求

你到了一家新的单位&#xff0c;人家接了一套新的设备&#xff0c;在了解设备工艺流程之后&#xff0c;你就能决定用什么电气元件&#xff0c;至少95%以上电气原件不论你用过没用过都有把握拍板使用&#xff0c;剩下5%&#xff0c;3%你可以先买来做实验&#xff0c;这次不能用&…...

今年还能学java么?

“Java很卷”、“大家不要再卷Java了”&#xff0c;经常听到同学这样抱怨。但同时&#xff0c;Java的高薪也在吸引越来越多的同学。不少同学开始疑惑&#xff1a;既然Java这么卷&#xff0c;还值得我入行吗&#xff1f; 首先先给你吃一颗定心丸&#xff1a;现在选择Java依然有…...

ajax学习1

不刷新页面的情况下&#xff0c;向服务端发送请求&#xff0c;异步的js和XMLajax不是新的编程语言&#xff0c;只是把现有标准组合到一起使用的新方式...

一题多解-八数码(万字长文)

16 张炜皓 (ζ͡顾念̶) LV 5 1 周前 在做这道题前&#xff0c;先来认识一下deque双端队列 C STL 中的双端队列 题目连接 使用前需要先引入 头文件。 #include; STL 中对 deque 的定义 // clang-format off template< class T, class Allocator std::allocator class d…...

九种跨域方式实现原理(完整版)

前言 前后端数据交互经常会碰到请求跨域&#xff0c;什么是跨域&#xff0c;以及有哪几种跨域方式&#xff0c;这是本文要探讨的内容。 一、什么是跨域&#xff1f; 1.什么是同源策略及其限制内容&#xff1f; 同源策略是一种约定&#xff0c;它是浏览器最核心也最基本的安…...

fighting

目录Mysqlgroup by和 distinct哪个性能好java觉得Optional类怎么样isEmpty和isBlank的用法区别使用大对象时需要注意什么内存溢出和内存泄漏的区别及详解SpringResource和Autowired的起源既生“Resource”&#xff0c;何生“Autowired”使用Autowired时为什么Idea会曝出黄色警告…...

网络安全日志监控管理

内部安全的重要性 无论大小&#xff0c;每个拥有IT基础设施的组织都容易发生内部安全攻击。您的损失等同于黑客的收益&#xff1a;访问机密数据、滥用检索到的信息、系统崩溃&#xff0c;以及其他等等。专注于网络外部的入侵是明智的&#xff0c;但同时&#xff0c;内部安全也…...

线程池的使用:如何写出高效的多线程程序?

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

React 架构流程概览

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

【Linux】进程管理之kill、killall、pkill

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

LSTM从入门到精通(形象的图解,详细的代码和注释,完美的数学推导过程)

先附上这篇文章的一个思维导图什么是RNN按照八股文来说&#xff1a;RNN实际上就是一个带有记忆的时间序列的预测模型RNN的细胞结构图如下&#xff1a;softmax激活函数只是我举的一个例子&#xff0c;实际上得到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 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 3…...

django DRF请求访问频率限制

Django REST framework&#xff08;DRF&#xff09;提供了一个throttle_classes属性&#xff0c;可以用于限制API的访问频率。它可以防止恶意用户发送大量请求以消耗服务器资源。使用throttle_classes属性&#xff0c;需要在settings.py中配置REST_FRAMEWORK&#xff1a;REST_F…...

二分查找创新性总结

LeetCode题目 704.二分查找35.搜索插入位置69.x 的平方根367.有效的完全平方数34.在排序数组中查找元素的第一个和最后一个位置 二分查找适用范围 可随机访问的数据结构数据已经有序要查找的值只有一个 上述的前四题都可直接使用二分查找&#xff0c;第五题要求查找上限和下限&…...

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 线程池…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...