数据结构课程设计-迷宫问题的操作要点.docx

《数据结构课程设计-迷宫问题的操作要点.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计-迷宫问题的操作要点.docx（19页珍藏版）》请在三一文库上搜索。

1、课程设计说明书No. 1课 程 设 计 任 务 书专 业计算机科学与技术班 级姓 名设 计 起 止 日 期设计题目：迷宫问题的操作设计任务（主要技术参数） ：学会运用数据结构建立迷宫问题，编造出迷宫并设计出走出迷宫的方法硬件环境：处理器：英特尔 第三代酷睿 i3-3110M 2.40GHz 双核内存： 4GB(三星 DDR3 1333MHz)主硬盘：希捷ST500LM012 HN-M500MBB (500GB/5400 转/分 )显示器：三星SEC3649(14 英寸 )软件环境：操作系统：Windows 8 64 位(DirectX 11)开发环境： VC+6.0指导教师评语：成绩：签字：年

2、月日课程设计说明书No. 21、课程设计目的为了配合数据结构课程的开设，通过设计一完整的程序，掌握数据结构的应用、算法的编写、类C语言的算法转换成 C程序并用 TC上机调试的基本方法特进行题目为两个链表合并的课程设计。通过此次课程设计充分锻炼有关数据结构中链表的创建、合并等方法以及怎样通过转化成C语言在微机上运行实现等其他方面的能力。2课程设计的内容与要求2.1 问题描述：迷宫问题是取自心理学的一个古典实验。 在该实验中，把一只老鼠从一个无顶大盒子的门放入， 在盒子中设置了许多墙， 对行进方向形成了多处阻挡。 盒子仅有一个出口，在出口处放置一块奶酪， 吸引老鼠在迷宫中寻找道路以到达出口。 对同

3、一只老鼠重复进行上述实验， 一直到老鼠从入口走到出口， 而不走错一步。 老鼠经过多次试验最终学会走通迷宫的路线。 设计一个计算机程序对任意设定的矩形迷宫如下图 A 所示，求出一条从入口到出口的通路，或得出没有通路的结论。图 A2.2 设计要求：要求设计程序输出如下：(1) 建立一个大小为 mn 的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；（ 2）找出一条通路的二元组（ i,j ）数据序列，（ i,j ）表示通路上某一点的坐标。课程设计说明书No. 3（ 3）用一种标志（如数字 8）在迷宫中标出该条通路；（ 4）在屏幕上输出迷宫和通路；（ 5）上述功能可用菜单选择。3

4、课程设计总体方案及分析3.1 问题分析：1.迷宫的建立：迷宫中存在通路和障碍， 为了方便迷宫的创建， 可用 0 表示通路，用 1 表示障碍，这样迷宫就可以用0、1 矩阵来描述，2.迷宫的存储：迷宫是一个矩形区域， 可以使用二维数组表示迷宫， 这样迷宫的每一个位置都可以用其行列号来唯一指定， 但是二维数组不能动态定义其大小， 我们可以考虑先定义一个较大的二维数组 mazeM+2N+2, 然后用它的前 m 行 n 列来存放元素，即可得到一个 mn 的二维数组，这样 (0,0)表示迷宫入口位置， (m-1,n-1)表示迷宫出口位置。注：其中 M ，N 分别表示迷宫最大行、列数，本程序M 、N 的缺省

5、值为39、39，当然，用户也可根据需要，调整其大小。3.迷宫路径的搜索：首先从迷宫的入口开始， 如果该位置就是迷宫出口， 则已经找到了一条路径， 搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径； 若是障碍就选择另一个相邻的位置，并从它开始搜索路径。 为防止搜索重复出现， 则将已搜索过的位置标记为 2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中， 如果所有相邻的非障碍位置均被搜索过， 且未找到通往出口的路径，则表明不存在从入口到出口的路径。 这实现的是广度优先遍历的算法， 如果找到路径，则为最

6、短路径。课程设计说明书No. 4以矩阵 0 0 1 0 1为例，来示范一下1 0 0 1 01 0 0 0 10 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.对于每一个非障碍位置， 它的相邻非障碍节点均入队列， 且它们的前节点序号均为该位置的序号，

7、所以如果存在路径， 则从出口处节点的位置， 逆序就可以找到其从出口到入口的通路。如下表所示：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)搜索算法流程图如下所示：课程设计说明书No. 53.2 概要设计1.构建一个二维数组mazeM+2N+2 用于存储迷宫矩阵自动或手动生成迷宫，即为二维数组mazeM+2N+2 赋值构建一个队列用于存储迷宫路径建立迷宫节点struct poin

8、t,用于存储迷宫中每个节点的访问情况实现搜索算法屏幕上显示操作菜单2.本程序包含 10 个函数：(1)主函数main()(2)手动生成迷宫函数shoudong_maze()课程设计说明书No. 6(3)自动生成迷宫函数zidong_maze()(4)将迷宫打印成图形print_maze()(5)打印迷宫路径(若存在路径 ) result_maze()(6)入队 enqueue()(7)出队 dequeue()(8)判断队列是否为空is_empty()(9)访问节点visit()(10)搜索迷宫路径mgpath()3.3 详细设计实现概要设计中定义的所有数据类型及操作的伪代码算法1. 节点类型和

9、指针类型迷宫矩阵类型： int mazeM+2N+2; 为方便操作使其为全局变量迷宫中节点类型及队列类型：struct pointint row,col,predecessor que5122. 迷宫的操作(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_MAX,RAND_MAX/ 由 于rand() 产 生 的

10、随 机 数 是 从0到是定义在 stdlib.h 中的 ,其值至少为 32767),要产生从 X到 Y 的数 ,只需要这样写： k=rand()%(Y-X+1)+X;课程设计说明书No. 7(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

11、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) 先定义入口节点为 str

12、uct 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, 说明未到迷宫右边界，且其右方有通课程设计说明书No. 8路 ,则 visit(p.row,p.col

13、+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=

14、queuep.predecessor; mazep.rowp.col=3;最后将路径图形打印出来。3.菜单选择while(cycle!=(-1)手动生成迷宫请按： 1自动生成迷宫请按： 2退出请按： 3scanf(%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);

15、mgpath(maze,m,n);if(X!=0) result_maze(m,n);课程设计说明书No. 9case 3：cycle=(-1); break;注：具体源代码见附录3.4 调试分析在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最短路径，所以通过算法比较，改用此算法3.5 测试结果1.手动输入迷宫课程设计说明书No. 10课程设计说明书No. 112 自动生成迷宫：课程设计说明书No. 124设计体会通过本次的课程设计，使我学会了如何去组织代码量较大大程序。 与此同时，也使我学会了一些对代码量较大的的程序进行编写、 连接、编译运行、以及调试和修改的技巧这次的课程

16、设计涉及到编程语言和数据结构的知识，要求和平时的实比相对较高。从本次的课程设计可以检验我们对 C 语言和数据结构的掌握情况， 同时也检验了我们对所学习过的知识的灵活运用情况。 在创新性方面，这次的课程设计虽然完成了课程设计的任务， 但是缺乏创造性的设计思想， 在以后的学习过程中还得继续努力。课程设计说明书No. 135参考文献1. 严蔚敏编著 . 数据结构（ C语言版） . 清华大学出版社， 20022. 朱战立 . 编著 . 数据结构使用 C 语言 . 西安交通大学出版社， 20043. 朱战立，张选平编著 . 数据机构学习指导和典型题解 . 西安交通大学出版社，20024. 苏小红，孙志岗

17、等编著 .C 语言大学实用教程（第 2 版） . 电子工业出版社，20085. 梁肇新编著 . 编程高手箴言 . 电子工业出版社， 2003课程设计说明书No. 14附件：#includestdlib.h#includest dio.h#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 表示通路，

18、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;/由于 rand() 生的随机数是从0 到 RAND_MAX/RAND_MAX是定 在stdlib.h 中的 ,其 至少 32767)/要 生从X 到 Y 的数 ,只需要 写：k=rand()%(Y-X+1)+X;课程设计说明书No. 15void pri

19、nt_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

20、) printf( );if(mazeij=1) printf( );if(mazeij=3) printf( );void enqueue(struct point p)queuetail=p;tail+;struct point dequeue()课程设计说明书No. 16head+;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(visi

21、t_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)&(m

22、azep.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);课程设计说明书No. 17printf( 迷宫路径为：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

23、.col=3;elseprintf(n=n);printf( 此迷宫无解！nn);X=0;return 0;void main()int i,m,n,cycle=0;while(cycle!=(-1)printf(*n);printf(欢迎进入迷宫求解系统n);printf(*n);printf(手动生成迷宫请按： 1n);printf(自动生成迷宫请按： 2n);printf(退出请按： 3nn);printf(*课程设计说明书No. 18*n);printf(n);printf( 请选择你的操作：n);scanf(%d,&i);switch(i)case 1:printf(n 请输入行数：

24、);scanf(%d,&m);printf(n);printf( 请输入列数：);scanf(%d,&n);while(m39)|(n39)printf(n抱歉，你输入的行列数超出预设范围(0-39,0-39), 请重新输入：nn);printf( 请输入行数：);scanf(%d,&m);printf(n);printf( 请输入列数：);scanf(%d,&n);shoudong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0) result_maze(m,n);printf(nnPress Enter Contiue!n);getch

25、ar();while(getchar()!=n);break;case 2:printf(n 请输入行数：);scanf(%d,&m);printf(n);printf( 请输入列数：);scanf(%d,&n);while(m39)|(n39)printf(n抱歉，你输入的行列数超出预设范围(0-39,0-39), 请重新输入：nn);printf( 请输入行数：);scanf(%d,&m);printf(n);printf( 请输入列数：);scanf(%d,&n);zidong_maze(m,n);print_maze(m,n);课程设计说明书No. 19mgpath(maze,m,n);if(X!=0) result_maze(m,n);printf(nnPress Enter Contiue!n);getchar();while(getchar()!=n);break;case 3:cycle=(-1);break;default:printf(n);printf(你的输入有误!n);printf(nPress Enter Contiue!n);getchar();while(getchar()!=n);break;