hanoi.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include<iostream.h>
#include<fstream.h>
ifstream in("input.txt");	
ofstream out("output.txt");


class NoMem{
public:
	NoMem(){}
};

class OutOfBounds{
public:
	OutOfBounds(){}
};

template<class T>
class Stack{
	public:
		Stack(int Max=100);
		~Stack(){delete[]stack;}
		bool Empty()const{return top==-1;}
		bool Full()const{return top==MaxTop;}
		T Top()const;
		Stack<T>&Push(const T& x);
		Stack<T>&Pop(T& x);
	private:
		int top;
		int MaxTop;
		T*stack;
};

template<class T>
Stack<T>::Stack(int Max)
{
	MaxTop=Max-1;
	stack=new T[Max];
	top=-1;
}

template<class T>
T Stack<T>::Top()const
{
	if(Empty())throw OutOfBounds();
	else return stack[top];
}

template<class T>
Stack<T>&Stack<T>::Push(const T& x)
{
	if(Full())throw NoMem();
	stack[++top]=x;
	return *this;
}

template<class T>
Stack<T>&Stack<T>::Pop(T& x)
{
	if(Empty())throw OutOfBounds();
	x=stack[top--];
	return *this;
}

class Hanoi{
	friend void TowersOfHanoi(int);
public:
	void TowersOfHanoi(int n,int a,int c,int b);
private:
	Stack<int>*S[4];
};

void Hanoi::TowersOfHanoi(int n,int a,int c,int b)//把塔a上的n个圆盘移到塔b上
{	
	
	int d;char ch[]={'0','A','B','C'};//ch[1]对应A，ch[2]对应B,ch[3]对应C
	if(n>0)
	{	
		TowersOfHanoi(n-1,a,b,c);//把塔a上前面的n－1个圆盘移到塔c上.
		S[a]->Pop(d);//把第n个圆盘从塔a移到塔b上.
		S[b]->Push(d);
	
		out<<"Move disk "<<n<<" from tower "<<ch[a]<<" to tower "<<ch[b]<<endl;//输出移动圆盘的情况
		for(int i=1;i<=3;i++)//输出各个塔当前的状态。
		{
			if(S[i]->Empty()==1)
			{
		       
		       out<<"0"<<endl;
			}
			else
			{
				while(S[i]->Empty()!=1)
				{
	        	    int num;
		            S[i]->Pop(num);
	        	    S[0]->Push(num);
				}
	            while(S[0]->Empty()!=1)
				{
		            int num;
		            S[0]->Pop(num); 
				    S[i]->Push(num);
		            out<<num<<" ";

				}
				out<<endl;
			}
		}
		TowersOfHanoi(n-1,c,a,b);//把n-1个圆盘从塔c移到塔b上
	}
}



void TowersOfHanoi(int n)
{
	Hanoi X;
	X.S[0]=new Stack<int>(n);//用来中转的栈
	X.S[1]=new Stack<int>(n);//存A塔的栈
	X.S[2]=new Stack<int>(n);//存B塔的栈
	X.S[3]=new Stack<int>(n);//存C塔的栈
	
	for(int i=n;i>0;i--)
		out<<i<<" ";
	out<<endl<<"0"<<endl<<"0"<<endl;//输出各汉洛塔的初始状态值。
	
	for(int d=n;d>0;d--)
	{
		X.S[1]->Push(d);//把塔A的值存入栈中
	}
	
	X.TowersOfHanoi(n,1,3,2);//具体移动过程的函数
}

void main()
{
	int n;
	
	in>>n;

    TowersOfHanoi(n);
}