数据结构(清华大学)chap3教材课程.pptVIP

第三章;线性表;3.1 栈的类型定义;ADT Stack { }ADT Stack; ClearStack (S) (栈清空);a1;a1;a1;数制转换的原理为： N = (N div d)×d + N mod d;void conversion ( ) { // 显示和输入的十进制数对应的八进制数值 InitStack(S); scanf (%d,N); while (N) { Push(S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(S,e); printf ( %d, e ); } } // conversion;检验含两种括弧的表达式中括弧匹配的正确性。;[ ;算法的设计思想：;bool matching(char exp[], int n) { // 检测长度为 n 的字符序列 exp 中的括弧是否匹配 int i = 0; mat = true; InitStack(S); while ( in mat ) { switch of exp[i] { case 左括弧:{ Push(S,exp[i]); i++; break; } case ? ) ? : { if ( !StackEmpty(S) GetTop(S) == ?(? ) { Pop(S, e); i++; } else {mat = false;} break; } //case ?)? … …;计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。 ;#;#;结论:;求迷宫路径算法的基本思想是：;设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； ｝ 否则 { ｝ ｝while (栈不空）；;若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；;表达式 ::= (操作数) + (运算符) + (操作数) 操作数 ::= 简单变量 | 表达式 简单变量 :: = 标识符 | 无符号整数; 表达式的三种标识方法：;例如: Exp = a ? b + (c ? d / e) ? f 前缀式: + ? a b ? ? c / d e f 中缀式: a ? b + c ? d / e ? f 后缀式: a b ? c d e / ? f ? + ;如何从后缀式求值？; 在后缀式中，优先权高的运算符领先于优先??权的运算符出现。;从原表达式求得后缀式的规律为：;4) 若当前运算符的优先数高于栈顶运算符，则进栈;;a ? ( b ? ( c + d / e ) - f ) #;void transform(char suffix[ ], char exp[ ] ) { InitStack(S); Push(S, ?#?); p = exp; ch = *p; while (!StackEmpty(S)) { if (!IN(ch, OP)) Pass( Suffix, ch); else { } if ( ch!= ?#? ) { p++; ch = *p; } } // while } // CrtExptree;switch (ch) { case ?(? : Push(S, ch); break; case ?)? : Pop(S, c); while (c!= ?(? ) { Pass( Suffix, c); Pop(S, c) }