hanoi.cpp

Hanoi非递归源码

// Hanoi.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include ".\hanoi.h"


Hanoi::Hanoi(void)
{
	out.open("Hanoi.txt");

}


Hanoi::~Hanoi(void)
{
	delete []position;
	out.close();
}


bool Hanoi::initial(int num)
{
	if(num<1)
		return false;
	position=new char[num];
	for(int i=0;i<num;i++)
	{
		position[i]='x';
	}
	for(int i=num;i>0;i--)
	{
		tower[0].push(i);
	}
	NumOfDisk=num;

	return true;


}

void Hanoi::PrintPath(int num)
{
	initial(num);
	queue<int> sequence;
	sequence.push(1);
	for(int i=2;i<=NumOfDisk;i++)
	{
		int* temp=new int[sequence.size()];
		copy(sequence,temp);

		sequence.push(i);

		add(sequence,temp);
		delete []temp;
	}



	for(;sequence.size()!=0;)
	{
		
		move(sequence.front(),position[sequence.front()-1]);
		sequence.pop();
	}

	cout<<"////////////////////////////Tower Z/////////////////////////////"<<endl;
	for(;tower[2].size()!=0;)
	{
		cout<<tower[2].top()<<endl;
		tower[2].pop();
	}

	


}


void Hanoi::copy(queue<int> list,int *array)
{
	for(int i=0;list.size()>0;i++)
	{
		array[i]=list.front();
		list.pop();
	}
}


void Hanoi::add(queue<int> &sequence,int *array)
{

	int count=sequence.size()-1;
	for(int i=0;i<count;i++)
	{
		sequence.push(array[i]);
	}
}

void Hanoi::move(int diskNo,char& pos)
{
	
	
	if(diskNo%2==NumOfDisk%2)
	{
		cout<<"Disk "<<diskNo<<' '<<pos<<" to "<<circle2(pos)<<endl;
		out<<"Disk "<<diskNo<<' '<<pos<<" to "<<circle2(pos)<<'\n';
		int disk=tower[(int)pos-(int)'x'].top();
		tower[(int)pos-(int)'x'].pop();
		tower[(int)circle2(pos)-(int)'x'].push(disk);

		pos=circle2(pos);
	}
	else
	{
		cout<<"Disk "<<diskNo<<' '<<pos<<" to "<<circle1(pos)<<endl;
		out<<"Disk "<<diskNo<<' '<<pos<<" to "<<circle1(pos)<<'\n';
		int disk=tower[(int)pos-(int)'x'].top();
		tower[(int)pos-(int)'x'].pop();
		tower[(int)circle1(pos)-(int)'x'].push(disk);
		
		pos=circle1(pos);
	}

}


char Hanoi::circle1(char ch)
{
	switch(ch)
	{
	case 'x':return 'y';
	case 'y':return 'z';
	case 'z':return 'x';
	}
}

char Hanoi::circle2(char ch)
{
	switch(ch)
	{
	case 'x':return 'z';
	case 'z':return 'y';
	case 'y':return 'x';
	}
}