纯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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。