【数据结构】链表
目录
数据结构之链表::
SList.h
1.链表的概念及结构
2.链表的分类
SList.c
3.动态申请一个结点
4.单链表打印
5.单链表销毁
6.单链表头插
7.单链表头删
8.单链表尾插
9.单链表尾删
10.单链表查找
11.单链表在pos之前插入
12.单链表在pos之后插入
13.删除pos位置
14.删除pos后面位置
数据结构之链表::
SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
SListNode* next为C++中的语法 将其封装成了类
void SListPrint(SLTNode* phead);
void Destory(SLTNode** pphead);
void SListPushFront(SLTNode** pphead, SLTDataType x);
void SListPushBack(SLTNode** pphead, SLTDataType x);
void SListPopBack(SLTNode** pphead);
void SListPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
在pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
删除pos后面位置
void SListEraseAfter(SLTNode* pos);
1.链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.

注意:
1.从上图可以看出,链式结构在逻辑上是连续的,但是在物理上不一定连续.
2.现实中的结点一般都是从堆上申请出来的.
3.从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续.
2.链表的分类
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构.
1.单向或者双向
2.带头或者不带头

3.循环或者非循环

虽然有这么多的链表结构,但是我们实际中最常用还是两种结构.

无头单向非循环链表:
结构简单,一般不会用来单独存数据,实际上更多是作为其他数据结构的子结构,如哈希桶,图的邻接表等.
带头双向循环链表:
结构最复杂,一般用来单独存储数据,实际中使用到的链表数据结构,都是带头双向循环链表,这个结构虽然复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了.
SList.c
3.动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}
4.单链表打印
void SListPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
5.单链表销毁
void Destory(SLTNode** pphead)
{assert(pphead);SLTNode* cur = *pphead;while (cur != NULL){SLTNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}
6.单链表头插
void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}
7.单链表头删
void SListPopFront(SLTNode** pphead)
{assert(pphead);温柔的检查if (*pphead == NULL){return;}暴力的检查//assert(*pphead != NULL);SLTNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}
8.单链表尾插
void SListPushBack(SLTNode** pphead, SLTDataType x)
{1.链表是空2.链表非空链表为空 插入第一个结点 要改变的是SListNode* 用的是结构体指针的指针链表不为空 尾插要改变的是结构体SListNode的成员 用的是结构体指针assert(pphead);SLTNode* newnode = BuySLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
9.单链表尾删
void SListPopBack(SLTNode** pphead)
{assert(pphead);温柔的检查——为空不删if (*pphead == NULL){return;}暴力的检查//assert(*pphead != NULL);1.一个结点 2.多个结点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{找尾SLTNode* prev = NULL;/*SLTNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}prev->next == NULL;free(tail);tail = NULL;*/SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}prev->next = NULL;free(tail->next);tail->next = NULL;}
}
10.单链表查找
链表中的查找函数可以替代其修改函数
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
11.单链表在pos之前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SListPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;pos不在链表中 pos不在链表中 prev为空还没有找到pos 说明pos传错了assert(prev);}SLTNode* newnode = BuySLTNode(x);prev->next = newnode;newnode->next = pos;}
}
12.单链表在pos之后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}
13.删除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;检查pos不是链表中结点 参数传错的情况assert(prev);}prev->next = pos->next;free(pos);//pos = NULL;此代码并不会改变pos 使用人在main函数将其置空}
}
14.删除pos后面位置
void SListEraseAfter(SLTNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SLTNode* next = pos->next;pos->next = next->next;free(next);}
}
单链表:只适合头插头删——O(1)
任意位置高效插入删除——双向链表
进阶:删除pos位置 要求是O(1) 替换法删除
缺陷:pos不能是尾结点 解决方法:将链表改成循环链表
进阶:在pos位置之前插入 要求是O(1)
方法:在pos位置后创造结点+替换法
newnode = BuySListNode(pos->val);
pos->val = x;
相关文章:
【数据结构】链表
目录 数据结构之链表:: SList.h 1.链表的概念及结构 2.链表的分类 SList.c 3.动态申请一个结点 4.单链表打印 5.单链表销毁 6.单链表头插 7.单链表头删 8.单链表尾插 9.单链表尾删 10.单链表查找 11.单链表在pos之前插入…...
一文讲明Hystrix熔断器
前言 解决问题: 主要防止服务器集群发生雪崩, 起到对服务器的保护作用 GitHub地址:https://github.com/Netflix/Hystrix/wiki 1 Hystrix是什么 1.1 分布式系统面临的问题 复杂分布式体系结构中的应用程序有数十个依赖关系,每个依赖关系在某些时候将不…...
第12篇:Java类核心构成要素分析
目录 1、Java类构成要素 1.1 如何定义类 1.2 如何定义变量 1.2.1 类变量 1.2.2 实例变量...
记一次 .NET 某医保平台 CPU 爆高分析
一:背景 1. 讲故事 一直在追这个系列的朋友应该能感受到,我给这个行业中无数的陌生人分析过各种dump,终于在上周有位老同学找到我,还是个大妹子,必须有求必应 😁😁😁。 妹子公司的…...
滤波算法 | 无迹卡尔曼滤波(UKF)算法及其MATLAB实现
目录简介UKF滤波滤波流程和公式MATLAB程序结论简介 本文接着分享位姿跟踪和滤波算法中用到的一些常用程序,希望为后来者减少一些基础性内容的工作时间。以往分享总结见文章:位姿跟踪 | 相关内容目录和链接总结(不断更新中~~~) 本…...
JAVA开发(运行JAR包怎么指定虚拟机内存大小)
我们都使用过 java -jar xxx.jar包去运行jar包。但是有时候要指定jar包运行时内存,该怎么做,而且设置多大怎么衡量,很多人从来没有了解过。 背景: 我们开发java程序,可能涉及到开发环境,测试环境&#x…...
领导力的终极奥义
过去,我曾多次演讲、著书,把自己在长达半个世纪的经营实践中所体悟到的经营思想和方法告诉中国的企业家。 但是,对于任何一家企业来说,不管它倡导了多么高尚的经营哲学,不管它构建了多么精致的管理系统,这样…...
1-MATLAB APP Design-图像的输入与输出
一、APP 界面设计展示 新建一个空白的APP,在此次的学习中,我们会用到编辑字段(文本框)、 按钮、坐标区和面板,首先在界面中拖入一个编辑字段(文本框),在文本框中输入内容:图形的输入与输出,调整背景颜色,字体的颜色为黑色,字体的大小调为25....
【C++】内存管理
目录一、C/C内存分布二、C内存管理方式2.1、new/delete操作内置类型2.2、new和delete操作自定义类型三、operator new与operator delete函数3.1、operator new与operator delete函数四、new和delete的实现原理4.1、内置类型4.2、自定义类型五、定位new表达式(placement-new)六、…...
Dilworth定理
偏序关系 设RRR是集合AAA的一个二元关系,若RRR满足: 1.自反性:∀x∈A\forall x \in A∀x∈A,有xRxxRxxRx 2.反对称性:∀x,y∈A\forall x,y \in A∀x,y∈A,若xRy,yRxxRy,yRxxRy,yRx,则xyxyxy 3.传递性&…...
使用loading动画让你的条件渲染页面更高级
前言在我们做项目的使用常常会使用条件渲染去有选择的给用户展示相关页面,如果渲染的数据或场景比较多比较复杂,那么往往需要3、4s的时间去完成,用户点击了之后就会陷入3、4s的空白期,并且这段时间屏幕是处于一种”未响应“的状态…...
Renegade:基于MPC+Bulletproofs构建的anonymous DEX
1. 引言 白皮书见: Renegade Whitepaper: Protocol Specification, v0.6 开源代码见: https://github.com/renegade-fi/renegade(Renegade p2p网络每个节点的核心网络和密码逻辑)https://github.com/renegade-fi/mpc-bulletpr…...
二、Plugin The chain/event/query function
The chain function 链函数是所有数据处理都在其中进行的函数。在简单过滤器的情况下(本节示例的情况),_chain()函数大多是线性函数——因此对于每个传入的缓冲区,也将输出一个缓冲区。下面是一个非常简单的chain函数的实现: sta…...
了解 PostgreSQL 的扩展查询协议
1.介绍 本篇博客用于解释扩展协议的工作原理以及它与简单查询的区别。 2.简单查询 在PostgreSQL中,客户端连接能够发起两种类型的查询:简单查询和扩展协议查询。 简单查询顾名思义。 当启动 psql 客户端连接到pg服务器时,几乎所有发送的…...
接入网关和隔离网关
文章目录1. 什么是网关?2. 网关的作用是什么?3. 接入网关和隔离网关1. 什么是网关? 网关(Gateway)是一种网络设备,通常用于将不同网络之间的流量进行转发和路由,将一个网络连接到另一个网络&…...
实用指南:如何在Anolis OS上轻松使用 Kata 安全容器?
文/云原生SIG本篇文章我们将详细介绍怎么轻松在 Anolis OS 上使用 Kata Containers 安全容器,我们将介绍 Kata Container 社区于 2022 年 10 月 10 日最新发行的 Kata3.0.0 的安装部署方式,3.0.0 版本包含了基于袋鼠 RunD 开源的最新 Rust Kata runtime …...
如何锁定Word文档部分文字不被修改
我们知道,想要保护Word文档的内容无法随意更改,可以设置“限制编辑”的保护模式。 那如果实际工作中,只需要固定的一部分内容不能编辑,可以实现吗?答案是肯定的,今天就来说说如何设置Word文档部分文字可修…...
聊聊8万8的私董会,很扎心
聊聊8万8的私董会,很扎心 道几句真心话,很扎心,但也很现实。 如果你喜欢刷抖音,这种感觉应该会更加明显。 股市哀鸿遍野,实体一地鸡毛,我们办公室楼下的门面换了一波又一波。 别说那些不起眼的小生意&a…...
卷积网络与全连接网络的区别
问题卷积神经网络是一类包含卷积计算且具有深度结构的前馈神经网络,是深度学习。卷积神经网络具有表征学习能力,能够按其阶层结构对输入信息进行平移不变分类,因此也被称为“平移不变人工神经网络。全连接神经网络是具有多层感知器的的网络&a…...
【5000左右电脑配置清单】预算不高于5000,不带显示器的电脑配置清单推荐
由于本人是学生党经济有限,预算不高于5000元配一套电脑主机,说实话5000左右的电脑配置已经很好了,今天站长整理了几款配置给大家参考参考,更多电脑配置还请继续关注西安SEO优化站点! 配置1: <CPU> I5…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
