数据结构之单链表(赋源码)

技匠晓晨

发布于 2024-11-26 09:30:29

1260

文章被收录于专栏：C/C++基础到进阶C/C++基础到进阶

数据结构之单链表

线性表

线性表的顺序存储结构，有着较大的缺陷

插入和删除操作需要移动大量元素。会耗费很多时间
增容需要申请空间，拷贝数据，释放旧空间。会有不小的消耗
即使是使用合理的增容策略，实际上还会浪费许多用不上的空间。如我只需要101个空间存放数据，而100进行2倍增容后有200个空间，这样实际上浪费了99块空间。

线性表的链式存储结构就可以解决这些问题，首先链式存储结构并不需要增容，而是使用多少数据申请多少空间，这一点就避免了时间和空间的浪费。

顺序存储结构和链式存储结构

存储方式

顺序存储结构，使用一段连续的空间依次存储数据
链式存储结构，使用一个个存储单元存放数据

时间性能

插入和删除
- 顺序存储结构，O(N)
- 链式存储结构，O(1)

空间性能

顺序存储结构，需要预分配空间，给小了不够用，给打了浪费
链式存储结构，不需要预分配空间，只要有新的元素插入才会开辟内存单元

使用场景

具体在什么场景使用不同的线性表存储结构呢？

若线性表需要频繁的查找，很少进行插入和删除操作时，可以采用顺序存储结构。
若线性表中的元素个数变化较大或不知道有多大时，可以采用链式存储结构。
- 单链表在插入和删除不需要移动元素，只需改变指针的指向即可。

单链表

概念：单链表是在物理存储结构上不连续，逻辑结构上连续的线性表。它是通过指针链接，就像火车的一节一节车厢一样通过挂钩链接在一起，车厢就是单链表的一个一个节点，里面用来存放数据。

而在单链表里“车厢”内有些什么的呢？单链表是一种数据结构“车厢”里肯定存放在数据，而单链表又是通过指针链接在以起，就像车厢的钩子一样链接，它在物理存储结构上不是连续的，所以“车厢”里还有一个指针变量用来存放下一节“车厢”的地址。

typedef int SLNodeDatatpye;
struct SListNode
{
	SLNodeDatatpye data;//存放数据
	struct SListNode* next;//存放单链表类型的指针
};

存放的数据类型：单链表不会只用来存放整形数据，这里只是以整形举例，所以需要对类型重命名，方便对后面的类型进行修改，需要修改数据类型的只需要动动 typedef int SLNodeDatatpye;，这串代码。

功能实现

typedef int SLNodeDatatpye;
struct SListNode
{
	SLNodeDatatpye data;
	struct SListNode* next;
};
typedef struct SListNode SL;

//创建节点
SL* SLBuyNode(SLNodeDatatpye x);

//打印
void SLPrint(SL** pphead);

//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x);
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x);

//头删
void SLPopFront(SL** pphead);
//尾删
void SLPopBack(SL** pphead);

//查找，返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x);

//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos);

//删除pos之后的节点
void SLEraseBack(SL* pos);
//删除pos节点
void SLErase(SL** pphead, SL* pos);

//销毁链表
void SLDestory(SL** pphead);

创建节点和打印

实现单链表的功能第一步需要为它创建节点以用来存放数据。实现打印功能，将链表的数据打印出来方便更好的观查链表存储数据的情况，配合着调试功能可以更加完善的查找，观测在实现完一个功能，它执行的结果是否与预期相符合，若发生错误，又可以借助调试功能更好、更快的查找bug。

//创建节点
SL* SLBuyNode(SLNodeDatatpye x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;//忘记返回newnode的地址了
}
//打印
void SLPrint(SL** phead)
{
	//assert(phead);
	SL* pcur = phead;
	while (pcur)//pcur != NULL
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

创建节点很容易理解，一个单链表的节点用来存放数据和下一个节点的地址，在创建节点时使用malloc函数开辟一个内存单元，然后判断开辟空间是否成功，接着将传递过来的参数放在 newnode->data = x;里。

newnode->next = NULL;置为空即可，这只是一个节点没有与其余节点有任何关联，借助插入函数来实现像火车一样一节一节车厢链接在一起的效果。

打印单链表时应注意：

循环体，单链表的循环通过next指针来实现，结束条件是最后一个节点的next指针为空。

pcur = pcur->next;，通过 pcur->next，赋值给 pcur，来来遍历每一个节点。重述：将pcur的下一个节点的地址赋给pcur，此时pcur就等于下一个节点，直达循环到最后一个节点，在最后一个节点data == 4 ，pcur = pcur->next;，为空指针将其赋给 pcur，此时它为空指针，跳出循环。

查找数据

查找数据，为什么传递二级指针，这里是为了保持函数接口的一致性，后续实现的插入、删除、销毁操作都需要传递二级指针，同时也是减少对函数的混淆，当函数量较多时，这个函数传一级指针，另一个函数传递二级指针，四处分散，容易让使用者看了傻眼~。

//查找，返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x)
{
	assert(*pphead && pphead);
	SL* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

查找数据的基本的逻辑与打印类似，都需要使用循环遍历链表，循环内增加了一个条件判断，用于判断这个节点的数据是否等于形参x，相等就说明找到了 “找到了”，将当前节点的地址返回即可，若跳出循环后还是没有找到对应的节点，将返回NULL，空指针。

assert断言是防止，传递过来的链表的节点是空指针，在函数内对进行解引用导致程序报错。

插入数据

在插入数据时需要考虑，插入的数据会对影响那些节点

特别注意的一点，插入数据会对单链表进行改变，在传递参数的时候需要对取pliat的地址，而plist又是一个指针变量，所以函数需要使用二级指针来接收。

节点	函数参数
*plist(第一个节点)	**pphead
plist(指向第一个节点的指针)	*pphead
&plist(指向第一个节点的指针的地址)	pphead

void test()
{
	SL* plist = NULL;
	SLPushFront(&plist, 1);
	SLPushFront(&plist, 2);
}

//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x)
{
	assert(pphead);
	SL* newnode = SLBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLBuyNode(x);
	}
	else
	{
		SL* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = SLBuyNode(x);
	}
}

需要对头插、尾插分两种场景，一是没有节点，传递过来的是空链表，二是有节点，传递的不是空链表。

实现头插、尾插先认为传递的不是一个空链表，基于此来实现，然后对空链表的情况做出判断和处理。这样做会更容易上手，先实现最主要的功能，然后再检擦其完整性。

assert断言是防止，传递过来的链表的节点是空指针，在函数内对进行解引用导致程序报错。

头插：

需要创建一个节点，SL* newnode = SLBuyNode(x);，使用上述的函数创建一个新节点
将其放在链表的第一个位置，newnode->next = *pphead;，

将新插入的节点置为新的头(让*pphead指向新的节点)，*pphead = newnode;。

千万别忘了，需要将*pphead置为新的头，否则此时，它指向的是下一个节点的位置，会影响到后续对链表的操作。

**最后取特殊情况：**当链表为空时，上述头插是否支持。很明显，我们将 *pphead == NULL的情况带入头插函数，SL* newnode = SLBuyNode(x);，第一步正常创建节点；newnode->next = *pphead;，第二步正常，由于只有一个节点所以 newnode->next == NULL，没有问题；*pphead = newnode;，第三步将*pphead置为新的头，这步没有问题，也不存在对空指针解引用的情况。

最后通过运行代码观测：

尾插：

尾插同理，也是将链表默认不为空的情况实现。

想要进行尾插首先得有一个指针指向最后一个节点，然后将创建的新节点插入。
定义一个指针pcur，使用循环遍历到最后一个节点。
跳出循环，完成最后一步尾插代码~，pcur->next = SLBuyNode(x);。

当链表为空时，这不就是头插吗？！，这样我们使用一个if语句判断*pphead是否为空，为空就调用头插函数，不为空就循环到最后一个节点，然后插入~

指定位置插入：

指定位置插入实际上与尾插代码差别不大，就改变了跳出while循环的的条件。

//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos)
{
	assert(pphead);
	assert(pos);
	SL* newnode = SLBuyNode(x);
	SL* pcur = *pphead;
	if (*pphead == pos)//这不就是头插吗？
	{
		newnode->next = pos;
		*pphead = newnode;
	}
	else
	{
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
		newnode->next = pos;

	}
}

首先想要实现指定位置插入，传入的链表和pos不可能为空使用一个assert断言进行判断。

同样，将指定位置插入分为两种情况，一是 *pphead == pos ，二是 *pphead ！= pos

这里可以将pos看似空指针（NULL），那指定位置插入（之前）不就是尾插吗？细节上不就是在 pos这个指针上，处理它也很简单。

在指针pos之前插入数据会影响到的节点：pcur pos ，在pcur和pos之前插入newnode，pcur newnode pos

这里需要将pcur和pos之间的”线“断开，然后使 newnode->next = pos;，newnode->next = pos;这不就完成了插入操作。

删除数据

在删除数据时需要考虑，删除这个节点会影响到那些节点

删除数据需要注意的是 *pphead 和 pphead不能为空，删除数据也不可能删除空，函数里对空指针解引用也会报错。

头删：

头删的逻辑简单：一，保存*pphead之后的节点 SL* pcur = (*pphead)->next;，二、然后释放第一个节点 free(*pphead);，三、最后将 pcur 赋给 *pphead，更新头节点的位置。

尾删：

尾删，需要考虑最后一个节点，和最后一个节点之前的节点，所以需要使用pdst指针指向倒数第二个节点，以及pcur指针指向最后一个节点。在循环时以 pcur->next != NULL为结束条件，在循环体内要保证 pdst指针在pcur指针后，这种做法保证了，pdst指针在pcur指针后，而pcur指针指向的也是最后一个节点。

SL* pdst = *pphead; SL* pcur = pdst->next;

//头删
void SLPopFront(SL** pphead)
{
	assert(*pphead && pphead);
	SL* pcur = (*pphead)->next;
	free(*pphead);
	*pphead = pcur;
}
//尾删
void SLPopBack(SL** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SL* pdst = *pphead;
		SL* pcur = pdst->next;
		while (pcur->next)
		{
			pcur = pcur->next;
			pdst = pdst->next;
		}
		pdst->next = NULL;
		free(pcur);
		pcur = NULL;
	}
}

指定位置删除数据：

指定位置删除数据与指定位置插入数据类似，与尾删也比较类似。首先想要指定位置删除数据， *pphead和pphead以及pos都不可能为空，否则这还删什么?传递过来的东西都是空的。

删除指定位置的数据时需要从它会影响那些节点，pos会影响到 pcur pos pos->next。

*pphead 刚好等于pos 的情况，和 *pphead != pos的情况。当 *pphead != pos时：

需要使用循环将定义的pcur指针指向pos之前的节点，所以结束条件是 pcur->next != pos
当跳出循环时开始销毁，在销毁前需要将 pos->next;赋给 pcur->next，否则直接删除pos节点，无法将pso的后继节点与它前驱节点链接，链表断开了~

讲pcur与pos->next链接上后，释放pos即可。

当*pphead == pos时，pos指向的时第一个节点的位置，此时不就是头删吗，这是直接调用头删函数就完成了。

//指定位置删除
void SLErase(SL** pphead, SL* pos)
{
	assert(*pphead && pphead);
	assert(pos);
    SL* pcur = *pphead;
	if (*pphead == pos)//头删
	{
		//free(*pphead);
		//*pphead = NULL;
		SLPopFront(pphead);
	}
	else
	{
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的节点
void SLEraseBack(SL* pos)
{
	assert(pos->next && pos);
	//  pos pos->next pos->next-->next
	SL* del = pos->next;
	//  pos del del->next
	pos->next = del->next;
	free(del);
	del = NULL;
}

删除pos之后的节点逻辑简单与删除pos节点类似。第一步同样是需要考虑，删除pos之后·的节点会影响到那些节点。

删除pos之后的节点会影响：pos pos->next pos->next-->next，这三个节点，所以传递过来的 pos 和 pos->next不能为空否则就是对空指针解引用，导致程序异常。

在删除时，需要注意删除和将pos 与 pos->next–>next链接的顺序，先链接，在删除

将pos->next保存，赋给del指针
将pos与 del->next链接
释放del指针

销毁链表

销毁链表需要使用free对每一个节点进行释放。

//销毁链表
void SLDestory(SL** pphead)
{
	//循环销毁所有节点
	assert(*pphead && pphead);
	SL* pcur = *pphead;
	while (pcur)
	{
		SL* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

销毁链表，需要对每一个节点进行释放，而只使用一个指针pcur，释放当前的节点就找不到下一个节点了，这里需要使用两个指针。

一个指针用来释放（pcur），一个指针用来指向待释放之后的节点（next）。

当释放完pcur节点后，更新pcur的位置 pcur = next;，用来释放下一个节点，next指针也需要更新用来指向下一个节点 next = pcur->next;，用来对pcur进行更新。直到pcur指向空指针时释放完所有节点，跳出循环。而 *pphead，还没有置为空，这时候时野指针，最后一步 *pphead = NULL;。

源码

SListNode.h

#pragma once

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


typedef int SLNodeDatatpye;
struct SListNode
{
	SLNodeDatatpye data;
	struct SListNode* next;
};
typedef struct SListNode SL;

//创建节点
SL* SLBuyNode(SLNodeDatatpye x);

//打印
void SLPrint(SL* phead);

//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x);
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x);

//头删
void SLPopFront(SL** pphead);
//尾删
void SLPopBack(SL** pphead);

//查找，返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x);//不需要二级指针，保证接口一直，所以传递二级

//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos);

//删除pos之后的节点
void SLEraseBack(SL* pos);
//删除pos节点
void SLErase(SL** pphead, SL* pos);

//销毁链表
void SLDestory(SL** pphead);

SListNode.c

#define _CRT_SECURE_NO_WARNINGS

#include "SListNode.h"
//创建节点
SL* SLBuyNode(SLNodeDatatpye x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//打印
void SLPrint(SL* phead)
{
	//assert(phead);
	SL* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

//头插
void SLPushFront(SL** pphead, SLNodeDatatpye x)
{
	assert(pphead);
		SL* newnode = SLBuyNode(x);
		newnode->next = *pphead;
		*pphead = newnode;
}
//尾插
void SLPushBack(SL** pphead, SLNodeDatatpye x)
{
	assert(pphead);
	if (*pphead == NULL)
	{
		*pphead = SLBuyNode(x);
	}
	else
	{
		SL* pcur = *pphead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = SLBuyNode(x);
	}
}
//头删
void SLPopFront(SL** pphead)
{
	assert(*pphead && pphead);
	SL* pcur = (*pphead)->next;
	free(*pphead);
	*pphead = pcur;
}
//尾删
void SLPopBack(SL** pphead)
{
	assert(*pphead && pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SL* pdst = *pphead;
		SL* pcur = pdst->next;
		while (pcur->next)
		{
			pcur = pcur->next;
			pdst = pdst->next;
		}
		pdst->next = NULL;
		free(pcur);
		pcur = NULL;
	}
}
//查找，返回地址
SL* SLFind(SL** pphead, SLNodeDatatpye x)
{
	assert(*pphead && pphead);
	SL* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//指定位置插入(之前)
void SLInsert(SL** pphead, SLNodeDatatpye x, SL* pos)
{
	assert(pphead);
	assert(pos);
	SL* newnode = SLBuyNode(x);
	SL* pcur = *pphead;
	if (*pphead == pos)
	{
		newnode->next = pos;
		*pphead = newnode;
	}
	else
	{
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
		newnode->next = pos;

	}
}
//指定位置删除
void SLErase(SL** pphead, SL* pos)
{
	assert(*pphead && pphead);
	assert(pos);
	if (*pphead == pos)//头删
	{
		//free(*pphead);
		//*pphead = NULL;
		SLPopFront(pphead);
	}
	else
	{
		SL* pcur = *pphead;
		while (pcur->next != pos)
		{
			pcur = pcur->next;
		}
		pcur->next = pos->next;
		free(pos);
		pos = NULL;
	}
}
//删除pos之后的节点
void SLEraseBack(SL* pos)
{
	assert(pos->next && pos);

	//  pos pos->next pos->next-->next
	SL* del = pos->next;
	//  pos del del->next
	pos->next = del->next;
	free(del);
	del = NULL;
}

//销毁链表
void SLDestory(SL** pphead)
{
	assert(*pphead && pphead);

	SL* pcur = *pphead;
	while (pcur)
	{
		SL* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-07-13，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构