【数据结构】-- 单链表的实现

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

引入

在前面我们学习了顺序表,顺序表在数组的基础上提供了很多现成的方法,方便了我们对数据的管理,但是我们也发现顺序表有着许多不足:

在处理大型的数据时,需要频繁的增容且在中间删除或插入数据时需要遍历顺序表,这些性质导致了顺序表的效率较低。这时我们就可以使用另一种数据结构--链表。

和顺序表一样,链表也是一种线性表。和顺序表不同的是,虽然链表在逻辑上是连续的,链表在物理上并不是连续的。

【数据结构】-- 单链表的实现,数据结构

既然物理上不是连续的,那么链表是怎么把一个个数据联系到一起的呢?链表分为一个个节点,

每个节点通常由两部分组成:数据域和指针域。

  1. 数据域(Data Field):数据域存储节点所需要的数据,可以是任意类型的数据,如整数、字符串等。

  2. 指针域(Pointer Field):指针域存储指向下一个节点的指针,这个指针通常称为“后继指针”或“next 指针”。

  3. 【数据结构】-- 单链表的实现,数据结构

【数据结构】-- 单链表的实现,数据结构

链表中的节点通过指针域相互连接起来,形成一个链式结构。当我们创建一个新的节点时,我们将前一个节点的指针域指向新节点,从而将新节点连接到链表中。具体来说,当我们在链表尾部添加一个新节点时,我们将原来链表中最后一个节点的指针域指向这个新节点,从而将新节点连接到链表尾部。

链表的头节点通常用来标识整个链表的起始位置,而链表的最后一个节点的指针域通常指向一个特殊的值(如空值NULL),表示这是链表的末尾。链表中的节点通过指针域相互连接,形成一个动态的数据结构,可以方便地进行插入、删除等操作,而不需要像数组一样需要连续的内存空间。

 单链表的实现

模块划分

和实现顺序表一样,分为三个文件来实现,SList..c用来实现顺序表的各种方法,SList.h用来包含实现方法所需的头文件和所需方法的初始化。test.c用来测试写的方法是否有问题。

节点

实现链表的节点需要创建两个变量,数据域用来储存数据,指针域用来存放下一个节点的地址。我们用结构体来实现。

typedef int SLTDatatype;//方便后面调整数据类型

typedef struct SListNode
{
    SLTDatatype data;
	struct SListNode* next;
}SListNode;

方法声明

在SList.h中将需要实现的方法进行声明,同时包含需要的头文件。

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#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);



//链表的尾插
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);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead,SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

方法实现

在SList.c中对需要的方法进行实现。顺序表的实现需要初始化,开始就为顺序表申请一块内存,而链表却不需要。这是为什么呢?顺序表需要初始化的主要原因是因为它们在内存中需要一段连续的存储空间来存储数据,而链表则不需要。

  1. 顺序表

    • 顺序表通常使用数组来实现,数组需要一块连续的内存空间来存储元素。
    • 在使用顺序表之前,需要明确指定表的长度(即数组的大小),以便系统为其分配一段连续的内存空间。
    • 初始化顺序表时,需要为其分配内存空间,并且要进行一些必要的初始化操作,如将元素个数设置为0,以及初始化其他相关的变量。
    • 如果不进行初始化,顺序表中的元素将会包含一些未知的随机值,这可能导致程序出现错误或者不可预测的行为。
  2. 链表

    • 链表由节点组成,每个节点可以在内存中分散存储,它们通过指针相互连接起来。
    • 在使用链表时,不需要一开始就为整个链表分配一段连续的内存空间,节点可以动态地在内存中创建和删除。
    • 因此,链表在使用之前不需要像顺序表那样进行显式的初始化,只需要在插入第一个节点时,将链表的头指针设置为该节点即可。

链表的打印

//链表的打印
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	//创建一个新的指针来遍历,这样不会改变phead
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

链表是由一个一个节点构成的,我们可以手动地创建几个几点并把它们连接起来,


	//链表是由一个一个的节点组成
	//创建几个节点
 	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将四个节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	//打印链表
	SLTNode* plist = node1;
	SLTPrint(plist);

 我们来测试一下

【数据结构】-- 单链表的实现,数据结构

链表插入的一般步骤(删除类似)

链表插入一般需要:

  1. 首先,需要找到插入位置,即要将新节点插入到哪个节点之后或之前。
  2. 然后,创建新节点,并将其插入到链表中。
  3. 最后,调整相邻节点的指针,使得链表的结构得以维护。

在链表的插入操作中,我们需要修改的是当前节点的指针,以将其指向新节点。如果我们只传递指向当前节点的指针,那么在函数内部修改指针的值只会影响函数内部的副本(传值调用),而不会影响调用者传递给函数的原始指针。为了能够修改调用者传递的指针的值,我们需要传递指针的地址,也就是二级指针(传址调用)。这样,在函数内部就可以通过二级指针来修改调用者传递的指针的值,从而实现链表的插入操作。(传值调用和传址调用CSDNhttps://mp.csdn.net/mp_blog/creation/editor/136962591)简单的说就是,如果要对链表进行遍历来找到需要插入的位置,在插入时我们不能直接传入要改变的地址,这是一个一级指针,一级指针作为形参改变不了实参的一级指针,如果传入的是一级指针,形参就是一个新创建的临时地址,并不能通过解引用找到需要改变的位置,当然就不能对链表进行插入删除操作了。我们要使用二级指针,对它解引用一次才能得到我们传入的指针,对其进行遍历就能找到我们需要插入数据的位置。

要对链表进行遍历来找到需要插入的位置才需要传入二级指针,这是不是意味着不通过头节点来遍历链表就不需要传入二级指针了。这个猜想是正确的,不需要通过头节点来遍历,我们可以直接传入要操作的地址。所以,是否需要传入二级指针取决于你的插入操作需要定位的位置以及你如何确定这个位置。如果通过遍历链表来确定插入位置,那么可能需要传入二级指针;如果已经明确了插入位置,那么只需要传入指向该位置的指针即可。

链表的尾插

在尾插中我们需要对链表的遍历来找到要进行插入的位置,所以需要传入二级指针。

//创建一个新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

//链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//空链表和非空链表
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		//ptail指向的就尾节点
		ptail->next = newnode;
	}
}

让我们一起来测试一下吧

【数据结构】-- 单链表的实现,数据结构

头插

在头插中我们也需要遍历链表来找到要要操作的位置,故传入二级指针。

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);//申请一个新节点
	//newnode  *pphead
	newnode->next = *pphead;
	*pphead = newnode;
}

 测试

【数据结构】-- 单链表的实现,数据结构

 尾删

如果只有一个节点直接释放并置空,若有多个节点,找到尾节点之前的节点和尾节点,释放尾节点并置空,把尾节点的前一个节点的指针域指向NULL。

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	//链表也不能为空
	
	//链表只有一个节点
	if ((*pphead)->next == NULL)//->优先级高于*
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)   //要找两个节点
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//此时ptail指向尾节点
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

测试

【数据结构】-- 单链表的实现,数据结构 头删

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	//链表也不能为空
	SLTNode* next = (*pphead)->next;//->优先级高于*
	free(*pphead);
	*pphead = next;
}

测试

【数据结构】-- 单链表的实现,数据结构

查找

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	//只有一个节点时

	//有多个节点时

	SLTNode* pcur = phead;
	while (pcur)
	{
		if ((pcur)->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

创建一个find变量,用来接收SLTFind()的返回值,如果返回的不是空指针则找到了,反之则没有找到。

//测试查找
SLTNode* find = SLTFind(plist, 2);
if (find != NULL)
{
	printf("找到了\n");
}
else
{
	printf("没找到\n");
}

SLTNode* find2 = SLTFind(plist, 10);
if (find2 != NULL)
{
	printf("找到了\n");
}
else
{
	printf("没找到\n");
}

【数据结构】-- 单链表的实现,数据结构

在指定位置前插入数据

虽然我们知道了指定位置的数据,但是单链表无法通过通过一个节点访问上一个节点。所以我们仍然需要遍历链表来找到指定位置之前的节点。

//在指定位置之前插入数据

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);

	//找pos的前一个节点
	SLTNode* newnode = SLTBuyNode(x);
	//如果pos == *pphead;说明头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//此时prev已经指向pos的前一个节点
		newnode->next = pos;
		prev->next = newnode;
	}
}

测试

【数据结构】-- 单链表的实现,数据结构

在指定位置后插入数据 

单链表可以通过一个节点访问上一个节点,这时候就不用遍历链表了。

//在指定位置之后插入数据

void SLTInsertAfter(SLTNode* pos, SLTDataType x)//不需要头节点,自己就能找到下一个节点
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

测试

【数据结构】-- 单链表的实现,数据结构

删除指定节点


//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//当*pphead == pos时
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev指向pos的前一个节点
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
	
}

 不能先释放pos节点再改变prev的指向,释放后pos是一个野指针,置为空之后为空指针。不能再找到原来pos之后的位置

测试

【数据结构】-- 单链表的实现,数据结构

如果用prev->next = prev->next->next不使用pos指针的话,就可以对pos节点提前释放并置空

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	//当*pphead == pos时
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		//prev指向pos的前一个节点
		prev->next = prev->next->next;
		free(pos);
		pos = NULL;
	}

}

【数据结构】-- 单链表的实现,数据结构

删除指定节点之后的节点 

/删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

测试

【数据结构】-- 单链表的实现,数据结构

销毁链表 

如果链表创建后不进行销毁或释放,可能会导致内存泄漏和资源浪费的问题。内存泄漏是指程序分配了内存空间但未释放,导致该内存空间无法再被程序使用,最终导致系统资源耗尽或程序性能下降。

实现时需要两个指针,一个用来储存当前节点的next指针;一个用来储存当前节点的指针;释放当前节点并使当前节点指向next。

//销毁链表
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

调试 

【数据结构】-- 单链表的实现,数据结构 

总结 

仔细观察,凡是不需要遍历链表的操作,我们就不需要传二级指针做形参。例如删除指定位置之后的数据和在指定位置后插入数据就不需要传二级指针。

在对某一个节点进行操作时,要考虑两个方面,一要对指定的节点进行操作,二要调整相邻节点的指针,使得链表的结构得以维护。文章来源地址https://www.toymoban.com/news/detail-859418.html

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

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

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

相关文章

  • 【数据结构】单链表的层层实现!! !

    关注小庄 顿顿解馋(●’◡’●) 上篇回顾 我们上篇学习了本质为数组的数据结构—顺序表,顺序表支持下标随机访问而且高速缓存命中率高,然而可能造成空间的浪费,同时增加数据时多次移动会造成效率低下,那有什么解决之法呢?这就得引入我们链表这种数据结构 概念

    2024年03月12日
    浏览(131)
  • 【数据结构】实现单链表的增删查

    链表类和节点类的定义: 图解: 从中间位置插入: 图解:假定index=2 尾插: 删除当前线性表中索引为index的元素,返回删除的元素值: 图解: 删除当前线性表中第一个值为element的元素: 删除当前线性表中所有值为element的元素: 将当前线性表中index位置的元素替换为eleme

    2024年02月14日
    浏览(136)
  • 数据结构:单链表的实现(C语言)

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

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

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

    2024年02月13日
    浏览(57)
  • 初阶数据结构之单链表的实现(四)

    链表的概念 :链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 所谓的逻辑结构其实就是能让我们自己能够更好的理解这个东西是什么?那么我们就用画图来理解理解吧!!在单链表中,存放着两个量,一个

    2024年02月06日
    浏览(42)
  • 【数据结构】 链表简介与单链表的实现

    在【数据结构】 ArrayList简介与实战中我们已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素 由于其底层是一段连续空间, 当在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为

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

    优势 : 可通过 下标i (数据连续(物理空间连续)) 便捷查询查找顺序表中的信息,也会在后面的 排序算法 和 堆算法 中尽显身手 问题 : 在头部/中间的插入与删除需要 挪动数据 ,时间复杂度为O(N),效率低; 增容需要申请新空间, 可能会拷贝数据 ,释放旧空间,会有

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

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

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

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

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

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

    2024年02月06日
    浏览(55)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包