【数据结构】链表
目录
数据结构之链表::
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…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
