用C语言写一个非递归汉诺塔

下面是使用 C 语言编写的非递归汉诺塔的代码：

#include <stdio.h>
#include <stdlib.h>

// 定义一个栈结构体
typedef struct {
    int *data;  // 栈的数据存储区
    int top;    // 栈顶指针
    int size;   // 栈的容量
} Stack;

// 初始化栈
void initStack(Stack *stack, int size) {
    stack->data = (int *) malloc(sizeof(int) * size);
    stack->top = -1;
    stack->size = size;
}

// 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isFull(Stack *stack) {
    return stack->top == stack->size - 1;
}

// 入栈操作
void push(Stack *stack, int value) {
    if (isFull(stack)) {
        printf("Stack overflow!\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 出栈操作
int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Stack underflow!\n");
        return -1;
    }
    return stack->data[stack->top--];
}

// 非递归实现汉诺塔移动操作
void hanoi(int n) {
    Stack s1, s2, s3;       // 定义三个栈
    initStack(&s1, n);      // 初始化第一个栈
    initStack(&s2, n);      // 初始化第二个栈
    initStack(&s3, n);      // 初始化第三个栈
    int i, x, from, to, tmp;    // 定义临时变量
    for (i = n; i >= 1; i--) {
        push(&s1, i);       // 初始化第一个栈
    }
    if (n % 2 == 0) {       // 判断奇偶性
        tmp = s2.top;
        s2.top = s3.top;
        s3.top = tmp;
        from = 1;
        to = 2;
    } else {
        tmp = s1.top;
        s1.top = s3.top;
        s3.top = tmp;
        from = 1;
        to = 3;
    }
    int step = 0;
    while (s3.top != n - 1) {
        switch (step % 3) {
            case 0:     // 第一步
                if (!isEmpty(&s1)) {
                    x = pop(&s1);
                    push(&s2, x);
                    printf("%d -> %d\n", from, to);
                } else {
                    x = pop(&s2);
                    push(&s1, x);
                    printf("%d -> %d\n", to, from);
                }
                if (x % 2 == 0) {
                    if (from == 1) {
                        to = 3;
                    } else {
                        to = 1;
                    }
                } else {
                    if (from == 1) {
                        to = 2;
                    } else {
                        to = 1;
                    }
                }
                from = 3 - from - to;
                break;
            case 1:     // 第二步
                if (!isEmpty(&s1) && (isEmpty(&s2) || s1.data[s1.top] < s2.data[s2.top])) {
                    x = pop(&s1);
                    push(&s2, x);
                    printf("%d -> %d\n", from, to);
                } else {
                    x = pop(&s2);
                    push(&s1, x);
                    printf("%d -> %d\n", to, from);
                }
                if (x % 2 == 0) {
                    if (from == 1) {
                        to = 3;
                    } else {
                        to = 1;
                    }
                } else {
                    if (from == 1) {
                        to = 2;
                    } else {
                        to = 1;
                    }
                }
                from = 3 - from - to;
                break;
            case 2:     // 第三步
                if (!isEmpty(&s1)) {
                    x = pop(&s1);
                    push(&s3, x);
                    printf("%d -> %d\n", from, to);
                } else {
                    x = pop(&s3);
                    push(&s1, x);
                    printf("%d -> %d\n", to, from);
                }
                if (x % 2 == 0) {
                    if (from == 1) {
                        to = 3;
                    } else {
                        to = 1;
                    }
                } else {
                    if (from == 1) {
                        to = 2;
                    } else {
                        to = 1;
                    }
                }
                from = 3 - from - to;
                break;
        }
        step++;
    }
}

int main() {
    int n;
    printf("Enter the number of disks: ");
    scanf("%d", &n);
    hanoi(n);
    return 0;
}

这个非递归算法模拟了汉诺塔的移动过程，使用了三个栈来模拟三个柱子，通过不断出栈和入栈操作，实现了汉诺塔的移动。