数据结构：栈应用_求解汉诺塔(Hanoi)2

/************************************************************************/

/* 数据结构：栈应用：汉诺塔(Hanoi)问题                                                           */

/* 挑灯看剑[e-mail] 2010-10                                                                   */

/* 云歌国际（Cloud Singers International） www.cocoral.com                              */

/************************************************************************/

//参见版面《数据结构：栈应用_求解汉诺塔(Hanoi)1》

 

//循环函数：将from中的前n-1个元素通过tmp搬运到to中

void recursion(int n, StackPointer from, StackPointer tmp, StackPointer to,

       int* cnt)

{

       static       void move(StackPointer a, StackPointer b, int* cnt);

       if (n == 1)

       {

              move(from, to, cnt);

       }

       else

       {

              recursion(n - 1, from, to, tmp, cnt); //将from中的前n-1个盘子搬运到tmp中，to作辅助塔

              move(from, to, cnt);

              recursion(n - 1, tmp, from, to, cnt); //将tmp中的前n-1个盘子搬运到to中，from作辅助塔

       }

}

 

static void move(StackPointer a, StackPointer b, int* cnt)

{

       Node rtnN =

       {

              0, NULL, NULL

       };

       NodePointer N = &rtnN;

       StackOut(a, N);

       StackIn(b, N->data);

       *cnt += 1; //统计搬运次数

}

 

运行测试结果如下：

--------------------------------

汉诺塔：搬运前 A塔 盘子情况：

栈长度：4

打印结点信息（栈顶到栈底）：

Node[4] = 1

Node[3] = 2

Node[2] = 3

Node[1] = 4

 

B塔 盘子情况：

栈长度：0

打印失败！栈为空！

 

C塔 盘子情况：

栈长度：0

打印失败！栈为空！

--------------------------------

--------------------------------

汉诺塔：搬运后 A塔 盘子情况：

栈长度：0

打印失败！栈为空！

 

B塔 盘子情况：

栈长度：0

打印失败！栈为空！

 

C塔 盘子情况：

栈长度：4

打印结点信息（栈顶到栈底）：

Node[4] = 1

Node[3] = 2

Node[2] = 3

Node[1] = 4

--------------------------------

搬运次数合计：15

 

Press any key to continue