单链表（Single Link Table)——单文件实现

一、单链表前言

上篇文章我们讲述了顺序表，认真学习我们会发现顺序表优缺点。

缺点1：头部和中部的插入删除效率都不行，时间和空间复杂度都为O(N);

缺点2：空间不够了扩容有一定的消耗(尤其是realloc的异地扩容)；

缺点3：扩容逻辑，可能还存在空间，就像我只需要插入170个数据，但是要扩容200个数据大小，就会造成浪费。

优点1：尾插尾删足够快；

优点2：下标的随机访问和修改很快很方便；

基于顺序表的缺点我们通过今天的单链表来解决；

二、链表

2.1链表的基本概念和结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的 。

结构图：

链表和顺序表一样也是通过结构体实现的，不一样的是链表中的结构体只含有有效数据和指向下个结构体的结构体指针

让我们先通过代码实现一个简单的链表吧！

#include<stdio.h>
#include<stdlib.h> 
typedef struct SListNode{int data;struct SListNode* next;
}SLTNode;
int main()
{SLTNode*n1=(SLTNode*)malloc(sizeof(SLTNode));n1->data=1;SLTNode*n2=(SLTNode*)malloc(sizeof(SLTNode));n2->data=2;SLTNode*n3=(SLTNode*)malloc(sizeof(SLTNode));n3->data=3;n1->next=n2;n2->next=n3;n3->next=NULL;SLTNode*plist=n1;while(plist){printf("%d->",plist->data);plist=plist->next;}printf("NULL\n");return 0;}

这里我们开辟了三个结构体的空间用三个结构体指针指向每个结构体，然后将每个结构体里的结构体指针指向下一个结构体，再将每个结构体存入有效数据，一个简单的3长度的链表。

注意：

1.看上面的图逻辑上我们可能会认为是连续的，但是在物理地址内存上可能是连续的也可能是不连续的；

2.现实中的每个结点都是从堆上开辟的

3.从堆上开辟空间是按照一定策略的，两次连续的开辟空间可能是连续的，也可能是不连续的

2.2链表的分类

2.2.1单向或者双向

2.2.2带头或者不带头

2.2.3循环或者非循环

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

 1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了，后面我们代码实现了就知道了。

三、无头单向非循环链表增删查改链表的实现

3.1链表的创建

typedef int SLTDatatype;
typedef struct SListNode
{SLTDatatype data;struct SListNode* next;
}SLTNode;

3.2填充数据及开辟新的结点

SLTNode* BuySLT(SLTDatatype x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

链表的实现靠的是结构体里的结构体指针指向下一个结构体链接，所以我们要将新的结点返回，

返回的是结构体指针，定义函数是也要结构体指针接受。

3.3打印链表

void SLprint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

我们是靠头结构体指针找到链表的，但是打印有效数据要移动指针所以我们就要在一开始创建一个指针，利用这个指针的移动打印数据，当这个指针为空时并不是指向空时停止打印。

3.4查找有效数据

SLTNode* SLFind(SLTNode* phead, SLTDatatype x)
{SLTNode* cur = phead;while (cur){if (cur->data = x){return cur;}cur = cur->next;}return NULL;
}

和打印有效数据相似通过另一个指针的移动查找我们需要的有效数据，当指针为空时我们找不到有效数据返回NULL，当找到有效数据时返回指向含有这个有效数据的结构体；

3.5单链表尾插

void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{SLTNode* newnode = BuySLT(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}
}

首先我们需要一个空结构体指针指向开辟好的返回值为结构体指针，当无链表时也相当于头插我们只需将开辟好返回值为结构体指针赋值给空指针就行，此时这个链表只有一个结构体；当链表已经形成时此时才是我们的尾插，我们需要另一个指针从头开始找到链表末尾的空指针，再将这个空指针指向以开辟好的返回值为结构体指针就可以从尾部将其串联起来；

为什么要使用二级指针呢？

我们是有一个指针指向空或者链表的头，在尾插时我们要通过头指针的移动增添数据，但是这个指针我们不可以移动，移动的话会造成内存泄漏，所以我们又创建一个指针将这个指针指向我们的空或者链表的头，通过指针的操作将我们的链表串联起来，我们也可以将这个指针想象成我们的头指针，这个指针会变化相当于头指针变化，但是我们是在一个函数域中操作，除了这个作用域一切都会销毁，相当于什么都没敢。通俗的说我们是在操作头指针，在另个作用域中改变我们原有的值只能通过二级指针实现，但是头指针已经是个指针了，所以我们需要一个二级指针。

3.6尾删

void SLTPopBack(SLTNode** pphead)
{if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

首先我们要判断这个链表是否只有一个结构体，如果只有一个结构体直接将这个结构体释放销毁就行了；如果有多个结构体链接只需要找到倒数第二个结构体中的指向最后一个结构体的指针，释放这个指向最后一个结构体的指针就是可以实现尾删；

3.7头插

void SLPushFront(SLTNode** pphead, SLTDatatype x)
{SLTNode* newnode = BuySLT(x);if ((*pphead) == NULL){*pphead = newnode;}else{SLTNode* newnode = BuySLT(x);newnode->next = *pphead;*pphead = newnode;}
}

如果这个头指针为空时及没有链表，直接将这个指针指向开辟好的结构体的就行，如果不为空，将开辟好的结构体里指向下一个结构体的结构体指针指向我们的头指针，再将头指针指向开辟好的结构体就行；

3.8头删

void SLPopFront(SLTNode** pphead)
{if ((*pphead) == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}
}

首先我们还是先判断这个链表是否只含有一个结构体，如果只含有一个结构体和尾删的方法一样

如果含有多个结构体头删，我们只需要新创建一个指针保存第一个结构体里储存着第二个结构体的指针，然后释放掉我们的头指针，再将新创建的指针赋值给头指针就可以完成尾删。

到这里无头单向非循环链表增删查改的重点内容和注意事项就讲解完毕了，下面我们实现一下链表中间随机的增删查改，就不一一讲解了，大家自行了解；

四、无头单向非循环链表中间随机增删查改

4.1在pos位置后插入x

void SLInsertAfter(SLTNode* pos, SLTDatatype x)
{SLTNode* newnode = BuySLT(x);newnode->next = pos->next;pos->next = newnode;
}

4.2在pos位置后插入x

void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{if (pos == *pphead){SLPushFront(pphead, x);}else{SLTNode* newnode = BuySLT(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}

4.3删除pos位置的值

void SLTErase(SLTNode** pphead, SLTNode* pos)
{if ((*pphead) == pos){SLPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

 4.4删除pos位置后面的值

void SLEraseAfter(SLTNode* pos)
{assert(pos->next);SLTNode* newnode = pos->next->next;free(pos->next);pos->next = newnode;
}

五、无头单向非循环链表增删查改完整代码

#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDatatype;
typedef struct SListNode
{SLTDatatype data;struct SListNode* next;
}SLTNode;
//打印 
void SLprint(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
//开辟新的空间
SLTNode* BuySLT(SLTDatatype x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc failed");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}
//查找
SLTNode* SLFind(SLTNode* phead, SLTDatatype x)
{SLTNode* cur = phead;while (cur){if (cur->data = x){return cur;}cur = cur->next;}return NULL;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDatatype x)
{SLTNode* newnode = BuySLT(x);if (*pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}
}
//尾删
void SLTPopBack(SLTNode** pphead)
{if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}
//头插	
void SLPushFront(SLTNode** pphead, SLTDatatype x)
{SLTNode* newnode = BuySLT(x);if ((*pphead) == NULL){*pphead = newnode;}else{SLTNode* newnode = BuySLT(x);newnode->next = *pphead;*pphead = newnode;}
}
//头删 
void SLPopFront(SLTNode** pphead)
{if ((*pphead) == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* newhead = (*pphead)->next;free(*pphead);*pphead = newhead;}
}
//在pos位置后插入x
void SLInsertAfter(SLTNode* pos, SLTDatatype x)
{SLTNode* newnode = BuySLT(x);newnode->next = pos->next;pos->next = newnode;
}
//在pos位置前插入x 
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDatatype x)
{if (pos == *pphead){SLPushFront(pphead, x);}else{SLTNode* newnode = BuySLT(x);SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{if ((*pphead) == pos){SLPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}void SLEraseAfter(SLTNode* pos)
{assert(pos->next);SLTNode* newnode = pos->next->next;free(pos->next);pos->next = newnode;
}
int main()
{SLTNode* plist = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushBack(&plist, 5);SLTPushBack(&plist, 10);printf("尾插:\n");SLprint(plist);//尾删printf("尾删:\n");SLTPopBack(&plist);SLprint(plist);//头插printf("头插:\n");SLPushFront(&plist, 10);SLprint(plist);//头删printf("头删:\n");SLPopFront(&plist);SLprint(plist);//在pos位置后插入xSLTNode* pos1 = SLFind(plist, 1);SLInsertAfter(pos1, 10);printf("在pos位置后插入x\n");SLprint(plist);//在pos位置前插入xSLTNode* pos2 = SLFind(plist, 1);printf("在pos位置前插入x\n");SLInsert(&plist, pos2, 20);SLprint(plist);//删除pos位置的值SLTNode* pos3 = SLFind(plist, 10);SLTErase(&plist, pos3);printf("删除pos位置的值:\n");SLprint(plist);//删除pos后面的值SLTNode* pos4 = SLFind(plist, 1);SLEraseAfter(pos4);printf("删除pos位置后面的值:\n");SLprint(pos4);return 0;
}

到这里我们的无头单向非循环链表增删查改的所有内容就讲解完了，有什么问题或者需要指正的可以在评论区留下您宝贵的意见。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/130070.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Docker-namespace

Docker-namespace

Docker-namespace namespace基础命令dd 命令mkfsdfmountunshare pid 隔离试验mount 隔离 namespace namespace 是 Linux 内核用来隔离内核资源的方式。通过 namespace 可以让一些进程只能看到与自己相关的一部分资源&#xff0c;而另外一些进程也只能看到与它们自己相关的资源…
阅读更多...
【Unity编辑器扩展】| 顶部菜单栏扩展 MenuItem

【Unity编辑器扩展】| 顶部菜单栏扩展 MenuItem

前言【Unity编辑器扩展】 | 顶部菜单栏扩展 MenuItem一、创建多级菜单二、创建可使用快捷键的菜单项三、调节菜单显示顺序和可选择性四、创建可被勾选的菜单项五、右键菜单扩展5.1 Hierarchy 右键菜单5.2 Project 右键菜单5.3 Inspector 组件右键菜单六、AddComponentMenu 特性…
阅读更多...
MediaBox助力企业一站式获取音视频能力

MediaBox助力企业一站式获取音视频能力

以一只音视频百宝箱&#xff0c;应对「千行千面」。 洪炳峰、楚佩斯&#xff5c;作者 大家好&#xff0c;今天我分享的主题是MediaBox——行业音视频数字化再加速。 根据权威数据表明&#xff0c;65%的行业数字化信息来自视频&#xff0c;基于此&#xff0c;音视频技术对于行…
阅读更多...
群晖NAS教程(二十五)、利用web station安装nextcloud

群晖NAS教程(二十五)、利用web station安装nextcloud

群晖NAS教程(二十五)、利用web station安装nextcloud 一、下载离线安装包文件 下载地址https://download.nextcloud.com/server/releases/&#xff0c;我们选择zip格式的&#xff0c;下载这个latest-27.zip的最新版的。 把它加压缩到群辉web/hepnextcloud路径下&#xff0c;并…
阅读更多...
CSS：隐藏移动端的滚动条的方式

CSS：隐藏移动端的滚动条的方式

目录 方式一&#xff1a;-webkit-scrollbar方式二&#xff1a;overflow方式三&#xff1a;clip-path方式四&#xff1a;mask 遮罩总结参考 移动端开发中&#xff0c;有一个横向滚动元素&#xff0c;产品告诉我不需要滚动条&#xff0c;我说这个简单&#xff0c;隐藏一下不就行了…
阅读更多...
Ubuntu使用命令行界面配置静态IP地址

Ubuntu使用命令行界面配置静态IP地址

参考地址&#xff1a;https://www.zhihu.com/tardis/sogou/art/46544606 方法一&#xff1a;配置/etc/network/interfaces文件 首先查看网卡接口名称&#xff1a;ip a 知道网卡接口名称之后&#xff0c;在 /etc/network/interfaces 文件中配置&#xff1a; auto enp0s31f6 …
阅读更多...
keep-alive缓存三级及三级以上路由

keep-alive缓存三级及三级以上路由

需求需要缓存这个出入记录&#xff0c;当tab切换时不重新加载&#xff0c;当刷新页面时&#xff0c;或把这个关闭在重新打开时重新加载如图&#xff1a; &#xff08;我这里用的是芋道源码的前端框架) keep-alive 1、include 包含页面组件name的这些组件页面&#xff0c;会被…
阅读更多...
【算法与数据结构】236、LeetCode二叉树的最近公共祖先

【算法与数据结构】236、LeetCode二叉树的最近公共祖先

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a; 根据定义&#xff0c;最近祖先节点需要遍历节点的左右子树&#xff0c;然后才能知道是否为最近祖先节…
阅读更多...
Kubernetes 部署发布镜像（cubefile:0.4.0）

Kubernetes 部署发布镜像（cubefile:0.4.0）

目录 实验&#xff1a;部署发布镜像&#xff08;cubefile:0.4.0&#xff09; 需求分析&#xff1a; 1、部署Kubenetes环境&#xff1a; 2、撰写 cubefile-deployment.yaml 文件 代码解释&#xff1a; 遇到的问题&#xff1a; 问题解决 &#xff1a; 3、撰写 cubefile-se…
阅读更多...
vue2中实现 TDesign 树形懒加载

vue2中实现 TDesign 树形懒加载

之前我有写过Element ui的树形懒加载 其主要是通过load函数来实现 而TDesign也是照虎画猫 他也是主要靠load 我们先来看一个基本的组件 <template><t-tree :data"items" :load"load" /> </template><script lang"jsx">…
阅读更多...
开启更高效之路，美创科技暗数据发现和数据分类分级系统全新升级

开启更高效之路，美创科技暗数据发现和数据分类分级系统全新升级

数字经济时代&#xff0c;数据分类分级作为平衡数据保护和流通利用的基础工作&#xff0c;愈发受到广泛的关注。但面对海量繁杂的数据&#xff0c;如何快速地实现数据梳理与分类分级&#xff0c;对于绝大多数组织而言&#xff0c;并非易事—— ◼︎ 在缺少标准方法和自动化、智…
阅读更多...
C++之结构体智能指针shared_ptr实例(一百九十四)

C++之结构体智能指针shared_ptr实例(一百九十四)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 人生格言&#xff1a; 人生…
阅读更多...
Redis的基本概念与基础用法（1）

Redis的基本概念与基础用法（1）

在节假日前12306的访问量就会急剧增加&#xff0c;在这种海量用户高并发的情况下就容易出现网站崩溃的情况&#xff0c;造成网站奔溃的罪魁祸首就是关系型数据库&#xff0c;因为关系型数据库有&#xff1a; 性能瓶颈&#xff1a;磁盘IO性能低下扩展瓶颈&#xff1a;数据关系复…
阅读更多...
机器学习（10）---特征选择

机器学习（10）---特征选择

文章目录 一、概述二、Filter过滤法2.1 过滤法说明2.2 方差过滤2.3 方差过滤对模型影响 三、相关性过滤3.1 卡方过滤3.2 F检验3.3 互信息法3.4 过滤法总结 四、Embedded嵌入法4.1 嵌入法说明4.2 以随机森林为例的嵌入法 五、Wrapper包装法5.1 包装法说明5.2 以随机森林为例的包…
阅读更多...
SpringMVC之文件上传下载以及jrebel的使用

SpringMVC之文件上传下载以及jrebel的使用

目录 前言 文件上传 导入依赖 配置文件上传解析器 配置存放地址 ​编辑 导入PropertiesUtil工具类 编写resource.properties 添加sql 编写PageController类 编写主页展示界面 编写文件上传方法 搭建一个图片上传的操作页面 文件下载 多文件上传 效果展示​编辑 jre…
阅读更多...
web UI自动化介绍

web UI自动化介绍

文章目录 一、web UI自动化介绍1.1 执行UI自动化测试前提1.2 Selenium介绍以及知识点梳理 二、Selenium 学习2.1 基础2.1.1 环境安装与基础使用2.1.2 web浏览器控制2.1.3 常见控件的八大定位方式2.1.3.1 八大定位方式介绍2.1.3.2 NAME、ID定位2.1.3.3 css_selector定位2.1.3.4 …
阅读更多...
c++qt day2

c++qt day2

封装一个结构体&#xff0c;结构体中包含一个私有数组&#xff0c;用来存放学生的成绩&#xff0c;包含一个私有变量&#xff0c;用来记录学生个数&#xff0c; 提供一个公有成员函数&#xff0c;void setNum(int num)用于设置学生个数 提供一个公有成员函数&#xff1a;void…
阅读更多...
Cascade-MVSNet CVPR-2020 学习笔记总结 译文 深度学习三维重建

Cascade-MVSNet CVPR-2020 学习笔记总结 译文 深度学习三维重建

文章目录 4 Cascade-MVSNet CVPR-20204.0 主要特点4.1 背景介绍4.2 代价体构造回顾4.3 Cascade-MVSNet4.4 Loss的设置4.5 Cascade-MVSNet实战操作4.6 总结4 Cascade-MVSNet CVPR-2020 深度学习三维重建 cascade-MVSNet-CVPR-202（源码、原文、译文 )下载 4.0 主要特点 采用特…
阅读更多...
Python用GAN生成对抗性神经网络判别模型拟合多维数组、分类识别手写数字图像可视化...

Python用GAN生成对抗性神经网络判别模型拟合多维数组、分类识别手写数字图像可视化...

全文链接&#xff1a;https://tecdat.cn/?p33566 生成对抗网络&#xff08;GAN&#xff09;是一种神经网络&#xff0c;可以生成类似于人类产生的材料&#xff0c;如图像、音乐、语音或文本&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 相关视频 最近我们…
阅读更多...
Python之数据库（MYSQL）连接

Python之数据库（MYSQL）连接

一&#xff09;数据库SQL语言基础 MySQL是一个关系型数据库管理系统&#xff0c;由瑞典MySQL AB 公司开发&#xff0c;目前属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理系统之一&#xff0c;在 WEB 应用方面&#xff0c;MySQL是最好的 RDBMS (Relational Database…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023