栈与队列的应用举例.pptVIP

栈的应用举例 由于栈的“后进先出”特点，在很多实际问题中都利用栈做一个辅助的数据结构来进行求解，下面通过几个例子进行说明。 【算法1-1】数制转换算法1 typedef int DataType; void conversion(int N,int r) { SeqStack s; /*定义一个顺序栈*/ datetype x; Init_SeqStack(s); while (N) { Push_SeqStack(s,N%r); /*余数入栈 */ N=N/r; /*商作为被除数继续 */ } while (!Empty_SeqStack(s)) /*余数按顺序出栈*/ { Pop_SeqStack(s,x); printf (%d,x ); } printf (\n ); } 算法1 是将对栈的操作抽象为模块调用，使问题的层次更加清楚。 算法2中直接用int数组s和int 变量top作为一个栈来使用。 往往初学者将栈视为一个很复杂的东西，不知道如何使用，通过这个例子可以消除栈的“神秘”性，当应用程序中需要使用与数据保存顺序相反的数据时，就要想到栈。 通常用顺序栈较多。 例3 表达式求值 队列应用举例 例4 设计一个算法找一条从迷宫入口到出口的最短路径。 算法的基本思想为：从迷宫入口点（1,1）出发，向四周有哪些信誉好的足球投注网站，记下所有一步能到达的坐标点；然后依次再从这些点出发，再记下所有一步能到达的坐标点，…，依此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿有哪些信誉好的足球投注网站路径回溯直至入口。这样就找到了一条迷宫的最短路径，否则迷宫无路径。 * 例 1 简单应用：数制转换问题 将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3467，r=8为例转换方法如下： N N / 8 （整除） N % 8（求余） 3467 433 3 低 433 54 1 54 6 6 6 0 6 高 所以：（3467）10 =（6613）8 将得到的余数一次放入栈中。 算法思想如下： 当N0时重复(1)，(2) (1) 若 N≠0，则将N % r 压入栈s中 ，执行(2); 若N=0，将栈s的内容依次出栈，算法结束。 (2) 用N / r 代替 N。 【算法1-2】数制转换算法2 void conversion(int N,int r) { int s[L],top; /*定义一个顺序栈*/ int x; top=-1; /*初始化栈*/ while (N) { s[++top]=N%r; /*余数入栈*/ N=N/r; /*商作为被除数继*/ } while (top!=-1) /*余数按顺序出栈 */ { x=s[top--]; printf (%d,x ); } printf (\n ); } 例 2 利用栈实现迷宫的求解。 问题：这是实验心理学中一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。 求解思想：采用回溯法。回溯法是一种不断试探且及时纠正错误的有哪些信誉好的足球投注网站方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。 ⒈表示迷宫的数据结构 设迷宫为m行n列，利用maze[m][n]来表示一个迷宫。 maze[i][j]=0 或 1，其中：