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

这篇具有很好参考价值的文章主要介绍了纯c实现链表 数据结构大全。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

        介绍

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

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

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

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

        这次还是默认存储的数据为整形,要是想修改存储类型的话也很简便,使用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;
}

完整代码 

最后给出完整代码,可以和最前面的头文件一起使用文章来源地址https://www.toymoban.com/news/detail-793751.html

#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;
}

到了这里,关于纯c实现链表 数据结构大全的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • <数据结构> 链表 - 单链表(c语言实现)

    哨兵位结点也叫哑节点。哨兵位结点 也是头结点 。该节点 不存储有效数据,只是为了方便操作 (如尾插时用带哨兵位的头结点很爽,不需要判空)。 有哨兵位结点的链表,第一个元素应该是链表第二个节点(head - next,head为哨兵位结点)对应的元素。 有哨兵位结点的链表

    2023年04月11日
    浏览(113)
  • 【数据结构】—C语言实现双向链表(超详细!)

                                          食用指南:本文在有C基础的情况下食用更佳                                       🔥 这就不得不推荐此专栏了:C语言                                     🍀 双向链表 前 置知识 :单链表      

    2024年02月13日
    浏览(49)
  • 【数据结构】C语言实现双向链表(带头结点、循环)

    结点定义: 接口定义: 我们将申请结点的代码封装成函数,方便后续使用 由于是带头结点的双向链表,因此在使用链表前,我们需要对链表进行初始化。 遍历链表,值得说的是,带头结点的双向链表的循环结束条件是 cur != phead 尾插时,需要先找到尾结点,然后将新结点插

    2024年02月03日
    浏览(68)
  • (c语言实现)数据结构链表oj题(2)

    🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介::分析力扣中有关链表的部分题目. 题目来源于:牛客网-题目链接 输入一个链表,输出该链表中倒数第k个结点。 示例: 输入:1,{1,2,3,4,5} 返回值:{5} 创建两个指针: ①

    2024年02月04日
    浏览(53)
  • 【数据结构】链表OJ题(顺序表)(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年02月05日
    浏览(43)
  • [C语言][数据结构][链表] 双链表的从零实现!

    目录 零.必备知识 0.1 一级指针 二级指针 0.2 双链表节点的成员列表         a. 数据         b. 后驱指针         c. 前驱指针 0.3 动态内存空间的开辟 一. 双链表的实现与销毁         1.1 节点的定义         1.2 双向链表的初始化 创建新节点         1.3 尾插       

    2024年04月17日
    浏览(202)
  • [C语言][数据结构][链表] 单链表的从零实现!

    目录 零.必备知识 1.一级指针 二级指针 2. 节点的成员列表     a.数据     b.指向下一个节点的指针. 3. 动态内存空间的开辟 (malloc-calloc-realloc) 一.单链表的实现与销毁          1.1 节点的定义         1.2 单链表的尾插         1.3 单链表的头插         1.4 单链表的尾删  

    2024年04月11日
    浏览(72)
  • c语言数据结构——链表的实现及其基本操作

    顺序表的问题及思考 问题: 中间/头部的插入删除,时间复杂度为O(N) 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插

    2023年04月09日
    浏览(82)
  • c语言数据结构实验:链表实现学生信息的储存

    进入正题 本文作者同为大一新生,写这篇文章的目的是记录自己的学习经历,以及帮助一些稍有困难的同学理解数据结构,能力有限,如有错误请指出。本文基于严蔚敏老师的《数据结构与算法(c语言版 第二版)》创作。(建议学习的时候搭配着书看) 学习前提 : 1.本文

    2024年02月03日
    浏览(39)
  • 【数据结构初阶】四、线性表里的链表(带头+双向+循环 链表 -- C语言实现)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】三、 线性表里的链表(无头+单向+非循环链表 -- C语言实现)-CSDN博客  ====

    2024年02月08日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包