西安网站建设聂卫,代理网页网游,哈尔滨网站制作多少钱,网络服务合同要交印花税吗君兮_的个人主页 勤时当勉励 岁月不待人 C/C 游戏开发 Hello,米娜桑们#xff0c;这里是君兮_#xff0c;我们接着之前讲过的顺序表来继续介绍初阶数据结构的内容#xff0c;今天给大家带来的是有关链表的基本知识和各种接口功能的实现 好了#xff0c;废话不多说#x… 君兮_的个人主页 勤时当勉励 岁月不待人 C/C 游戏开发 Hello,米娜桑们这里是君兮_我们接着之前讲过的顺序表来继续介绍初阶数据结构的内容今天给大家带来的是有关链表的基本知识和各种接口功能的实现 好了废话不多说开始今天的学习吧— 链表 一.链表的基础知识1.链表的概念与基本结构2.链表的分类 二.无头单链表的实现1.初始化链表 BuySListNode2.打印链表 SLTPrint3.头插 SLTPushFront与头删 SLTPopFront头插头删 4.尾插SLTPushBack和尾删 SLTPopBack尾插尾删 总结 一.链表的基础知识
1.链表的概念与基本结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。链表链表表如其名链表的结构就如同被连接起来了只不过在中间连接链表的“绳索”是指针。 从基本结构图中我们可以看出 1.链式结构在逻辑上是连续的但与顺序表不同在物理上链表是不一定连续的 2.现实中链表的节点一般都是从堆上申请出来的。 3.从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续。
2.链表的分类
在实际中链表的结构非常多样下面就简单的介绍几种 虽然链表有多种结构但是最常用的还是这两种 1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我也会带大家逐一实现代码。
二.无头单链表的实现
由于我们是初阶数据结构且这是有关链表的第一篇博客我们就先从最简单的无头单链表开始实现。首先我们先把需要的几个功能的接口列出来然后咱们来一个一个介绍。 说明以下包括后面的所有代码的函数名称等都是我根据该函数的功能编的也就是说这些函数名等不唯一你也可以起别的名字不影响链表的使用但就像给孩子取名一样我们都不希望我们的孩子的名字叫狗蛋二狗子什么的实际上在函数的命名中你瞎起名字就和这些差不多因此我建议无论是现在还是以后的函数的命名最好都按照功能来命名这样既增加了代码的可读性也让人一看便知各个函数的功能。 #pragma once
#includestdio.h
#includestdlib.h
#includeassert.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);
//修改pos位置的值
void SLTModify(SLTNode**pphead, SLTNode* pos, SLTDataType x);
// 单链表的销毁
void SListDestroy(SLTNode** pphead);注意对接口的声明都包含在头文件中先讲一下这里面需要注意的几个地方 1.第一处的 typedef 实际是为了方便我们的使用因为我们也不知道我们的链表是用来存储什么类型的数据的因此我们这里就定义一个SLDataType下面的代码中统一把数据类型用它来代替这样一来我们以后想要改变存储的数据类型只需要改动这里即可比如我们现在想要存储double类型的数据
typedef double SLDataType;2.关于我们的链表的结构体
typedef struct SListNode
{SLTDataType Data;struct SListNode * next;}SLTNode;我们说了我们的链表的连接是通过指针来实现的因此我们的结构体中第一个成员是该节点存储的值第二个成员则是一个该结构体的指针指向的是下一个节点的地址。
1.初始化链表 BuySListNode
当我们想使用我们的链表时首先就像变量一样需要先把它初始化一下
//初始化链表
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc failed:);exit(-1);}newnode-Data x;newnode-next NULL;return newnode;}我们首先通过malloc为我们链表的一个节点开辟了空间然后通过perror判断了我们的malloc是否成功如果成功我们就把该链表的值置为我们输入的x由于此时只有它一个节点因此next置空这样我们的一个节点就初始化好了。
2.打印链表 SLTPrint
当我们初始化成功后我们就想把我们的链表打印一下看看我们的链表是否成功初始化了因此我们继续来写打印链表的函数
//打印链表
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-Data);cur cur-next;}printf(NULL\n);
}我们定义了一个结构体指针cur指向传入的链表的表头当cur不为空时我们就打印一下此时该节点中的Data并通过next找到下一个节点由于我们链表的最后一个元素是NULL因此我们最后把链表中所有节点都打印完后在最后再补上一个NULL。 效果如上图 3.头插 SLTPushFront与头删 SLTPopFront
头插与头删顾名思义就是在链表表头插入节点或者删除链表表头的节点
头插
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}头插的逻辑图是这样的
头删
//头删
void SLTPopFront(SLTNode** pphead)
{//空assert(*pphead);//非空SLTNode* newhead (*pphead)-next;//保存一下下一个节点的地址free(*pphead);*pphead newhead;
}头删的逻辑图首先先判断*pphead是否为空如果为空说明这个链表压根不存在 4.尾插SLTPushBack和尾删 SLTPopBack
与前面同理尾插和尾删是作用于链表的最后的
尾插
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);SLTNode* tail *pphead;//链表中没有节点时if (*pphead NULL){*pphead newnode;}else{//不为空时while (tail-next){tail tail-next;}tail-next newnode;}
}我们知道链表的最后一个节点的next存放的地址为空我们来通过逻辑图分析一下首先还是特殊情况当我们的链表中没有节点时那我们就把头指针直接指向需要插入的节点就行。
尾删
//尾删
void SLTPopBack(SLTNode** pphead)
{//为空assert(*pphead);//只有一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//不为空且有多个节点else{SLTNode* tail *pphead;while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;}
}还是先来分析特殊情况先通过assert断言来判断一下该链表是否为空其次如果这个链表只有一个节点时我们指向把该节点free释放掉再置空即可不需要其他操作。一般情况的逻辑图 总结 由于篇幅有限今天的内容到这里就结束了之后我们会把剩下没讲的接口讲完然后再带大家做几道oj题让大家更加熟悉链表的使用。相信如果你能一直跟着坚持下去那么你链表这一块的初阶知识就一定没什么问题啦切记要自己上手敲敲代码哦 好了如果你有任何疑问欢迎在评论区或者私信我提出大家下次再见啦 新人博主创作不易如果感觉文章内容对你有所帮助的话不妨三连一下这个新人博主再走呗。你们的支持就是我更新的动力 **可莉请求你们三连支持一下博主点击下方评论点赞收藏帮帮可莉吧**
