《[毕业设计精品] 数据结构迷宫求解课程设计.doc》由会员分享，可在线阅读，更多相关《[毕业设计精品] 数据结构迷宫求解课程设计.doc（28页珍藏版）》请在三一办公上搜索。
1、数据结构课程设计课程名称:数据结构课程代码:408024题 目:迷宫求解年级/专业/班:10级计算机科学与技术1班学生姓名:学 号 :指导老师: 开题时间:2010-12-21完成时间:2010-12-26目 录摘 要3Abstract3一、引 言1二、设计目的与任务11、设计目的是12、设计任务是2三、设计方案与实施21、总体设计思想22、设计流程图33、详细设计44、程序清单45、程序调试与体会46、运行结果（截图）5五、致 谢13参考文献14附件14摘 要随着计算机的高速发展，计算机能很简便地解决很多问题。C语言编程也是解决问题的一种语言。而此我们的数据结构程序设计是解决迷宫问题。求迷宫
2、(老鼠吃奶酪)中从入口到出口的路径是一个经典的程序设计问题。“数据结构”成为计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其它理工专业的热门选修课。主要包括线性表、树和二叉树以及图等基本类型的数据结构。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科，包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容，其中逻辑结构可分为线性结构和非线性结构；存储结构可分为顺序存储和链式存储两类，图则属于逻辑结构中的非线性结构。广度优先搜索(BFS)用的队列一步一步完成的，从而找到的是最短路径。关键词：队列，广度优先，搜索，最短
3、路径，遍历AbstractWith the rapid development of the computer,the computer can very easily solve many problems. C programming language is a language problem. Our data structure and this program is designed to solve maze problems.Find the maze(Mouse eat cheese) to the exit path from the entrance is a class
4、ic programming problem.data structure has become the important theory and the foundation of computer programming.It is not only the core curriculum of computer science,but also has became the hottest elective course of other tech professional. Mainly including linear list, trees and binary tree and
5、graph, and other basic types of data structure.Data structure is the study of the non-numerical calculation program design problem in computer operation objects and their relationship and operation，including data logical structure, data storage structure and the data of operation this three aspects,
6、 and the logical structure can be divided into linear structure and nonlinear structure.Storage structure can be divided into sequenced store and chain store two kinds.Graph belongs to the logical structure of nonlinear structure.it is breadth-first search (BFS) with the queue for find the shortest
7、pathKey words: Queue，Breadth-first ，search，Shortest path，Traversal数据结构课程设计 -迷宫求解设计一、引 言数据结构是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和比较，内容非常丰富。本课程设计我们要解决的问题是图迷宫求解问题。本需要用到栈的相关数据结构。但我们这个程序没有用栈，而是用队列替代栈的功能，使程序运行效率更加高。还用到求迷宫问题最平常的数据结构算法，
8、即广度优先搜索算法(BFS)，还保持了它的路径，再从串中输出图。本课程设计总的思路要解决的问题是构造迷宫，寻找路线，打印路径。我们首先要做的是创建一个二维数组，用以来存储图，然后我们要想好怎样利用BFS算法来寻找路线。把这个算法以及其他过程写成调用函数，各自调用后调试程序。达到满意结果后写报告。二、设计目的与任务1、设计目的是根据课堂讲授内容，学生做相应的自主练习，消化数据结构课堂所讲解的内容；通过调试典型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力、团体合作能力。2、设计任务是它的任务就是训练学生对计算机数据对象进行分析的能力
9、，选择适当的数据结构及相关算法的能力。 此程序的任务是实现把能走的最短路找到，并很直观的显示在屏幕上的功能。三、设计方案与实施1、总体设计思想(1) 迷宫形状由0表示可通过，用1表示是障碍。为方便用0,1输入。并把迷宫图形保存在二维数组Map中。而打印出的图形中 表示能过表示障碍.(2) 对探索过的位置加以标记Used，输入起点终点后可由BFS（）来完成搜索。到目的点就可退出该调用程序。把每步路径保存到Mark内，通过反向进行退步可把完整的路径保存在结构体result数组re内，通过标记的路径可将串str作相应的改变就能输出的带路径的图。(3) 根据二维字符数组和加标记的位置坐标，输出迷宫的图
10、形。(4) 该程序在获取迷宫图结构后，可对迷宫任意入口到出口的路线进行搜索，主要由广度优先搜索完成该操作。它可以是100以内大小的迷宫，有自行提供的迷宫图，本课程设计是以二维数组作为迷宫的存储结构。而广度优先搜索(BFS)用的队列一步一步完成的，从而找到的是最短路径；该程序还能选择是4方向还是8方向的迷宫走法。并能输出打印2、设计流程图开始输入迷宫图形显示迷宫图形输入起点终点是否符合题意输出路径节点输出迷宫路线是否继续？是否更换迷宫结束3、详细设计struct Pointint x,y,s;这个结构体是用来做广度搜索的对每个迷宫节点有相应的s(最短的步数，当然有些是不可达的)int move8
11、2 = 1,0,0,1,-1,0,0,-1,1,1,-1,-1,1,-1,-1,1 ;/int BFS(int step)/ 广度搜索用来算出最短路径的走法 并将走法保存在re数组结构体中int Initialization()/ 将str图形初始化int Format_Limit()/图形打印格式限制int Print_Maze_Figure()/打印出图形int PPMF()/ 打印出迷宫图形int Save_Path()/ 将路径保存在str中并打印出路径迷宫图形int Init()/ 从文件中植入数据 完成对Map迷宫图的结构int Judge()/判断输入的起点终点是否符合实际int
12、 main()/对上面函数的结合应用4、程序清单见附件5、程序调试与体会调试：在我组的集体努力下，课程设计终于完成，由于我们对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编写程序的过程中出现了一些问题。对于打字有时粗心导致出现一些难以发现的小错误，在我们的耐心，细致的调试下最终使得程序能够运行，课程设计完满完工。1、问题一：求出起点到终点的路径 现象：求出的结果总是无任何现象原因：把相关重要的变量重复定义以至赋过的值被覆盖2、 问题二：常量转义字符现象：出现不正常字符常量原因：字符常量形式弄错3、问题三：输入起点终点时，未判断下标越界就使用数据现象： 原因：未判断下标越界就使用
13、数据体会：在复杂的程序，都可以拆成一个个简单的小部分，逐个击破，再拼凑起来，在复杂的事也变的简单了。由于本程序较大，调试时多人协作能更容易找出程序的错误并修改。6、运行结果（截图）将程序员录入后,让其运行。将会出现一个菜单的界面，执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均会有相应的提示。操作简单方便实用，下面即为一些操作的示意图。运行程序后出界面，运行结果如图所示。四、结 论经过我们不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于
14、找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是迷宫求解问题，深刻的体会到它的游戏可玩性。通过本次课程设计我们发现我们对于C语言和数据结构还有很多地方不了解，今后继续努力学习。五、致 谢在这里我真心的感谢朱素英老师对我们精心的指导和不倦的教育,她在我们的课程设计过程中提出了指导性的方案和架构,时事关注我们设计的进程，并指引我们阅读相关的资料和书籍，使我们的课设能够按时顺利的完成。还有周国柱同学全面承担本次课程设计的程序编写工作,并为此付出大量的时间和精力。在这里
15、我代表我们组全体同学对他表示感谢,同时也有组员的积极配合与协作。同时也感谢学校给我们这次机会，训练我们灵活应用所学数据结构知识，独立完成问题分析的能力，让我们学会怎样结合数据结构理论知识去解决实际问题。参考文献1数据结构(C语言版)M,严蔚敏等编著.清华大学出版社,2004,2数据结构用面向对象方法与C+描述，殷人昆，陶水雷，谢若阳，盛绚华，清华大学出版社3任意N重循环的设计方法与应用J-计算机工程，肖建华,欧阳浩,何宏，2004年22期 4用人工智能中的搜索原理解决迷宫问题-微计算机信息，陈春梅，杨世恩，2006年11期5 编程爱好者网站（迷宫问题）6编程论坛附件#include #incl
16、ude #include #include / 这个是stl 它是一个方便的东西 #include #include using namespace std;struct result int rx,ry;re100*100;int ri=-1;struct Pointint x,y,s;s,t;/s代表起点 t代表终点int mark100100; /用来标记怎么走到这个地方的 (保存的是方向的序号):0,1,2,3,4,5,6,7bool Used100100;/标记已经走过的地方bool Map100100;/输入0，1表示迷宫int move82 = 1,0,0,1,-1,0,0,-1
17、,1,1,-1,-1,1,-1,-1,1 ;/int n,m;int BFS(int step) / 广度搜索用来算出最短路径的走法 并将走法保存在re结构体中queue My;s.s =0;while(!My.empty()My.pop();My.push(s);Point temp,s1;while(!My.empty()s1 = My.front();My.pop();if(s1.x = t.x&s1.y=t.y)int u;re+ri.rx=s1.x; reri.ry=s1.y;printf(到目的地了n步数:%dn(%2d,%2d) - ,s1.s,s1.x,s1.y);for(in
18、t j = 1 ;j = s1.s;j+)u = s1.x;s1.x = s1.x - move marks1.xs1.y0;s1.y = s1.y - move markus1.y 1;re+ri.rx=s1.x; reri.ry=s1.y;printf(%2d,%2d) - ,s1.x,s1.y);if(j+1)%5=0)printf(n);printf(n);system(pause); system(cls);return 1;for(int i =0 ;i step ; i+)temp.x = s1.x + movei0;temp.y = s1.y + movei1;temp.s =
19、 s1.s;if(temp.x=n|temp.y=n|Usedtemp.xtemp.y|Maptemp.xtemp.y)continue;elsemarktemp.xtemp.y = i;temp.s += 1 ;My.push(temp);Usedtemp.xtemp.y = true;printf(不好意思,起点至终点无路径不可达!n);return 0;char str256*2563; /串保存图int Initialization()/ 将str图形初始化int i1,j1,xj;for(i1=0;i1256*256;i1+) strcpy(stri1, );for(i1=0;i1n
20、;i1+)for(j1=0,xj=0;xjn;j1=j1+2,xj+)if(Mapi1xj = 0) strcpy(str2*i1*(2*n-1)+j1,);else strcpy(str2*i1*(2*n-1)+j1,);return 1;int Format_Limit()/图形打印格式限制for(int i =0; i 0;i+)printf( );return 1;int Print_Maze_Figure()/打印出图形int i,xi,xj;Format_Limit();for(i =0 ;i = n*2;i+)printf();printf(n);for(xi=0,xj=0;xj
21、(2*n-1)*(2*n-1);xj+,xi+)if(0 = xi)Format_Limit();printf(); printf(%s,strxj); if(xi=2*n-2) printf(n);xi=-1; Format_Limit();for(i =0 ;i = n*2 ;i+)printf();printf(n);return 1;int PPMF()/ 打印出迷宫图形printf(tttt迷宫为nttt 表可走，表不可走 n);Initialization();Print_Maze_Figure();return 1;int Save_Path()/ 将路径保存在str中并打印出路
22、径迷宫图形printf(ttt 迷宫路径图n(%d,%d)至(%d,%d)tt 表可走，表不可走 n,s.x,s.y,t.x,t.y);Initialization();strcpy(str2*s.x*(2*n-1)+2*s.y,起);strcpy(str2*t.x*(2*n-1)+2*t.y,终);for(int wri=0;wriri;wri+) if(rewri.rxrewri+1.rx&rewri.ry=rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)+2*rewri.ry,); if(rewri.rx=rewri+1.rx&rewri.
23、ryrewri+1.rx&rewri.ry=rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)-(2*n-1)+2*rewri.ry,); if(rewri.rx=rewri+1.rx&rewri.ryrewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+2*rewri.ry-1,); if(rewri.rxrewri+1.rx&rewri.ryrewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)+1+2*rewri.ry,); if(rewri.rxrewri+1.ry) strcpy(st
24、r2*rewri.rx*(2*n-1)+(2*n-1)-1+2*rewri.ry,); if(rewri.rxrewri+1.rx&rewri.ryrewri+1.rx&rewri.ryrewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)-(2*n-1)-1+2*rewri.ry,); Print_Maze_Figure();return 1;/队列int Init()/ 从文件中植入数据 完成对Map迷宫图的结构FILE *pf;int i,j;pf = fopen(maze.txt,r);if(pf=NULL)return 0;fscanf(pf,%d,&n);
25、for(i = 0;i n; i+)for(j = 0 ; j n; j+)Usedij = false;fscanf(pf,%d,&Mapij);fclose(pf);return 1;int Judge()/判断输入的起点终点是否符合实际bool flag = true;if(s.x=n|s.y=n)printf(起点越界,不符合!n);flag = false;else if(t.x=n|t.y=n)printf(终点越界,不符合!n);flag = false;else if(Maps.xs.y)printf(起点是墙,不符合!n);flag = false;else if(Mapt.
26、xt.y)printf(终点是墙,不符合!n);flag = false;else if(s.x=t.x&s.y=t.y)printf(起点是终点,不符合!n);flag = false;if(!flag)printf(是则再输入否则退出程序:(Y/N)n);char ch20;scanf(%s,ch);if(ch0 = Y|ch0 =y)return 1;else return 0;return 2;int main()char ch;int i,j,step;printf(tttn);next:system(pause); system(cls); printf(是否使用系统提供的迷宫图:
27、(Y/N)n); ch = getch(); if(ch = Y|ch =y) Init(); else printf(请输入迷宫的大小:(n*n);scanf(%d,&n);printf(t请输入迷宫的结构0,1表示0是路1是墙n);for(i = 0;i n; i+)for(j = 0 ; j n; j+)Usedij = false;scanf(%d,&Mapij); bool flag=true;while(flag)for(i =0 ;i n;i+)for(j =0 ;j n ;j+)Usedij = false;ri = -1;system(pause);system(cls);p
28、rintf(是否显示原始迷宫:(Y/N)n);ch = getch();if(ch = Y|ch =y)PPMF();again:printf(请输入起点与终点:(x1 y1 x2 y2);scanf(%d %d %d %d,&s.x,&s.y,&t.x,&t.y);if(1=Judge()goto again;elseif(0=Judge()break;printf(请选择4方向还是8方向的迷宫:);scanf(%d,&step);if(8=step)step=8;else step = 4;system(pause);system(cls);BFS(step);Save_Path();pr
29、intf(是否继续(Y/N)n);ch = getch();if(ch != Y&ch !=y) flag = false;if(flag)printf(是否更换迷宫(Y/N)n);ch = getch();if(ch = Y|ch =y)goto next;return 0;/*测试例子50 0 0 0 01 1 1 1 00 0 0 0 00 1 1 1 10 0 0 0 00 0 4 4 4160 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 1 1 1 1 1 1 1 1 1 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0 1 00 1 1
30、 1 1 1 1 1 1 1 1 1 1 0 1 00 1 0 0 0 0 0 0 0 0 0 0 1 0 1 00 1 0 1 1 1 1 1 1 1 1 0 1 0 1 00 1 0 1 0 0 0 0 0 0 1 0 1 0 1 00 1 0 1 0 1 1 1 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 1 0 1 0 1 0 1 00 1 0 1 0 1 0 0 0 0 1 0 1 0 1 00 1 0 1 0 1 1 1 1 1 1 0 1 0 1 00 1 0 1 0 0 0 0 0 0 0 0 1 0 1 00 1 0 1 1 1 1 1 1 1 1 1 1
31、0 1 00 1 0 0 0 0 0 0 0 0 0 0 0 0 1 00 1 1 1 1 1 1 1 1 1 1 1 1 1 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 8 6 40 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1
32、 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0 1 00 1 0 1 0 1 0 1 0 1 0 1 0 1 0 11 0 1 0 1 0 1 0 1 0 1 0 1 0
33、1 00 0 15 15 80 0 14 0 80 1 0 1 0 1 0 11 0 1 0 1 0 1 11 0 1 1 1 1 1 11 0 0 0 1 0 1 00 1 1 1 1 1 0 11 0 1 1 1 1 1 10 1 1 1 0 1 0 11 0 1 0 1 0 1 00 0 7 9 80 0 0 0 1 0 1 0 1 1 1 0 1 1 1 01 1 1 0 0 0 1 0 1 1 1 0 1 1 1 00 0 0 1 0 0 0 0 0 1 0 0 1 1 1 00 0 0 0 0 0 0 0 0 0 0 1 0 1 0 00 0 0 1 0 0 1 0 1 1 1 0
34、 0 0 0 11 1 1 0 1 0 1 0 0 0 0 1 0 1 0 00 0 0 0 0 0 0 0 0 0 0 1 0 1 0 00 0 0 0 0 1 0 1 1 1 1 0 1 1 1 00 0 0 1 0 1 0 1 0 0 0 0 1 1 0 00 0 0 0 1 0 1 0 1 0 0 1 0 0 0 10 1 0 0 0 0 0 1 0 0 0 0 1 1 0 00 0 0 0 1 1 1 0 0 0 1 0 0 0 1 00 0 0 1 0 0 0 0 1 0 1 0 0 1 0 00 1 1 0 0 1 1 1 0 0 0 1 0 1 0 00 0 0 1 1 0 0
35、 0 0 0 1 0 0 0 0 01 1 0 0 0 0 1 0 0 0 0 1 0 1 0 00 11 0 15 40 11 0 15 80 2 14 12 40 2 14 12 80 0 0 15 40 0 0 15 8*/返回课程设计任务书及成绩评定课题名称： 迷宫求解 完成者： 李小锋、田芳、黄健、周国柱 1、设计的目的与要求： 1) 灵活应用所学数据结构知识，独立完成问题分析。2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等方法。3) 训练用系统的观点和软件开发一般规范进行软件开发。4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。 2、 设计进度及完成情况日 期内 容12.21分析问题，找出所要解决问题的关键12.21总体设计，找出解决方案12.21详细设计，列出解决步骤12.21-25程序编码12.25程序调试，修改加以完善12.26书写文档3、成绩评定： 设计成绩： （教师填写）指导老师： （签字）二00 年 月 日
