第三章 计算机软件技术基础

1 第三章栈与队列 数据结构电子教案 郇矢宇 2 栈队列栈的应用 表达式求值栈的应用 递归队列的应用 第三章栈与队列 3 只允许在一端插入和删除的线性表允许插入和删除的一端称为栈顶 top 另一端称为栈底 bottom 特点后进先出 LIFO 栈 Stack 退栈 进栈 a0 an 1 an 2 top bottom 4 栈的数组存储表示 顺序栈 5 top 空栈 top top top top top a进栈 b进栈 a a b a b c d e e进栈 a b c d e f进栈溢出 a b d e e退栈 c 6 top c退栈 b退栈 a b a a退栈 空栈 top a b d d退栈 c top a b c top top 7 建立一个容量为m的空栈 include stdlib h Voidinit stack s m top ET s intm top s malloc m sizeof ET top 0 return 8 PROCEDUREPUSH S m top x 若栈不满 则将元素x插入该栈栈顶 否则溢出处理if top m then Stackoverflow RUTURN 栈满top top 1 栈顶指针先加1 再进栈S top x RETURNPROCEDUREPOP S m top y 退出栈顶元素并返回栈顶元素的值if top 0 then Stackunderflow RETURN y S top top top 1 栈顶指针退1returntrue 退栈成功 9 PROCEDURETOP S m top y 若栈不空则返回该栈栈顶元素的地址if top 0 then Stackempty RETURN y S top return 10 栈的链接存储表示 链式栈 链式栈无栈满问题 空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作 top 11 链式栈类操作的实现 templateLinkedStack makeEmpty 逐次删去链式栈中的元素直至栈顶指针为空 StackNode p while top NULL 逐个结点释放 p top top top link deletep templatevoidLinkedStack Push Ex 将元素值x插入到链式栈的栈顶 即链头 12 top newStackNode x top 创建新结点assert top NULL 创建失败退出 templateboolLinkedStack Pop E 13 templateboolLinkedStack getTop EtemplatevoidLinkedStack output ostream os StackNode ptr inti 递归输出栈中所有元素 沿链逆向输出 if ptr NULL 14 if ptr link NULL output os ptr link i osdata endl 逐个输出栈中元素的值 15 队列 Queue 定义队列是只允许在一端删除 在另一端插入的线性表允许删除的一端叫做队头 front 允许插入的一端叫做队尾 rear 特性先进先出 FIFO FirstInFirstOut 16 队列的进队和出队 front rear 空队列 front rear A进队 A front rear B进队 AB front rear C D进队 ABCD front rear A退队 BCD front rear B退队 CD front rear E F G进队 CDEFG CDEFG front rear H进队 溢出 17 队列的进队和出队原则 进队时先将新元素按rear指示位置加入 再将队尾指针加一rear rear 1 队尾指针指示实际队尾的后一位置 出队时按队头指针指示位置取出元素 再将队头指针进一front front 1 队头指针指示实际队头位置 队满时再进队将溢出出错 假溢出 队空时再出队将队空处理 解决假溢出的办法之一 将队列元素存放数组首尾相接 形成循环 环形 队列 18 队列存放数组被当作首尾相接的表处理 队头 队尾指针加1时从maxSize 1直接进到0 可用语言的取模 余数 运算实现 队头指针进1 front front 1 maxSize 队尾指针进1 rear rear 1 maxSize 队列初始化 front rear 0 队空条件 front rear 队满条件 rear 1 maxSize front 循环队列 CircularQueue 19 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front rear A A B C rear rear 空队列 A进队 B C进队 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 A退队 B退队 0 1 2 3 4 5 6 7 D E F G H I进队 front B C rear A front B C rear front C rear D E F G H I 20 队列的链接存储表示 链式队列 队头在链头 队尾在链尾 链式队列在进队时无队满问题 但有队空问题 队空条件为front NULL 21 栈的应用 表达式求值 一个表达式由操作数 亦称运算对象 操作符 亦称运算符 和分界符组成 算术表达式有三种表示 中缀 infix 表示 如A B 前缀 prefix 表示 如 AB 后缀 postfix 表示 如AB 22 中缀表达式a b c d e f后缀表达式abcd ef 前缀表达式 a b cd ef表达式中相邻两个操作符的计算次序为 优先级高的先计算 优先级相同的自左向右计算 当使用括号时从最内层括号开始计算 表达式事例 23 应用后缀表示计算表达式的值 从左向右顺序地扫描表达式 并用一个栈暂存扫描到的操作数或计算结果 在后缀表达式的计算顺序中已隐含了加括号的优先次序 括号在后缀表达式中不出现 计算例abcd ef rst1 rst2 rst3 rst4 rst5 24 一般表达式的操作符有4种类型 算术操作符如双目操作符 和 以及单目操作符 关系操作符包括 这些操作符主要用于比较 逻辑操作符如与 或 非 括号 和 它们的作用是改变运算顺序 25 中缀表示 转后缀表示 先对中缀表达式按运算优先次序加上括号 再把操作符后移到右括号的后面并以就近移动为原则 最后将所有括号消去 如中缀表示 A B D E F A D C 其转换为后缀表达式的过程如下 26 中缀表示 转前缀表示 先对中缀表达式按运算优先次序通统加上括号 再把操作符前移到左括号前并以就近移动为原则 最后将所有括号消去 如中缀表示 A B D E F A D C 其转换为前缀表达式的过程如下 27 应用栈计算中缀表达式的值 使用两个栈 操作符栈OPTR operator 操作数栈OPND operand 为了实现这种计算 需要考虑各操作符的优先级 28 各个算术操作符的优先级 isp叫做栈内 instackpriority 优先数icp叫做栈外 incomingpriority 优先数 操作符优先数相等的情况只出现在括号配对或栈底的 号与输入流最后的 号配对时 29 中缀算术表达式求值 对中缀表达式求值的一般规则 建立并初始化OPTR栈和OPND栈 然后在OPTR栈中压入一个 扫描中缀表达式 取一字符送入ch 当ch 或OPTR栈的栈顶 时 执行以下工作 否则结束算法 在OPND栈的栈顶得到运算结果 若ch是操作数 进OPND栈 从中缀表达式取下一字符送入ch 30 若ch是操作符 比较icp ch 的优先级和isp OPTR 的优先级 若icp ch isp OPTR 则ch进OPTR栈 从中缀表达式取下一字符送入ch 若icp ch isp OPTR 则从OPND栈退出a2和a1 从OPTR栈退出 形成运算指令 a1 a2 结果进OPND栈 若icp ch isp OPTR 且ch 则从OPTR栈退出 对消括号 然后从中缀表达式取下一字符送入ch 31 voidInFixRun stackOPTR OPND charch op OPTR makeEmpty OPND makeEmpty OPTR Push 两个栈初始化getchar ch 读入一个字符op while ch op if isdigit ch 是操作数 进栈 OPND Push ch getchar ch else 是操作符 比较优先级OPTR GetTop op 读一个操作符 32 if icp ch isp op 栈顶优先级低 OPTR Push ch getchar ch elseif icp ch isp op OPTR Pop op 栈顶优先级高OPND DoOperator op elseif ch 优先级相等 OPTR Pop op getchar ch OPTR GetTop op endofwhile 33 34 35 36 栈的应用 递归 递归的定义若一个对象部分地包含它自己 或用它自己给自己定义 则称这个对象是递归的 若一个过程直接地或间接地调用自己 则称这个过程是递归的过程 以下三种情况常常用到递归方法 定义是递归的数据结构是递归的问题的解法是递归的 37 定义是递归的 求解阶乘函数的递归算法longFactorial longn if n 0 return1 elsereturnn Factorial n 1 例如 阶乘函数 38 求解阶乘n 的过程 主程序main fact 4 参数4计算4 fact 3 返回24 参数3计算3 fact 2 返回6 参数2计算2 fact 1 返回2 参数1计算1 fact 0 返回1 参数0直接定值 1返回1 参数传递 结果返回 递归调用 回归求值 39 例如 单链表结构一个结点 它的指针域为NULL 是一个单链表 一个结点 它的指针域指向单链表 仍是一个单链表 数据结构是递归的 40 问题的解法是递归的 例 汉诺塔 TowerofHanoi 问题的解法 如果n 1 则将这一个盘子直接从A柱移到C柱上 否则 执行以下三步 用C柱做过渡 将A柱上的 n 1 个盘子移到B柱上 将A柱上最后一个盘子直接移到C柱上 用A柱做过渡 将B柱上的 n 1 个盘子移到C柱上 41 42 递归算法的执行需要递归工作栈例如 Hanoi算法Hanoi n A B C IFn 1THENmove A 1 C ELSE Hanoi n 1 A C B r1 move A n C Hanoi n 1 B A C r2 RETURN每一层递归要保存参数 返址 n值 A值 B值 C值 43 自顶向下 逐步分解的策略 子问题应与原问题做同样的事情 且更为简单 解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题 分别对这些比较小的问题