C语言单链表详解

链表和顺序表的区别

顺序表的底层存储空间是连续的，链表的底层存储空间是不连续的，链表的每个节点需要额外的指针来指向下一个节点，占用更多的存储空间。
顺序表的随机访问性能好，时间复杂度为O(1)，链表的随机访问性能差，时间复杂度为O(n)。
顺序表的插入和删除操作需要移动大量的元素，时间复杂度为O(n)，链表的插入和删除操作只需要修改指针，时间复杂度为O(1)。
顺序表适合于查找为主的静态操作，链表适合于插入和删除为主的动态操作。

总的来说顺序表的底层是数组，而链表的底层是指针也就是地址，数组在内存中是连续存放的，所以顺序表的随机访问性要比链表好，而链表是以地址的方式存放在内存中，有可能一个空间与另一个空间的地址离的非常远，以指针的形式进行访问，所以随机访问性比较差，我们可以把顺序表和链表类比成动车和火车一节动车组是由8节车厢组成，车厢与车厢之间不能编组，他们8节就是一个整体就像数组一样，而火车就不同了，火车车厢之间可以灵活编组，就像链表的各个节点一样。
在这里插入图片描述

链表存储的优缺点

**优点：**空间利用率高，需要一个空间就分配一个空间，数据与数据之间以指针的形式联系，增添空间方便，只需要前一个结点和增加的节点，以及后一个节点，地址与地址之间形成联系手拉手，而不像顺序表那样需要前后移动来增加删除数据
**缺点：**存储密度小，每个节点的指针存放区域要额外申请空间，随机访问性差

链表的实现

下面是代码，会分部讲解

# include<stdio.h>
# include<stdlib.h>
# include<assert.h>
typedef int SLdatatype;
struct SListnode
{SLdatatype data;struct SListnode* next;
};
typedef struct SListnode SLnode;SLnode* create_memspace(SLdatatype x);//申请空间void pushback(SLnode** phead, SLdatatype x);//尾插void SLprint(SLnode* phead);//打印void del_pushback(SLnode** phead);//尾删void head_del(SLnode** phead);//头删void pushhead(SLnode** phead, SLdatatype x);//头插void pushpos(SLnode* pos, SLdatatype x);//指定位置之后插入void appoint_push(SLnode** phead, SLdatatype x, SLnode* pos);//在指定位置之前插入SLnode* find_data(SLnode* phead, SLdatatype x);//查找节点void del_pos_appoint(SLnode** phead, SLnode* pos);//删除节点void del_appoint_after(SLnode* pos);//删出之后的节点//销毁链表
void del_slist(SLnode** phead);
void SLprint(SLnode* phead)//打印链表{SLnode* printlist = phead;while (printlist != NULL){printf("%d->", printlist->data);printlist = printlist->next;}printf("NULL\n");
}
//申请空间
SLnode* create_memspace(SLdatatype x)
{SLnode* newspace = (SLnode*)malloc(sizeof(SLnode));if (newspace == NULL){perror("malloc");exit(1);}newspace->data = x;newspace->next = NULL;return newspace;
}//头插
void pushhead(SLnode** phead, SLdatatype x)
{assert(phead);SLnode* newspace = create_memspace(x);newspace->next = *phead;*phead = newspace;
}
//尾插
void pushback(SLnode** phead, SLdatatype x)
{assert(phead);SLnode* newspace = create_memspace(x);SLnode* pfind_tail = *phead;if (*phead == NULL){*phead = newspace;}else{while (pfind_tail->next != NULL){pfind_tail = pfind_tail->next;}pfind_tail->next = newspace;}
}
//尾删
void del_pushback(SLnode** phead)
{assert(phead);if ((*phead)->next == NULL){free(*phead);}else{SLnode* pfind_tail = *phead;//尾巴节点SLnode* pfind_previous = *phead;//基于尾巴节点的上一个节点while (pfind_tail->next != NULL){pfind_previous = pfind_tail;pfind_tail = pfind_tail->next;}pfind_previous->next = NULL;free(pfind_tail);pfind_tail = NULL;}
}
//头删
void head_del(SLnode** phead)
{assert(phead && *phead);SLnode* new_next = (*phead)->next;free(*phead);*phead = new_next;
}
//在指定位置之前插入
void appoint_push(SLnode** phead, SLdatatype x, SLnode* pos)
{assert(*phead && phead);SLnode* newspace = create_memspace(x);SLnode* find_appoint = *phead;if (*phead == pos){pushhead(phead, x);}else{while (find_appoint->next != pos){find_appoint = find_appoint->next;}newspace->next = pos;find_appoint->next = newspace;}
}
//查找
SLnode* find_data(SLnode* phead, SLdatatype x)
{SLnode* find_pdata = phead;while (find_pdata->next != NULL){if (find_pdata->data == x){return find_pdata;}find_pdata = find_pdata->next;}return NULL;
}
//在指定位置后插入
void pushpos(SLnode* pos, SLdatatype x)
{assert(pos);SLnode* newspace = create_memspace(x);newspace->next = pos->next;pos->next = newspace;
}
//删除指定节点
void del_pos_appoint(SLnode** phead, SLnode* pos)
{assert(phead && *phead && pos);SLnode* pfind_previous = *phead;if (pos == *phead){head_del(phead);}else{while (pfind_previous->next != pos){pfind_previous = pfind_previous->next;}pfind_previous->next = pos->next;free(pos);pos = NULL;}
}
//删除指定位置后一个
void del_appoint_after(SLnode* pos)
{assert(pos && pos->next);SLnode* temp_del = pos->next;pos->next = temp_del->next;free(temp_del);temp_del = NULL;
}
//销毁链表
void del_slist(SLnode** phead)
{assert(phead && *phead);SLnode* appoint_pervious = *phead;while (appoint_pervious->next != NULL){SLnode* next = appoint_pervious->next;free(appoint_pervious);appoint_pervious = next;}*phead = NULL;
}

测试代码

void test(){SLnode* plist = NULL;pushback(&plist, 1);pushback(&plist, 2);pushback(&plist, 3);SLprint(plist);del_pushback(&plist);SLprint(plist);head_del(&plist);SLprint(plist);pushhead(&plist, 5);SLprint(plist);pushhead(&plist, 3);pushhead(&plist, 2);	SLprint(plist);SLnode* find = find_data(plist, 2);pushpos(find, 5);pushpos(find, 9);SLprint(plist);appoint_push(&plist,34,find);SLprint(plist);del_pos_appoint(&plist, find);SLprint(plist);SLnode* find2 = find_data(plist, 5);SLprint(plist);del_appoint_after(find2);SLprint(plist);del_slist(&plist);
}int main()
{test();return 0;
}

代码讲解

链表的结构体声明

typedef int SLdatatype;
struct SListnode
{SLdatatype data;struct SListnode* next;
};
typedef struct SListnode SLnode;

这里我们创建了一个链表结构体，他的数据类型是int我们用来类型定义把他定义成 SLdatatype这样做的目的是为了以后方便修改链表中存放的数据，struct SListnode*next
这个就是存放下一个链表节点的指针。

typedef struct SListnode SLnode;

这里我们把链表重命名为SLnode这样是为了方便书写代码。

申请内存空间

SLnode* create_memspace(SLdatatype x)
{SLnode* newspace = (SLnode*)malloc(sizeof(SLnode));if (newspace == NULL){perror("malloc");exit(1);}newspace->data = x;newspace->next = NULL;return newspace;
}

这里我们用了一个malloc函数来申请内存空间为什么吧用realloc，那是由于这里我们不需要对空间进行扩容，不像顺序表那样，这里就申请一个定长空间就可以了返回类型是一个结构体指针SLnode*
然后下面进行了一个if判断看看空间有没有申请成功，再来看看下面的代码

	newspace->data = x;newspace->next = NULL;

在这里插入图片描述
这里通过指针的形式来访问结构体，给新申请的空间把值存放进去。

头插入

void pushhead(SLnode** phead, SLdatatype x)
{assert(phead);SLnode* newspace = create_memspace(x);newspace->next = *phead;*phead = newspace;
}

这里我们传了一个参数是一个二级指针，为什么要传二级指针，那是因为我们头部插入会改变原始指针指向的位置，所以要传一个二级指针，不能传一个一级指针，如果传了一个一级指针，对一级指针解引用就得到第一个节点只能修改该指针所指向的值，而不能修改指针本身，就不能完成修改指针原始指向的位置了

然后我们assert断言了一下判断传过来的指针不能为空。
在下面就是申请内存空间了
关于下面两行节点之间的链接看下面这张图

newspace->next = *phead;*phead = newspace;

在这里插入图片描述

尾插入

void pushback(SLnode** phead, SLdatatype x)
{assert(phead);SLnode* newspace = create_memspace(x);SLnode* pfind_tail = *phead;if (*phead == NULL){*phead = newspace;}else{while (pfind_tail->next != NULL){pfind_tail = pfind_tail->next;}pfind_tail->next = newspace;}
}

同样这里的参数是一个二级指针，因为这里的尾插入可以也会修改原始指针指向的位置，如果在链表的开始没有任何数据存储的情况下执行尾插入，就和执行头插入一样需要修改原始指针的指向。assert断言和申请空间我们就跳过讲解，来看看这段代码

SLnode* pfind_tail = *phead;

尾插需要通过寻找链表的尾部所以我们把第一个头节点的指针赋值给了我们需要寻找链表尾部的指针SLnode* pfind_tail

if (*phead == NULL)
{*phead = newspace;
}

这里就是判断第一个头节点是不是空，如果是就直接把新增加的空间赋值给头节点。
如果不是就进入下面else通过while进行找尾。

else
{while (pfind_tail->next != NULL){pfind_tail = pfind_tail->next;}pfind_tail->next = newspace;
}

在这里插入图片描述

头删除

void head_del(SLnode** phead)
{assert(phead && *phead);SLnode* new_next = (*phead)->next;free(*phead);*phead = new_next;
}

这里我们同样传了个二级指针过来，这里头删也要改变原始指针指向的位置assert(phead && *phead);这里断言了两个一个是phead另一个是 phead这样是为了防止链表不能为空，还有指向链表的头节点也不能为空。这样删除才有意义，我们这里创建了一个临时变量SLnode new_next来存放(phead)->next的值，最后在把原始phead给释放了，再把new_next赋值给phead，这样就完成了头删除。
在这里插入图片描述

尾删除

void del_pushback(SLnode** phead)
{assert(phead && *phead);if ((*phead)->next == NULL){free(*phead);}else{SLnode* pfind_tail = *phead;//尾节点SLnode* pfind_previous = *phead;//基于尾节点的上一个节点while (pfind_tail->next != NULL){pfind_previous = pfind_tail;pfind_tail = pfind_tail->next;}free(pfind_tail);pfind_previous->next = NULL;pfind_tail = NULL;}
}

这里的assert断言和上面一样的解释，然后下面一个if判断，判断头节点的下一个节点是不是空指针，如果是就代表链表只有一个节点直接释放掉就可以了，如果不是我们就需要创建两个指针变量一个是当前节点，另一个是基于当前节点的上一个节点这样是为了在尾删的时候重新创建链表的新的尾节点，也就是尾节点的上一个节点。
在这里插入图片描述

查找节点

SLnode* find_data(SLnode* phead, SLdatatype x)
{SLnode* find_pdata = phead;while (find_pdata->next != NULL){if (find_pdata->data == x){return find_pdata;}find_pdata = find_pdata->next;}return NULL;
}

查找节点，这里我们创建了一个find_data的结构体指针，把头节点赋值给了他，这样我们就不用动头节点指向的位置，这样安全一些，然后按照节点里面存放的数据进行查找，用了while循环在链表节点里面遍历如果找到了就返回当前节点的指针，如果未找到就返回NULL空指针

在指定位置前插入数据

void appoint_push(SLnode** phead, SLdatatype x, SLnode* pos)
{assert(*phead && phead);SLnode* newspace = create_memspace(x);SLnode* find_appoint = *phead;if (*phead == pos){pushhead(phead, x);}else{while (find_appoint->next != pos){find_appoint = find_appoint->next;}newspace->next = pos;find_appoint->next = newspace;}
}

这里就要结和查找节点一起来讲了，先通过查找节点函数来找到该节点，然后在在此节点之前插入数据，这里我们用了个if判断语句来判断是不是头插，如果要在此节点之前插入的节点是phead的话就执行头插，如果不是就从头开始找，直到找到那个节点为止
在这里插入图片描述

指定位置后插入

void pushpos(SLnode* pos, SLdatatype x)
{assert(pos);SLnode* newspace = create_memspace(x);newspace->next = pos->next;pos->next = newspace;
}

在指定位置后插入就比较简单了，这里我们就不需要传头节点，这里我们假定pos是存在的，因为在调用pos节点的时候会执行查找节点，如果查找的节点为空，那么这里就只需要断言一下pos节点就行了。
在这里插入图片描述

删除指定节点

void del_pos_appoint(SLnode** phead, SLnode* pos)
{assert(phead && *phead && pos);SLnode* pfind_previous = *phead;if (pos == *phead){head_del(phead);}else{while (pfind_previous->next != pos){pfind_previous = pfind_previous->next;}pfind_previous->next = pos->next;free(pos);pos = NULL;}
}

这里的删除和上面的代码类似只不过多了一个断言pos，if判断语句里面还是一样的如果POS是头节点的话就执行头删如果不是就找POS节点，找到了就把pos的上一个节点和pos的下一个节点联系起来，然后在把POS节点给释放掉。
在这里插入图片描述

删除指定位置的后一个

void del_appoint_after(SLnode* pos)
{assert(pos && pos->next);SLnode* temp_del = pos->next;pos->next = temp_del->next;free(temp_del);temp_del = NULL;
}

这里和指定位置后插入一样简单，这里我们的参数只有POS，我们需要断言POS和POS->next，然后要创建一个临时指针变量，用来存放pos的下一个节点temp_del->next相当于pos->next->next也就是pos节点后面的后面一个节点，就是要删除的节点的后一个节点。
最后把把pos->下一个节点赋值给了temp_del->next，这样就可以删除掉pos的下一个节点了，让pos与要删除的下一个节点手拉手起来了。
在这里插入图片描述

销毁链表

void del_slist(SLnode** phead)
{assert(phead && *phead);SLnode* pcur = *phead;while (appoint_pervious->next != NULL){SLnode* next = pcur->next;free(appoint_pervious);pcur = next;}*phead = NULL;
}

最后就是销毁链表了，把链表所占用的空间还给操作系统，循环销毁直到下一个节点为空。注意销毁的时候要存放下一个节点的指针，不然会找不到。

以上就是C语言链表的详解了，如果有错误欢迎指正

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

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

相关文章

Linux系统搭建FastDFS文件服务结合内网穿透实现公网访问本地文件

Linux系统搭建FastDFS文件服务结合内网穿透实现公网访问本地文件

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…
阅读更多...
在个人电脑上,本地部署llama2-7b大模型

在个人电脑上,本地部署llama2-7b大模型

文章目录 前言原理效果实现 前言 我想也许很多人都想有一个本地的ai大语言模型,当然如果能够摆脱比如openai,goole,baidu设定的语言规则,可以打破交流界限,自由交谈隐私之类的,突破规则,同时因为部署在本地也不担心被其他人知道,那最好不过了 那究竟有没有这样的模型呢? llam…
阅读更多...
Oracle 数据库 count的优化-避免全表扫描

Oracle 数据库 count的优化-避免全表扫描

Oracle 数据库 count的优化-避免全表扫描 select count(*) from t1; 这句话比较简单&#xff0c;但很有玄机&#xff01;对这句话运行的理解&#xff0c;反映了你对数据库的理解深度&#xff01; 建立实验的大表他t1 SQL> conn scott/tiger 已连接。 SQL> drop table …
阅读更多...
树莓派安装Nginx服务结合内网穿透实现无公网IP远程访问

树莓派安装Nginx服务结合内网穿透实现无公网IP远程访问

文章目录 1. Nginx安装2. 安装cpolar3.配置域名访问Nginx4. 固定域名访问5. 配置静态站点 安装 Nginx&#xff08;发音为“engine-x”&#xff09;可以将您的树莓派变成一个强大的 Web 服务器&#xff0c;可以用于托管网站或 Web 应用程序。相比其他 Web 服务器&#xff0c;Ngi…
阅读更多...
解决动态规划问题

解决动态规划问题

文章目录 动态规划的定义动态规划的核心思想青蛙跳阶问题解法一&#xff1a;暴力递归解法二&#xff1a;带备忘录的递归解法&#xff08;自顶向下&#xff09;解法三&#xff1a;动态规划&#xff08;自底向上&#xff09; 动态规划的解题套路什么样的问题考虑使用动态规划&…
阅读更多...
OR36 链表的回文结构

OR36 链表的回文结构

描述 对于一个链表&#xff0c;请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法&#xff0c;判断其是否为回文结构。 给定一个链表的头指针A&#xff0c;请返回一个bool值&#xff0c;代表其是否为回文结构。保证链表长度小于等于900。 测试样例&#xff1a; 1->…
阅读更多...
【C++成长记】C++入门 | 类和对象（中） |类的6个默认成员函数、构造函数、析构函数

【C++成长记】C++入门 | 类和对象（中） |类的6个默认成员函数、构造函数、析构函数

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;C❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、类的6个默认成员函数 二、构造函数 1、概念 2、特性 三、析构函数 1、概念 2、特性 一、…
阅读更多...
R语言 多组堆砌图

R语言 多组堆砌图

目录 数据格式 普通绘图 添加比例 R语言 堆砌图_r语言堆砌图-CSDN博客 关键点在于数据转换步骤和数据比例计算步骤&#xff0c;然后个性化调整图。 ①data <- melt(dat, id.vars c("ID"))##根据分组变为长数据 ②#计算百分比## data2 <- ddply(data, …
阅读更多...
【数据结构】第三节：单链表

【数据结构】第三节：单链表

前言 本篇要求掌握的C语言基础知识&#xff1a;指针、结构体 目录 前言 单链表 概念 对比链表和顺序表 创建链表 实现单链表 准备工作 打印链表 创建节点并初始化 尾插 二级指针的调用 尾插代码 头插 尾删 头删 查找&#xff08;返回节点&#xff09; 在指定位…
阅读更多...
Vue笔记 2

Vue笔记 2

数据代理 数据代理&#xff1a;通过一个对象代理对另一个对象中属性的操作&#xff08;读/写&#xff09; let obj{x:100} let obj2{y:200} Object.defineProperty(obj2,x,{get(){return obj.x},set(value){obj.x value} })Vue中的数据代理 Vue中的数据代理&#xff1a; 通…
阅读更多...
Java集合（一）--Map（2）

Java集合（一）--Map（2）

ConcurrentHashMap与HashTable 底层实现 在JDK1.7时&#xff0c;底层采用的是分段数组&#xff0b;链表的形式&#xff0c;在JDK1.8之后&#xff0c;采用的是与HashMap相同的形式&#xff0c;数组链表/红黑树。而HashTable采用的是数组链表的形式。 如何实现线程安全 Concu…
阅读更多...
OpenCV4.9图像金字塔

OpenCV4.9图像金字塔

目标 在本教程中&#xff0c;您将学习如何&#xff1a; 使用 OpenCV 函数 pyrUp()和 pyrDown()对给定图像进行下采样或上采样。 理论 注意 下面的解释属于 Bradski 和 Kaehler 的 Learning OpenCV 一书。 通常&#xff0c;我们需要将图像转换为与原始图像不同的大小。为此…
阅读更多...
spring boot 集成rocketMq + 基本使用

spring boot 集成rocketMq + 基本使用

1. RocketMq基本概念 1. NameServer 每个NameServer结点之间是相互独立&#xff0c;彼此没有任何信息交互 启动NameServer。NameServer启动后监听端口&#xff0c;等待Broker、Producer、Consumer连接&#xff0c; 相当于一个路由控制中心。主要是用来保存topic路由信息&#…
阅读更多...
Blender表面细分的操作

Blender表面细分的操作

在使用Blender的过程中，刚开始创建的模型，都会比较少面，这样操作起来比较流畅，减少电脑的计算量，当设计快要完成时，就会增加表面细分，这样更加圆滑，看起来更加顺眼。 比如创建一个猴头，它会默认显示如下： 从上图可以看到，有一些表面会比较大，棱角很多。 这时候你…
阅读更多...
微商商城源码小程序好用么？

微商商城源码小程序好用么？

商城APP作为电子商务行业的重要组成部分&#xff0c;已经成为了人们购物的主要方式之一。为了在竞争激烈的市场中脱颖而出&#xff0c;开发一款专业且思考深度的商城APP方案显得尤为关键。本文将从专业性和思考深度两个方面&#xff0c;探讨商城APP的开发方案。 一、专业性的重…
阅读更多...
CloudCompare——win11配置CloudComPy

CloudCompare——win11配置CloudComPy

CloudComPy配置 1 基本环境介绍2 安装Anaconda2.1 下载anaconda2.2 安装anaconda2.3 配置镜像源2.4 更改虚拟环境的默认创建位置2.5 其他问题2.5.1 激活自己创建的环境提示&#xff1a;系统找不到指定的路径2.5.2 InvalidVersionSpecError: Invalid version spec: 2.72.5.3 卸载…
阅读更多...
如何解决网站建设打开速度慢的问题？

如何解决网站建设打开速度慢的问题？

如何解决网站建设打开速度慢的问题&#xff1f;在浏览网站的时候&#xff0c;网站打开速度的快慢也是能够直接影响到用户的体验感的。因为网站打开速度太慢&#xff0c;不仅浪费了大家的时间&#xff0c;同时还容易消耗浏览者的很大一部分耐心。 所以说不管是对于企业来说&…
阅读更多...
hive了解系列一

hive了解系列一

“ 随着智能手机的普及&#xff0c;互联网时代红利的爆发&#xff0c;用户数量和产生的数据也越发庞大。为了解决这个问题&#xff0c;提高数据的使用价值。 Hadoop生态系统就被广泛得到应用。 在早期&#xff0c;Hadoop生态系统就是为处理如此大数据集而产生的一个合乎成本效益…
阅读更多...
C++ 红黑树模拟实现

C++ 红黑树模拟实现

&#x1f493;博主CSDN主页:麻辣韭菜&#x1f493;   ⏩专栏分类&#xff1a;C知识分享⏪   &#x1f69a;代码仓库:C高阶&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学习更多C知识   &#x1f51d;&#x1f51d; 前言 前面我们实现了AVL树&#xff0c;发明AVL树…
阅读更多...
蓝桥杯备赛刷题——css

蓝桥杯备赛刷题——css

新鲜的蔬菜 这题需要使用grid 我不会 去学一下 一.什么是grid Grid 布局与 Flex 布局有一定的相似性&#xff0c;都可以指定容器内部多个项目的位置。但是&#xff0c;它们也存在重大区别。 Flex 布局是轴线布局&#xff0c;只能指定"项目"针对轴线的位置&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023