*******************
实践教学
*******************
理工大学
软件学院
2012年春季学期
算法与数据结构 课程设计
题 目： 迷宫问题 专业班级： 姓 名： 学 号： 指导教师： 成 绩：_______________
页脚 .
摘要
在现实生活中，会遇到很多很多关于迷宫这样很复杂、很难解决的问题的问题。如果人工去解决这些问题，会很麻烦，花很长的时间，甚至无法解决。假如用计算机去解决，可以通过手动生成迷宫，也可以通过计算机随机的产生迷宫，最终退出。而且可以很快的求解迷宫，找到从入口到出口的通路，或者当没有通路时，得出没有通路的结论。找出通路之后，会显示出通路路经，而且以图示的方式显示出通路，这样会使人一目了然的看清此迷宫的通路。迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。
关键词： 迷宫；通路；二维数组；路径
页脚 .
序言
随着社会经济的发展，信息化程度的不断深入，传统的人工求解迷宫问题已不能满足生
活的需要。近几年，随着迷宫问题越来越复杂、科技也越来越发达，人们逐渐的开始用计算机求解迷宫问题。迷宫问题很复杂，但是人们又不得不去研究这个问题，因为人们的生活中需要它，离不开它。在迷宫路径的搜索过程中，首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。
页脚 .
目录
一、需求分析 ............................................................................................................................................................ 5
1.1 功能与数据需求 ........................................................................................................................................ 5 1.1.1 题目要求的功能 .................................................................................................................................... 5 1.1.2 扩展功能 ................................................................................................................................................ 5
1.2 界面需求 .................................................................................................................................................... 6 1.3 开发环境与运行需求 ................................................................................................................................ 6 二、概要设计 ............................................................................................................................................................ 7
2.1主要数据结构 ............................................................................................................................................. 7 2.2各模块函数说明 ......................................................................................................................................... 8 三、详细设计 ............................................................................................................................................................ 9 四、测试 .................................................................................................................................................................. 10 五、使用说明 .......................................................................................................................................................... 13
5.1应用程序功能的详细说明 ....................................................................................................................... 13 5.2应用程序运行环境要求 ........................................................................................................................... 13 5.3输入数据类型、格式和容限制 ............................................................................................................... 13 六、总结提高 .......................................................................................................................................................... 14
6.1课程设计总结 ........................................................................................................................................... 14 6.2开发中遇到的问题和解决方法 ............................................................................................................... 14 6.3 对自己完成课设完成情况的评价 .......................................................................................................... 14 参考文献 .................................................................................................................................................................. 15 致 .......................................................................................................................................................................... 16
页脚 .
一、需求分析
1.1 功能与数据需求
问题描述：以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
1.1.1 题目要求的功能
基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）, （1,2,2）, （2,2,2） （3,2,3）, （3,1,2）,…。
测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。
1 2 3 4 5 6 7 8 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0
1.1.2 扩展功能
（1）编写递归形式的算法，求得迷宫中所有可能的通路；
（2）以方阵形式输出迷宫及其通路
页脚 .
1.2 界面需求
请求输入进入程序 请求输入起始位置 请求输入终点位置 输出方阵迷宫 输出路径 输出方阵路径
1.3 开发环境与运行需求
Visual C++6.0
页脚 .
二、概要设计
2.1主要数据结构
输入起始位置，终点位置 判断首节点是否为通路 Y 判断路径能否走通 N 无解迷宫 Y 对坐标标记 N 选择路径 处是否 到达迷宫出口有解迷宫 输出迷宫 页脚 .
Y 左边是 否存在通路下边是 否存在通路右边是 否存在通路上边是 否存在通路 图一.主流程图
存储路径，将路径入栈
2.2各模块函数说明
typedef struct{
int pos_x[length];//进栈坐标 int pos_y[length]; int top; int base;
}Stack; //新建结构体
void initStack(Stack *p) //初始化栈
Push(Stack *p,int x,int y,int d) //入栈具体操作 Pop(Stack *p,int read[2],int d) //出栈并读出前一步的坐标 initMaze(int Maze[10][9])//建立迷宫
Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具体路径的求解 menu();//调用菜单函数 main();//实现迷宫求解的主函数
页脚 .
三、详细设计
迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按左、右、上、下4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。
每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条合适的通路；若退回到了入口处，则说明不存在合法的通路到达出口。
用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。
二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。
页脚 .
四、测试
图二.进入迷宫
页脚 .
图三.查找路径
页脚 .
图四.退出迷宫
页脚 .
五、使用说明
5.1应用程序功能的详细说明
按提示输入数字1进入迷宫，输入迷宫入口，迷宫出口
5.2应用程序运行环境要求
Microsoft Visual C++6.0
5.3输入数据类型、格式和容限制
输入的数据都是整型（int），输入迷宫的数据间要用空格或回车隔开
页脚 .
六、总结提高
6.1课程设计总结
要能很好的掌握编程,仅仅通过简单的程序的编写是无法达成的,需要大量积累和深入研究才有可能。就从这个迷宫问题求解来说,在迷宫求路径就需要使用链表的栈,靠出栈和进栈来存取路径数据.在程序的编写中也不能一味的向已有的程序进行模仿,而要自己摸索,去寻找最好的解决方法,只有带着问题去反复进行实践,才能更熟练的掌握和运用,当然,对现有的程序也要多去接触,因为有些程序是我们无法在短时间想出来的.最重要的一点是持之以恒,要经常性的复习原来接触的程序,这样才能保证我们有足够的经验去面对程序问题.
6.2开发中遇到的问题和解决方法
问题： 在开始时迷宫求解的 路径无法显示寻找路径所走的方向等问题。 解决方法：在栈中增加一个变量d来表示方向，在寻找路径的时候判断下一个坐标点和本坐标点的关系。在（x）行不变的情况下：（y+1）列加一则表示坐标往右走了一步记为1、（y-1）列减一则表示坐标往左走了一步记为3；在（y）不变的情况下：（x+1）行加一则表示坐标往下走了一步记为2、（x-1）行减一则表示坐标往上走了一步记为4；
6.3 对自己完成课设完成情况的评价
经过本次课程设计，我深刻地明白了理论与实践应用相结合的重要性，并努力克服自己在分析复杂问题的弱点。这次课程设计同时也考验我的综合运用所学知识的能力和操作能力。
页脚 .
参考文献
1 严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学. 2 严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学.
3 《DATA STRUCTURE WITH C++》. William Ford,William Topp .清华大学（影印版）.
4 谭浩强.《c语言程序设计》. 清华大学.
5．数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 铭,晓丹译 电子工业 2001 年1月
页脚 .
致
在这样的一个程序设计中，靠一个人的单打独斗是不可能完成的。在这次设计过程中，在开始的构思、设想，源代码编写时的提示，上机时精心的指点，有了老师和舍友以及身边同学的指导、意见和帮助，最终才完成了这个迷宫求解问题系统的设计与实现。所以在这里要对以上老师及同学表示感，非常感他们的帮助。而且在这次课程设计中我学习到了很多很多。
页脚 .
附录：程序源代码
#include #define d direction //用d代表所走路径的方向 int n=-1; int step=0; //记录步骤数 typedef struct{ int pos_x[length];//进栈坐标 int pos_y[length]; int top; int base; }Stack; //新建结构体 void initStack(Stack *p) { p->top=p->base=0; }//初始化栈. Push(Stack *p,int x,int y,int d) //入栈具体操作 { step++; d=0; n=n+1; p->top=p->top+1; 页脚 . p->pos_x[n]=x; p->pos_y[n]=y; } Pop(Stack *p,int read[2],int d) //出栈并读出前一步的坐标 { step++; d=0; n=n-1; p->top=p->top-1; read[0]=p->pos_x[n]; read[1]=p->pos_y[n]; } initMaze(int Maze[10][9])//建立迷宫函数. { int i; for (i=0;i<=9;i++) {Maze[0][i]=1;} for (i=0;i<=10;i++) {Maze[i][0]=1;} for (i=0;i<=9;i++) {Maze[10][i]=1;} for (i=0;i<=10;i++) {Maze[i][9]=1;} Maze[1][1]=0;Maze[1][2]=0;Maze[1][3]=1;Maze[1][4]=0;Maze[1][5]=0;Maze[1][6]=0;Maze[1][7]=1;Maze[1][8]=0; Maze[2][1]=0;Maze[2][2]=0;Maze[2][3]=1;Maze[2][4]=0;Maze[2][5]=0;Maze[2][6]=0;Maze[2][7]=1;Maze[2][8]=0; Maze[3][1]=0;Maze[3][2]=0;Maze[3][3]=0;Maze[3][4]=0;Maze[3][5]=1;Maze[3][6]=1;Maze[3][7]=0;Maze[3][8]=1; Maze[4][1]=0;Maze[4][2]=1;Maze[4][3]=1;Maze[4][4]=1;Maze[4][5]=0;Maze[4][6]=0;Maze[4][7]=1;Maze[4][8]=0; 页脚 . Maze[5][1]=0;Maze[5][2]=0;Maze[5][3]=0;Maze[5][4]=1;Maze[5][5]=0;Maze[5][6]=0;Maze[5][7]=0;Maze[5][8]=0; Maze[6][1]=0;Maze[6][2]=1;Maze[6][3]=0;Maze[6][4]=0;Maze[6][5]=0;Maze[6][6]=1;Maze[6][7]=0;Maze[6][8]=1; Maze[7][1]=0;Maze[7][2]=1;Maze[7][3]=1;Maze[7][4]=1;Maze[7][5]=1;Maze[7][6]=0;Maze[7][7]=0;Maze[7][8]=1; Maze[8][1]=1;Maze[8][2]=1;Maze[8][3]=0;Maze[8][4]=0;Maze[8][5]=0;Maze[8][6]=1;Maze[8][7]=0;Maze[8][8]=1; Maze[9][1]=1;Maze[9][2]=1;Maze[9][3]=0;Maze[9][4]=0;Maze[9][5]=0;Maze[9][6]=0;Maze[9][7]=0;Maze[9][8]=0; } Print( )//打印出迷宫界面 { int m,n,j,sum; int Maze[10][9]; printf(\"迷宫(1代表墙即不通,0代表可通过)\\n\"); printf(\" \"); for(j=1;j<=8;j++) { printf(\"%4d\printf(\"\\n\"); for(m=0;m<=10;m++) { { printf(\"%4d\for(n=0;n<=9;n++) sum++; } } } if(sum%10==0) printf(\"\\n\"); 页脚 . Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具体路径的求解函数 { int x,y; int read[2]; x=rukou_x; y=rukou_y; printf(\"第%d步:\ printf(\"(%d,%d,%d)\\n\ if(x==chukou_x&&y==chukou_y) { printf(\"到达出口坐标共走了%d步\\n\} else if(Maze[x][y+1]==0) {y=y+1;d=1;Push(p,x,y,d);Maze[x][y-1]=1;Maze[x][y]=1;} else if(Maze[x+1][y]==0) {x=x+1;d=2;Push(p,x,y,d);Maze[x-1][y]=1;Maze[x][y]=1;} else if(Maze[x][y-1]==0) {y=y-1;d=3;Push(p,x,y,d);Maze[x][y+1]=1;Maze[x][y]=1;} else if(Maze[x-1][y]==0) {x=x-1;d=4;Push(p,x,y,d);Maze[x+1][y]=1;Maze[x][y]=1;} else { Pop(p,read,d); x=read[0]; y=read[1]; if(p->top==p->base) {printf(\"找不到出口 \\n\");return 0;} 页脚 . } } Ways(p,Maze,x,y,chukou_x,chukou_y,d); return 1; menu() { printf(\"\\************************************\\n\"); printf(\"\\* 欢迎进入课程设计 *\\n\"); printf(\"\\* 迷宫求解程序 *\\n\"); printf(\"\\* 菜单: *\\n\"); printf(\"\\***进入迷宫***请输入1 *\\n\"); printf(\"\\***退出迷宫***请输入2 *\\n\"); printf(\"\\************************************\\n\"); } int main() { Stack *p; Stack S; int Maze[10][9]; //定义迷宫 int elem_1[1],elem_2[1],a,j; int rukou_x,rukou_y,d=0; int chukou_x,chukou_y; int sum=0; p=&S; initMaze(Maze); system(\"color 5f\");//dos窗口背景颜色函数 menu();//调用菜单函数 页脚 . printf(\"请输入您的选择:\"); scanf(\"%d\ if(a==1){ Print( ); //打印迷宫图 printf(\"请输入入口坐标:\"); scanf(\"%d\scanf(\"%d\ rukou_x=elem_1[0];rukou_y=elem_1[1]; printf(\"请输入出口坐标:\"); //迷宫入口坐标. scanf(\"%d\scanf(\"%d\ chukou_x=elem_2[0];chukou_y=elem_2[1];//迷宫出口坐标. if(elem_1[0]>10||elem_1[1]>9||elem_2[0]>10||elem_2[1]>9|| elem_1[0]<0||elem_1[1]<0||elem_2[0]<0||elem_2[1]<0) { printf(\"输入的入口或出口坐标错误\\n\");} //首先判断输 入坐标是否正确 else { printf(\"\\n\"); printf(\"说明(x,y,z)x,y代表坐标点;\\n\"); printf(\"z代表上个坐标到达这个坐标所走的方向,0为 初始值,1234分别代表向右、下、左、上方向\\n\"); printf(\"查找路径的具体步骤:\\n\"); initStack(p); Push(p,rukou_x,rukou_y,d); Ways(p,Maze,rukou_x,rukou_y,chukou_x,chukou_y,d); 页脚 . } system(\"pause\"); system(\"cls\"); return main(); } else{ } } system(\"pause\"); printf(\"欢迎您的再次光临,再见!\\n\"); 页脚 . 因篇幅问题不能全部显示，请点此查看更多更全内容