3-2 漢諾塔的非遞歸實作

　　漢諾塔實作的基本思路是：不斷将n個盤的漢諾塔問題轉換為2個n - 1個盤的漢諾塔問題，一次用遞歸實作是很自然的方法。當吧n盤問題轉換為n -1 個盤的問題時， 問題的起始柱子和目标柱子也發生了變化，設n盤問題為(n, a, b, c)，其中參數如下結構體所定義，則問題求解可轉換為對(n - 1, a, c, b)、(1, a, b, c)、(n - 1, b, a, c)這三個問題的求解，其中(1, a, b, c)不需要遞歸，可直接實作。

　　但是若是用堆棧來實作的話，當将分解出的上述三個問題雅茹堆棧時，應該按照“需要先求解的問題後壓入”的順序，也就是壓入順序為：(n - 1, b, a, c), (1, a, b, c), (n - 1, a, c, b).

1 typedef struct {　　//漢諾塔問題的結構類型
2     int N;
3     char A;        //起始柱
4     char B;        //借助柱
5     char C;        //目标柱
6 
7 }ElementType;    //漢諾塔問題的結構類型           

1 //借助棧的非遞歸實作
 2 void Hanoi(int n)
 3 {
 4     ElementType P, toPush;
 5     Stack S;
 6 
 7     P.N = n; P.A = 'a'; P.B = 'b'; P.C = 'c';
 8     S.top = -1;
 9 
10     Push(&S, P);
11     while (S.top != -1)        //當堆棧不為空時
12     {
13         P = Pop(&S);
14         if (P.N == 1)
15             printf("%c  -> %c\n", P.A, P.C);
16         else
17         {
18             toPush.N = P.N - 1;
19             toPush.A = P.B; toPush.B = P.A; toPush.C = P.C;
20             Push(&S, toPush);        //将第二個待解子問題(n - 1, b, a, c)入棧
21             toPush.N = 1;
22             toPush.A = P.A; toPush.B = P.B; toPush.C = P.C;
23             Push(&S, toPush);        //将可直接求解的子問題(1, a, b, c)入棧
24             toPush.N = P.N - 1;
25             toPush.A = P.A; toPush.B = P.C; toPush.C = P.B;
26             Push(&S, toPush);        //将第一個待解子問題(n - 1, a, c, b)入棧
27         }
28     }
29 }           

下面是棧的實作和主函數：

1 #include <stdio.h>
 2 #define MaxSize 100
 3 
 4 typedef struct {
 5     ElementType Data[MaxSize];
 6     int top;
 7 }Stack;        //堆棧的标準定義
 8 
 9 void Push(Stack *PtrS, ElementType item)
10 {
11     //入棧操作
12     if (PtrS->top == MaxSize)
13     {
14         printf("The stack is full!\n");
15         return;
16     }
17     else
18     {
19         PtrS->Data[++(PtrS->top)] = item;
20         return;
21     }
22 }
23 
24 ElementType Pop(Stack *PtrS)
25 {
26     if (PtrS->top == -1)
27     {
28         printf("The stack is empty!\n");
29         return ERROR;        //ERROR是ElementType的特殊值，标志錯誤
30     }
31     else
32     {
33         PtrS->top--;
34         return (PtrS->Data[PtrS->top + 1]);        //或者是return PtrS->Data[PtrS->top--];
35     }
36 }
37 
38 int main()
39 {
40     int n;
41     ERROR.N = -1;　　　　//ERROR是ElementType的特殊值，标志錯誤
42     scanf_s("%d", &n);
43     Hanoi(n);
44     return 0;
45 }