数据结构之链表（单链表）

摘星

发布于 2023-04-28 09:27:35

2530

发布于 2023-04-28 09:27:35

文章被收录于专栏：C/C++学习C/C++学习

前言

数据结构之顺序表中我们有讲到顺序表有一些问题和缺点，为了能解决顺序表的问题，我们引入一个新的线性表——链表

一、链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表与顺序表的不同 1.链表是按需申请空间的 2.链式结构在逻辑上是连续的但是在物理结构上不一定是连续的；两次申请的空间可能是连续的，也可能是不连续的。注意：链表和顺序表所申请的空间都是在堆上申请的。（动态开辟的空间都是在堆上申请的）

二、链表的八种结构

1.单向或者双向

2.带头或者不带头（头：哨兵位）

3.循环或者不循环

以上三种类型，两两组合就能得到链表的八种结构，虽然有这么多种链表，但是我们最常用的还是两种： 1.无头单向非循环链表；

2.有头双向循环链表。

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。 2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。

我们今天主要介绍的是无头单向非循环链表（单链表）。

三、单链表

1.单链表的声明及接口的声明

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
//动态申请一个新的节点
SLTNode* BuySLTNode(SLTDataType x);
//打印单链表中的数据
void SLTPrint(SLTNode* phead);
//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//单链表的头删
void SLTPopFront(SLTNode** pphead);
//单链表的尾删
void SLTPopBack(SLTNode** pphead);
//单链表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* pphead, SLTNode* pos, SLTDataType x);
// 单链表删除pos位置的节点
void SLTEarse(SLTNode** pphead, SLTNode* pos);
// 单链表删除pos位置之后的节点
void SLTEarseAfter(SLTNode* pos);

2.接口的实现

1.开辟一个新的节点

（单链表是由一个节点一个节点链接起来的）

//开辟一个新的节点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* p = (SLTNode*)malloc(sizeof(SLTNode));
	p->data = x;
	p->next = NULL;
	return p;

1.打印单链表

（方便调试观察）

//打印单链表中的数据
void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while(cur != NULL)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.头插

//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* NewNode = BuySLTNode(x);
	NewNode->next = *pphead;
	*pphead = NewNode;
}

3.尾插

//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* NewNode = BuySLTNode(x);
	//单链表为空
	if ((*pphead) == NULL)
	{
		NewNode->next = *pphead;
		*pphead = NewNode;
	}
	//单链表不为空
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = NewNode;
	}
}

4.头删

//单链表的头删
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);//如果链表为空再继续删除就会报警告
	SLTNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);
}

5.尾删

//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);//如果链表为空再继续删除就会报警告
	SLTNode* cur = *pphead;
	if ((cur->next) != NULL)
	{
		SLTNode* prev = cur->next;
		while (prev->next != NULL)
		{
			prev = prev->next;
			cur = cur->next;
		}
		free(prev);
		cur->next = NULL;
	}
	else
	{
		free(cur);
		*pphead = NULL;
	}
}

6.单链表的查找

//单链表的查找（找到了返回该节点的地址）
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* p = phead;
	while (p)
	{
		if (p->data == x)
		{
			return p;
		}
		p = p->next;
	}
	assert(p);
}

7.在pos位置之前插入数据

// 单链表在pos位置之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	SLTNode* prev = *pphead;
	SLTNode* NewNode = BuySLTNode(x);
	if (prev == pos)
	{
		NewNode->next = prev;
		*pphead = NewNode;

	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		NewNode->next = prev->next;
		prev->next = NewNode;
	}
}

8.在pos位置之后插入数据

// 单链表在pos位置之后插入x
void SLTInsertAfter(SLTNode* phead, SLTNode* pos, SLTDataType x)
{
	SLTNode* prev = phead;
	SLTNode* NewNode = BuySLTNode(x);
	while (prev)
	{
		if (prev == pos)
		{
			NewNode->next = prev->next;
			prev->next = NewNode;
			break;
		}
		prev = prev->next;
	}
}

9.删除pos位置的数据

// 单链表删除pos位置的节点
void SLTEarse(SLTNode** pphead, SLTNode* pos)
{
	SLTNode* prev = *pphead;
	if (prev == pos)
	{
		*pphead = prev->next;
		free(prev);
		prev = *pphead;
	}
	else
	{
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

10.删除pos位置之后的数据

// 单链表删除pos位置之后的节点
void SLTEarseAfter( SLTNode* pos)
{
	SLTNode* cur = pos;
	assert(cur->next);//当pos指向链表最后一个节点时，不能删除pos后的值
	cur = cur->next;
	pos->next = cur->next;
	free(cur);
}

3.主函数（测试）

主要用于测试单链表实现的接口，大家也可以自行调整，代码如下：

void test1()//测试：头插
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 6);//注意是传plist的地址过去（要改变plist的值就要传plist的地址，因为形参只是实参的一份临时拷贝，如果只是传plist过去就只是将phead这个plist的临时拷贝值进行改变，)
	SLTPushFront(&plist, 16);
	SLTPushFront(&plist, 62);
	SLTPushFront(&plist, 63);
	SLTPushFront(&plist, 46);
	SLTPushFront(&plist, 67);
	SLTPrint(plist);
}
void test2()//测试：尾插
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 62);
	SLTPushBack(&plist, 63);
	SLTPushBack(&plist, 46);
	SLTPushBack(&plist, 67);
	SLTPrint(plist);
}
void test3()//测试：头删
{

	SLTNode* plist = NULL;
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 62);
	SLTPushBack(&plist, 63);
	SLTPushBack(&plist, 46);
	SLTPushBack(&plist, 67);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
}
void test4()//测试：尾删
{

	SLTNode* plist = NULL;
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
}
void test5()//测试：查找
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTNode* ret = SLTFind(plist, 56);
	if (ret)
	{
		printf("%p\n",ret);
	}
}
void test6()//测试:在pos位置之前插入数据
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPrint(plist);
	//SLTNode* pos = SLTFind(plist, 26);
	//SLTInsert(&plist, pos, 55);//相当于头插
	//SLTNode* pos = SLTFind(plist, 16);
	//SLTInsert(&plist, pos, 55);//正常插入
	//SLTNode* pos = SLTFind(plist, 88);//pos不是链表中的数据，会被SLTFind检测出来不会进行插入
	//SLTInsert(&plist, pos, 98);//正常插入
	SLTInsert(&plist,NULL, 55);//相当于尾插
	SLTPrint(plist);
}
void test7()//测试:插入（在pos位置之后插入）//不可能进行头插
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 78);//相当于尾插
	SLTInsertAfter(plist, pos, 55);
	SLTInsertAfter(plist, plist, 55);
	SLTPrint(plist);
}
void test8()//测试:删除pos位置的数据
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 78);//相当于尾删
	SLTEarse(&plist, pos);
	SLTPrint(plist);
}
void test9()//测试:删除pos位置之后的数据
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 26);
	SLTPushBack(&plist, 18);
	SLTPushBack(&plist, 16);
	SLTPushBack(&plist, 56);
	SLTPushBack(&plist, 78);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 56);
	SLTEarseAfter(pos);
	SLTPrint(plist);
}

int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	//test5();
	//test6();
	//test7();
	//test8();
	test9();
	return 0;
}

总结

以上就是今天要讲的内容，本文介绍了线性表中的链表，主要实现了单链表（无头不循环单链表），大家感兴趣的也可以根据作者所写思路（注释）自行实现单链表。本文作者也是一个正在学习编程的萌新，目前也只是刚开始接触数据结构这方面的内容，如果有什么内容方面的错误或者不严谨，欢迎大家在评论区指出。最后，如果本篇文章对你有所启发的话，也希望可以支持支持作者，谢谢大家！

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

原始发表：2022-11-20，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构