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

【初阶数据结构】探索数据的多米诺链：单链表

article 2025/1/21 6:17:16

文章目录

  • 1.链表
    • 1.1 概念及结构
    • 1.2 分类
  • 2.单链表接口实现
    • 2.1 单链表节点创建
    • 2.2 单链表打印
    • 2.3 单链表尾插
    • 2.4 单链表头插
    • 2.5 单链表尾删
    • 2.6 单链表头删
    • 2.7单链表查找
    • 2.8 单链表在pos位置插入x
      • 2.8.1 pos前
      • 2.8.2 pos后
    • 2.9单链表在pos位置删除x
      • 2.9.1 pos前
      • 2.9.2 pos后
    • 2.2.10 单链表销毁
  • 3.代码展示
    • 3.1 SList.h
    • 3.2 SList.c
  • 希望读者们多多三连支持
  • 小编会继续更新
  • 你们的鼓励就是我前进的动力！

本篇介绍线性表链表中的单链表，链表由一系列节点组成，每个节点包含数据和指向下一个节点（对于单链表）或前后节点（对于双向链表）的指针

1.链表

1.1 概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

请添加图片描述
链式结构的逻辑一般是连续的，但是在物理存储上不一定是连续的，因为每个节点都是从堆上申请来的，从堆上申请的空间要根据实际情况分配空间，两次申请可能是连续的也有可能不是连续的

简单来说，每个节点都存储了下一个节点的地址，即能找到下一个节点，就形成了链表

我们还需要了解几个概念：

🚩头结点

图中的plist就是头结点，位于链表的起始位置，但不存储实际的有效数据(有效数据指的是结构体的内的数据，而不是结构体地址)，主要作用是作为链表的入口，通过它的指针域来指向链表中的第一个实际存储数据的节点

🚩首节点

首节点就是跟在头节点后的链表中第一个存储实际有效数据的节点

🚩哨兵位

哨兵位和头结点类似，通常不存储实际数据，存储地址，哨兵位可以看成一个灵活的节点，可以在链表任何位置方便进行增删查改操作

每个节点的结构体：

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

1.2 分类

链表有三种分类方式
🚩⑴单向或双向

请添加图片描述

🚩⑵带头或不带头

请添加图片描述

🚩⑶循环或者非循环

请添加图片描述

这三种情况能组合出8种链表，这里我们只介绍两种常用的链表

请添加图片描述
无头单向非循环链表： 结构简单，实现麻烦，通常在面试笔试中以题目形式出现比较多(因为其他出成题目太难了)，单链表也更多的作为底层结构来进行算法应用

带头双向循环链表： 结构复杂，实现简单，这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

2.单链表接口实现

2.1 单链表节点创建

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}

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

	return newnode;
}

顺序表中我们空间不够时需要不断扩容，链表中的节点申请函数就是这种类似的效果，但是顺序表是对它底层的数组进行二倍扩容，而节点申请函数一次性只能申请一个节点，用一个给一个，间接避免了空间浪费，注意返回的是新节点的地址

2.2 单链表打印

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while(cur->next != NULL)会遗漏最后一个数据
	//while(cur != NULL)也可以这样写
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
		//cur++只有数组才这么写
	}
	printf("NULL\n");
}

先传入头结点，然后我们需要一个cur指针作为移动指针来遍历单链表中的数据，每个节点的next都存储了下一个节点的地址，所以循环赋值就可以实现单链表的移动，最后一个节点指向的是空指针

🔥值得注意的是： 顺序表的打印需要断言传入的结构体指针是因为该指针涉及到访问，万一传入的空指针，会造成非法访问；链表的打印有可能该链表本来就是空的，空链表也是能打印的，而且也不涉及指针访问，所以加断言反而不合理

2.3 单链表尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	//分没有节点，和有节点的情况
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

凡是涉及增加删除节点的操作，都要考虑是否为空的情况要不要特别考虑，因此这里为空时直接将头指针和新节点链接即可；不为空时循环遍历找到最后一个节点，将最后一个节点和新节点连接

🔥值得注意的是： 循环判断条件为tail->next != NULL，因为为空时可能要修改头指针存的地址，所以应该传二级指针

2.4 单链表头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头指针中存储的是第一个节点的地址，所以newnode->next = *pphead，然后newnode就成了第一个节点，那么当前头指针存的就是当前第一个节点newnode的地址

2.5 单链表尾删

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//*phead要指针访问所以要断言
	if ((*pphead)->next == NULL)//分没有节点，和有节点的情况
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找最后一个节点的前一个节点
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;//free之后可以赋值但不能指针访问
	}
}

当没有节点时，删除的就是头指针，直接释放即可；当有节点时，我们要给最后一个节点和倒数第二个节点做标记，因为最后一个节点要释放，倒数第二个节点需要把他的next置为NULL

2.6 单链表头删

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

先存储首节点的地址，便于把首节点的下一个节点传给头节点，注意不要先释放节点，避免非法访问

2.7单链表查找

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

这个和顺序表一样，通过简单的遍历链表 一 一 对比值即可

2.8 单链表在pos位置插入x

2.8.1 pos前

void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

同样是分为链表为空和链表不为空的情况，当链表为空时，相当于头插；当链表不为空时，prev找到pos的前一个位置，然后进行链接操作即可

2.8.2 pos后

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

从代码形式上来看，pos后的插入明显是比pos前插入更简单的，pos前需要多传一个头指针参数，找到pos前一个数的位置；pos后只需要在pos后直接链接即可

2.9单链表在pos位置删除x

2.9.1 pos前

void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}

和在pos位置删除其实是一样的，分为空和不空的链表，但是一般我们不在函数内将要删除的节点置为空，习惯性在函数外进行此操作

2.9.2 pos后

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	//del = NULL;
}

直接释放pos位置之后的节点即可，但是要注意需要断言pos->next，万一是最后一个节点的话，在其后删除会报错

2.2.10 单链表销毁

void SLTDestroy(SLTNode** pphead)
{
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* del = pcur;
		pcur = pcur->next;
		free(del);
	}
	*pphead = NULL;
}

销毁的方法也不难，就是遍历链表，只要链表不为空就循环释放节点，关键是我们在释放前要把下一个节点记录下来，如果直接释放了当前节点，那么就找不到下一个节点了，所以我们要把下一个节点保存下来才释放当前节点

3.代码展示

传送门：Gitee单链表代码

3.1 SList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);

SLTNode* BuySLTNode(SLTDataType x);

void SLTPushBack(SLTNode** pphead, SLTDataType x);

void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);

void SLTPopFront(SLTNode** pphead);

SLTNode* SListFind(SLTNode* phead, SLTDataType x);

void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);

void SLTEraseBefore(SLTNode** pphead, SLTNode* pos);

void SLTInsertAfter(SLTNode* pos, SLTDataType x);

void SLTEraseAfter(SLTNode* pos);

void SLTDestroy(SLTNode** pphead);

3.2 SList.c

#include "SList.h"

//打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//创建节点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}

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

	return newnode;
}

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLTNode* first = *pphead;
	*pphead = first->next;
	free(first);
	first = NULL;
}

//查找节点
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//pos前插入
void SLTInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushBack(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//pos前删除
void SLTEraseBefore(SLTNode** pphead, SLTNode* pos)
{
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos = NULL;
	}
}

//pos后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//pos后删除
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！

请添加图片描述


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

相关文章：

  • 力扣动态规划-5【算法学习day.99】
  • vue2使用flv.js在浏览器打开flv格式视频
  • kubernetes学习-Service（七）
  • opencv笔记2
  • python助力WRF自动化运行
  • SAP POC 项目完工进度 - 收入确认方式【工程制造行业】【新准则下工程项目收入确认】
  • 跳石头，，
  • 【机器学习】嘿马机器学习（科学计算库）第11篇：Pandas,学习目标【附代码文档】
  • TensorFlow深度学习实战——情感分析模型
  • SpringCloud系列教程：微服务的未来（十四）网关登录校验、自定义过滤器GlobalFilter、GatawayFilter
  • 应急管理大数据指挥中心解决方案
  • HUDI-0.11.0 BUCKET index on Flink 特性试用
  • C语言数组与字符串操作全解析：从基础到进阶，深入掌握数组和字符串处理技巧
  • 数智化转型 | 星环科技Defensor 助力某银行数据分类分级
  • 在k8s中部署一个可外部访问的Redis Sentinel
  • Pix2Pix ：用于图像到图像转换的条件生成对抗网络
  • 第八篇：监视`ref`定义的【基本类型】数据
  • qt for android 报错解决记录
  • 嵌入式Linux驱动开发之platform
  • 深度学习学习笔记（第30周）
  • C语言之斗地主游戏
  • 简述1个业务过程：从客户端调用接口，再到调用中间件（nacos、redis、kafka、feign），数据库的过程
  • 【HarmonyOS NAPI 深度探索11】搭建 NAPI 开发环境：HarmonyOS DevEco Studio 全指南
  • PortSwigger NoSQL 注入
  • mybatis保存数据库类型为json类型数据报错
  • JAVA使用自定义注解，在项目中实现EXCEL文件的导出