纯c实现链表数据结构大全

2024-01-16 12:36:04
开发
30

介绍

我们已经知道数组是连续的内存地址，顺序表是由数组为基础的一种数据结构，拥有比数组更多的功能，在概念上属于线性结构，跟链表不同的是，顺序表在物理结构上也是线性的。

我们现在写的链表在物理结构上就不是线性的，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/节点” 节点的组成主要有两个部分：当前节点要保存的数据和保存下⼀个节点的地址（指针变量）。

链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

这次还是默认存储的数据为整形，要是想修改存储类型的话也很简便，使用typedef关键字，这里就不再赘述了。

头文件

为了避免你们复制的代码报错，我想把完整的头文件打出来

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义链表节点的结构
typedef int SLDataType;
typedef struct SListNode {
	SLDataType data;//要保存的数据
	struct SListNode* next;
}SLNode;

//我来创建几个结点组成一个链表，并打印链表
void SLPrint(SLNode* phead);

//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
void SLPushFront(SLNode** pphead, SLDataType x);
//删除
void SLPopBack(SLNode** pphead);
void SLPopFront(SLNode** pphead);

//找节点，这里的第一个参数写一级指针还是二级指针
//这里传一级实际上就可以了，因为不改变头结点
//但是这里要写二级指针，因为要保持接口一致性
SLNode* SLFind(SLNode** pphead, SLDataType x);

//指定位置的插入删除
//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x);
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x);
//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos);
//删除pos之后节点
void SLEraseAfter(SLNode* pos);

//销毁链表
void SLDesTroy(SLNode** pphead);

核心.c文件的实现

定义

这里是对链表基础结构体的定义

typedef struct SListNode 
{
	SLDataType data;//要保存的数据
	struct SListNode* next;
}SLNode;

打印

直到找到最后面的空指针才停止打印

void SLPrint(SLNode* phead) 
{
	//循环打印
	SLNode* pcur = phead;
	while (pcur != NULL)
	{
		printf("%d ->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

创建新节点

引用上文链表中每个节点都是独⽴申请的（即需要插⼊数据时才去申请⼀块节点的空间），我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。

//创建新节点
SLNode* SLBuyNode(SLDataType x) 
{
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	node->data = x;
	node->next = NULL;
	return node;
}

后面的每一个操作都要考虑三种情况，在最前面，在中间，在末尾，这样才能保证代码的鲁棒性

尾插

先找到尾端再插入数据，注意特判链表为空

//尾插
void SLPushBack(SLNode** pphead, SLDataType x) 
{
	assert(pphead);
	SLNode* node = SLBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = node;
		return;
	}
	//说明链表不为空,找尾
	SLNode* pcur = *pphead;
	while (pcur->next)
	{
		pcur = pcur->next;
	}
	pcur->next = node;
}

头插

头插比较简单，注意更新pphead即可

//头插
void SLPushFront(SLNode** pphead, SLDataType x) 
{
	assert(pphead);
	SLNode* node = SLBuyNode(x);
	//新节点跟头结点连接起来
	node->next = *pphead;//plist
	//让新的节点成为头结点
	*pphead = node;
}

尾删

还是注意特判只有一个节点的情况

//尾删
void SLPopBack(SLNode** pphead) 
{
	assert(pphead);
	//第一个节点不能为空
	assert(*pphead);
	//只有一个节点的情况
	if ((*pphead)->next == NULL) 
	{
		//直接把头结点删除
		free(*pphead);
		*pphead = NULL;
	}
	else 
	{
		//有多个节点的情况
		//找尾结点和尾结点的前一个节点
		SLNode* prev = NULL;
		SLNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev的next指针不再指向ptail，而是指向ptail的下一个节点
		prev->next = ptail->next;
		free(ptail);
		//为什么必须要置为空？代码后面明明没有再使用ptail？打印链表方法里有判断节点的地址是否为空
		ptail = NULL;
	}
}

头删

较为简单，更新头指针即可，注意将原来的置为空指针

//头删
void SLPopFront(SLNode** pphead) 
{
	assert(pphead);
	assert(*pphead);
	SLNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;//出于代码规范
}

查找结点

通过遍历查找第一个为x的元素位置，主要是在后续删除接口需要用

//查找第一个为X的节点
SLNode* SLFind(SLNode** pphead, SLDataType x) 
{
	assert(pphead);
	SLNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x) 
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

在指定位置之前插入数据

注意特判只有一个头节点

//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) 
{
	assert(pphead);
	//约定链表不能为空，pos也不能为空
	assert(pos);
	assert(*pphead);
	SLNode* node = SLBuyNode(x);
	//pos刚好是头结点，头插
	if (pos == *pphead) 
	{
		node->next = *pphead;
		*pphead = node;
		return;
	}
	//找pos的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)//第一次循环的时候（缺少pos刚好是第一个节点的判断）
	{
		prev = prev->next;
	}
	//prev node  pos
	node->next = pos;
	prev->next = node;
}

在指定位置之后插入数据

找到结点直接插入，不用考虑是否只有一个结点

//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);
	SLNode* node = SLBuyNode(x);
	//pos  node  pos->next
	node->next = pos->next;
	pos->next = node;
}

删除pos节点

特判只有一个结点的情况，然后遍历找到pos前面的结点，直接free掉+置为空指针

//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos) 
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(pos);
		return;
	}
	//找pos的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;//只是规范
}

删除pos之后节点

直接free，不用考虑是否只有一个节点

//删除pos之后节点
void SLEraseAfter(SLNode* pos) 
{
	assert(pos && pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
}

销毁链表

遍历free掉全部结点，再将头节点置为空指针，防止野指针出现

//销毁链表
void SLDesTroy(SLNode** pphead) 
{
	assert(pphead);
	SLNode* pcur = *pphead;
	//循环删除
	while (pcur)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

完整代码

最后给出完整代码，可以和最前面的头文件一起使用

#define _CRT_SECURE_NO_WARNINGS
#include "slit.h"

void SLPrint(SLNode* phead) 
{
	//循环打印
	SLNode* pcur = phead;
	while (pcur != NULL)
	{
		printf("%d ->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//创建新节点
SLNode* SLBuyNode(SLDataType x) 
{
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	node->data = x;
	node->next = NULL;
	return node;
}
//尾插
void SLPushBack(SLNode** pphead, SLDataType x) 
{
	assert(pphead);
	SLNode* node = SLBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = node;
		return;
	}
	//说明链表不为空,找尾
	SLNode* pcur = *pphead;
	while (pcur->next)
	{
		pcur = pcur->next;
	}
	pcur->next = node;
}
//头插
void SLPushFront(SLNode** pphead, SLDataType x) 
{
	assert(pphead);
	SLNode* node = SLBuyNode(x);
	//新节点跟头结点连接起来
	node->next = *pphead;//plist
	//让新的节点成为头结点
	*pphead = node;
}
//尾删
void SLPopBack(SLNode** pphead) 
{
	assert(pphead);
	//第一个节点不能为空
	assert(*pphead);
	//只有一个节点的情况
	if ((*pphead)->next == NULL) 
	{
		//直接把头结点删除
		free(*pphead);
		*pphead = NULL;
	}
	else 
	{
		//有多个节点的情况
		//找尾结点和尾结点的前一个节点
		SLNode* prev = NULL;
		SLNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev的next指针不再指向ptail，而是指向ptail的下一个节点
		prev->next = ptail->next;
		free(ptail);
		//为什么必须要置为空？代码后面明明没有再使用ptail？打印链表方法里有判断节点的地址是否为空
		ptail = NULL;
	}
}
//头删
void SLPopFront(SLNode** pphead) 
{
	assert(pphead);
	assert(*pphead);
	SLNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;//出于代码规范
}

//查找第一个为X的节点
SLNode* SLFind(SLNode** pphead, SLDataType x) 
{
	assert(pphead);
	SLNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x) 
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}


//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x) 
{
	assert(pphead);
	//约定链表不能为空，pos也不能为空
	assert(pos);
	assert(*pphead);
	SLNode* node = SLBuyNode(x);
	//pos刚好是头结点，头插
	if (pos == *pphead) 
	{
		node->next = *pphead;
		*pphead = node;
		return;
	}
	//找pos的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)//第一次循环的时候（缺少pos刚好是第一个节点的判断）
	{
		prev = prev->next;
	}
	//prev node  pos
	node->next = pos;
	prev->next = node;
}
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);
	SLNode* node = SLBuyNode(x);
	//pos  node  pos->next
	node->next = pos->next;
	pos->next = node;
}
//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos) 
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(pos);
		return;
	}
	//找pos的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;//只是规范
}
//删除pos之后节点
void SLEraseAfter(SLNode* pos) 
{
	assert(pos && pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
}
//销毁链表
void SLDesTroy(SLNode** pphead) 
{
	assert(pphead);
	SLNode* pcur = *pphead;
	//循环删除
	while (pcur)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

原文地址:https://blog.csdn.net/2302_79128004/article/details/135578666 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1747115474887512064.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部