汉诺塔的递归与非递归求解（c语言）

直接上代码 环境vs2019

递归

#define _CRT_SECURE_NO_WARNINGS
#include

int m = 0;//移动次数
void move(int n,char A, char C) {

	printf("n第%d次移动,移动%d号盘子：%c-->%c", ++m,n, A, C);
}
void hanoi(int n, char A, char B, char C)
{
	if (n == 1)
		move(n,A, C);
	else
	{
		hanoi(n - 1, A, C, B);
		move(n,A, C);
		hanoi(n - 1, B, A, C);
	}

}
int main()
{
	int n;
	printf("玩几层汉诺塔? ");
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}

非递归：用栈

#define _CRT_SECURE_NO_WARNINGS
#include
#define Error -1
#define OK 1
#define True 1
#define False 0

typedef struct Node
{
	char A;
	char B;
	char C;
	int num;//起始柱上的盘子数
}node;
int m = 0;//移动步数
typedef node ElemType;//栈存的元素类型
// 栈结构的定义
typedef struct Stack
{
	ElemType* base;
	ElemType* top;
	int stacksize;
}SeqStack;

// 栈的基本操作
int InitStack(SeqStack* S);
int Push(SeqStack* S, ElemType e);
int Pop(SeqStack* S, ElemType* e);
int IsEmpty(SeqStack* S);
const int STACK_INIT_SIZE = 100; //初始分配的长度
const int STACKINCREMENT = 10; // 分配内存的增量

// 初始化栈
int InitStack(SeqStack* S)
{
	S->base = (ElemType*)malloc(STACK_INIT_SIZE * sizeof(ElemType));
	if (S->base == NULL)
		return Error;
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
	return OK;
}
//压栈——插入元素e为新的栈顶元素
int Push(SeqStack* S, ElemType e)
{
	if (S->top - S->base >= S->stacksize)
	{
		S->base = (ElemType*)malloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(ElemType));
		if (!S->base)
			return Error;
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*(S->top++) = e;
	return OK;
}
//弹栈——删除栈顶元素
int Pop(SeqStack* S, ElemType* e)
{
	if (S->top == S->base)
		return Error;
	*e = (*--S->top);
	return OK;
}

//判断栈是否为空
int IsEmpty(SeqStack* S)
{
	if (S->top == S->base) return True;//空栈返回1
	else
		return False;//非空栈返回0
}
void move(char A, char C) {

	printf("n第%d次移动,%c-->%c", ++m,A, C);
}
void hanoi(int n) 
{
	SeqStack S;
	struct Node h = { 'A','B','C',n};
	struct Node topush=h;
	InitStack(&S);//初始化栈
	Push(&S, h);
	while (!IsEmpty(&S)) 
	{
		if (Pop(&S, &h) != OK)
			break;
		if (h.num == 1)
			move(h.A, h.C);
		else 
		{
			topush.num = h.num - 1;
			topush.A = h.B;topush.B = h.A; topush.C = h.C;
			if (Push(&S, topush)!=OK)
				break;
			topush.num= 1;
			topush.A = h.A; topush.B = h.B; topush.C = h.C;
			if (Push(&S, topush)!=OK)
				break;
			topush.num = h.num - 1;
			topush.A = h.A; topush.B = h.C; topush.C = h.B;
			if (Push(&S, topush)!=OK)
				break;
		}
	}
}

int main()
{
	int n;
	printf("玩几层汉诺塔? ");
	scanf("%d", &n);
	hanoi(n);
}