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语言链表的详解了,如果有错误欢迎指正

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

谷歌最强大模型Gemini 1.5 Pro免费开放了,附详细流程!

Gemini 1.5 Pro可以免费使用了。打开试了下。 下面分享一下,实际体验已经登录流程。 打开 网址,点击上方红色箭头所指的蓝色框。 https://ai.google.devhttps://ai.google.dev登录Gmail账号 输入谷歌邮箱账号,然后点击下一步。 输入密码,然

Windows文件搜索神器Everything安装配置结合内网穿透实现公网查询本地文件

文章目录 前言1.软件安装完成后&#xff0c;打开Everything2.登录cpolar官网 设置空白数据隧道3.将空白数据隧道与本地Everything软件结合起来总结 前言 要搭建一个在线资料库&#xff0c;我们需要两个软件的支持&#xff0c;分别是cpolar&#xff08;用于搭建内网穿透数据隧道…

三次握手与四次挥手到底是怎么回事?

三次握手和四次挥手是TCP/IP协议中建立和断开连接的关键步骤&#xff0c;它们是保证可靠通信的重要机制。这里将探讨这两个概念&#xff0c;并解释它们背后的原理。 三次握手 三次握手用于建立TCP连接&#xff0c;它由客户端和服务器之间发送的三个报文组成&#xff1a; 第一次…

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

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

【分享】linux下安装sunshine串流配置进行远程办公

前排提示教程内容比较短&#xff0c;废话比较多&#xff0c;需要看教程的建议直接跳目录 目录 前言&#xff08;原因&#xff09; 选择远程连接软件 三种连接软件的优劣以及体验 sunshine支持显卡 教程 注意事项 显示器 如果为远程部署 前言&#xff08;原因&#xff0…

什么是人力资源成本?人力资源成本有哪些?

人力资源成本是企业运营成本的重要组成部分&#xff0c;对企业的财务状况和经营效率有着直接影响&#xff0c;如今企业面临着持续的成本压力和效率挑战。人力资源成本不仅直接关联企业的运营效率&#xff0c;还影响着企业的长期战略发展。因此&#xff0c;如何优化人力资源成本…

8款AI绘画工具推荐,让你绘画更加生动有趣

大家好&#xff0c;我是你们的AI绘画导购员小助手&#xff01;今天我给大家带来了8款超级厉害的AI绘画工具推荐&#xff0c;它们不仅能让你的绘画更加生动有趣&#xff0c;还能让你的创作达到一个新的高度&#xff01; "爱制作AI"---这是一款非常好用的 AI 写作工具&…

C++ 优先级队列用法详解与模拟实现

文章目录 C 优先级队列用法与模拟实现介绍用法头文件1.创建优先级队列priority_queue 2. 插入元素push 3. 删除元素pop 访问顶部元素top 检查优先级队列的大小size 检查优先级队列是否为空empty 模拟实现 C 优先级队列用法与模拟实现 介绍 优先级队列&#xff08;Priority Qu…

使用SpeechRecognition和vosk处理ASR

SpeechRecognition可以支持多种模型语音转文字&#xff0c;感觉vosk还不错&#xff0c;使用起来也简单一些&#xff1b;百度也有PaddleSpeech&#xff0c;但是安装起来太麻烦&#xff0c;不是这个库版本不对就是那个库有问题&#xff0c;用起来不方便&#xff1b; 安装SpeechR…

python读取文件数据写入到数据库中,并反向从数据库读取保存到本地

学python&#xff0c;操作数据库是必不可少的&#xff0c;不光要会写python代码&#xff0c;还要会写SQL语句&#xff0c;本篇文章主要讲如何把本地txt文件中的数据读取出来并写入到对应的数据库中&#xff0c;同时将数据库单个表中的数据读出来保存在本地txt文件中。 话不多说…

测试人必看,11个非技术高频面试问题

大家都知道&#xff0c;测试岗位可是保证产品质量的重要一环。除了技术能力&#xff0c;面试官还会关注你的其他方面的素质。包括沟通能力、团队协作、解决问题等方面。 今天&#xff0c;咱们就来聊聊这些看似简单&#xff0c;实则暗藏玄机的非技术问题。 1、请你做一下自我介…

Linux系统编程---文件系统

一、文件存储 一个文件主要由两部分组成&#xff0c;dentry(目录项)和inode inode本质是结构体&#xff0c;存储文件的属性信息&#xff0c;如&#xff1a;权限、类型、大小、时间、用户、盘块位置… 也叫做文件属性管理结构&#xff0c;大多数的inode都存储在磁盘上。 少量…

Docker镜像,什么是Docker镜像,Docker基本常用命令

docker镜像 1.1什么是镜像&#xff0c;镜像基础 1.1.1 镜像的简介 镜像是一种轻量级&#xff0c;可执行的独立软件包&#xff0c;也可以说是一个精简的操作系统。镜像中包含应用软件及应用软件的运行环境&#xff0c;具体来说镜像包含运行某个软件所需的所有内容&#xff0c;…

免费领!赛盈分销联合UseePay发布《2024全球户外家居电商市场分析报告》

随着全球化的浪潮愈演愈烈&#xff0c;家居行业正在经历着深刻的变革与转型。过去几年&#xff0c;随着消费升级和科技创新的推动&#xff0c;家居行业呈现出以下几个明显趋势&#xff1a; 智能化与互联网家居 智能家居产品不断涌现&#xff0c;人们对于智能、便捷的家居生活…

Nacos 入门篇---服务端如何处理客户端的服务注册请求?(三)

一、引言 ok呀&#xff0c;上个章节我们讲了Nacos客户端的服务自动注册&#xff0c;今天我们来看看服务端接收到了客户端的服务注册请求&#xff0c;服务端都做了哪些事情&#xff5e; 二、目录 目录 一、引言 二、目录 三、回顾上节内容&#xff1a; 四、Nacos 服务代码入…

react antd 实现修改密码(原密码,新密码,再次输入新密码,新密码增加正则复杂度校验)

先看样子 组件代码&#xff1a; import React, { useState, useEffect } from react import { Row, Col, Modal, Spin, Input, Button, message, Form } from antd import { LockOutlined, EyeTwoTone, EyeInvisibleOutlined } from ant-design/icons import * as Serve from …

改进 Elastic Agent 和 Beats 中的事件队列

作者&#xff1a;Fae Charlton, Alexandros Sapranidis 内部改进如何降低 Elastic 8.13 中的内存使用。 在 8.12 版本中&#xff0c;我们引入了性能预设 —— 一种更简单的方法&#xff0c;用于调整 Elastic Agent 和 Beats 以适应各种场景。这提高了常见环境的性能&#xff0…

喜讯|我司再次获得国家发明专利,硬核科技研发成果呈加速度增长

热烈祝贺 璞华软件成功获得国家发明专利 我司自主研发成果《一种工伤案件裁决书的生成方法及装置》&#xff08;专利号&#xff1a;ZL 2019 1 1170975.8&#xff09;成功获得国家发明专利&#xff0c;2024年4月成功获得专利证书。 发明人&#xff1a;高志凯&#xff1b;杨德…

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

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

BGI | STCellBin:动植物组织细胞分割

简介 STCellbin 利用细胞核染色图像作为桥梁来获取与空间基因表达图谱对齐的细胞膜/壁染色图像。通过采用先进的细胞分割技术&#xff0c;可以获得准确的细胞边界&#xff0c;从而获得更可靠的单细胞空间基因表达谱。此次更新的增强功能为细胞内基因表达的空间组织提供了宝贵的…