数据结构·单链表

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

        不可否认的是,前几节我们讲解的顺序表存在一下几点问题:

        1. 中间、头部的插入和删除,需要移动一整串数据,时间复杂度O(N)

        2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗

        3. 增容一般是2倍的增长,这势必会造成空间的浪费

        那如何解决这些问题呢,此时,链表出现了

1. 链表的概念和结构

        我们之前说过,线性表的特点就是逻辑上是连续的,物理上不一定连续。顺序表是逻辑上是连续的,物理上也是连续的。而今天的链表就是逻辑上是连续的,但是物理上是不连续的

        最简单的链表是由节点们串在一起组成的,每个节点包含了两个内容:

                1. 要存入的有效数据

                2. 下一个节点的地址

数据结构·单链表,数据结构之谜,数据结构

        可以看出,每个节点在物理上都是独立的,不连续的。但是每个节点在逻辑上又有关联,每个节点都知道下一个节点的指针,要找到下一个节点就访问那个指针就好了

        具体来讲就是把 plist 当成一个钥匙,最开始保存的是第一个节点的地址,用完第一个节点的数据之后,把第一个节点中存储的地址再给到plist,这样plist就可以开第二个节点了,以此类推···

        下面我们依照上面的图片做一个简单的节点结构

                                数据结构·单链表,数据结构之谜,数据结构

        到这里,链表的地基就学会了,下面我们尝试实现一下

2. 单链表(Single linked list)的实现

        跟顺序表一样,先是把准备工作,三个文件准备好

                                数据结构·单链表,数据结构之谜,数据结构

        再把链表节点写出来

                                 ​​​​​​数据结构·单链表,数据结构之谜,数据结构

        在这里我要重点声明一下,接下来如果从主函数前去访问链表时用的都是plist参数,从主函数中给子函数传参也是plist,就像这样

        ​​​​​​​        ​​​​​​​                数据结构·单链表,数据结构之谜,数据结构

        然后就正式进入链表实现啦,大家伙坐稳喽

2.1 链表的打印

        打印的逻辑就是先拿到第一个节点的地址 pcur,把这个地址访问到 data 打印出来,然后将pcur的内容变成下一个要打印的节点的地址,直到pcur的内容是NULL为止

        ​​​​​​​        ​​​​​​​        数据结构·单链表,数据结构之谜,数据结构

2.2 链表的插入

        因为插入就一定需要申请一个新的节点,所以我们先把这个功能封装好

        向堆区申请一块空间用来存放节点,记录这个节点的地址

数据结构·单链表,数据结构之谜,数据结构

        当然,如果你想把newnode的类型改成 SLTNode 也可以,不过后面要用到节点地址的时候就要取地址一下,很麻烦,所以我们干脆直接返回节点的地址

2.2.1 尾插

        在链表的尾端插入一个数据。

        因为如果链表为空(没有节点)的时候要修改 plist 的内容,让它指向我们新添加的第一个节点,所以我们传参的时候要传 &plist ,因此函数参数要用二级指针来接收这个可能会被修改的plist

        如果链表不为空,就去找尾节点,把为节点的next成员内容从NULL变成我们新添加的节点地址,可以这么理解:

数据结构·单链表,数据结构之谜,数据结构

        这个图里有一点不恰当,就是这个 pphead 要解引用一次 (*pphead) 才能找到第一个节点的地址

        ​​​​​​​数据结构·单链表,数据结构之谜,数据结构

        接下来我们运行一下看看效果

数据结构·单链表,数据结构之谜,数据结构

2.2.2 头插

        头插比尾插好理解一点,直接上思路图(画的太丑了QAQ)

        数据结构·单链表,数据结构之谜,数据结构

        很明显,链表是否为空对于需要的操作是没有影响的,上代码:

        数据结构·单链表,数据结构之谜,数据结构

        最后运行一下看结果:

        数据结构·单链表,数据结构之谜,数据结构

        因为每次都是把节点插到最前面,所以反着打出来是对的

2.3 链表的删除

2.3.1 尾删

        尾删的逻辑就是找到最后一个节点 ptail 和倒数第二个节点 prev ,把倒数第二个节点的next成员置为空指针,释放掉最后一个节点。当然,如果链表为空,也就是说没有节点的话就不能执行删除操作,用assert断言报错

        ​​​​​​​        ​​​​​​​        数据结构·单链表,数据结构之谜,数据结构

        上代码:

        数据结构·单链表,数据结构之谜,数据结构

2.3.2 头删

        头删也是需要两个指针控制,要注意的就是要先释放掉*pphead也就是第一个节点,然后再把*pphead的内容改成第二个节点的地址,接上第二个节点

        ​​​​​​​              ​​​​​​​数据结构·单链表,数据结构之谜,数据结构

        代码如下:

        ​​​​​​​        数据结构·单链表,数据结构之谜,数据结构

2.4 查找

        链表的查找很简单,就是遍历链表,找到了就返回节点地址,没找到就返回空指针

        数据结构·单链表,数据结构之谜,数据结构

2.5 在任意位置插入数据

2.5.1 在指定位置前插入数据

        可以用SLTFind找到要被前插的节点的地址pos,在这个节点前面插入节点,还需要直到它前面那个节点的地址prev

        ​​​​​​​        ​​​​​​​        数据结构·单链表,数据结构之谜,数据结构

        在实现这个功能的时候我们要注意,当pos是头节点的情况:

        数据结构·单链表,数据结构之谜,数据结构

        下面使用一下

        数据结构·单链表,数据结构之谜,数据结构

2.5.2 在指定位置后插入数据

        这个比较简单,但是要注意给地址的顺序,要先把后面那个节点的地址给到新节点,再把指定位置pos节点的地址成员改成新节点的地址,否则就会导致后面那个节点地址的丢失,没办法接到新节点后面了

        还有就是我们不需要知道链表的头节点是什么了,只需要关注pos就行了

        ​​​​​​​                ​​​​​​​数据结构·单链表,数据结构之谜,数据结构

        数据结构·单链表,数据结构之谜,数据结构

2.6 在任意位置删除节点

2.6.1 删除pos节点

        删除pos节点要先知道它前面的那个节点prev,然后把prev跟pos后面那个节点先连起来,最后再把pos释放掉。还有要注意的一点就是当pos就是链表头节点的时候要特殊处理一下

        ​​​​​​​        ​​​​​​​          数据结构·单链表,数据结构之谜,数据结构

        数据结构·单链表,数据结构之谜,数据结构

2.6.2 删除pos后面的一个节点

        这个功能也是只需要关注pos后面的内容就行,所以只需要传pos一个参数。还要注意一点就是pos不能是链表中的最后一个节点,否则它后面没有节点了还删什么

        ​​​​​​​        数据结构·单链表,数据结构之谜,数据结构

        ​​​​​​​        数据结构·单链表,数据结构之谜,数据结构

2.7 链表的销毁

        两个变量,pcur记录当前要准备销毁的节点地址,next记录下一个节点地址,防止销毁上一个节点之后找不到下一个节点了。然后两个变量一直循环向后扫描销毁,直到pcur指向NULL

        ​​​​​​​                ​​​​​​​数据结构·单链表,数据结构之谜,数据结构

                        数据结构·单链表,数据结构之谜,数据结构

3. 链表的分类

        链表按带头或不带头,单向或双向,循环或不循环,排列组合有8种

        我们刚刚学的单链表全称就是:不带头单向不循环链表

        带头不带头是说链表有没有一个不存储有效数据的节点,放在第一个存放有效数据节点之前

        ​​​​​​​        ​​​​​​​        数据结构·单链表,数据结构之谜,数据结构

        单向双向是说链表能通过后一项找到前一项就是双向的,如果只能根据前一项找到后一项链表就是单项的。或者说双向链表的节点中的两个存放地址的成员中,一个存下一个节点的地址,一个存上一个节点的地址。

        ​​​​​​​        ​​​​​​​        数据结构·单链表,数据结构之谜,数据结构

        循环不循环是说最后一个节点指向第一个节点就是循环链表,要是最后一个节点指向NULL就是不循环链表

                        数据结构·单链表,数据结构之谜,数据结构

        虽然链表的种类很多,但是常用的只有两种:

                1.单链表(不带头单向不循环链表)

        单链表结构简单,一般不会单独用来存贮数据,它一般作为其他数据结构的子结构出现

                2.双向链表(带头双向循环链表)

        双向链表结构最复杂,一般用来单独存储数据。它虽然复杂,但是之后实现它的实际就会发现它有很多优势,致使实现它反而变得简单了,后面会有实现它的章节的。

4. 本节代码

        SList.h

#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** pphead, SLTDataType x);


//在任意位置插入数据
//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//在任意位置删除节点
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos后面的一个节点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SLTDestory(SLTNode** pphead);

        SList.c文章来源地址https://www.toymoban.com/news/detail-824254.html

#include"SList.h"

//链表的打印	
void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}


//申请一个新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	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;
		return;
	}

	//链表不为空,找尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//找到尾节点了
	ptail->next = newnode;
}

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

	//链表为不为空,操作都一样
	//斩断第一个连接,再把新节点接进去
	newnode->next = *pphead;
	*pphead = newnode;
}




//链表的头删和尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//链表不为空
	//链表只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		return;
	}
	//链表有多个节点
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	//找到尾节点
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}
	prev->next = NULL;
	free(ptail);
	ptail = NULL;
	
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//让第二个节点变成新的头节点
	//释放旧的头节点
	SLTNode* sec = (*pphead)->next;
	free(*pphead);
	*pphead = sec;
}



//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	//遍历链表
	SLTNode* pcur = *pphead;

	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}

	return NULL;
}




//在任意位置插入数据
//在指定位置前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);
	//这里断言*pphead不能为空
	//因为指定节点的地址pos不能为空,所以这个链表也不能为空
	assert(*pphead);

	//当pos是头节点,执行头插
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
		return;
	}

	//当pos不是头节点
	//申请一个新节点
	SLTNode* newnode = SLTBuyNode(x);

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = newnode;
	newnode->next = pos;
}

//在指定位置后插入数据
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);
	assert(pos);
	assert(*pphead);

	//如果pos指向头节点,执行头删
	if (*pphead == pos)
	{
		SLTPopFront(pphead);
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

//删除pos后面的一个节点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//pos->next不能为空
	//就是说pos不能是最后一个节点
	assert(pos->next);

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



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

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

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

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

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

相关文章

  • 数据结构·单链表

            不可否认的是,前几节我们讲解的顺序表存在一下几点问题:         1. 中间、头部的插入和删除,需要移动一整串数据,时间复杂度O(N)         2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗         3. 增容一般是2倍的增长,这势

    2024年01月25日
    浏览(75)
  • 【数据结构】单链表详解

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

    2024年02月09日
    浏览(35)
  • 数据结构——单链表(上)

    🌇个人主页:_麦麦_ 📚今日名言:“生活总是让我们遍体鳞伤,但到后来,那些受伤的地方一定会变成我们最强壮的地方。”        ——海明威《永别了武器》 目录 ​编辑 一、前言 二、正言  3.1链表的概念及结构 3.2链表的分类 3.3链表的实现【无头单向非循环】 3.

    2024年02月02日
    浏览(41)
  • 数据结构入门——单链表

    目录 前言 链表的定义 链表的创建 头插法创建链表 尾插法创建链表 链表的删除 在头部删除元素 在尾部删除元素 查找固定元素 在链表中插入元素 在pos位置前插入 在pos位置后插入 删除链表结点 删除pos位置的结点 删除pos后的结点 链表的销毁 写在最后 前面我们学习了顺序表

    2024年02月20日
    浏览(40)
  • 【数据结构】单链表(详解)

    所属专栏:初始数据结构 博主首页:初阳785 代码托管:chuyang785 感谢大家的支持,您的点赞和关注是对我最大的支持!!! 博主也会更加的努力,创作出更优质的博文!! 关注我,关注我,关注我,重要的事情说三遍!!!!!!!! 前面我们已经用顺序表方式来实现接口

    2023年04月24日
    浏览(53)
  • 【数据结构】单链表(超全)

    前言:  上一次我们分享了线性表中的一种结构顺序表,它存在着一些其缺点,比如:在中间位置或者头部进行元素插入或者删除的时候时间复杂度是 O ( N ) O(N) O ( N ) 效率比较低,并且顺序表在扩容的时候也存在时间和空间上的消耗,由于我们每次都是按照二倍来扩的,那

    2024年02月11日
    浏览(41)
  • 数据结构--单链表

    目录 1.单链表的定义: 单链表基本操作的实现: 2.单链表的初始化(构造带头结点的空表) 2.将头结点的指针域置空 3.链表是否为空: 4.单链表的销毁: 5.单链表的清空: 6.求单链表的表长: 7.   取值  取单链表第i个元素: 8按值查找 根据指定数据查找指定数据所在位置序

    2024年02月15日
    浏览(42)
  • 数据结构单链表

    单链表 1 链表的概念及结构 概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。 在我们开始讲链表之前,我们是写了顺序表,顺序表就是类似一个数组的东西,它的存放是连续的,优点有很多,比如支持

    2024年02月12日
    浏览(45)
  • 数据结构:单链表

    单链表的全称为\\\"不带头单向不循环链表\\\" 注意:         下文提到的头节点与带头链表时两个概念,文中的头节点指的是第一个有效节点,二带头节点中的头指的是第一个无效节点 链表和顺序表一样,都是线性表,逻辑结构上是线性的,但不同的是,链表在物理结构上不是线性的

    2024年01月21日
    浏览(41)
  • 数据结构—单链表

    目录 1.前言 2.了解单链表 3.单链表代码实现       3.1 单链表结构体实现       3.2 创建节点       3.3  打印单链表       3.4 尾插        3.5  头插        3. 6 头删       3.7  尾删       3.8  查找       3.9  插入            3.9.1 在pos位置之前插入             3.9.

    2023年04月20日
    浏览(105)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包