为何基于栈实现汉诺塔的C语言while循环无法终止？

核心问题拆解 #

1. size函数计算错误 #

代码里的size直接返回s->top，但栈的top初始值是-1——栈里有k个元素时，top的值是k-1。比如栈里存1个元素，top是0，此时size返回0，和实际元素数完全不符。这直接导致循环条件size(&z) < n-1永远无法触发终止：拿n=3举例，z需要攒2个元素才停，但size(&z)返回的是1（此时top=1），1<2始终成立，循环就无限跑下去了。

2. 移动逻辑混乱，导致无效来回移动 #

当前代码每次循环会挨个判断所有可能的逆序移动——比如刚把X的盘移去Z，紧接着又判断Z到X的移动，结果刚移过去的盘立刻被挪回来，完全是无意义的循环。汉诺塔的迭代实现得每次只做一次合法移动，而且要严格遵循奇偶圆盘数的移动顺序，不能双向判断都执行。

3. 输出笔误 #

在X和Y的逆移动分支里，错误输出了"Z to X"，实际应该是"Y to X"，这会让日志和实际操作对不上。

修复后的完整代码 #

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 100

struct stack{
    int a[MAX_SIZE];
    int top;
}x, y, z;

typedef struct stack stk;

void push(stk *s, int n)
{
    if(s->top == MAX_SIZE-1)
        printf("Stack Overflow\n");
    else
        s->a[++s->top] = n;
}

int pop(stk *s)
{
    if(s->top < 0)
    {
        printf("Stack Underflow\n");
        return -1;
    }
    else
    {
        return s->a[s->top--];
    }
}

int top(stk *s)
{
    if(s->top < 0)
    {
        // 空栈返回超大值，避免和圆盘编号（从1开始）混淆
        return MAX_SIZE + 1;
    }
    else
    {
        return s->a[s->top];
    }
}

int isEmptyStack(stk *s)
{
    return s->top < 0;
}

// 修复size函数：返回实际元素数量
int size(stk *s)
{
    return s->top + 1;
}

// 封装移动操作，避免重复代码
void move(stk *from, stk *to, char from_name, char to_name)
{
    push(to, pop(from));
    printf("%c to %c\n", from_name, to_name);
}

int main()
{
    x.top = -1;
    y.top = -1;
    z.top = -1;

    int n;
    printf("Enter number of disks: ");
    scanf("%d", &n);

    // 注意：汉诺塔初始要把大圆盘放底部，所以从n到1入栈
    for(int i = n; i >= 1; i--)
    {
        push(&x, i);
    }

    // 汉诺塔总移动次数固定为2^n -1，用这个控制循环更可靠
    int total_moves = (1 << n) - 1;

    if(n > 0)
    {
        for(int i = 1; i <= total_moves; i++)
        {
            if(n % 2 != 0)
            {
                // 奇数个圆盘的移动顺序：X↔Z → X↔Y → Y↔Z
                switch(i % 3)
                {
                    case 1:
                        top(&x) < top(&z) ? move(&x, &z, 'X', 'Z') : move(&z, &x, 'Z', 'X');
                        break;
                    case 2:
                        top(&x) < top(&y) ? move(&x, &y, 'X', 'Y') : move(&y, &x, 'Y', 'X');
                        break;
                    case 0:
                        top(&y) < top(&z) ? move(&y, &z, 'Y', 'Z') : move(&z, &y, 'Z', 'Y');
                        break;
                }
            }
            else
            {
                // 偶数个圆盘的移动顺序：X↔Y → X↔Z → Y↔Z
                switch(i % 3)
                {
                    case 1:
                        top(&x) < top(&y) ? move(&x, &y, 'X', 'Y') : move(&y, &x, 'Y', 'X');
                        break;
                    case 2:
                        top(&x) < top(&z) ? move(&x, &z, 'X', 'Z') : move(&z, &x, 'Z', 'X');
                        break;
                    case 0:
                        top(&y) < top(&z) ? move(&y, &z, 'Y', 'Z') : move(&z, &y, 'Z', 'Y');
                        break;
                }
            }
        }
    }

    return 0;
}

关键修复点说明 #

1. 修正size函数：返回top + 1，准确统计栈内元素数量。
2. 重构移动逻辑：采用汉诺塔迭代实现的标准规则——根据圆盘数奇偶性确定循环移动顺序，每次循环只执行一次合法移动，彻底避免来回无效操作。
3. 优化top函数：空栈返回一个大于最大圆盘编号的值，这样判断移动时，空栈会被视为“比任何圆盘都大”，完美符合汉诺塔小圆盘只能放在大圆盘上的规则。
4. 修复输出笔误：封装移动函数，统一输出正确的移动路径，避免手动写输出出错。
5. 改用总移动次数控制循环：汉诺塔的总移动次数是固定的2^n -1，用这个条件终止循环比判断目标栈元素数量更可靠，也更符合迭代实现的常规思路。

内容的提问来源于stack exchange，提问作者Divyanshu Mahi