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

枣庄学院信息科学与工程学院

课程设计任务书题目： 迷宫求解课程设计 学号： 姓名： 专业：网络工程 课程：数据结构 指导教师： 职称： 完成时间：2011年12月----2011年12月枣庄学院信息科学与工程学院制年月日课程设计任务书及成绩评定课程设计的任务和具体要求根据课堂讲授内容，学生做相应的自主练习，消化数据结构课堂所讲解的内容；通过调试典型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力、团体合作能力。它的任务就是训练学生对计算机数据对象进行分析的能力，选择适当的数据结构及相关算法的能力。此程序的任务是实现把能走的最短路找到，并很直观的显示在屏幕上的功能。指导教师签字：_ 、— 日期：_指导教师评语成绩： 指导教师签字： 日期：

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

3.2设计流程图3.3详细设计struetPoint{intx,y,s;}这个结构体是用来做广度搜索的对每个迷宫节点有相应的s（最短的步数，当然有些是不可达的）intmove[8][2]={{1,0},{0,1},{—1,0},{0,—1},{1,1},{—1,—1},{1,—1},{—1,1}};//intBFS(intstep)//广度搜索用来算出最短路径的走法并将走法保存在re数组结构体中intInitialization()//将str[][]图形初始化intFormat_Limit()//图形打印格式限制intPrint_Maze_Figure()//打印出图形intPPMF()//打印出迷宫图形intSave_Path()//将路径保存在str[][]中并打印出路径迷宫图形intInit()//从文件中植入数据完成对Map迷宫图的结构intJudge()//判断输入的起点终点是否符合实际intmain()//对上面函数的结合应用3.4程序清单#include<stdlib.h>#include<iostream>#include<string>#include〈queue〉//这个是stl它是一个方便的东西#include<fstream>#include<conio.h>usingnamespacestd;struetresult{intrx,ry;}re[100*100];intri=-1;struetPoint{intx,y,s;}s,t;//s代表起点t代表终点intmark[100][100];//用来标记怎么走到这个地方的(保存的是方向的序号)：0,1,2,3,4,5,6,7boolUsed[100][100];//标记已经走过的地方boolMap[100][100];//输入0,1表示迷宫intmove[8][2]={{1,0},{0,1},{—1,0},{0,—1},{1,1},{—1,—1},{1,—1},{—1,1}};//intn,m;intBFS(intstep)//广度搜索用来算出最短路径的走法并将走法保存在re结构体中{queue<Point>My;s.s=0;while(!My.empty())My.pop();My.push(s);Pointtemp,sl;while(!My.empty()){s1=My.front();My.popO;if(sl.x==t.x&&sl.y二二t.y){intu;re[++ri].rx二sl.x;re[ri].ry二sl.y;printf(“到目的地了\n步数:％d\n(%2d,%2d)〈- "，s1.s,s1.x,s1.y);for(intj二1;j<=s1.s;j++){u=s1.x;s1.x=s1.x-move[mark[s1.x][s1.y]][0];s1.y=s1.y-move[mark[u][s1.y]][1];re[++ri].rx二s1.x;re[ri].ry=s1.y;printf(“(％2d,%2d)〈- "，s1.x,s1.y);if((j+1)%5==0)printf("\n");}printf("\n");system("pause");system("cls");return1;}for(inti=0;i<step;i++)temp.x=sl.x+move[i][0];temp.y=sl.y+move[i][l];temp.s=sl.s;if(temp.x<0||temp.x>二n||temp.y<0||temp.y>二n||Used[temp.x][temp.y]||Map[temp.x][temp.y])continue;else{mark[temp.x][temp.y]=i;temp.s+=1;My.push(temp);Used[temp.x][temp.y]=true;}}}printf("不好意思，起点至终点无路径不可达！！！！\n");return0;}charstr[256*256][3]; //串保存图intInitialization()//将str[][]图形初始化{intil,jl,xj;for(il=0;il<256*256;il++)strcpy(str[il],"");for(il=O;il<n;il++){for(jl=0,xj=0;xj<n;jl二jl+2,xj++){if(Map[il][xj]==0)strcpy(str[2*il*(2*nT)+jl],"・")；elsestrcpy(str[2*il*(2*nT)+jl],"D");}}return1;}intFormat_Limit()//图形打印格式限制{for(inti=0;i<35-2*n&&(35-2*n)>0;i++)printf(“")；return1;}intPrint_Maze_Figure()//打印出图形{inti,xi,xj;Format_Limit();for(i=0;i<=n*2;i++)printf("□");printf("\n");for(xi=0,xj=0;xj<((2*nT)*(2*nT));xj++,xi++){if(0==xi){Format_Limit();printf("h);}printf("%s",str[xj]);if(xi==2*n-2){printf("□、『)；xi=-1;}}Format_Limit();for(i=0;i<=n*2;i++)printf("□");printf("\n");return1;}intPPMF()//打印出迷宫图形{printf("\t\t\t\t[迷宫为]\n\t\t\t•表可走，□表不可走\n");Initialization();Print_Maze_Figure();return1;}intSave_Path()//将路径保存在str[][]中并打印出路径迷宫图形{printf("\t\t\t [迷宫路径图]\n(%d,%d)至(%d,%d)\t\t•表可走，□表不可走\n",s.x,s.y,t.x,t.y);Initialization();strcpy(str[2*s.x*(2*n-1)+2*s.y]，"起")；strcpy(str[2*t.x*(2*n-1)+2*t.y],"终")；for(intwri=O;wri<ri;wri++){if(re[wri].rx<re[wri+1].rx&&re[wri].ry==re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)+2*re[wri].ry],"t");if(re[wri].rx==re[wri+1].rx&&re[wri].ry<re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+2*re[wri+1].ry-1],"〜")；if(re[wri].rx>re[wri+1].rx&&re[wri].ry==re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-1)+2*re[wri].ry],"I");if(re[wri].rx==re[wri+1].rx&&re[wri].ry>re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+2*re[wri].ry-1],"f");if(re[wri].rx<re[wri+1].rx&&re[wri].ry<re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)+1+2*re[wri].ry]," \");if(re[wri].rx<re[wri+1].rx&&re[wri].ry>re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)-1+2*re[wri].ry]," /");if(re[wri].rx>re[wri+1].rx&&re[wri].ry<re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-2)+2*re[wri].ry],"/");if(re[wri].rx>re[wri+1].rx&&re[wri].ry>re[wri+1].ry)strcpy(str[2*re[wri].rx*(2*n—l)—(2*n—l)T+2*re[wri].ry],〃 \〃）;}Print_Maze_Figure();return1;}//队列intInit()//从文件中植入数据完成对Map迷宫图的结构{FILE*pf;inti,j;pf=fopen("maze.txt","r");if(pf==NULL)return0;fscanf(pf,"%d"，&n);for(i=0;i<n;i++)for(j=0;j<n;j++){Used[i][j]=false;fscanf(pf,"%d"，&Map[i][j]);}fclose(pf);return1;}intJudge()//判断输入的起点终点是否符合实际{boolflag=true;if(s.x<0||s.x>二n||s.y<0||s.y>二n){printf(“起点越界，不符合!\n");flag=false;}elseif(t.x<0||t.x>二n||t.y<0||t.y>二n){printf(“终点越界，不符合！\n");flag=false;}elseif(Map[s.x][s.y]){printf(“起点是墙，不符合！\n");flag=false;}elseif(Map[t.x][t.y]){printf(“终点是墙，不符合！\n");flag=false;}elseif(s.x==t.x&&s.y==t.y){printf(“起点是终点，不符合！\n");flag=false;}if（!flag）{ printf（〃是则再输入\\否则退出程序：（Y/N）\n〃）;charch[20];scanf("%s",ch);if(ch[O]=='Y'||ch[O]=='y')return1;elsereturn0;}return2;}intmain(){charch;inti,j,step;printf("\t\t\t〈请按提示操作>\n");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++){Used[i][j]=false;scanf(〃％d〃，&Map[i][j]);}}boolflag二true;while(flag){for(i=0;i<n;i++)for(j=0;j<n;j++)Used[i][j]=false;ri=-1;system("pause");system("cls");printf("是否显示原始迷宫：(Y/N)\n");ch=getch();if(ch二二，Y'||ch二二,y，)PPMF();again:printf("请输入起点与终点：(xly1x2y2)");scanf("%d%d%d%d",&s.x,&s.y,&t.x,&t.y);if(1==Judge())gotoagain;elseif(0==Judge())break;printf("请选择4方向还是8方向的迷宫：")；scanf("%d"，&step);if(8==step)step=8;elsestep=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，)gotonext;}}return0;}/*测试例子5000001111000000TOC\o"1-5"\h\z01 1 1 100 0 0 000 4 4 41600 0 0 0 0 0 0 0 0 0 0 0 0 0 011 1 1 1 1 1 1 1 1 1 1 1 1 1 000 0 0 0 0 0 0 0 0 0 0 0 0 1 001 1 1 1 1 1 1 1 1 1 1 1 0 1 001 0 0 0 0 0 0 0 0 0 0 1 0 1 001 0 1 1 1 1 1 1 1 1 0 1 0 1 001 0 1 0 0 0 0 0 0 1 0 1 0 1 001 0 1 0 1 1 1 1 0 1 0 1 0 1 001 0 1 0 1 0 1 1 0 1 0 1 0 1 001 0 1 0 1 0 0 0 0 1 0 1 0 1 001 0 1 0 1 1 1 1 1 1 0 1 0 1 001 0 1 0 0 0 0 0 0 0 0 1 0 1 001 0 1 1 1 1 1 1 1 1 1 1 0 1 001 0 0 0 0 0 0 0 0 0 0 0 0 1 001 1 1 1 1 1 1 1 1 1 1 1 1 1 000 0 0 0 0 0 0 0 0 0 0 0 0 0 000 8 6 401 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 001 0 1 0 1 0 1 0 1 0 1 0 1 0 110 1 0 1 0 1 0 1 0 1 0 1 0 1 0

0100011101010010001000000000100000010101010101010101010101010101001515801408TOC\o"1-5"\h\z10 1 0 1 0 101 0 1 0 1 101 1 1 1 1 100 0 1 0 1 011 1 1 1 0 101 1 1 1 1 111 1 0 1 0 101 0 1 0 1 007 9 800 0 1 0 1 0 1 1 1 0 1 1 1 011 0 0 0 1 0 1 1 1 0 1 1 1 000 1 0 0 0 0 0 1 0 0 1 1 1 000 0 0 0 0 0 0 0 0 1 0 1 0 000 1 0 0 1 0 1 1 1 0 0 0 0 111 0 1 0 1 0 0 0 0 1 0 1 0 000 0 0 0 0 0 0 0 0 1 0 1 0 000 0 0 1 0 1 1 1 1 0 1 1 1 000 1 0 1 0 1 0 0 0 0 1 1 0 000 0 1 0 1 0 1 0 0 1 0 0 0 110 0 0 0 0 1 0 0 0 0 1 1 0 000 0 1 1 1 0 0 0 1 0 0 0 1 000 1 0 0 0 0 1 0 1 0 0 1 0 011 0 0 1 1 1 0 0 0 1 0 1 0 000 1 1 0 0 0 0 0 1 0 0 0 0 010 0 0 0 1 0 0 0 0 1 0 1 0 01101541101582141242141280015400158

*/3.5程序调试与体会调试：经过几天的努力，课程设计终于完成，由于我对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编写程序的过程中出现了一些问题。对于打字有时粗心导致出现一些难以发现的小错误，在我的耐心，细致的调试下最终使得程序能够运行，课程设计完满完工。1、 问题一：求出起点到终点的路径现象：求出的结果总是无任何现象原因：把相关重要的变量重复定义以至赋过的值被覆盖2、 问题二：常量转义字符现象：出现不正常字符常量原因：’\'字符常量形式弄错3、 问题三：输入起点终点时，未判断下标越界就使用数据原因：未判断下标越界就使用数据体会：在复杂的程序，都可以拆成一个个简单的小部分，逐个击破，再拼凑起来,在复杂的事也变的简单了。

3.6运行结果（截图）将程序员录入后，让其运行。将会出现一个菜单的界面，执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均会有相应的提示。操作简单方便实用，下面即为一些操作的示意图。运行程序后出界面，运行结果如图所示。賦"E:\SES构已迷宫求fi.exe"是否显示原始迷宫：(Y/N)□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□走口可□口口1不口两表□口口宫□口迷•—走口可□口口表口□■□□■□□■□□■□□□□□□□■••••□•••••••••□•□□□•□□□■□□■•□□□■■■□•□•■■■■□□••■■■□••••■□□□□□□•□□•□□•□□•□□□□□•□□•□□•□□•□□□□□•□□□□□•□□•□倩输入起点.与终点.：(siylk2y2)011015倩选择4方向还是塔方向的迷宫:4倩按任意键继续...□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□数据錯构\Debug\j£宫求lft.exe"到目的地了歩数低(0,15)<-(1,15)<-(2,15)<-(3,15)<-(3,14)<-(4,14)<-(5,14)<-(5,15)<-(乞15)<-(7,15)<-(8,15)<-(8,14)<-(9,14)<-(10,14)<-(10,15)<-(11,15)<-(12,15)<-(13,15)<-(14,15)<-(14,14)<-(14,13)<-(14,12)<-(13,12)<-(12,12)<-(12,11)<-(11,11)<-(10,11)<-(10,10)<-(10,9)<-(11,9)<-(12,9)<-(13,9)<-(14,9)<-(14,8)<-(14,7)<-(14,6)<-(14,5)<-(15,5)<-(15,4)<-(15,3)<-(15,2)<-(14,2)<-(14,1)<-(14,0)<-(13,0)<-(12,0)<-(12,1)<-(12,2)<-(11,2)<-(10,2)<-(9,2)<-(8,2)<-(7,2)<-(7,3)<-(7,4)<-(6,4)<-(6,5)<-(6,6)<-(6,7)<-(&7)<-(4,7)<-(3,7)<-(3,8)<-(3,9)<-(3,10)<-(2,10)<-(2,11)<-(1,11)<-(0,11)<-请按任意键继续.•.C：c"E:\SES构\D曰迷宫求解.田ce；"□•□□表□□口J走□□□□□□起•J•□□□□□□□□□□□[终[f[•[t[•[t[•[•□□□□□□••□•J□□□•■<—•■<—•□•□••□□□•■■•□[■•••□•□••[••••□•□•t[•[□□□□•□□□■H•[□■■••□□•f[•[•□••□•••□[□••f••□□t••[•■t■□•■■□f[•[■□t•□■•□•f[•[□•t••□1•□•t[•[••t•□•1••■t[■[□□□□□口孵走口[M可□口

表口□□）至（□□■o,□■15）□□•□□□••••••■■•□□□□□口口□□□□口□□―>□□―>□□―>■□—•口―>■□□□―>□•□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□口JO是否继续(Y/N)是否更换迷宫(Y/N)倩按任意键继续...曲"E：\数据踣构\Debug\迷宫^ft.exe"是否使用系统提洪的迷宫图：(丫颅)请按任意键继续•••C：c"E：\数据结构\D已bug\迷宫求fi.exe"是否显示原始迷宫:(Y/N)表□可□瞇宫□□70表□]走□□■□□■•□走□•□□•口」□□□□□□□□□■□□□□■■•□•□□□■□•□•••••□••□•••••••••□••□••□•□□□••□■□•□•■■■□■■■■•••■■■□■•••□•□□□□•□•□•□•□••••□••□•□•□••□•■■■••□■■■■□■■□□□•■■□■■□□□•□□•□□□□□□□□□□□•□□•□□•□□□□□•□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□