迷宫问题求解

山东理工大学计算机学院课程设计（数据结构）二○一一年一月二十日班级姓名学号指导教师课程设计任务书及成绩评定Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。2、设计题目要求：问题描述：求迷宫中从一个入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向再继续探索，直到所有可能的通路都探索到为止；假如所有可能的通路都探索到而未能到达出口，则所假定的迷宫没有解。基本要求：首先实现一个以链表作存储结构的栈的类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向，可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。课题名称迷宫问题求解Ⅱ、设计进度及完成情况日期内容1.10-1.11选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。1.12~1.14创建相关数据结构,录入源程序。1.17~1.19调试程序并记录调试中的问题，初步完成课程设计报告。1.20~1.21上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。Ⅲ、主要参考文献及资料[1]严蔚敏数据结构（C语言版）清华大学出版社1999[2]严蔚敏数据结构题集（C语言版）清华大学出版社1999[3]谭浩强C语言程序设计清华大学出版社[4]与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一一年一月二十一目录第一章概述....................................................................................................................................1第二章系统分析............................................................................................................................2第三章概要设计............................................................................................................................4第四章详细设计............................................................................................................................7第五章运行与测试......................................................................................................................13第六章总结与心得......................................................................................................................16参考文献:......................................................................................................................................17数据结构程序设计1第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。本次课设我选择了迷宫问题，迷宫求解是数据结构课程的一个经典问题。迷宫问题要求寻找一条从入口到出口的路径。即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路，通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。对于栈的内容在整个学期的学习中我也有了一定的了解，所以选择了迷宫这一经典问题作为本次课设的内容。数据结构程序设计2第二章系统分析求迷宫中从一个入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路返回，换一个方向再继续探索，直到所有可能的通路都探索到为止；假如所有可能的通路都探索到而未能到达出口，则所假定的迷宫没有解。迷宫问题要求寻找一条从入口到出口的路径。通常用的是“穷举求解”的方法。为了保证在任何位置上都能原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求解迷宫通路的算法中要应用“栈”的思想。1:基本原理分析迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。2:功能设计分析1:以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫任何一个位置，均约定东、南、西、北四个方向可通。2:以一个二维数组Maze[m+2][n+2]表示迷宫，而Maze[0][j]Maze[m+1][j](0=j=n+1)及Maze[i][0]和Maze[i][n+1](0=i=m+1)为做外层的一圈障碍，数组中以0表示通路，1表示障碍。3：用户需用输入迷宫的数据：第一行的数据为迷宫的行数m和列数n；从第2行至第m+1行（每行n个数）为迷宫值，用0，1输入，同行中的两个数字之间用空白字符相隔。4:迷宫的入口位置和出口位置可由用户随时设定。5:若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件上,若设定迷宫不存在通路则报告相应信息。数据结构程序设计36:本程序只求出一条成功的通路。7:程序执行的命令为：1：输入迷宫的行和列；2：创建迷宫；3：求解迷宫；4：输出迷宫的解。数据结构程序设计4第三章概要设计1、数据结构及其抽象数据类型的定义。（1）栈的抽象数据类型ADTStack{数据对象：D={ai|ai∈CharSet,i=1,2…n,n=0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…n}基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：销毁栈S。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已存在。数据结构程序设计5操作结果：删除S的栈顶元素，并以e返回其值。StackTraverse（S，visit（））初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。}ADTStack（2）迷宫的抽象数据类型ADTmaze{数据对象：D={ai,j|ai,j∈{'','0','1'},0=i=m+1,0=j=n+1,m,n=10}数据关系：R={ROW,COL}基本操作：Initmaze(intmaze[M][N])初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫数组，并在迷宫四周加上一圈障碍。MazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2])初始条件：迷宫maze已被赋值。操作结果：输出迷宫的矩阵形式，其值为0或1，如果迷宫有从入口到出口的路径，则输出三元组即坐标和方向，假若没有同路，则系统给出提示。}ADTmaze2、整体框架本程序包含三个模块（1）栈模块——实现栈抽象数据类型,以链式存储结构为基础设计的，因为本设计常做查找路径，所以采用了栈的链式存储结构，其中包括栈的初始化，建栈，入栈，出栈，判栈是否为空等操作。本模块主要实现实现探索有无通路时的先进后出的操作。（2）迷宫模块——实现迷宫抽象数据类型即输入行和列，数值，最后建立迷宫，并且在屏幕上输处迷宫的形式。（3）主程序模块：voidmain(){初始化；建立迷宫输入入口的横坐标,纵坐标[逗号隔开]；输入出口的横坐标,纵坐标[逗号隔开]；数据结构程序设计6调用MazePath(structmarkstart,structmarkend,intmaze[M][N],intdiradd[4][2])}（4）各模块之间的调用关系如图一：图一：调用关系图（5）程序的实现：标记入口位置（说明此位置已试探），把入口压入栈中栈非空栈非空取栈顶元素初始试探方向存在试探方向确定试探位置的坐标试探位置是否为迷宫出口打印路径上每个位置是否为通道标记该位置换个方向试探返回该位置及方向进栈前进到下一位置3、数据结构的选择本设计采用的栈的链式存储结构，因为在进行探索是否有通路的过程中，常进行查找，比较，看看是否有通路，所以对于查找操作倾向于采用链式存储结构，同时对于链式存储结构不用限定存储空间的大小，这个优点对设计很有利，所以采用了链式存储结构。数据结构程序设计7第四章详细设计1：设计每个成员函数：structmark//定义迷宫内点的坐标类型{intx;in