汉诺塔非递归实现 C语言版

我上一篇博客是汉诺塔C语言递归实现，非递归和递归想法一样。这里不再赘述，直接链接转到：

汉诺塔递归实现 C语言版

递归实现固然好理解，但是n的值越大，空间和时间上都是极大的消耗，最终可能导致程序直接崩溃。 在以后的做题或者是面试中，不推荐用递归方法做，所以要写出对应的非递归方法。

某次上课无意间听到老师说了这样一句话：任何递归法都可以用循环的方法进行非递归实现，然后回头找了找汉诺塔非递归的资料，整理整理，搞出了一个c实现的非递归方法

#include<stdio.h> #include <stdlib.h> #define MaxSize 100 typedef struct{ int N; char A; //起始柱 char B; //借助柱 char C; //目标柱 }ElementType; typedef struct { ElementType Data[MaxSize]; int top; }Stack;//汉诺塔问题的结构类型 void Push(Stack *PtrS, ElementType item){ //入栈操作 if (PtrS->top == MaxSize) { printf("The stack is full!\n"); return; } else { PtrS->Data[++(PtrS->top)] = item; return; } } ElementType Pop(Stack *PtrS){ if (PtrS->top == -1) { printf("The stack is empty!\n"); exit(1); //直接终止程序，一般不会出现这个错误 } else { PtrS->top--; return (PtrS->Data[PtrS->top + 1]); //或者是return PtrS->Data[PtrS->top--]; } } //借助栈的非递归实现 void Hanoi(int n){ ElementType P, toPush; Stack S; P.N = n; P.A = 'a'; P.B = 'b'; P.C = 'c'; S.top = -1; Push(&S, P); while (S.top != -1) //当堆栈不为空时 { P = Pop(&S);//出栈 if (P.N == 1)//当只剩一个盘子时，直接由当前柱移动到目的柱 printf("%c -> %c\n", P.A, P.C); else { toPush.N = P.N - 1; toPush.A = P.B; toPush.B = P.A; toPush.C = P.C; Push(&S, toPush); //将第三步(n - 1, b, a, c)入栈 toPush.N = 1; toPush.A = P.A; toPush.B = P.B; toPush.C = P.C; Push(&S, toPush); //将第二步1, a, b, c)入栈 toPush.N = P.N - 1; toPush.A = P.A; toPush.B = P.C; toPush.C = P.B; Push(&S, toPush); //将第一步(n - 1, a, c, b)入栈 } } } int main(){ int n; scanf("%d", &n); if (n <= 0)return 0; else Hanoi(n); }

还是三个步骤： 1.将n-1个盘子由a柱借助c柱移动到b柱 2.将最下面的盘子由a柱直接移动到c柱 3.将那n-1个盘子在由b柱借助a柱移动到c柱

因为这个是出栈时的操作，所以入栈时要到着写

简要解释一下（因为跟递归思路差不多）

如果n不等于一时，就意味着，以上的n-1个盘子，都要做上述所说的三个步骤，知道n等于1时，直接移动到目的柱。 因此，移动次数最多的是最上边的那个盘子，移动次数最少的是最下面的那个盘子，只需要移动一次

利用结构体数组更便于理解。

本文为原创，如有问题欢迎评论区留言。