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

目录

​编辑

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://www.rhkb.cn/news/262478.html

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

相关文章

糖尿病性视网膜病变（DR）的自动化检测和分期

糖尿病性视网膜病变（DR）的自动化检测和分期

糖尿病性视网膜病变&#xff08;DR&#xff09;的自动化检测和分期 提出背景DR的阶段及其特征 历年解法计算机视觉方法多分类方法 新的解法深度学习方法迁移学习大模型多模型集成全流程分析 总结特征1&#xff1a;图像分割特征2&#xff1a;疾病分级特征3&#xff1a;治疗建议生…
阅读更多...
Radware Alteon负载均衡-基于域名的七层负载均衡

Radware Alteon负载均衡-基于域名的七层负载均衡

Radware Alteon作为一款高性能的负载均衡器&#xff0c;其基于域名的七层负载均衡功能为众多企业提供了灵活、高效的解决方案。 该案例实现如下需求&#xff1a;客户端访问服务器&#xff0c;当访问域名为www.iisstart.com时&#xff0c;默认访问Server1&#xff0c;当配置七层…
阅读更多...
Sqoop 入门基础

Sqoop 入门基础

简介 Sqoop&#xff08;SQL to Hadoop&#xff09;是一个开源工具&#xff0c;用于在关系型数据库和Hadoop之间传输数据。它提供了一种快速高效的方式&#xff0c;将数据从关系型数据库导入到Hadoop集群进行分析&#xff0c;并支持将Hadoop集群中的数据导出到关系型数据库中。本…
阅读更多...
MAC M1安装vmware和centos7虚拟机并配置静态ip

MAC M1安装vmware和centos7虚拟机并配置静态ip

一、下载vmware和centos7镜像 1、VMWare Fusion 官网的下载地址是&#xff1a;下载地址 下载好之后注册需要秘钥&#xff0c;在官网注册后使用免费的个人秘钥 2、centos7 下载地址&#xff1a; https://biosyxh.cn:5001/sharing/pAlcCGNJf 二、虚拟机安装 直接将下…
阅读更多...
学生成绩管理系统（C语言课设 ）

学生成绩管理系统（C语言课设 ）

这个学生成绩管理系统使用C语言编写&#xff0c;具有多项功能以方便管理学生信息和成绩。首先从文件中读取数据到系统中&#xff0c;并提供了多种功能&#xff08;增删改查等&#xff09;选项以满足不同的需求。 学生成绩管理系统功能: 显示学生信息增加学生信息删除学生信息…
阅读更多...
使用 C++23 协程实现第一个 co_await 同步风格调用接口--Qt计算文件哈希值

使用 C++23 协程实现第一个 co_await 同步风格调用接口--Qt计算文件哈希值

C加入了协程 coroutine的特性&#xff0c;一直没有动手实现过。看了网上很多文章&#xff0c;已经了解了协程作为“可被中断和恢复的函数”的一系列特点。在学习过程中&#xff0c;我发现大多数网上的例子&#xff0c;要不就是在main()函数的控制台程序里演示yeild,await, resu…
阅读更多...
Jmeter基础(2) 目录介绍

Jmeter基础(2) 目录介绍

目录 Jmeter目录介绍bin目录docsextrasliblicensesprintable_docs Jmeter目录介绍 在学习Jmeter之前&#xff0c;需要先对工具的目录有些了解&#xff0c;也会方便后续的学习 bin目录 examplesCSV目录中有CSV样例jmeter.batwindow 启动文件jmeter.shMac/linux的启动文件jmete…
阅读更多...
《最新出炉》系列初窥篇-Python+Playwright自动化测试-19-处理鼠标拖拽-中篇

《最新出炉》系列初窥篇-Python+Playwright自动化测试-19-处理鼠标拖拽-中篇

1.简介 上一篇中&#xff0c;主要是介绍了拖拽的各种方法的理论知识以及实践&#xff0c;今天宏哥讲解和分享一下划取字段操作。例如&#xff1a;需要在一堆log字符中随机划取一段文字&#xff0c;然后右键选择摘取功能。 2.划取字段操作 划取字段操作就是在一段文字中随机选…
阅读更多...
分布式id实战

分布式id实战

目录 常用方式 特征 潜在问题 信息安全 高性能 UUID 雪花算法 数据库生成 美团Leaf方案 Leaf-segment 数据库方案 Leaf-snowflake 方案 常用方式 uuid雪花算法数据库主键 特征 全局唯一趋势递增信息安全 潜在问题 信息安全 如果id连续递增, 容易被爬虫, 批量下…
阅读更多...
记录 使用FFMPEG 笔记本摄像头推流

记录 使用FFMPEG 笔记本摄像头推流

一、使用 FFMPEG 测试摄像头拉流显示 # 获取摄像头名称 ffmpeg -list_devices true -f dshow -i dummy# 我笔记本上的摄像头名称如下 device_pnp_\\?\usb#vid_0408&pid_1020&mi_00#6&199e90f7&0&0000#{65e8773d-8f56-11d0-a3b9-00a0c9223196}\global# 使…
阅读更多...
蓝桥杯DP算法——区间DP（C++）

蓝桥杯DP算法——区间DP（C++）

根据题意要求的是将石子合并的最小权值&#xff0c;我们可以根据DP思想使用二维数组f[i,j]来存放所有从第i堆石子到第j堆石子合并成一堆石子的合并方式。 然后由第二个图所示&#xff0c;我们可以将i到j区间分成两个区间&#xff0c;因为将i到j合并成一个区间的前一步一定是合…
阅读更多...
戏曲文化苑|戏曲文化苑小程序|基于微信小程序的戏曲文化苑系统设计与实现(源码+数据库+文档)

戏曲文化苑|戏曲文化苑小程序|基于微信小程序的戏曲文化苑系统设计与实现(源码+数据库+文档)

戏曲文化苑小程序目录 目录 基于微信小程序的戏曲文化苑系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、微信小程序前台 2、管理员后台 &#xff08;1&#xff09;戏曲管理 &#xff08;2&#xff09;公告信息管理 &#xff08;3&#xff09;公告类型管理…
阅读更多...
京东前端笔试（附答案解答）

京东前端笔试（附答案解答）

引言 我目前本科大四&#xff0c;正在春招找前端&#xff0c;有大厂内推的友友可以聊一聊&#xff0c;球球给孩子的机会吧。 我整理了一份10w字的前端技术文档&#xff1a;https://qx8wba2yxsl.feishu.cn/docx/Vb5Zdq7CGoPAsZxMLztc53E1n0k?fromfrom_copylink &#xff0c;对…
阅读更多...
RabbitMQ监控方法以及核心指标

RabbitMQ监控方法以及核心指标

RabbitMQ监控方法以及核心指标 1. 监控指标采集2. 使用rabbimq插件采集指标2.1 3.8.0之前版本&#xff0c;使用外部插件暴露2.2 3.8.0之后版本&#xff0c;使用内置插件暴露 3. 使用rabbitmq_exporter采集指标3.1 部署rabbitmq_exporter3.2 prometheus采集rabbitmq_exporter的暴…
阅读更多...
MacBook的nginx出现13: Permission denied 的问题分析和解决办法

MacBook的nginx出现13: Permission denied 的问题分析和解决办法

同样的项目代码&#xff0c;电脑从Windows更换到了MacBook&#xff0c;发现网站的样式都没有了&#xff0c;直接访问CSS文件 http://crm.ms-test.cc/toolstatic/css/bootstrap.min.css 发现无法访问。查看Nginx错误日志&#xff1a; 说明是nginx没有权限访问这个CSS文件&#…
阅读更多...
LeetCode--代码详解 59. 螺旋矩阵 II

LeetCode--代码详解 59. 螺旋矩阵 II

59. 螺旋矩阵 II 题目 给你一个正整数 n &#xff0c;生成一个包含 1 到 n2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;[[1,2,3],[8,9,4],[7,6,5]]示例 2&#xff1a; 输入&a…
阅读更多...
Stable Diffusion 模型分享：Indigo Furry mix（人类与野兽的混合）

Stable Diffusion 模型分享：Indigo Furry mix（人类与野兽的混合）

本文收录于《AI绘画从入门到精通》专栏，专栏总目录：点这里。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八案例九案例十
阅读更多...
Recorder 实现语音录制并上传到后端（兼容PC和移动端）

Recorder 实现语音录制并上传到后端（兼容PC和移动端）

Recorder 首页&#xff1a;https://github.com/xiangyuecn/Recorder 一、安装 npm install recorder-core二、代码部分 1. HTML页面 <template><div><el-inputv-model"ttsText"type"textarea"placeholder"请输入内容"><…
阅读更多...
C#写的一个计算DCI-P3色域和SRGB的小工具

C#写的一个计算DCI-P3色域和SRGB的小工具

文章最后附带分享链接与提取码 方便需要测试屏幕的小伙伴&#xff0c;只需要输入RGB就能得到覆盖率与比率&#xff0c;W计算色温&#xff0c;不测也要写上&#xff0c;不然会报错 链接&#xff1a;https://pan.baidu.com/s/1wdmAwmwiXjNvn1tGsvy0HA 提取码&#xff1a;1234
阅读更多...
基于SpringBoot的在线拍卖系统设计与实现（源码+调试+LW+PPT）

基于SpringBoot的在线拍卖系统设计与实现（源码+调试+LW+PPT）

项目描述 临近学期结束&#xff0c;还是毕业设计&#xff0c;你还在做java程序网络编程&#xff0c;期末作业&#xff0c;老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。今天给大家介绍一篇基于SpringBoot的在线拍…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023