【数据结构】—C语言实现单链表(超详细!)

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

【数据结构】—C语言实现单链表(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表

                                     食用指南:本文在有C基础的情况下食用更佳

                                    🔥这就不得不推荐此专栏了: C语言

                                    ♈️今日夜电波: あなたは煙草 私はシャボン——今泉愛夏 

                                                                    1:31 ━━━━━━️💟──────── 4:36
                                                                            🔄   ◀️   ⏸   ▶️    ☰

                                   💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍 


目录

一、单链表介绍

单链表是什么?

单链表需要实现的基本功能?

单链表的基本结构是怎么样的?

二、总体思路

        结构体定义

        接口函数定义

三、具体每个接口函数的实现

        1、打印

        2、申请新的节点

        3、尾插

        4、头插

        5、尾删

        6、头删

        7、找节点(用于后续的插入以及删除操作)

        8、基于第7小点在pos之前插入x

        9、基于第7小点在pos以后插入x

        10、基于第7小点删除pos位置

        11、基于第7小点删除pos的后一个位置

        12、销毁链表,释放空间

四、总体代码

1、头文件

2、主体函数文件

3、测试用例


一、单链表介绍

单链表是什么?

        单链表是一种常见的数据结构,它由一个个节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。

单链表需要实现的基本功能?

        基本的操作为:增、删、查、改

        具体为:

  1. 插入元素:将新元素插入到链表的指定位置,可以是链表的头部、尾部或中间位置。
  2. 删除元素:从链表中删除指定位置的元素。
  3. 查找元素:根据给定的值,在链表中查找对应的元素,并返回其位置。
  4. 遍历链表:按顺序访问链表中的每个元素。
  5. 获取链表长度:获取链表中元素的个数。
  6. 判断链表是否为空:判断链表是否为空链表。
  7. 清空链表:删除链表中的所有元素,使其成为一个空链表。

单链表的基本结构是怎么样的?

        一张图让你理解

        注:此文实现的是没有带哨兵的单链表

【数据结构】—C语言实现单链表(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表

        注意:最后一个节点的next指针指向的是NULL


二、总体思路

        如何实现?按照单链表的基本介绍以及功能来一步一步实现!首先实现什么?->节点!最基本的元素,没有节点之后的都实现不了。接着实现什么?接口!按照功能将每一个接口都写好,以此来保证后续所写功能的连续性。最后,按照接口将每一个功能都实现即可!注意在编写的过程中也要反复的比对接口,及时修改接口的传参或者地址的传递。

        对此节点定义如下:

        结构体定义

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

        int 型 data 用于储存数据,结构体指针型 next 用于指向下一个节点。

        接口函数定义

//打印
void SLTPrint(SLTNode* phead);
//生成新的节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
// 找节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);

       重点:

        此为对本版本单链表的不断优化后得到的接口。其中* phead 存储的是结构体类型的地址,即:他是用于改变结构体内的数据而设置的,* pos也是同理。而重点在于**pphead,他存储的结构体指针的地址,他是用于改变结构体指针的,即改变的是结构体的地址。x则是用于传参,输入需要添加的数据。

        你可能有个疑问,在此处为什么要使用**pphead呢?

        注意看在用到**pphead的函数,其中大多都是插入以及删除的操作,仔细看操作,例如:在插入时指针为空,而申请了新的节点,再将节点的地址替换原来的指针。删除了最后一个节点,将节点制空。即将节点替换为NULL。因此,使用**pphead是有必要的。


三、具体每个接口函数的实现

        1、打印

void SLTPrint(SLTNode* phead)//打印全部节点
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

        2、申请新的节点

SLTNode* BuySListNode(SLTDataType x)//申请新的节点
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

        3、尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* newnode = BuySListNode(x);
	//pphead空指针,对地址进行操作
	if(!*pphead)
	*pphead = newnode;
	else//不为空,以下为对结构体进行操作
	{
		SLTNode* dit = *pphead;
		while (dit->next)
		{
			dit = dit->next;
		}
		dit->next = newnode;
	}
}

        4、头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
	SLTNode* newnode = BuySListNode(x);
	if (!*pphead)//加这个干啥?
	*pphead = newnode;
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

        5、尾删

void SLTPopBack(SLTNode** pphead)//尾删
{
	//判空
	assert(pphead);
	assert(*pphead);//空链表不能删
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//多个节点
	{
		SLTNode* tail = *pphead,*ftail=*pphead;
		while (tail->next != NULL)
		{
			ftail = tail;
			tail = tail->next;
		}
		free(ftail->next);
		ftail->next = NULL;
	}
}

        6、头删

void SLTPopFront(SLTNode** pphead)//头删
{
	assert(*pphead);//判空

	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}

        7、找节点(用于后续的插入以及删除操作)

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
	//判空
	assert(phead);
	//遍历找值
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

        8、基于第7小点在pos之前插入x

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)// 在pos之前插入x
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		/*SLTNode* newnode=BuySListNode(x);
		newnode->next = pos;
		*pphead=newnode;*/
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* pre = *pphead;

		/*while (pre != NULL)
		{
			if (pre->next == pos)
			{
				SLTNode* newnode = BuySListNode(x);
				newnode->next = pos;
				pre->next = newnode;
				
			}
		}*/
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		SLTNode* newnode = BuySListNode(x);
		newnode->next = pos;
		pre->next = newnode;
	}
}

        9、基于第7小点在pos以后插入x

void SLTInsertAfter(SLTNode* pos, SLTDataType x)// 在pos以后插入x
{
	assert(pos);

	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

        10、基于第7小点删除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置
{
	assert(pphead);
	assert(pos);
	
	if (*pphead == pos)//在头
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* dit = *pphead;
		while (dit->next != pos)
		{
			dit = dit->next;
		}
		dit->next = pos->next;
		free(pos);
		//pos=NULL//此为形参无用
	}

}

        11、基于第7小点删除pos的后一个位置

void SLTEraseAfter(SLTNode* pos)// 删除pos的后一个位置
{
	assert(pos);
	assert(pos->next);//检查pos是否为尾结点

	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;
}

        12、销毁链表,释放空间

void SLTDestroy(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);

		cur = next;
	}
	
	*pphead = NULL;
}

四、总体代码

1、头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS 01
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//打印
void SLTPrint(SLTNode* phead);
//生成新的节点
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
// 找节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);
// 删除pos的后一个位置
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDestroy(SLTNode** pphead);

2、主体函数文件

#include"SList.h"

SLTNode* BuySListNode(SLTDataType x)//申请新的节点
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

void SLTPrint(SLTNode* phead)//打印全部节点
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}


void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* newnode = BuySListNode(x);
	//pphead空指针,对地址进行操作
	if(!*pphead)
	*pphead = newnode;
	else//不为空,以下为对结构体进行操作
	{
		SLTNode* dit = *pphead;
		while (dit->next)
		{
			dit = dit->next;
		}
		dit->next = newnode;
	}
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
	SLTNode* newnode = BuySListNode(x);
	if (!*pphead)//加这个干啥?
	*pphead = newnode;
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

void SLTPopBack(SLTNode** pphead)//尾删
{
	//判空
	assert(pphead);
	assert(*pphead);//空链表不能删
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//多个节点
	{
		SLTNode* tail = *pphead,*ftail=*pphead;
		while (tail->next != NULL)
		{
			ftail = tail;
			tail = tail->next;
		}
		free(ftail->next);
		ftail->next = NULL;
	}
}

void SLTPopFront(SLTNode** pphead)//头删
{
	assert(*pphead);//判空

	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{
	//判空
	assert(phead);
	//遍历找值
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)// 在pos之前插入x
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		/*SLTNode* newnode=BuySListNode(x);
		newnode->next = pos;
		*pphead=newnode;*/
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* pre = *pphead;

		/*while (pre != NULL)
		{
			if (pre->next == pos)
			{
				SLTNode* newnode = BuySListNode(x);
				newnode->next = pos;
				pre->next = newnode;
				
			}
		}*/
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		SLTNode* newnode = BuySListNode(x);
		newnode->next = pos;
		pre->next = newnode;
	}
}

void SLTInsertAfter(SLTNode* pos, SLTDataType x)// 在pos以后插入x
{
	assert(pos);

	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置
{
	assert(pphead);
	assert(pos);
	
	if (*pphead == pos)//在头
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* dit = *pphead;
		while (dit->next != pos)
		{
			dit = dit->next;
		}
		dit->next = pos->next;
		free(pos);
		//pos=NULL//此为形参无用
	}

}

void SLTEraseAfter(SLTNode* pos)// 删除pos的后一个位置
{
	assert(pos);
	assert(pos->next);//检查pos是否为尾结点

	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;
}

void SLTDestroy(SLTNode** pphead)
{
	assert(pphead);

	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);

		cur = next;
	}
	
	*pphead = NULL;
}

3、测试用例

#include"SList.h"

void text()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 10);
	SLTPushFront(&plist, 20);
	SLTPushFront(&plist, 30);
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	
	SLTNode* p = SLTFind(plist, 10);//把找到的地址给p
	SLTInsert(&plist, p, 100);
	SLTPrint(plist);
	SLTInsertAfter(p, 200);
	SLTPrint(plist);
	SLTErase(&plist, p);
	SLTPrint(plist);
	SLTNode* pp = SLTFind(plist, 100);
	SLTEraseAfter(pp);
	SLTPrint(plist);
	SLTDestroy(&plist);
}

int main()
{
	
	text();
	return 0;
}

        测试结果:

【数据结构】—C语言实现单链表(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表


                感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o! 

【数据结构】—C语言实现单链表(超详细!),数据结构与算法炼体 淬体中,c语言,开发语言,数据结构,链表

                                                                  给个三连再走嘛~ 文章来源地址https://www.toymoban.com/news/detail-629497.html

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

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

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

相关文章

  • 数据结构:单链表的实现(C语言)

    个人主页 : 水月梦镜花 个人专栏 : 《C语言》 《数据结构》 本博客将要实现的无头单向不循环链表。 我们将节点定义为如下结构: 其成员变量有data,next。 将int重命名为STLDataType,方便我们以后修改数据域的内容。 动态申明一个空间,来放置数据。如下: 将data的内容置

    2024年02月14日
    浏览(59)
  • 【数据结构】C语言实现单链表(带头结点)

    Single linked list with leading nodes 关于不带头结点的单链表:不带头结点的单链表 结点定义: 接口定义: 初始化需要申请头结点,让头指针指向空的头结点。 将申请结点的代码进行封装: 需要越过头结点 找到尾结点,然后插入到尾结点的后面。 对比不带头结点的单链表的尾插

    2024年02月02日
    浏览(219)
  • 数据结构——单链表的实现(c语言版)

    前言           单链表作为顺序表的一种,了解并且熟悉它的结构对于我们学习更加复杂的数据结构是有一定意义的。虽然单链表有一定的缺陷,但是单链表也有它存在的价值, 它也是作为其他数据结构的一部分出现的,比如在图,哈希表中。 目录 1.链表节点的结构 2.头插

    2024年02月13日
    浏览(60)
  • 【数据结构】单链表的增删查改(C语言实现)

    在上一节中我们提到了顺序表有如下缺陷: 在头部/中间的插入与删除需要挪动数据,时间复杂度为O(N),效率低; 增容需要申请新空间,可能会拷贝数据,释放旧空间,会有不小的消耗; 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容

    2024年02月06日
    浏览(62)
  • 【数据结构】C语言实现单链表的基本操作

    大家好,很高兴又和大家见面啦!!! 在上一篇中,我们详细介绍了单链表的两种创建方式——头插法与尾插法,相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前,我们先通过尾插法创建一个单

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

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

    2024年04月11日
    浏览(76)
  • 【算法基础】数据结构| 单链表+双链表 代码实现+图解+原理

    博主简介: 努力学习的预备程序媛一枚~ 博主主页: @是瑶瑶子啦 所属专栏: Java岛冒险记【从小白到大佬之路】 因为瑶瑶子正在备战蓝桥杯和校内ACM选拔赛,最近在学习算法相关的知识。我是借助 AcWing网站 来学习的,这篇文章是我学习就我学习内容的一个笔记,其中的一些

    2024年02月01日
    浏览(61)
  • Leetcode刷题---C语言实现初阶数据结构---单链表

    删除链表中等于给定值 val 的所有节点 给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [ ], val = 1 输出:[ ] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:

    2024年02月15日
    浏览(56)
  • 【数据结构与算法】深入浅出:单链表的实现和应用

      🌱博客主页:青竹雾色间. 😘博客制作不易欢迎各位👍点赞+⭐收藏+➕关注  ✨ 人生如寄,多忧何为  ✨ 目录 前言 单链表的基本概念 节点 头节点 尾节点 单链表的基本操作 创建单链表 头插法: 尾插法: 插入(增)操作  删除(删)操作: 查找(查)操作: 修改(改

    2024年02月08日
    浏览(75)
  • 【一起学数据结构与算法】快速教你了解并实现单链表

    此篇是对单链表知识的学习和实现,基本上大体的方法实现和思路都已经表达,如果有不对的地方,还请各位大佬多多指教! 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素

    2024年02月19日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包