2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

【数据结构初阶】单链表

作者：2023面试高手 | 2024-04-09 05:04:58

踩

【数据结构初阶】单链表

各位读者老爷好，鼠鼠我又来了哈。鼠鼠我呀现在来基于C语言实现一下单链表，希望对你有所帮助！

鼠鼠我上次浅谈了顺序表。但是吧，Any coin has two sides。

顺序表有一些缺陷：

1.尾部插入效率还不错。头部或者中间插入删除，需要挪动数据，效率低下。

2.顺序表满了以后只能扩容。扩容是有一定消耗的，扩容一般是存在一定的空间浪费：一次扩得越多，可能浪费越多；一次扩得少，可能需要频繁扩容。

当然，顺序表也有它的优势：

得益于它的物理空间连续，顺序表支持随机的下标访问。

So，我们有链表（也是线性表）可以避免顺序表的缺陷，那我们先来看看链表哈！

1.链表的概念及结构

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

不带头非循环单向链表的逻辑结构如下图：

链表是由节点（或者结点）构成的。这些个节点一般是动态内存申请得来的，所以每个节点的地址没有关联，是随机的，可能动态申请的时候申请到了连续的空间，更多可能是申请到不连续的空间，也就是说链表的物理结构不一定连续，。既然每个节点的地址是随机的，那我们如何管理链表呢？

其实也很简单，拿不带头非循环单向链表来说，如上逻辑结构可知，只要节点有俩个数据域即可，一个数据域存放所需存入的值（即有效数据），另一个数据域存放下一个节点的地址（最后一个节点保存空指针）。这样我们就可以通过第一个节点找到第二个节点、第二个节点找到第三个节点……这样就可以管理链表了。

了解了链表的特点，那我们对于数据的增删改等操作，更改节点内存储的地址即可，不必挪动数据。而且节点是一个个动态申请得到的，想要多少就申请多少，自然就避免了扩容有浪费的情况。这样子就很好避免的顺序表的缺陷！

画图方便理解：

2.链表的分类

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

1.单向或者双向

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

3.循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

咱们这篇博客实现的是无头单向非循环链表。

3.无头单向非循环链表的实现

具体我们实现这些无头单向非循环链表（以下简称单链表）的增删查改等等功能：


typedef int SLTDateType;     //有效数据类型，方便后续维护代码
 
//定义单链表节点
typedef struct SListNode
{
	SLTDateType data;     //有效数据
	struct SListNode* next;  //下一个节点的地址
}SListNode;
 
// 单链表打印
void SListPrint  (SListNode * plist);
 
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
 
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
 
// 单链表的尾删
void SListPopBack(SListNode** pplist);
 
// 单链表头删
void SListPopFront(SListNode** pplist);
 
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
 
// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x);
 
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
 
// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
 
// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos);
 
//销毁单链表
void SLTDestroy(SListNode** pphead);

好了好了，一个个来实现吧！

3.1.单链表打印


//单链表打印
void SListPrint(SListNode* plist)
{
		SListNode* cur = plist;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
}

这个打印的实现还是很简单的，我们只要遍历单链表在将每个节点的数据打印出来即可。

3.2.单链表尾插


//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	if (*pplist == NULL)//单链表为空
	{
		*pplist = BuySListNode(x);
	}
	else//单链表不为空
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)//找尾
		{
			tail = tail->next;
		}
		SListNode* newnode = BuySListNode(x);
		tail->next = newnode;
	}
}

这个尾插的实现来说，正常情况下先找到单链表的最后一个节点（找尾），在让最后一个节点存储新申请节点的地址即可，所以要调用动态申请一个节点的函数（BuySListNode），这个函数已经让新申请的节点存储空指针和需要保存的数据了。但是要区别单链表是否为空（如果不加以区分单链表是否为空的话就会访问空指针），如果为空的话直接让*pplist保存新申请的节点地址即可。

3.3.单链表头插


//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}

对于头插的实现，只要让新申请的节点存储原来*pplist的地址，让*pplist保存新申请的节点的地址即可。

3.4.单链表尾删


//单链表尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* tail = *pplist;
	SListNode* fronttail = *pplist;
	while (tail->next != NULL)//找尾节点和尾节点前一个节点
	{
		fronttail = tail;
		tail = tail->next;
	}
	if (fronttail->next == NULL)//一个节点
	{
		*pplist = NULL;
		free(tail);
		tail = NULL;
		fronttail = NULL;
	}
	else//多个节点
	{
		free(tail);
		tail = NULL;
		fronttail->next = NULL;
	}
}

对于尾删，我们要区分单链表为空、单链表有一个节点和单链表有多个节点的情况。如果单链表为空就不能删除，断言即可。单链表一个节点的话，让*pplist保存空指针，free掉尾节点（也是头节点）。单链表有多个节点的话，free掉尾节点，让尾节点前一个节点保存空指针即可。（如果不区分一个节点和多个节点的情况，一律按多个节点情况来处理的话，当只有一个节点时，fronttail会成为野指针。）。

3.5.单链表头删


//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}

这个简单，只要free掉头节点（free掉之前需要保存头节点下一个节点地址，不然的话就找不到头节点下一个节点了），*pplist保存头节点下一个节点地址即可。

3.6.单链表查找


//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

这个实现的话，只要遍历单链表找到单链表节点中第一个出现的与x相等的val ，再返回该节点的地址即可，找不到就返回空指针。

3.7.单链表在pos位置之和插入值


//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}

实现这个功能的话，我们需要知道pos的值（这个值是某个节点的地址，可以通过单链表查找获得），然后的话让pos指向的节点存储新申请节点的地址，新申请的节点存储pos指向的节点的下一个节点的地址即可（这个地址记得提前用变量存储下来，如果在改变pos指向的节点存储的地址之前没有存储下来的话，就找不到pos指向节点的下一个节点了）。

3.8.单链表删除pos位置之后的值


// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);//防止删pos指向尾节点 
	SListNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}

这里需要注意防止单链表为空和防止pos指向尾节点（尾节点后面为空，不可删），断言即可。这个实现大致就是让pos指向的节点存储pos指向节点的后两个节点的地址，free掉pos指向节点后一个节点即可。

3.9.在pos的前面插入值


//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	assert(pphead);
	assert((!*pphead && !pos) || (*pphead && pos));
	if (*pphead == pos)
	{
		SListPushBack(pphead, x);
	}
	else
	{
		SListNode* frontpos = *pphead;
		while (frontpos->next != pos)//找pos前一个节点
		{
			frontpos = frontpos->next;
		}
		SListNode* newnode = BuySListNode(x);
		SListNode* next = frontpos->next;
		frontpos->next = newnode;
		newnode->next = next;
	}
}

如果单链表为空，直接调用单链表尾插（单链表头插也行）即可。不为空就找到pos指向节点的前一个节点，让pos指向节点的前一个节点存储新申请节点地址，让新申请节点存储pos指向节点的地址即可。

3.10.删除pos位置的值


// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(*pphead);//没有节点
	assert(pos);
	if ((*pphead)->next == NULL)//一个节点
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* frontpos = *pphead;
		while (frontpos->next != pos)//找pos前一个节点
		{
			frontpos = frontpos->next;
		}
		SListNode* next = pos->next;
		free(pos);
		frontpos->next = next;
	}
}

注意断言，防止单链表为空，为空不能删除。如果单链表有一个节点，直接调用单链表头删（单链表尾删也行）即可。如果有单链表有多个节点，大致的话让pos指向的节点前一个节点存储pos指向节点后一个节点地址，free掉pos指向节点即可。

3.11.销毁单链表


//销毁单链表
void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

如果不再使用单链表的话，可以销毁单链表。虽然单链表是动态申请的，不手动销毁的话结束程序也会自动销毁，但手动销毁是一个好习惯。这个实现也简单，遍历单链表一一销毁节点即可。

4.单链表的小应用

对于上面的单链表增删查改等等实现来说，鼠鼠我讲解的只是大概思想，我们只要懂得这些思想再注意一些细节就可完成上面代码的实现。单链表的实现不是唯一的，上面代码只是一种参考，最重要要懂得单链表的含义和增删查改等等思想。

鼠鼠我还是一样，写了一个工程来验证单链表增删查改等等功能的实现，有兴趣的读者老爷可以将以下三个文件（上面的实现代码都在slist.c里面了）放到一个工程玩玩！

4.1.slist.h


#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
 
typedef int SLTDateType;
 
 
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;
 
 
// 单链表打印
void SListPrint  (SListNode * plist);
 
 
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
 
 
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
 
 
// 单链表的尾删
void SListPopBack(SListNode** pplist);
 
 
// 单链表头删
void SListPopFront(SListNode** pplist);
 
 
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
 
 
// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x);
 
 
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
 
 
// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
 
 
// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos);
 
 
//销毁单链表
void SLTDestroy(SListNode** pphead);

4.2.slist.c


#define _CRT_SECURE_NO_WARNINGS
#include"slist.h"
 
 
//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
 
//单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	if (*pplist == NULL)//单链表为空
	{
		*pplist = BuySListNode(x);
	}
	else//单链表不为空
	{
		SListNode* tail = *pplist;
		while (tail->next != NULL)//找尾
		{
			tail = tail->next;
		}
		SListNode* newnode = BuySListNode(x);
		tail->next = newnode;
	}
}
 
//单链表打印
void SListPrint(SListNode* plist)
{
		SListNode* cur = plist;
		while (cur != NULL)
		{
			printf("%d->", cur->data);
			cur = cur->next;
		}
		printf("NULL\n");
}
 
//单链表头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	assert(pplist);
	SListNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
	*pplist = newnode;
}
 
//单链表尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* tail = *pplist;
	SListNode* fronttail = *pplist;
	while (tail->next != NULL)//找尾节点和尾节点前一个节点
	{
		fronttail = tail;
		tail = tail->next;
	}
	if (fronttail->next == NULL)//一个节点
	{
		*pplist = NULL;
		free(tail);
		tail = NULL;
		fronttail = NULL;
	}
	else//多个节点
	{
		free(tail);
		tail = NULL;
		fronttail->next = NULL;
	}
}
 
//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SListNode* next = (*pplist)->next;
	free(*pplist);
	*pplist = next;
}
 
//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
 
// 单链表在pos位置之后插入值
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
	SListNode* next = pos->next;
	pos->next = newnode;
	newnode->next = next;
}
 
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);//防止删pos指向尾节点 
	SListNode* next = pos->next->next;
	free(pos->next);
	pos->next = next;
}
 
// 在pos的前面插入值
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{
	assert(pphead);
	assert((!*pphead && !pos) || (*pphead && pos));
	if (*pphead == pos)
	{
		SListPushBack(pphead, x);
	}
	else
	{
		SListNode* frontpos = *pphead;
		while (frontpos->next != pos)//找pos前一个节点
		{
			frontpos = frontpos->next;
		}
		SListNode* newnode = BuySListNode(x);
		SListNode* next = frontpos->next;
		frontpos->next = newnode;
		newnode->next = next;
	}
}
 
// 删除pos位置的值
void SLTErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(*pphead);//没有节点
	assert(pos);
	if ((*pphead)->next == NULL)//一个节点
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* frontpos = *pphead;
		while (frontpos->next != pos)//找pos前一个节点
		{
			frontpos = frontpos->next;
		}
		SListNode* next = pos->next;
		free(pos);
		frontpos->next = next;
	}
}
 
//销毁单链表
void SLTDestroy(SListNode** pphead)
{
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

4.3.test.c


#define _CRT_SECURE_NO_WARNINGS
#include"slist.h"
void menu()
{
	printf("**********************\n");
	printf("********0.退出********\n");
	printf("****1.头插  2.头删****\n");
	printf("****3.尾插  4.尾删****\n");
	printf("****5.查找  6.打印****\n");
	printf("*7.在pos位置之后插入值\n");
	printf("*8.删除pos位置之后的值\n");
	printf("*9.在pos的前面插入值**\n");
	printf("*10.删除pos位置的值***\n");
	printf("**********************\n");
}
int main()
{
	SListNode* pplist = NULL;
	int input;
	do
	{
		menu();
		printf("请输入你想操作的数字：->");
		scanf("%d", &input);
		if (input == 0)
		{
			SLTDestroy(&pplist);
			printf("\n");
			break;
		}
		else if (input == 1)
		{
			int number = 0;
			printf("请输入你要头插数据的个数：->");
			scanf("%d", &number);
			printf("请输入你要头插的数据：->");
			while (number--)
			{
				SLTDateType x = 0;
				scanf("%d", &x);
				SListPushFront(&pplist, x);
			}
			printf("\n");
		}
		else if (input == 2)
		{
			SListPopFront(&pplist);
			printf("\n");
		}
		else if (input == 3)
		{
			int  number = 0;
			printf("请输入你要尾插数据的个数：->");
			scanf("%d", &number);
			printf("请输入你要尾插的数据：->");
			int i = 0;
			for (i = 0; i < number; i++)
			{
				SLTDateType x = 0;
				scanf("%d", &x);
				SListPushBack(&pplist, x);
			}
			printf("\n");
		}
		else if (input == 4)
		{
			SListPopBack(&pplist);
			printf("\n");
		}
		else if (input == 5)
		{
			SLTDateType x = 0;
			printf("请输入你要查找的值：->");
			scanf("%d", &x);
			SListNode* p = SListFind(pplist, x);
			if (p != NULL)
			{
				printf("你要查找的值地址是%p\n", p);
			}
			else
			{
				printf("找不到！\n");
			}
			printf("\n");
		}
		else if (input == 6)
		{
			SListPrint(pplist);
			printf("\n");
		}
		else if (input == 7)
		{
			SLTDateType x = 0,pos = 0;
			printf("请分别输入你要插入的值及pos指向的值：->");
			scanf("%d %d", &x, &pos);
			SListInsertAfter( SListFind(pplist,pos), x);
			printf("\n");
		}
		else if (input == 8)
		{
			SLTDateType pos = 0;
			printf("请输入pos指向的值：->");
			scanf("%d", &pos);
			SListEraseAfter(SListFind(pplist, pos));
			printf("\n");
		}
		else if (input == 9)
		{
			SLTDateType x = 0, pos = 0;
			printf("请分别输入你要插入的值及pos指向的值：->");
			scanf("%d %d", &x, &pos);
			SLTInsert(&pplist, SListFind(pplist, pos), x);
			printf("\n");
		}
		else if (input == 10)
		{
			SLTDateType pos = 0;
			printf("请输入pos指向的值：->");
			scanf("%d", &pos);
			SLTErase(&pplist, SListFind(pplist, pos));
			printf("\n");
		}
		else
		{
			printf("输入错误，请重新输入：->");
		}
	} while (input);
	return 0;
}

5.ending

鼠鼠我呀不怎么会写博客，读者老爷看到这里如果觉得不好就多多包涵，看看图一乐也不是不行。当然如有不足，恳请斧正哈！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/390503