当前位置: 首页 > news >正文

数据结构与算法基础-学习-11-线性表之链栈的初始化、判断非空、压栈、获取栈长度、弹栈、获取栈顶元素

一、个人理解

链栈相较于顺序栈不存在上溢(数据满)的情况,除非内存不足,但存储密度会低于顺序栈,因为会多存一个指针域,其他逻辑和顺序表一致。总结如下:

  1. 头指针指向栈顶。

  1. 链栈没有头节点直接就是首元节点。

  1. 基本不会出现上溢的情况。

  1. 头指针为空,表示链栈为空,没有元素。

  1. 插入删除操作都是在栈顶(首元节点)操作。

二、链栈图解

三、结构体定义

1、ElemType

(1)说明

数据域,存放自定义数据。

(2)源码

typedef struct ElemType
{char StudentNum[StudentNumLen];char StudentName[StudentNameLen];int  StudentScore;
}ElemType;

2、Stack

(1)说明

链栈的数据域和指针域。

(2)源码

typedef struct Stack
{ElemType      Data;struct Stack* NextPointer;
}Stack;

3、LinkStack

(1)说明

多加了一个StackLen是为了提升计算链栈长度的效率,因为链栈不能像顺序栈一样用栈顶指针减去栈底指针得到栈长度,而是需要遍历整个链栈得到栈长度,时间复杂度为O(n),所以多加了一个参数StackLen,使得时间复杂度变为O(1)。

(2)源码

typedef struct LinkStack
{Stack*       StackTop;StackLenType StackLen;
}LinkStack;

四、函数定义

1、InitLinkStack

(1)用途

初始化链栈,头节点置为NULL,表示栈为空,后续入栈时,再申请空间。

(2)源码

Status InitLinkStack(LinkStack* LS)
{JudgeAllNullPointer(LS);LS->StackTop = NULL;LS->StackLen = 0;Log("Init LinkStack  : OK\n",Info);return SuccessFlag;
}

(3)参数

参数名

说明

LS

需要初始化的LinkStack*类型链栈。

2、JudgeLinkStackIsEmpty

(1)用途

判断链栈是否为空,如果头指针为空,则链栈为空,反之非空。

(2)源码

Status JudgeLinkStackIsEmpty(LinkStack* LS)
{JudgeAllNullPointer(LS);if(LS->StackTop == NULL){Log("Judge LinkStack: Empty\n",Debug);return SuccessFlag;}Log("Judge LinkStack: Not Empty\n",Debug);return FailFlag;
}

(3)参数

参数名

说明

LS

需要判断是否为空的LinkStack*类型链栈。

3、GetLinkStackLen

(1)用途

获取链栈的长度。

(2)源码

StackLenType GetLinkStackLen(LinkStack* LS)
{JudgeAllNullPointer(LS);return LS->StackLen;
}

(3)参数

参数名

说明

LS

需要获取长度的LinkStack*类型链栈。

4、PushLinkStack

(1)用途

压栈,将数据放入链栈中。

(2)源码

Status PushLinkStack(LinkStack* LS, ElemType E)
{JudgeAllNullPointer(LS);Stack* NewStack       = (Stack*)MyMalloc(sizeof(Stack));NewStack->Data        = E;NewStack->NextPointer = LS->StackTop;LS->StackTop          = NewStack;LS->StackLen++;Log("Push LinkStack  : OK\n",Info);return SuccessFlag;
}

(3)参数

参数名

说明

LS

需要压栈的LinkStack*类型链栈。

E

需要压栈的ElemType类型数据。

5、GetLinkStackTop

(1)用途

获取栈顶元素数据域,返回一个ElemType类型数据。

(2)源码

ElemType GetLinkStackTop(LinkStack* LS)
{JudgeAllNullPointer(LS);return LS->StackTop->Data;
}

(3)参数

参数名

说明

LS

需要获取栈顶元素数据域的LinkStack*类型链栈。

6、PopLinkStack

(1)用途

弹栈,将栈顶的数据删除。

(2)源码

Status PopLinkStack(LinkStack* LS, ElemType* E)
{JudgeAllNullPointer(LS);JudgeAllNullPointer(E);if(JudgeLinkStackIsEmpty(LS) == SuccessFlag){Log("LinkStack is Empty, Data cannot be poped\n",Warning);return FailFlag;}LS->StackLen--;*E = LS->StackTop->Data;Stack* Tmp = LS->StackTop;LS->StackTop = LS->StackTop->NextPointer;free(Tmp);Tmp = NULL;Log("Pop LinkStack   : OK\n",Info);return SuccessFlag;
}

(3)参数

参数名

说明

LS

需要弹栈的LinkStack*类型链栈。

E

需要弹栈的ElemType*类型数据,是一个输出参数。

五、虚机测试

[gbase@czg2 LinearTable_LinkStack]$ make
gcc -Wall -O3 ../Log/Log.c LinkStack.c main.c -o TestLinkStack -I ../Log/[gbase@czg2 LinearTable_LinkStack]$ ./TestLinkStack 
2023-2--Info--Init LinkStack  : OK
2023-2--Debug--Judge LinkStack: Empty
2023-2--Info--Push LinkStack  : OK
2023-2--Info--Push LinkStack  : OK
2023-2--Info--Push LinkStack  : OK
2023-2--Info--Push LinkStack  : OK
2023-2--Info--Push LinkStack  : OK
2023-2--Info--Push LinkStack  : OK
2023-2--Info--Push LinkStack  : OK
2023-2--Info--Push LinkStack  : OK
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 107
2023-2--Debug--LinkStack Data :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 107
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 106
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 105
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 104
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 103
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 102
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 101
+++++++++++++++
StudentNum     : X666
StudentName    : Sun
StudentScore   : 100
+++++++++++++++
LinkStackLen   : 8
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 107
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 106
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 105
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 104
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 103
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 102
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 101
2023-2--Debug--Judge LinkStack: Not Empty
2023-2--Info--Pop LinkStack   : OK
2023-2--Debug--ElemType Data  :
StudentNum     : X666
StudentName    : Sun
StudentScore   : 100
2023-2--Debug--LinkStack Data :
LinkStackLen   : 0

相关文章:

数据结构与算法基础-学习-11-线性表之链栈的初始化、判断非空、压栈、获取栈长度、弹栈、获取栈顶元素

一、个人理解链栈相较于顺序栈不存在上溢(数据满)的情况,除非内存不足,但存储密度会低于顺序栈,因为会多存一个指针域,其他逻辑和顺序表一致。总结如下:头指针指向栈顶。链栈没有头节点直接就是…...

Hive内置函数

文章目录Hive内置函数字符串函数时间类型函数数学函数集合函数条件函数类型转换函数数据脱敏函数其他函数用户自定义函数Hive内置函数 查询内置函数用法: DESCRIBE FUNCTION EXTENDED 函数名;字符串函数 字符串连接函数:concat带分隔符字符串连接函数…...

Git如何快速入门

什么是Git?我们开发的项目,也需要一个合适的版本控制系统来协助我们更好地管理版本迭代,而Git正是因此而诞生的(有关Git的历史,这里就不多做阐述了,感兴趣的小伙伴可以自行了解,是一位顶级大佬在…...

netcore构建webservice以及调用的完整流程

目录构建前置准备编写服务挂载服务处理SoapHeader调用添加服务调用服务补充内容构建 前置准备 框架版本要求:netcore3.1以上 引入nuget包 SoapCore 编写服务 1.编写服务接口 示例 using System.ServiceModel;namespace Services;[ServiceContract(Namespace &…...

Mysql事务基础(解析)

并发事务带来的问题A和B是并发事务脏写(A被B覆盖)两个事务。B事务覆盖了A事务。解决:应该事务并行脏读(B读到了A的执行中间结果)A修改了东西。B看到了他的中间状态。解决:读写冲突。加锁,改完再…...

2023 年首轮土地销售活动来了 与 The Sandbox 一起体验「体素狂热」!

2 月 14 日晚上 11 点,开始你的体素冒险。 The Sandbox 很高兴推出 2023 年的第一次土地销售活动。欢迎来到「体素狂热 (Voxel Madness)」! 简要概括 土地销售抽奖活动将于北京时间 2 月 14 日星期二晚上 11 点开始 「体素狂热」 土地销售活动将于 2 月…...

vue AntD中栅格布局的四种大小xs,sm,md,lg

cssBootstrap栅格布局的四种大小xs,sm,md,lg前端为了页面在不同大小的设备上也能够正常显示,通常会使用栅格布局的方式来实现。使用bootStrap的网格系统时,常见到一下格式的类名col-*-*visible-*-*hidden_*_* 中间可为xs,xsm,md,lg等表示大小的单词的缩写…...

window.open()打开窗口全屏

window.open (page.html, page, height100, width400, top0, left0, toolbarno, menubarno, scrollbarsno, resizableno,locationn o, statusno, fullscreenyes); 参数解释: window.open() 弹出新窗口的命令; ‘page.html’ 弹出窗口的文件名&#xff…...

VFIO软件依赖——VFIO协议

文章目录背景PCI设备模拟PCI设备抽象VFIO协议实验Q&A背景 在虚拟化应用场景中,虚拟机想要在访问PCI设备时达到IO性能最优,最直接的方法就是将物理设备暴露给虚拟机,虚拟机对设备的访问不经过任何中间层的转换,没有虚拟化的损…...

C/C++【内存管理】

✨个人主页: Yohifo 🎉所属专栏: C修行之路 🎊每篇一句: 图片来源 Love is a choice. It is a conscious commitment. It is something you choose to make work every day with a person who has chosen the same thi…...

第8篇:Java编程语言的8大优势

目录 1、简单性 2、面向对象 3、编译解释性 4、稳健性 5、安全性 6、跨平台性...

STM32定时器实现红外接收与解码

1.NEC协议 红外遥控是一种比较常用的通讯方式,目前红外遥控的编码方式中,应用比较广泛的是NEC协议。NEC协议的特点如下: 载波频率为 38KHz8位地址和 8位指令长度地址和命令2次传输(确保可靠性)PWM 脉冲位置调制&#…...

18- Adaboost梯度提升树 (集成算法) (算法)

Adaboost 梯度提升树: from sklearn.ensemble import AdaBoostClassifier model AdaBoostClassifier(n_estimators500) model.fit(X_train,y_train) 1、Adaboost算法介绍 1.1、算法引出 AI 39年(公元1995年),扁鹊成立了一家专治某疑难杂症…...

zlink 介绍

zlink 是一个基于 flink 开发的分布式数据开发工具,提供简单的易用的操作界面,降低用户学习 flink 的成本,缩短任务配置时间,避免配置过程中出现错误。用户可以通过拖拉拽的方式实现数据的实时同步,支持多数据源之间的…...

C++之std::string的resize与reverse

std::string的resize与reverse前言1.resize2.reserve前言 在C中我们经常用std::string 来保存字符串,其中有两个比较常用但是却平时容易被搞混的两个函数,分别是resize和reserve,模糊意识里,这两个方法都是对std::string的容量或元…...

在.net中运用ffmpeg 操作视频

using System;using System.Collections.Generic;using System.Diagnostics;using System.IO;using System.Text;namespace learun.util{/// <summary>/// ffmpeg视频相关处理的类/// </summary>public class FFmpegUtil{public static int Run(string cmd){try{//…...

05- 线性回归算法 (LinearRegression) (算法)

线性回归算法(LinearRegression)就是假定一个数据集合预测值与实际值存在一定的误差, 然后假定所有的这些误差值符合正太分布, 通过方程求这个正太分布的最小均值和方差来还原原数据集合的斜率和截距。当误差值无限接近于0时, 预测值与实际值一致, 就变成了求误差的极小值。 fr…...

JAVA补充知识01之枚举enum

目录 1. 枚举类的使用 1.1 枚举类的理解 1.2 举例 1.3 开发中的建议&#xff1a; 1.4 Enum中的常用方法 1.5 熟悉Enum类中常用的方法 1.6 枚举类实现接口的操作 1.7 jdk5.0之前定义枚举类的方式 &#xff08;了解即可&#xff09; 1.8 jdk5.0之后定义枚举类的方式 1…...

jenkins下配置maven

1. 先在jenkins服务器上安装maven 下载-解压-重命名-启动 [rootVM-0-12-centos local]# wget https://mirrors.aliyun.com/apache/maven/maven-3/3.9.0/binaries/apache-maven-3.9.0-bin.tar.gz [rootVM-0-12-centos local]# tar xf apache-maven-3.9.0-bin.tar.gz [rootVM-0…...

春季开学即将到来!大学生活必备数码清单奉上

马上就要开学了&#xff0c;你的返校装备是否已经准备齐全了呢&#xff1f;对于高校学生来说&#xff0c;很多数码产品都属于必备装备&#xff0c;比如下面这几款产品就受到了大量年轻消费者的喜爱&#xff0c;在它们的帮助下能够让大家的学习时光变得更快乐。1、不入耳黑科技骨…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Python Ovito统计金刚石结构数量

大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

欢乐熊大话蓝牙知识17:多连接 BLE 怎么设计服务不会乱?分层思维来救场!

多连接 BLE 怎么设计服务不会乱&#xff1f;分层思维来救场&#xff01; 作者按&#xff1a; 你是不是也遇到过 BLE 多连接时&#xff0c;调试现场像网吧“掉线风暴”&#xff1f; 温度传感器连上了&#xff0c;心率带丢了&#xff1b;一边 OTA 更新&#xff0c;一边通知卡壳。…...

JS设计模式(5): 发布订阅模式

解锁JavaScript发布订阅模式&#xff1a;让代码沟通更优雅 在JavaScript的世界里&#xff0c;我们常常会遇到这样的场景&#xff1a;多个模块之间需要相互通信&#xff0c;但是又不想让它们产生过于紧密的耦合。这时候&#xff0c;发布订阅模式就像一位优雅的信使&#xff0c;…...