《数据结构》-栈的应用举例

3.1 栈,3.2 栈的应用举例,3.3 栈与递归的实现,3.4 队列,第三章 栈和队列,3.2.1 数制转换,3.2 栈的应用举例,十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理： N = ( N div d ) d + N mod d （其中：div为整除运算，mod为求余运算）,例如：(1348)10(2504)8，其运算过程如下：NN div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若计算过程中得到八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。,算法3.1如下： 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,3.2.2 括号匹配检验,假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即( ( )或( ) 等为正确的格式， ( )或 ( ) )或( ( ) )均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如： ( ) 1234 567 8,当计算机接受了第一个括号后,它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号“”只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号”)”的出现,类似的,因等来的是第三个括号“”，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，依次类推。可见，这个处理过程恰与栈的特点相吻合。由此，在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的栈中的所有未消解的期待的急迫性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余,Status matching(string .,3.2.3 行编辑程序,功能：接受用户从终端输入的程序或数据，并存入用户的数据区。退格符“#”：表示前一个字符无效。退行符“”：表示当前行中的字符均无效。,例如： whli # # ilr # e(s # *s)outchaputchar (*s = # +); 等效为： while (* s)putchar (*s +);,为了提高程序的效率，我们设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。在此，将这个输入缓冲区设为一个栈结构，每当从终端接受了一个字符之后先作如下判断：,如果它既不是退格符也不是退行符，则将该字符 压入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将字符栈清为空栈。,void LineEdit /利用字符栈S，从终端接收一行并传送至调用过程的数据区。InitStack (S);/构造空栈Sch = getchar ();/从终端接收第一个字符while (ch != EOF) /EOF为全文结束符while (ch != EOF /LineEdit,算法3.2如下：,3.2.4 迷宫求解,入口,图3.4 迷宫,0 1 2 3 4 5 6 7 8 9,出口,空白方块：表示通道。带阴影线的方块：表示墙。,当前位置：指在搜索过程中某一时刻所在图中某个方块位置。,下一位置：指“当前位置”四周4个方向（东、南、西、北） 上相邻的方块。,当前位置可通：指未曾走到过的通道块。即要求该方块位置不仅 是通道块，而且既不在当前路径上，也不是曾经 纳入过路径的通道块。,求迷宫中一条从入口到出口的路径的算法可简单描述如下：,设定当前位置的初值为入口位置；do 若当前位置可通， 则 将当前位置插入栈顶；/纳入路径 若该位置是出口位置，则结束；/求得路径存放在栈中 否则切换当前位置的相邻方块为新的当前位置； 否则， 若栈不空且栈顶位置尚有其他方向未经探索，则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/从路径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while(栈不空)；,typedef struct int ord;/通道块在路径上的“序号”PosTypeseat;/通道块在迷宫中的“坐标位置”intdi;/从此通道块走向下一通道块的“方向”SElemType；/栈的元素类型Status MazePath (MazeType maze, PosType start, PosType end) /若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中 /（从栈底到栈顶），并返回TRUE，否则返回FALSEInitStack (S);curpos = start;/设定“当前位置”为“入口地址”curstep = 1;/探索第一步do if (Pass (curpos) /当前位置可以通过，即是未曾走到过的通道块 FootPrint (curpos);/留下足迹 e = (curstep, curpos, 1);Push (S, e);/加入路径if (curpos = = end) return (TRUE);/到达终点（出口）curpos = NextPos (curpos, 1);/下一位置是当前位置的东阾curstep+;/探索下一步 /if,算法3.3如下：,else /当前位置不能通过 if (!StackEmpty (S) Pop (S, e);while (e.di = = 4 / MazePath,表达式求值,要对算术表达式求值：4+2*3-10/5,任何一个表达式都是由操作数、运算符和界限符组成的。,实现运算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是： （1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素； （2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直到整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）,3.2.5 表达式求值,算法3.4如下： OperandType EvaluateExpression ( ) /算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和/运算数栈，OP为运算符集合。InitStack (OPTR);Push (OPTR, #);InitStack (OPND);c = getchar ( );while (c != # | | GetTop(OPTR) != #) if (!In (c, OP) /不是运算符则进栈 Push (OPND, c); c = getchar ( );,else switch (Precede (GetTop (OPTR), c) / Precede是判定运算符栈的栈顶运算符 与读入/的运算符 之间优先关系的函数。,case :/退栈并将运算结果入栈Pop (OPTR, theta);Pop (OPND, b);Pop (OPND, a);Push (OPND, Operate (a, theta, b);/ Operate为进行二元运算ab的函数。break; / switch / while return GetTop (OPND); / EvaluateExpression,例如：利用上述算法对表达式3*(72)求值的操作过程如下所示：,步骤OPTR栈 OPND栈输入字符 主要操作,1 #3*(7-2) # Push (OPND, 3) 2 # 3 *(7-2) # Push (OPTR, *) 3 #* 3 (7-2) # Push (OPTR, () 4 #*( 3 7-2) # Push (OPND, 7) 5 #*( 3 7 -2) # Push (OPTR, -) 6 #*( - 3 7 2) # Push (OPND, 2) 7 #*( - 3 7 2 ) # operate (7, -, 2) 8 #*( 3 5 ) # Pop (OPTR) 消去一对括号 9 #* 3 5 # operate (3, *, 5) 10 # 15 # return (GetTop(OPND),一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。 递归是程序设计中一个强有力的工具。其一，有很多数学函数是递归定义的；其二，有的数据结构，如二叉树等，由于结构本身固有的递归特性，则它们的操作可递归地描述；其三，如Hanoi塔问题等。,3.3 栈与递归的实现,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。,从被调用函数返回调用函数之前，应该完成下列三项任务：,保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。,多个函数嵌套调用时，按照“后调用先返回”的原则进行。,int main() int m,n; . first(m,n);1: ,int first(int s, int t) int i; second(i);2: ,int second(int d) intx,y;3: ,此时的内存管理实行“栈式管理”,int main()int m,n;.int i;int x,y;3: 2: 1: ,函数嵌套调用过程示例,递归工作栈：递归过程执行过程中占用的 数据区。递归工作记录：每一层的递归参数合成 一个记录。当前活动记录：栈顶记录指示当前层的 执行情况。当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用，例如：,(n阶Hanoi塔问题）假设有三个分别命名为X、Y、和Z的塔座，在塔座上插有n个大小各有相同、依小到大编号为1、2、n的圆盘。,void hanoi (int n, char x, char y, c