数据结构复习篇:用栈实现递归

void  TOH( int  n, Pole start, Pole goal, Pole temp) // 把n个圆盘从start柱移到goal柱，temp柱作为辅助柱
{
     if  (n  ==   0 )  return ;     // base case
    TOH(n - 1 , start, temp, goal);     // 把n-1个圆盘从start柱移到temp柱，goal作为此次的辅助柱
    move(start,goal);         // 从start柱移动一块圆盘到goal柱
    TOH(n - 1 , temp, goal, start);     // 把temp柱中的n-1个圆盘移到goal柱
     return ;
}

#include  < iostream >
#include  < conio.h >
#include  " StackInterface.h " // 这个头文件，可以在栈那篇文章中找到，也可以自己用标准库中的stack改一下面的程序即可
using   namespace  std;
/*
现在我们来定义一个栈的元素类：TaskPaper任务纸
由下属B、C对子任务的分解情况，很容易看出，
可以把任务分成两类：
1、移动n-1个圆盘。这说明，这种任务可以继续分解。
2、移动1个圆盘。这说明，这种任务无法再分，可以执行移动操作。
那么，我们可以定义一个枚举类型，这个枚举类型作为栈元素
的一个数据成员，用来指示到底是继续分解，还是作出移动操作。
*/
enum  Flag {toMove, toDecompose}; // 移动、继续分解
enum  Pole {start, goal, temp};     // 柱的三种状态，既然起始柱、目标柱、临时柱（也叫辅助柱）

class  TaskPaper     // 任务纸类，将作为栈的元素类
{
public :
    Flag flg;     // 任务分类
     int  num;         // 任务规模
    Pole A, B, C;     // 三根柱

    TaskPaper( int  n, Pole a, Pole b, Pole c, Flag f)
    {
        flg  =  f;
        num  =  n;
        A  =  a;        
        B  =  b;
        C  =  c;
    }
};

void  TOH( int  n, Pole s, Pole t, Pole g) // 用栈实现的汉诺塔函数
{
    LStack < TaskPaper  *>  stk;
    stk.push( new  TaskPaper(n,s,t,g, toDecompose));     // 上司A放第一张任务纸到办公桌上

    TaskPaper  *  paperPtr;
     long  step = 0 ;
     while  (stk.pop(paperPtr))     // 如果办公桌上有任务纸,就拿最上面的一张来看看
    {
         if  (paperPtr -> flg  ==  toMove  ||  paperPtr -> num  ==   1 )
        {
             ++ step;
             if  (paperPtr -> A  ==  start  &&  paperPtr -> B  ==  goal)
            {
                cout << " 第 " << step << " 步：从A柱移动一个圆盘到B柱。 " << endl;
            }
             else   if  (paperPtr -> A  ==  start  &&  paperPtr -> C  ==  goal)
            {
                cout << " 第 " << step << " 步：从A柱移动一个圆盘到C柱。 " << endl;
            }
             else   if  (paperPtr -> B  ==  start  &&  paperPtr -> A  ==  goal)
            {
                cout << " 第 " << step << " 步：从B柱移动一个圆盘到A柱。 " << endl;
            }
             else   if  (paperPtr -> B  ==  start  &&  paperPtr -> C  ==  goal)
            {
                cout << " 第 " << step << " 步：从B柱移动一个圆盘到C柱。 " << endl;
            }
             else   if  (paperPtr -> C  ==  start  &&  paperPtr -> A  ==  goal)
            {
                cout << " 第 " << step << " 步：从C柱移动一个圆盘到A柱。 " << endl;
            }
             else   if  (paperPtr -> C  ==  start  &&  paperPtr -> B  ==  goal)
            {
                cout << " 第 " << step << " 步：从C柱移动一个圆盘到B柱。 " << endl;
            }
        }
         else
        {
             int  num  =  paperPtr -> num;
            Pole a  =  paperPtr -> A;
            Pole b  =  paperPtr -> B;
            Pole c  =  paperPtr -> C;
            
             if  (a == start  &&  c == goal) 
            {
                 // 书中仅写了这一种情况，而后面的五种的情况被作者大意地认为是相同的，
                 // 于是程序出错了。我估计没有几个人发现这个问题，因为只我这种疑心很重的人，
                 // 才会按照书中的思路写一遍这种程序^_^
                stk.push( new  TaskPaper(num - 1 , b, a, c, toDecompose)); // 子任务执行顺序为3
                stk.push( new  TaskPaper( 1 ,a,b,c,::toMove));     // 子任务中执行顺序为2
                stk.push( new  TaskPaper(num - 1 , a, c, b, toDecompose)); // 子任务中执行顺序为1
            }
             else   if  (a == start  &&  b == goal)
            {
                stk.push( new  TaskPaper(num - 1 , c, b, a, toDecompose)); // 为goal的柱状态不变,其它两根柱的状态互换
                stk.push( new  TaskPaper( 1 ,a,b,c,::toMove));     // 移动操作中,柱的状态不变
                stk.push( new  TaskPaper(num - 1 , a, c, b, toDecompose)); // 为start的柱状态不变,其它两根柱的状态互换
            }
             else   if  (b == start  &&  a == goal)
            {            
                stk.push( new  TaskPaper(num - 1 , a, c, b, toDecompose));
                stk.push( new  TaskPaper( 1 ,a,b,c,::toMove));
                stk.push( new  TaskPaper(num - 1 , c, b, a, toDecompose));
            }
             else   if  (b == start  &&  c == goal)
            {
                
                stk.push( new  TaskPaper(num - 1 , b, a, c, toDecompose));
                stk.push( new  TaskPaper( 1 ,a,b,c,::toMove));
                stk.push( new  TaskPaper(num - 1 , c, b, a, toDecompose));
            }
             else   if  (c == start  &&  a == goal)
            {
                
                stk.push( new  TaskPaper(num - 1 , a, c, b, toDecompose));
                stk.push( new  TaskPaper( 1 ,a,b,c,::toMove));
                stk.push( new  TaskPaper(num - 1 , b, a, c, toDecompose));
            }
             else   if  (c == start  &&  b == goal)
            {
                
                stk.push( new  TaskPaper(num - 1 , c, b, a, toDecompose));
                stk.push( new  TaskPaper( 1 ,a,b,c,::toMove));
                stk.push( new  TaskPaper(num - 1 , b, a, c, toDecompose));
            }

        }

        delete paperPtr;
        
    }
}

void  main()
{
    
    TOH( 3 ,start,temp,goal);        
    getch();

}

/*
这是我个人的头文件，用来定义各种函数
文件名：zyk.h
*/
#ifndef ZYK_H
#define  ZYK_H
#include  < iostream >
#include  < stack >
using   namespace  std;

namespace  zyk
{
     // Fibonacci数列的递归函数
     long  fibr ( int  n);

     // 用栈实现fibr递归
     long  fibr_stack( int  n);
}

long  zyk::fibr( int  n)
{
     if  (n  ==   1   ||  n  ==   2 )
    {  return   1 ;}
    
     return  fibr(n - 1 )  +  fibr(n - 2 );
}

long  zyk::fibr_stack( int  n)
{
     long  val  =   0 ;
    stack < int >  stk;
    stk.push(n);       // 初始化栈

     while  ( ! stk.empty())     // 如果办公桌上不是空的，即有任务纸
    {
         int  nn  =  stk.top();     // 查看这张纸
        stk.pop();             // 拿开这张纸
        
         if  (nn == 1   ||  nn == 2 )
        {
            val  +=   1 ;         // 累加。
        }
         else
        {
            stk.push(nn - 1 );     // 分成两个子任务
            stk.push(nn - 2 );     // 对于这两个子任务，其先后执行顺序是无关紧要的。
        }

    }

     return  val;
}


#endif