(4)出栈 t LinkStack Pop_Link Stack(Link Stack top, datatype *x) i StackNode*p if(top==NULL return NULL else i*x=top->data p =top top- top-next; free(p); return top 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 16 ⑷出栈 LinkStack Pop_LinkStack(LinkStack top, datatype *x) { StackNode *p; if (top= =NULL) return NULL; else { *x = top->data; p = top; top = top->next; free (p); return top; } }
3.2栈的应用举例 由于的“后进先出”特点,在 很多实际问题中都利用栈做一个辅助的 数据结构来进行求解,下面通过几个例 子进行说明。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 17 3.2 栈的应用举例 由于栈的“后进先出”特点，在 很多实际问题中都利用栈做一个辅助的 数据结构来进行求解，下面通过几个例 子进行说明
例31简单应用:数制转换问题 将十进制数N转换为进制的数,其转换方法利用辗转 相除法:以N=3467,r=8为例转换方法如下: NN/8(整除)N%8(求余) 3467 433 低 433 4 546 6 6 所以:(3467)10=(6613)8 我们看到所转换的8进制数按底位到高位的顺序产生 的,而通常的输出是从高位到低位的,恰好与计算过程 相反,因此转换过程中每得到一位8进制数则进栈保存, 转换完毕后依次出栈则正好是转换结果。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 18 例 3.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 我们看到所转换的8进制数按底位到高位的顺序产生 的，而通常的输出是从高位到低位的，恰好与计算过程 相反，因此转换过程中每得到一位8进制数则进栈保存， 转换完毕后依次出栈则正好是转换结果
算法思想如下:当N>0时重复1,2 1.若N≠0,则将N%r压入栈s中,执行2;若N=0,将栈s的内容依次出栈, 算法结束。 2.用N/r代替N pede int datatype void conversion(int N, int r) i SeqStack S datatype X, Init Seqstack( &s) while (n i Push Seqstack(&s, N%r); NEN/r: while(empty Seqstack(& s)) Pop seqstack(&s,&x) printf(“%od”,x);} 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 19 算法思想如下：当N>0时重复1，2 1. 若 N≠0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈， 算法结束。 2. 用N / r 代替 N 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) ; } }
例3.2利用栈实现迷宫的求解。 问题:这是实验心理学中的一个经典问题,心理学家把 老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置 很多隔壁,对前进方向形成了多处障碍,心理学家在迷宫的 唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以 到达出口。 求解思想:采用回溯法。回溯法是一种不断试探且及时纠正 错误的搜索方法。从入口出发,按某一方向向前探索,若能 走通(未走过的),即某处可以到达,则到达新点,否则试 探下一方向;若所有的方向均没有通路,则沿原路返回前一点 ,换下一个方向再继续试探,直到所有可能的通路都探索到 ,或找到一条通路,或无路可走又返回到入口点。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 20 例 3.2 利用栈实现迷宫的求解。 问题：这是实验心理学中的一个经典问题，心理学家把一只 老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置 很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的 唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以 到达出口。 求解思想：采用回溯法。回溯法是一种不断试探且及时纠正 错误的搜索方法。从入口出发，按某一方向向前探索，若能 走通（未走过的），即某处可以到达，则到达新点，否则试 探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点 ，换下一个方向再继续试探，直到所有可能的通路都探索到 ，或找到一条通路，或无路可走又返回到入口点