mizmaze.cpp

迷宫算法.很好的实现栈和链表的数据结构算法

//  AUTHOR: 	Yang Zhong			 				    	
//	    	Copyright(c) 2007 	for ***			    	
//         	JianngSu University 212013           		    	
//         	[e-mail] QQ:349034589
#include "malloc.h" //malloc()
#include <stdlib.h> //rand()
#include <time.h>   //time()
#include <iostream> //cout

using namespace std;

#define NULL 0
#define false 0
#define true 1
#define LENGTH 10 //迷宫的宽度（高度）
#define STACK_INIT_SIZE (LENGTH*LENGTH) //初始化栈的长度
#define STACKINCRAEMENT (sizeof(SElemType))//栈每次增加时的长度

typedef struct MizmazeNode
{ //
	int data;  //为0时不通，为1时可能通
	bool flag; //当为false时为未该不通，true该位可通
	struct MizmazeNode *East;
	struct MizmazeNode *South;
	struct MizmazeNode *West;
	struct MizmazeNode *North;
	int TextWord; //测试保留字(元素的唯一标志)
}*Mizmaze;

typedef struct SElemType
{
	int sequence; //序号
	int seat;     //当前可行通道块日位置
	int direction;//下一个通道的方向：1为东，2为南，3为西，4为北
}*pElemStack;

typedef struct 
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

Mizmaze InitMizmaze(Mizmaze& m_pMizmaze);//建立迷宫
void OnDrawInit(Mizmaze HeadMizmazeNode);//绘制当前迷宫
bool MazePath(Mizmaze& HeadMizmazeNode); //确定迷宫可通行的路径
void InitStack(SqStack& Stack);          //初始化栈
void Push(SqStack &Stack,SElemType e);
void Pop(SqStack &Stack,SElemType &e);
bool StackEmpty(SqStack Stack);
void OnDrawResult(Mizmaze& HeadMizmazeNode,SqStack Stack);//绘制最后的结果。

	
int main()
{
	Mizmaze HeadMizmazeNode; //建立迷宫链表首指针
	Mizmaze m_pMizmaze;//定义一个迷宫链表	
	char flag =false;  //标志位，为y时重新开始	
	do 
	{
		HeadMizmazeNode = InitMizmaze(m_pMizmaze); //建立迷宫
		OnDrawInit(HeadMizmazeNode);
		MazePath(HeadMizmazeNode);	//迷宫求解
		do 
		{
			cout<<"\n还要继续进行么：(y/n)";
			cin>>flag;
		
			if (flag != 'y' || flag !='n')
			{
				cout<<"   输入错误,请重新输入：\n"<<endl;
			}
			if (flag == 'y' || flag =='n')
			{
				break;
			}	
		} while(true);
		
	} while(flag =='y');
	
	return true;
}

Mizmaze InitMizmaze(Mizmaze &m_pMizmaze)
{
	srand((unsigned)time( NULL ));//获取系统时钟随即数
	Mizmaze HeadNode;//定义头结点
	Mizmaze TempNode,NewNode;
	
	HeadNode  = (Mizmaze)malloc(sizeof(MizmazeNode));
	//初始化头结点
	HeadNode->data = 0; //第一个为0即边界为0
	HeadNode->flag = false;
	HeadNode->East = NULL;
	HeadNode->South = NULL;
	HeadNode->West = NULL;
	HeadNode->North = NULL;
	HeadNode->TextWord = 1;
	
	TempNode = HeadNode;//将头指针赋给移动指针

	for (int i=2;i<=LENGTH;i++)
	{//建立第一行LENGTH个元素的链表
		NewNode = (Mizmaze)malloc(sizeof(MizmazeNode));
		////初始化
		NewNode->data = 0; //第一行为0即边界为0
		NewNode->flag = false;
		NewNode->East = NULL;
		NewNode->South = NULL;
		NewNode->West = TempNode;//将当前结点连接到链表中
		NewNode->North = NULL;
		NewNode->TextWord = i;
		
		
		TempNode->East = NewNode;//将当前结点与连接在一起
		TempNode = NewNode; //移动指针后移一位
	}

	Mizmaze UpTempNode;  //上一行的链表结点
	Mizmaze DownTempNode;//下一行的链表结点
	TempNode = HeadNode;
	for (i=1;i<LENGTH;i++)
	{//构建从第二行到第LENGTH行

		UpTempNode = TempNode;	//TempNode在此为下移指针
		
		//每一行的第一个元素
		DownTempNode = (Mizmaze)malloc(sizeof(MizmazeNode));
		//初始化
		if (i ==1)
		{
			DownTempNode->data =1; //第二行的第一个元素置为1
		}
		else
		{
			DownTempNode->data = 0; //其于的每一行的第一个都为0。即边界为0
		}		
		DownTempNode->flag = false;
		DownTempNode->East = NULL;
		DownTempNode->South = NULL;
		DownTempNode->West = NULL;
		DownTempNode->TextWord = LENGTH*i+1;
		DownTempNode->North = UpTempNode;
		UpTempNode->South = DownTempNode;		
		UpTempNode = UpTempNode->East;//上一行的指针后移一位		
			
		for (int j=2;j<=LENGTH;j++)
		{//构建从第二列到第10列
			NewNode = (Mizmaze)malloc(sizeof(MizmazeNode));
			//初始化
			if (i ==  LENGTH-1)
			{
				NewNode->data = 0;//最后一行即边界为0
			}
			else
			{
				if (i ==1 && j==2)
				{
					NewNode->data = 1;//第二行的第二个元素置为1
				}
				else
				{
					NewNode->data =rand()%3;//取随即数0，1，2。其中1和2置为1.目的：使1出现的概率为75%，0出现的概率为25%
				}				
			}		
			NewNode->flag = false;
			NewNode->East = NULL;
			NewNode->South = NULL;	
			NewNode->TextWord = LENGTH*i+j;//迷宫每一个元素在链表中的唯一标号
			NewNode->North = UpTempNode;
			UpTempNode->South = NewNode;
			NewNode->West = DownTempNode;
			DownTempNode->East = NewNode;	

			UpTempNode = UpTempNode->East;//上层指针后移
			DownTempNode = DownTempNode->East;//下层指针后移
			if (i ==LENGTH-2 && j== LENGTH-1)
			{//倒数第二行的倒数第二个元素置为1
				DownTempNode->data = 1;
			}
		}
		
		if (i ==  LENGTH-2 &&j == LENGTH+1)
		{
			DownTempNode->data = 1;//出口为1
		}
		else
		{
			DownTempNode->data = 0;	//最后一行边界为0
		}
		
		TempNode = TempNode->South;//首行指针下移
		
	}

	return HeadNode;
}


void OnDrawInit(Mizmaze HeadMizmazeNode)
{
	Mizmaze horizontalNode;//水平方向结点
	Mizmaze VerticalNode;  //垂直方向结点
	VerticalNode=HeadMizmazeNode;

	cout<<"\n   #####迷宫问题求解######"<<endl<<endl;
	for (int i=0;i<LENGTH;i++)
	{//垂直方向下移
		cout<<"\t";
		horizontalNode = VerticalNode;
		for (int j=0;j<LENGTH;j++)
		{//水平方向右移并打印出当前数值	
			if (horizontalNode->data == 2)
			{//将数字为2的元素团置为1.得到效果：1出现的概率由50%上升到75%
				horizontalNode->data = 1;
			}
			cout<<horizontalNode->data<<"  ";			
			horizontalNode = horizontalNode->East;//水平右移
		}
		VerticalNode = VerticalNode->South;//垂直下移
		cout<<endl;		
	}
	cout<<endl;
}

bool MazePath(Mizmaze& HeadMizmazeNode)
{
	int curstep = 1;     //探索第一步
	Mizmaze CurrentNode; //迷宫当前结点
	CurrentNode = HeadMizmazeNode->South; //当前结点指向迷宫入口
	int curpose = CurrentNode->TextWord;
	SqStack Stack;       //定义一个栈
	InitStack(Stack);    //构建一个栈
	SElemType e;
	
	do 
	{		
		if (CurrentNode->data == 1 && CurrentNode->flag == false)
		{//当前位置可以通过且为未走过的点		
			CurrentNode->flag = true; //该步目前可通
			//初始化结点
			e.sequence = curstep;
			e.seat = CurrentNode->TextWord;
			e.direction = 1;
			Push(Stack,e);
			if (CurrentNode->East == NULL && CurrentNode->South->TextWord == LENGTH*LENGTH)
			{//到达最终出口
				//打印出路线图				
				OnDrawResult(HeadMizmazeNode,Stack); 
				return true;
			}
			CurrentNode = CurrentNode->East; //向东走一步
			curstep++;		
		}
		else
		{//当前结点不可通过
			if (!StackEmpty(Stack))
			{
				Pop(Stack,e);
				//当前结点不可通，退到e结点
				if (e.direction == 1)
				{//当前结点指向东，则向西退一步
					CurrentNode = CurrentNode->West;
				}
				if (e.direction == 2)
				{//当前结点指向南，则向北退一步
					CurrentNode = CurrentNode->North;
				}
				if (e.direction == 3)
				{//当前结点指向西，则向东退一步
					CurrentNode = CurrentNode->East;
				}
				if (e.direction == 4)
				{//当前结点指向北，则向南退一步
					CurrentNode = CurrentNode->South;
				}
			}
			while (e.direction == 4 && !StackEmpty(Stack))
			{//当前路径所有方向都不通。回退
				CurrentNode->flag = false;
				Pop(Stack,e);
				if (e.direction == 1)
				{//当前结点指向东，则向西退一步
					CurrentNode = CurrentNode->West;
				}
				if (e.direction == 2)
				{//当前结点指向南，则向北退一步
					CurrentNode = CurrentNode->North;
				}
				if (e.direction == 3)
				{//当前结点指向西，则向东退一步
					CurrentNode = CurrentNode->East;
				}
				if (e.direction == 4)
				{//当前结点指向北，则向南退一步
					CurrentNode = CurrentNode->South;
				}
				curstep--;
			}
			if (e.direction<4)
			{
				e.direction++;
				Push(Stack,e);
				//向前走一步
				if (e.direction == 1)
				{//向东前进一步
					CurrentNode = CurrentNode->East;
				}
				if (e.direction == 2)
				{//向南进一步
					CurrentNode = CurrentNode->South;
				}
				if (e.direction == 3)
				{//当向西进一步时，需要进一步判断
					if (e.seat == LENGTH+1)
					{//当位置为第二行的第一个元素
						CurrentNode->flag =false;
						if (e.seat ==4)						
						{//当返回时为第一步时，退出while循环	
							break;
						}
					}
					else
					{//向西进一步
						CurrentNode = CurrentNode->West;
					}										
				}
				if (e.direction ==4 )
				{//向北进一步
					CurrentNode = CurrentNode->North;
				}
			}
		}
		
	} while(!StackEmpty(Stack));
	
	//打印当前迷宫不通
	cout<<"       迷宫问题无解"<<endl;
	
	return false;

}

void InitStack(SqStack &Stack)
{
	Stack.base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	Stack.top = Stack.base;
	Stack.stacksize = STACK_INIT_SIZE;
}

void Push(SqStack &Stack,SElemType e)
{
	if (Stack.top - Stack.base >= Stack.stacksize)
	{//栈满
		Stack.base = (SElemType*)realloc(Stack.base,
			(Stack.stacksize+STACKINCRAEMENT)*sizeof(SElemType));
		
		Stack.top = Stack.base += Stack.stacksize;
		Stack.stacksize += STACKINCRAEMENT;
	}
	
	*Stack.top ++ = e;
}

void Pop(SqStack &Stack,SElemType &e)
{
	e = *--Stack.top;	
}

bool StackEmpty(SqStack Stack)
{
	if (Stack.top == Stack.base)
	{
		return true;
	}
	else
	{
		return false;
	}
}


void OnDrawResult(Mizmaze& HeadMizmazeNode,SqStack Stack)
{
	
	Mizmaze horizontalNode;//水平方向结点
	Mizmaze VerticalNode;  //垂直方向结点
	SElemType e;

	SqStack MyStack;//重新建一个栈，目的：使原来的栈逆序
	InitStack(MyStack);
	do 
	{
		Pop(Stack,e);
		Push(MyStack,e);	
	} while(!StackEmpty(Stack));
	//////////////////////////////////////////////////////////////////////////
	//测试程序
/*	do 
	{
		Pop(MyStack,e);
		cout<<e.sequence<<" ";
	} while(!StackEmpty(MyStack));
	
	//////////////////////////////////////////////////////////////////////////
*/	

	VerticalNode=HeadMizmazeNode->South;//指向第二行第一个元素，即入口
	do 
	{
		a:if (!StackEmpty(MyStack))
		{
			Pop(MyStack,e);
		}
		  else
		  {
			  goto b; //栈为空时转到输出
		  }
		for (int i=1;i<LENGTH;i++)
		{//垂直方向下移
			horizontalNode = VerticalNode;
			for (int j=0;j<LENGTH;j++)
			{//水平方向右移并打印出当前数值
				
				if (e.seat == horizontalNode->TextWord)
				{//当前栈内的位值与迷宫的位置相同时，说明当前结点是可通的结点。加2标注
					horizontalNode->data = e.sequence;
					goto a;
				}
				horizontalNode = horizontalNode->East;//结点右移
			}
			VerticalNode = VerticalNode->South;	//结点下移
		
		}
		
	} while(1);


//////////////////////////////////////////////////////////////////////////
//显示最后的结果
b:VerticalNode=HeadMizmazeNode;
  
	cout<<endl;
	for (int i=0;i<LENGTH;i++)
	{//垂直方向下移
		cout<<"\t";
		horizontalNode = VerticalNode;
		for (int j=0;j<LENGTH;j++)
		{//水平方向右移并打印出当前数值
			if (horizontalNode->data >= 10 && horizontalNode->data<=100 && horizontalNode->flag == 1)
			{				
				cout<<horizontalNode->data<<" ";											
			}
			else
			{
				cout<<horizontalNode->data<<"  ";			
			}			
			horizontalNode = horizontalNode->East;
		}
		VerticalNode = VerticalNode->South;
		cout<<endl;		
	}
	cout<<"     -^-迷宫问题有解-^-\n";	
}