Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 递归转化为非递归的一般方法
发信站: 哈工大紫丁香 (2002年08月31日15:45:46 星期六), 站内信件

较一般的例子：
void hades( canshu_0 )
{
    code_0; //表示进入程序要做的代码。
    if( ... ) hades( canshu_1 ); //按条件进入低归。
    code_1; //用tag_1表示要执行的代码编号。
    if( ... ) hades( canshu_2 );
    code_2;
    if( ... ) hades( canshu_3 );
    ......
}
其实要把这个低归函数非低归化，我们可以不知道其代码本身是干什么，就可以改造了
。其方法类似编译里面的活动记录的方式，具体做法是用些特别的符号来模拟一个函数
放在栈中（类似活动记录功能）：
void hades( canshu_0 )
{
    Push( canshu_0 );
    while( !StackIsEmpty( stack ) )
    {
        Pop( &canshu );
        if(canshu == tag_1 )
        {
            Exe code_1; //执行code_1的代码；
            continue;
        }
        if( canshu == tag_2 )
        {
            Exe code_2; //执行code_2的代码；
            continue;
        }
        //否则说明当前要处理的是一个低归函数部分。
        code_0;
        if( ... ) Push( canshu_3 );
        Push( tag_2 );
        if( ... ) Push( canshu_2 );
        Push( tag_1 );
        if( ... ) Push( canshu_1 );
    }
}
这关键是就是要处理放代码信息和参数信息怎样放在一个栈里面的问题。这就要具体问
题具体分析了。
现在就用上面的方法来解决一下我们碰到的常见问题（树的边里和喊若塔）
void InOrder(Tree tree) //中序
{
    if( tree ) Push( tree,0 );
    while( !StackIsEmpty( stack ) )
    {
        Pop( ¤t_node,&tag );
        if( tag )
        { // 说明现在栈顶的元素是个要打印的接点，不再是低归子树了。
            visit( current_node );
            continue;
        }
        if( current_node->right ) Push( current_node->right,0 );
        Push( current_node,1 ); //压入要处理代码信息。
        if( current_node->left ) Push( current_node->left,0 );
    }
}
void LastOrder(Tree tree) //后序
{
    if( tree ) Push( tree,0 );
    while( !StackIsEmpty( stack ) )
    {
        Pop( ¤t_node,&tag );
        if( tag )
        { // 说明现在栈顶的元素是个要打印的接点，不再是低归子树了。
            visit( current_node );
            continue;
        }
        if( current_node->right ) Push( current_node->right,0 )；
        if( current_node->left ) Push( current_node->left,0 );
        Push( current_node,1 ); //压入要处理代码信息。
    }
}
前序由于是个尾低归，就不用放标志了。和上面类似。
void Hanoi(int n,int first,int second,int third) //喊若塔
{
    Push( n,first,second,third,0 ); //后面加了个标志，用来记录什么时候该进行打印
了。
    while( !StackIsEmpty( stack ) )
    {
        Pop( &n,&first,&second,&third,&tag );
        if( tag ) printf("%d-->%d ",second,third); //注意为什么是打印这两个接点。
        if( n==1 )
        {
            printf("%d-->%d ",first,third);
            continue;
        }
        Push( n-1,second,first,third,1);
        Push( n-1,first,third,second,0);
    }
}


※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 218.7.32.163]
--
※ 修改:·Lerry 於 08月31日16:02:06 修改本文·[FROM: 218.7.32.163]