链表之“无头单向非循环链表”

目录

​编辑

1.顺序表的问题及思考

2.链表

2.1链表的概念及结构

2.2无头单向非循环链表的实现

1.创建结构体

2.单链表打印

3.动态申请一个节点

3.单链表尾插

4.单链表头插

5.单链表尾删

6.单链表头删

7.单链表查找

8.单链表在pos位置之前插入x

9.单链表删除pos位置的值

10.单链表在pos位置之后插入x

11.单链表删除pos位置之后的值

12.单链表销毁

3.源码

1.顺序表的问题及思考

🌻问题：

  • 顺序表在尾部插入删除效率还不错，但是在头部或者中间位置插入删除，就需要挪动数据，时间复杂度为O(N)，效率低下。
  • 空间满了以后只能增容，增容需要申请新的空间，拷贝数据，释放旧空间，会有一定的消耗。
  • 增容一般是呈2倍的增长，势必会有一定的空间浪费。假设当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。也就是说，一次增的越多，可能浪费越多；一次增的少了，那么就会频繁增容。

🌻思考：

  • 如何解决以上问题呢？下面让我们一起来看看链表的结构：

2.链表

2.1链表的概念及结构

🌴概念： 

  • 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
  • 简单来说，就是链表中的每一个数据元素都是单独存储的，我们把这个数据元素又叫做节点。当需要存储下一个数据元素的时候就申请一块新的内存用来存储数据，每一个节点又通过地址链接起来，当前节点存放的是下一个节点的地址。所以，一个节点里边就包含数据元素和下一个节点的地址这两部分。

🌴结构：

注意：

  1. 从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
  2. 现实中的节点一般都是从堆上申请出来的。
  3. 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

假设在32位系统上，节点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：

2.2无头单向非循环链表的实现

1.创建结构体

typedef int SLTDataType;typedef struct SListNode
{SLTDataType val;        //数据域struct SListNode* next; //指针域
}SLNode;

2.单链表打印

  • phead是一个指针变量，占4个字节，它指向第一个节点，即存的是第一个节点的地址。而在其它节点中，每个节点里边分别又有两个数据域，其中一个保存val，另一个保存下一个节点的地址，在32位环境下，一个节点占8个字节。
  • 遍历链表时，担心phead会发生意外，所以我们先将phead的值赋给cur，看cur等不等于NULL，如果不等于NULL，就进入循环，打印第一个节点的值，然后将第二个节点的地址再赋给cur，看它等不等于NULL，如果不等于NULL，再打印第二个节点的值，再将第三个节点的地址赋给cur，以此循环，直到cur等于NULL，就跳出循环。

//单链表打印
void SLTPrint(SLNode* phead)
{//不要动phead，否则会找不到头SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->val);cur = cur->next;}printf("NULL\n");
}

3.动态申请一个节点

如果直接在其它函数内部申请节点的话，它的作用域就只能在那个函数内部，出了函数作用域就会销毁，所以得单独写一个函数来申请节点，让其它函数来调用它。

//动态申请一个节点
SLNode* CreateNode(SLTDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}

3.单链表尾插

单链表尾插分为有节点和无节点两种情况：

  • 假设现在链表里边有节点，那我们要尾插一个数据，第一步肯定是要先找到尾。先定义一个tail，让它指向头节点，然后看tail->next等不等于NULL，如果不为NULL，让tail等于tail->next，依次循环，直到tail->next等于NULL的时候，tail刚好就是尾节点。找到尾节点后，再动态申请一个节点，让新申请的节点指向NULL，再让尾节点指向新申请的这个节点。

  • 如果链表里边没有节点，即链表为空，那我们直接让*pphead指向新节点的地址就行了。因为在主函数里边我们定义的是*plist的指针，所以要想改变外面结构体指针SLNode*，就要用二级指针SLNode**。
//单链表尾插
void SLTPushBack(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

4.单链表头插

头插时比较简单，我们让新申请出来的节点newnode指向第一个节点的地址，而第一个节点的地址保存在plist里边，我们又把plist的地址赋给了pphead，所以让newnode->next指向*pphead，再将*pphead指向newnode就可以了。

//单链表头插
void SLTPushFront(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;
}

5.单链表尾删

单链表的尾删也分为两种情况：

  • 第一种是当链表里边只有一个节点的时候，我们只需要free掉这个节点，然后让plist指向空就行了。
  • 第二种是当链表里边有多个节点的时候，我们可以定义两个指针，让第一个指针prev指向NULL，第二个指针保存头节点的地址，然后通过循环找尾，当找到尾的时候，跳出循环，此时prev刚好指向了尾的前一个节点，我们再free掉尾，让前一个节点指向空就可以了。
//单链表尾删
void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//1.一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//2.多个节点else{/*SLNode* prev = NULL;SLNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;*/SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

6.单链表头删

因为空链表无法删除，所以需要先断言。头删只需要将第一个节点free掉就可以了，但是free之前得先保存下一个节点的地址。

//单链表头删
void SLTPopFront(SLNode** pphead)
{assert(pphead);//空assert(*pphead);//一个或多个以上节点都可以处理SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

7.单链表查找

单链表的查找只需要遍历一遍就可以了，定义一个cur让它指向第一个节点的地址，通过循环如果cur不为空，就进入循环，进入循环后，如果cur->val等于x，则返回cur，否则，让cur指向下一个节点的地址。遍历完一遍如果没有找到，则返回NULL。可以说查找函数是为了配合修改单链表中的值而写的。

//单链表查找
SLNode* SLTFind(SLNode* phead, SLTDataType x)
{SLNode* cur = phead;while (cur){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}

8.单链表在pos位置之前插入x

如果此时链表为空，那么就相当于头插；如果不为空，则只需找到pos位置的前一个节点，让前一个节点的地址指向新节点，新节点指向pos位置即可。

//单链表在pos位置之前插入x
void SLTInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{assert(pphead);//要么都为空，要么都不为空assert((!pos && !(*pphead)) || (pos && *pphead));if (*pphead == pos){//头插SLTPushFront(pphead, x);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLNode* newnode = CreateNode(x);prev->next = newnode;newnode->next = pos;}
}

9.单链表删除pos位置的值

如果链表只有一个节点，则相当于头删；如果有多个节点，则需要找到pos位置的前一个节点，然后让前一个节点指向pos位置的后一个节点，接着free掉pos即可。

//单链表删除pos位置的值
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){//头删SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}

10.单链表在pos位置之后插入x

创建一个新节点，先让新节点的指针域存pos后一个节点的地址，然后让pos的指针域存新节点的地址。

//单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLTDataType x)
{assert(pos);SLNode* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;
}


11.单链表删除pos位置之后的值

这个操作必须保证链表中有两个以上的数据，如果只有一个数据的话，那它后面为空，没法执行删除操作，所以得先断言一下。

//单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos->next);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}

12.单链表销毁

//单链表销毁
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

3.源码

🌻SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLTDataType;typedef struct SListNode
{SLTDataType val;struct SListNode* next;
}SLNode;//单链表打印
void SLTPrint(SLNode* phead);//单链表尾插
void SLTPushBack(SLNode** pphead, SLTDataType x);
//单链表头插
void SLTPushFront(SLNode** pphead, SLTDataType x);
//单链表尾删
void SLTPopBack(SLNode** pphead);
//单链表头删
void SLTPopFront(SLNode** pphead);//单链表查找
SLNode* SLTFind(SLNode* phead, SLTDataType x);//单链表在pos位置之前插入x
void SLTInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
//单链表删除pos位置的值
void SLTErase(SLNode** pphead, SLNode* pos);//单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLTDataType x);
//单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos);//单链表销毁
void SLTDestroy(SLNode** pphead);

🌻SList.c

#include "SList.h"//单链表打印
void SLTPrint(SLNode* phead)
{//不要动phead，否则会找不到头SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->val);cur = cur->next;}printf("NULL\n");
}//动态申请一个节点
SLNode* CreateNode(SLTDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->val = x;newnode->next = NULL;return newnode;
}//单链表尾插
void SLTPushBack(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = CreateNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找尾SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}//单链表头插
void SLTPushFront(SLNode** pphead, SLTDataType x)
{assert(pphead);SLNode* newnode = CreateNode(x);newnode->next = *pphead;*pphead = newnode;
}//单链表尾删
void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);//1.一个节点if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//2.多个节点else{/*SLNode* prev = NULL;SLNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;*/SLNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}//单链表头删
void SLTPopFront(SLNode** pphead)
{assert(pphead);//空assert(*pphead);//一个或多个以上节点都可以处理SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//单链表查找
SLNode* SLTFind(SLNode* phead, SLTDataType x)
{SLNode* cur = phead;while (cur){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}//单链表在pos位置之前插入x
void SLTInsert(SLNode** pphead, SLNode* pos, SLTDataType x)
{assert(pphead);//要么都为空，要么都不为空assert((!pos && !(*pphead)) || (pos && *pphead));if (*pphead == pos){//头插SLTPushFront(pphead, x);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLNode* newnode = CreateNode(x);prev->next = newnode;newnode->next = pos;}
}//单链表删除pos位置的值
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){//头删SLTPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}//单链表在pos位置之后插入x
void SLTInsertAfter(SLNode* pos, SLTDataType x)
{assert(pos);SLNode* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;
}//单链表删除pos位置之后的值
void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos->next);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}//单链表销毁
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

C++的stack容器-＞基本概念、常见接口

C++的stack容器-＞基本概念、常见接口

#include<iostream> using namespace std; #include <stack> //栈stack容器常用接口 void test01() { //创建栈容器 栈容器必须符合先进后出 stack<int> s; //向栈中添加元素&#xff0c;叫做 压栈 入栈 s.push(10); s.push(20); s…
阅读更多...
华清远见作业第四十一天——Qt（第三天）

华清远见作业第四十一天——Qt（第三天）

思维导图&#xff1a; 编程 完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面 如…
阅读更多...
Java编程实战：构建医疗信息管理新平台

Java编程实战：构建医疗信息管理新平台

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…
阅读更多...
项目升级神器 Taze,告别查找单个依赖版本的烦恼

项目升级神器 Taze,告别查找单个依赖版本的烦恼

Taze 是由Vue 和 Nuxt 核心成员 AntFu 写的开源库。Taze 主要是用在项目重构或者项目升级的时候检查依赖版本。 Taze 如何使用 Taze 无需安装&#xff0c;可以直接执行 npx taze 即可。 默认情况只会检查 package.json 依赖版本。 要忽略范围&#xff0c;请显式设置允许的最大…
阅读更多...
Unity中URP实现水效果（水的深度）

Unity中URP实现水效果（水的深度）

文章目录 前言一、搭建预备场景1、新建一个面片&#xff0c;使其倾斜一个角度&#xff0c;来模拟水底和岸边的效果2、随便创建几个物体&#xff0c;作为与水面接触的物体3、再新建一个面片&#xff0c;作为水面 二、开始编写水体的Shader效果1、新建一个URP基础Shader2、把水体…
阅读更多...
第N3周：Pytorch文本分类入门

第N3周：Pytorch文本分类入门

>- **&#x1f368; 本文为[&#x1f517;365天深度学习训练营](https://mp.weixin.qq.com/s/rbOOmire8OocQ90QM78DRA) 中的学习记录博客** >- **&#x1f356; 原作者&#xff1a;[K同学啊 | 接辅导、项目定制](https://mtyjkh.blog.csdn.net/)** import torch import…
阅读更多...
C语言——实用调试技巧——第1篇——（第22篇）

C语言——实用调试技巧——第1篇——（第22篇）

坚持就是胜利 文章目录 一、什么是bug?二、调试是什么&#xff1f;有多重要&#xff1f;三、debug 和 release 的介绍&#xff1f;1、2、3、 四、windows环境调试介绍1、调试环境的准备2、学会快捷键F5 或者 Fn F5条件断点 Ctrl F5F9 或者 Fn F9F10 或者 Fn F10F11 或者 F…
阅读更多...
RAG中如何解决上下文知识连贯性问题 || 如何更好的切分和组织非结构化的文档数据

RAG中如何解决上下文知识连贯性问题 || 如何更好的切分和组织非结构化的文档数据

当信息蕴含在较长的上下文时&#xff0c;基于片段的搜索召回&#xff0c;一定会丢失数据&#xff0c;导致最终无法正确的回答问题。 实际上复杂的问题&#xff0c;这里只是说问题本身倾向于从全文获取答案&#xff0c;而不仅仅是基于片段。 斯坦福论文提出的核心问题和解决思路…
阅读更多...
小程序--本地存储API

小程序--本地存储API

1、存储数据 wx.setStorageSync()&#xff1a;无需转换数据类型&#xff0c;存什么类型的就是什么类型的&#xff0c;data中的数据&#xff0c;使用时是this.data.名称。 saveData() {wx.setStorageSync(list, this.data.list)wx.showToast({title: 存储成功,})}, 2、读取数据…
阅读更多...
【Mocreak】傻瓜式一键安装部署OFFICE教程

【Mocreak】傻瓜式一键安装部署OFFICE教程

微软 Office 办公软件安装除了官方的安装包外&#xff0c;还可以通过部署工具来安装各种版本的 Office&#xff0c;其中目前比较流行的是 Office Tool Plus 和 Office 2013-2021 C2R Install 这两个软件。 今天再分享一个类似的 Office 部署工具「Mocreak」同样傻瓜式可以一键…
阅读更多...
边缘计算网关如何实现高效数据处理与传输？-天拓四方

边缘计算网关如何实现高效数据处理与传输？-天拓四方

随着物联网&#xff08;IoT&#xff09;技术的迅猛发展&#xff0c;海量的设备接入和数据交换对传统的中心化数据处理模式提出了巨大的挑战。在这一背景下&#xff0c;边缘计算作为一种将计算任务从云端推向网络边缘的新型计算模式&#xff0c;正逐渐成为解决这一问题的有效手段…
阅读更多...
nginx 配置文件详细介绍

nginx 配置文件详细介绍

一&#xff0c; nginx 配置文件架构 上一篇 已对 main 全局配置做了详细介绍 本章对剩下的配置文件部分做介绍 二&#xff0c;event 设置 &#xff08;一&#xff09;event 相关的配置文件为 配置工作模式以及连接数 &#xff08;二&#xff09;具体表现 1&#xff…
阅读更多...
过年放鞭炮

过年放鞭炮

解法&#xff1a; 取巧 #include <iostream> #include <vector> #include <algorithm> using namespace std; #define endl \nint main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t, n;cin >> t;while (t--) {cin >> n;vec…
阅读更多...
素数筛法详解：埃氏筛和欧拉筛

素数筛法详解：埃氏筛和欧拉筛

主要讲解怎么判断一个数字是否是素数&#xff1a; 埃式筛 学习埃氏筛之前&#xff0c;我们先看一下暴力筛法&#xff0c;即对每个数都用试除法判断其是不是质数&#xff1a; 暴力筛法&#xff1a; # include <stdio.h>int main() {int st[N]; // 初始化为0&#xff0…
阅读更多...
GitLab代码库提交量统计工具

GitLab代码库提交量统计工具

1.说明 统计公司所有项目的提交情况&#xff0c;可指定分支和时间段&#xff0c;返回每个人的提交新增数、删除数和总数。 2.API 文档地址&#xff1a;http://公司gitlab域名/help/api/README.md 项目列表查询 返回示例&#xff1a; [{"id": 1, //项目ID"http…
阅读更多...
Microsoft 365自定义安装软件

Microsoft 365自定义安装软件

如图&#xff0c;在安装类型的步骤的时候&#xff0c;可以勾选自己想要的软件&#xff08;而非一股脑儿的安装一大堆自己不需要的&#xff09;。
阅读更多...
搜索引擎是如何工作的？

搜索引擎是如何工作的？

搜索引擎是如何工作的&#xff1f; 本文转自 公众号 ByteByteGo&#xff0c;如有侵权&#xff0c;请联系&#xff0c;立即删除 搜索引擎是如何工作的&#xff1f; 搜索引擎在互联网时代扮演着至关重要的角色&#xff0c;它们不仅极大地影响了人们获取信息的方式&#xff0c;还…
阅读更多...
RSA加密原理

RSA加密原理

2024.2.23 密钥对的生成过程 1、随机找两个质数 P 和 Q &#xff0c;P 与 Q 越大&#xff0c;越安全 本例取 P 67 &#xff0c;Q 71 计算他们的乘积 N P * Q 4757 转化为二进为 1001010010101&#xff0c;该加密算法即为 13 位&#xff0c;实际使用中的算法是往往是 …
阅读更多...
基于RK3399 Android11适配OV13850 MIPI摄像头

基于RK3399 Android11适配OV13850 MIPI摄像头

目录 1、原理图分析2、编写和配置设备树3、调试方法4、遇到的问题与解决5、补丁 1、原理图分析 从上图可看出&#xff0c;我们需要关心的&#xff0c;①MIPI数据和时钟接口使用的是MIPI_TX1/RX1 ②I2C使用的是I2C4总线 ③RST复位引脚使用的是GPIO2_D2 ④PWDN使用的是GPIO1_C7 ⑤…
阅读更多...
kali xrdp

kali xrdp

Kali Linux 使用远程桌面连接——xrdp&xfce_kali xfce桌面-CSDN博客 Ubuntu/Debian/Kali xrdp远程桌面黑屏/空屏/无画面解决办法 - 知乎 (zhihu.com) sudo apt-get install xrdp -y sudo apt-get install xfce4 -ysudo systemctl enable xrdp --now systemctl status xrd…
阅读更多...
最新文章

Copyright @ 2022~2023