数据结构课程设计-迷宫求解.doc

26湖南人文科技学院·课程设计湖南人文科技学院计算机系数据结构课程设计课程名称:数据结构课程代码:题 目:迷宫求解年级/专业/班:09级计算机科学与技术1班学生姓名:学 号 :指导老师:开题时间:2010-12-21完成时间:2010-12-26目 录摘 要3Abstract3一、引 言1二、设计目的与任务11、设计目的是12、设计任务是2三、设计方案与实施21、总体设计思想22、设计流程图33、详细设计44、程序清单45、程序调试与体会46、运行结果（截图）5五、致 谢13参考文献14附件14摘 要随着计算机的高速发展，计算机能很简便地解决很多问题。C语言编程也是解决问题的一种语言。而此我们的数据结构程序设计是解决迷宫问题。求迷宫(老鼠吃奶酪)中从入口到出口的路径是一个经典的程序设计问题。“数据结构”成为计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其它理工专业的热门选修课。主要包括线性表、树和二叉树以及图等基本类型的数据结构。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科，包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容，其中逻辑结构可分为线性结构和非线性结构；存储结构可分为顺序存储和链式存储两类，图则属于逻辑结构中的非线性结构。广度优先搜索(BFS)用的队列一步一步完成的，从而找到的是最短路径。关键词：队列，广度优先，搜索，最短路径，遍历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 classic 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 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, 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 path1、总体设计思想(1) 迷宫形状由0表示可通过，用1表示是障碍。为方便用0,1输入。并把迷宫图形保存在二维数组Map中。而打印出的图形中 表示能过表示障碍.(2) 对探索过的位置加以标记Used，输入起点终点后可由BFS（）来完成搜索。到目的点就可退出该调用程序。把每步路径保存到Mark内，通过反向进行退步可把完整的路径保存在结构体result数组re内，通过标记的路径可将串str作相应的改变就能输出的带路径的图。(3) 根据二维字符数组和加标记的位置坐标，输出迷宫的图形。(4) 该程序在获取迷宫图结构后，可对迷宫任意入口到出口的路线进行搜索，主要由广度优先搜索完成该操作。它可以是100以内大小的迷宫，有自行提供的迷宫图，本课程设计是以二维数组作为迷宫的存储结构。而广度优先搜索(BFS)用的队列一步一步完成的，从而找到的是最短路径；该程序还能选择是4方向还是8方向的迷宫走法。并能输出打印2、设计流程图开始输入迷宫图形显示迷宫图形输入起点终点是否符合题意输出路径节点输出迷宫路线是否继续？是否更换迷宫结束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()/对上面函数的结合应用4、程序清单见附件5、程序调试与体会调试：在我组的集体努力下，课程设计终于完成，由于我们对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编写程序的过程中出现了一些问题。对于打字有时粗心导致出现一些难以发现的小错误，在我们的耐心，细致的调试下最终使得程序能够运行，课程设计完满完工。1、问题一：求出起点到终点的路径 现象：求出的结果总是无任何现象原因：把相关重要的变量重复定义以至赋过的值被覆盖2、 问题二：常量转义字符现象：出现不正常字符常量原因：''字符常量形式弄错3、问题三：输入起点终点时，未判断下标越界就使用数据现象： 原因：未判断下标越界就使用数据体会：在复杂的程序，都可以拆成一个个简单的小部分，逐个击破，再拼凑起来，在复杂的事也变的简单了。由于本程序较大，调试时多人协作能更容易找出程序的错误并修改。6、运行结果（截图）将程序员录入后,让其运行。将会出现一个菜单的界面，执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均会有相应的提示。操作简单方便实用，下面即为一些操作的示意图。运行程序后出界面，运行结果如图所示。#include <stdlib.h>#include <iostream>#include <string>#include <queue>/ 这个是stl 它是一个方便的东西 #include <fstream>#include <conio.h>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<Point> 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<0|temp.x>=n|temp.y<0|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;i1<256*256;i1+) strcpy(stri1," ");for(i1=0;i1<n;i1+)for(j1=0,xj=0;xj<n;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 <35-2*n&&(35-2*n)>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;wri<ri;wri+) if(rewri.rx<rewri+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.ry<rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+2*rewri+1.ry-1,""); if(rewri.rx>rewri+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.ry>rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+2*rewri.ry-1,""); if(rewri.rx<rewri+1.rx&&rewri.ry<rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)+1+2*rewri.ry,""); if(rewri.rx<rewri+1.rx&&rewri.ry>rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)+(2*n-1)-1+2*rewri.ry,""); if(rewri.rx>rewri+1.rx&&rewri.ry<rewri+1.ry) strcpy(str2*rewri.rx*(2*n-1)-(2*n-2)+2*rewri.ry,""); if(rewri.rx>rewri+1.rx&&rewri.ry>rewri+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<0|s.x>=n|s.y<0|s.y>=n)printf("起点越界,不符合!n");flag = false;else if(t.x<0|t.x>=n|t.y<0|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("ttt<请按提示操作>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+)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 15 40 11 0 15 80 2 14 12 40 2 14 12 80 0 0 15 40 0 0 15 8*/返回