第三章栈和队列ppt课件.ppt

第三章栈和队列 通常称 栈和队列是限定插入和删除只能在表的 端点 进行的线性表 线性表栈队列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 2栈的应用举例 3 3栈类型的实现 3 4队列的类型定义 3 5队列类型的实现 3 1栈的类型定义 栈 Stack 定义 是限定仅在表尾进行插入或删除操作的线性表 允许插入和删除的一端称为栈顶 top 另一端称为栈底 bottom 特点 后进先出 LIFO a1 top bottom an 进栈 出栈 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 3 2栈类型的实现 顺序栈 链栈 栈的表示和实现 顺序栈 栈的顺序存储结构 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 指针top指向栈顶元素在顺序栈中的下一个位置 base为栈底指针 指向栈底的位置 base 顺序栈的类型表示 defineSTACK INIT SIZE100 defineSTACKINCREMENT10 typedefcharSElemType typedefstruct 顺序栈定义SElemType base 栈底指针SElemType top 栈顶指针intstacksize 当前已分配的存储空间 SqStack 判栈空intStackEmpty SqStackS if S top S base return1 判栈空 空则返回1elsereturn0 否则返回0 判栈满intStackFull SqStackS if S top S base S StackSize return1 判栈满 满则返回1elsereturn0 否则返回0 顺序栈的基本运算 初始化StatusInitStack SqStack 入栈StatusPush SqStack 取栈顶元素StatusGetTop SqStackS SElemType 出栈StatusPop SqStack 链式栈 栈的链接表示 链式栈无栈满问题 空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作 top 链栈 top 链栈 a1 an 注意 链栈中指针的方向 an 1 栈底元素 3 3栈的应用举例 例一 数制转换 例二 括号匹配的检验 例三 行编辑程序问题 例四 迷宫求解 例五 表达式求值 例六 实现递归 例一 数制转换算法基于原理 N Ndivd d Nmodd 例如 1348 10 2504 8 其运算过程如下 NNdiv8Nmod8134816841682102125202 计算顺序 输出顺序 voidconversion InitStack S scanf d conversion 例二 括号匹配的检验假设在表达式中 或 等为正确的格式 或 或 均为不正确的格式 则检验括号是否匹配的方法可用 期待的急迫程度 这个概念来描述 分析可能出现的不匹配的情况 到来的右括弧非是所 期待 的 例如 考虑下列括号序列 12345678 到来的是 不速之客 直到结束 也没有到来所 期待 的括弧 算法的设计思想 1 凡出现左括弧 则进栈 2 凡出现右括弧 首先检查栈是否空若栈空 则表明该 右括弧 多余否则和栈顶元素比较 若相匹配 则 左括弧出栈 否则表明不匹配 3 表达式检验结束时 若栈空 则表明表达式中匹配正确否则表明 左括弧 有余 Statusmatching string 例三 行编辑程序问题 如何实现 每接受一个字符即存入存储器 并不恰当 设立一个输入缓冲区 用以接受用户输入的一行字符 然后逐行存入用户数据区 并假设 为退格符 为退行符 在用户输入一行的过程中 允许用户输入出差错 并在发现有误时可以及时更正 合理的作法是 假设从终端接受了这样两行字符 whli ilr e s s outcha putchar s 则实际有效的是下列两行 while s putchar s while ch EOF 从终端接收下一个字符 ClearStack S 重置S为空栈if ch EOF ch getchar while ch EOF EOF为全文结束符 将从栈底到栈顶的字符传送至调用过程的数据区 例四 迷宫求解 通常用的是 穷举求解 的方法 111 122 222 321 331 344 241 251 264 163 153 144 3 0123456789 0123456789 求迷宫路径算法的基本思想是 若当前位置 可通 则纳入路径 继续前进 若当前位置 不可通 则后退 换方向继续探索 若四周 均无通路 则将当前位置从路径中删除出去 设定当前位置的初值为入口位置 do 若当前位置可通 则 将当前位置插入栈顶 若该位置是出口位置 则算法结束 否则切换当前位置的东邻方块为新的当前位置 否则 while 栈不空 求迷宫中一条从入口到出口的路径的算法 若栈不空且栈顶位置尚有其他方向未被探索 则设定新的当前位置为 沿顺时针方向旋转找到的栈顶位置的下一相邻块 若栈不空但栈顶位置的四周均不可通 则 删去栈顶位置 从路径中删去该通道块若栈不空 则重新测试新的栈顶位置 直至找到一个可通的相邻块或出栈至栈空 若栈空 则表明迷宫没有通路 例五 实现递归 将所有的实在参数 返回地址等信息传递给被调用函数保存 为被调用函数的局部变量分配存储区 将控制转移到被调用函数的入口 当在一个函数的运行期间调用另一个函数时 在运行该被调用函数之前 需先完成三项任务 保存被调函数的计算结果 释放被调函数的数据区 依照被调函数保存的返回地址将控制转移到调用函数 从被调用函数返回调用函数之前 应该完成下列三项任务 多个函数嵌套调用的规则是 此时的内存管理实行 栈式管理 后调用先返回 例如 voidmain voida voidb a b main a b Main的数据区 函数a的数据区 函数b的数据区 递归工作栈 递归过程执行过程中占用的数据区 递归工作记录 每一层的递归参数合成一个记录 当前活动记录 栈顶记录指示当前层的执行情况 当前环境指针 递归工作栈的栈顶指针 递归函数执行的过程可视为同一函数进行嵌套调用 例如 voidhanoi intn charx chary charz 将塔座x上按直径由小到大且至上而下编号为1至n 的n个圆盘按规则搬到塔座z上 y可用作辅助塔座 1if n 1 2move x 1 z 将编号为 的圆盘从x移到z3else 4hanoi n 1 x z y 将x上编号为 至n 1的 圆盘移到y z作辅助塔5move x n z 将编号为n的圆盘从x移到z6hanoi n 1 y x z 将y上编号为 至n 1的 圆盘移到z x作辅助塔7 8 83abc 返址nxyz 52acb 51abc voidhanoi intn charx chary charz 1if n 1 2move x 1 z 3else 4hanoi n 1 x z y 5move x n z 6hanoi n 1 y x z 7 8 71cab 3 4队列的类型定义 队列 Queue 也是一种运算受限的线性表 它只允许在表的一端进行插入 而在另一端进行删除 允许删除的一端称为队头 front 允许插入的一端称为队尾 rear 例如 排队购物 先进入队列的成员总是先离开队列 因此队列亦称作先进先出 FirstInFirstOut 的线性表 简称FIFO表 队列的类型定义 ADTQueue 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 R1 ai 1 ai D i 2 n 约定其中a1端为队列头 an端为队列尾 基本操作 ADTQueue 队列的基本操作 InitQueue Q DestroyQueue Q QueueEmpty Q QueueLength Q GetHead Q e ClearQueue Q DeQueue Q e EnQueue Q e QueueTravers Q visit InitQueue Q 操作结果 构造一个空队列Q DestroyQueue Q 初始条件 队列Q已存在 操作结果 队列Q被销毁 不再存在 QueueEmpty Q 初始条件 队列Q已存在 操作结果 若Q为空队列 则返回TRUE 否则返回FALSE QueueLength Q 初始条件 队列Q已存在 操作结果 返回Q的元素个数 即队列的长度 GetHead Q e 初始条件 Q为非空队列 操作结果 用e返回Q的队头元素 a1 a2 an ClearQueue Q 初始条件 队列Q已存在 操作结果 将Q清为空队列 EnQueue Q e 初始条件 队列Q已存在 操作结果 插入元素e为Q的新的队尾元素 a1 a2 an e DeQueue Q e 初始条件 Q为非空队列 操作结果 删除Q的队头元素 并用e返回其值 a1 a2 an 3 5队列类型的实现 链队列 链式映象 循环队列 顺序映象 链队列 队列的链式表示 队列的链式存储结构简称为链队列 它是限制仅在表头删除和表尾插入的单链表 显然仅有单链表的头指针不便于在表尾做插入操作 为此再增加一个尾指针 指向链表的最后一个结点 于是 一个链队列由头指针和尾指针唯一确定 队列的链式存储结构 typedefstructQNode 结点类型QElemTypedata structQNode next QNode QueuePtr typedefstruct 链队列类型QueuePtrfront 队头指针QueuePtrrear 队尾指针 LinkQueue 空队列 链队列 队列的链式表示 链队列中 有两个分别指示队头和队尾的指针 链式队列在进队时无队满问题 但有队空问题 空队列 StatusInitQueue LinkQueue StatusEnQueue LinkQueue StatusDeQueue LinkQueue if Q rear p Q rear Q front 循环队列 顺序映象 defineMAXQSIZE100 最大队列长度typedefstruct QElemType base 动态分配存储空间intfront 头指针 若队列不空 指向队列头元素intrear 尾指针 若队列不空 指向 队列尾元素的下一个位置intqueuesize SqQueue 顺序队列 队列的顺序存储表示 用一组地址连续的存储单元依次存放从队列头到队列尾的元素 指针front和rear分别指示队头元素和队尾元素的位置 插入新的队尾元素 尾指针增1 rear rear 1 删除队头元素 头指针增1 front front 1 因此 在非空队列中 头指针始终指向队列头元素 而尾指针始终指向队列尾元素的下一个位置 队满时再进队将溢出解决办法 将顺序队列臆造为一个环状的空间 形成循环 环形 队列 循环队列 顺序映象 队列的进队和出队 队空 Q front Q rear队满 Q rear Q front maxsize 求队长 入队 新元素按rear指示位置加入 再将队尾指针加一 即rear rear 1出队 将front指示的元素取出 再将队头指针加一 即front front 1 非循环队列 和栈类似 队列中亦有上溢和下溢现象 此外 顺序队列中还存在 假上溢 现象 因为在入队和出队的操作中 头尾指针只增加不减小 致使被删除元素的空间永远无法重新利用 因此 尽管队列中实际的元素个数远远小于向量空间的规模 但也可能由于尾指针巳超出向量空间的上界而不能做入队操作 该现象称为假上溢 为充分利用向量空间 克服上述假上溢现象 可以将向量空间想象为一个首尾相接的圆环 并称这种向量为循环向量 存储在其中的队列称为循环队列 CircularQueue 在循环队列中进行出队 入队操作时 头尾指针仍要加1 朝前移动 只不过当头尾指针指向向量上界 QueueSize 1 时 其加1操作的结果是指向向量的下界0 显然 因为循环队列元素的空间可以被利用 除非向量空间真的被队列元素全部占用 否则不会上溢 因此 除一些简单的应用外 真正实用的顺序队列是循环队列 打开P64如图3 14所示 由于入队时尾指针向前追赶头指针 出队时头指针向前追赶尾指针 故队空和队满时头尾指针均相等 因此 我们无法通过Q front Q rear来判断队列 空 还是 满 解决此问题的方法至少有两种 其一是另设一个布尔变量以区别队列的空和满 其二是少用一个元素的空间 约定入队前 测试尾指针在循环意义下加1后是否等于头指针 若相等则认为队满 注意 rear所指的单元始终为空 循环队列 CircularQueue 队头 队尾指针加1 可用取模 余数 运算实现 队头指针进1 front front 1 maxsize 队尾指针进1 rear rear 1 maxsize 队列初始化 front rear 0 队空条件 front rear 队满条件 rear 1 maxsize front 0 1 2 3 4 5 6 7 循环队列 front rear Maxsize 1 解决方案 1 另外设一个标志以区别队空 队满2 少