【数据结构实战】从零开始打造你的专属链表

f狐o狸x

发布于 2024-11-19 17:31:40

5300

代码可运行

文章被收录于专栏：【数据结构实战篇】【数据结构实战篇】

运行总次数：0

代码可运行

本期我们接着上期的来，开始我们的链表环节

一、链表的概念及结构

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

我们可以看出： 1. 链表结构在逻辑上是连续的，在物理上不一定连续 2. 现实中，每一个节点都需要用malloc向堆栈申请 3. 申请出来的空间可能连续，也有可能是不连续的

二、链表的分类

实际中链表的结构非常多样，这里介绍几种类别

2.1 单向的或双向的

2.2 带头的或不带头的

带头的链表也被称为哨兵位

2.3 循环或非循环

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

三、链表的实现

我们先实现单链表

typedef int SLDataType;

typedef struct SListNode
{
	SLDataType data;
	struct SList* next;
}SListNode;

先在头文件中声明好单链表

3.1 打印和动态申请一个结点

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

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));
	if (newcode == NULL)
	{
		perror("SListPushBack::malloc");
		return NULL;
	}
	newcode->next = NULL;
	newcode->data = x;
	return newcode;
}

3.2 尾插一个数

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	SListNode* newcode = BuySListNode(x);
	//检查单链表是否为空
	if (*pplist == NULL)
	{
		*pplist = newcode;
	}
	else
	{
		SListNode* tail = *pplist;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newcode;
	}
}

3.3 头插一个数

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	SListNode* NewCode = BuySListNode(x);
	NewCode->next = *pplist;
	*pplist = NewCode;
}

3.4 尾删一个数

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
	//只有一个节点
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		//找尾	
		SListNode* tail = *pplist;
		SListNode* prev = NULL;;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		//删除节点
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}

}

也可以这样尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
	//只有一个节点
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	else
	{
		找尾	
		//SListNode* tail = *pplist;
		//SListNode* prev = NULL;;
		//while (tail->next)
		//{
		//	prev = tail;
		//	tail = tail->next;
		//}
		删除节点
		//free(tail);
		//tail = NULL;
		//prev->next = NULL;

		SListNode* tail = *pplist;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		//删除节点
		free(tail->next);
		tail->next = NULL;

		
	}

}

3.5 头删一个数

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

3.6 查找数据

找到数据返回该节点的地址，找不到则返回null

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

3.7 pos位置插入数据

利用查找函数找到数据的地址之后，在该节点前面插入数据

// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{
	assert(pplist);
	assert(pos);
	//申请一个节点
	SListNode* NewNode = BuySListNode(x);
	//找到pos前的位置
	SListNode* prev = NULL;
	SListNode* cur = *pplist;
	//第一个位置插入
	if (pos == *pplist)
	{
		//直接头插
		SListPushFront(pplist, x);
	}
	//其他位置插入
	else
	{
		while (cur)
		{
			if (cur == pos)
			{
				prev->next = NewNode;
				NewNode->next = cur;
			}
			prev = cur;
			cur = cur->next;
		}
	}
}

3.8 pos位置删除数据

同理，先找到数据节点的位置，再删除

// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(pos);
	//pos是第一个节点
	if (pos == *pplist)
	{
		//直接头删
		SListPopFront(pplist);
	}
	//其他位置删除
	else
	{
		//找到pos前的位置
		SListNode* prev = *pplist;
		SListNode* cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = cur->next;
		free(cur);
		cur = NULL;
	}
}

3.9 销毁链表

每次申请一个节点我们都用到了malloc开辟了一块空间，记得归还，有借有还，再借不难~

void DestorySList(SListNode** pplist)
{
	SListNode* del = NULL;
	while (*pplist)
	{
		del = *pplist;
		*pplist = (*pplist)->next;
		free(del);
		del = NULL;
	}
	pplist = NULL;
}

四、链表代码

#define  _CRT_SECURE_NO_WARNINGS 1;

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

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x);
// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos);


#define  _CRT_SECURE_NO_WARNINGS 1;

#include "SList.h"

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

// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newcode = (SListNode*)malloc(sizeof(SListNode));
	if (newcode == NULL)
	{
		perror("SListPushBack::malloc");
		return NULL;
	}
	newcode->next = NULL;
	newcode->data = x;
	return newcode;
}

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	SListNode* newcode = BuySListNode(x);
	//检查单链表是否为空
	if (*pplist == NULL)
	{
		*pplist = newcode;
	}
	else
	{
		SListNode* tail = *pplist;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newcode;
	}
}

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	SListNode* NewCode = BuySListNode(x);
	NewCode->next = *pplist;
	*pplist = NewCode;
 }

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);
	//只有一个节点
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	//多个节点

	else
	{
		找尾	
		//SListNode* tail = *pplist;
		//SListNode* prev = NULL;;
		//while (tail->next)
		//{
		//	prev = tail;
		//	tail = tail->next;
		//}
		删除节点
		//free(tail);
		//tail = NULL;
		//prev->next = NULL;

		SListNode* tail = *pplist;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		//删除节点
		free(tail->next);
		tail->next = NULL;

		
	}

}

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

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

// pos之前插入
void SListInsert(SListNode** pplist, SListNode* pos, SLTDataType x)
{
	assert(pplist);
	assert(pos);
	//申请一个节点
	SListNode* NewNode = BuySListNode(x);
	//找到pos前的位置
	SListNode* prev = *pplist;
	SListNode* cur = *pplist;
	//第一个位置插入
	if (pos == *pplist)
	{
		//直接头插
		SListPushFront(pplist, x);
	}
	//其他位置插入
	else
	{
		while (cur!=pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NewNode;
		NewNode->next = cur;
	}
}

// pos位置删除
void SLTErase(SListNode** pplist, SListNode* pos)
{
	assert(pplist);
	assert(pos);
	//pos是第一个节点
	if (pos == *pplist)
	{
		//直接头删
		SListPopFront(pplist);
	}
	//其他位置删除
	else
	{
		//找到pos前的位置
		SListNode* prev = *pplist;
		SListNode* cur = *pplist;
		while (cur != pos)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = cur->next;
		free(cur);
		cur = NULL;
	}
}

// 销毁链表
void DestorySList(SListNode** pplist)
{
	SListNode* del = NULL;
	while (*pplist)
	{
		del = *pplist;
		*pplist = (*pplist)->next;
		free(del);
		del = NULL;
	}
	pplist = NULL;
}

坚持学习！当你快扛不住的时候，困难也快扛不住了！

留下你宝贵的三连叭~ QAQ