《[毕业设计 论文 精品]数据结构课程设计-漫步迷宫(论文).doc》由会员分享，可在线阅读，更多相关《[毕业设计 论文 精品]数据结构课程设计-漫步迷宫(论文).doc（16页珍藏版）》请在三一文库上搜索。
1、课 程 设 计 报 告学生姓名:学 号：学 院:理学院班 级:题 目:漫步迷宫指导教师： 职称: 2010 年 6 月 9 日目 录一、选题背景- 1 -1.1解决的主要问题和达到的技术要求- 1 -1.2 指导思想- 1 -二、算法设计- 2 -2.1 设计原理及方案选择- 2 -2.2 选择这个设计方案的缘由- 2 -2.2.1 方案的特点- 2 -三、程序及功能说明- 3 -3.1 程序及功能说明- 3 -四、结果分析- 4 -4.1、结果分析 - 4 -五、总 结- 5 -六、课程设计心得体会- 6 -参考文献- 7 -12一、选题背景1.1 解决的主要问题和达到的技术要求主要可以解决
2、数学建模中两地有多条通路，怎么选择一条路，使这条路的里程最短，或者根本没有路。首先从文件中读入迷宫矩阵，在这儿设计到文件数据的读写。接着要从出口和入口选择出最短的路径。从初始点开始出发，开始想四周“探测”，如果能够到达，那么把这个位置存入到一个设定的数据栈中，然后以到达的位置开始，重新探测，如此循环下去。如果最后能够到达出口位置，那么输出走出的轨迹，否则，不能够到达。迷宫的规格（即行数与列数）,状态设置(即各方格能否通行的状态)，以及入口和出口的位置，均可以由输入随机确定。求得的最短路径，可以以从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时，可以报告无路径的信息。采用结构化程序
3、设计方法，对各个模块的功能及参数作必要的说明。1.2 指导思想 随机生成一个矩阵，这个矩阵根据实际情况输入一个文件中，然后把该文件导入程序中，可以随意的选着出口和入口，通过搜索，把出口和入口之间的所有路径选择出来，通过比较选择出最短的路径。最后显示出具体的矩阵位置。二、算法设计2.1 设计原理及方案选择首先选择出所有的路径，然后从中挑选出，最短的路径。先从出口和入口选择出所有的路径，然后从选择出的所有路径中选着出最短的路径。这个过程中可以分出口和入口的先后选择，一共有两种选择。按照现实生活中的习惯，例如我们出门旅游，我们一般都先定下最终的目的地，再选择路径。所以我们在设计过程中，先定下出口，再
4、定下入口，这样就符合生活中的逻辑。使得方案更加符合实际。2.2 选择这个设计方案的缘由让自己做的方案更加符合实际、符合我们日常生活中的逻辑习惯。这样设计的软件才更加有应用价值。2.2.1 方案的特点1、思路清晰，先找出所有的路经，再选择出最短的路径。2、符合我们的日常生活逻辑习惯。3、可以解决一般的数学习题中最短路问题，直接当做软件包使用。三、程序及功能说明3.1 程序及功能说明1、确定出口的位置，也就是我们生活中的目的地。/*-输入进口的坐标-*/void enter() int a,b; printf(Please input the enter import postion:); sca
5、nf(%d%d,&a,&b); *m=a; *n=b;2、 找到从入口到出口的所有通路。/*-输出一条通路-*/void footprint(int seat) int i; i=seat; while(i!=0) printf(%d,%d) ,mazepathi-x,mazepathi-y); i=mazepathi-pre; 3、 通过比较选择出最短的路径/*-寻找一条最短的通路-*/void pass() int zx5,zy5; int i,j,x,y,z,front=1,rear=1,find=0; printf(Please input the exit postion :); s
6、canf(%d%d,&mazepath1-x,&mazepath1-y); /*mazepath1-x和mazepath1-y为迷宫的出口*/ zx1=0; zx2=1; zx3=0; zx4=-1; zy1=1; zy2=0; zy3=-1; zy4=0; enter(); while(frontx; y=mazepathfront-y; for(z=1;z0&i0&ix=i; mazepathrear-y=j; mazepathrear-pre=front; mazeij=-1; if(i=*m & j=*n) footprint(rear); find=1; front+; if(!fi
7、nd) printf(no find any way!);数据流程图打开指定文件，读取数据到矩阵输出矩阵输入起始位置和终点位置创建一个栈检验右、下、左、上，找出能到达的位置越界，或不能到达出点输出栈中存储的通路输出不可到达信息结束开始需找路径的流程图是否确定进出口位置调用maze（）（定义一组数上下左右移动依次检验右，下，上，左，是否可到达越界，到达出点？下一个位置可到达则入栈到达出点调用footprint（），输出路径否输出信息结束四、结果分析4.1、结果分析图4-1是一个5*6的比较小的矩阵，有两条通路经过，经过比较有确定了最小的路径。最后显示出来，确实有可行性。图4-1图4-2是一个6*
8、10的比较大的矩阵，有两条通路经过，经过比较有确定了最小的路径。最后显示出来，有更加广泛的应用性。这个在实际生活中是很有用的。如果从甲市道乙市有两条路，必定要经过丙市，通过比较得出最短的路径。这个编译的程序在找网格路径寻找最短路径是很有应用前景的。在实际的应用中，我们通过标准规范具体的路径长度，转化在这个矩阵中就可以求出最短路径的长度。五、总 结 1、由于要寻找从入口到出口的一条最短路径，将迷宫看作是一个图结构。则问题转化为寻找从对应于入口顶点到对应于出口顶点的一条最短路径的问题。该问题可以采用从入口顶点出发，进行广度优先搜索遍历，直到遇到出口顶点或者遍历完毕也没有遇到出口顶点为止。 2、基于
9、上述分析，涉及到数据结构的转换，即将二维数组表示的迷宫A转换为以adjlist类型的邻接表表示的图结构G。在图结构中，将迷宫中的每个方格看作是一个顶点。不可通行的方格都是孤立顶点；相邻的可通行的方格所对应的顶点之间看作是有边相连。因此迷宫可以看作是由m*n个顶点及无向边构成的一个非连通的无向图。尽管图是不连通的，但不影响本问题的求解，而且本问题有解的条件是：入口顶点与出口顶点在同一个连通分量中。 3、在广度优先搜索遍历求解最短路径过程中，设置一个队列queue作为辅助数据结构；路径采用一个整数数组pred来表示。队列queue应该设置front和rear分别指示列首与列尾，queuek表示第k
10、个入列的顶点编号。采用pred记录路径，predi表示顶点i在广度优先搜索遍历过程中的前趋顶点的编号，它表明是经过边（predi，i）达到顶点i的。这样，当路径探索成功时，我们可以从出口顶点倒推出从入口到出口的一条路径来。当然涉及到从顶点编号向方格坐标的反转换。 六、课程设计心得体会这是一个痛苦的过程，并且是一个快乐的结果。风雨过后会有彩虹。其实做了这么多回的课程设计，每回都差不多。调试过程是很痛苦的，每次听到那“嘟”听到后面总是令人崩溃的。但是听多了，最终可以运行的时候，海阔天空的感觉是很爽的。如果不经历那个痛苦的过程，是不会体会到到底有多快乐的。就像生活当中你一直在吃糖，你并不会觉得这糖有
11、多甜，如果你之前吃苦涩的东西，再吃糖，会有很甜的感觉。后者就应该整个过程的形象的比喻了。我们设计的东西要符合实际情况才有生命力，才有应用价值。不然就是简单的一个程序，像一个没有水分的橙子，吃不了但是扔了又可惜。鸡肋食之无味，去之可惜。没有应用价值的东西设计出来也没有人买，难道自己留作纪念?整个过程应该思路清晰，知道自己做完这一步下一步应该做什么。不然就会像一个迷失在大海中的小舟。驶向何方，彼岸在哪里？都不得而知。只有思路清晰了。想尽所有的办法最终到达目的。最后相信自己会成功的，才可以能成功，自己都认为自己不行，别人就更加认为你不行了。坚定信念，一定会成功的，皇天不会辜负有心人的。参考文献1 谭
12、浩强.C程序设计(第三版).北京:清华大学出版社,2005源程序#include#include#define STACKSIZE 100#define M 100#define file11 shili1.dat/*-用数组定义一个栈-*/typedef struct int x; int y; int pre;sqmaze100;int mazeMM; /*-定义迷宫，1为墙壁，0为通路-*/sqmaze *mazepath;int *m,*n; /*-m、n分别为进口的坐标-*/int row,col;/*-输入进口的坐标-*/void enter() int a,b; printf(P
13、lease input the enter import postion:); scanf(%d%d,&a,&b); *m=a; *n=b;/*-输出一条通路-*/void footprint(int seat) int i; i=seat; while(i!=0) printf(%d,%d) ,mazepathi-x,mazepathi-y); i=mazepathi-pre; /*-寻找一条最短的通路-*/void pass() int zx5,zy5; int i,j,x,y,z,front=1,rear=1,find=0; printf(Please input the exit po
14、stion :); scanf(%d%d,&mazepath1-x,&mazepath1-y); /*mazepath1-x和mazepath1-y为迷宫的出口*/ zx1=0; zx2=1; zx3=0; zx4=-1; zy1=1; zy2=0; zy3=-1; zy4=0; enter(); while(frontx; y=mazepathfront-y; for(z=1;z0&i0&ix=i; mazepathrear-y=j; mazepathrear-pre=front; mazeij=-1; if(i=*m & j=*n) footprint(rear); find=1; fro
15、nt+; if(!find) printf(no find any way!);/*-创建迷宫-*/void creatmaze() int i,j,t; FILE *fp; fp=fopen(file11,rt); fread(&row,sizeof(int),1,fp); fread(&col,sizeof(int),1,fp); for(i=1;i=row;i+) for(j=1;j=col;j+) fread(&mazeij,sizeof(int),1,fp); printf(The maze is: %d X %dn,row,col); printmaze(maze,row,col);int printmaze(int mazeMM,int m,int n) int i,j; printf(There is your maze;); for(i=1;i=m;i+) printf(n); for(j=1;j=n;j+) printf(%4d,mazeij); printf(n);/*-主函数-*/main() int row,col; creatmaze(); pass(); system(pause)