🏝️专栏：【数据结构实战篇】

🌅主页：f狐o狸x

目录

一、链表的概念及结构

二、链表的分类

        2.1 单向的或双向的

        2.2 带头的或不带头的

        2.3 循环或非循环

        三、链表的实现

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

        3.2 尾插一个数

        3.3 头插一个数

        3.4 尾删一个数

 3.5 头删一个数

        3.6 查找数据

        3.7 pos位置插入数据

        3.8 pos位置删除数据

         3.9 销毁链表

四、链表代码

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

一、链表的概念及结构

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

        我们可以看出：

        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

# 数据结构 # 链表 # c语言 # 数据挖掘 # 机器学习
Logo
松山湖开发者村综合服务平台

助力广东及东莞地区开发者，代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展，成为松山湖开发者首选的工作与学习平台

更多推荐

cover

基于YOLOv8深度学习的智慧农业柑橘病害识别检测系统(PyQt5界面+数据集+训练代码)

avatar 松山湖开发者村综合服务平台
cover

【Kafka】与【Hadoop】的集成应用案例深度解析

avatar 松山湖开发者村综合服务平台
cover

SpringBoot 整合 RabbitMQ

avatar 松山湖开发者村综合服务平台