单链表专题(上)
链表的定义与创建
线性表: 1. 物理结构上不一定是线性的
2. 逻辑结构上一定是线性的
链表是一种物理存储结构上非连续,非顺序的存储结构
链表也是线性表的一种,但是在物理结构上不是连续的
链表是由一个一个的节点组成,需要数据的时候只需要申请空间即可
节点包含两个组成部分: 1. 存储的数据
2. 指向下一个节点的指针
//节点的结构演示
struct SListNode //single list node
{int data;struct SListNode* next; //指向下一个节点的指针
}
下面我们将详细的进行链表节点的定义:
//定义节点的结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType; //由于数据不止 int 一种类型,所以统一用 SLTDataType 表示
typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;
这里我们将struct SListNode 统一改写成 SLTNode
接下来,我们来学习创建几个节点:
//创建四个节点
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node4->data = 4;
//将四个节点连接起来
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
由于创建的新节点的内存情况未知,所以使用 malloc 来动态分配内存。realloc 主要用于调整已分配内存块的大小
链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next; }printf("NULL\n");
}
但是我们一般不会像那样创建节点,而是给一个空链表去插入数据,所以下面是链表的尾插
链表的尾插
想找到进行尾插,要先找到尾节点,再将尾节点和新节点连接起来
注意: 我们在尾插头插等等时,都需要用到malloc创建新的空间,重复的书写会使代码显得冗长,所以我们封装一个函数专门用于开辟空间
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//判断空间是否开辟成功if (newnode == NULL){perror("malloc failed !");exit(1); //用非零的数表示非正常退出}newnode->data = x;newnode->next = NULL;return newnode;
}
有了创建控件函数后,我们开始写尾插代码:
void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = SLTBuyNode(x);//先找尾SLTNode* ptail = phead; while (ptail->next != NULL){ptail = ptail->next;}//此时ptail指向的就是尾节点ptail->next = newnode;
}
请注意,这里的原链表并不知道是否是空链表,若为空,则对空指针解引用是非法的。所以需要对两种情况进行讨论:
void SLTPushBack(SLTNode* phead, SLTDataType x)
{//空链表情况SLTNode* newnode = SLTBuyNode(x);if (phead == NULL){phead = newnode;}else{//非空链表情况//先找尾SLTNode* ptail = phead; while (ptail->next != NULL){ptail = ptail->next;}//此时ptail指向的就是尾节点ptail->next = newnode;}
}
这里用个很重大的问题,我们传入实参 plist ,而我们需要形参改变实参,plist虽然也是指针,但他存储着一个结构体的地址,我们现在就是要修改这个地址的相关内容,所以我们需要使用二级指针来传址调用
下面是一些对应关系:
第一个节点 | *plist | **pphead |
指向第一个节点的指针 | plist | *pphead |
指向第一个节点的指针的地址 | &plist | pphead |
//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//空链表情况SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL){*pphead = newnode;}else{//非空链表情况//先找尾SLTNode* ptail = *pphead; while (ptail->next != NULL){ptail = ptail->next;}//此时ptail指向的就是尾节点ptail->next = newnode;}
}
由于节点的地址的地址不能为空,所以再加入断言,尾插代码就写好了。
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead); //链表不能为空SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;
}
链表的头插(相对简单)
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
链表的尾删
思路为先找到尾节点,将尾节点释放掉,由于释放了尾节点后,尾节点的上一个节点依然指向尾节点,所以还需将上一个节点置零
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead); //链表不能为空SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;
}
当链表只有一个节点的时候,此时尾节点的上一个节点并不实际存在,所以需要单独讨论
void SLTPopBack(SLTNode** pphead)
{assert(pphead && *pphead); //链表不能为空//链表只有一个节点时if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//有多个节点时SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}
相关文章:
单链表专题(上)
链表的定义与创建 线性表: 1. 物理结构上不一定是线性的 2. 逻辑结构上一定是线性的 链表是一种物理存储结构上非连续,非顺序的存储结构 链表也是线性表的一种,但是在物理结构上不是连续的 链表是由一个一个的节点组成,需要数…...

【stm32学习】STM32F103相关特性
| 名称 | 缩写 | 频率 | 外部连接 | 功能 | 用途 | 特性 | |--------------------|------|----------------|---------------|------------|--------------|----------------| | 外部高速晶体振荡器 | HSE | 4~16MHz …...

PostGIS笔记:PostgreSQL中表、键和索引的基础操作
创建、查看与删除表 在数据库中创建一个表,使用如下代码: create table streets (id serial not null primary key, name varchar(50));这里的表名是streets,id是主键所以非空,采用serial数据类型,这个数据类型会自动…...

蓝桥杯python语言基础(3)——循环结构
一、for语句 理解range函数 range(start, stop, step) start: 序列开始的数字(默认为0)。stop: 序列结束的数字(不包含stop)。step: 步长(默认为1)。 练习 输出在 l 和 r 之间的所有偶数: pri…...

微服务网关鉴权之sa-token
目录 前言 项目描述 使用技术 项目结构 要点 实现 前期准备 依赖准备 统一依赖版本 模块依赖 配置文件准备 登录准备 网关配置token解析拦截器 网关集成sa-token 配置sa-token接口鉴权 配置satoken权限、角色获取 通用模块配置用户拦截器 api模块配置feign…...

23【进制的理解】
很多人可能听过计算机的最底层是2进制执行,但是原理并不知道,我们今天先不讨论那么复杂的问题,先讨论什么是进制 1910,10并不是1个字符,而是2个字符,也就是说在10进制里面没有“10”这个字符,1…...

jemalloc 5.3.0的tsd模块的源码分析
一、背景 在主流的内存库里,jemalloc作为android 5.0-android 10.0的默认分配器肯定占用了非常重要的一席之地。jemalloc的低版本和高版本之间的差异特别大,低版本的诸多网上整理的总结,无论是在概念上和还是在结构体命名上在新版本中很多都…...

【Convex Optimization Stanford】Lec3 Function
【Convex Optimization Stanford】Lec3 Function 前言凸函数的定义对凸函数在一条线上的限制增值扩充? 一阶条件二阶条件一些一阶/二阶条件的例子象集和sublevel set关于函数凸性的扩展(Jesen Inequality)保持函数凸性的操作非负加权和 & 仿射函数的…...

深入 Rollup:从入门到精通(三)Rollup CLI命令行实战
准备阶段:初始化项目 初始化项目,这里使用的是pnpm,也可以使用yarn或者npm # npm npm init -y # yarn yarn init -y # pnpm pnpm init安装rollup # npm npm install rollup -D # yarn yarn add rollup -D # pnpm pnpm install rollup -D在…...

wangEditor富文本编辑器,Laravel上传图片配置和使用
文章目录 前言步骤1. 构造好前端模版2. 搭建后端存储3. 调试 前言 由于最近写项目需要使用富文本编辑器,使用的是VUE3.0版本所以很多不兼容,实际测试以后推荐使用wangEditor 步骤 构造好前端模版搭建后端存储调试 1. 构造好前端模版 安装模版 模版安…...
chrome源码剖析—进程通信
Chrome 浏览器采用多进程架构(multi-process architecture),这种架构使得每个浏览器标签、扩展、插件、GPU 渲染等都在独立的进程中运行。为了确保不同进程之间的高效通信,Chrome 使用 进程间通信(IPC, Inter-Process …...
JJJ:linux时间子系统相关术语
文章目录 墙上时间内核管理的各种时间无时钟滴答模式(tickless mode 或 no-tick mode)简要介绍具体实现动态时钟滴答 Dynamic Ticks完全无时钟滴答(Full Tickless) nohz sleep单触发模式 oneshot mode 墙上时间 真实世界的真实时…...

0 基础学运维:解锁 K8s 云计算运维工程师成长密码
前言:作为一个过来人,我曾站在技术的门槛之外,连电脑运行内存和内存空间都傻傻分不清,完完全全的零基础。但如今,我已成长为一名资深的k8s云计算运维工程师。回顾这段历程,我深知踏上这条技术之路的艰辛与不…...
大一计算机的自学总结:位运算的应用及位图
前言 不仅异或运算有很多骚操作,位运算本身也有很多骚操作。(尤其后几个题,太逆天了) 一、2 的幂 class Solution { public:bool isPowerOfTwo(int n) {return n>0&&n(n&-n);} }; 根据二进制表示数的原理&#…...

计算机毕业设计Django+Tensorflow音乐推荐系统 机器学习 深度学习 音乐可视化 音乐爬虫 知识图谱 混合神经网络推荐算法 大数据毕设
温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 温馨提示:文末有 CSDN 平台官方提供的学长联系方式的名片! 作者简介:Java领…...

AI 图片涌入百度图库
在这个信息爆炸的时代,我们习惯了通过搜索引擎来获取各种想要的信息和图片。然而,现在打开搜索引擎看到的却是许多真假难辨的信息——AI图片,这部分数据正以惊人的速度涌入百度图库,让小编不禁想问:未来打开百度图库不…...

可爱狗狗的404动画页面HTML源码
源码介绍 可爱狗狗的404动画页面HTML源码,源码由HTMLCSSJS组成,记事本打开源码文件可以进行内容文字之类的修改,双击html文件可以本地运行效果 效果预览 源码获取 可爱狗狗的404动画页面HTML源码...

【微服务与分布式实践】探索 Dubbo
核心组件 服务注册与发现原理 服务提供者启动时,会将其服务信息(如服务名、版本、所在节点的网络地址等)注册到注册中心。服务消费者则可以从注册中心发现可用的服务提供者列表,并与之通信。注册中心会存储服务的信息,…...

OpenCSG月度更新2025.1
1月的OpenCSG取得了一些亮眼的成绩 在2025年1月,OpenCSG在产品和社区方面继续取得了显著进展。产品方面,推出了AutoHub浏览器自动化助手,帮助用户提升浏览体验;CSGHub企业版功能全面升级,现已开放试用申请,…...

C++封装红黑树实现mymap和myset和模拟实现详解
文章目录 map和set的封装map和set的底层 map和set的模拟实现insertiterator实现的思路operatoroperator- -operator[ ] map和set的封装 介绍map和set的底层实现 map和set的底层 一份模版实例化出key的rb_tree和pair<k,v>的rb_tree rb_tree的Key和Value不是我们之前传统意…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...

C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...