文档介绍：马踏棋盘课程设计报告课程名称数据结构课程设计课题名称迷宫问题、马踏遍棋盘问题专业计算机科学与技术班级计算机0981学号200913030138姓名甘礼彬指导教师周铁山2011年7月7日湖南工程学院课程设计任务书课程名称面向对象程序设计课题迷宫问题、马踏遍棋盘问题专业班级计算机0981学生姓名甘礼彬学号200913030138指导老师周铁山审批任务书下达日期2011年6月27日任务完成日期2011年7月7日课题1迷宫问题(一)、课程设计题目:迷宫问题(二)、目的与要求:1、目的:数据结构课程设计是计算机专业的专业课程,通过课程设计使学生进一步巩固课堂所学知识,全面熟悉、掌握数据结构的基本设计方法和技巧,进一步提高分析问题、解决问题及上机操作能力,为将来从事计算机工作打下一定的专业基础2、基本要求:用计算机模拟“迷宫问题”,求出其中一条通道。用数组MZE[1..M][1..N]表示迷宫,为迷宫入口,MZE[M][N]为迷有的可以通行(0表示),有的是路障(1表示),MZE[1][1]宫出口,用非递归算法求出一条通路并用“?”标示所输出的路径(见运行示例)否则说明没有通路,继续生成迷宫,直到有通路。3、创新要求:在基本要求达到后,可进行创新设计,如根据查找结果进行修改的功能。4、写出设计说明书(三)、设计方法和基本原理:1、问题描述(功能要求):以一个M*N的长方阵表示迷宫,0和1分别表示迷宫中的可通的方块和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通道,或得出没有通道的结论。2、问题的解决方案:实现这一算法的具体方法很多(如堆栈,队列等),但基本思想一般是回溯法使用MZE[M][N]表示迷宫(如图,),为判定过程中是否越界,在其外围加一圈,作为路障,mrk[M][N]作为标志数组,move[8][2]是行列增量数组(见图,-,);建堆栈(约定(i,j)表示i行j列,direction表示方向,从入口开始探索路径:沿,-7八个方向依次试探,若某方向可通(为,),则该点连同方向入堆栈,从该点继续试探;若八个方向都不通,则取出堆栈顶点,从其标记的方向开始试探其余方向;直至找到出口(有通路)或堆栈为空(没有通路)。目录一、需求分析.........................41、程序的功能..........................................................................42、输入输出的要求................................................................4二、概要设计.........................5三、详细设计.........................62、系统类之间的关系............................................................63、系统流程图..........................................................................7四、调试分析以及设计体会..............91、不同功能的实现................................................................92、调试分析............................................................................143、心得体会............................................................................15五、使用说明........................16六、源程序清单(带注释).............18一、需求分析1、程序的功能该系统主要是随机生成一个迷宫,并且由系统自动判断从该迷宫的从第一行、第一列进入到最后一行、最后一列出是否存在通路,并输出存在的通路。2、输入输出的要求本系统无输入要求,迷宫由系统自动生成。本系统要求输出自动生成的迷宫、以及找到的通路。二、概要设计(系统功能模块)(一)、概要设计1(数据结构的定义为实现输出迷宫路径需用到栈,下面定义栈的抽象数据类型:栈(stck)是限定仅在表尾进行插入或删除操作的线性表。因此,对栈来说,表尾端有特殊含义,称为栈顶(top),相应的,表头端称为栈底(bottom)。不含元素的空表称为空栈。假设栈S=(1,2,…,n),则称1为栈底元素,n为栈顶元素。栈的修改是按后进先出的原则进行的。因此,栈又称为后进先出(List