第3章栈和队列.pptxVIP

第三章 栈和队列 ;主要内容;3.2 栈的应用举例;数制转换;数制转换;括号匹配的检验;括号匹配的检验;括号匹配的检验;Status match(char *str) //括号匹配的检验 { InitStack(S); for (p=str; *p; p++) { switch(*p) { case ‘(‘: case ‘[‘: case ‘{‘: Push(S, *p); break; //出现左括弧，则进栈； case ‘)’: if (StackEmpty(S)) return ERROR; Pop(S, e); if(e != ‘(‘) return ERROR; break; case ‘]’: if (StackEmpty(S)) return ERROR; Pop(S, e); if(e != ‘[‘) return ERROR; break; case ‘}’: if (StackEmpty(S)) return ERROR; Pop(S, e); if(e != ‘{‘) return ERROR; } //switch } //for if (StackEmpty(S)) return OK; else return ERROR; };行编辑程序;行编辑程序;Void LineEdit ( ) //行编辑程序 { InitStack(s); ch=getchar(); while (ch != EOF) { //EOF为全文结束符 while (ch != EOF ch != \n ) { switch (ch) { case # : Pop(S, c); break; case @: ClearStack(S); break; // 重置S为空栈 default : Push(S, ch); break; } ch = getchar(); // 从终端接收下一个字符 } 将从栈底到栈顶的字符传送至调用过程的数据区（略）； ClearStack(S); // 重置S为空栈 if (ch != EOF) ch = getchar(); } DestroyStack(s); };迷宫求解;迷宫求解; 为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图所示的迷宫,对应的迷宫数组mg如下: int mg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; ; 下一位置： int movei[4] = {1, 0, -1, 0}; int movej[4] = {0, 1, 0, -1}; 设当前位置为e(i, j)，则e(i, j)的下一位置： i = e.i + movei[e.dir-1]; j = e.j + movej[e.dir-1]; 当前通道块是否可通： if (maze[i][j] ==0) 可通；;从入口到出口的路径算法 设当前位置的初值为入口位置； do{ 若当前位置可通，则 { 将当前位置插入栈顶； 若该位置为出口位置，则结束； 将该位置的东邻块置为当前位置；