数据结构迷宫问题求解

《数据结构迷宫问题求解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件学院课程设计报告设计名称:选题名称:名:学号:专业班级数据结构课程设计迷宫问题求解王海洋1515925530移动二班系（院）:软件学院设计时间：2016.12・5〜2016・12・9设计地点：15#6061.课程设计目的通过布置具有一定难度的实际程序设计项目，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；使学生掌握分析问题，求解问题的方法并提高学生设计编程实现的能力。2.课程设计任务与要求:任务设计题目从任务书所列选题表中选取，每人1题。要求：基本要求：1.要求利用cc++语言来完成系统的设计

2、；2.突出C语言的函数特征（以多个函数实现每一个子功能）或者C卄语言面向对象的编程思想;3.画出功能模块图；4.进行简单界面设计，能够实现友好的交互；5.具有清晰的程序流程图和数据结构的详细定义；6.熟练掌握C语言或者C++语言的各种操作。创新要求：在基本要求达到后，可进行创新设计，如系统用户功能控制，改进算法的实现，实现友好的人机交互等等3・课程设计说明书一需求分析1.可以任意定义一个迷宫，用栈的方法求出找出迷宫的通路，并把路径输出出来。2.迷宫的存储使用数组存储；3.应该考虑算法的时间和空间复杂度。4.当确定迷宫的规模以及形态以后要把至少一条能走岀迷宫的路径输岀出

3、来；5.当迷宫不通时要能修改迷宫和岀入口6.程序应当满足正确性、可读性、健壮性和高效率及低存储量等目标要求，遵循代码规范，方便调试和阅读。二系统设计利用了C++完成了这个迷宫问题求解。在设计中采用二维数组來保存迷宫地图，利用栈來在迷宫屮找寻通道；基本功能：（1）选择自动生成迷宫还是手动输入迷宫地图，0为通路，1为不通（2）选择出入口的设置是随机牛成还是手动输入；（3）当迷宫不通时，选择重新牛成迷宫或者重新设置岀口、入口；有功能模块图和流程图1•迷宫流程图：迷宫问题求解自动生成出入口结束迷宫足否通岀入手动输入岀入口童新生成迷宮还是出入口2.寻找迷宫通路函数:■寻找迷宫通

4、路函数当前位It是否诵否・将当前位賈数堀入栈迷宫不通找寻四个方向哪个能通栈是否为空否・找寻光毕且栈不空"岀栈当前位貿周围是否寻找気毕且栈不空找寻充毕且找空・3.查找迷宫通路方向函数寻找迷宫通路方向函数当前位置左侧未走过返回査找函数当前位置上侧未走过三详细设计1、首先写入头文件和宏定义#include#include#include#includeh>usingnamespacestd;#defineOVERFLOW-1〃分配空间时未分配返回值#defineMAXSIZE100//栈的最大空间#d

5、efineINCREASE10//栈慢时再分配空间#defineERROR0#defineOK1#defineStatusint2、栈的元素类型和栈指针等的定义typedefstmet//迷宫中x行y列的位置intx;inly;JLocate;typedefstruct//栈类型{intord;〃通道块在路径上的“序号”Locateseat;//ffi道块在迷宫中的“坐标位置”intdi;〃从此通道块走向下一通道块的方向1:东2:北3:西顺时针)}MazeType;tvpedefstructcMazeType*base;〃栈底指针MazeType*top;//栈顶指针

6、intstacksize;〃栈储存数据大小JMazeStack;3.o所有函数的声明StatuslnitStack(MazeStack&S);//栈的初始化StatusPush(MazeStack&S,MazeType&e);//入栈StatusPop(MazeStack&S,MazeType&e);//出栈StatusStackEmpty(MazeStack&S);//判断栈是否为空StatusMazePath(Locatestart,Locateend);//迷宫路径求解StatusPass(Locate&pos);//判断该位置能否通过voidMenu();//

7、菜单函数，选择手动生成迷宫还是自动生成等voidCreatMaze(intmazeMap[10][10]);//自动创建迷宫voidlnputMaze(intmazeMap[10][10]);//手动生成迷宫voidSetMaze(Locate&start,Locate&end);〃设置迷宫出口入口voidResetMaze(Locate&start,Locate&end);〃当迷宫不通时，重新设置入口出口坐标voidPrintMaze(intmazeMap[10][10]);〃输出迷宫voidFootPrint(Locatepos);〃走过的路留下