上届迷宫搜索课程设计模板.doc

安徽理工大学数据结构课程设计说明书题目: 使用队列实现的迷宫搜索 院 系： 计算机科学与工程学院 专业班级： 信息安全09-02班 学 号： 2009303028 学生姓名： 金国庆 指导教师： 郝伟 2010年 06 月 26日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 学 号2009303028学生姓名金国庆专业（班级）信息安全09-02设计题目使用队列实现的迷宫搜索设计技术参数1. 使用C+或C语言实现设计任务；2. 所设计的程序能友好处理各种特殊情况，可读性好，执行效率高；3. 界面友好，操作简单；4. 设计说明书完整，简洁，层次合理；5. 设计说明书易于阅读并且能够很好的反映设计内容。设计要求用二维数组Mazemn为0，表示可通过，为1表示此路不通，入口时mazexy出口为mazezw且mazexy=0,编写寻找入口到出口的路径及一条最短路径的程序；1. 用矩阵表示迷宫转换为无向图；2. 对无向图从入口结点开始广度优先搜索及深度优先搜索。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划6月21号：根据实验报告的要求，对实验过程进行总结概括。6月22号：进行算法的概要分析和设计。6月23号：查找相关资料，完成需求分析；6月24-25号：进行算法的详细设计和源代码的书写。6月26号：对程序进行调试、修改、优化、分析，写出实验报告。参考资料1. 数据结构（C语言版），秦峰主编，合肥，中国科学技术大学出版社，20072. 谭浩强编著，C语言设计（第三版），北京，清华大学出版社，20053. 秦峰等编，数据结构（C语言版例题详解与课程设计），合肥：中国科学技术大学出版社4. 温秀梅，丁学均主编VC+面向对象程序设计教程与实验严蔚敏，吴伟民，数据结构（C语言版）北京：清华大学出版社，2002指导教师签字教研室主任签字 2010年 06 月 26日 学生姓名： 金国庆 学号： 2009303028 专业班级：信息安全09-02 课程设计题目： 使用队列实现的迷宫搜索 指导教师评语： 成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩评定表摘要1. 设置数组mazemaxmax来模拟迷宫；2. mazeij=0表示该方格所在的位置可通行，mazeij=1则表明该位置不能通行；3. 每一个结点的邻接结点为其相邻（从点在数组maze中所处位置的角度）的8个点中值为0的点，按结点的顺序依次找出每一个点的邻接点，此即完成迷宫图的数组表示转化为无向图表示，G用邻接表存储；4. 采用图的广度优先遍历的方法，从入口结点开始遍历，直到碰到出口点为止。并设置record数组来记录结点i在广度优先遍历过程中的前驱结点的标号recordi;5. 这样（recordi,i）表示存在从结点recordi到i的边，这样就可以从出口顶点在图中的标号回溯出口顶点，如此，一条从从入口到出口的最短路径就找到了。在定义record数组是将所有初始值设为-1，只是为了判断是否存在从入口到出口的路径，因为如果出口结点i的recordi的值为-1,则表明遍历过程没有找到出库，也就是说此迷宫无解；6. 反之recordi!=-1,则此迷宫一定是有解的，因为只有遍历过程中找到了出口i，才会改变recordi的值，而这个改变后的值是不可能为-1的；7. 输出从入口到出口的路径，用回溯法，只需将图中结点的编号换算成数组maze的坐标即可。关键词：深度搜索，广度搜索，路径，回溯法，递归1 算法分析该程序所作的工作是各种场合所用到搜索，其中包括社会中各部门用到的搜索技术如：人口信息查询，交通，通讯，银行以及一些迷宫类游戏搜索。该程序要是想广度优先，深度优先搜索，给出起点和终点，由该程序找出起点和终点之间的路径以及一条最短路径。11 读入，显示迷宫地图由外存读入地图MAP，MAP是有二维数组存放，由txt文档中的1.0表示图形及可连通路径，可将其显示在桌面上12 遍历查找路径 从起点开始进行广度优先搜索直到将整个地图全部读取并找到所求路径，然后进行深度优先搜索找出一条连通起点和终点的路径即可，然后再屏幕输出找到的路径。 目录(要求：给出一级目录和二级目录，宋体，四号字,1.5倍行距，页码使用罗马数字，居中)2算法设计框架2.1关键思路已访问上下结点下一结点左右结点2.2相应代码void Map:checkblock(Block *b)v-visited=1;if(b-x0)dealblock(b,GetBlock(b-x-1,b-y);if(b-xx+1,b-y);if(B-Y0)dealblock(b,GetBlock(b-x+1,b-y-1);if(b-yx,b-y+1); 3.算法全文3.1所需类的定义class Block public:int visited;int canpass;int x;int y;Block * parent;int value;Block();virtual Block();class Map public:Block * blocks;void SetValue(int x,int y,int v);void LoadMap();void Reset();void Show();Block * GetBlock(int x,int y);Block * end;Block * start;void checkblock(Block *b);void bfs();void dealblock(Block *b1,Block *b2);void ShowBlockValue();Map();virtual Map();queue q;3.2函数的实现#include stdafx.h#include Map.hMap:Map()blocks=new Block400;Map:Map()void Map:ShowBlockValue()for(int j=0;j20;j+)for(int i=0;j40;j+)if(ivalue);coutendl;coutendlcanpass!=0)return ;if(!b2-visited)b2-visited=1;b2-value=b1-value+1;b2-parent=b1;q.push(b2);else if(b2-valueb1-value+1)b2-parent=b1;b2-value=b1-value+1;void Map:bfs()Block *b;q.push(start);start-visited=1;while(!q.empty()b=q.front();q.pop();checkblock(b);void Map:checkblock(Block *b)b-visited=1;if(b-x0)dealblock(b,GetBlock(b-x-1,b-y);if(b-xx+1,b-y);if(b-xx,b-y-1);if(b-xx1,b-y+1);Block * Map:GetBlock(int x, int y)return &blocksy*20+x;void Map:Show()for(int j=0;j20;j+)for(int i=0;j40;j+)if(icanpass=1)printf();elseprintf(;)coutendl;void Map:Reset()for(int i=0;i20;i+)for(int j=0;j20;j+)blocksj*20+i.canpass=0;blocksj*20+i.visited=0;void Map:LoadMap()ifstream in(map.txt);char chs400;in.read(chs,sizeof(chs);in.close();int i=0;while(i400)blocksi.canpass=chsi-48;i+;start=GetBlock(0,10);end=GetBlock(19,10);void Map:SetValue(int x, int y, int v)blocksy*20+x.canpass=v;int main(int argc, char* argv)queue s;Map map;char choice=1;while(choice!=0)printf(*Menu*n);printf(Please enter the choice:n1.Load Map.n2.Show Data.n3.Breach First Search.n4.Depth First Search.n5.ShowBlock Value n6.Show All Blocks In Details.na.Auto Load ,DFS and Show.n*.Quit Appn);printf(*n);scanf(%c,&choice);if(choice=0)printf(Welcome!);break;switch(choice)case 1: map.LoadMap();printf(Succeeded!nnn);break;case2:map.Show();break;case 3:map.bfs();printf(Succeeded!nnn);break;case 4:map.ShowBlockValue();break;case 5:case 6:case a:case *:break;default:printf(Unknown choice!n);break;getchar();return 0;4.总结 要很好的掌握编程，仅仅通过几个简单的程序的编写时无法达成的，更需要大量的积累和深入才有可能，就从这个迷宫的问题来说，在迷宫无向图结构的转化时，对图可用广度优先搜索的算法来解决两点间最短路径问题，在程序的编写中也不能一位得向已有的程序进行模仿，而要自己去摸索，去寻求最好的解决方式，只有带着问题去反复进行实践，才有更熟练的掌握和运用，当然，对现有的程序也要夺去接触，因为有的程序是我们现在在短时期内想的出来的，最重要的一点就是持之以恒，要经常性的复习原来所接触的程序，这样才能保证我们有足够的经验去面对问题！参考文献1.数据结构（C语言版），秦峰主编，合肥，中国科学