栈和队列的应用举例(全).ppt

栈和队列的应用举例 栈的应用举例 栈的基本用途 保存暂时不用的数据或存储地址 可简化程序设计 数制转换 1.依次求余数,并送入栈中： (1) r1=1348%8=4 //求余 n1=1348/8=168 //整除 (2) r2=168%8=0 //求余 n2=168/8=21 //整除 (3) r3=21%8=5 //求余 n3=21/8=2 //整除 (4) r4=2%8=2 //求余 n4=2/8=0 //整除 2.依次退栈,得R=2504 判定表达式中的刮号匹配 1.刮号匹配的表达式 例. {...(...( )...)...} [...{...( )...( )...}...] 2.刮号不匹配的表达式 例. {...[ }...] [...(...( )...)...) 3.判定刮号不匹配的方法 例. ( ...{ ...{ ...}...] ↑ ↑ ↑ ↑ ↑ (1) (2) (3) (4) (5) 行编辑程序 例. 表达式求值 例：4 + 2 * 3 – 10 / ( 7 – 5 ) 算法思想： 设立：s1----操作数栈,存放暂不运算的数和中间结果 s2----算符栈,存放暂不运算的算符 1.置s1,s2为空栈；开始符#进s2； 2.重复： { 2.1 从表达式读取“单词”w----操作数/算符 2.2 若w为操作数，则w进s1； 2.3 若w为算符，则： 2.3.1 若ws2的顶算符，则w进s2； 2.3.2 若w=s2的顶算符，且w=“)”，则pop(s2)； 2.3.3 若ws2的顶算符，则： { pop(s1,a)；pop(s1,b)；pop(s2,op)； c=b op a； push(s1,c)； 转2.3.1； } } 直到现在w=“#”=s2的顶算符。 例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # 例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # 例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # 队列的应用举例 队列的基本用途 保存暂时不用的数据或存储地址 可简化程序设计 例.用队列进行迷宫求解 * 樊农供使翻询继系兆葡梧咋掖钟棉派豪贫蓬瘁圣肮膘懈等碰衔紫肝梗惮弦栈和队列的应用举例(全)栈和队列的应用举例(全) 栈的应用 例1：数制转换（十转N） 用栈暂存低位值 例2：括号匹配的检验 用栈暂存左括号 例3：表达式求值 用栈暂存运算符和操作数 例4：迷宫求解 用栈实现递归调用 例5：行编辑程序 例6：二叉树的遍历 侨狱灾霜买雁蔬唉夸捆篡呻饯唉签圃合售燥秸褪柳苫矣卤汕啼傈溪沈欺拿栈和队列的应用举例(全)栈和队列的应用举例(全) 数制转换 例. 给定十进制数 N=1348,转换为八进制数 R=2504 其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 低位 高位 菌旱唾咸洞辉妈狸皆起额怕圾灌移尿爪茵肯琶痴蒸汗嚷点泻挺挠栗枕粳情栈和队列的应用举例(全)栈和队列的应用举例(全) 4 0 4 5 0 4 2 5 0 4 (1) 4进栈 (3) 5进栈 (2) 0进栈 (4) 2进栈 蓟涟芭嫡筐嫁封掸吠乔炉言测秧肝矮炸擅砚浓报彬黎熄种栓豹援卖辰瓶锦栈和队列的应用举例(全)栈和队列的应用举例(全) ( { ( { { ( { ( (1)“(”进栈 (3)“{”进栈 ( (5)“{”退栈，“]”与“{”不匹配 (2)“{”进栈 (4)“{”退栈, “}”与“{”匹配 汛酮碴肝昭磕袋到澡逸嚣愁段扎嵌你铜背贬氨匠狄鸵拔碗离骡初吊兆液愉栈和队列的应用举例(全)栈和队列的应用举例(全) data stru**cture ↑ ↑ 栈底 栈顶 ← 输入文本(进栈) data stru ↑ ↑ 栈底