如何用栈实现递归与非递归的转换
(一)三种遍历树的算法
递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。
一.为什么要学习递归与非递归的转换的实现方法?
1)并不是每一门语言都支持递归的.
2)有助于理解递归的本质.
3)有助于理解栈,树等数据结构.
二.三种遍历树的递归和非递归算法
递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。
1)前序遍历
a)递归方式:
void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ {
if (T) {
visit(T); /* 访问当前结点*/
preorder_recursive(T->lchild); /* 访问左子树*/
preorder_recursive(T->rchild); /* 访问右子树*/
}
}
b)非递归方式
void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法*/
{
initstack(S);
push(S,T); /* 根指针进栈*/
while(!stackempty(S)) {
while(gettop(S,p)&&p) { /* 向左走到尽头*/
visit(p); /* 每向前走一步都访问当前结点*/
push(S,p->lchild);
}
pop(S,p);
if(!stackempty(S)) { /* 向右走一步*/
pop(S,p);
push(S,p->rchild);
}
}
}
2)中序遍历
a)递归方式
void inorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法*/ {
if (T) {
inorder_recursive(T->lchild); /* 访问左子树*/
visit(T); /* 访问当前结点*/
inorder_recursive(T->rchild); /* 访问右子树*/
}
}
b)非递归方式
void inorder_nonrecursive(Bitree T)
{
initstack(S); /* 初始化栈*/
push(S, T); /* 根指针入栈*/
while (!stackem pty(S)) {
while (gettop(S, p) && p) /* 向左走到尽头*/
push(S, p->lchild);
pop(S, p); /* 空指针退栈*/
if (!stackem pty(S)) {
pop(S, p);
visit(p); /* 访问当前结点*/
push(S, p->rchild); /* 向右走一步*/
}
}
}
3)后序遍历
a)递归方式
void postorder_recursive(Bitree T) /* 中序遍历二叉树的递归算法*/ {
if (T) {
postorder_recursive(T->lchild); /* 访问左子树*/
postorder_recursive(T->rchild); /* 访问右子树*/
visit(T); /* 访问当前结点*/
}
}
b)非递归方式
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; /* 有m ark域的结点指针类型*/
void postorder_nonrecursive(BiTree T) /*
后续遍历二叉树的非递归算法*/
{
PMType a;
initstack(S); /* S的元素为PMType类型*/
push (S,{T,0}); /* 根结点入栈*/
while(!stackempty(S)) {
pop(S,a);
switch(a.m ark)
{
case 0:
push(S,{a.ptr,1}); /* 修改m ark域*/
if(a.ptr->lchild)
push(S,{a.ptr->lchild,0}); /* 访问左子树*/
break;
case 1:
push(S,{a.ptr,2}); /* 修改m ark域*/
if(a.ptr->rchild)
push(S,{a.ptr->rchild,0}); /* 访问右子树*/
break;
case 2:
visit(a.ptr); /* 访问结点*/
}
}
}
三.实现递归与非递归的换转原理和例子
一）原理分析
通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口.
从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的.
ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步.
下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式).
下面以先序遍历来说明:
void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/
{
if (T) {
visit(T); /* 访问当前结点*/
preorder_recursive(T->lchild); /* 访问左子树*/
preorder_recursive(T->rchild); /* 访问右子树*/
}
}
visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了.
现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点".
二）.三个例子
好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识.即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以明白(事实上我也是花了两个星期的时间才弄得比较明白得).
1)例子一:
f(n) = n + １; (n <２)
= f[n/2] + f[n/4](n >= 2);
这个例子相对简单一些,递归程序如下:
int f_recursive(int n)
{
int u1, u2, f;
if (n < 2)
f = n + 1;
else {
u1 = f_recursive((int)(n/2));
u2 = f_recursive((int)(n/4));
f = u1 * u2;
}
return f;
}
下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点,我们看到当n < 2时f = n + 1,这就是返回的语句,有人问为什么不是f = u1 * u2,这也是一个返回的语句呀?答案是:这条语句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之后执行的,是这两条语句的父结点. 其次,什么是当前结点,由上面的分析,f = u1 * u2即是父结点
然后,顺理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分别是左子树和右子树了.最后,我们可以看到,这个递归函数可以表示成后序遍历的二叉调用树.好了,树的情况分析到这里,下面来分析一下栈的情况,看看我们要把什么数据保存在栈中：非递归程序中我们已经看到了要加入一个标志域,因此在栈中要保存这个标志域;另
外,u1,u2和每次调用递归函数时的n/2和n/4参数都要保存,这样就要分别有三个栈分别保存:标志域,返回量和参数,不过我们可以做一个优化,因为在向上一层返回的时候,参数已经没有用了,而返回量也只有在向上返回时才用到,因此可以把这两个栈合为一个栈.如果对于上面的分析你
没有明白,建议你根据这个递归函数写出它的递归栈的变化情况以加深理解,再次重申一点:前期对树结构和栈的分析是最重要的,如果你的程序出错,那么请返回到这一步来再次分析,最好把递归调用树和栈的变化情况都画出来,并且结合一些简单的参数来人工分析你的算法到底出错在哪里.
ok,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来的).
代码:
int f_nonrecursive(int n)
{
int stack[20], flag[20], cp;
/* 初始化栈和栈顶指针*/
cp = 0;
stack[0] = n;
flag[0] = 0;
while (cp >= 0) {
switch(flag[cp]) {
case 0: /* 访问的是根结点*/
if (stack[cp] >= 2) { /* 左子树入栈*/
flag[cp] = 1; /* 修改标志域*/
cp++;
stack[cp] = (int)(stack[cp - 1] / 2);
flag[cp] = 0;
} else { /* 否则为叶子结点*/
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 1: /* 访问的是左子树*/
if (stack[cp] >= 2) { /* 右子树入栈*/
flag[cp] = 2; /* 修改标志域*/
cp += 2;
stack[cp] = (int)(stack[cp - 2] / 4);
flag[cp] = 1;
} else { /* 否则为叶子结点*/
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 2: /* */
if (flag[cp - 1] == 2) { /* 当前是右子树吗? */
/*
* 如果是右子树, 那么对某一棵子树的后序遍历已经
* 结束,接下来就是对这棵子树的根结点的访问
*/
stack[cp - 2] = stack[cp] * stack[cp - 1];
flag[cp - 2] = 2;
cp = cp - 2;
} else
/* 否则退回到后序遍历的上一个结点*/
cp--;
break;
}
}
return stack[0];
}
算法分析:a)flag只有三个可能值:0表示第一次访问该结点,1表示访问的是左子树,2表示已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点.b)每遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2;否则根据访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向.
2)例子二
快速排序算法
递归算法如下:
代码:
void swap(int array[], int low, int high)
{
int tem p;
tem p = array[low];
array[low] = array[high];
array[high] = temp;
}
int partition(int array[], int low, int high)
{
int p;
p = array[low];
while (low < high) {
while (low < high && array[high] >= p)
high--;
swap(array,low,high);
while (low < high && array[low] <= p)
low++;
swap(array,low,high);
}
return low;
}
void qsort_recursive(int array[], int low, int high)
int p;
if(low < high) {
p = partition(array, low, high);
qsort_recursive(array, low, p - 1);
qsort_recursive(array, p + 1, high);
}
}
需要说明一下快速排序的算法: partition函数根据数组中的某一个数把数组划分为两个部分,左边的部分均不大于这个数,右边的数均不小于这个数,然后再对左右两边的数组再进行划分.这里我们专注于递归与非递归的转换,partition函数在非递归函数中同样的可以调用(其实partition函数就是对当前结点的访问).
再次进行递归调用树和栈的分析: 递归调用树:a)对当前结点的访问是调用partition函
数;b)左子树:qsort_recursive(array, low, p - 1);c)右子树:qsort_recursive(array, p +1, high); d)叶子结点:当low < high时;e)可以看出这是一个先序调用的二叉树.栈:要保存的数据是两个表示范围的坐标.
代码:
void qsort_nonrecursive(int array[], int low, int high)
{
int m[50], n[50], cp, p;
/* 初始化栈和栈顶指针*/
cp = 0;
m[0] = low;
n[0] = high;
while (m[cp] < n[cp]) {
while (m[cp] < n[cp]) { /* 向左走到尽头*/
p = partition(array, m[cp], n[cp]); /* 对当前结点的访问*/
cp++;
m[cp] = m[cp - 1];
n[cp] = p - 1;
}
/* 向右走一步*/
m[cp + 1] = n[cp] + 2;
n[cp + 1] = n[cp - 1];
cp++;
}
}
3)例子三
阿克曼函数:
代码:
akm(m, n) = n + 1; (m = 0时)
akm(m - 1, 1); (n = 0时)
akm(m - 1, akm(m, n - 1)); (m != 0且n != 0时) 递归算法如下:
int akm_recursive(int m, int n)
{
int tem p;
if (m == 0)
return (n + 1);
else if (n == 0)
return akm_recursive(m - 1, 1);
else {
tem p = akm_recursive(m, n - 1);
return akm_recursive(m - 1, tem p);
}
}
这道题的难点就是确定递归调用树的情况,因为从akm函数的公式可以看到,有三个递归调用,一般而言,有几个递归调用就会有几棵递归调用的子树,不过这只是一般的情况,不一定准确,也不一定非要机械化的这么作,因为通常情况下我们可以做一些优化,省去其中的一些部分,这道题就是一个例子.
递归调用树的分析:a)是当m=0时是叶子结点;b)左子树是akm(m - 1, akm(m, n - 1))调用中的akm(m, n - 1)调用,当这个调用结束得出一个值tem p时,再调用akm(m - 1, tem p),这个调用是右子树.c)从上面的分析可以看出,这个递归调用树是后序遍历的树.
栈的分析:要保存的数据是m, n,当n = 0 或m = 0时开始退栈,当n = 0时把上一层栈的m值变为m - 1,n变为1，当m = 0时把上一层栈的m值变为0,n变为n + 1.从这个分析过程可以看出,我们省略了当n = 0时的akm(m - 1, 1)调用,原来在系统机械化的实现递归调用的过程中,这个调用也是一棵子树,不过经过分析,我们用修改栈中数据的方式进行了改进.
代码:
int akm_nonrecursive(int m, int n)
{
int m1[50], n1[50], cp;
cp = 0;
m1[0] = m;
n1[0] = n;
do {
while (m1[cp] > 0) { /* 压栈, 直到m1[cp] = 0 */
while (n1[cp] > 0) { /* 压栈, 直到n1[cp] = 0 */
cp++;
m1[cp] = m1[cp - 1];
n1[cp] = n1[cp - 1] - 1;
}
/* 计算akm(m - 1, 1),当n = 0时*/
m1[cp] = m1[cp] - 1;
n1[cp] = 1;
}
/* 改栈顶为akm(m - 1, n + 1),当m = 0时*/
cp--;
m1[cp] = m1[cp] - 1;
n1[cp] = n1[cp + 1] + 1;
} while (cp > 0 || m1[cp] > 0);
return n1[0] + 1;
}
五.递归程序的分类及用途
递归程序分为两类:尾部递归和非尾部递归.上面提到的几个例子都是非尾部递归,在一个选择分支中有至少一个的递归调用.相对而言,尾部递归就容易很多了,因为与非尾部递归相比,每个选择分支只有一个递归调用,
我们在解决的时候就不需要使用到栈,只要循环和设置好循环体就可以了.下面再举几个尾部递归的例子吧,比较简单我就不多说什么了.
1)例子一
g(m, n) = 0 (m = 0, n >= 0)
= g(m - 1, 2n) + n; (m > 0, n >= 0)
a)递归程序
int g_recursive(int m, int n)
{
if (m == 0 && n >= 0)
return 0;
return (g_recurse(m - 1, 2*n) + n);
}
b)非递归程序
int g_nonrecursive(int m, int n)
{
int p;
for (p = 0; m > 0 && n >= 0; m--, n *= 2)
p += n;
return p;
}
2)例子二
f(n) = n + 1 (n = 0)
= n * f(n/2) (n > 0)
a)递归程序
int f_recursive(int n)
{
if (n == 0)
return 1;
return (n * f_recurse(n/2));
}
b)非递归程序
int f_nonrecursive(int n)
{
int m;
for (m = 1; n > 0; n /= 2)
m *= n;
return m++;
}
分析完了递归程序的分类,让我们回头看看在向非递归转换的过程中用到了什么来实现转换:
1)循环,因为程序要在某个条件下一直执行下去,要代替递归程序,循环必不可少,对于尾部递归,循环结束的条件十分容易确定,只要按照不同分支的条件写出来就可以了.而对于非尾部递归程序,循环结束的条件一般是当栈为空时或者是结束了对递归调用树的遍历从树的根结点退出时,而且有的时候写成while()的形式,有时写成do ...while的形式(如上面的akm函数),具体怎样,很难说清楚,取决于你对整个递归程序的分析。
2)递归调用树,树的结构在转换的过程中是不可见的,你不必为转换专门写一个树结构,不过能不能把递归调用中的树遍历方式以及叶子结点,左子树,右子树等元素确定好是你能否正确解
决问题的关键(这一点已经在上面的分析过程中展露无疑),确定好这些后,剩下的工作大部分就
是按照给出的几种不同的遍历树的方式把程序进行改写,这个过程就考验你对树结构还有遍历方式是否很好的掌握了(看出基础的重要了吗?如果回答是,那么和我一样好好的打好基础吧,一切
都还不晚!!).对于尾部递归而言,可以看作没有递归调用树,所以尾部递归的难度大大降低了。
3)栈,非尾部调用中需要栈来保存数据,这一点已经很清楚了,需要注意几个问题:a)栈有时
可能会出现不够的情况,拿上面的akm函数来说,我用的50个元素的数组,你如果把m和n值设置得大一些,这个栈就不能用了,有时你的算法正确了,不过没有注意到这个问题还是会出错的;反过来说,在递归调用中,系统或者编译器的优化功能不够好的化,在这个栈上可能会消耗很多空间,这个时候如果你把程序改成非递归的形式,然后再用动态分配技术分配栈可能就会把程序的
性能提高一大块--这也是我们学习这门技术的意义之一,因为系统是机械化的,你如果知道更好
的优化办法,为什么不用呢?
什么时候可以用递归解决问题?到了这一步,如果你对于上面说的已经相当明白的话,这个问题不难回答,如果我们要解决的问题要分成几个小的部分,而其中的一些与你要解决的问题是一
样的,只不过是问题的规模(如参数等)小了,那么这样的问题可以用递归来解决.根据问题设计好一个递归是所有这些的基础,转换也是在原来的递归程序上进行的,所以这一步一定要做好.通常,设计一个递归程序要注意一下几个问题:a)可以递归解决的问题是什么?b)入口和出口参数是什么--即要明确好出入的接口。
说白了，递归程序是在对所要解决的问题进行数学上的分析后给出的，也就是说递归算法是从纯数学的角度出发考虑的，而非递归的算法则是在递归算法的基础上考虑计算机内部处理递归程序的机制考虑来实现转换的。任何一个递归算法，只要能够准确的写出递归调用树的情况，分析清楚对当前结点的访问操作是什么，左子树右子树是什么那么实现起递归和非递归的转换就很轻松了。
六.学习过程中参考到的一些资料
1)<<算法导论>>国防科大出版社张益新沈雁编著
这本书比较老了,也许很难找了,不过参考价值不大,里面专门用了一章来讲这个问题,可惜用的是goto来实现递归调用的选择分支(所以我说参考价值不大),如果没有也无所谓的.
2)https://www.doczj.com/doc/6e14344284.html,/m zhang/ 北京大学张铭老师的主页.
上面可以找到一个张老师讲解递归和非递归转换的视频,有大概50多分钟吧,我没有听完,
原先看第一本书的对于如何不用goto实现选择分支十分不解,张老师讲到的递归调用树真正让我豁然开朗,从此以后虽然还是有很多问题,不过明白了这个大体的解决思路就有了.
3)<<数据结构>>清华大学出版社严蔚敏著
这本书讲到栈的时候略微讲到了一些这方面的内容,网上可以找到一位叫一具的仁兄写的这本书的习题解答,可以自己去找一找,我的中序和后序遍历的算法完全看的他写的.
4) https://www.doczj.com/doc/6e14344284.html,/kfjy/bkjy/jsj/bxk/sjjg/kcdh/忘了是什么的网页了
里面的一个dn5.doc的文件中有讲解转换akm函数的方法,给我的启发很大,如果你对于我说的akm函数还有疑问,那么可以看看人家写的,他把递归调用树和栈的变化情况都写出来了,非常直观.
-------------------
转自：https://www.doczj.com/doc/6e14344284.html,/209803.ht ml
第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。 ①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p 1,p 2 ,p 3 ，…，p N ,若p N 是n，则 p i 是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是
目录 摘要 (1) 研究背景 (2) 基本概念及特性.......................................................... (2) 栈的运算 (3) 栈的运用举例 (5) 递归原理 (6) 迷宫求解 (8) 栈实现迷宫问题 (8) 递归实现迷宫算法 (8) 参考文献 (9) 附录 (9)
栈与递归的关系 摘要：栈（stack）又称堆栈，他是线性表中的一种特殊情况，并且也是最简单的情况之一，它是一种运算受限的线性表，其限制是仅仅允许在表的一端进行插入和删除运算。由于栈的插入和删除运算仅在栈的一端实现，后进栈的元素必定先出栈，所以又把栈称为后进先出表。 递归是一种非常重要的概念和解决问题的方法，在计算机科学和数学领域有着广泛的应用，递归调用是计算机解决部分疑难问题特别有效,易于实现的一种算法。比如著名的汉诺塔问题、八皇后问题、树的遍历等如果不用递归算法解决,几乎难以实现,大部分计算机语言教材都涉及到这一重要算法。在计算机系统内，执行递归函数是通过栈来实现的，栈中的每一个元素包含有递归函数的每一参数域、每一个局部变量和调用后的返回地址域，其中引用参数域只保存传送来的实参的地址，以便按此地址访问实参的储存空间存取其值，其他的每个域是用于存储其值的实际存储空间，每次进行函数调用的时候，都要把相应的填压入栈，每次结束调用时，都按照本次返回地址返回到指定的位置进行，并且自动做一次退栈操作，使得下一层所使用的参数称为新的栈顶，继续被使用。栈与递归都能够解决一些实际问题，主要是通过C/C++语言来实现编程运算，得到相应的结果。 递归和栈是可以相互转换的，当编写递归算法时，虽然表面上没有使用栈，但是系统执行时会自动建立和使用栈，本文中在求解迷宫问题时就充分的体现出了这一点。 关键词：栈递归C/C++语言迷宫问题
递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： int f(int n) {
实验报告 【实验名称】项目一迷宫问题的求解 【实验目的】 1.了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体 的运用。 2.学会用栈或者递归方法解决迷宫问题。 【实验原理】 1.本次实验中，以二维数组maze[row][col]表示迷宫，0表示通路，1表示墙，在构建迷宫时，为了清晰显示，在最外层添加一圈墙。 2.算法的核心思想是利用栈后进先出的特点，对迷宫进行探索，如果此路可行，则将此坐标的信息入栈，如果此路不通，则将此坐标的信息出栈。 3.输入形式：根据控制台的提示，依次输入迷宫的行数、列数，然后输入迷宫，再输入入口和出口坐标。 4.输出形式：由用户选择，由递归、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案，并给出相应的三元组序列和迷宫方阵；以递归方式则会显示出所有的路线。 【实验内容】 1.需求分析 （1）问题描述 以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 要求以递归和非递归两种方式分别输出一条迷宫的通路，以带方向坐标和迷宫图像表示。
（2）基本要求 （1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。 （2）编写递归形式的算法，求得迷宫中所有可能的通路。 （3）以方阵形式输出迷宫及其通路。 2.概要设计 （1）栈的抽象数据类型 ADT Stack{ 数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系：R1={
栈与递归的关系 姓名：郭小兵 学号：1007010210 专业：信息与计算科学院系：理学院 指导老师：彭长根 2012年10月17日
栈与递归的关系 郭小兵 摘要递归是计算机科学中一个极为重要的概念,许多计算机高级语言都具有递归的功能,对于初学计算机者来讲,递归是一个简单易懂的概念,但真正深刻理解递归,正确自如的运用递归编写程序却非易事,本文通过一些实例来阐述递归在计算机内的实现及递归到非递归的转换,也许使读者能加深对递归的理解。 关键词栈递归非递归 引言递归是一种程序设计的方式和思想。计算机在执行递归程序时，是通过栈的调用来实现的。栈，从抽象层面上看，是一种线性的数据结构，这中结构的特点是“先进后出”，即假设有a，b，c三个元素，依次放某个栈式存储空间中，要从该空间中拿到这些元素，那么只能以c、b、a的顺序得到。递归程序是将复杂问题分解为一系列简单的问题，从要解的问题起，逐步分解，并将每步分解得到的问题放入“栈”中，这样栈顶是最后分解得到的最简单的问题，解决了这个问题后，次简单的问题可以得到答案，以此类推。分解问题是进栈（或者说压栈）的过程，解决问题是一个出栈的过程。 科学家对栈与递归都做了很多深入的研究，研究表明“递归算法
和栈都有后进先出这个性质，基本上能用递归完成的算法都可以用栈完成，都是运用后进先出这个性质的”这个性质可用于进制的转换。与汇编程序设计中主程序和子程序之间的链接及信息交换相类似，在高级语言编制的程序中，调用函数和被调用函数之间的链接及信息交换需过栈来进行。递归是计算科学中一个极为重要的概念。许多计算机高级语言都具有递归的功能，本文将通过一些是例来阐述递归在计算机内的实现及递归到非递归的转换，也许能加深对递归的理解。递归是某一事物直接或间接地由自己完成。一个函数直接或间接地调用本身，便构成了函数的递归调用，前者称之为直接递归调用，后者为间接递归调用。递归会使某些看起来不容易解决的问题变得容易解决。特别当一个问题蕴含递归特性且结构比较复杂时，采用递归算法往往要自然、简洁、清晰，写出的程序较为简短。在很多时候，程序结构简单，可读性好甚至比运行时间更重要，所以掌握递归算法也就存在一定的必要性。但许多人，特别是计算机专业低年级和一些初学者，往往觉得递归很难理解。为了更好地掌握他，了解递归过程的操作原理就更有意义了。
实习二栈、队列和递归算法设计-停车场管理 一、需求分析 1.每一组输入数据包括：汽车“到达”或“离去”信息、汽车牌照号码以 及到达或离去的时刻。 2.输出信息：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用。 3.测试数据 设n=2，输入数据为：（‘A’,1,5），（‘A’,2,10），（‘D’,1,15），（‘A’,3,20），（‘A’,4,25），（‘A’,5,30），（‘D’,2,35），（‘D’,4,40），（‘E’,0,0）。其中：‘A’表示到达；‘D’表示离去；‘E’表示输入结束。 4.【选作内容】：两个栈共享空间，思考应开辟数组的空间是多少？ 5.【选作内容】：停放在便道上的汽车也收费，收费标准比停放在停车场的车。 实习二栈、队列和递归算法设计 题目：停车场管理实习时间：2012/10/14 一、需求分析 1.每一组输入数据包括：汽车“到达”或“离去”信息、汽车牌照号码以 及到达或离去的时刻。 2.输出信息：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用。 3.测试数据 设n=2，输入数据为：（‘A’,1,5），（‘A’,2,10），（‘D’,1,15），（‘A’,3,20），（‘A’,4,25），（‘A’,5,30），（‘D’,2,35），（‘D’,4,40），（‘E’,0,0）。其中：‘A’表示到达；‘D’表示离去；‘E’表示输入结束。 4.【选作内容】：两个栈共享空间，思考应开辟数组的空间是多少？ 5.【选作内容】：停放在便道上的汽车也收费，收费标准比停放在停车场的车。 二、设计 二、 1. 设计思想 二、（1）存储结构 以栈模拟停车场，以队列模拟车场外的便道。栈以顺序结构实现，队列以链表结构实现。 不需另设一个栈，栈顶空间临时停放为将要离去的汽车让路而从停车场退出来的汽车，栈用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含三个数据项：汽车的牌照号码停车时刻和进入停车场的时刻。 （2）主要算法基本思想 按照顺序（两栈共享空间）栈和链式队列的基本操作，初始化一个栈和一个队列，若车辆进站，先判断车站是否满，未满就进车站，满了就进过道：若车辆离开，先在站中找到该车辆，再判断队列是否空，若非空则将车从过道进到站中并记录进站的时间；若不进行车辆的进出则终止程序。 2. 设计表示 （1）函数调用关系图
利用栈实现递归参考程序1（Turbo2.0环境）： #define MAXSIZE 100 #include
printf("%d",k); else printf("%c",k+55); } printf("\n"); } main(){ int num; clrscr(); printf("Input a num,-1 to quit:\n"); scanf("%d",&num); while(num!=-1){ trans(num); scanf("%d",&num); } } 参考程序2：（C＋＋/VC环境） #define STACK_INIT_SIZE 100//存储空间初始分配量 #define OVERFLOW -1 #define OK 1 #define STACKINCREMENT 10//存储空间分配增量 #define ERROR 0 #define TRUE 1 #define FALSE 0 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #include "iostream.h" typedef int status; typedef char SElemType; typedef struct{//顺序栈的定义 SElemType *base; SElemType *top; int stacksize; }SqStack; status InitStack(SqStack &S){//构造一个空栈S S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW);//存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }
通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口. 从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的. ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步. 下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式). 下面以先序遍历来说明: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->lchild)就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点".
第三章栈和队列 一选择题 1. 对于栈操作数据的原则是（B ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ①B ),在作退栈运算时应先判别栈是否( ②A )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③B )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ D )分别设在这片内存空间的两端,这样,当( ⑤C )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。 A. 不确定 B. n-i+1 C. i D. n-i 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( D )。 A. i B. n-i C. n-i+1 D. 不确定
6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（C ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 7. 设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 9. 设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D ）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 11. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（D ）。 A．fedcba B. bcafed C. dcefba D. cabdef 12. 设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( C )。 A．XYZ B. YZX C. ZXY D. ZYX 13. 输入序列为ABC，可以变为CBA时，经过的栈操作为（B ） A.push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C.push,push,pop,pop,push,pop D.push,pop,push,push,pop,pop 15. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（B ）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D.top[1]=top[2]
递归算法实验报告 篇一：递归算法的设计和实现的实验报告 班级学号姓名实验组别试验日期室温报告日期成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等） 实验名称：递归算法的设计和应用 实验目的： 1. 掌握递归算法的实现。 2. 实现递归算法的应用。 实验环境（硬/软件要求）： Windows XX, Visual C++ 6.0 实验内容： 用递归算法实现前n个自然数的累加和与平均数【C语言源程序】 #include int Digui(int n)//设计递归算法功能为求前n个整数的和// { if(n==0) return 0; if(n==1) return 1;
else return Digui(n-1)+n; } int main() { int n; printf("请输入n的值：\n"); scanf("%d",&n); printf("计算结果为：\n%d\n",Digui(n)); printf("这n个数的平均数是：\n%f\n",(float)Digui(n)/n); } 篇二：数据结构- 递归算法实验报告 实验报告 实验五递归算法 实验目的： 1.熟悉递归算法的实现过程及实现机理； 2.熟练并掌握递归算法的设计方法； 3.了解递归算法到非递归算法的转换。 实验原理： 高级程序语言函数调用原理； 递归算法的设计方法。 实验内容：
6-14 折半查找问题。折半查找问题的描述见6.1节，折半查找问题的递归算法见例6-2。要求： （1）设计折半查找问题的循环结构算法； （2）设计一个查找成功的例子和一个查找不成功的例子，并设计测试主程序； （3）设计一个包含10000个数据元素的查找成功的例子，然后分别调用循环结构的查找算法和递归结构的查找算法，并测试出两种算法在计算机上的实际运行时间。 实验结果： （1）折半查找问题的循环结构算法程序为： int Csearch(int test[],int x,int low,int high) { int i; for( i=0;i { if(x==test[i]) return i; else if(x>test[i])low=i+1; else high=i-1; } if(i>=high) return -1; } （2）①查找成功的例子： #include
第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是（A ）。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示，则栈ST 为空的条件是（ B ） A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时，则执行（ C ） A、HS->next=s; B、s->next=HS->next；HS->next=s; C、s->next=HS；HS=s; D、s->next=HS；HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行（ C） A 、x=HS；HS=HS->next; B 、HS=HS->next；x=HS->data; C 、x=HS->data；HS=HS->next; D 、s->next=Hs；Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为（ B ） A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-（B+C/D）*E 的后缀形式是（ D ） A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1，2，3，4，则队列的输出序列是（ B ） A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为空的条件是（） A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值，已知其头尾指针分别是front 和rear，则判定此循环队 列为满的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列，且当前rear 和front 的值分别为0 和3，当从队列中删除一个元素， 再加入两个元素后，rear 和front 的值分别为（） A、1，5 B、2, 4 C、4，2 D、5，1 11.用单链表表示的链式队列的队头在链表的（）位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q（最多元素为n 个）为空的条件是（） A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中，插入s 所指结点需顺序执行的指令是（） A 、Q.front->next=s；f=s; B 、Q.rear->next=s；Q.rear=s; C 、s->next=Q.rear；Q.rear=s; D 、s->next=Q.front；Q.front=s; 14.在一个链队列Q 中，删除一个结点需要执行的指令是（） A、Q.rear=Q.front->next; B、Q.rear->next=Q.rear->next->next; C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next;
汉诺塔C递归算法详细解答 程序如下： void move(char x,char y){ printf("%c-->%c\n",x,y); } void hanoi(intn,charone,chartwo,char three){ /*将n个盘从one座借助two座，移到three座*/ if(n==1) move(one,three); else{ hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three); } } main(){ int n; printf("input the number of diskes:"); scanf("%d",&n); printf("The step to moving %3d diskes:\n",n); hanoi(n,'A','B','C'); } Hanoi塔问题, 算法分析如下，设A上有n个盘子。 如果n=1，则将圆盘从A直接移动到C。 如果n=2，则： （1）将A上的n-1（等于1）个圆盘移到B上； （2）再将A上的一个圆盘移到C上； （3）最后将B上的n-1（等于1）个圆盘移到C上。 如果n=3，则： A）将A上的n-1（等于2，令其为n`）个圆盘移到B（借助于C），步骤如下：（1）将A上的n`-1（等于1）个圆盘移到C上。 （2）将A上的一个圆盘移到B。 （3）将C上的n`-1（等于1）个圆盘移到B。 B）将A上的一个圆盘移到C。 C）将B上的n-1（等于2，令其为n`）个圆盘移到C（借助A），步骤如下：（1）将B上的n`-1（等于1）个圆盘移到A。 （2）将B上的一个盘子移到C。 （3）将A上的n`-1（等于1）个圆盘移到C。到此，完成了三个圆盘的移动过程。
如何用栈实现递归与非递归的转换 (一)三种遍历树的算法 递归与非递归转换的基础知识是能够正确理解三种树的遍历方法：前序，中序和后序，第一篇就是关于这三种遍历方法的递归和非递归算法。 一.为什么要学习递归与非递归的转换的实现方法? 1)并不是每一门语言都支持递归的. 2)有助于理解递归的本质. 3)有助于理解栈,树等数据结构. 二.三种遍历树的递归和非递归算法 递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。 1)前序遍历 a)递归方式: void preorder_recursive(Bitree T) /* 先序遍历二叉树的递归算法*/ { if (T) { visit(T); /* 访问当前结点*/ preorder_recursive(T->lchild); /* 访问左子树*/ preorder_recursive(T->rchild); /* 访问右子树*/ } } b)非递归方式 void preorder_nonrecursive(Bitree T) /* 先序遍历二叉树的非递归算法*/ { initstack(S); push(S,T); /* 根指针进栈*/ while(!stackempty(S)) { while(gettop(S,p)&&p) { /* 向左走到尽头*/ visit(p); /* 每向前走一步都访问当前结点*/ push(S,p->lchild); } pop(S,p); if(!stackempty(S)) { /* 向右走一步*/ pop(S,p); push(S,p->rchild); }
第3章栈和队列习题练习答案 3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)? (2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。 (3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答： (1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做 Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。 (3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是： 1423,2413,3124,3142,3412,4123,4132,4213,4231,4312 3.2 链栈中为何不设置头结点? 答： 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 3.3 循环队列的优点是什么? 如何判别它的空和满? 答： 循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 3.4设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答： 当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。
选择题： 1、设abcdef 以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ D ）。 A．fedcba B. bcafed C. dcefba D. cabdef 2、若已知一个栈的入栈序列是 1,2,3,…,n，其输出序列为 p1,p2,p3，…，pN,若pN 是 n，则 pi 是( D )。 A. i B. n-i C. n-i+1 D. 不确定 3、设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 4、用链接方式存储的队列，在进行删除运算时（ D ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 5、递归过程或函数调用时，处理参数及返回地址，要用一种称为（ C ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 6、假设以数组 A[m]存放循环队列的元素,其头尾指针分别为 front 和rear，则当前队列中的元素个数为（ A ）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 7、若用一个大小为 6的数组来实现循环队列，且当前 rear和 front 的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？( B ) A. 1 和 5 B. 2 和4 C. 4 和2 D. 5 和1 8、最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是（ A ）。 A. (rear+1) MOD n=front B. rear=front C．rear+1=front D. (rear-l) MOD n=front 9、栈和队列的共同点是（ C ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 10、设栈S和队列 Q 的初始状态为空，元素 e1，e2，e3，e4,e5 和e6 依次通过栈 S，一个元素出栈后即进队列 Q，若 6 个元素出队的序列是 e2，e4，e3,e6,e5,e1 则栈 S 的容量至少应该是( C )。 A． 6 B. 4 C. 3 D. 2 判断题： 栈和队列都是限制存取点的线性结构。（） 消除递归不一定需要使用栈，此说法（） 任何一个递归过程都可以转换成非递归过程。（） 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（）
1-1 通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。(2分) T F 作者: DS课程组 单位: 浙江大学 1-2 在用数组表示的循环队列中，front值一定小于等于rear值。(1分) T F 作者: DS课程组 单位: 浙江大学 1-3 若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。(2分) T F 作者: 徐镜春 单位: 浙江大学 1-4 If keys are pushed onto a stack in the order {1, 2, 3, 4, 5}, then it is impossible to obtain the output sequence {3, 4, 1, 2, 5}. (2分) T F 作者: 徐镜春 单位: 浙江大学 1-5 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。(1分) T F 作者: DS课程组 单位: 浙江大学 1-6 An algorithm to check for balancing symbols in an expression uses a stack to store the symbols. (1分) T F 2-1 设栈S和队列Q的初始状态均为空，元素a、b、c、d、e、f、g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b、d、c、f、e、a、g，则栈S的容量至少是：(2分)
1. 1 2. 2 3. 3 4. 4 作者: DS课程组 单位: 浙江大学 2-2 若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是？(2分) 1. b c a e f d 2. c b d a e f 3. d c e b f a 4. a f e d c b 作者: DS课程组 单位: 浙江大学 2-3 设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？(2分) 1. 3 2 1 5 4 2. 5 1 2 3 4 3. 4 5 1 3 2 4. 4 3 1 2 5
数据结构教案 第三章栈和队列
目录 3.1栈的基本概念 (2) 3.1.1 栈的抽象数据类型定义 (2) 3.1.2 顺序栈 (2) 3.1.3 链栈 (4) 3.2栈的应用 (4) 3.2.1 数制转换：将十进制数N转换成其他d进制数 (4) 3.2.2 括号匹配的检验 (4) 3.2.3 行输入处理程序 (4) 3.2.4 迷宫求解 (5) 3.2.5 表达式求值 (5) 3.3栈与递归的实现 (6) 3.4队列的基本概念 (6) 3.4.1 队列的抽象数据类型定义 (6) 3.4.2 链队列 (7) 3.4.3 循环队列 (8) 3.5队列与栈的应用 (8) 3.5.1 离散事件模拟 (8)
第3章栈和队列 3.1 栈的基本概念 3.1.1 栈的抽象数据类型定义 1、栈的逻辑特征 1）限定在表尾进行插入或删除操作的线性表； 2）栈顶——表尾端；栈底——表头端 3）后进先出的线性表 2、抽象数据类型的定义 ADT Stack{ 数据对象：D={a i |a i∈ElemSet, i=1,2,…,n, n≥0} 数据关系：R={R1},R1={|a i-1,a i∈D, i=2,3,…,n } 基本操作： InitStack( &S ) 操作结果：构造一个空的栈S DestroyStack( &S ) 初始条件：栈S已存在 操作结果：销毁栈S ClearStack( &S ) 初始条件：栈S已存在 操作结果：将栈S重置为空栈 StackEmpty( S ) 初始条件：栈S已存在 操作结果：若S为空栈，则返回TRUE，否则返回FALSE StackLength( S ) 初始条件：栈S已存在 操作结果：返回栈S中数据元素的个数 GetTop( S, &e ) 初始条件：栈S已存在且非空 操作结果：用e返回S中栈顶元素 Push( &S, e ) 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素 Pop( &S, &e ) 初始条件：栈S已存在且非空 操作结果：删除S的栈顶元素，并用e返回其值 StackTraverse( S, visit( ) ) 初始条件：栈S已存在且非空 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit( )。一 旦visit( )失败，则操作失败 }ADT Stack 思考：栈的取元素、插入、删除操作与线性表的相应操作有何区别，为什么？ 3.1.2 顺序栈