（毕业论文 字数：2260 页数：20 带程序）摘要：本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中要应用“栈”的思想。

目录
一、 问题描述和分析　…………………………………………………………1
二、 数据结构设计　……………………………………………………………1
三、 算法设计　…………………………………………………………………2
四、 源代码说明　………………………………………………………………2
五、 结果与分析　………………………………………………………………15
六、 参考文献　…………………………………………………………………17

一、 问题描述和分析
首先，在计算机中可以用方块图表示迷宫。每个方块或为通道，或为墙。所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。
假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置四周4个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。

二、 数据结构设计
1. 数据结构设计考虑
1) 建立一个二维数组表示迷宫的路径（0表示通道，1表示墙壁）；
2) 创建一个栈，用来存储“当前路径”，即“在搜索过程中某一时刻所在图中某个方块位置”。
2. 逻辑结构存储结构
1) 创建一个Int类型的二维数组Maze(i,j),用来存放0和1 ；
2) 创造一个栈包括（*top表示栈顶，*base表示栈基址，stackSize表示栈容量）
堆栈中每个空间包括（ord表示当前位置在路径上的序号，seat表示当前坐标，di表示往下一坐标的方向）当前坐标包括（r表示行，c表示列）

三、 算法设计
设定当前位置的初值为入口位置；
do{
若当前位置可通，
则{将当前位置插入栈顶；
若该位置是出口位置，则结束；
否则切换当前位置的东邻方块为新的当前位置；
}
否则，
若栈不空且栈顶位置尚有其他方向未经探索，
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则{删去栈顶位置；
若栈不空，则重新测试新的栈顶位置，
直到找到一个可通的相邻块或出栈至栈空；
}
}while（栈不空）；
在此，尚需说明一点的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入过路径的通道块（否则只能在死胡同内转圈）。
四、 源代码说明
#include <windows.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <list>
#include <stack>
#include <time.h>
using namespace std;

//class:MazePos-----------------------------------------
class MazePos
{
public:
int wx,ly;
int path;
bool pass;
bool operator==(const MazePos pos)
{
return (wx==pos.wx && ly==pos.ly );
};
MazePos operator=(const MazePos pos)
{

wx=pos.wx;
ly=pos.ly;
pass=pos.pass;
path=pos.path;
return *this;
};
};

//辅助栈元素类型
class SElemType
{
public:
int ord;
MazePos seat;
int di;
bool operator==(const SElemType et)
{
return (seat==et.seat);
};
SElemType operator=(const SElemType et)
{
ord =et.ord ;
seat =et.seat ;
di =et.di ;
return (*this);
};
};

#define MAPWIDTH 10
#define MAPHEIGHT 10
typedef struct MazeMap
{ MazePos mazemap[MAPWIDTH][MAPHEIGHT];
}MazeMap;


typedef struct MazeWay
{
int wx,ly;
}MazeWay;

class Maze
{
public:
Maze(int width=MAPWIDTH,int height=MAPHEIGHT);
~Maze();
void DoMaze();
private:
bool InitOK;
MazeMap map;
MazePos start,end;
bool FindPath();
list<MazeWay> mazeway;
void RandMap();
bool CreateMap(bool init);
bool pass(MazePos curpos);
MazePos NextPos(MazePos curpos,int di);
bool Invalide(SElemType e);
void DisplayMaze(); //显示迷宫地图
};
Maze::Maze(int width,int height)
{

CreateMap(true);

DisplayMaze();
}
Maze::~Maze()
{
//Add codes here
}
bool Maze::FindPath ()
{ if(InitOK)
{
//MazeStack mstack;
stack<SElemType,list<SElemType> > mstack;
MazePos curpos=start;
int curstep=1;
MazeWay mw;
unsigned mwsize=mazeway.size ();
do
{
if(pass(curpos))
{

SElemType e;
e.ord =curstep;
e.seat =curpos;
e.di =1;
mstack.push (e);

mw.wx =e.seat .wx ;
mw.ly =e.seat .ly ;
mazeway.push_back (mw);


if(curpos==end)
return true;

curpos=NextPos(curpos,e.di );
curstep++;
}
else
{

if(!mstack.empty())
{
SElemType e;
e=mstack.top ();
mstack.pop ();

//调整出口路径链表
mazeway.pop_back ();
while((e.di==0 || e.di ==4) && !mstack.empty ())
{
Invalide(e); //标记刻通道块不能通过
e=mstack.top ();
mstack.pop (); //退回一步
//调整出口路径链表
mazeway.pop_back ();
}
if(mstack.empty ())
return false;
else if( e.di<5)
{
e.di++;
e.di=e.di%5;
mstack.push (e);
//保存当前位置到出口路径链表
mw.wx =e.seat .wx ;
mw.ly =e.seat .ly ;
mazeway.push_back (mw);
curpos=NextPos(e.seat ,e.di );
}

}
}
///*//显示运行过程
if(mwsize!=mazeway.size () )
{
CreateMap(false);
DisplayMaze();
mwsize=mazeway.size ();
Sleep(800); //要包含windows.h头文件
}
//*
}while(!mstack.empty ());
}
return false;
}
MazePos Maze::NextPos(MazePos curpos,int di)
{
//
MazePos pos;
switch(di)
{
case 1:
pos=map.mazemap [curpos.wx+1][curpos.ly ] ;
break;
case 2:
pos=map.mazemap [curpos.wx][curpos.ly+1 ] ;
break;
case 3:
pos=map.mazemap [curpos.wx-1][curpos.ly] ;
break;
case 4:
pos=map.mazemap [curpos.wx][curpos.ly-1] ;
break;
}
return pos;
}
bool Maze::pass(MazePos curpos)
{

if(curpos.wx <0 ||
curpos.wx >=MAPWIDTH ||
curpos.ly <0 ||
curpos.ly >=MAPHEIGHT)
return false;
return (map.mazemap [curpos.wx ][curpos.ly ].path ==0 &&
map.mazemap [curpos.wx ][curpos.ly ].pass ==false );

}
void Maze::DoMaze ()
{
//
if(!InitOK)
return;
if(FindPath())
{
CreateMap(false);
DisplayMaze();
}
else
{
cout<<endl<<"NO PATH!"<<endl;
}
}
void Maze::RandMap ()
{
//

MazeWay curway;
list<MazeWay> mw;
list<MazeWay>::iterator iter;
curway.wx =0;
curway.ly =1;
mw.push_back (curway);
curway.wx ++;
mw.push_back (curway);
srand(time(0)); //取得当前时间作为随机数种子
while(curway.wx <MAPWIDTH-1 && curway.ly <MAPHEIGHT-1)
{
if(rand()%2==1)
{
//生成随机X坐标上的路径块
curway.wx ++;

mw.push_back (curway);
}
else
{
//生成随机Y坐标上的路径块
curway.ly ++;
mw.push_back (curway);
}
}
srand(time(0));
for(int y=0;y<MAPHEIGHT;y++)
{
for(int x=0;x<MAPWIDTH;x++)
{
//填充每个通道块
map.mazemap [x][y].wx =x;
map.mazemap [x][y].ly =y;
map.mazemap [x][y].pass =false;
if(x==0||y==0||x==MAPWIDTH-1||y==MAPHEIGHT-1)
{
//生成四周墙壁
map.mazemap [x][y].path =-1;
//map.mazemap [x][y].pass =true;
}
else
{
if(rand()%10>=6) //数值越小,墙壁越多
{
map.mazemap [x][y].path =-1; //随机生成墙壁
//map.mazemap [x][y].pass =true;
}
else
{
map.mazemap [x][y].path =0; //生成空的通道块
//map.mazemap [x][y].pass =false;
}
}
}
}
//生成出口路径
for(iter=mw.begin ();iter!=mw.end ();iter++)
{
map.mazemap [(*iter).wx ][(*iter).ly ].path =0;
//map.mazemap [(*iter).wx ][(*iter).ly ].pass =false;
}
//生成入口和出口
start=map.mazemap [mw.front ().wx][mw.front ().ly];
end=map.mazemap [mw.back ().wx][mw.back ().ly];
//初始化成功
InitOK=true;
}
bool Maze::CreateMap (bool init)
{
//
if(init)
{
RandMap();
}
else
{
for(int y=0;y<MAPHEIGHT;y++)
for(int x=0;x<MAPWIDTH;x++)
{
if(map.mazemap [x][y].path ==0)
map.mazemap [x][y].pass =0;
}
list<MazeWay>::iterator iter;
for(iter=mazeway.begin ();iter!=mazeway.end ();iter++)
{
map.mazemap [(*iter).wx][(*iter).ly ].path =1;
}
}
return true;
}
bool Maze::Invalide (SElemType e)
{