C语言非递归解决汉诺塔问题
时间: 2024-05-10 08:10:38 浏览: 10
以下是C语言非递归解决汉诺塔问题的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义栈的结构
typedef struct {
int *arr;
int top;
int capacity;
} Stack;
// 初始化栈
Stack* initStack(int capacity) {
Stack *stack = (Stack*)malloc(sizeof(Stack));
stack->arr = (int*)malloc(capacity * sizeof(int));
stack->top = -1;
stack->capacity = capacity;
return stack;
}
// 判断栈是否为空
int isEmpty(Stack *stack) {
return stack->top == -1;
}
// 判断栈是否已满
int isFull(Stack *stack) {
return stack->top == stack->capacity - 1;
}
// 入栈
void push(Stack *stack, int data) {
if (isFull(stack)) {
printf("Stack is full.\n");
return;
}
stack->arr[++stack->top] = data;
}
// 出栈
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
return -1;
}
return stack->arr[stack->top--];
}
// 非递归解决汉诺塔问题
void hanoiNonRecursive(int n, Stack *src, Stack *aux, Stack *dest) {
int totalMoves = (1 << n) - 1; // 总共需要移动的次数
// 根据奇偶性确定第一个辅助塔
Stack *temp;
if (n % 2 == 0) {
temp = aux;
aux = dest;
dest = temp;
}
for (int i = n; i >= 1; i--) {
push(src, i); // 将盘子依次入栈
}
for (int i = 1; i <= totalMoves; i++) {
if (i % 3 == 1) {
if (isEmpty(src)) {
push(src, pop(aux));
} else if (isEmpty(aux)) {
push(aux, pop(src));
} else if (src->arr[src->top] > aux->arr[aux->top]) {
push(src, pop(aux));
} else {
push(aux, pop(src));
}
} else if (i % 3 == 2) {
if (isEmpty(src)) {
push(src, pop(dest));
} else if (isEmpty(dest)) {
push(dest, pop(src));
} else if (src->arr[src->top] > dest->arr[dest->top]) {
push(src, pop(dest));
} else {
push(dest, pop(src));
}
} else if (i % 3 == 0) {
if (isEmpty(aux)) {
push(aux, pop(dest));
} else if (isEmpty(dest)) {
push(dest, pop(aux));
} else if (aux->arr[aux->top] > dest->arr[dest->top]) {
push(aux, pop(dest));
} else {
push(dest, pop(aux));
}
}
}
}
int main() {
int n = 3; // 汉诺塔的盘子数量
Stack *src = initStack(n);
Stack *aux = initStack(n);
Stack *dest = initStack(n);
hanoiNonRecursive(n, src, aux, dest);
printf("Move the disks from source to destination:\n");
for (int i = n - 1; i >= 0; i--) {
printf("%d -> %d\n", src->arr[i], dest->arr[i]);
}
free(src->arr);
free(aux->arr);
free(dest->arr);
free(src);
free(aux);
free(dest);
return 0;
}
```