首页 > 其他分享 >数据结构(单链表(1))

数据结构(单链表(1))

时间:2024-07-14 18:30:24浏览次数:21  
标签:pphead 结点 单链 SLTNode void 链表 SLTDataType 数据结构

前言

线性表中有着许多的结构,如顺序表链表。而单链表则是链表的最基础的一种形式,下面就让我们对其做一个了解。

概念

概念:链表是⼀种物理存储结构上⾮连续、⾮顺序存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

结构

我们可以将单链表的结构想象成火车的车厢:

淡季时⻋次的⻋厢会相应减少,旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/ 加上,不会影响其他⻋厢,每节⻋厢都是独⽴存在的。 在链表⾥,每节“⻋厢”是什么样的呢?

如图:

结点

与顺序表不同的是,链表⾥的每节"⻋厢"都是独⽴申请下来的空间,我们称之为“结点”。

结点的组成主要有两个部分:当前结点要保存的数据和保存下⼀个结点的地址(指针变量)。

中指针变量plist保存的是第⼀个结点的地址,我们称plist此时“指向”第⼀个结点,如果我们希望 plist“指向”第⼆个结点时,只需要修改plist保存的内容为0x0012FFA0

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

性质

1、链式结构在逻辑上是连续的,在物理结构上不⼀定连续

2、结点⼀般是从上申请的

3、从堆上申请来的空间,是按照⼀定策略分配出来的,每次申请的空间可能连续,可能不连续

结合C语言中结构体的相关知识,我们能得到链表的每个结点对应的结构体代码: 假设当前保存的结点为整型:

struct SListNode
{
 int data; //结点数据
 struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};

当我们想要保存⼀个整型数据时,实际是向操作系统申请了⼀块内存,这个内存不仅要保存整型数 据,也需要保存下⼀个结点的地址(当下⼀个结点为空时保存的地址为空)。

当我们想要从第⼀个结点⾛到最后⼀个结点时,只需要在当前结点拿上下⼀个结点的地址就可以了。

链表的打印

给定的链表结构中,我们该如何实现结点从头到尾的打印呢?

我们用一张图来解释:

实现单链表

下面我先给出实现单链表所必须的头文件,(SList.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 x);
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** pphead);

具体的实现我将在下一期进行详细说明,敬请期待!

标签:pphead,结点,单链,SLTNode,void,链表,SLTDataType,数据结构
From: https://blog.csdn.net/2406_83947720/article/details/140420041

相关文章

  • 高级数据结构-可并堆
    可并堆,就是可以合并的堆。堆满足一个性质,就是当前节点,都大于或者等于他的所有子树上的节点,自然在这里我所讲的是结点的权值。显而易见,既然可并堆是堆的一种,容易推出,可并堆也满足这个性质。现在思考一个问题,当题目里需要合并两个堆的时候,该如何合并呢?如果只是普通的堆的话,我们可以......
  • 数据结构与算法分析实验7 构造哈夫曼树和生成哈夫曼编码
    文章目录1.上机名称2.上机要求3.上机环境4.程序清单(写明运行结果及结果分析)4.1程序清单4.1.1head.h头文件内容如下:4.1.2head.cpp实现文件内容如下:4.1.3源文件main.cpp内容如下:4.2程序运行结果5.上机体会1.上机名称构造哈夫曼树和生成哈夫曼编码2.上机......
  • 可持久化数据结构
    P4735转化到区间求\(\text{xor}\x\)后的最大值,用Trie。那么需要知道区间是否有在Trie树某个子树内的节点,用可持久Trie,或者离线扫右端点并记录左端点时间戳即可。第二个做法可以不离线,同样使用可持久Trie,但是求区间时不使用减法,而是只使用插入前\(r\)个数的Trie,通过......
  • 数据结构第25节 深度优先搜索
    深度优先搜索(Depth-FirstSearch,简称DFS)是一种用于遍历或搜索树或图的算法。DFS从根节点开始,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到上一个节点w,然后探索w的其他未搜索过的子节点。DFS有两种常用的方式:递归方式和非递归方式(通常使用栈来实......
  • 【数据结构与算法】详解二叉树下:实践篇————通过链式结构深入理解并实现二叉树
          ......
  • 数据结构题目:几种典型排序算法的实现
    1、实验目的实现几种典型的排序算法2、实验具体要求分别利用直接插入/折半插入/希尔/冒泡/快速/简单选择排序算法实现将待排序序列{26,6,18,8,36,66,56,76,99}由小到大排序,并输出结果。3、实验设计思路(编程语言、模块划分及函数功能描述等)模块划分及函数功能描述:主函数模......
  • 数据结构,(动态)顺序表,C语言实现
    ——如果代码存在问题,请务必评论告诉我,感激不尽(#^.^#)——动态和静态的顺序表差别主要在于开辟内存的方式,动态顺序表中的数据所在内存是通过malloc函数实现的,这也意味着,动态顺序表可以更改存储数据的内存大小,其他的话基本没什么差别1.数据类型定义 structElemType想要建......
  • 数据结构与算法学习day4之单向链表
    1.单向链表的的定义链表是有序的列表,这是它在内存中的存储,如下图所示:链表是以节点的形式存储的,是链式存储每个节点都包含两个部分,一个是data域,一个是next域指向下一个节点每个节点不一定是连续存储链表分为带头节点和不带头节点2.单向链表的实现思路(1)添加添加节点的......
  • 数据结构(队列的实现)
    目录队列队列的定义队列的实现创建队列的结构队列的初始化进行插入数据删除数据计算个数 判断是否为空返回队列头部数据返回队列尾部数据队列队列的定义队列是:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First......
  • 第八篇:Python集合:高效的无序集数据结构
    1.集合的定义Python中的集合(set)是一种高度优化的无序且不重复的数据结构。它在概念上类似于数学中的集合,能够存储多个不同的元素。集合的这种特性使其成为处理唯一性和成员资格检查的理想选择。在Python中,我们可以通过两种主要方式定义集合:a)使用花括号{}:set1={1,......