迷宫问题求解

1、精选优质文档-倾情为你奉上山东理工大学计算机学院课 程 设 计（数据结构）班 级姓 名学 号 指导教师二一一年一月二十日专心-专注-专业课程设计任务书及成绩评定课题名称 迷宫问题求解、题目的目的和要求： 1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2、设计题目要求：问题描述：求迷宫中从一个入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫

2、时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向再继续探索，直到所有可能的通路都探索到为止；假如所有可能的通路都探索到而未能到达出口，则所假定的迷宫没有解。基本要求：首先实现一个以链表作存储结构的栈的类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向，可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点

3、的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。、设计进度及完成情况日 期内 容1.10-1.11选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.121.14创建相关数据结构,录入源程序。1.171.19调试程序并记录调试中的问题，初步完成课程设计报告。1.201.21上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。、主要参考文献及资料1 严蔚敏 数据结构（C语言版）清华大学出版社

4、 19992 严蔚敏 数据结构题集（C语言版）清华大学出版社 19993 谭浩强 C语言程序设计 清华大学出版社4 与所用编程环境相配套的C语言或C+相关的资料、成绩评定：设计成绩： （教师填写）指导老师： （签字）二一一 年一月二十一 目录第一章 概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法

5、的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题。迷宫问题要求寻找一条从入口到出口的路径。即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路，通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对

6、于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设的内容。第二章 系统分析求迷宫中从一个入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向再继续探索，直到所有可能的通路都探索到为止；假如所有可能的通路都探索到而未能到达出口，则所假定的迷宫没有解。迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法

7、中要应用“栈”的思想。1:基本原理分析 迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。2: 功能设计分析1: 以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点

8、的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。2: 以一个二维数组Mazem+2n+2表示迷宫，而Maze0jMazem+1j(0<=j<=n+1)及Mazei0和Mazein+1 (0<=i<=m+1)为做外层的一圈障碍，数组中以0表示通路，1表示障碍。3： 用户需用输入迷宫的数据：第一行的数据为迷宫的行数m和列数n；从第2行至第m+1行（每行n个数）为迷宫值，用0，1输入，同行中的两个数字之间用空白字符相隔。4: 迷宫的入口位置和出口位置可由用户随时设定。5: 若设定的迷宫存在通路，则以长方阵形式

9、将迷宫及其通路输出到标准输出文件上, 若设定迷宫不存在通路则报告相应信息。6: 本程序只求出一条成功的通路。7: 程序执行的命令为：1：输入迷宫的行和列；2：创建迷宫；3 ：求解迷宫；4：输出迷宫的解。第三章 概要设计1、数据结构及其抽象数据类型的定义。（1）栈的抽象数据类型ADT Stack数据对象：D=ai| aiCharSet,i=1,2n,n>=0数据关系：R1=<ai-1, ai >| ai-1, aiD,i=2,n基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。

10、ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若S为空栈，则返回TRUE，否则返回FALSE。GetTop(S，&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S， e)初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。Pop(&S，&e)初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse（S，visit（

11、）初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。 ADT Stack（2）迷宫的抽象数据类型ADT maze数据对象：D=ai,j| ai,j ' ','0','1',0<=i<=m+1,0<=j<=n+1,m,n<=10数据关系：R=ROW,COL基本操作：Initmaze(int mazeMN)初始条件：二维数组arow+2col+2已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫数组

12、，并在迷宫四周加上一圈障碍。MazePath(struct mark start,struct mark end,int mazeMN,int diradd42)初始条件：迷宫maze已被赋值。操作结果：输出迷宫的矩阵形式，其值为0或1，如果迷宫有从入口到出口的路径，则输出三元组即坐标和方向，假若没有同路，则系统给出提示。 ADT maze2、整体框架 本程序包含三个模块（1）栈模块实现栈抽象数据类型,以链式存储结构为基础设计的，因为本设计常做查找路径，所以采用了栈的链式存储结构，其中包括栈的初始化，建栈，入栈，出栈，判栈是否为空等操作。本模块主要实现实现探索有无通路时的先进后出的操作。（2）

13、迷宫模块实现迷宫抽象数据类型即输入行和列，数值，最后建立迷宫，并且在屏幕上输处迷宫的形式。（3）主程序模块： void main() 初始化；建立迷宫输入入口的横坐标,纵坐标逗号隔开；输入出口的横坐标,纵坐标逗号隔开；调用MazePath(struct mark start,struct mark end,int mazeMN,int diradd42) （4）各模块之间的调用关系如图一：图一：调用关系图（5）程序的实现：标记入口位置（说明此位置已试探），把入口压入栈中 栈非空栈非空取栈顶元素初始试探方向存在试探方向 确定试探位置的坐标 试探位置是否为迷宫出口打印路径上每个位置是否为通道标记该

14、位置换个方向试探返回该位置及方向进栈前进到下一位置3、数据结构的选择 本设计采用的栈的链式存储结构，因为在进行探索是否有通路的过程中，常进行查找，比较，看看是否有通路，所以对于查找操作倾向于采用链式存储结构，同时对于链式存储结构不用限定存储空间的大小，这个优点对设计很有利，所以采用了链式存储结构。第四章 详细设计1：设计每个成员函数： struct mark /定义迷宫内点的坐标类型 int x; int y; ; struct Element /"恋"栈元素，嘿嘿。 int x,y; /x行,y列 int d; /d下一步的方向 ; typedef struct LSta

15、ck /链栈 Element elem; struct LStack *next; *PLStack; /*栈函数*/ int InitStack(PLStack &S)/构造空栈 S=NULL; return 1; int StackEmpty(PLStack S)/判断栈是否为空 if(S=NULL) return 1; else return 0; int Push(PLStack &S, Element e)/压入新数据元素 PLStack p; p=(PLStack)malloc(sizeof(LStack); p->elem=e; p->next=S;

16、S=p; return 1; int Pop(PLStack &S,Element &e) /栈顶元素出栈 PLStack p; if(!StackEmpty(S) e=S->elem; p=S; S=S->next; free(p); return 1; else return 0; /*求迷宫路径函数*/ void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42) int i,j,d;int a,b; Element elem,e; PLStack S1, S2; InitSt

17、ack(S1); InitStack(S2); mazestart.xstart.y=2; /入口点作上标记 elem.x=start.x; elem.y=start.y; elem.d=-1; /开始为-1 Push(S1,elem); while(!StackEmpty(S1) /栈不为空 有路径可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; /下一个方向 while(d<4) /试探东南西北各个方向 a=i+diraddd0; b=j+diraddd1; if(a=end.x && b=end.y &&

18、; mazeab=0) /如果到了出口 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); elem.x=a; elem.y=b; elem.d=886; /方向输出为-1 判断是否到了出口 Push(S1,elem); printf("n0=东 1=南 2=西 3=北 886为则走出迷宫nn通路为:(行坐标,列坐标,方向)n"); while(S1) /逆置序列 并输出迷宫路径序列 Pop(S1,e); Push(S2,e); while(S2) Pop(S2,e); printf("->(%d,%d,%d)"

19、;,e.x,e.y,e.d); return; /跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不错滴o(_)o. if(mazeab=0) /找到可以前进的非出口的点 mazeab=2; /标记走过此点 elem.x=i; elem.y=j; elem.d=d; Push(S1,elem); /当前位置入栈 i=a; /下一点转化为当前点 j=b; d=-1; d+; printf("没有找到可以走出此迷宫的路径n"); /*建立迷宫*/ void initmaze(int mazeMN) int i,j; int m,n; /迷宫

20、行,列 printf("请输入迷宫的行数 m="); scanf("%d",&m); printf("请输入迷宫的列数 n="); scanf("%d",&n); printf("n请输入迷宫的各行各列:n用空格隔开,0代表路,1代表墙n",m,n); for(i=1;i<=m;i+) for(j=1;j<=n;j+) scanf("%d",&mazeij); printf("你建立的迷宫为o(_)o.n"); for(

21、i=0;i<=m+1;i+) /加一圈围墙 mazei0=1; mazein+1=1; for(j=0;j<=n+1;j+) maze0j=1; mazem+1j=1; for(i=0;i<=m+1;i+) /输出迷宫 for(j=0;j<=n+1;j+) printf("%d ",mazeij); printf("n"); 2：设计主函数： void main() int stoMN; struct mark start,end; /start,end入口和出口的坐标 int add42=0,1,1,0,0,-1,-1,0;/行

22、增量和列增量 方向依次为东西南北 initmaze(sto);/建立迷宫 printf("输入入口的横坐标,纵坐标逗号隔开n"); scanf("%d,%d",&start.x,&start.y); printf("输入出口的横坐标,纵坐标逗号隔开n"); scanf("%d,%d",&end.x,&end.y); MazePath(start,end,sto,add); /find path system("PAUSE"); 第五章 运行与测试1、调试分析：（1

23、）本程序有一个核心算法，即求迷宫的路径，在调试的时候，出现的问题是：无法设计遍历是的四个方向。方法：add42=0,1,1,0,0,-1,-1,0实现四个方向。（2）在设计程序算法：寻找迷宫路径，未想到要用两个栈去实现迷宫的路径输出。在一开始在寻找时先让通的节点先进栈，最后输出路径时再借助于另一个栈输出。（3）函数MazePath ( struct mark start ,struct mark end ,int mazeMN,int diradd42)调试老出现错误，最后是试出来的。2、使用说明和运行结果： （1）首先输入迷宫数据，如图： （2）进入演示程序后，会出现以下界面如图： （3）进

24、入“创建迷宫”的命令后，即提示输入迷宫数据，结束符为“回车符”，该命令执行之后输出“迷宫建立的形式”，且输出下面可执行的操作。如图： （4）输入入口和出口位置，若有路径存在则输出通路路径，否则提示不存在从路径 如下图，出现查找成功和不成功的情况： 上图有通路 上图通路3、缺点与改进：只是手动的形式输入迷宫 ，如果迷宫数据量大时，要先建好文件还是很浪费时间，如果以随机产生函数自动产生迷宫会更好 。然用随机函数产生迷宫 比如用： for (i = 0; i < MAX_ROW; i+) for(j = 0; j < MAX_COL; j+) mazeij = (int) (rand() % 2); maze10 = 1; /* start point */ mazeMAX_ROW - 1MAX_COL - 2 = 1; /* end point */这样产生迷宫要更加的方便。结果也有不确定性，可能可以有通路也可能没有。第六章 总结与心得数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。