汉诺塔非递归实现-JZTXT

汉诺塔非递归实现

思路

使用栈结构模拟函数调用。

代码

#include <stdio.h>

// 栈帧结构体 
typedef struct {
	int pc, n;
	char from, via, to;
} Frame; 

// 全局变量（包括容量为 64 的栈和头指针） 
Frame stk[64], *top = stk - 1;
	
// 模拟函数调用，相当于将函数压入栈中
void call(int n, char from, char via, char to) {
	*(++top) = (Frame) { 0, n, from, via, to };
}

// 模拟函数执行完毕，相当于将函数从栈顶弹出 
void _return() {
	top--;
}

/**
	非递归汉诺塔算法 
	n: 汉诺塔层级
	from：初始柱子 
	via：途经柱子 
	to：目标柱子 
**/
void hanoi(int n, char from, char via, char to) {
	call(n, from, via, to);
	for (Frame *f; (f = top) >= stk; f->pc++) {
		/**
			我们知道想要完成汉诺塔移动操作，主要分为以下几个步骤（假设此处汉诺塔高度为 n） 
			1. 如果 n == 1 那么直接移动。 
			2. 如果 n != 1，就要先将 1 ~ (n - 1) 层的圆环从 A 柱移到 B 柱。 
			3. 再将第 n 层的圆环从 A 柱移到 C 柱。 
			4. 最后将  1 ~ (n - 1) 层的圆环从 B 柱移到 C 柱，堆叠上去。
			仔细观察 switch 就会发现它的分支操作恰好体现了上面的移动思路。 
		**/
		// switch 实现状态机功能 
		switch(f->pc) {
			case 0: 
			if (f->n == 1) {
				printf("%c -> %c\n", f->from, f->to);
				_return();
			}
				break;
			case 1: 
				call(f->n - 1, f->from, f->to, f->via);
				break;
			case 2: 
				call(1, f->from, f->via, f->to);
				break;
			case 3: 
				call(f->n - 1, f->via, f->from, f->to);
				break;
			default : _return();	
		}
	}
}

int main() {
	hanoi(3, 'A', 'B', 'C');
	return 0;
}

鸣谢

这里特别感谢 [蒋炎岩](Yanyan Jiang | Institute of Computer Software (nju.edu.cn)) 老师在操作系统课上展示的的汉诺塔非递归实现，B站视频链接在此。由于本人糟糕的 C 语言基础，对视频中涉及的 宏调用 不太理解，所以自己写了一个个函数来实现该功能。