枣 庄 学 院 信息科学与工程学院 课程设计任务书
题目： 迷宫求解课程设计
学 号：
姓 名： 专 业： 网络工程 课 程： 数据结构 指导教师： 职称：
完成时间： 2011 年 12 月----20 11 年 12 月
枣庄学院信息科学与工程学院制
年 月 日
第 1 页 共 26 页
课程设计任务书及成绩评定
课程设计的任务和具体要求 根据课堂讲授内容，学生做相应的自主练习，消化数据结构课堂所讲解的内容；通过调试典型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力、团体合作能力。 它的任务就是训练学生对计算机数据对象进行分析的能力，选择适当的数据结构及相关算法的能力。 此程序的任务是实现把能走的最短路找到，并很直观的显示在屏幕上的功能。 指导教师签字： 、 日期： 指导教师评语 成绩： 指导教师签字： 日期： 第 2 页 共 26 页
课程设计所需软件、硬件等 电脑、C++6.0 课程设计进度计划 起至日期 工作内容 备注 参考文献、资料索引 序号 文献、资料名称 编著者 出版单位 [1] 数据结构 蒋秀英，栾晓春，燕孝飞 中国石油大学出版社 [2] 数据结构(C语言版)[M], 严蔚敏等 清华大学出版社 [3] 数据结构－用面向对象方法与C++描述， 殷人昆等 清华大学出版社 [4]http://www.programfans.com 编程爱好者网站（迷宫问题） [5]编程论坛http://bbs.bccn.net/thread-247790-1-7.html（迷宫问题） 第 3 页 共 26 页
目 录
摘 要 ................................................................... 2 1引 言 .................................................................. 3 2设计目的与任务 .......................................................... 3
2.1设计目的是 ......................................................... 3 2.2设计任务是 ......................................................... 4 3设计方案与实施 .......................................................... 4
3.1总体设计思想 ....................................................... 4 3.2设计流程图 ......................................................... 5 3.3详细设计 ........................................................... 6 3.4程序清单 ........................................................... 6 3.5程序调试与体会 ..................................................... 6 3.6运行结果（截图） ................................................... 7 结 论……………………………………………………………………………… ……… 15 致 谢 ................................................................... 15
第 4 页 共 26 页
摘 要
随着计算机的高速发展，计算机能很简便地解决很多问题。C语言编程也是解决问题的一种语言。而此我们的数据结构程序设计是解决迷宫问题。求迷宫(老鼠吃奶酪)中从入口到出口的路径是一个经典的程序设计问题。“数据结构”成为计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其它理工专业的热门选修课。主要包括线性表、树和二叉树以及图等基本类型的数据结构。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科，包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容，其中逻辑结构可分为线性结构和非线性结构；存储结构可分为顺序存储和链式存储两类，图则属于逻辑结构中的非线性结构。广度优先搜索(BFS)用的队列一步一步完成的，从而找到的是最短路径。
关键词：队列，广度优先，搜索，最短路径，遍历
1引 言
《数据结构》是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和比较，内容非常丰富。
本课程设计我们要解决的问题是图迷宫求解问题。本需要用到栈的相关数据结构。但我们这个程序没有用栈，而是用队列替代栈的功能，使程序运行效率更加高。还用到求迷宫问题最平常的数据结构算法，即广度优先搜索算法(BFS)，还保持了它的路径，再从串中输出图。
本课程设计总的思路要解决的问题是构造迷宫，寻找路线，打印路径。我们首先要做的是创建一个二维数组，用以来存储图，然后我们要想好怎样利用BFS算法来寻找路线。把这个算法以及其他过程写成调用函数，各自调用后调试程序。达到满意结果后写报告。
第 5 页 共 26 页
2设计目的与任务
2.1设计目的是
根据课堂讲授内容，学生做相应的自主练习，消化数据结构课堂所讲解的内容；通
过调试典型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力、团体合作能力。
2.2设计任务是
它的任务就是训练学生对计算机数据对象进行分析的能力，选择适当的数据结构及相关算法的能力。 此程序的任务是实现把能走的最短路找到，并很直观的显示在屏幕上的功能。
3设计方案与实施
3.1总体设计思想
(1) 迷宫形状由0表示可通过，用1表示是障碍。为方便用0,1输入。并把迷宫图形保存在二维数组Map中。而打印出的图形中 ‘●’表示能过‘□’表示障碍.
(2) 对探索过的位置加以标记Used[][]，输入起点终点后可由BFS（）来完成搜索。到目的点就可退出该调用程序。把每步路径保存到Mark[][]内，通过反向进行退步可把完整的路径保存在结构体result数组re[][]内，通过标记的路径可将串str作相应的改变就能输出的带路径的图。
(3) 根据二维字符数组和加标记的位置坐标，输出迷宫的图形。
(4) 该程序在获取迷宫图结构后，可对迷宫任意入口到出口的路线进行搜索，主要由广度优先搜索完成该操作。它可以是100以内大小的迷宫，有自行提供的迷宫图，本课程设计是以二维数组作为迷宫的存储结构。而广度优先搜索(BFS)用的队列一步一步完成的，从而找到的是最短路径；该程序还能选择是4方向还是8方向的迷宫走法。并能输出打印
第 6 页 共 26 页
3.2设计流程图
输入迷宫图形 显示迷宫图形 输入起点终点 是否符合题意 输出路径节点 输出迷宫路线 是否继续？ 是否更换迷宫 开始
结束
3.3详细设计
struct Point {int x,y,s;}
这个结构体是用来做广度搜索的对每个迷宫节点有相应的s(最短的步数，当然有些是不可达的)
第 7 页 共 26 页
int move[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}} ;// int BFS(int step)// 广度搜索用来算出最短路径的走法 并将走法保存在re数组结构体中
int Initialization()// 将str[][]图形初始化 int Format_Limit()//图形打印格式限制 int Print_Maze_Figure()//打印出图形 int PPMF()// 打印出迷宫图形
int Save_Path()// 将路径保存在str[][]中并打印出路径迷宫图形 int Init()// 从文件中植入数据 完成对Map迷宫图的结构 int Judge()//判断输入的起点终点是否符合实际 int main()//对上面函数的结合应用
3.4程序清单
#include #include int rx,ry; }re[100*100]; int ri=-1; struct Point { int x,y,s; }s,t;//s代表起点 t代表终点 int mark[100][100]; //用来标记怎么走到这个地方的 (保存的是方向的序号):0,1,2,3,4,5,6,7 bool Used[100][100];//标记已经走过的地方 bool Map[100][100];//输入0，1表示迷宫 int move[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}} ;// 第 8 页 共 26 页 int n,m; int BFS(int step) // 广度搜索用来算出最短路径的走法 并将走法保存在re结构体中 { queue while(!My.empty())My.pop(); My.push(s); Point temp,s1; while(!My.empty()) { s1 = My.front(); My.pop(); if(s1.x == t.x&&s1.y==t.y) { } for(int i =0 ;i < step ; i++) 第 9 页 共 26 页 int u; re[++ri].rx=s1.x; printf(\"到目的地了\\n步数:%d\\n(%2d,%2d) <- \for(int j = 1 ;j <= s1.s;j++) { } printf(\"\\n\"); system(\"pause\"); return 1; u = s1.x; s1.x = s1.x - move[ mark[s1.x][s1.y]][0]; s1.y = s1.y - move[ mark[u][s1.y] ][1]; re[++ri].rx=s1.x; printf(\"(%2d,%2d) <- \if((j+1)%5==0)printf(\"\\n\"); re[ri].ry=s1.y; re[ri].ry=s1.y; system(\"cls\"); { temp.x = s1.x + move[i][0]; temp.y = s1.y + move[i][1]; temp.s = s1.s; if(temp.x<0||temp.x>=n||temp.y<0||temp.y>=n||Used[temp.x][temp.y]||Map[temp.x][temp.y]) continue; else { mark[temp.x][temp.y] = i; temp.s += 1 ; My.push(temp); Used[temp.x][temp.y] = true; } } } printf(\"不好意思,起点至终点无路径不可达!!!!\\n\"); return 0; } char str[256*256][3]; //串保存图 int Initialization()// 将str[][]图形初始化 { int i1,j1,xj; for(i1=0;i1<256*256;i1++) strcpy(str[i1],\" \"); for(i1=0;i1 strcpy(str[2*i1*(2*n-1)+j1],\"□\"); } 第 10 页 共 26 页 } return 1; } int Format_Limit()//图形打印格式限制 { for(int i =0; i <35-2*n&&(35-2*n)>0;i++) printf(\" \"); return 1; } int Print_Maze_Figure()//打印出图形 { int i,xi,xj; Format_Limit(); for(i =0 ;i <= n*2;i++) printf(\"□\"); printf(\"\\n\"); for(xi=0,xj=0;xj<((2*n-1)*(2*n-1));xj++,xi++) { if(0 == xi) { Format_Limit(); printf(\"□\"); } printf(\"%s\ if(xi==2*n-2) { printf(\"□\\n\"); xi=-1; } } Format_Limit(); for(i =0 ;i <= n*2 ;i++) printf(\"□\"); printf(\"\\n\"); return 1; 第 11 页 共 26 页 } int PPMF()// 打印出迷宫图形 { } int Save_Path()// 将路径保存在str[][]中并打印出路径迷宫图形 { printf(\"\\\ [迷宫路径图]\\n(%d,%d)至(%d,%d)\\ ●表可走，□表不可Initialization(); strcpy(str[2*s.x*(2*n-1)+2*s.y],\"起\"); strcpy(str[2*t.x*(2*n-1)+2*t.y],\"终\"); for(int wri=0;wri printf(\"\\\\[迷宫为]\\n\\\ ●表可走，□表不可走 \\n\"); Initialization(); Print_Maze_Figure(); return 1; if(re[wri].rx strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-1)+2*re[wri].ry],\"↓\"); if(re[wri].rx==re[wri+1].rx&&re[wri].ry>re[wri+1].ry) strcpy(str[2*re[wri].rx*(2*n-1)+2*re[wri].ry-1],\"→\"); if(re[wri].rx strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)+1+2*re[wri].ry],\"\"); if(re[wri].rx ↗ strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)-1+2*re[wri].ry],\"\"); if(re[wri].rx>re[wri+1].rx&&re[wri].ry 第 12 页 共 26 页 strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-2)+2*re[wri].ry],\"↙\"); strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-1)-1+2*re[wri].ry],\"\"); } } //队列 int Init()// 从文件中植入数据 完成对Map迷宫图的结构 { } int Judge()//判断输入的起点终点是否符合实际 { bool flag = true; if(s.x<0||s.x>=n||s.y<0||s.y>=n){printf(\"起点越界,不符合!\\n\");flag = else if(t.x<0||t.x>=n||t.y<0||t.y>=n){printf(\"终点越界,不符合!\\n\");flag = else if(Map[s.x][s.y]){printf(\"起点是墙,不符合!\\n\");flag = false;} else if(Map[t.x][t.y]){printf(\"终点是墙,不符合!\\n\");flag = false;} else if(s.x==t.x&&s.y==t.y){printf(\"起点是终点,不符合!\\n\");flag = false;} if(!flag) { printf(\"是则再输入\\\\否则退出程序:(Y/N)\\n\"); 第 13 页 共 26 页 ↘ Print_Maze_Figure(); return 1; FILE *pf;int i,j; pf = fopen(\"maze.txt\if(pf==NULL)return 0; fscanf(pf,\"%d\for(i = 0;i < n; i++) for(j = 0 ; j < n; j++) { } fclose(pf); return 1; Used[i][j] = false; fscanf(pf,\"%d\ false;} false;} } int main() { char ch; int i,j,step; printf(\"\\\<请按提示操作>\\n\"); system(\"cls\"); printf(\"是否使用系统提供的迷宫图:(Y/N)\\n\"); ch = getch(); if(ch == 'Y'||ch =='y') { } bool flag=true; while(flag) {for(i =0 ;i < n;i++) for(j =0 ;j < n ;j++) Used[i][j] = false; printf(\"请输入迷宫的大小:(n*n)\"); scanf(\"%d\ printf(\"\请输入迷宫的结构0,1表示0是路1是墙\\n\"); for(i = 0;i < n; i++) for(j = 0 ; j < n; j++) { Used[i][j] = false; } scanf(\"%d\ Init(); else } return 2; char ch[20]; scanf(\"%s\ if(ch[0] == 'Y'||ch[0] =='y')return 1; else return 0; next:system(\"pause\"); ri = -1; 第 14 页 共 26 页 system(\"pause\"); system(\"cls\"); printf(\"是否显示原始迷宫:(Y/N)\\n\"); ch = getch(); if(ch == 'Y'||ch =='y') PPMF(); again: printf(\"请输入起点与终点:(x1 y1 x2 y2)\"); scanf(\"%d %d %d %d\ if(1==Judge())goto again; else if(0==Judge())break; printf(\"请选择4方向还是8方向的迷宫:\"); scanf(\"%d\ if(8==step)step=8; else step = 4; system(\"pause\"); system(\"cls\"); BFS(step); Save_Path(); printf(\"是否继续(Y/N)\\n\"); ch = getch(); if(ch != 'Y'&&ch !='y') flag = false; if(flag) { printf(\"是否更换迷宫(Y/N)\\n\"); ch = getch(); if(ch == 'Y'||ch =='y') goto next;} } return 0; } /*测试例子 5 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 第 15 页 共 26 页 0 1 1 1 1 0 0 0 0 0 0 0 4 4 4 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 6 4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 第 16 页 共 26 页 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 15 15 8 0 0 14 0 8 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 7 9 8 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 11 0 15 4 0 11 0 15 8 0 2 14 12 4 0 2 14 12 8 0 0 0 15 4 0 0 0 15 8 第 17 页 共 26 页 */ 3.5程序调试与体会 调试：经过几天的努力，课程设计终于完成，由于我对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编写程序的过程中出现了一些问题。对于打字有时粗心导致出现一些难以发现的小错误，在我的耐心，细致的调试下最终使得程序能够运行，课程设计完满完工。 1、问题一：求出起点到终点的路径 现象：求出的结果总是无任何现象 原因：把相关重要的变量重复定义以至赋过的值被覆盖 2、问题二：常量转义字符 现象：出现不正常字符常量 原因：'\\'字符常量形式弄错 3、问题三：输入起点终点时，未判断下标越界就使用数据 现象： 原因：未判断下标越界就使用数据 体会：在复杂的程序，都可以拆成一个个简单的小部分，逐个击破，再拼凑起来，在复杂的事也变的简单了。 第 18 页 共 26 页 3.6运行结果（截图） 将程序员录入后,让其运行。将会出现一个菜单的界面，执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均会有相应的提示。操作简单方便实用，下面即为一些操作的示意图。 运行程序后出界面，运行结果如图所示。 第 19 页 共 26 页 第 20 页 共 26 页 第 21 页 共 26 页 第 22 页 共 26 页 第 23 页 共 26 页 第 24 页 共 26 页 第 25 页 共 26 页 结 论 经过我们不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是迷宫求解问题，深刻的体会到它的游戏可玩性。通过本次课程设计我们发现我们对于C++语言和数据结构还有很多地方不了解，今后继续努力学习。 致 谢 在这里我真心的感谢杨振老师对我们精心的指导和不倦的教育,他在我们的课程设计过程中提出了指导性的方案和架构,时事关注我们设计的进程，并指引我们阅读相关的资料和书籍，使我们的课设能够按时顺利的完成。同时也感谢学校给我们这次机会，训练我们灵活应用所学数据结构知识，独立完成问题分析的能力，让我们学会怎样结合数据结构理论知识去解决实际问题。 第 26 页 共 26 页 因篇幅问题不能全部显示，请点此查看更多更全内容