当前位置： 首页 > article >正文

【数据结构】一篇带你彻底玩转 链表

article 2024/11/16 7:26:54

文章目录

  • 链表的概念及结构
  • 链表的分类
  • 链表接口的实现
    • 链表打印
    • 链表申请节点
    • 链表尾插
    • 链表头插
    • 链表尾删
    • 链表头删
    • 链表查找
    • 链表在指定位置之后插入数据
    • 链表删除指定位置之后的数据
    • 链表在指定位置之前插入数据
    • 链表删除指定位置之前的数据
    • 链表删除指定位置的数据
    • 链表的销毁

链表的概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数是据元素的逻辑顺序是通过链表中的指针链接次序实现的 。C语言结构体指针在这里得到了充分的利用，可以在节点中定义多种数据类型, 并可以根据需要进行增删查改功能.

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里?

最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空” 用NULL表示

  • 单链表的存储结构
struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
};
  • 链表存储结构图
    在这里插入图片描述
    注意:
  • 图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
  • 现实中的结点一般都是从malloc堆上申请出来的
  • 从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

在这里插入图片描述在这里插入图片描述在这里插入图片描述

  • 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
  1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
    构的子结构
    在这里插入图片描述
  1. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了
    在这里插入图片描述
  • 该章节我们讲解的是无头单向循环链表

链表接口的实现

无头+单向+非循环链表增删查改实现

链表打印

  • 链表与顺序表不同，顺序表是通过下标来访问每个元素。而链表是通过结构体存储的指针指向下一个节点来遍历整个数据的.
void SListPrint(SListNode* plist)
{
	assert(plist); //断言 判断是否为空指针
	SListNode* tmp = plist; 
	while (tmp != NULL)  //遍历整个链表，直到tmp指针指向空
	{
		printf("%d-> ", tmp->data); //打印节点数据
		tmp = tmp->next;	//将指针指向下一个结点
	}
	printf("NULL\n");
}

链表申请节点

  • 链表添加一个节点数据时候，每次都要写一段代码，这样做是不是太繁琐了，我们可以封装一个函数来解决问题，每次添加一个节点时，将结点存放的数据置为需要存放的值，在将结构体存放节点的地址置为NULL, 需要增加节点时调用一下改函数即可。
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); //申请一个结构体节点
	
	//判断是否申请成功
	if (newnode == NULL)
		perror("malloc:\n");
	
	newnode->data = x;
	newnode->next = NULL;
	//申请成功返回节点
	return newnode;
}

链表尾插

  • 在单链表进行尾插时，我们需要遍历整个链表直到找到最后一个节点才可以进行尾插，但如果此时链表为空时，我们直接插入节点数据即可。

错误代码示例：
相信许多人会写出这样的代码在这里插入图片描述 错误原因:

tail最后找到NULL了，tail和newnode 都是一个临时变量，把newnode给了tail，tail存放的是newnode里面的内容，tail出了作用域就不存在了。把newnode给了tail 并不会链接上链表的节点。最后还会存在内存泄漏. 所有我们这里要使用结构体指针来链接节点,正确写法应该让上一节节点找下一个节点的地址，让tmp->next （next这些节点都是在堆上的，并不会销毁） 找尾 ，将结构体指针指向的尾结点(NULL)指向新结点

正确代码示例

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	//申请一个节点
	SListNode* newnode = BuySListNode(x);
	
	//当链表还没有节点时为空时，我们直接插入数据即可.
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		//进行找尾进行尾插
		//找到指针指向的尾结点(NULL)指向新结点
		SListNode* tmp = *pplist;
		while (tmp->next != NULL)  
		{
			tmp = tmp->next;
		}
		tmp->next = newnode;//将尾结点中存放的指针置为插入结点的地址即可链接上
	}
}

链表头插

  • 头插逻辑相对简单.只需要申请一个节点，让节点的指针指向头指针，在把头指针指向申请节点的位置
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	//申请一个节点
	SListNode* newnode = BuySListNode(x);
	
	newnode->next = *pplist;
	*pplist = newnode;
}

链表尾删

  • 尾删的细节较多一点
    1: 链表为空时，无须删除
    2: 链表只有一个元素时，做特需处理
    3: 正常处理

这里提供两种方法给大家参考

  • 方法一： 前后指针
    使用一个指向为空的指针 prev和一个指向头节点的指针cur,当cur->next指向的不是NULL时我们让prev 指向cur节点，而cur指向cur的下一个节点，循环直到cur->next指向null时，prev->next指向的就是我们要删除的最后一个节点.
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);  //断言 判断是否为空指针
	
	//当只有一个节点时
	if ((*pplist)->next == NULL)
	{
	//只有一个结点，直接释放该结点，然后将结点置为NULL
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* cur = *pplist; 
		SListNode* prev = NULL;
		while (cur->next != NULL)
		{
			prev = cur;	
			cur = cur->next; //循环遍历
		}
		free(prev->next); //释放尾结点
		prev->next = NULL;
	}
}
  • 方法二: 知需判断cur->next->next是否为空，如果为空释放cur->next。当链表只有两个节点时循环不进去，直接释放cur->next.
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);//断言 判断是否为空指针

	//只有一个结点，直接释放该结点，然后将结点置为NULL
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		SListNode* cur = *pplist;
		while (cur->next->next != NULL)
		{
			cur = cur->next;//循环遍历
		}
		free(cur->next); //释放尾结点
		cur->next = NULL;
	}
}

链表头删

  • 链表头删逻辑也简单，只需要注意一下链表是否为空。然后用一个临时变量保存头指针的->next,然后在把头指针销毁，把头指针给回临时变量即可.
// 单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(*pplist);  //断言 判断是否为空指针
	
	SListNode* tmp = (*pplist)->next;//保存头指针的下一个节点
	free(*pplist); //销毁释放头指针
	*pplist = tmp; 头指针指向释放前的下一个节点
}

链表查找

  • 获得链表某个节点的数据思路也较简单
    1： 定义一个cur指针指向头节点，不断指向下一个节点
    2： 如查找成功，返回节点cur的数据
    3： 如cur指向Null已经遍历完了，则说明查找的内容不存在，返回空指针。
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);//断言 判断是否为空指针
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

链表在指定位置之后插入数据

  • 先把新节点的next 指向pos->next, 然后再把pos->next 更新成新节点.
void SLInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);//断言 判断是否为空指针

	SListNode* newnode = BuySListNode(x);//申请一个节点
	newnode->next = pos->next; //新节点指向pos位置的下一个节点
	pos->next = newnode; //pos下一个位置插入新节点
}

链表删除指定位置之后的数据

  • 整体逻辑就是保存将要删除位置下一个节点的位置，把pos->next后的位置在链接上要删除位置的下一个节点。 如果pos下一个节点为空，无需删除直接返回即可.
void SListEraseAfter(SListNode* pos)
{
	assert(pos);//断言 判断是否为空指针
	
	if (pos->next == NULL) //如果pos下一个节点为空，无须删除
		return;
	SListNode* cur = pos->next->next;//保存要删除位置的下一个节点
	free(pos->next); //释放pos之后的数据
	pos->next = cur; //链接上要删除位置的下一个节点
}

链表在指定位置之前插入数据

  • 算法思路：
    1： 当指定位置为第一个元素时，这时我们只需调用一下头插函数即可.
    2： 遍历链表，找到pos上一个节点的数据.
    3： 找到上一个节点数据，把新节点的next指向指定位置，在把找到的节点指向新开辟的节点，这样就可以链接上了。
void SLInsertfront(SListNode** pplist, SListNode* pos, SLTDateType x)
{
	assert(pos);//断言 判断是否为空指针
	if (*pplist == pos) //当pos位置是第一个节点数据时，那就是头插了
	{
		SListPushFront(pplist, x);//头插
	}
	else
	{
		SListNode* tmp = *pplist;
		while (tmp->next != pos)
		{
			tmp = tmp->next;//循环遍历
		}
		SListNode* newnode = BuySListNode(x);
		newnode->next = pos; //把新节点的next指向指定位置
		tmp->next = newnode; //找到的节点指向新开辟的节点
	}
}

链表删除指定位置之前的数据

  • 整体思路：
  • 1: 当指定位置pos是第一个节点时，无需删除，直接返回即可。
  • 2: 当指定位置pos是第二个节点数据时，只需要进行头删即可。
  • 3: 遍历数组，找到pos 之前要删除节点数据的上一个节点。把该节点的next（就是pos上一个节点的数据）直接销毁释放掉，再把找到的节点next重新链接上pos.
void SLErasefront(SListNode** pplist, SListNode* pos)
{
	assert(pos); //断言 判断是否为空指针

	if (pos == *pplist) //当指定是第一个节点时，无需再删除，直接返回.
	{
		printf("pos位置前为空\n");
		return;
	}
	else if ((*pplist)->next == pos)//当指定位置pos是第二个节点数据时，只需要进行头删即可
	{
		SListPopFront(pplist);//头删
	}
	else
	{
		SListNode* tmp = *pplist;
		while (tmp->next->next != pos)
		{
			tmp = tmp->next; //遍历循环
		}
		free(tmp->next);//释放pos之前的节点数据
		tmp->next = pos; //链接上pos
	}
}

链表删除指定位置的数据

  • 思路:
    1: 当指定位置pos是第一节点数据时，直接使用头删即可。
    2: 查找指定位置pos上一个节点位置，再把该位置的next链接上pos的next位置.
    3: 释放指定位置的数据。
void SLErase(SListNode** pplist, SListNode* pos)
{
	assert(pos);//断言 判断是否为空指针
	
	if (pos == *pplist)//当pos是第一节点数据时，直接使用头删即可
	{
		SListPopFront(pplist);//头删
	}
	
	else
	{
		//
		SListNode* tmp = *pplist;
		while (tmp->next != pos)//找pos上一个节点
		{
			tmp = tmp->next;
		}
		tmp->next = pos->next;//将需要删除的结点的上一个结点的next指向需要删除的下一个结点
		free(pos);//释放指定位置的数据
		pos = NULL;
	}
}

链表的销毁

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

  • 思路：保存当前节点的下一个结点的地址，释放当前结点，再将指针指向刚刚保留的结点，如此循环直到为空。链表销毁成功.
// 单链表的销毁
void SListDestroy(SListNode* plist)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur != NULL)
	{
		SListNode* next = cur->next; //保存下一个节点
		free(cur); //释放当前指定
		cur = next; //指向下一个节点
	}
}

http://www.kler.cn/a/16164.html

相关文章：

  • 使用热冻结数据层生命周期优化在 Elastic Cloud 中存储日志的成本
  • 力扣 LeetCode 541. 反转字符串II（Day4：字符串）
  • 从python源码到可自动更新软件
  • Mysql每日一题（行程与用户，困难※）
  • 前端面试笔试（二）
  • SpringBoot（十八）SpringBoot集成Minio
  • 电脑CPU/GPU处理器知识普及
  • 【vueCms】vueCms_xg后台管理系统(开源)
  • QString类方法和变量简介(全)
  • Spring注解开发
  • Python中True、False、None的判断(避坑)
  • Http1.0 、1.1、2.0、3.0的区别
  • 《企业级Linux高可用负载均衡集群实践真传》目录
  • LeetCode：面试题 02.07. 链表相交
  • 数据结构基础day9
  • 书接上回，接着研究当今世上缓存第一人
  • pnpm 实现 Monorepo 一些操作命令
  • Java 异常处理、日志
  • Linux od命令
  • ESP32-CAM：TinyML 图像分类——水果与蔬菜
  • 【群智能算法】一种改进的蜣螂优化算法IDBO[2]【Matlab代码#18】
  • 浅谈Kubernetes集群外部通信—Ingress方式
  • 【Java笔试强训 2】
  • Python 练习实例希望这些例子可以帮助您
  • 网络编程 总结二
  • sql注入（三）绕过方法及防御手段