设有X,Y,Z三根柱子，X上开始有n个盘子
1 当n=1时： 将盘子从X柱直接移到Z柱；
2 当n=2时： 首先将编号为1的盘子从X柱移到Y柱；
其次将编号为2的盘子从X柱移到Z柱；
最后将编号为1的盘子从Y柱移到Z柱；
3 当n=n时： 首先将n-1个盘子从X柱移到Y柱；
其次将编号为n的盘子从X柱移到Z柱；
最后将n-1个盘子从Y柱移到Z柱；
代码实现，基于链式栈
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <fcntl.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdbool.h>
#define ERROR_DATA -1
typedef int Element;
typedef struct stack_node
{
Element data;
struct stack_node *next;
}stack_node, *stack_node_ptr;
bool empty_stack(stack_node_ptr top)
{
if(top == NULL)
return true;
else
return false;
}
void push_stack(stack_node_ptr *top, Element data)
{
if(empty_stack(*top)) {
*top = (stack_node_ptr)malloc(sizeof(stack_node));
if(*top == NULL) {
perror("malloc error\n");
exit(-1); //goto end;
}
(*top)->data = data;
(*top)->next = NULL;
} else {
stack_node_ptr new_node = (stack_node_ptr)malloc(sizeof(stack_node));
if(new_node == NULL) {
perror("malloc error\n");
exit(-1); //goto end;
}
new_node->data = data;
new_node->next = *top;
*top = new_node;
}
}
Element pop_stack(stack_node_ptr *top)
{
Element data = ERROR_DATA;
if(empty_stack(*top)) {
perror("the stack is empty\n");
goto end;
} else {
stack_node_ptr free_node = *top;
*top = (*top)->next;
data = free_node->data;
free(free_node);
}
end:
return data;
}
void printf_stack(stack_node_ptr top)
{
stack_node_ptr p = top;
while(!empty_stack(p)) {
printf("%d\t", p->data);
p = p->next;
}
printf("\n");
}
void clear_stack(stack_node_ptr top)
{
stack_node_ptr p = top;
stack_node_ptr free_node = p;
while(!empty_stack(p)) {
p = p->next;
}
}
/*为什么选择传递stack_node_ptr *x的原因在于栈随时都在变化之中，栈顶指针也随之变化
所以传递指针的指针也就是必然的*/
void hanoi(int n, stack_node_ptr *x, stack_node_ptr *y, stack_node_ptr *z)
{
if(n == 1) {
Element data = pop_stack(x);
if(data == ERROR_DATA) { /*release the other stack*/
printf("error: func=%s line=%d\n", __func__, __LINE__);
while(!empty_stack(*y))
pop_stack(y);
while(!empty_stack(*z))
pop_stack(z);
exit(-1);
}
push_stack(z, data);
} else {
hanoi(n-1, x, z, y);
hanoi(1, x, y, z);
hanoi(n-1, y, x, z);
}
}
int main(void)
{
stack_node_ptr top_x = NULL;
stack_node_ptr top_y = NULL;
stack_node_ptr top_z = NULL;
int hanoi_data[] = {8, 7, 6, 5, 4, 3, 2,1};
int i = 0;
for(i=0; i<sizeof(hanoi_data)/sizeof(int); i++)
{
push_stack(&top_x, hanoi_data[i]);
}
printf("before excute hanoi function:\n");
printf_stack(top_x);
printf_stack(top_y);
printf_stack(top_z);
hanoi(8, &top_x, &top_y, &top_z);
printf("after excute hanoi function:\n");
printf_stack(top_x);
printf_stack(top_y);
printf_stack(top_z);
return 0;