hanoi_nonrescursive.cpp

利用堆栈的原理来实现汉诺塔程序的模拟递归

/////////////////////////////////////////////////////////////////////////////////////////////////
//				Hanoi_NonRes.cpp 
//	汉诺塔的模拟递归的实现.
//	依照递归的思想,采用模拟递归的方法,用栈来实现模拟相应递归函数的执行流程.
//
//	相应的递归算法:
//			void hanoi(int n, int a, int b, int c )
//			{
//	0:			if ( n == 1 )
//					Move (n, a, c);
//				else 
//				{
//	1:				hanoi(n-1, a, c, b);
//	2:				Move(n, a, c);
//	3:				hanoi(n-1, b, a, c);
//	4:			}
//			}
/////////////////////////////////////////////////////////////////////////////////////////////////

#include <fstream.h>

#include <stack>

using namespace std;


typedef	struct
{
	int	DiskOrder,	// 盘子序号
		C1,		// 源柱
		C2,		// 中间柱
		C3,		// 目的柱
		AddressReturn;	// 返回地址
}	ElemType;

////////////////////////////////////////////////////////////////////////////////////////////////
//			核心算法函数
//	依照递归的思想,采用模拟递归的方法,用栈来实现模拟相应递归函数的执行流程.
////////////////////////////////////////////////////////////////////////////////////////////////
void Hanoi(int n);	

/////////////////////////////////////////////////////////////
//			移动盘子的函数
/////////////////////////////////////////////////////////////		
void Move( ElemType e);

//*******************************************************************************************
//			主函数
int main(int argc, char* argv[])
{
	int	N;	//=10;
	cout << "Please intput the number of all disks:" ;
	cin >> N;
	Hanoi( N );
	return 0;
}
//********************************************************************************************

////////////////////////////////////////////////////////////////////////////////////////////////
//			核心算法函数
//	依照递归的思想,采用模拟递归的方法,用栈来实现模拟相应递归函数的执行流程.
////////////////////////////////////////////////////////////////////////////////////////////////

void Hanoi(int n)
{
	stack<ElemType> S;

	int	Processing	= 0;	// 模拟 递归函数正执行到何处
	ElemType	e = {n, 1, 2, 3, 0};	// 5 个参数依次是 盘子序号, 源柱, 中间柱, 目的柱, 返回地址
	int temp;	// 用于交换两根柱子值

	S.push( e );
	
	while ( ! S.empty() )
	{
		switch ( Processing )
		{
		//	执行递归函数判断语句 : if ( n == 1) {} else {}
		case 0:
			e = S.top();
			if ( e.DiskOrder == 1 )
			{
				Processing = e.AddressReturn;
				S.pop();
				Move( e );
			}
			else
			{
				Processing++;
			}
			
			break;
			
		//	执行递归函数中的 Hanoi(n, a, c, b)
		case 1:
			Processing = 0;
			
			e.AddressReturn = 2;
			e.DiskOrder--;
			
			temp = e.C2;
			e.C2 = e.C3;
			e.C3 = temp;
			
			S.push( e );
			
			break;
			
		//	执行递归函数中的 Move(n, a, c)
		case 2:
			Processing++;
			e = S.top();
			Move( e );
			
			break;
			
		//	执行递归函数中的 Hanoi(n, b, a, c)
		case 3:
			Processing = 0;
			
			e.AddressReturn = 4;
			e.DiskOrder--;
			
			temp = e.C1;
			e.C1 = e.C2;
			e.C2 = temp;

			S.push( e );
						
			break;

		//	递归函数中完,返回
		case 4:
			e = S.top();
			S.pop();
			Processing = e.AddressReturn;

			break;
		}	// end of switch
	}	// end of switch

}	// end of Hanoi

/////////////////////////////////////////////////////////////
//			移动盘子的函数
/////////////////////////////////////////////////////////////	
void Move( ElemType e)
{
	static int Counter = 0;
	cout << ++Counter << "\t:	Move disk "
		<< e.DiskOrder << "\t from " 
		<< e.C1 << " to " << e.C3
		<< endl;
}