hanoi塔问题的非递归算法c

Hanoi塔问题是一个经典的递归问题，但是也可以使用非递归算法来解决。以下是使用栈实现Hanoi塔问题的非递归算法C代码：

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

typedef struct {
    int *arr;
    int top;
    int size;
} Stack;

// 初始化栈
Stack *initStack(int size) {
    Stack *s = (Stack*)malloc(sizeof(Stack));
    s->arr = (int*)malloc(sizeof(int) * size);
    s->top = -1;
    s->size = size;
    return s;
}

// 判空
int isEmpty(Stack *s) {
    return s->top == -1;
}

// 判满
int isFull(Stack *s) {
    return s->top == s->size - 1;
}

// 入栈
void push(Stack *s, int x) {
    if (isFull(s)) {
        printf("Stack is full!\n");
        return;
    }
    s->arr[++s->top] = x;
}

// 出栈
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->arr[s->top--];
}

// 移动
void move(Stack *a, Stack *b) {
    int x = pop(a);
    push(b, x);
    printf("Move %d from %d to %d\n", x, a->arr[0], b->arr[0]);
}

// Hanoi塔问题的非递归算法
void hanoi(int n, Stack *a, Stack *b, Stack *c) {
    int i, step = 0;
    // 初始状态
    for (i = n; i > 0; i--) {
        push(a, i);
    }
    // 栈操作模拟递归
    while (!isEmpty(a) || !isEmpty(b)) {
        while (!isEmpty(a)) {
            move(a, c);
            step++;
        }
        if (step == n) break;
        move(b, a);
        step++;
        while (!isEmpty(c)) {
            move(c, b);
            step++;
        }
        if (step == n) break;
        move(a, c);
        step++;
        while (!isEmpty(b)) {
            move(b, a);
            step++;
        }
        if (step == n) break;
        move(c, b);
        step++;
    }
}

int main() {
    int n = 3;
    Stack *a = initStack(n);
    Stack *b = initStack(n);
    Stack *c = initStack(n);
    a->arr[0] = 1;
    b->arr[0] = 2;
    c->arr[0] = 3;
    hanoi(n, a, b, c);
    return 0;
}

在上述代码中，我们使用了三个栈来表示三个柱子，首先将所有盘子都压入第一个栈a中，然后根据Hanoi塔问题的规则，不断将盘子从一个柱子移动到另一个柱子，直到所有盘子都移动到了目标柱子。移动盘子的操作使用了move函数来实现，这个函数将一个栈中的顶部元素弹出并压入另一个栈中，同时输出移动的信息。在主函数中，我们初始化了三个栈，并将第一个栈的第一个元素设为1，第二个栈的第一个元素设为2，第三个栈的第一个元素设为3，然后调用hanoi函数来解决Hanoi塔问题。