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

发布时间：2024年01月16日

? ? ? ? 介绍

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

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

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

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

? ? ? ? 这次还是默认存储的数据为整形，要是想修改存储类型的话也很简便，使用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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

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