速学数据结构 | 手把手教你会单链表的构建方式

C/C++
178
0
0
2024-02-25
【C语言进阶篇】什么还没学会指针? 一篇文章让你彻底搞懂指针的奥秘
上一篇
【C语言进阶篇】关于指针的八个经典笔试题（图文详解）
下一篇
标签   数据结构

⛺️生活的理想，就是为了理想的生活!

文章目录
  • 📋 前言
  • 1. 什么是链表
  • 1.1 链表的物理结构
  • 1.2 链表的种类
  • 2. 链表的实现
  • 一. SList.h 单链表的声明
  • 3.1 定义链表结构
  • 3.2 单链表函数的声明
  • 二. SList.h 单链表的定义
  • 2.1 动态申请链表一个节点
  • 2.2 单链表打印
  • 2.3 单链表尾插
  • 2.4 单链表的头插
  • 2.5 单链表的尾删
  • 2.6 单链表头删
  • 2.7 单链表查找
  • 2.8 在pos之前插入x
  • 2.9 在pos之后插入x
  • 2.10 删除pos位置
  • 2.11 删除pos的后一个位置
  • 三. test.c 单链表的功能测试
  • 📝全篇总结

📋 前言

🌈hello！ 各位宝子们大家好啊！今天给大家带来的是初阶数据结构中单链表的构建方式，手把手教会你单链表！ ⛳️链表是指一种逻辑上是连在一起的数据结构，但是物理存储上却是分开的部分！是通过链表中的指针链接次序实现的一种数据结构！

1. 什么是链表

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

在这里插入图片描述

顺序表我们都知道有点类似数组，是在物理上一块连续存放的内存块！所以顺序表也叫 线性表 但是开辟必须需要连续的空间空间的浪费特别严重！
  • 所以就有链表这种数据结构，避免了空间的浪费。
  • 链表在逻辑上是连在一起但是内存块确实分布在不同位置的
  • 通过指针访问每个链表的节点

1.1 链表的物理结构

在这里插入图片描述

从这里可以看出：

链表在逻辑上是连续的但是，物理上是单独分开的。由每一块的指针记录下一个节点的地址进行访问

🔥 注意

  • 现实中的节点一般都是在堆上申请出来的
  • 在堆上申请的空间，是编译器按照一定规则分配的，俩次申请的空间可能有时连续有时不连续。

1.2 链表的种类

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

  • 单向或者双向

在这里插入图片描述

  • 带头或者不带头

在这里插入图片描述

  • 循环或者非循环

在这里插入图片描述

但是我们今天就先从简单的入手，先来实现一下单链表的结构！先从简单的下手。
  • 单链表结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 链表的实现

好了废话不多讲，下面我们就来到链表的实现过程。链表前面我们了解了不是一个连续的存储结构,S是利用指针来进行每个节点的访问。

  • 注：我们把链表里的每个内容叫做一个节点

在这里插入图片描述

一. SList.h 单链表的声明

3.1 定义链表结构

链表链表首先我们要先定义链表的结构，链表既有数据又要和下一个链表联系起来那么肯定是要使用结构体：

  • 来定义链表
  • 而内容需要一个 data 和 指向下一个节点的指针！
typedef  int  SLTDataType;
//定义链表结构
typedef	struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
3.2 单链表函数的声明

单链表要实现的功能其实也非常简单，和顺序表是一模一样的。增删改查等这些操作而我们只要把这些函数实现了，那么在刷关于链表的题的时候也就无非是这些操作的变形。

  • 下面我们就来看看单链表具体要实现的功能把!
//动态申请链表节点
SLTNode* BuySListNode(SLTDataType x);

//打印单链表
void SLTPrint(SLTNode* plist);

//单链表头插
void SLTPushFront(SLTNode** pplist,SLTDataType x);

//单链表尾插
void SLTPushBack(SLTNode** pplist, SLTDataType x);

//单链表头删
void SLTPopFront(SLTNode** pplist);

//单链表尾删
void SLTPopBack(SLTNode** pplist);

//查找节点
SLTNode* SLTFind(SLTNode* pplist, SLTDataType x);

//在pos以前插入x
void SLTInsert(SLTNode** pplist, SLTNode* pos, SLTDataType x);

// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

// 删除pos位置
void SLTErase(SLTNode** pplist, SLTNode* pos);

// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);

// 单链表的销毁
void SListDestroy(SLTNode* pplist);

二. SList.h 单链表的定义

2.1 动态申请链表一个节点

前面我们把链表的基本结构定义好了那么接下来就申请节点了，这样我们才能进行链表的链接已经数据的存储！

  • 而开辟节点直接用 malloc 开辟空间然后赋值就好啦！
//动态申请链表节点
SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc file");
		exit(-1);
	}

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

	return newnode;
}
2.2 单链表打印

打印单链表也是一个十分简单的功能了，既然我们链表的每个节点的 next 存储的都是下一个节点那么直接循环访问就好啦！

  • 要注意控制好循环变量的结束条件
  • 和链表最后 NULL 的打印
//打印单链表
void SLTPrint(SLTNode* plist)
{
	SLTNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL\n");
}
2.3 单链表尾插

单链表的尾插也不是很难控制好着俩点就好了：

  • 第一个是 plist 为空的情况，直接尾插
  • 第二个是 plist 不为空的情况，循环找到尾直接尾插
//单链表尾插
void SLTPushBack(SLTNode** pplist, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SLTNode* tail = *pplist;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;
	}
}
2.4 单链表的头插

这个可以说是最简单的部分了，只要让要 plist 指向 插入的节点，插入节点的 next 指向下一个节点。

  • 还要注意一下断言
//单链表头插
void SLTPushFront(SLTNode** pplist,SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	newnode->next = *pplist;
	*pplist = newnode;
}
2.5 单链表的尾删

单链表的头插尾插我们实现了下面就是单链表的尾删了。注意要控制好边界的几种情况就好了

  • 一个是链表只有一个节点的情况下直接删除
  • 还有一个是链表有多个节点需要遍历
//单链表尾删
void SLTPopBack(SLTNode** pplist)
{
	//非空判断
	assert(*pplist);
	SLTNode* tail = *pplist;
	
	
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

	 
		free(tail->next);
		tail->next = NULL;
	}

}
2.6 单链表头删

单链表的头删注意考虑俩总情况，一个是只有一个节点释放，一个是多个节点释放。

  • 在 assert 断言一下NULL链表就不删除
//单链表头删
void SLTPopFront(SLTNode** pplist)
{
	//非空判断
	assert(*pplist);

	SLTNode* newhead = (*pplist)->next;
	free(*pplist);
	*pplist = newhead;
}
2.7 单链表查找

为什么要先写单链表的查找呢，因为我们现实中通常不知道我们要删除或者插入的数在第一个点上所以需要先查找要删除或者插入的数到时候删除直接复用就好了。

  • 查找的话直接循环遍历就好了，如果找不到就返回空NULL。
//查找节点
SLTNode* SLTFind(SLTNode* plist, SLTDataType x)
{
	SLTNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}
2.8 在pos之前插入x

和前面的删除一样，需要控制好不同的情况和 暴力检测一下 plist 传过来的是不是一个空指针。

  • 空指针就直接退出说明传错了
  • 还要注意遍历pos前一个节点
//在pos以前插入x
void SLTInsert(SLTNode** pplist, SLTNode* pos, SLTDataType x)
{
	assert(*pplist);
	assert(pos);
	

	if (pos == *pplist)
	{
		SLTPushFront(pplist,x);
	}
	else
	{
		SLTNode* prev = *pplist;

		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);

		prev->next = newnode;
		newnode->next = pos;
	}
}
2.9 在pos之后插入x

这个就没在pos之前插入x那么复杂了可以根据指针找到下一个节点，然后删除pos的后一个节点

  • 将next 连接到pos的下下个节点上
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (pos->next == NULL)
	{
		pos->next = newnode;
	}
	else
	{
		SLTNode* next = pos->next->next;
		pos->next = newnode;
		newnode->next = next;
	}
}
2.10 删除pos位置

删除pos的位置就需要循环遍历pos，的前一个位置。然后进行 free 释放空间

  • 在把俩个节点关联起来就可以了
// 删除pos位置
void SLTErase(SLTNode** pplist, SLTNode* pos)
{
	assert(pplist);
	assert(pos);

	if(*pplist == pos)
	{
		SLTPopFront(pplist);
	}
	else
	{
		SLTNode* prve = *pplist;
		while (prve->next != NULL)
		{
			prve = prve->next;
		}

		prve->next = pos->next;
		free(pos);
	}
}
2.11 删除pos的后一个位置
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);

	assert(pos->next);
	
	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;

	
}

三. test.c 单链表的功能测试

这里博主就不给大家测试给大家写个样例，大家自己去试试增删查改哦！

void Test_SList2()
{
	SLTNode* plist = NULL;

	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPushFront(&plist, 5);
	SLTPrint(plist);
}
int main()
{
	Test_SLsit1();
	
}

📝全篇总结

✅ 归纳： 好了以上就是关于分支语句 链表 的所有知识点了，大家快下去练习练习吧！ 链表的介绍链表的结构链表的增删查改

☁️ 把本章的内容全部掌握，铁汁们就可以熟练应用switch语句啦！

在这里插入图片描述

【C语言进阶篇】什么还没学会指针? 一篇文章让你彻底搞懂指针的奥秘
上一篇
【C语言进阶篇】关于指针的八个经典笔试题（图文详解）
下一篇