【数据结构】链表篇
文章目录
- 1.链表的概念以及结构
- 2.链表的分类
- 2.1 单向或者双向
- 2.2 带头或者不带头
- 2.3 循环或者不循环
- 2.4 无头单向非循环链表和带头双向循环链表
- 3.单链表的实现
- 3.1 准备工作
- 3.2 节点的创建
- 3.3 单链表的释放
- 3.4 打印链表
- 3.5 单链表的尾插
- 3.6 单链表的尾删
- 3.7 单链表头删
- 3.8 单链表的头插
- 3.9 单链表的查找
- 3.10 在pos位置后插入
- 3.11 删除pos位置后的数据
- 4.代码整合
- 5.顺序表与链表的区别
1.链表的概念以及结构
概念:链表是一种物理储存结构上的非连续、非顺序的储存结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
- 链式结构在逻辑上是连续的,但是在物理上不一定连续
- 现实中的节点一般都是从堆上申请出来的
- 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
2.链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表。
2.1 单向或者双向
2.2 带头或者不带头
2.3 循环或者不循环
2.4 无头单向非循环链表和带头双向循环链表
虽然有这么多的链表结构,但是我们实际中最常用的还是两种结构。
无头单向非循环链表
带头双向循环链表
- 无头单向非循环链表:结构简单,一般不会单独用来存储数据,实际中更多的是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外在笔试中出现较多
- 带头双向循环链表:结构最复杂,一般用来单独存储数据。实际中使用的链表结构都是带头双向循环链表。另外这个结构虽然复杂,但是使用代码实现时反而简单。
3.单链表的实现
3.1 准备工作
定义结构体.
链表的节点只要两个值需要存储,一个是数据内容,一个是下一个节点的地址。
注意:为了更多的使用场景,我们可以定义一个宏去去替换数据类型。为了方便我就直接写int的。
typedef struct SListNode
{int data;struct SListNode* next;
}SL;
3.2 节点的创建
正常利用malloc创建就好,注意要检查内存是否开辟失败。
//动态申请一个节点
SL* BuySListNode(int x)
{SL* tmp = (SL*)malloc(sizeof(SL));if (tmp == NULL){perror("malloc");exit(-1);}tmp->data = x;tmp->next = NULL;return tmp;
}
3.3 单链表的释放
注意使用二级指针,因为我们传递的是一级指针的地址
SL* head = NULL;
DestoryList(&head);
释放时,为了释放当前节点,我们要在cur指向下一个节点时先保存一下该节点的地址。
//释放
void DestoryList(SL** head)
{SL* cur = (*head);while (cur){SL* prev = cur;cur = cur->next;free(prev);prev = NULL;}
}
3.4 打印链表
遍历打印就可以了,assert的目的是为了防止有人把空指针传进来。
//打印链表
void PrintList(SL** head)
{assert(head);//assert(*head);SL* cur = *head;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
3.5 单链表的尾插
尾插有两种情况:
1.*head为空
直接让*head指向一个新的节点
2.*head不为空
找到当前链表的最后一个节点,然后将新创建的节点连接到后面
//单链表尾插
void PushBackList(SL** head,int x)
{assert(head);//防止有人把空指针传进来。if (*head == NULL){*head = BuySListNode(x);return;}SL* cur = *head;SL* tmp = BuySListNode(x);while (cur->next){cur = cur->next;}cur->next = tmp;
}
3.6 单链表的尾删
删除存在三种情况:
1.只有一个节点了
直接free释放,*head要置为NULL
2.不止一个节点
先找到第二个节点,然后释放第一个节点,将*head指向新的第一个节点。
3.没有节点
直接报错
//单链表尾删
void PopbackList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur = *head;if (cur->next == NULL)//当剩下1个元素时,直接释放{free(cur);*head = NULL;return;}SL* prev = cur;while (cur->next){prev = cur;cur = cur->next;}free(cur);cur = NULL;prev->next = NULL;
}
3.7 单链表头删
删除存在三种情况:
1.只有一个节点了
直接free释放,*head要置为NULL
2.不止一个节点
找到最后一个节点和其前一个节点,找倒数第二个节点的目的是为了将next置为NULL
3.没有节点
直接报错
//单链表头删
void PopFrontList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur = *head;if (cur->next == NULL)//当剩下1个元素时,直接释放{free(cur);*head = NULL;return;}SL* next = cur->next;free(cur);cur = NULL;*head = next;
}
3.8 单链表的头插
头插有两种情况:
1.*head为空
直接让*head指向一个新的节点
2.*head不为空
创建一个新的节点,找到当前链表的第一个节点,然后将新创建的节点的next指针指向第一个节点。然后让*head指向新的节点
//单链表头插
void PushFrontList(SL** head, int x)
{assert(head);if (*head == NULL){*head = BuySListNode(x);return;}SL* newnode = BuySListNode(x);newnode->next = *head;*head = newnode;
}
3.9 单链表的查找
找到返回节点,找不到返回NULL
//单链表的查找
SL* FindSlistNode(SL** head, int x)
{assert(head);assert(*head);SL* cur = *head;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
3.10 在pos位置后插入
既然要在pos节点后插入数据,那就要保证链表不为NULL,pos不为NULL
插入的逻辑就是尾插的逻辑,但是这里我们不在需要找节点位置了,已经给出pos节点了。
//在pos位置后插入
void InsertList(SL** head, SL* pos, int x)
{assert(head);assert(*head);assert(pos);SL* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}
3.11 删除pos位置后的数据
注意两种情况就行了。
//删除pos位置后的节点
void EraseList(SL** head, SL* pos)
{assert(pos);assert(head);assert(*head);if (pos->next == NULL)return;else{SL* next = pos->next->next;SL* tmp = pos->next;pos->next = next;free(tmp);tmp = NULL;}
}
4.代码整合
//list.h
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <assert.h>typedef struct SListNode
{int data;struct SListNode* next;
}SL;//动态申请一个节点
SL* BuySListNode(int x);//销毁链表
void DestoryList(SL** head);//打印链表
void PrintList(SL** head);//单链表尾插
void PushBackList(SL** head, int x);//单链表尾删
void PopbackList(SL** head);//单链表头删
void PopFrontList(SL** head);//单链表头插
void PushFrontList(SL** head, int x);//单链表的查找
SL* FindSlistNode(SL** head, int x);//在pos位置后插入
void InsertList(SL** head, SL* pos, int x);//删除pos位置后的节点
void EraseList(SL** head, SL* pos);//list.c
#include "list.h"SL* BuySListNode(int x)
{SL* tmp = (SL*)malloc(sizeof(SL));if (tmp == NULL){perror("malloc");exit(-1);}tmp->data = x;tmp->next = NULL;return tmp;
}void DestoryList(SL** head)
{SL* cur = (*head);while (cur){SL* prev = cur;cur = cur->next;free(prev);}}//打印链表
void PrintList(SL** head)
{//assert(*head);SL* cur = *head;while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}//单链表尾插
void PushBackList(SL** head,int x)
{if (*head == NULL){*head = BuySListNode(x);return;}SL* cur = *head;SL* tmp = BuySListNode(x);while (cur->next){cur = cur->next;}cur->next = tmp;
}//单链表尾删
void PopbackList(SL** head)
{assert(*head);SL* cur = *head;if (cur->next == NULL)//当剩下1个元素时,直接释放{free(cur);cur = NULL;*head = NULL;return;}SL* prev = cur;while (cur->next){prev = cur;cur = cur->next;}free(cur);cur = NULL;prev->next = NULL;
}//单链表头删
void PopFrontList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur = *head;if (cur->next == NULL)//当剩下1个元素时,直接释放{free(cur);cur = NULL;*head = NULL;return;}SL* next = cur->next;free(cur);cur = NULL;*head = next;
}//单链表头插
void PushFrontList(SL** head, int x)
{assert(head);if (*head == NULL){*head = BuySListNode(x);return;}SL* newnode = BuySListNode(x);newnode->next = *head;*head = newnode;
}//单链表的查找
SL* FindSlistNode(SL** head, int x)
{assert(*head);SL* cur = *head;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}//在pos位置后插入
void InsertList(SL** head, SL* pos, int x)
{assert(pos);SL* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}//删除pos位置后的节点
void EraseList(SL** head, SL* pos)
{assert(pos);assert(head);assert(*head);if (pos->next == NULL)return;else{SL* next = pos->next->next;SL* tmp = pos->next;pos->next = next;free(tmp);tmp = NULL;}
}//test.c
#include "list.h"//void test1()
//{
// SL* head = BuySListNode(1);
// PushBackList(&head, 2);
// PushBackList(&head, 3);
// PushBackList(&head, 4);
// PopFrontList(&head);
// PrintList(&head);
// PopFrontList(&head);
// PrintList(&head);
// PopFrontList(&head);
// PrintList(&head);
// PopFrontList(&head);
// PrintList(&head);
// DestoryList(&head);
//}
//
//void test2()
//{
// SL* head = BuySListNode(1);
// PushFrontList(&head, 4);
// PushFrontList(&head, 2);
//
// SL* tmp = FindSlistNode(&head, 1);
// printf("tmp:%d\n", tmp->data);
//
// tmp = FindSlistNode(&head, 100);
// if(tmp!=NULL)
// printf("tmp:%d\n", tmp->data);
// DestoryList(&head);
//
//}
//
//void test3()
//{
// SL* head = NULL;
// PushFrontList(&head, 4);
// PushFrontList(&head, 2);
// PushBackList(&head, 1);
// PushBackList(&head, 1);
// PushBackList(&head, 1);
// SL* tmp = FindSlistNode(&head, 2);
// InsertList(&head, tmp, 100);
// EraseList(&head, tmp);
// PrintList(&head);
// DestoryList(&head);
//
//}int main()
{test3();return 0;
}
5.顺序表与链表的区别
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定 连续 |
随机访问 | 支持O(1) | 不支持:O(N) |
任意位置插入或者删除 元素 | 可能需要搬移元素,效率低 O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要 扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率 | 高 | 低 |
相关文章:

【数据结构】链表篇
文章目录 1.链表的概念以及结构2.链表的分类2.1 单向或者双向2.2 带头或者不带头2.3 循环或者不循环2.4 无头单向非循环链表和带头双向循环链表 3.单链表的实现3.1 准备工作3.2 节点的创建3.3 单链表的释放3.4 打印链表3.5 单链表的尾插3.6 单链表的尾删3.7 单链表头删3.8 单链…...
Python SciPy介绍
在数据科学和工程领域,Python已经成为了一个不可或缺的工具,这主要得益于其强大的库和框架支持。其中,SciPy库作为Python科学计算的核心库之一,为研究人员、工程师和数据分析师提供了大量高效的算法和数学工具。本文将带您深入了解…...
docker镜像源
1、直接在服务器上创建这个文件,将镜像源配置在里面 /etc/docker/daemon.json {"registry-mirrors": ["https://do.nark.eu.org","https://dc.j8.work","https://docker.m.daocloud.io","https://dockerproxy.com&qu…...

【clion】clion打开文件目录卡死问题
巨卡,几乎无法打开,据说是fsnotifier64.exe 被限制了。删除 火绒就好了。 关闭windows defender 官方:关闭 Windows 安全中心中的Defender 防病毒保护 此时,删除火绒: 界面变这样了:...
[CR]厚云填补_GridFormer
GridFormer: Residual Dense Transformer with Grid Structure for Image Restoration in Adverse Weather Conditions Abstract 恶劣天气条件下的图像恢复是计算机视觉中的一个难点。在本文中,我们提出了一种新的基于变压器的框架GridFormer,它可以作为…...
PostgreSQL数据库内核(二):通过initdb传递guc参数
目录 增加guc参数 initdb参数传递 pg_ctl参数传递 参数验证 新增guc参数pg_test_parameter,支持从initdb和pg_ctl命令中传递/覆盖参数,使用场景是TDE透明加密指定算法或者某些定制化需求。 增加guc参数 pg源码是这样描述guc参数的:它是全局…...
rust常用的宏使用记录(九)
matches! 宏使用 matches! 是 Rust 标准库中一个非常有用的宏,它允许你方便地匹配一个表达式的结果是否符合某个模式。它的基本用法如下:matches!(expression, pattern) 这个宏返回一个布尔值,如果 expression 匹配 pattern,则返回…...

【Python机器学习】支持向量机——手写数字识别问题
基于SVM的数字识别步骤: 1、收集数据:提供的文本文件 2、准备数据:基于二值图像构造向量 3、分析数据:对图像向量进行目测 4、训练算法:采用两种不同的核函数,并对径向基核函数采用不同的设置来运行SMO算法…...

学习笔记-Cookie、Session、JWT
目录 一、验证码的生成与校验 1. 创建生成验证码的工具类 2. 写一个 Controller 3. 实现验证码验证 1. 获取验证码 2. 验证码请求过程 3. 验证码的校验 4. 原理说明 5. 验证 6. 总结 二、JWT登录鉴权 1. 为什么要做登录鉴权? 2. 什么是 JWT 3. JWT相比…...

题海战术,面试必胜秘诀
目录 1.Java 的优势是什么?2.什么是 Java 的多态特性?3.Java 中的参数传递是按值还是按引用?4.为什么 Java 不支持多重继承?5.什么是 Java 中的不可变类?总结 题目 来自面试鸭刷题神器 1.Java 的优势是什么? Java 的跨平台性、垃圾回收机制以及其强…...
设计模式详解(十九)——命令模式
命令模式简介 命令模式定义 命令模式(Command Pattern)是一种在面向对象程序设计中常用的行为型设计模式。命令模式的核心思想在于将请求封装成一个对象,从而使发出请求的责任和执行请求的责任分割开。它可以让请求发送者和请求接收者之间消…...

实战:MySQL数据同步神器之Canal
1.概叙 场景一:数据增量实时同步 项目中业务数据量比较大,每类业务表都达到千万级别,虽然做了分库分表,每张表数据控制在300W以下,但是效率还是达不到要求,为了提高查询效率,打算使用ES进行数…...
5.6软件工程-运维
运维 系统转换系统维护系统评价练习题 系统转换 新老系统的转换 系统转换是指:新系统开发完毕,投入运行,取代现有系统的过程,需要考虑多方面的问题,以实现与老系统的交接,有一下三种转换计划: …...
在JavaScript中如何确保构造函数只被new调用
构造函数是一个特殊的函数,用于初始化一个新创建的对象。它是在创建对象时自动调用的。构造函数通常用于为对象的属性赋值,或者执行其他必要的设置。 使用函数名大写字母开头,这是一种命名约定,用于区分构造函数和普通函数。如何…...

【数据结构算法经典题目刨析(c语言)】反转链表(图文详解)
💓 博客主页:C-SDN花园GGbond ⏩ 文章专栏:数据结构经典题目刨析(c语言) 目录 一、题目描述 二、思路分析 三、代码实现 一、题目描述: 二、思路分析 : 通过三个指针n1,n2,n3来实现链表的反转 1.首先初始化 n1为…...

机器学习之争:Python vs R,谁更胜一筹?
一、引言 随着人工智能和大数据的迅速发展,机器学习已成为现代科技的重要组成部分。在医疗、金融、零售、制造等多个领域,机器学习技术的应用无处不在。从数据分析到预测建模,再到深度学习,机器学习正在改变我们的工作和生活方式…...

Vulnhub靶机:JANGOW_ 1.0.1
目录 前言: 一、安装虚拟机Jangow:1.0.1靶机 二、Web部分 前言: 难度:简单,本文使用VirtualBox打开,下载地址: https://download.vulnhub.com/jangow/jangow-01-1.0.1.ova 一、安装虚拟机J…...
Python脚本实现USB自动复制文件
USB驱动器作为常见的数据存储设备,经常用于数据传输和备份。 然而,我们在手动处理文件复制可能效率低下且容易出错。 因此,我们可以利用Python编写脚本来自动化这一过程,提高效率和数据安全性。 准备工作 首先,我们需…...

【C++学习第19天】最小生成树(对应无向图)
一、最小生成树 二、代码 1、Prim算法 #include <cstring> #include <iostream> #include <algorithm>using namespace std;const int N 510, INF 0x3f3f3f3f;int n, m; int g[N][N]; int dist[N]; bool st[N];int prim() {memset(dist, 0x3f, sizeof di…...

第一个 Flask 项目
第一个 Flask 项目 安装环境创建项目启动程序访问项目参数说明Flask对象的初始化参数app.run()参数 应用程序配置参数使用 Flask 的 config.from_object() 方法使用 Flask 的 config.from_pyfile() 方法使用 Flask 的 config.from_envvar() 方法步骤 1: 设置环境变量步骤 2: 编…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...

iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...

群晖NAS如何在虚拟机创建飞牛NAS
套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...