数据结构——lesson3单链表介绍及实现

2024-02-18 22:04
文章标签 实现 介绍 数据结构 单链 lesson3

本文主要是介绍数据结构——lesson3单链表介绍及实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

 

1.什么是链表？

2.链表的分类

（1）无头单向非循环链表：

（2）带头双向循环链表：

3.单链表的实现

 （1）单链表的定义

（2）动态创建节点

（3）单链表打印

（4）单链表尾插

（5）单链表头插

（6）单链表尾删

（7）单链表头删

（8）单链表查找

（9）单链表在pos位置之后插入

(10)单链表在pos位置之前插入

（11）单链表删除pos位置的节点

（12）单链表销毁

 4.运行结果

5.结语 


4da1dfe51db24bf1b72fbdc29e0e7e93.jpeg

1.什么是链表？

链表是一种 物理存储结构上非连续、非顺序的存储结构，数据元素的 逻辑顺序是通过链表中的 指针链 接次序实现的 。
逻辑图如下：
a83f5df4179a4feca08f0f62d06a39f7.png

可以看出链表有两个变量，一个存放数据，另一个存放指向下一节点的指针；

此外链表还具有以下特征：

（1）链表在逻辑上连续，但在物理上不一定连续；

（2）链表的节点在现实中一般都是在堆上开辟出来的，所以使用结束后需要释放空间；

（3）从堆上申请的空间是按照一定策略分配的，所以物理空间可能连续也可能不连续。

 

2.链表的分类

链表按单向双向、无头带头、循环非循环可分为多种，这里我们介绍最常用的两种——无头单向非循环链表、带头双向循环链表。本篇文章将详细介绍无头单向非循环链表（简称单链表）的增删查改等的实现。

（1）无头单向非循环链表：

fafc7d2473954f09b3d06e85bfe83539.jpeg

 

结构简单，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试中出现很多。

（2）带头双向循环链表：

3a1b4f8edc084008881c1a27a3973991.jpeg 
结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

3.单链表的实现

 （1）单链表的定义

typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;//存放数据struct SListNode* next;//存放下一个节点的指针
}SListNode;

结构体定义两个变量，一个是SLDataType类型的数据，另一个时结构体的指针用来存放下一节点指针；

（2）动态创建节点


//申请新的节点，返回指向节点的指针
SListNode* BuySListNode(SLTDateType x)
{SListNode* buynode = (SListNode*)malloc(sizeof(SListNode));buynode->data = x;buynode->next = NULL;return buynode;
}

（3）单链表打印


// 单链表打印
void SListPrint(SListNode* plist)
{//assert(plist);//没有节点，指针为空，断言，为空也可打印空指针所以不需要断言SListNode* psl = plist;//用一个临时变量接收，如果不喜欢也可以不用while (psl)//利用while循环遍历单链表{printf("%d->", psl->data);//打印单链表指向的数据psl = psl->next;//继续循环}printf("%d->NULL\n");//最后一个不要漏了
}

（4）单链表尾插

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);//断言二级指针SListNode* buy = BuySListNode(x);assert(buy);//判断节点是否开辟成功SListNode* psl= *pplist;//创建一个新的变量if (psl == NULL)//如果是一个节点都没有的情况{*pplist = buy;//需要将头指针改变（原本头指针是NULL）所以需要节点指针的指针return;}while (psl->next)//如果已经有节点的情况{psl = psl->next;//通过next遍历链表找到最后的节点}psl->next = buy;//将最后节点的next改成buy节点的指针，所以需要节点的指针即可，不需要二级指针}

pplist是指向链表第一个节点指针的指针，是二级指针，所以一定不为空，要用assert断言；

（5）单链表头插

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* buy = BuySListNode(x);assert(buy);//判断节点是否开辟成功SListNode* psl = *pplist;if (*pplist == NULL)//如果一个节点都没有的情况{*pplist = buy;//需要将头指针改变（原本头指针是NULL）所以需要节点指针的指针return;}//有节点的情况buy->next = psl;//需要通过next连接新节点*pplist = buy;//通过节点的指针的指针改变节点的指针
}

 要注意有两种情况一直是没有一个节点的情况即*pplist = NULL，另一种是有节点的情况；

传二级指针的作用就是为了改变指针plist，所以需要指针的指针pplist；

（6）单链表尾删

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);//删除节点要判断有没有节点SListNode* psl = *pplist;if (psl->next == NULL)//只有一个节点时{free(psl);//释放最后一个节点的空间*pplist = NULL;//尾指针置空return;}while (psl->next->next)//多个节点时找到倒数第二个节点{psl = psl->next;}free(psl->next);psl->next = NULL;//尾指针置空
}

单链表尾删同样要注意两种情况；使用free释放指针指向的空间；

（7）单链表头删

// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);//删除节点要判断有没有节点SListNode* psl = *pplist;if (psl->next == NULL)//只有一个节点时{free(psl);*pplist = NULL;return;}//多个节点时*pplist = psl->next;//将第二个节点的指针给头指针free(psl);//释放第一个节点的空间
}

（8）单链表查找

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);//查找节点要判断有没有节点SListNode* psl = plist;while (psl){if (psl->data == x){return psl;//找到了返回psl}psl = psl->next;}return NULL;//没找到返回空指针
}

（9）单链表在pos位置之后插入

// 单链表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* buy = BuySListNode(x);assert(buy);//判断节点是否开辟成功//if (pos->next == NULL)//{//	pos->next = buy;//将最后节点的next改成buy节点的指针	//	return;//}buy->next = pos->next;//只有一个节点和多个节点一样pos->next = buy;
}

思考分析这两行代码可不可以调换一下顺序呢？

buy->next = pos->next;//只有一个节点和多个节点一样
pos->next = buy;

答案是不能，我们看到如果交换顺序，先将buy赋值给pos->next，那么pos->next的值将会被改变，而我们需要在buy->next中保存原来的pos->next，所以不能调换顺序；

如果你想要换也可以通过创建一个临时变量来存储pos->next的方式实现.例如：


SListNode* cur = pos->next;
pos->next = buy;
buy->next = cur;

(10)单链表在pos位置之前插入

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x)
{//assert(pphead);assert(pos);SListNode* buy = BuySListNode(x);assert(buy);//判断节点是否开辟成功SListNode* psl = *pphead;if (psl->next == NULL)//只有一个节点{buy->next = pos;*pphead = buy;return;}while (psl->next != pos)//多个节点{psl = psl->next;}buy->next = pos;psl->next = buy;
}

（11）单链表删除pos位置的节点

// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos)
{assert(pos);SListNode* psl = *pphead;if (psl->next == NULL)//只有一个节点，类似于头删{free(pos);pos = NULL;*pphead = NULL;return;}while (psl->next != pos)//多个节点{psl = psl->next;}//此时psl->next = pos;psl->next = pos->next;将pos位置指向的下一个节点指针赋给psl->nextfree(pos);pos = NULL;}

删除pos位置也要注意有两种情况；

（12）单链表销毁

void SLTDestroy(SListNode** pphead)
{assert(pphead);SListNode* psl = *pphead;SListNode* psll = *pphead;while (psl != NULL){free(psll);psl = psl->next;psll = psl;}*pphead = NULL;
}

 4.运行结果

ee434ab5c2f04694b1021b41252e8c93.png

5.结语 

        以上就是今天学习的内容了，单链表的实现关键在于理解它的逻辑结构，包括两个变量，一个是指向数据，另一个则指向下一节点的指针，此外，单链表实现还涉及了二级指针的内容以及动态内存函数的内容，涉及的代码知识更为广泛，但是只要抓住了关键点就会发现每个函数的中心思想都是不变的，好了以上就是今天学习的内容啦，有什么问题欢迎大家在评论区指出或者私信我哦~

 

这篇关于数据结构——lesson3单链表介绍及实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/722599。

相关文章

Nginx 配置跨域的实现及常见问题解决

Nginx 配置跨域的实现及常见问题解决

《Nginx配置跨域的实现及常见问题解决》本文主要介绍了Nginx配置跨域的实现及常见问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来... 目录1. 跨域1.1 同源策略1.2 跨域资源共享（CORS）2. Nginx 配置跨域的场景2.1
阅读更多...
Python中提取文件名扩展名的多种方法实现

Python中提取文件名扩展名的多种方法实现

《Python中提取文件名扩展名的多种方法实现》在Python编程中,经常会遇到需要从文件名中提取扩展名的场景,Python提供了多种方法来实现这一功能,不同方法适用于不同的场景和需求,包括os.pa... 目录技术背景实现步骤方法一：使用os.path.splitext方法二：使用pathlib模块方法三
阅读更多...
CSS实现元素撑满剩余空间的五种方法

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中，我们经常需要让某个元素占据容器的剩余空间，本文将介绍5种不同的方法来实现这个需求，并分析各种方法的优缺点，感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中，我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求
阅读更多...
HTML5 getUserMedia API网页录音实现指南示例小结

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API，结合WebAudioAPI，实现网页录音功能,从获取音频流到处理和保存录音，整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3
阅读更多...
Java实现删除文件中的指定内容

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja
阅读更多...
使用Python和OpenCV库实现实时颜色识别系统

使用Python和OpenCV库实现实时颜色识别系统

《使用Python和OpenCV库实现实时颜色识别系统》：本文主要介绍使用Python和OpenCV库实现的实时颜色识别系统,这个系统能够通过摄像头捕捉视频流,并在视频中指定区域内识别主要颜色（红... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间详解
阅读更多...
PostgreSQL中MVCC 机制的实现

PostgreSQL中MVCC 机制的实现

《PostgreSQL中MVCC机制的实现》本文主要介绍了PostgreSQL中MVCC机制的实现,通过多版本数据存储、快照隔离和事务ID管理实现高并发读写,具有一定的参考价值,感兴趣的可以了解一下... 目录一 MVCC 基本原理python1.1 MVCC 核心概念1.2 与传统锁机制对比二 Postg
阅读更多...
SpringBoot整合Flowable实现工作流的详细流程

SpringBoot整合Flowable实现工作流的详细流程

《SpringBoot整合Flowable实现工作流的详细流程》Flowable是一个使用Java编写的轻量级业务流程引擎,Flowable流程引擎可用于部署BPMN2.0流程定义,创建这些流程定义的... 目录1、流程引擎介绍2、创建项目3、画流程图4、开发接口4.1 Java 类梳理4.2 查看流程图4
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2