大数据结构课程设计深度与广度优先搜索：迷宫问的题目

数据结构课程设计深度与广度优先搜索：迷宫问题专业计算机科学与技术网络技术学生某某班级学号指导教师完成日期目 录1. 课程设计的目的.32. 简介.33. 算法说明.44. 测试结果.55. 分析与探讨.66. 小结.87. 参考文献.98. 附录,.10附录1 源程序清单.10一课程设计的目的数据结构课程设计是为数据结构课程独立开设的实践性教学环节。数据结构课程设计对于巩固数据结构知识，加强学生的实际动手能力和提高学生综合素质是十分必要的。课程设计的目的：1要求学生达到熟练掌握C语言的根本知识和技能。2了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。3提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用根本调试方法，迅速找出程序代码中的错误并且修改。4培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。5初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法和技能。二简介1.图的存储结构图的存储结构又称图的表示，其最常用的方法是邻接矩阵和邻接表。无论采用存储方式，其目的总是一样的，即不仅要存储图中各个顶点的信息，同时还要存储顶点之间的所有关系。2.图的遍历图的遍历就是从指定的某个顶点称其为初始点出发，按照一定的搜索方法对图中所有顶点各做一次访问的过程。根据搜索的方法不同，遍历有如下两种。1深度优先搜索遍历：深度优先搜索DFS是一个递归过程。首先访问一个顶点Vi并将其标记为已访问过，然后从Vi的任意一个未被访问的邻接点出发进展深度优先搜索遍历。如此执行，当Vi的所有邻接点均被访问过时，如此退回到上一个顶点Vk，从Vk的另一未被访问过的邻接点出发进展深度优先搜索遍历。如此执行，直到退回到初始点并且没有违背访问过的邻接点为止。2广度优先搜索遍历：广度优先搜索过程BFS为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过的邻接点，其访问顺序可以任意，假定依次为Vi1，Vi2，.Vin，并均被标记为已访问过，然后按照Vi1，Vi2，.Vin，的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，以此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。无论是深度优先搜索还是广度优先搜索，其本质都是将图的二维顶点结构线性化的过程，并将当前顶点相邻的未被访问的顶点作为下一个顶点，由于与当前顶点相邻的顶点可能多于一个，而每次只能选择其中一个作为下一个顶点，这样势必要保存其他相邻顶点。深度优先搜索和广度优先搜索在数据结构上的区别就在于用于保存其他相邻顶点的方式不一样，深度优先搜索采用栈，而广度优先搜索如此采用队列。从形式上，深度优先搜索往往采用一个递归过程，实际上递归的编译实现就应用了栈。本实验的目的是设计一个程序。一般的迷宫可表示为一个二维平面图形，将迷宫的左上角作入口，右下角作出口。迷宫问题求解的目标是寻找一条从入口点到出口点的通路。具体实验内容如下：选择手动或者自动生成一个n*m的迷宫，将迷宫的左上角作为入口，右下角作为出口，设“0为通路，“1为墙，即无法穿越。假设一只老鼠从起点出发，目的地为右下角终点，可向“上，下，左，右，左上，左下，右上，右下8个方向行走。如果迷宫可以走通，如此用图形界面标出走出迷宫的路径。如果迷宫为死迷宫，如此只输出迷宫原型图。三算法说明在实例程序中使用二维数组mazeN+2N+2 的行，列数。(不用mazeNN原因是当老鼠跑到了迷宫的边界点就有可能跳出迷宫，而使用mazeN+2N+2就可以把迷宫的外面再包一层“1，这样就可以阻止老鼠走出格)当值为“0时表示该点是通路，当值为“1时表示该点是墙。老鼠在迷宫中的位置在任何时候都可以有行号row和列号col表示。（1） 手动生成迷宫void hand_maze(int m,int n) /手动生成迷宫int i,j;for(i=0;im;i+)for(j=0;jmazeij;(2)自动生成迷宫void automatic_maze(int m,int n) /自动生成迷宫int i,j;for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2; /随机生成0，1maze00=0; /将开始和完毕位置强制为0，保证有可能出来迷宫mazem-1n-1=0;四测试结果1.手动生成迷宫2.自动生成迷宫3.迷宫开始界面五分析与探讨首先明确题目中的条件：（1） 迷宫是一个8*8大小的矩阵。（2） 从迷宫的左上角进入，右下角为迷宫的终点。（3） mazeij=0代表第i+1行第j+1列的点是通路；mazeij=1代表该点是墙，无法通行。（4） 迷宫有两种生成方式：手工设定和自动生成。（5） 当老鼠处于迷宫中某一点的位置上，它可以向8个方向前进，分别是：“上、下、左、右、左上、左下、右上、右下8个方向。（6） 在实例程序中使用二维数组mazeN+2N+2 的行，列数。(不用mazeNN原因是当老鼠跑到了迷宫的边界点就有可能跳出迷宫，而使用mazeN+2N+2就可以把迷宫的外面再包一层“1，这样就可以阻止老鼠走出格)当值为“0时表示该点是通路，当值为“1时表示该点是墙。老鼠在迷宫中的位置在任何时候都可以有行号row和列号col表示（7） 老鼠在每一点都有8种方向可以走，分别是：North，NorthEast，East，SouthEast,South,SouthWest,West，NorthWest。可以用数组move8来表示每一个方向上的横纵坐标的偏移量，见表3.1。根据这个数组，就很容易计算出沿某个方向行走后的下一个点的坐标。 表3.1 8种方向move的偏移量Name dirMovedir.vertMovedir.horizN0-10NE1-11E201SE311S410SW51-1W60-1NW60-1迷宫问题可以用深度优先搜索方法实现。当老鼠在迷宫中移动的时候，可能会有许多种移动选择方向。程序需要记录并用栈来保存当前点的坐标，然后任意选择一个方向进展移动。由于应用栈保存了当前通道上各点的坐标，所以当在当前各方向上都走不通时可以返回上一个点，然后选择另一个方向前进。 可定义element结构用于存储每一步的横纵坐标和方向。 typedef struct short int row; short int col; short int dir;element;element stackMAX _STACK_SIZE;根据表3.1可推算出每次移动后的坐标。设当前的坐标是row,col,移动的方向是dir，移动后的点是next,如此有next_row=row+movedir.vert;next_col=col+movedir.horiz; 可用另一个二维数组markN+2来记录哪些点已经被访问过。当经过点mazerowcol时，相应地将markrowcol的值从0置为1。 本程序支持自动生成迷宫。利用random2函数可随机产生0或1，来支持迷宫的自动生成。注意mazeNN和maze11一定要等于0，因为他们分别是起点和终点。六小结一周的课程设计完毕了，在这次课程设计中不仅检验我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情的方法和技巧。在设计的过程中，和同学们相互探讨，相互学习，相互监视。我学会了运筹帷幄，学会了宽容，学会了理解，也学会了做人和处世，这次的课程设计对我来说受益良多。通过这次课程设计，更是让我深刻认识到自己在学习中的不足，同时也找到了克制不足的方法，这也是一笔很大的资源。在以后的时间中，我们应该利用更多的时间去上机实验，加强自学的能力，多编写程序，相信不久后我们的编程能力都会有很大的提高。参考文献1 X振安,X燕君.C程序设计课程设计M.机械工业,2004年9月2 谭浩强.C程序设计第三版.清华大学,2005年7月3 严蔚敏,吴伟民.数据结构C语言版.清华大学,1997年4月4 李志球实用C语言程序设计教程 ：电子工业，19995 王立柱：C/C+与数据结构 ：清华大学，20026 吴文虎 程序设计根底 ：清华大学，20037 郭福顺，王晓芬，李莲治 数据结构修订本，某某理工大学，19978 潘道才，陈一华 数据结构，电子科技大学，1994附 录附录1 源程序清单#include /库中包含system(pause)和rand()函数#include /c语言里的库#includeusing namespace std;#define N 49 /定义为全局变量,这是迷宫数组的上线，可以自行修改#define M 49int X; int mazeN+2M+2;int head=0,tail=0; /队列的头尾指针，初始值设为0struct point /存放迷宫访问到点的队列结构体，包含列，行，序号 int row,col,predecessor; queue1200;void hand_maze(int m,int n) /手动生成迷宫int i,j;coutendl; cout请按行输入迷宫，0表示通路，1表示障碍:endl; for(i=0;im;i+) for(j=0;jmazeij; void automatic_maze(int m,int n) /自动生成迷宫int i,j;coutn迷宫生成中nn;system(pause);for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2; /随机生成0、1maze00=0; /将开始和完毕位置强制为0，保证有可能出来迷宫mazem-1n-1=0;void data(int m,int n) /当用户输入的不是规整的m行n列的迷宫，用来生成规如此的数字迷宫int i,j; coutendl;cout根据您先前设定的迷宫X围endl;coutendl;cout 我们将取所输入的前m*n个数生成迷宫endl;coutn数字迷宫生成结果如下:nn;cout迷宫入口n; cout;for(i=0;im;i+) coutn;for(j=0;jn;j+) if(mazeij=0) cout 0;if(mazeij=1) cout 1; cout迷宫出口n;void print_maze(int m,int n) /打印迷宫外壳int i,j,k;coutn字符迷宫生成结果如下:nn;cout迷宫入口n;cout ;coutendl;cout ; /生成上外壳for(k=0;kn;k+)cout; /这两个黑三角用来生成顶部外壳for(i=0;im;i+)coutn; /生成左外壳cout;for(j=0;jn;j+) if(mazeij=0) printf();if(mazeij=1) printf();cout; /生成右外壳coutendl;for(k=0;kn;k+)cout;cout n; /生成底部外壳 for(i=0;in;i+)cout ; coutn;for(i=0;in;i+)cout ;cout迷宫出口n;void result_maze(int m,int n) /这个是打印输出迷宫的星号路径 int i,j;cout迷宫通路(用表示)如下所示：nt;for(i=0;im;i+)coutn;for(j=0;jn;j+)if(mazeij=0|mazeij=2) /2是队列中访问过的点 cout;if(mazeij=1) cout;if(mazeij=3) /3是标记的可以走通的路径cout;void enqueue(struct point p) /迷宫中队列入队操作queuetail=p;tail+; /先用再加，队列尾部加1struct point dequeue() /迷宫中队列出队操作，不需要形参，因此用结构体定义head+;return queuehead-1;int is_empty() /判断队列是否为空return head=tail;void visit(int row,int col,int maze5151) /访问迷宫矩阵中的节点struct point visit_point=row,col,head-1; /head-1的作用是正在访问的这个点的序号为之前的点序号maze /将访问过的点位标记为2enqueue(visit_point);/入队int path(int maze5151,int m,int n) /路径求解X=1; /初始值定为1struct point p=0,0,-1; /定义入口节点if(mazep.rowp.col=1) /入口为1时，迷宫不可解 coutn=n; cout=0)&(p.row-1)m)&(p.col+0)=0)&(p.row-1)m)&(p.col+1)n)&(mazep.row-1p.col+1=0) visit(p.row-1,p.col+1,maze); /东北 if(p.row+0)m)&(p.col+1)n)&(mazep.row+0p.col+1=0) visit(p.row+0,p.col+1,maze); /东 if(p.row+1)m)&(p.col+1)n)&(mazep.row+1p.col+1=0) visit(p.row+1,p.col+1,maze); /东南 if(p.row+1)m)&(p.col+0)n)&(mazep.row+1p.col+0=0) visit(p.row+1,p.col+0,maze); /南 if(p.row+1)m)&(p.col-1)=0)&(mazep.row+1p.col-1=0) visit(p.row+1,p.col-1,maze); /西南 if(p.row+0)m)&(p.col-1)=0)&(mazep.row+0p.col-1=0) visit(p.row+0,p.col-1,maze); /西 if(p.row-1)=0)&(p.row-1)m)&(p.col-1)=0)&(mazep.row-1p.col-1=0) visit(p.row-1,p.col-1,maze); /西北if(p.row=m-1&p.col=n-1) /如果当前矩阵点是出口点，输出路径coutn=n; cout迷宫路径为：n; cout出口endl; cout endl; printf(%d,%d)n,p.row+1,p.col+1); cout endl; mazep.rowp.col=3; /逆序将路径标记为3 while(p.predecessor!=-1) p=queuep.predecessor; printf(%d,%d)n,p.row+1,p.col+1); cout endl; mazep.rowp.col=3; cout入口endl;else coutn=n; cout此迷宫无解！nn; X=0;return 0;void main() int i,m,n,cycle=0; while(cycle!=(-1) cout*n; cout 欢迎进入迷宫求解系统n; coutendl; cout 设计者:姜雯B计算机131班n; cout*n; cout 手动生成迷宫 请按：1n; cout 自动生成迷宫 请按：2n; cout 退出 请按：3nn; cout*n; coutn; couti; switch(i) case 1: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你输入的行列数超出预设X围(0-49,0-49),请重新输入：nn; coutm; coutn; coutn; hand_maze(m,n); data(m,n); print_maze(m,n); path(maze,m,n); if(X!=0) result_maze(m,n); /当X不为0时，有解，调用输出路径函数 coutnnPress Enter Contiue!n; getchar(); while(getchar()!=n); /承受一个输入，当为回车时执行break跳出，否如此一直执行承受数据 break; case 2: coutm; coutn; coutn; while(m49)|(n49) coutn抱歉，你输入的行列数超出预设X围(0-49,0-49),请重新输入：nn; coutm; coutn; coutn; automatic_maze(m,n); data(m,n); print_maze(m,n); path(maze,m,n); if(X!=0) result_maze(m,n); coutnnPress Enter Contiue!n; getchar(); while(getchar()!=n); break; case 3: cycle=(-1);break; default: coutn;cout你的输入有误!n; coutnPress Enter Contiue!n; getchar(); while(getchar()!=n); break;