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

数据结构-单链表及其应用

article 2025/1/8 14:59:26

文章目录

  • 一、单链表的概念及结构
    • 1.链表的概念
    • 2.链表的节点结构
    • 3.单链表增删查改操作的实现

一、单链表的概念及结构

1.链表的概念

🍉🍉概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
在这里插入图片描述在这里插入图片描述(1) 链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。
(2) 车厢是独立存在的，且每节车厢都有车门。想象这样一个场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾? 最简单的做法就是：每节车厢里都放一把下一节车厢的钥匙🔑。

那在链表里，每节"车厢"是什么样的呢?
在这里插入图片描述与顺序表不同的是，链表里的每节"车厢"都是独立申请下来的空间，我们称之为"结点/节点"。节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址。图中指针变量 plist 保存的是第一个节点的地址，我们称plist此时"指向"第一个节点。如果我们希望plist"指向"第二个节点时，只需要修改plist保存的内容为0x0012FFA0即可。(链表是由一个一个的节点组成的)

为什么还需要指针变量来保存下一个节点的位置呢?
答：链表中每个节点都是独立申请的(即需要插入数据时才去申请一块节点的空间)，🔑🔑🔑我们需要通过指针变量来保存下一个节点的地址才能从当前节点找到下一个节点。

2.链表的节点结构

学到这里就知道了应该用结构体来描述一个节点。一个节点中既要有保存的数据还要有下一个节点的指针，那我们就可以给出节点的结构。假设节点保存的数据为整型：【注：本节讲的是单链表(single linked list)，节点的英文单词为node】

//定义节点的结构
typedef int SLTDataType;
struct SListNode
{
	SLTDataType data; //节点数据
	struct SListNode* next; //指针变量用来保存下⼀个节点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数据，也需要保存下一个节点的地址(当下一个节点为空时保存的地址为NULL)。如果我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上 下一个节点的地址(下一个节点的钥匙)就可以了。

3.单链表增删查改操作的实现

知道了链表就是由一个一个的节点组成的，接下来就是链表的增删查改等操作方法的实现。我们将节点的结构定义及单链表各种方法的声明放在SList.h的头文件中，将方法的实现放在SList.c的源文件中，最后再创建一个test.c的源文件用来测试单链表的各种操作方法。

//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);

//链表尾插节点
void SLTPushBack(SLTNode** pphead, SLTDataType x);

//链表头插节点
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//链表的尾删
void SLTPopBack(SLTNode** pphead);

//链表的头删
void SLTPopFront(SLTNode** pphead);

//链表数据的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsertPre(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除指定位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos);

//删除指定位置之后的节点
void SLTEraseAfter(SLTNode* pos);

//链表的销毁
void SLTDestory(SLTNode** pphead);

//SList.c
#include"SList.h"
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur) //pcur!=NULL
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//动态申请节点并存储数据
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	//需要考虑空链表和非空链表两种情况
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		//找尾节点
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//此时ptail指向的就是尾节点
		ptail->next = newnode;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);
	if ((*pphead)->next==NULL)
	{
		//链表只有一个节点
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//链表有多个节点
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
//链表数据的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)//循环条件等价于pcur!=NULL
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
void SLTInsertPre(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	//若pos == *pphead时，即为头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//若pos==*pphead则是头删
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}
void SLTDestory(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

现在我们在test.c的源文件中进行测试：

//test.c
#include"SList.h"
void SListTest01()
{
    //手动创建四个节点并将它们连起来
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;
    node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SLTNode* plist = node1;
	SLTPrint(plist);
	//销毁链表
	SLTDestory(&plist);
	SLTPrint(plist);
}
int main()
{
	SListTest01();
	return 0;
}

程序运行结果：
在这里插入图片描述上面是手动创建链表节点，后续我们并不需要手动地去创建节点，通过上面链表各种方法的实现之后，我们就可以直接调用这些方法来实现链表节点的增删查改：

//test.c
#include"SList.h"
void SListTest02()
{
	//创建一个结构体(节点结构)指针用于后续链表节点的插入
	SLTNode* plist = NULL;
	//⑴尾插节点
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	//⑵头插节点
	SLTPushFront(&plist, 6);
	SLTPrint(plist);
	SLTPushFront(&plist, 7);
	SLTPrint(plist);
	SLTPushFront(&plist, 8);
	SLTPrint(plist);
	//⑶查找链表中的数据
	SLTNode* find = SLTFind(plist, 2);
	if (find == NULL)
	{
		printf("没有找到!\n");
	}
	else
	{
		printf("找到了!\n");
	}
	//⑷在指定位置之前插入数据
	SLTInsertPre(&plist, find, 11);
	SLTPrint(plist);
	//⑸在指定位置之后插入数据
	SLTInsertAfter(find, 22);
	SLTPrint(plist);
	//⑹尾删节点
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	//⑺头删节点
	SLTPopFront(&plist);
	SLTPrint(plist);
	//⑻删除指定位置的节点
	SLTErase(&plist, find);
	SLTPrint(plist);
	//⑼删除指定位置之后的节点
	SLTEraseAfter(find);
	SLTPrint(plist);
	//⑽销毁链表
	SLTDestory(&plist);
	SLTPrint(plist);
}
int main()
{
	SListTest02();
	return 0;
}

上面的各种方法需要一个一个(单独)地进行调试，以确保每个方法没有bug。

思考：当我们想保存的数据类型为字符型、浮点型或者其他自定义的类型时，该如何修改?
补充说明:
🍓1. 链式结构在逻辑上是连续的，在物理结构上不一定连续
🍓2. 节点一般是从堆上申请的
🍓3. 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，也可能不连续

这里所讲的单链表全称是:🍎不带头单向不循环链表🍎。关于链表的种类一共有8种，后面讲双向链表的时候会介绍。

在这里插入图片描述


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

相关文章：

  • [开源]自动化定位建图系统
  • Hadoop解决数据倾斜方法
  • 51单片机——共阴数码管实验
  • 什么样的人适合从事FPGA开发的工作？
  • 标题：利用Spring Boot构建JWT刷新令牌应用
  • 【USRP】教程：在Macos M1（Apple芯片）上安装UHD驱动（最正确的安装方法）
  • 2025课题推荐：低空飞行器在复杂环境中的导航与避障系统
  • 资源分享：gpts、kaggle、paperswithcode
  • excel快速计算周数的方法
  • vue3中ref动态定义
  • 使用Llama 3.1创建合成数据集以调优你的大型语言模型
  • LeetCode代码随想录（二）——977.有序数组平方、209长度最小子数组、59螺旋矩阵2
  • Unity3D仿星露谷物语开发15之创建道具晃动效果
  • Vue——使用html2pdf插件，下载pdf文档到本地
  • VAxios
  • 深入了解 Nginx：进程、代理及用途解析
  • 苍穹外卖-day07（Spring Cache 购物车业务逻辑）
  • Flink 实时数据处理中的问题与解决方案
  • 【简博士统计学习方法】3. 统计学习方法的三要素
  • laravel 批量更新：‌INSERT ... ON DUPLICATE KEY UPDATE
  • 移动端自动化测试Appium-java
  • AI大模型的搭建和训练
  • Linux——修改文件夹的所属用户组和用户
  • 【A-Lab】部署手册：开源AAA解决方案 —FreeRADIUS
  • Git - 记录一次由于少输入了一个命令导致的更改丢失
  • HTML——72. 下拉列表分组（下拉列表中多选）