关于低归的转化问题

我想说说低归转化为非低归的一般方法。我个人觉得低归是程序设计的一个难点。尽管当时学了编译原理，个人认为已经是懂得程序执行整个过程（其实也就是活动记录的变化），但还是碰到低归的转化就有点蒙了。下面是个比较一般的例子：
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( &current_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( &current_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);
       }
}

上面都是仅仅通过原程序改编，不用理解程序意思就可以做。

上面几个都没考虑对低归函数的返回信息进行怎样处理，但是大多数低归函数都有返回信息（象KMWang的排序），这就让简单的一段处理代码的信息还不够，因为还在进行代码处理时候还有前面处理的函数的返回信息，这就要要求在低归函数返回的时候把返回信息放在栈中代码标志部分以便代码部分进行处理（如果只用一个栈的话）。但是在进行栈顶处理并返回的时候，代码标志部分一般都还栈的中间位置，这不怎么好进行返回信息的插入，并且在一个栈中放这么一堆标志信息搞的真就是个活动记录了，搞的栈有点不纯，也复杂了。 我想一般可以用两个栈来完成这样一个工作。一个是用来处理低归，一个用来放返回信息。
现在就以KMWang的排序来说明一下：

List ListSorting(List list)
{
       Push( stack_sorting,list );
       while( !StackIsEmpty( stack_sorting ) ){
            Pop( stack_sorting,&head );
            if( !head ){ //说明此时上一次二分排序的前后两条链都排序完成，并且两个链头接点都在sorted栈顶。
                 Pop( stack_sorted,&head );
                 Pop( stack_sorted,&mid );
                 Push( stack_sorted,ListMerge( head,mid ) ); //把新的归并头放到此栈里。
                 continue;
            }

            l1 = mid = head;
            while ((mid = mid->next) != NULL){
                 if ((mid = mid->next) == NULL) break;
                 l1 = l1->next;
            }
            mid = l1->next;
            l1->next = NULL;

            if( !mid ){
                 Push( stack_sorted,head ); //说明此时就一个接点了，不用低归排序了,放到已排序好的栈里。
                 continue;
            }

            Push( stack_sorting,NULL ); //放一个标志位。
            Push( stack_sorting,mid );
            Push( stack_sorting,head );
       }
       Pop( stack_sorted,&list );
       return list;
}

以上仅供参考，望建议。 --------------------   Optimistic is my color
　 We spend our time on something from dawn to dark
   Day in and day out
　 Sun rise and down　
　 Make an own goal to confront life　
   Self-discovery is the first step toward self-appreciation
   成功只会降临在自认为会成功的人身上