数据结构第七讲课件.ppt

《数据结构第七讲课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七讲栈的应用3行编辑程序一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。每接受一个字符即存入用户数据区不恰当较好的做法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，允许用户输入出差错，并在发现有错误时可以及时更正。3.行编辑程序p50算法3.2voidlineedit(){initstack(s);ch=getchar();while(ch!=eof){while(ch!=eof&&ch!=‘’){switch(ch){case‘#’:pop(s,c);case‘@’:clearstack(s);def

2、ault:push(s,ch);}ch=getchar();}clearstack(s);if(ch!=eof)ch=gethar();}destroystack(s);}3.2.4迷宫求解入口出口迷宫求解问题通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此在求迷宫通路的算法中应用栈也就

3、是自然而然的事情了。则求迷宫中一条路径的算法的基本思想：若当前位置“可通”，则纳入“当前路径”，并继续朝下一位置探索，即切换下一位置为当前位置，如此重复直到到达出口；若当前位置不可通，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。d

4、o{若当前位置可通，则{　　　将当前位置插入栈顶；//纳入路径若该位置是出口位置，则算法结束；//此时栈中存放的是一条从入口位置到出口位置的路径否则切换当前位置的东邻方块为新的当前位置；　　　}否则{若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为:沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则{删去栈顶位置；//从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空；　　　　}　　}　}while(栈不空)；表达式求值的算法采用“算符优先法”，在表达式中,优先级的顺序是:（1）括

5、号的优先级最高,对括号内的各种运算符有:先乘除、再加减，同级运算从左至右。（2）先括号内，后括号外，多层括号，由内向外。任何表达式都是由操作数、运算符和界符组成。操作数可以是常量、变量、常数运算符有算术运算符、关系运算符、逻辑运算符界符包括左右括号算式结束符。运算符和界符统称为“算符”。在算符集中，在每一个运算步，相邻的算符c1和c2之间的关系是如下三种情况（c1出现在c2之前）：c1c2,c1的优先级大于c27*(5-3)算符间优先级c2c1为实现算符优先算法，在这里用了两个工作栈。一个存放算符OPTR，

6、另一个存放数据OPND。算法思想是：（1）首先置数据栈为空栈，表达式起始符“＃”为算符栈的栈底元素（2）自左向右扫描表达式，读到操作数进OPND栈，读到运算符，则和OPTR栈顶元素比较（栈顶元素为c1，读到的算符为c2);若c1c2,则将c1出栈，并在操作数栈取出两个元素a和b按c1做运算，运算结果进OPND.重复直到表达式求值完毕。例如：表达式3*(7-2),求值过程如下表：intexpress(){Initstack(OP

7、TR);Push(OPTR,’#’);InitStack(OPND);w=getchar();while(w!=‘#’

8、

9、GetTop(OPTR)!=‘#’){if(!In(w,OP)){Push(OPND,w);w=getchar();}else//OP是操作符集合switch(Precede(GetTop(OPTR),w)){case‘<‘:Push(OPTR,w);w=getchar();break;case‘=‘:Pop(OPTR);w=getchar();break;case‘>‘:op=Pop(OPTR);b=Po