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

数据结构课程设计迷宫问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 华 北 科 技 学 院 数据结构课程设计说明书 班级 小组成员:______成绩: _____ 小组成员: 成绩: _____ 小组成员: _成绩: _____ 设计题目:_____ 迷宫问题 _______ 设计时间: 2013.7.1 至 2013.7.5 指导教师:___ _____________ 评 语:________________________________ _________________________________________ _________________________________________ _________________________________________ 评阅教师: _____________ 目录 设计总说明............................................................................................................... II 第1章 课程设计内容和要求 ................................................................................. 1 1.1问题描述 ....................................................................................................... 1 1.2设计要求 ....................................................................................................... 1 1.3需求分析 ....................................................................................................... 2 第2章 课程设计总体 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 及分析 ......................................................................... 3 2.1 问题分析 ...................................................................................................... 3 2.2 系统总体设计 .............................................................................................. 4 2.3系统详细设计 ............................................................................................... 6 第3章 程序运行结果与分析 ............................................................................... 11 3.1 调试分析 .................................................................................................... 11 3.2 测试结果 .................................................................................................... 11 第4章 心得 信息技术培训心得 下载关于七一讲话心得体会关于国企改革心得体会关于使用希沃白板的心得体会国培计划培训心得体会 总结 .................................................................................................. 20 参考文献 ................................................................................................................. 21 附录 ......................................................................................................................... 22 I 设计总说明:本课程设计是解决迷宫求解的问题，从入口出发，顺某一方向向前探索，若能走通，则继续往前走;否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要用一个保存从入口到当前位置的路径的结构。因此，在求迷宫通路的算法中要应用“队列”的思想假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是:若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口;若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索;若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置四周4个方向(上、下、左、右)上相邻的方块。假设以队列记录“当前路径”，则队列中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前位置入队”;“从当前路径上删除前一通道块”的操作即为“出队”。 关键词:迷宫;穷举;队列。 II 第1章 课程设计内容和要求 1.1问题描述 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫如下图A所示，求出一条从入口到出口的通路，或得出没有通路的论。 图1.1矩形迷宫图 1.2设计要求 要求设计程序输出如下: (1) 建立一个大小为m×n的任意迷宫(迷宫数据可由用户输入或由程序自动生成)，并在屏幕上显示出来; (2)找出一条通路的二元组(i,j)数据序列，(i,j)表示通路上某一点 的坐标。 (3)用一种标志(如数字8)在迷宫中标出该条通路; (4)在屏幕上输出迷宫和通路; (5)上述功能可用菜单选择。 第 1 页 共 31 页 1.3需求分析 1、用户进入菜单页面选择迷宫的状态(1表示手动生成迷宫，2表示自动生成迷宫，3表示迷宫游戏，4表示退出) 2、运用本迷宫系统，用户可以根据自己的需求输入所需的迷宫，其中0表示通路，1表示障碍。用户可以自己定义迷宫并设置其中的障碍，以矩阵形式输入，也可通过定义迷宫的行列数由系统自动生成迷宫。 3、本系统自带一迷宫地图可供用户娱乐，用户的最高成绩可以被保存，下次进入游戏系统可以刷新纪录。 第 2 页 共 31 页 第2章 课程设计总体方案及分析 2.1 问题分析 1.迷宫的建立 要建立迷宫首先就要建立存储结构，这里我们用数组的方式建立的。根据用户输入的迷宫的大小(我们设置的最大值为40可以根据要求调解)，迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述; 2.迷宫的存储 迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组，这样(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 第 3 页 共 31 页 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 搜索路径表 0 1 2 3 4 5 6 7 8 9 10 (0,0) (0,1) (1,1) (1,2) (2,1) (2,2) (1,3) (2,3) (0,3) (3,3) (3,4) -1 0 1 2 2 3 4 5 6 7 9 由此可以看出，得到最短路径(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 4.输出结果 输出的结果分为两种，一种是直观的用图给出的通路，其中通路用?表示，第二种输出的是寻找完后的路径，路径用具体的坐标来表示。 2.2 系统总体设计 1.功能结构图 第 4 页 共 31 页 进入主界面 退手自出动迷动迷生宫生宫成游成系迷戏迷统宫宫 生输生输输进成入成入入入迷迷迷迷迷迷宫宫宫宫宫宫给障给行行游出碍出列列戏路矩路数数径阵径 图2.2功能结构图 2.迷宫系统概要设计 (1)构建一个二维数组maze[M+2][N+2]用于存储迷宫矩阵 (2)自动或手动生成迷宫，即为二维数组maze[M+2][N+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() 第 5 页 共 31 页 (8)出队 dequeue() (9)判断队列是否为空 is_empty() (10)访问节点 visit() (11)搜索迷宫路径 mgpath() 2.3系统详细设计 实现概要设计中定义的所有数据类型及操作的伪代码算法 1.节点类型和指针类型 迷宫矩阵类型:int maze[M+2][N+2];为方便操作使其为全局变量 迷宫中节点类型及队列类型: struct point{int row,col,predecessor}que[512] 2.迷宫的操作 (1)手动生成迷宫 void shoudong_maze(int m,int n) {定义i,j为循环变量 for(i<=m) for(j<=n) 输入maze[i][j]的值 } (2)自动生成迷宫 void zidong_maze(int m,int n) {定义i,j为循环变量 for(i<=m) for(j<=n) maze[i][j]=rand()%2 //由于rand()产生的随机数是从0到 RAND_MAX,RAND_MAX是定义在stdlib.h中的,其值至少为32767),要产生从X到Y的数,只需要这样写:k=rand()%(Y-X+1)+X; } (3)打印迷宫图形 第 6 页 共 31 页 void print_maze(int m,int n) {用i,j循环变量，将maze[i][j]输出 ?、?} (4)打印迷宫路径 void result_maze(int m,int n) {用i,j循环变量，将maze[i][j]输出 ?、?、?} (5)搜索迷宫路径 ?迷宫中队列入队操作 void enqueue(struct point p) {将p放入队尾，tail++} ?迷宫中队列出队操作 struct point dequeue(struct point p) {head++,返回que[head-1]} ?判断队列是否为空 int is_empty() {返回head==tail的值，当队列为空时，返回0} ?访问迷宫矩阵中节点 void visit(int row,int col,int maze[41][41]) {建立新的队列节点visit_point,将其值分别赋为 row,col,head-1,maze[row][col]=2,表示该节点以被访问过;调用enqueue(visit_point),将该节点入队} ?路径求解 void mgpath(int maze[41][41],int m,int n) {先定义入口节点为struct point p={0,0,-1},从maze[0][0]开始访问。如果入口处即为障碍，则此迷宫无解，返回0 ，程序结束。否则访问入口节点，将入口节点标记为访问过maze[p.row][p.col]=2,调用函数enqueue(p)将该节点入队。 判断队列是否为空，当队列不为空时，则运行以下操作: { 调用dequeue()函数，将队头元素返回给p， 如果p.row==m-1且p.col==n-1,即到达出口节点，即找到了路径，结束; 第 7 页 共 31 页 如果p.col+10且maze[p.row][p.col-1]==0,说明未到迷宫左边界，且其左方有通路,则visit(p.row,p.col-1,maze),将左方节点入队标记已访问; 如果p.row-1>0且maze[p.row-1][p.col]==0,说明未到迷宫上边界，且其上方有通路,则visit(p.row,p.col+1,maze),将上方节点入队标记已访问。 } 访问到出口(找到路径)即p.row==m-1且p.col==n-1,则逆序将路径标记为3即: maze[p.row][p.col]==3; while(p.predecessor!=-1) {p=queue[p.predecessor]; maze[p.row][p.col]==3;} 最后将路径图形打印出来。 搜索算法流程如图2.3所示: 第 8 页 共 31 页 图2.3 迷宫路径搜索流程图 3.菜单选择 while(cycle!=(-1)) ? 手动生成迷宫 请按:1 ? 自动生成迷宫 请按:2 ? 进入迷宫游戏 请按:3 ? 退出迷宫游戏 请按:4 ? ~~特别鸣谢~~ 请按:0 scanf("%d",&i); switch(i) { case 1:请输入行列数(如果超出预设范围则提示重新输入) 第 9 页 共 31 页 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; } 注:具体源代码见附录 第 10 页 共 31 页 第3章 程序运行结果与分析 3.1 调试分析 在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最 短路径，所以通过算法比较，改用队列。 3.2 测试结果 1.迷宫系统主界面 图3.1 迷宫系统主界面 2.手动生成迷宫 2.1 手动生成迷宫无解情况 第 11 页 共 31 页 图3.2 手动生成迷宫界面 用户自定义迷宫的行数、列数、迷宫障碍矩阵，由系统生成对应的迷宫并求 出无解。 2.2 手动生成迷宫有解情况 第 12 页 共 31 页 图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("\n\n"); printf("请按行输入迷宫，0表示通路，1表示障碍(用空格隔开):\n\n"); for(i=0;i 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 。我们依据实验 报告 软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载 的要求和步骤一项项进行规划，期间在图书馆查阅了很多资料，小组成员之间也相互学习，不懂的地方大家一起讨论。至于最后代码的实现，也是我们小组成员共同努力的结果。我们不断改进和完善代码中繁琐和冗余的部分，力图写出一个最简洁明了又不脱离实际的程序，尽可能做到和现实相贴近。在上机实际操作中，也并不是从一开始就顺利的，代码中出现了不少错误，虽然我们一一调试改正，但在最后还是遇到了瓶颈，大家也都纷纷绞尽脑汁思考问题所在。当然，错误最后被我们查找了出来。而后便是收尾工作，成员们依旧尽心尽力，最终，经过我们一周多的努力，我们有了实验成果。 在这次团队合作中，我们都深深体会到学好专业知识的重要性，老师上课所教授的基本知识是非常必要的，在真正应用到实际选题的时候就凸显了出来，就以我们小组的选题为例，迷宫问题的基本思想就是栈的问题，如果对栈的知识比较了解，在实现迷宫问题时是不会太吃力的。其次，通过团队合作，我们每个人都感觉到了团队精神的重要性，它不是说将每个人的想法叠加或简单拼凑起来，而是需要我们每个人协调，汲取每个人的专长和想法的独到之处，进而整合起来，确定一个完备的方案。其中非常重要的是，在相互讨论和商榷中，争执是不可避免的。成员们并没有因此动怒，而是耐心倾听和思考，说出每个人的意见，做到了让每个人都信服。所以说，通过这次实验，也使我们小组成员之间的关系更加和谐和亲密。 第 20 页 共 31 页 参考文献 [1]文东,华进.Visual C++程序设计基础与项目实训.第1版.北京:中国人民大学出版社,2009 [2]段德亮,余健,张仁才.C#课程设计案例精编.第1版.北京:清华大学出版社,2008 [3]李翠霞.零基础学Visual C++.第2版.北京:机械工业出版社，2010 [4]李言，李伟明，李贺.Visual C++项目开发全程实录.第1版.北京:清华大学出版社，2008 [5]朱战立.数据结构--使用C语言.第四版.北京:电子工业出版社，2011 [6]谭浩强.C程序设计.第三版.北京:清华大学出版社，2005 第 21 页 共 31 页 附录 程序代码: #include"stdlib.h" #include"stdio.h" #include #include #include #define N 39 #define M 39 int X; int maze[N+2][M+2]; struct point { int row,col,predecessor; } queue[512]; int head=0,tail=0; void shoudong_maze(int m,int n)//手动输入迷宫 { int i,j; printf("\n\n"); printf("请按行输入迷宫，0表示通路，1表示障碍(用空格隔开):\n\n"); for(i=0;i=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze);//左 if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze);//上 } 第 24 页 共 31 页 if(p.row==m-1&&p.col==n-1)//到达终点 { printf("\n=================================================== ===============\n"); printf("迷宫路径为:\n"); printf("(%d,%d)\n",p.row,p.col);//输出当前路径坐标 maze[p.row][p.col]=3;//更改通路路径的值 while(p.predecessor!=-1)//前一点为通路 { p=queue[p.predecessor];//循环寻找前点 printf("(%d,%d)\n",p.row,p.col); maze[p.row][p.col]=3; } } else {printf("\n===================================================== ========\n"); printf("此迷宫无解～\n\n");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 iMap[10][20] = {{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}, 第 25 页 共 31 页 {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; nJ++) { if(iMap[nI][nJ] == 1) { printf("?"); } else { printf(" "); } } printf("\n");//打印地图 } printf("\n\n\t按Esc退出到主界面。。。"); printf("\n纪录%.5f\n",jl); int iRow = 1,iCol = 0; //定义人物的坐标 int iInput = 0; MoveCursorTo(iCol * 2,iRow); time (&st); printf("?");//在当前的位置输出 bool bRun = true;//表示程序继续运行 while(bRun) { iInput = _getch(); if(iInput == 27) //用户按下了ESC键 { system("cls"); break; } if(iInput == 224)//用户按下了控制键 { iInput = _getch(); switch(iInput) { 第 26 页 共 31 页 case 75://左 { if(iMap[iRow][iCol - 1] == 0)//可以行走 { MoveCursorTo(iCol * 2,iRow); printf("?");//当前位置移动方向 iCol -= 1;//左移 MoveCursorTo(iCol * 2,iRow); printf("?");//在当前的位置输出 } } break; case 72://上 { if(iMap[iRow - 1][iCol] == 0)//可以行走 { MoveCursorTo(iCol * 2,iRow); printf("?");//当前位置移动方向 iRow -= 1;//上移 MoveCursorTo(iCol * 2,iRow); printf("?");//在当前的位置输出 } } break; case 77://右 { if(iCol + 1 >= 20)//到达终点 { MoveCursorTo(0,16); printf(" 冲出迷宫～\n"); time (&en); t=difftime(en,st); printf(" 游戏用时%.5f sec \n\n",t); if(t>=jl) printf(" o(,，,)o 遗憾，再接再厉。。。\n\n"); else if(t39)||(n<=0||n>39)) { printf("\n抱歉，你输入的行列数超出预设范围(0-39,0-39),请重新输入:\n\n"); printf("请输入行数:"); scanf("%d",&m); printf("\n"); printf("请输入列数:"); scanf("%d",&n); } shoudong_maze(m,n);//调用手动 print_maze(m,n);//调用输出 第 29 页 共 31 页 mgpath(maze,m,n);//调用路径探索 if(X!=0) result_maze(m,n); printf("\n\nPress Enter To Contiue!\n"); //输入回车继续 getchar(); while(getchar()!='\n');//输入不是回车，终止 system("cls"); break; //自动生成 case 2: system("cls"); printf("\n请输入行数:"); scanf("%d",&m); printf("\n"); printf("请输入列数:"); scanf("%d",&n); while((m<=0||m>39)||(n<=0||n>39)) { printf("\n抱歉，你输入的行列数超出预设范围(0-39,0-39),请重新 输入:\n\n"); printf("请输入行数:");scanf("%d",&m); printf("\n"); printf("请输入列数:");scanf("%d",&n); } zidong_maze(m,n);//调用自动 time (&start); print_maze(m,n);//调用输出 mgpath(maze,m,n);//调用路径探索 time (&end); t=difftime(end,start); printf("用时%.5f sec \n",t); if(X!=0) result_maze(m,n); printf("\n\nPress Enter To Contiue!\n");//输入回车继续 getchar(); while(getchar()!='\n'); system("cls"); break;//输入不是回车，终止 第 30 页 共 31 页 case 3: system("cls"); youxi(); printf("\n\n"); break; case 4: cycle=(-1); printf("\t正在退出系统。。。\n\t欢迎下次再来O(?_?)O~~\n\n"); break; default:printf("\n"); printf("你的输入有误!\n"); printf("\nPress Enter To Contiue!\n"); getchar(); while(getchar()!='\n'); break; case 0: system("cls"); \n\n\t\t周洁\n\n\t\t周胡勇\n\n\n"); printf("制作人:\n\n\t\t刘畅 system("pause"); system("cls"); break; } } } 第 31 页 共 31 页