




已阅读5页,还剩17页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第三章栈和队列 栈和队列是操作受限的线性表 它们的基本操作是线性表操作的子集 栈是限定仅在表尾进行插入或删除操作的线性表 表尾端成为栈顶 表头端成为栈底 栈的修改是按后进先出的原则进行 栈又称为后进先出的线性表 栈和队列的示意图 栈只能在栈顶进行插入删除等操作 按照后进先出的原则 a1 a2 an 栈顶 栈底 进栈 出栈 a1 a2 a3 an 出队列 入队列 队头 队尾 队列 队尾进行插入操作 队头进行删除操作 线性表栈队列Insert L i x Insert S n 1 x Insert Q n 1 x 1 i n 1Delete L i Delete S n Delete Q 1 1 i n 栈和队列是两种常用的数据类型 栈 队列与线性表的插入 删除操作对比 3 1栈的类型定义 3 3栈的应用举例 3 2栈的表示与实现 3 4队列的类型定义 3 5队列类型的实现 3 1栈的类型定义 ADTStack 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定an端为栈顶 a1端为栈底 基本操作 ADTStack InitStack S DestroyStack S ClearStack S StackEmpty s StackLength S GetTop S e Push S e Pop S e StackTravers S visit InitStack S 操作结果 构造一个空栈S DestroyStack S 初始条件 栈S已存在 操作结果 栈S被销毁 StackEmpty S 初始条件 栈S已存在 操作结果 若栈S为空栈 则返回TRUE 否则FALE StackLength S 初始条件 栈S已存在 操作结果 返回S的元素个数 即栈的长度 GetTop S e 初始条件 栈S已存在且非空 操作结果 用e返回S的栈顶元素 a1 a2 an ClearStack S 初始条件 栈S已存在 操作结果 将S清为空栈 Push S e 初始条件 栈S已存在 操作结果 插入元素e为新的栈顶元素 a1 a2 an e Pop S e 初始条件 栈S已存在且非空 操作结果 删除S的栈顶元素 并用e返回其值 a1 a2 an an 1 栈的存储方法 顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 同时附设指针top指示栈顶元素在顺序栈中的位置 链栈 头指针指向栈顶元素 每个结点的指针域指向前一个结点 顺序栈 top 栈顶指针 始终指向栈顶元素的下一个位置 base 栈底指针 始终指向栈底的位置 base NULL 栈不存在 base top 栈空 base top base top A B C D E F 链栈 注意 链栈中指针的方向 top a1 an an 1 链栈是动态分配元素存储空间 元素的插入删除操作都是在表的同一端进行 头指针就是栈顶指针 栈顶 栈底 3 2栈的表示和实现 栈的定义栈的几个基本操作的实现StatusInitStack SqStack S StatusPush SqStack S SElemTypee StatusPop SqStack S SElemType e 栈的顺序存储表示 defineSTACK INIT SIZE100 defineSTACKINCREMENT10typedefstruct SElemType base 构造栈之前和销毁栈之后 base值为NULLSElemType top 栈顶指针intstacksize 当前已分配的存储空间 以元素为单位 SqStack 类似于线性表的顺序映象实现 指向表尾的指针可以作为栈顶指针 StatusInitStack SqStack Statu
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 试验员实操基础知识培训课件
- 2025年银行、金融反诈骗预防措施知识考试题库(附含答案)
- 电商创业策略计划
- 爱丁堡城堡介绍
- 2025及未来5年中国回力鞋市场调查、数据监测研究报告
- 2025及未来5年中国硼烷市场调查、数据监测研究报告
- 考点解析-人教版八年级上册物理声现象《声音的特性声的利用》难点解析试卷(含答案详解版)
- 2025及未来5年中国舱口盖市场调查、数据监测研究报告
- 2025及未来5年中国珍珠岩保温板市场调查、数据监测研究报告
- 2025及未来5年中国镶蓝宝石项链市场调查、数据监测研究报告
- 2025广西北海市检察机关聘用人员控制数招聘26人考试模拟试题及答案解析
- 酒店治安管理制度模板
- 2025年社区网格工作人员考试题库及答案
- 小学生心理团辅方案与记录模板
- 2025年淮南市大通区和寿县经开区公开招聘社区“两委”后备干部30名备考考试题库附答案解析
- 国防科大优势课件
- 医疗器械财务汇报
- 消毒供应中心包装课件
- 人教PEP版(2024)三年级上册英语教案全册教案
- 河道生态修复工程重点难点分析
- 配电箱保养安全培训课件
评论
0/150
提交评论