汉诺塔---手写出栈压栈过程实现

代码实现:

 1 #include<stdio.h>
 2 
 3 //函数的形参A、B、C不一定代表的是A、B、C柱子，递归传参的时候会变化！
 4 void hanoit(int n,char A,char B,char C){
 5     if(n==1){
 6         //如果剩下一个盘子，直接将A柱上的盘子从A移到C(直接从初始塔移动到目标塔)
 7         printf("将编号为%d的盘子从%c柱子移到%c柱子",n,A,C);
 8     }
 9     else{
10       //否则，先将A柱上的n-1个盘子从A借助C移到B(从初始塔移动到介质塔)
11       hanoit(n-1,A,C,B);//注意参数顺序：从A借助C移到B
12       
13       //A柱上最后一个盘子直接移到C柱上
14       printf("将编号为%d的盘子从%c柱子移到%c柱子",n,A,C);
15       
16       //最后将B柱子的n-1个盘子从B借助A移到C(从介质塔移动到目标塔)
17       hanoit(n-1,B,A,C);
18     }
19 }
20 
21 int main(){
22     //三个柱子A、B、C，分别的作用是初始柱、介质柱、目标柱
23     char ch1 = 'A';
24     char ch2 = 'B';
25     char ch3 = 'C';
26     
27     int n;
28     
29     printf("移动盘子的个数：");//也是最后一个盘子的编号，顶部第一个盘子的编号是1
30     scanf("%d",&n);
31     
32     hanoit(n,'A','B','C');
33     
34     
35     return 0;
36 }

递归执行过程(调用方法的栈机制:不停的压栈、出栈（特点：先进后出）)：

　　假如输入的盘子个数为2：

主函数传参hanoit(2,’A‘,‘B','C')，压栈1。

n!=1，于是递归执行 hanoit(2-1,A,C,B)，压栈2。

n==1，输出语句，压栈3，输出“将编号为1的盘子从A柱移到B柱"，出栈3。

函数hanoit(2-1,A,C,B)出栈2

执行下一条输出语句，压栈2，输出”将编号为2的盘子从A柱移到C柱“，出栈2

执行递归 hanoit(2-1,B,A,C)，压栈2，输出”将编号为1的盘子从B柱移到C柱“，出栈2

函数hanoit(2,’A‘,‘B','C')出栈1

程序执行完毕

假如输入的盘子个数为3：(较为麻烦，需要不断交替参数)

主函数传参hanoit(n=3,A=’A‘,B=‘B',C='C')，压栈1。此时A=A、B=B、C=C

n==3，递归执行hanoit(3-1,A,C,B)，压栈2。此时A=A==A、B=C==C、C=B==B

n==2，递归执行hanoit(2-1,A,C,B)，压栈3。此时A=A==A、B=C==B、C=B==C

n==1，输出语句，压栈4，输出“将编号为1的盘子从A柱移到C柱"，出栈4。

函数hanoit(2-1,A,C,B)执行完毕，出栈3

执行下一条输出语句，压栈3，输出”将编号为2的盘子从A柱移到B柱“，出栈3。

执行函数hanoit(2-1,B,A,C)，压栈3，此时A=B==C、B=A==A、C=C==B

n==1，输出语句，压栈4，输出“将编号为1的盘子从C柱移到B柱"，出栈4

函数hanoit(2-1,B,A,C)执行完毕，出栈3

函数hanoit(3-1,A,C,B)执行完毕，出栈2

执行下一条输出语句，压栈2，输出“将编号为3的盘子从A柱移到C柱"，出栈2

注意此时n==3时的各个参数顺序，往下继续执行hanoit(3-1,B,A,C)，压栈2，此时A=B==B、B=A==A、C=C==C

n==2，递归执行hanoit(2-1,A,C,B)，压栈3。此时A=A==B、B=C==C、C=B==A

n==1，输出语句，压栈4，输出“将编号为1的盘子从B柱移到A柱"，出栈4。

函数hanoit(2-1,A,C,B)执行完毕，出栈3

执行下一条输出语句，压栈3，输出”将编号为2的盘子从B柱移到C柱“，出栈3。

往下执行hanoit(2-1,B,A,C)，压栈3。此时A=B==A、B=A==B、C=C==C

n==1，输出语句，压栈4，输出“将编号为1的盘子从A柱移到C柱"，出栈4

函数hanoit(2-1,B,A,C)执行完毕，出栈3

函数hanoit(3-1,B,A,C)执行完毕，出栈2

函数hanoit(n=3,A=’A‘,B=‘B',C='C')执行完毕，出栈1

程序执行完毕