数据结构迷宫求解(代码参数)课程设计.doc

枣 庄 学 院信息科学与工程学院课程设计任务书 题目： 迷宫求解课程设计 学 号： 姓 名： 专 业： 网络工程 课 程： 数据结构 指导教师： 职称： 完成时间： 2011 年 12 月-20 11 年 12 月枣庄学院信息科学与工程学院制 年 月 日课程设计任务书及成绩评定课程设计的任务和具体要求根据课堂讲授内容，学生做相应的自主练习，消化数据结构课堂所讲解的内容；通过调试典型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力、团体合作能力。它的任务就是训练学生对计算机数据对象进行分析的能力，选择适当的数据结构及相关算法的能力。 此程序的任务是实现把能走的最短路找到，并很直观的显示在屏幕上的功能。指导教师签字： 、 日期： 指导教师评语成绩： 指导教师签字： 日期： 课程设计所需软件、硬件等电脑、C+6.0课程设计进度计划起至日期工作内容备注参考文献、资料索引序号文献、资料名称编著者出版单位1 数据结构 蒋秀英，栾晓春，燕孝飞 中国石油大学出版社2 数据结构(C语言版)M, 严蔚敏等 清华大学出版社3 数据结构用面向对象方法与C+描述， 殷人昆等 清华大学出版社4 编程爱好者网站（迷宫问题）5编程论坛/thread-247790-1-7.html（迷宫问题）目 录摘 要21引 言32设计目的与任务32.1设计目的是32.2设计任务是43设计方案与实施43.1总体设计思想43.2设计流程图53.3详细设计63.4程序清单63.5程序调试与体会63.6运行结果（截图）7结 论 15致 谢15摘 要随着计算机的高速发展，计算机能很简便地解决很多问题。C语言编程也是解决问题的一种语言。而此我们的数据结构程序设计是解决迷宫问题。求迷宫(老鼠吃奶酪)中从入口到出口的路径是一个经典的程序设计问题。“数据结构”成为计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其它理工专业的热门选修课。主要包括线性表、树和二叉树以及图等基本类型的数据结构。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科，包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容，其中逻辑结构可分为线性结构和非线性结构；存储结构可分为顺序存储和链式存储两类，图则属于逻辑结构中的非线性结构。广度优先搜索(BFS)用的队列一步一步完成的，从而找到的是最短路径。关键词：队列，广度优先，搜索，最短路径，遍历1引 言数据结构是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和比较，内容非常丰富。本课程设计我们要解决的问题是图迷宫求解问题。本需要用到栈的相关数据结构。但我们这个程序没有用栈，而是用队列替代栈的功能，使程序运行效率更加高。还用到求迷宫问题最平常的数据结构算法，即广度优先搜索算法(BFS)，还保持了它的路径，再从串中输出图。本课程设计总的思路要解决的问题是构造迷宫，寻找路线，打印路径。我们首先要做的是创建一个二维数组，用以来存储图，然后我们要想好怎样利用BFS算法来寻找路线。把这个算法以及其他过程写成调用函数，各自调用后调试程序。达到满意结果后写报告。2设计目的与任务2.1设计目的是根据课堂讲授内容，学生做相应的自主练习，消化数据结构课堂所讲解的内容；通过调试典型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力、团体合作能力。2.2设计任务是它的任务就是训练学生对计算机数据对象进行分析的能力，选择适当的数据结构及相关算法的能力。 此程序的任务是实现把能走的最短路找到，并很直观的显示在屏幕上的功能。3设计方案与实施3.1总体设计思想(1) 迷宫形状由0表示可通过，用1表示是障碍。为方便用0,1输入。并把迷宫图形保存在二维数组Map中。而打印出的图形中 表示能过表示障碍.(2) 对探索过的位置加以标记Used，输入起点终点后可由BFS（）来完成搜索。到目的点就可退出该调用程序。把每步路径保存到Mark内，通过反向进行退步可把完整的路径保存在结构体result数组re内，通过标记的路径可将串str作相应的改变就能输出的带路径的图。(3) 根据二维字符数组和加标记的位置坐标，输出迷宫的图形。(4) 该程序在获取迷宫图结构后，可对迷宫任意入口到出口的路线进行搜索，主要由广度优先搜索完成该操作。它可以是100以内大小的迷宫，有自行提供的迷宫图，本课程设计是以二维数组作为迷宫的存储结构。而广度优先搜索(BFS)用的队列一步一步完成的，从而找到的是最短路径；该程序还能选择是4方向还是8方向的迷宫走法。并能输出打印3.2设计流程图开始输入迷宫图形显示迷宫图形输入起点终点是否符合题意输出路径节点输出迷宫路线是否继续？是否更换迷宫结束3.3详细设计struct Pointint x,y,s;这个结构体是用来做广度搜索的对每个迷宫节点有相应的s(最短的步数，当然有些是不可达的)int move82 = 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 main()/对上面函数的结合应用3.4程序清单#include #include #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,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(int 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 = 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;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(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中并打印出路径迷宫图形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.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(str2*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);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.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(是否使用系统提供的迷宫图:(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);printf(是否显示原始迷宫:(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();printf(是否继续(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 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 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 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 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 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 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