源代码.txt

本程序的功能是找出指定迷宫的路径

//程序名：labyrinth.cpp
//      程序功能：迷宫通路寻找的实现
//          作者：黄秋旋
//          日期：2008.12.20
//          版本：1.0
//      修改内容：
//      修改日期：
//      修改作者：
//对应类实现文件: labyrinth.h
//                Stack.h

#include"labyrinth.h"


////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：主函数
//函数返回值：无

void main()
{
	int i,j;
	char ch;
choice:cout<<"是否重新输入迷宫：Y/y：是，N/n：否 \n请选择（Y/N）：";     //选择是否重新输入迷宫
	cin>>ch;
	if(ch=='Y' || ch=='y') //选择重新输入迷宫     
	{
		cout<<"\n请输入8行10列的迷宫矩阵，其中最外层均为“1”!\n";
lg:for(i=0;i<m+2;i++)        //输入迷宫
			for(j=0;j<n+2;j++)
			{
				cin>>maze[i][j];
				mark[i][j]=0;       //初始化未访问标志
			}//for
	}//if:选择Y

	else if(ch=='N' || ch=='n')//选择从文件中读入迷宫
	{
		ifstream fip;
		fip.open("labyrinth.txt",ios::in|ios::binary);   //打开文件
        if(fip.fail())  //打开失败
		{
			cout<<"文件不存在！请重新输入迷宫！";
			goto lg;   //回到if重新输入迷宫
		}//else if 

		int in;
			for(i=0;i<m+2;i++)
			{
				for(j=0;j<n+2;j++)
				{     
					fip>>in;      //读取迷宫数据
					maze[i][j]=in;
					cout<<maze[i][j]<<' ';   //输出迷宫
                    mark[i][j]=0;    //初始化未访问标志
				
				}//for
				cout<<endl;
			}//for
		
		fip.close();   //关闭文件
	}//else if
	else   //输出错误，提示重新输入
	{
		cout<<"请重新输入你的选择！"; 
		goto choice;    //重新选择读入迷宫的方式
	}//else
	cout<<"(x,y,d)中的x，y分别表示迷宫中的坐标!"<<endl<<endl;
	cout<<"0: 向↓,1: 向↘,2: 向→, 3：向↖"<<endl<<endl;      
	cout<<"4: 向↑,5: 向↖,6: 向←, 7: 向↘" <<endl<<endl;         
	cout<<"有两种方式输出迷宫路径，"<<endl<<endl;
	cout<<"Y/y:逆序（递归算法）,N/n:顺序（非递归非递归）! \n";
    cout<<"\n请输入你的选择： ";   
choice1:cin>>ch;     //选择想调用的算法
	cout<<endl;
	
	if(ch=='N' || ch=='n')   //选择非递归算法
	{
		cout<<"采用顺序输出迷宫路径: \n";
		cout<<"\nd 表示做到下一个坐标的方向!\n";
	    cout<<"\n路径为：\n";
		Seek();    //调用寻路非递归函数
	}
     else if(ch=='Y' || ch=='y')   //选择递归算法
	 {
		 cout<<"采用逆序输出迷宫路径! \n";
		 cout<<"\nd 表示从前一个坐标走到该坐标的方向\n";
		 cout<<"\n路径为：\n";
                 mark[1][1]=1;    //加访问标志      
         if(Seekd(1,1))   //调用递归时用	
	     cout<<"("<<1<<","<<1<<")"<<endl;       //寻找到通路时，输出迷宫入口处的坐标	
	 }//else if
	 else  //输出错误，提示重新输入
	 {
		 cout<<"\n输入错误，请重新输入你的选择：";
		 goto choice1;     //重新选择算法
	 }
                    
}


????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
//程序名：labyrinth.h
//程序功能：寻找迷宫通路的实现程序
//作者：黄秋旋
//日期：2008.12.20
//版本：1.0
//修改内容：
//修改日期：
//修改作者：
//对应类实现文件: Stack.h
//对应主程序文件: labyrinth.cpp


#include<iostream.h>
#include"Stack.h"
#include<fstream.h>

#define m 6    //定义迷宫常量：m: 迷宫行数
#define n 8    //              n:迷宫列数
              
int mark[m+2][n+2];    //保存访问标记的数组
int maze[m+2][n+2];    //保存迷宫数据的数组
int move[8][2]={       //方向数组
	              {0,1},  //  向↓
	              {1,1},  //  向↘
	              {1,0},  //  向→
	              {1,-1}, // 向↗
               	  {0,-1}, // 向↑
	              {-1,-1},//向↖
	              {-1,0}, // 向←
				  {-1,1}  //  向↘
                 };               


///////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：寻找迷宫路径的递归算法
//函数功能：用递归寻找迷宫的通路
//函数参数：x:当前通路位置的横坐标
//          y:当前通路位置的纵坐标
//参数返回值：true:表示当前位置可访问时的返回值
//            false: 表示查找通路失败时的返回值

bool Seekd(int x,int y)               
{
	int i;
	int g,h;
	if((x==m)&&(y==n))   //当前位置是迷宫出口时，返回上一层递归函数
		return true;
	for(i=0;i<8;i++)    
	{
		g=x+move[i][0];                     //求出下个一位置的行、列坐标
		h=y+move[i][1];
	    if((maze[g][h]==0)&&(mark[g][h]==0))
		{
			mark[g][h]=1;                    //置mark为1，表明已访问过
		    if(Seekd(g,h))
			{
			    cout<<"("<<g<<","<<h<<","<<i<<") ";  //当下一个坐标位置可访问时，输出通路
		        return true;   //返回上一层递归函数
			}//if
		}//if
	}//for
   if((x==1)&&(y==1))  //当找不到通路时，输出提示
    	cout<<"No path!"<<endl;
   return false;    //寻找通路失败，返回false
}


////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：寻找迷宫路径的非递归算法
//函数功能：利用栈，找出迷宫的通路
//函数参数：无
//参数返回值：无

void Seek()                             
{ 
    Type item;
	mark[1][1]=1;   //访问入口处坐标
	Stack s;  //逆序暂存通路信息的栈
	Stack s1; //顺序存储通路信息

	item.x=1; item.y=1; item.d=-1;        //将入口位置及方向初值-1压入栈
	s.push(item);

	while(!s.empty())   //当栈不为空时
	{	
		item=s.top();  //取出栈顶元素，寻找从改坐标出发的下个一通路坐标
		s.pop();

		int x=item.x; int y=item.y; int d=item.d+1;         //沿原位置的下个一方向前进

		while(d<8)  //深度寻找迷宫通路
		{

			if((x==m)&&(y==n))          //到达出口，将栈s中的元素逆序压入栈s1中，然后从按顺序输出，最后返回
			{
				item.x=x;
	        	item.y=y;
		        item.d=NULL;
		        s1.push(item);      //将通路坐标压入栈s1
         
			    while(!s.empty())    //将栈s中的元素逆序
				{
					item=s.top();
                    s.pop();
                    s1.push(item);   
				}//while
                 while(!s1.empty())  //输出通路
				{
					item=s1.top();
                    s1.pop();
					if((item.x==m)&&(item.y==n))
						cout<<"("<<item.x<<","<<item.y<<") ";  //输出迷宫出口坐标
					else
						cout<<"("<<item.x<<","<<item.y<<","<<item.d<<") ";      //输出通路
				 }//while
			cout<<endl;
			return;  //输出完成，返回
			}//if

			int g=x+move[d][0];                  //按方向d前进，求出下一个位置的坐标
	        int h=y+move[d][1];

			if((maze[g][h]==0)&&(mark[g][h]==0))          //对未访问的可通行的下一个位置压入栈，并将下一个位置变为当前位置，否则沿下一个方向前进
	
			{
				mark[g][h]=1;  //访问标志
                item.x=x;
	        	item.y=y;
		        item.d=d;
		        s.push(item);      //将通路坐标暂存入栈s

				x=g;
	        	y=h;
		        d=0;                  //进入新位置后，重新从初始方向向下开始                   
			}//if
			else
				d++;  //试探下一个方向的坐标
		}//while
	}//while

cout<<"No path!"<<endl;      //不存在通路
}//Seek


????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????
//程序名：Stack.h
//程序功能：栈类的头文件
//作者：黄秋旋
//日期：2008.12.20
//版本：1.0
//修改内容：
//修改日期：
//修改作者：
//对应类实现文件: labyrinth.h
//对应主程序文件: labyrinth.cpp



#include<iostream.h>
#include<stdlib.h>

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


struct items         //存储通路坐标信息的结构体
{
	int x,y,d;
};

typedef items Type;


struct Node         //栈节点的结构体
{
	Type data; 
	Node *next;
};

class Stack      //栈类定义
{
private:
	Node *atop;

public:
	Stack(){atop=NULL;};  //构造函数
	~Stack();   //析构函数
	Type top();  //取栈顶函数
	void pop();  //出栈函数
	bool empty();  //判空函数
	bool push(Type& x);  //压栈函数
};


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：析构函数
//函数功能：释放栈类的空间
//函数参数：无
//参数返回值：无

Stack::~Stack()
{
	Node *p;
	while(atop!=NULL)
	{
		p=atop;
		atop=atop->next;
		delete p;  //释放节点p的空间
	}//while
};


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：取栈顶元素
//函数功能：取出栈顶元素
//函数参数：无
//参数返回值：atop->data ：栈顶元素的数据

Type Stack::top()
{
	if(atop==NULL)
		exit(1);
	else
		return (atop->data);     //返回栈顶元素的内容
};


/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：出栈函数
//函数功能：使栈顶元素出栈
//函数参数：无
//参数返回值：无

void Stack::pop()
{
	if(atop==NULL) exit(1);  //当栈为空时，正常退出
	else 
	{
	    atop=atop->next;  //栈顶指针指向下一个元素
	}
};


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：判空函数
//函数功能：判断栈是否为空
//函数参数：无
//参数返回值：bool：当栈为空时返回，否则返回0

bool Stack::empty()
{
	return atop==NULL;
};


////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//函数名：压栈函数
//函数功能：将通路数据压入栈中
//函数参数：Type &x:表示按引用方式，将通路的实参传给函数
//参数返回值：bool：压栈完成时返回true

bool Stack::push(Type &x)
{
	Node *p;
	p=new Node;  //为节点指针p申请空间
	p->data=x;  //将通路信息赋给p的数据域
	p->next=atop;  //用头插入的方式将节点p插入到栈链中
	atop=p;  //栈顶指针指向p
    return true;  //压栈完成，返回true
};