汉诺塔递归思维
汉诺塔比较经典的实现是利用递归，但也可以利用堆栈。
题意理解：有A,B,C三个柱子，将A柱子上的N个盘子（从大到小排列）移到C柱子上，每次只允许移动一个盘子，并且保证每个柱子上的盘子的排列都是从大到小。
1、递归实现
假设只有一个盘子，那么只需实现 A->C 这个动作；
如果有两个盘子，那么需要
(1)A->B;
(2)A->C;
(3)B->C;
如果有三个盘子，可以将前两个盘子看作一个盘子，对两个盘子重复以上三个步骤，于是得到N个盘子的递归算法，递归结束的条件是N=1；
1 void Hanoi(int n,char A,char B,char C) //A借助B,将n个盘子移到C ,递归的妙用在于不用关心具体实现的细节
2 {
3 if (n==1)printf("%c -> %c",A,C); //只有一个盘子，直接将其移到C
4 else
5 {
6 Hanoi(n-1,A,C,B); //第一步，A借助C，将n-1个盘子移到B;
7 printf("%c -> %c",A,C); //第二步，将A上剩余的一个盘移到C;
8 Hanoi(n-1,B,A,C) //第三步，将B上的n-1个盘子移到C。
9 }
10 }
可以用人脑来模拟一下该过程：
当有三个盘子时，在主函数中调用Hanoi（3，A，B，C）时，进入函数中执行else后的一句，Hanoi（2，A，C，B），并且在栈中为后续语句分配空间但不执行。接着再调用自身，Hanoi（1，A，B，C），输出A->C;函数开始“归”，即执行调用Hanoi（1，A，B，C）函数之后未执行的语句，“第二步”，由于这是在函数Hanoi（2，A，C，B），故输出A->B;接着调用Hanoi（1，C，A，B），输出C->B;接着“归”，此时回到函数Hanoi（3，A，B，C），输出A->C;接着调用函数Hanoi（2，B，A，C），在调用Hanoi（1，B，C，A）输出B->A;接着输出B->C;最后，调用Hanoi（1，A，B，C）输出A->C.
------------------------------------------------------------------------------------------------------------------------------------------------------
以下是利用堆栈实现非递归：
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<stdbool.h> 4 typedef struct Problem{ 5 int n; 6 char src,mid,dest; 7 struct Problem *Next; 8 }Stack; 9 10 Stack *CreateStack() 11 { 12 Stack *S; 13 S=(Stack*)malloc(sizeof(struct Problem)); 14 S->Next=NULL; 15 return S; 16 } 17 18 bool IsEmpty(Stack *S) 19 { 20 return (S->Next==NULL); 21 } 22 23 void Push(Stack *S,int n,char A,char B,char C) 24 { 25 Stack *TmpCell; 26 TmpCell=(Stack *)malloc(sizeof(struct Problem)); 27 TmpCell->n=n; 28 TmpCell->src=A; 29 TmpCell->mid=B; 30 TmpCell->dest=C; 31 TmpCell->Next=S->Next; 32 S->Next=TmpCell; 33 } 34 35 Stack *Pop(Stack *S,Stack *curPrb) 36 { 37 Stack *FirstCell; 38 FirstCell=(Stack *)malloc(sizeof(struct Problem)); 39 FirstCell=S->Next; 40 curPrb->n=FirstCell->n;curPrb->src=FirstCell->src;curPrb->mid=FirstCell->mid;curPrb->dest=FirstCell->dest; 41 S->Next=FirstCell->Next; 42 free(FirstCell); 43 return curPrb; 44 } 45 46 int main() 47 { 48 int n; 49 scanf("%d",&n); 50 Stack *S; 51 S=CreateStack(); 52 Push(S,n,'A','B','C'); 53 while (!IsEmpty(S)) 54 { 55 Stack *curPrb; 56 curPrb=(Stack *)malloc(sizeof(struct Problem)); 57 curPrb=Pop(S,curPrb); 58 if (curPrb->n==1)printf("%c -> %c\n",curPrb->src,curPrb->dest); 59 else 60 { 61 Push(S,curPrb->n-1,curPrb->mid,curPrb->src,curPrb->dest);//堆栈的顺序和递归正好相反 62 Push(S,1,curPrb->src,curPrb->mid,curPrb->dest); 63 Push(S,curPrb->n-1,curPrb->src,curPrb->dest,curPrb->mid); 64 } 65 free(curPrb); 66 } 67 free(S); 68 return 0; 69 }