数据结构.ppt

1 内容回顾 线性链表的链式存储及查找 插入和删除操作 2 第3章栈和队列 一 本讲主要内容 理论 栈的定义及实现栈的应用实例实验 栈的基本操作 3 课前思考 简单地说 线性结构是一个数据元素的序列 必然是依从上往下的次序 即n 2 1 它们遵循的是 后进先出 的规律 这正是本章要讨论的 栈 的结构特点 是 排队 在计算机程序中 模拟排队的数据结构是 队列 4 通常称 栈和队列是限定插入和删除只能在表的 端点 进行的线性表 线性表栈队列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 栈和队列是两种常用的数据类型 5 3 1栈3 1 1栈的定义及基本运算定义 栈 Stack 是限制在表的一端进行插入和删除运算的线性表 通常称插入 删除的这一端为栈顶 Top 另一端为栈底 Bottom 当表中没有元素时称为空栈 特点 先进后出 FILO 或后进先出 LIFO 6 例1 对于一个栈 给出输入项A B C 如果输入项序列由ABC组成 试给出所有可能的输出序列 A进A出B进B出C进C出ABCA进A出B进C进C出B出ACBA进B进B出A出C进C出BACA进B进B出C进C出A出BCAA进B进C进C出B出A出CBA不可能产生输出序列CAB 7 例2 一个栈的输入序列是12345 若在入栈的过程中允许出栈 则栈的输出序列43512可能实现吗 12345的输出呢 43512不可能实现 主要是其中的12顺序不能实现 12345的输出可以实现 只需压入一个立即弹出一个即可 8 栈的主要运算 1 初始化栈 InitStack S 将栈S置为一个空栈 不含任何元素 2 进栈 PUSH S X 将元素X插入到栈S中 也称为 入栈 插入 压入 3 出栈 POP S e 删除栈S中的栈顶元素 也称为 退栈 删除 弹出 4 取栈顶元素 GETTOP S e 取栈S中栈顶元素 5 判栈空 EMPTY S 判断栈S是否为空 若为空 返回值为1 否则返回值为0 9 栈的抽象数据类型描述 ADTStack 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 1 2 n 基本操作 InitStack S 操作前提 S为未初始化的栈 操作结果 将S初始化为空栈 ClearStack S 操作前提 栈S已经存在 操作结果 将栈S置成空栈 StackEmpty S 操作前提 栈S已经存在 操作结果 若栈S为空 则返回TRUE 否则FALSE 10 StackLength S 操作前提 栈S已经存在 操作结果 返回S的元素个数即栈的长度 IsFull S 操作前提 栈S已经存在 操作结果 判栈满函数 若S栈已满 则函数值为TRUE 否则为FALSE StackTraverse S visit 操作前提 栈S已经存在且非空 操作结果 从栈底到栈顶依次对S底每个元素调用函数visit 一旦visit 失败 则操作失效 11 Push S e 操作前提 栈S已经存在 操作结果 在S的顶部插入 亦称压入 元素e 若S栈未满 将e插入栈顶位置 若栈已满 则返回FALSE 表示操作失败 否则返回TRUE Pop S e 操作前提 栈S已经存在 操作结果 删除 亦称弹出 栈S的顶部元素 并用e带回该值 若栈为空 返回值为FALSE 表示操作失败 否则返回TRUE GetTop S e 操作前提 栈S已经存在 操作结果 取栈S的顶部元素 与Pop S e 不同之处在于GetTop S e 不改变栈顶的位置 ADTStack 12 3 1 2栈的表示和实现 顺序栈链栈 13 3 1 2栈的表示和实现 1 顺序栈 栈的顺序存储结构 base stackMaxSize 存放自栈底到栈顶的数据元素top附设栈顶指针top 来动态地指示栈顶元素栈中位置stacksize当前栈的最大容量 14 defineSTACK INIT SIZE100 defineSTACKINCREMENT10 typedefstruct SElemType base 栈底指针 始终指向栈底 SElemType top 栈顶指针intstacksize 当前栈的最大容量 SqStack SqStacks typedefstruct datatypebase stacksize inttop sqstack 15 s tops base A s base s top B A E D C B A s top s base s tops base s base始终指向栈底s base NULL表示栈结构不存在s top s base表示栈空s top始终指向栈顶元素的下一个位置s top 插入元素s top 删除元素 第3章 16 2020 2 3 几点说明 栈空条件 s top s base此时不能出栈栈满条件 s top s base s stacksize进栈操作 s top e 或 s top e s top 退栈操作 e s top 或s top e s top 当栈满时再做进栈运算必定产生空间溢出 简称 上溢 当栈空时再做退栈运算也将产生溢出 简称 下溢 17 顺序栈基本操作的实现如下 1 初始化栈 构造一个空栈voidInitStack SqStack 18 2 判栈空 intStackEmpty SqStackS 判栈S为空栈时返回值为真 反之为假 returnS top S base 3 判栈满 intStackFull SqStackS return S top S stacksize 19 4 读取栈顶元素 ElemTypeGetTop SqStackS ElemType 20 5 入栈voidPush SqStack 判满 栈顶指针后移 赋值 21 6 出栈 voidPop SqStack 判空 修改栈顶指针 22 栈的应用举例由于栈的操作具有后进先出的固有特性 致使栈成为程序设计中的有用工具 凡应用问题求解的过程具有 后进先出 的天然特性的话 则求解的算法中也必然需要利用 栈 数制转换假设要将十进制数N转换为d进制数 如8进制 81348余数81684821082502转换结果 2504 后得到的余数先输出 23 数制转换 假设要将十进制数N转换为d进制数 一个简单的转换算法是重复下述两步 直到N等于零 X Nmodd 其中mod为求余运算 N Ndivd 其中div为整除运算 24 voidConversion intN 对于任意的一个非负十进制数N 打印出与其等值的8进制数 StackS intx S为顺序栈或链栈 InitStack 算法3 1 25 作业 1 设将整数1 2 3 4依次进栈 但只要出栈时栈非空 则可将出栈操作按任何次序夹入其中 请回