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 ", 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! "); 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! "); 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 }