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

《栈和队列的应用举例(全)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈和队列的应用举例栈的应用举例栈的基本用途保存暂时不用的数据或存储地址可简化程序设计栈的应用例1：数制转换（十转N）用栈暂存低位值例2：括号匹配的检验用栈暂存左括号例3：表达式求值用栈暂存运算符和操作数例4：迷宫求解用栈实现递归调用例5：行编辑程序例6：二叉树的遍历数制转换例.给定十进制数N=1348,转换为八进制数R=2504其运算过程如下：nndiv8nmod8134816841682102125202低位高位数制转换1.依次求余数,并送入栈中：(1)r1=1348%8=4//求余n1=1348/8=168//整除(2)r

2、2=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=25044045042504(1)4进栈(3)5进栈(2)0进栈(4)2进栈判定表达式中的刮号匹配1.刮号匹配的表达式例.{...(...()...)...}[...{...()...()...}...]2.刮号不匹配的表达式例.{...[}...][...(...()...)...)3.判定刮号不匹配的方法例.(...{...{...}..

3、.]↑↑↑↑↑(1)(2)(3)(4)(5)({({{({((1)“(”进栈(3)“{”进栈((5)“{”退栈，“]”与“{”不匹配(2)“{”进栈(4)“{”退栈,“}”与“{”匹配行编辑程序例.datastru**cture↑↑栈底栈顶←输入文本(进栈)datastru↑↑栈底栈顶e,r,u,t,c,*,*退栈(输错了，删除)datastru↑↑栈底栈顶←再输入文本cturedatastructure↑↑栈底栈顶表达式求值例：4+2*3–10/(7–5)①③②④⑤求值规则：1.先乘除,后加减；2.先括号内,后括号外；3.同

4、类运算,从左至右。约定：1----左算符2----右算符1=#，为开始符2=#，为结束符算符优先关系表+-*/（）#+-*/（）#>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=12算法思想：设立：s1----操作数栈,存放暂不运算的数和中间结果s2----算符栈,存放暂不运算的算符1.置s1,s2为空栈；开始符#进s2；2.重复：{2.1从表达式读取“单词”w----操作数/算符2.2若w为操作数，则w进s1；2.3若w为算符，则：2.3.1若w>s2的顶算符，则w进s

5、2；2.3.2若w=s2的顶算符，且w=“)”，则pop(s2)；2.3.3若w

6、7–5)#1210（/-#571210-（/-#1210（/-#a=5；b=7；0p=“-”；c=7-5=2；21210（/-#21210/-#10-#a=2；b=12；0p=“/”；c=12/2=6；a=6；b=10；c=10-6=4；610-##s1s2s1s2s1s2s1s2s1s2s1s2s1s2s1s2例.#4+2*3–12/(7–5)#4#s1s2栈s1最后的顶(底)元素为表达式的值→迷宫求解从入口出发，按某一方向向未走过的前方探索若能走通，则到达新点，否则试探下一方向;若所有的方向均没有通路，则沿原路返回前一点，

7、换下一个方向再继续试探直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。求解思想：回溯法迷宫求解队列的应用举例队列的基本用途保存暂时不用的数据或存储地址可简化程序设计例.用队列进行迷宫求解用队列进行迷宫求解的基本思想是：从迷宫的入口[1][1]出发，向四周搜索，记下所有一步能到达的坐标点；然后依次从每一点出发，向四周搜索，记下所有从入口点出发，经过两步可以到达的坐标点……依次进行下去，一直到达迷宫的出口处[4][4]。然后从出口处沿搜索路径回溯直到入口点，这样就找到了从入口到出口的一条最短路径。011000

8、00101011100110000010101010474101-11115492548354744262335332432122112序号行列前驱由于先到达的点要先向下搜索，故引进一个“先进先出”数据结构——队列来保存已到达的点的坐标。到达迷宫的出口点(4,4)后，为了能够