数据结构——链表

本篇博客是关于链表内容的博客

树之羽

1442人浏览 · 2024-04-17 00:21:06

树之羽 · 2024-04-17 00:21:06 发布

(一).单链表的概念及结构

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

那么链表的结构是什么呢？下面我将通过火车的例子来说明：

这里我们通过火车车厢依次连接的例子来说明，火车的结构就和链表的结构相似，链表的删减就和火车的车厢的增减一样，每节车厢都是单独存在的，互不干涉；同样我们的链表也是这样，每个节点都是单独存在的，互补干扰。车厢每节都有单独的车门那么我们就需要一把钥匙，用这把钥匙来打开对应车厢，假设每节车厢都是锁上的，那么我们怎样打开下一节车厢呢？最后的办法就是将钥匙留在上一节车厢里面；同样链表中上一个节点怎样连接下一个节点呢？，这里我们就会通过指针来连接下一个节点，用指针来存储下一节点的地址放在上一个节点当中我们就可以找到下一节点了。

那么在链表中我们的节点是怎样连接呢？我们可以看看以下一个图

这里的plist指的是头节点也就是我们说的哨兵位，它里面是不存放数据的，纯指针用来存放第一个节点的地址用的，而我们同样也可以从图里面得知每个节点是由两部分组成的“当前节点要保存的数据和指向下一节点的指针两部分组成”。

这里大家可能还会有点疑惑为要指针来保存下一节点的地址呢？

这里每个节点它都会单独去申请一块空间，用来存储当前节点的数据，而并非是有顺序的，所以这里我们只有用一个指针变量来存储下一个节点的地址我们才能将一个一个节点连接起来。

那链表的结构是怎样的呢？

typedef struct ListNode {
	int data;//节点数据
	struct ListNode* next;//指针变量⽤保存下⼀个节点的地址
}SLTNode;

将链表的形式写成代码的形式就是这样的：带点数据+指针变量用保存下一个节点的地址。

注意：

补充说明：

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、节点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

好了以上就是链表的概念和结构。

(二).单链表的分类

链表的结构多种多样，具体我们可以分为以下2*2*2=8种：

这个图里面每个颜色是一种总共有八种，下面我将用图的形式来说明带头和不带头，单向和双向，循环和不循环这几种分别是什么意思，

1.带头和不带头

2.单向和双向

3.循环和不循环

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表

这里链表的分类虽然有那么多种但是我们只需要把上面这两种最关键的结构掌握了就可以了，单链表属于是最简单的一种情况，而双向带头循环链表属于最复杂的链表但当我们掌握了单链表的实现之后我们会发现双向带头循环链表也非常简单。

(三).单链表的实现

这里我将带领大家实现不带头单向不循环链表因为这种链表最容易理解当我们理解了这种链表之后其余的链表也就很容易实现了。

首先，进行单链表结构的创建。

typedef int SLTDataType;//int型定义成SLTDataType有利于对int的统一改变
typedef struct ListNode {
	SLTDataType data;//节点数据
	struct ListNode* next;//指针变量⽤保存下⼀个节点的地址
}SLTNode;

3.1单链表节点的尾插

//开辟一个新的节点
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)
{
	//首先要判断链表是否为空
	SLTNode* newnode = SLTbuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	
	else
	{
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}//跳出时plist->next=NULL;
		ptail->next = newnode;

	}
}

尾插我们需要注意的是要判断链表是否为空，创建新节点时也要判断是否动态开辟空间是否开辟成功。

3.2单链表节点的头插

//头插
void SLTpushfront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);//首先头节点必须要存在不然无法进行头插
	SLTNode* newnode = SLTbuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头插的时候我们需要注意的是必须要首先断言头头节点不为空，如果头节点为空的话那就无法进行头插。

3.3单链表节点的尾删

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else {
		SLTNode* ptail = *pphead;
		SLTNode* pcur = *pphead;
		while (ptail->next)
		{
			pcur = ptail;//这里用pcur将ptail的前一个指针存下来
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		pcur->next = NULL;
	}
}

尾删我们需要注意的是要断言链表不能为空，并且也要注意当链表中只有一个节点的情况。

3.4单链表节点的头删

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

3.5单链表节点的查找

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

3.6在指定位置之前插⼊数据

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTpushfront(pphead, x);
	}
	else
	{
		if ((*pphead)->next != pos)
		{
			*pphead = (*pphead)->next;
		}
		SLTNode* newnode = SLTbuyNode(x);
		newnode->next = (*pphead)->next;
		(*pphead)->next = newnode;
	}
}

这里要特别注意在插入之前必须要断言pos位置必须要存在。

3.7在指定位置之后插⼊数据

//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTbuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

}

3.8删除pos节点

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* ptail = *pphead;
		if (ptail->next != pos)
		{
			ptail = ptail->next;
		}
		ptail->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

这里我们需要注意的是当pos=*pphead时代码就相当于头删。

3.9删除pos之后的节点

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

3.10打印链表

void SLPrint(SLTNode* phead)
{
	SLTNode* pur = phead;
	while (pur != NULL)
	{
		printf("%d->", pur->data);
		pur = pur->next;
	}
	printf("NULL\n");
}

3.11销毁链表

void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = NULL;
		pcur = next;
	}
	*pphead = NULL;
}

（四）.代码汇总

SqList.h:

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

typedef int SLTDataType;//int型定义成SLTDataType有利于对int的统一改变
typedef struct ListNode {
	SLTDataType data;//节点数据
	struct ListNode* next;//指针变量⽤保存下⼀个节点的地址
}SLTNode;

////打印链表
void SLPrint(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 SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

SqList.c:

#include"SqList.h"

void SLPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (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)
{
	//首先要判断链表是否为空
	SLTNode* newnode = SLTbuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	
	else
	{
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}//跳出时plist->next=NULL;
		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* ptail = *pphead;
		SLTNode* pcur = *pphead;
		while (ptail->next)
		{
			pcur = ptail;//这里用pcur将ptail的前一个指针存下来
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		pcur->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)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTpushfront(pphead, x);
	}
	else
	{
		if ((*pphead)->next != pos)
		{
			*pphead = (*pphead)->next;
		}
		SLTNode* newnode = SLTbuyNode(x);
		newnode->next = (*pphead)->next;
		(*pphead)->next = newnode;
	}
}


//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTbuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

}

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* ptail = *pphead;
		if (ptail->next != pos)
		{
			ptail = ptail->next;
		}
		ptail->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}


//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = NULL;
		pcur = next;
	}
	*pphead = NULL;
}

test.c:

#include"SqList.h"

void SqListtest01()
{
	SLTNode* plist = NULL;
	SLTpushback(&plist, 1);
	SLTpushback(&plist, 2);
	SLTpushback(&plist, 3);
	SLTpushback(&plist, 4);
	SLPrint(plist);
	SLTpushfront(&plist, 55);
	SLPrint(plist);
	SLTPopBack(&plist);
	SLPrint(plist);
	SLTPopFront(&plist);
	SLPrint(plist);
	SLTNode* Find=SLTFind(plist, 2);
	if (Find == NULL)
	{
		printf("没找到了!\n");
	}
	else
	{
		printf("找到了！\n");
	}
	SLTInsert(&plist, Find, 99);
	SLPrint(plist);
	SLTInsertAfter(Find, 66);
	SLPrint(plist);
	SLTEraseAfter(Find);
	SLPrint(plist);
	SLTErase(&plist, Find);
	SLPrint(plist);
	SListDesTroy(&plist);
	SLPrint(plist);
}



int main()
{
	SqListtest01();


	return 0;
}

（五）.总结

对于单链表的实现我们要尽可能自己多的去进行代码实现，这样我们才能更好的掌握关于单链表的知识，对于单链表的增删查找每个里面都有许多值得我们特别注意的地方，当我们把该注意的都注意到了这时我们在自己实现的时候在一步一步的去测试，这样就能减少出现bug,好了以上就是我要跟大家分享的单链表的知识。

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

手把手｜VSCode搭建Claude编程环境，低成本用AI写代码

2048 AI社区

带来 Multi Agent 开发，OpenSolon v3.8.3 发布

penSolon 是新一代，Java 企业级应用开发框架。。采用商用友好的 Apache 2.0 开源协议，是“杭州无耳科技有限公司”开源的根级项目，是 Java 应用开发的生态基座（可替换美国博通公司的 Spring 生态）。7年开源时间，累计代码提交1.6万次，近半年下载量1200万次。

2048 AI社区

如何解决后端API服务配置自签名证书时APIM请求报错500：Error occured while calling backend service

但由于使用的自签名证书的根CA，中间证书都不是受信任机构所颁发的证书，所以在操作系统中没有内置CA信息，所以被浏览器认为这是不受信任的证书。当本地证书库中包含了这个服务器证书的中间证书，根证书后，浏览器访问就会被信任。在AIPM的证书管理页面，因为我们的服务器证书是一张包含根证书，中间证书，服务器证书的完整证书链证书，所以心想，是否可以直接上转这一张证书就可以了呢？所以openSSL生成的.crt