数据结构递归和非递归实现汉诺塔

任务描述

本关任务：采用递归和非递归方法求解Hanoi问题
实验目的:领会基本递归算法设计和递归到非递归的转换方法。
实验内容:编写程序，采用递归和非递归方法求解Hanoi问题，输出n个盘片的移动过程。

相关知识

为了完成本关任务，程序提供了一个顺序栈的实现，请参见代码文件中的头文件sqstack.h。

编程要求

根据提示，在右侧编辑器补充完成hanoi.cpp中的代码，输出n个盘片的移动过程。

测试说明

平台会对你编写的代码进行测试：

测试输入：3
预期输出：

C++代码

#include "sqstack.h"	//顺序栈基本运算及实现

//----递归算法------------------------------------------
void Hanoi1(int n, char a, char b, char c)
{
	if (n == 1)
		printf("\t将第%d个盘片从%c移动到%c\n", n, a, c);
	else
	{
        //请在下面编写代码
        /*************************Begin*********************/
        //将塔柱a上面的n-1个盘子移动到塔柱b，借助于塔柱c作为中转
		Hanoi1(n-1,a,c,b);
        /**************************End**********************/
		printf("\t将第%d个盘片从%c移动到%c\n", n, a, c);
		Hanoi1(n - 1, b, a, c);
	}
}

//----非递归算法------------------------------------------
void Hanoi2(int n, char x, char y, char z)
{
	StackType *st;							//定义顺序栈指针
	ElemType e, e1, e2, e3;
	if (n <= 0) return;						//参数错误时直接返回
	InitStack(st);							//初始化栈
	e.n = n; e.x = x; e.y = y; e.z = z; e.flag = false;
    //请在下面编写代码
    /*************************Begin*********************/
    //元素e进栈
    Push(st,e); 
    /**************************End**********************/

	while (!StackEmpty(st))					//栈不空循环
	{
        //请在下面编写代码
        /*************************Begin*********************/
        //出栈元素e
        Pop(st,e);
        /**************************End**********************/			
		if (e.flag == false)				//当不能直接移动盘片时
		{
			e1.n = e.n - 1; e1.x = e.y; e1.y = e.x; e1.z = e.z;
			if (e1.n == 1)					//只有一个盘片时可直接移动
				e1.flag = true;
			else							//有一个以上盘片时不能直接移动
				e1.flag = false;
			Push(st, e1);					//处理Hanoi(n-1,y,x,z)步骤
			e2.n = e.n; e2.x = e.x; e2.y = e.y; e2.z = e.z; e2.flag = true;

            //请在下面编写代码
            /*************************Begin*********************/
            //处理move(n,x,z)步骤
				Push(st,e2);
            /**************************End**********************/				
			e3.n = e.n - 1; e3.x = e.x; e3.y = e.z; e3.z = e.y;
			if (e3.n == 1)					//只有一个盘片时可直接移动
				e3.flag = true;
			else
				e3.flag = false;			//有一个以上盘片时不能直接移动
            
            //请在下面编写代码
            /*************************Begin*********************/
            //处理Hanoi(n-1,x,z,y)步骤
				Push(st,e3);
            /**************************End**********************/				
		}
		else								//当可以直接移动时
			printf("\t将第%d个盘片从%c移动到%c\n", e.n, e.x, e.z);
	}
	DestroyStack(st);						//销毁栈
}