| « | September 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | | | | | |
|
| 公告 |
|
My blog is about my major : network security.the most papers are talk about it ,I like my major ,i wish you could find what's you need in it. |
| 统计 |
blog名称:我的IT人生
日志总数:78
评论数量:185
留言数量:-1
访问次数:525654
建立时间:2006年4月5日 |
| 
|
本站首页 管理页面 写新日志 退出
 [C/C++]如何用栈实现递归与非递归的转换（1）（转 GOOD） |
如何用栈实现递归与非递归的转换
http://www.chinaunix.net 作者:converse 发表于：2006-08-24 09:00:06
原文：http://www.chinaunix.net/jh/23/331522.html http://blog.csdn.net/dragondwy/archive/2006/06/30/855391.aspx http://liqunsun.spaces.live.com/blog/cns!285A08B51269F219!114.entry如何用栈实现递归与非递归的转换
一.为什么要学习递归与非递归的转换的实现方法? 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 (!stackempty(S)) { while (gettop(S, p) && p) /* 向左走到尽头 */ push(S, p->;lchild); pop(S,p); /* 空指针退栈 */ if (!stackempty(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; /* 有mark域的结点指针类型 */ void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法 */ { PMType a; initstack(S); /* S的元素为PMType类型 */
push (S,{T,0}); /* 根结点入栈 */ while(!stackempty(S)) { pop(S,a); switch(a.mark) { case 0: push(S,{a.ptr,1}); /* 修改mark域 */ if(a.ptr->;lchild) push(S,{a.ptr->;lchild,0}); /* 访问左子树 */ break; case 1: push(S,{a.ptr,2}); /* 修改mark域 */ if(a.ptr->;rchild) push(S,{a.ptr->;rchild,0}); /* 访问右子树 */ break; case 2: visit(a.ptr); /* 访问结点 */ } } }
4)如何实现递归与非递归的转换 通常,一个函数在调用另一个函数之前,要作如下的事情: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)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的 "叶子结点".
|
阅读全文(1736) | 回复(0) | 编辑 | 精华 |
|
