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

华 北 科 技 学 院数据结构课程设计说明书班级 小组成员:_成绩: _小组成员: 成绩: _小组成员: _成绩: _设计题目:_ 迷宫问题 _ 设计时间: 2013.7.1 至 2013.7.5 指导教师:_ _ 评 语:_ _ _ _ 评阅教师: _目录设计总说明II第1章 课程设计内容和要求11.1问题描述11.2设计要求11.3需求分析2第2章 课程设计总体方案及分析32.1 问题分析32.2 系统总体设计42.3系统详细设计6第3章 程序运行结果与分析113.1 调试分析113.2 测试结果11第4章 心得总结20参考文献21附录22设计总说明：本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要用一个保存从入口到当前位置的路径的结构。因此，在求迷宫通路的算法中要应用“队列”的思想假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置四周4个方向（上、下、左、右）上相邻的方块。假设以队列记录“当前路径”，则队列中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入队”；“从当前路径上删除前一通道块”的操作即为“出队”。关键词：迷宫；穷举；队列。第1章 课程设计内容和要求1.1问题描述 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的论。 图1.1矩形迷宫图1.2设计要求要求设计程序输出如下：(1) 建立一个大小为mn的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；（2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点 的坐标。（3）用一种标志（如数字8）在迷宫中标出该条通路；（4）在屏幕上输出迷宫和通路；（5）上述功能可用菜单选择。1.3需求分析1、用户进入菜单页面选择迷宫的状态（1表示手动生成迷宫，2表示自动生成迷宫，3表示迷宫游戏，4表示退出）2、运用本迷宫系统，用户可以根据自己的需求输入所需的迷宫，其中0表示通路，1表示障碍。用户可以自己定义迷宫并设置其中的障碍，以矩阵形式输入，也可通过定义迷宫的行列数由系统自动生成迷宫。3、本系统自带一迷宫地图可供用户娱乐，用户的最高成绩可以被保存，下次进入游戏系统可以刷新纪录。第2章 课程设计总体方案及分析2.1 问题分析1.迷宫的建立要建立迷宫首先就要建立存储结构，这里我们用数组的方式建立的。根据用户输入的迷宫的大小（我们设置的最大值为40可以根据要求调解），迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述；2.迷宫的存储迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组mazeM+2N+2,然后用它的前m行n列来存放元素，即可得到一个mn的二维数组，这样(0,0)表示迷宫入口位置，(m-1,n-1)表示迷宫出口位置。注：其中M，N分别表示迷宫最大行、列数，本程序M、N的缺省值为39、39，当然，用户也可根据需要，调整其大小。3.迷宫路径的搜索首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径。以矩阵 0 0 1 0 1 为例，来示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0首先，将位置(0,0)(序号0)放入队列中，其前节点为空，从它开始搜索，其标记变为2，由于其只有一个非障碍位置，所以接下来移动到(0,1)(序号1)，其前节点序号为0，标记变为2，然后从(0,1)移动到(1,1)(序号2)，放入队列中，其前节点序号为1，(1,1)存在(1，2)(序号3)、(2，1)(序号4)两个可移动位置，其前节点序号均为2.对于每一个非障碍位置，它的相邻非障碍节点均入队列，且它们的前节点序号均为该位置的序号，所以如果存在路径，则从出口处节点的位置，逆序就可以找到其从出口到入口的通路，搜索路径如表2.1所示。表2.1 搜索路径表012345678910(0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)(3,4)-10122345679由此可以看出，得到最短路径(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)4. 输出结果输出的结果分为两种，一种是直观的用图给出的通路，其中通路用表示，第二种输出的是寻找完后的路径，路径用具体的坐标来表示。2.2 系统总体设计 1. 功能结构图图2.2功能结构图2.迷宫系统概要设计 (1)构建一个二维数组mazeM+2N+2用于存储迷宫矩阵 (2)自动或手动生成迷宫，即为二维数组mazeM+2N+2赋值 (3)构建一个队列用于存储迷宫路径 (4)建立迷宫节点struct point,用于存储迷宫中每个节点的访问情况 (5)实现搜索算法 (6)屏幕上显示操作菜单3.程序中的函数 (1)主函数 main() (2)手动生成迷宫函数 shoudong_maze() (3)自动生成迷宫函数 zidong_maze() (4)将迷宫打印成图形 print_maze() (5)打印迷宫路径 (若存在路径) result_maze() (6)迷宫游戏函数 youxi() (7)入队 enqueue() (8)出队 dequeue() (9)判断队列是否为空 is_empty() (10)访问节点 visit() (11)搜索迷宫路径 mgpath()2.3系统详细设计实现概要设计中定义的所有数据类型及操作的伪代码算法1.节点类型和指针类型迷宫矩阵类型：int mazeM+2N+2;为方便操作使其为全局变量 迷宫中节点类型及队列类型： struct pointint row,col,predecessorque5122.迷宫的操作(1)手动生成迷宫void shoudong_maze(int m,int n)定义i,j为循环变量for(i=m)for(j=n)输入mazeij的值 (2)自动生成迷宫void zidong_maze(int m,int n)定义i,j为循环变量 for(i=m) for(j=n)mazeij=rand()%2 /由于rand()产生的随机数是从0到 RAND_MAX,RAND_MAX是定义在stdlib.h中的,其值至少为32767),要产生从X到Y的数,只需要这样写：k=rand()%(Y-X+1)+X;(3)打印迷宫图形void print_maze(int m,int n)用i,j循环变量，将mazeij输出 、(4)打印迷宫路径void result_maze(int m,int n)用i,j循环变量，将mazeij输出 、(5) 搜索迷宫路径迷宫中队列入队操作void enqueue(struct point p)将p放入队尾，tail+迷宫中队列出队操作struct point dequeue(struct point p)head+,返回quehead-1判断队列是否为空int is_empty()返回head=tail的值，当队列为空时，返回0访问迷宫矩阵中节点void visit(int row,int col,int maze4141)建立新的队列节点visit_point,将其值分别赋为row,col,head-1,mazerowcol=2,表示该节点以被访问过;调用enqueue(visit_point),将该节点入队路径求解void mgpath(int maze4141,int m,int n)先定义入口节点为struct point p=0,0,-1,从maze00开始访问。如果入口处即为障碍，则此迷宫无解，返回0 ，程序结束。否则访问入口节点，将入口节点标记为访问过mazep.rowp.col=2,调用函数enqueue(p)将该节点入队。判断队列是否为空，当队列不为空时，则运行以下操作： 调用dequeue()函数，将队头元素返回给p，如果p.row=m-1且p.col=n-1,即到达出口节点，即找到了路径，结束；如果p.col+1n且mazep.rowp.col+1=0,说明未到迷宫右边界，且其右方有通路,则visit(p.row,p.col+1,maze),将右边节点入队标记已访问；如果p.row+10且mazep.rowp.col-1=0,说明未到迷宫左边界，且其左方有通路,则visit(p.row,p.col-1,maze),将左方节点入队标记已访问；如果p.row-10且mazep.row-1p.col=0,说明未到迷宫上边界，且其上方有通路,则visit(p.row,p.col+1,maze),将上方节点入队标记已访问。访问到出口(找到路径)即p.row=m-1且p.col=n-1,则逆序将路径标记为3即：mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3;最后将路径图形打印出来。搜索算法流程如图2.3所示：图2.3 迷宫路径搜索流程图 3. 菜单选择while(cycle!=(-1) 手动生成迷宫 请按：1 自动生成迷宫 请按：2 进入迷宫游戏 请按：3 退出迷宫游戏 请按：4 特别鸣谢 请按：0 scanf(%d,&i); switch(i) case 1：请输入行列数(如果超出预设范围则提示重新输入) shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); case 2 ：请输入行列数(如果超出预设范围则提示重新输入) zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); case 3: youxi(); case 4：cycle=(-1); case 0: 特别鸣谢;break;注：具体源代码见附录第3章 程序运行结果与分析3.1 调试分析在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最短路径，所以通过算法比较，改用队列。3.2 测试结果1.迷宫系统主界面 图3.1 迷宫系统主界面2. 手动生成迷宫2.1 手动生成迷宫无解情况图3.2 手动生成迷宫界面用户自定义迷宫的行数、列数、迷宫障碍矩阵，由系统生成对应的迷宫并求出无解。2.2 手动生成迷宫有解情况 图3.3 手动生成迷宫界面用户自定义迷宫的行数、列数、迷宫障碍矩阵，由系统生成对应的迷宫并求出路径。上面测试例子中，路径为（0,0）(1,0)(1,1)(2,1)(2,2)(3,2)(3,3)，在图中用“”表示。手动输入迷宫代码如下：void shoudong_maze(int m,int n)/手动输入迷宫int i,j;printf(nn);printf(请按行输入迷宫，0表示通路，1表示障碍(用空格隔开):nn);for(i=0;im;i+)for(j=0;jn;j+) scanf(%d,&mazeij);3. 自动生成迷宫3.1自动生成迷宫无解情况图3.4 自动生成迷宫界面用户自定义迷宫的行数和列数，由系统自动生成迷宫图并求出上例迷宫无解。3.2 自动生成迷宫有解情况图3.5 自动生成迷宫界面用户自定义迷宫的行数和列数，由系统自动生成迷宫图并求出路径。上面测试例子中，路径为（0,0）(0,1)(0,2)(0,3)(0,4)(1,4)(2,4)（3,4）（4,4），在图中用“”表示。自动生成迷宫代码如下：void zidong_maze(int m,int n)/自动生成迷宫int i,j;printf(n迷宫生成中nn);system(pause);for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2;for(i=0;i3;i+)for(j=0;j3;j+)mazeij=0;mazem-1-in-1-j=0;/由于rand()产生的随机数是从0到RAND_MAX/RAND_MAX是定义在stdlib.h中的,其值至少为32767)/要产生从X到Y的数,只需要这样写：k=rand()%(Y-X+1)+X; 4. 迷宫游戏4.1 迷宫游戏主界面图3.6 迷宫游戏主界面4.2 迷宫游戏过程图3.7 迷宫游戏过程图用户可用上下左右键控制迷宫中人物行走方向，控制人物走出迷宫。迷宫游戏地图代码如下：int iMap1020 = 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1, 1,0,1,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1, 1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1, 1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1, 1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,1, 1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1, 1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1, 1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;其人物行走方向以左为例：if(iMapiRowiCol - 1 = 0)/可以行走MoveCursorTo(iCol * 2,iRow);printf();/当前位置移动方向 iCol -= 1;/左移MoveCursorTo(iCol * 2,iRow);printf();/在当前的位置输出注：其他代码详见附录。5.特别鸣谢界面图3.8 特别鸣谢界面部分代码如下：system(cls);printf(制作人：nntt刘畅nntt周洁nntt周胡勇nnn);system(pause);system(cls);6.退出迷宫系统第 17 页 共 31 页图3.9 退出迷宫系统界面部分代码如下：cycle=(-1);printf(t正在退出系统。nt欢迎下次再来O(_)Onn);break;default:printf(n);printf(你的输入有误!n);printf(nPress Enter To Contiue!n);getchar();while(getchar()!=n);break;第4章 心得总结这是我们小组成员第一次以团队合作的形式参与程序设计这样的实验。由于数据结构这门课本身就比较晦涩和难以理解，我们从刚开始选题就陷入了僵局。经过我们几次的讨论和商讨，最终决定选择这个符合我们小组成员实际能力的选题迷宫。在确定下选题了之后，我们就着手开始准备实现程序的各个步骤。我们依据实验报告的要求和步骤一项项进行规划，期间在图书馆查阅了很多资料，小组成员之间也相互学习，不懂的地方大家一起讨论。至于最后代码的实现，也是我们小组成员共同努力的结果。我们不断改进和完善代码中繁琐和冗余的部分，力图写出一个最简洁明了又不脱离实际的程序，尽可能做到和现实相贴近。在上机实际操作中，也并不是从一开始就顺利的，代码中出现了不少错误，虽然我们一一调试改正，但在最后还是遇到了瓶颈，大家也都纷纷绞尽脑汁思考问题所在。当然，错误最后被我们查找了出来。而后便是收尾工作，成员们依旧尽心尽力，最终，经过我们一周多的努力，我们有了实验成果。 在这次团队合作中，我们都深深体会到学好专业知识的重要性，老师上课所教授的基本知识是非常必要的，在真正应用到实际选题的时候就凸显了出来，就以我们小组的选题为例，迷宫问题的基本思想就是栈的问题，如果对栈的知识比较了解，在实现迷宫问题时是不会太吃力的。其次，通过团队合作，我们每个人都感觉到了团队精神的重要性，它不是说将每个人的想法叠加或简单拼凑起来，而是需要我们每个人协调，汲取每个人的专长和想法的独到之处，进而整合起来，确定一个完备的方案。其中非常重要的是，在相互讨论和商榷中，争执是不可避免的。成员们并没有因此动怒，而是耐心倾听和思考，说出每个人的意见，做到了让每个人都信服。所以说，通过这次实验，也使我们小组成员之间的关系更加和谐和亲密。参考文献1文东,华进.Visual C+程序设计基础与项目实训.第1版.北京:中国人民大学出版社,20092段德亮,余健,张仁才.C#课程设计案例精编.第1版.北京:清华大学出版社,20083李翠霞.零基础学Visual C+.第2版.北京：机械工业出版社，20104李言，李伟明，李贺.Visual C+项目开发全程实录.第1版.北京：清华大学出版社，20085朱战立.数据结构-使用C语言.第四版.北京：电子工业出版社，20116谭浩强.C程序设计.第三版.北京：清华大学出版社，2005附录程序代码：#includestdlib.h#includestdio.h#include #include #include #define N 39#define M 39int X;int mazeN+2M+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)/手动输入迷宫int i,j;printf(nn);printf(请按行输入迷宫，0表示通路，1表示障碍(用空格隔开):nn);for(i=0;im;i+)for(j=0;jn;j+) scanf(%d,&mazeij);void zidong_maze(int m,int n)/自动生成迷宫int i,j;printf(n迷宫生成中nn);system(pause);for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2;for(i=0;i3;i+)for(j=0;j3;j+)mazeij=0;mazem-1-in-1-j=0;/由于rand()产生的随机数是从0到RAND_MAX/RAND_MAX是定义在stdlib.h中的,其值至少为32767)/要产生从X到Y的数,只需要这样写：k=rand()%(Y-X+1)+X; void print_maze(int m,int n)/输出迷宫图int i,j;printf(n迷宫生成结果如下:nn);printf(迷宫入口n);printf();for(i=0;im;i+)printf(n);for(j=0;jn;j+) if(mazeij=0) printf();/通if(mazeij=1) printf();/堵printf(迷宫出口n);void result_maze(int m,int n)/输出探索迷宫结果int i,j;printf(迷宫通路(用表示)如下所示：nt);for(i=0;im;i+)printf(n);for(j=0;jn;j+)if(mazeij=0|mazeij=2) printf();/通if(mazeij=1) printf();/障碍if(mazeij=3) printf();/路径void enqueue(struct point p)/增加queuetail=p;tail+;struct point dequeue()/删除head+;return queuehead-1;int is_empty()/空对return head=tail;void visit(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)/路径探索X=1;struct point p=0,0,-1;if(mazep.rowp.col=1)printf(n=n);printf(此迷宫无解nn);X=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=dequeue();if(p.row=m-1)&(p.col=n-1) break;if(p.col+1n)&(mazep.rowp.col+1=0)visit(p.row,p.col+1,maze);/右 顺时针，依次东南西北探索if(p.row+1=0)&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze);/左if(p.row-1=0)&(mazep.row-1p.col=0) visit(p.row-1,p.col,maze);/上if(p.row=m-1&p.col=n-1)/到达终点printf(n=n);printf(迷宫路径为：n);printf(%d,%d)n,p.row,p.col);/输出当前路径坐标mazep.rowp.col=3;/更改通路路径的值while(p.predecessor!=-1)/前一点为通路p=queuep.predecessor;/循环寻找前点printf(%d,%d)n,p.row,p.col);mazep.rowp.col=3;else printf(n=n); printf(此迷宫无解！nn);X=0;return 0;void MoveCursorTo(int iX,int iY)HANDLE hStd = GetStdHandle(STD_OUTPUT_HANDLE);COORD crPlayer = iX,iY;SetConsoleCursorPosition(hStd, crPlayer);void youxi() double t,jl=10;time_t st,en;int iMap1020 = 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 0,0,0,0,0,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1, 1,0,1,1,0,1,0,1,1,0,0,0,0,0,0,0,1,1,0,1, 1,0,1,1,0,1,0,1,1,1,1,1,1,0,1,1,1,1,0,1, 1,0,0,0,0,1,0,0,0,0,0,1,1,0,1,0,0,0,0,1, 1,0,1,1,0,1,0,1,0,1,1,1,1,0,1,0,1,0,1,1, 1,0,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,0,1,1, 1,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,1, 1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,1,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;for(int nI = 0; nI 10; nI+)for(int nJ = 0; nJ = 20)/到达终点MoveCursorTo(0,16);printf( 冲出迷宫！n);time (&en);t=difftime(en,st);printf(游戏用时%.5f sec nn,t);if(t=jl)printf(o()o 遗憾，再接再厉。nn);else if(tjl) printf()/ 好棒，纪录刷新！nn);jl=t;bRun = false; /结束循环break;if(iMapiRowiCol + 1 = 0)/可以行走MoveCursorTo(iCol * 2,iRow);printf(); /当前位置移动方向iCol += 1;/右移MoveCursorTo(iCol * 2,iRow);printf();/在当前的位置输出break;case 80:/下if(iMapiRow + 1iCol = 0)/可以行走MoveCursorTo(iCol * 2,iRow);printf();/当前位置移动方向 iRow += 1;/下移MoveCursorTo(iCol * 2,iRow); printf();/在当前的位置输出break;system(cls);void main()double t;time_t start,end;int i,m,n,cycle=0;while(cycle!=(-1)printf(*-*n);printf( 欢迎进入迷宫求解系统nn);printf( n);printf(*-*n);printf( 手动生成迷宫 请按：1nn);printf( 自动生成迷宫 请按：2nn);printf( 进入迷宫游戏 请按：3nn);printf( 退出迷宫系统 请按：4nn);printf( 特别鸣谢 请按：0nn);printf(*-*n);printf(n);printf( 请选择你的