学步园

设有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;