数据结构课程设计-迷宫问题

课程名称：数据结构题 目：迷宫设计系 别：软件学院专 业：移动设备应用开发班 级：* *****学 期：指导教师：***时 间：

数据结构课程设计

15级移动1班

2016-2017第一学期

2016年12月

目录

第一部分 需求分析 第二部分 详细设计 第三部分 调试分析 第四部分 用户手册 第五部分第六部分第七部分

测试结果 附录 参考文献

一、 需求分析

1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没有这样通路的信息。

2、可以用一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

3、编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。

4、手动设置迷宫是任意给定的，所以程序要能够对给定的迷宫生成对应的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。 5、自动生成的迷宫原理很简单，因为0和1分别代表通道和障碍物，所以只需要随机生成0和1然后再给最外围都赋值为1，就形成了新的迷宫。

二、详细设计

1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。

可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。 2、如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通。

3、所谓\"走不通\"不单是指遇到\"墙挡路\"，还有\"已经走过的路不能重复走第二次\"，它包括\"曾经走过而没有走通的路\"。

显然为了保证在任何位置上都能沿原路退回，需要用一个\"后进先出\"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。

4、若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通道块。

所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。 5、找通路的程序的关键部分可以表示如下：

do{

若当前位置可通， 则{

将当前位置插入栈顶； // 纳入路径 若该位置是出口位置，则算法结束；

// 此时栈中存放的是一条从入口位置到出口位置的路径 否则切换当前位置的东邻方块为新的当前位置； } 否则 {

若栈不空且栈顶位置尚有其他方向未被探索，

则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；

若栈不空但栈顶位置的四周均不可通，

则{ 删去栈顶位置； // 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； } }

} while (栈不空)； 6、程序中用的数据结构解析：

① 程序中用了顺序栈保存当前找到的路径，当前位置不可通时，

可以出栈，退回到前一个位置再继续探索通路，栈的定义如下：

struct SqStack {

SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL

SElemType *top; // 栈顶指针

int stacksize; // 当前已分配的存储空间，以元素为单位 }; // 顺序栈

② 栈中元素的类型结构

程序中先定义了一个表示坐标的类型结构： struct PosType // 迷宫坐标位置类型 {

int x; // 行值 int y; // 列值 };

栈中元素的类型结构如下： struct SElemType // 栈的元素类型 {

int ord; // 通道块在路径上的＂序号＂

PosType seat; // 通道块在迷宫中的＂坐标位置＂ int di; // 从此通道块走向下一通道块的＂方向＂(0～3表示东～北)

};

7、主函数的流程图

输入迷宫的行数列数（包括外墙） 设置外墙 设置内墙 显示当前的迷宫的结构 手动设置 自动生成 输入所求通路的起点终点坐标 自动生成迷宫不需要进行设置内墙一步，其他都一样。 输出没有这样的通路 显示当前含有通路的迷宫结构 输出从起点到终点的坐标

三、 调试分析

1、对于程序的设计由简单到复杂，先设计一个整体的轮廓然后再慢慢的增加程序的功能，这样能够有效的减少错误，功能慢慢的增加，在前一步的程序运行通过之后再继续增加功能，这样在检查错误的时候比较有目的性，提高写程序的效率。

2、对于程序中的错误，如果遇到说变量没有定义或者数据结构没定义的错误，可能是由于你在定义这种数据结构的变量时数据结构还没有定义，也就是说在定义此数据结构的变量的语句要放在声明这种结构体之后。

3、在写程序时要注意printf和scanf语句的格式，格式不对会得不到你想要的结果。

4、写程序时一定要瞻前顾后，前后一致，包括名称、数据类型等等。 四、用户手册

在使用程序时严格按照程序给出的提示一步一步来，下面给出程序正常执行的步骤：

1、程序会提示“请输入迷宫的行数，列数（包括外墙）：”，这时就需要输入表示迷宫的二维数组的行数和列数，需要注意的是由于我们在迷宫周围加了一道墙，所以要输入的行列数要比实际表示迷宫的行列数多两行两列。

2、程序提示“请输入迷宫内墙单元数：”，此时需要输入迷宫中墙的数目。

3、程序提示“请依次输入迷宫内墙每个单元的行数，列数：”，此

时要输入迷宫中所有墙的坐标，我们用数组中的一个元素来表示墙。 4、在输入了迷宫所有内墙的坐标后，程序会显示出迷宫的结构，然后程序会提示“请输入起点的行数，列数：”，此时需要输入所求通路的起点坐标。

5、程序提示“请输入终点的行数，列数：”，此时需要输入所求通路的终点的坐标。

6、终点坐标输入完毕之后，程序会显示出两种运行的结果，一种是输出了迷宫的结构，此时迷宫中已包含了所找的通路，用连续的数字表示出了通路在迷宫中是如何走的，此时迷宫中的-1表示找通路时走过的单元但是通路不通。

注意：再输入内墙单元的坐标是一定要细心，不要错输，也不要漏输。否则程序会出错。 五、测试结果

迷宫的测试数据如下：左上角(1，1)为入口，右下角(9，8)为出口。

1 2 3 4 5 6 7 8 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 程序的测试结果为：

1、 程序的开始界面

六、附录（附有完整的源程序） 源程序如下：

#include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0

#define OVERFLOW -2

#define STACKINCREMENT 10

#define STACK_INIT_SIZE 100//初始长度 typedef int Status;

struct PosType // 坐标竖直为x，横为y {

int x; int y; };

struct SElemType {

int ord; //序号1，2，3，4，5，6....路径的序号 PosType seat; //坐标 int di; //移动方向：上下左右 };

struct SqStack {

SElemType *base; SElemType *top; int stacksize; };

SqStack S;

#define MAXLENGTH 30

typedef int MazeType[MAXLENGTH][MAXLENGTH]; // 将数组做成地图。 MazeType m; // 宏定义，定义一个数组地图 int curstep=2; // curstep代表的是足迹，走过的路

Status InitStack(SqStack &S) {

S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));//开空间，栈底是表头

if(!S.base) exit(OVERFLOW);//检查是否开辟成功 S.top=S.base;//设为空栈

S.stacksize=STACK_INIT_SIZE;//设置长度 return OK; }

Status Pop(SqStack &S,SElemType &e)//得到栈顶元素 {

if(S.base==S.top) return ERROR;//检查是否为空栈 ，若为空则没有栈顶 e=*--S.top; //栈的特殊存储方式 return OK; }

Status StackEmpty(SqStack &S)//判断是否为空 {

if(!S.base) return ERROR;

if(S.base==S.top) return TRUE;//为空 else return FALSE; }

Status Push(SqStack &S,SElemType e)//进栈 {

if(S.top-S.base>=S.stacksize)//栈不满 { S.base=(SElemType *) realloc (S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType));//开空间 if(!S.base) exit(OVERFLOW);//检查是否开空间成功 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }

*S.top++=e;//压进栈里面 return OK; }

Status Pass(PosType a)//传参传的是当前位置的坐标 { //检查当前位置是墙还是通道 if(m[a.x][a.y]==0) { return OK; } else { return ERROR; } }

Status FootPrint(PosType a)//对已经走过的路做成标记 1，2，3，4.。。 {

m[a.x][a.y]=curstep;

}

PosType NextPos(PosType c,int di)//0-3上下左右 {

//作用是移动一个位置，所以需要传进来位置，移动方向，毕竟位移量已经确定为1

PosType direc[4]={{-1,0},{1,0},{0,-1},{0,1}};//上下左右 c.x+=direc[di].x; c.y+=direc[di].y; return c; }

void MarkPrint(PosType a)//走不通 {

m[a.x][a.y]=-1;//此路不通 }

void Print(int x,int y) //迷宫的输出 {

int i,j;

for(i=0;ifor(j=0;jif(m[i][j]==1) printf(\"■\"); else

printf(\"匚\"); } printf(\"\\n\"); } }

void Print1(int x,int y)//有通路的迷宫的输出 {

int i,j;

for(i=0;ifor(j=0;jif(m[i][j]==1) { printf(\"■\"); }

else if(m[i][j]==-1||m[i][j]==0) {

printf(\"匚\");

}

else if(m[i][j]>=2) { printf(\"☆\"); }

} printf(\"\\n\"); } }

Status MazePath(PosType start,PosType end)//找通路 {

InitStack(S);//保存可以走的路径 SElemType e;

PosType curpos=start;//curpos是指当前位置，将开始位置设为当前位置 do {

if(Pass(curpos))//如果当前位置的序号为0，即此位置不是迷宫中的墙 即为能走的路。 {

FootPrint(curpos);//留下标记 e.ord=curstep; //输出的时候的1，2，3，4，5 e.seat.x=curpos.x;

e.seat.y=curpos.y;//将当前位置信息存入e中 e.di=0;

Push(S,e);//将这一步记录，压进栈中 curstep++; //再走一步 和ord一个性质，路径的步数

if(curpos.x==end.x&&curpos.y==end.y) return TRUE;//如果已经是出口就完成栈的记录

curpos=NextPos(curpos,e.di);//否则就 走一步 }

else//如果当前位置是走过得 意思就是它的 序号不是0 {

if(!StackEmpty(S))//判断栈是不是空，不是空就后退到上一步 { Pop(S,e);//后退到上一步 curstep--; while(e.di==3&&!StackEmpty(S))// 后退直到 找到能走的路 { MarkPrint(e.seat); Pop(S,e); curstep--; } if(e.di<3)//0—3代表上下左右 {

e.di++; Push(S,e); curstep++; curpos=NextPos(e.seat,e.di);//下一步怎么移动 } } }

}while(!StackEmpty(S)); return FALSE; }

void Auto_maze(int x,int y) {

int i,j;

printf(\"\\n迷宫生成中……\\n\\n\"); system(\"pause\"); for(i=0;ivoid GenerateMaze(int x,int y)//生成迷宫地图 {

int i,j;

int x1,y1;//障碍物坐标 for(i=0;ifor(j=0;jfor(i=1;iprintf(\"输入迷宫里面阻碍物的个数:\"); scanf(\"%d\

printf(\"请输入迷宫中障碍物坐标：\\n\"); for(i=0;i{ scanf(\"%d%d\ m[x1][y1]=1; }

printf(\"************************************迷宫图**************************************\\n\"); Print(x,y);

printf(\"************************************迷宫图**************************************\\n\"); }

void Movingdirection(SElemType a)//用来显示迷宫通路怎么走的 {

switch(a.di) { case 0: printf(\"%d%3d ↑\\n\ break; case 1: printf(\"%d%3d ↓\\n\ break; case 2: printf(\"%d%3d ←\\n\ break; case 3: printf(\"%d%3d →\\n\ break; } }

void MazePathway(PosType begin,PosType end,int x,int y)//显示迷宫通路图 {

SElemType a; SqStack T; InitStack(T);

if(MazePath(begin,end)) {

printf(\"迷宫通路如下图所示:\\n\"); Print1(x,y);

while(!StackEmpty(S)) {

Pop(S,a); Push(T,a); }

printf(\"找到的路径用坐标表示如下:\\n\"); while(!StackEmpty(T))

{ Pop(T,a); Movingdirection(a); } }

else

printf(\"迷宫中没有出路。\\n\"); }

int main() {

PosType begin,end; int x,y; int n; int i,j; while(1) {

printf(\"*****************1.手动输入。*****************\\n\"); printf(\"*****************2.自动生成。*****************\\n\"); printf(\"*****************3.退 出。*****************\\n\"); printf(\"请输入：\"); scanf(\"%d\ system(\"CLS\"); switch(n) {

case 1:

printf(\"请输入迷宫的宽和长：\"); scanf(\"%d%d\ GenerateMaze(x,y);

printf(\"请输入起点的坐标：\"); scanf(\"%d%d\ printf(\"请输入终点的坐标：\"); scanf(\"%d%d\ MazePathway(begin,end,x,y); break; case 2:

printf(\"请输入迷宫的宽和长：\"); scanf(\"%d%d\ Auto_maze(x,y); for(i=0;ifor(j=0;j{ m[j][0]=1; m[j][y-1]=1; }

Print(x,y);

printf(\"请输入起点的坐标：\"); scanf(\"%d%d\ printf(\"请输入终点的坐标：\"); scanf(\"%d%d\ MazePathway(begin,end,x,y); break;

case 3: exit(-1); } }

return 0; }

七、参考文献

1、《数据结构（C语言版）》 严蔚敏 吴伟民 编著 清华大学出版社

2、讲课所用课件等等