《数据结构》课程设计报告迷宫求解.docx

枣庄学院信息科学与工程学院课程设计任务书题目:迷宫设计学号:0315姓名:王宇专业:网络技术课程:数据结构指导教师:刘彩霞职称:讲师完成时间:2013年12月----2014年1月枣庄学院信息科学与工程学院制年月日课程设计任务书及成绩评定实验任务:通过数据结构运用c语言写迷宫算法,实验目的:通过综合性课程设计题目的完成过程,运用所学数据结构知识,解决生活中遇到的实际问题,达到活学活用,所学所用的目的,进一步理解数据结构的学****目的,提高实际应用水平指导教师签字:、日期:成绩:指导教师签字:日期:联想笔记本win7系统,win-tc课程设计进度计划起至日期工作内容备注13年12月初13年12月中旬13年12月下旬选择题目制定方案制作设计参考文献、资料索引序号文献、资料名称编著者出版单位[1]蒋秀英燕孝飞等,:中国石油大学,2011[2](c语言版).北京:清华大学出版社,2007目录迷宫求解································问题描述···········································需求分析及设计思路·································(3)数据结构定义········································(4)系统功能模块介绍····································(5)源代码··············································(6)运行结果及调试分析································(7)课程设计总结·····························,用递归和非递归两种方法求出一条走出迷宫的路径,并将路径输出。(2)需求分析及设计思路从入口出发,按某一方向向前探索,若能走通并且未走过,即某处可以到达,则到达新点,否则试探下一个方向;若所有的方向均没有通路,则沿原路返回前一点,换下一个方向再继续试探,直到找到一条通路,或无路可走又返回入口点。在求解过程中,为了保证在到达某一点后不能向前继续行走(无路)时,能正确返回前一点以便继续从下一个方向向前试探,则需要用一个栈(递归不需要)保存所能够到达的每一点的下标及从该点前进的方向。设迷宫为m行n列,利用maze[m][n]来表示一个迷宫,maze[i][j]=0或1;其中:0表示通路,1表示不通,当从某点向下试探时,中间点有四个方向可以试探,而四个角点有两个方向,其他边缘点有三个方向,为使问题简单化,用maze[m+2][n+2]来表示迷宫,而迷宫的四周的值全部为1,这样做使问题简单了,每个点的试探方向全部为4,不用再判断当前点的试探方向有几个。(3)数据结构定义#definem6#definen8#defineMAXSIZE100//四周为1代表围墙,0为可走路径intmaze[m+2][n+2]={{1,1,1,1,1,1,1,1,1,1},{1,0,1,1,1,0,1,1,1,1},{1,0,0,0,0,1,1,1,1,1},{1,0,1,0,0,0,0,0,1,1},{1,0,1,1,1,0,0,1,1,1},{1,1,0,0,1,1,0,0,0,1},{1,0,1,1,0,0,1,1,0,1},{1,1,1,1,1,1,1,1,1,1}};//入口坐标为(1,1),出口坐标为(6,8)typedefstruct{intx,y;/*试探方向*/}item;itemmove[4]={{0,1},{1,0},{0,-1},{-1,0}};typedefstruct/*栈的设计*/{intx,y,d;/*纵横坐标及方向*/}DataType;系统功能模块介绍创建一顺序栈:PSeqStackInit_SeqStack(void)判断栈是否为空:intEmpty_SeqStack(PSeqStackS)在栈顶插入一新元素x:intPush_SeqStack(PSeqStackS,DataTypex)删除栈顶元素并保存在*x:intPop_SeqStack(PSeqStackS,DataType*x)销毁栈:voidDestroy_SeqStack(PSeqStack*S)利用栈的非递归算法求迷宫路径:intmazepath(intmaze[][n+2],itemmove[],intx0,inty0)递归算法求迷宫路径:intmazepath1(intmaze[][n+2],itemmove[],intx,inty)主函数:intmain(){出口坐标已定,利用while循环多次输入入点坐