迷宫问题

1长沙学院课程设计说明书题目迷宫问题学院计算机工程与应用数学学院专业(班级)软件工程（16软件02班）姓名潘旭斌学号B20160304203指导教师刘欣、黄彩霞起止日期2017年12月11日~2017年12月22日2课程设计任务书各阶段具体要求：（1）需求分析阶段定义目标系统的问题描述定义目标系统的功能需求定义目标系统的测试需求（2）设计阶段定义目标系统的输入、输出项定义目标系统的算法流程（3）编码阶段要求遵守常见的编码规范，包括变量命名规则要求给出一定的注释（4）测试阶段要求定义测试用例要求补充测试用例内容。课程设计工作量：（1）软件设计：完成问题陈述中所提到的所有需求功能。（2）课程设计说明书：要求撰写不少于3000个文字的文档，详细说明各阶段具体要求。工作计划：安排两周时间进行课程设计，软件开发步骤如下，第一周完成1～4项目，第二周完成5～6项目，课程设计说明书同步进行；（1）选定题目（2）需求分析3（3）结构设计（4）编码实现（5）测试（6）撰写课程设计说明书并答辩注意事项：提交文档长沙学院课程设计说明书（含课程设计任务书，每学生1份）长沙学院课程设计鉴定表（纸质打印，每学生1份）目录一、引言.......................................................................................................................................................................11.1编写目的............................................................................................................................................................11.2参考资料............................................................................................................................................................1二、需求规约...............................................................................................................................................................12.1问题描述............................................................................................................................................................12.2需求分析............................................................................................................................................................1三、程序设计...............................................................................................................................................................23.1概要设计............................................................................................................................................................23.2详细设计............................................................................................................................................................23.3数据结构设计....................................................................................................................................................33.4关键算法1.........................................................................................................................................................5四、运行测试...............................................................................................................................................................64.1运行环境搭建....................................................................................................................................................64.2测试数据说明....................................................................................................................................................74.3程序运行结果....................................................................................................................................................7五、总结.......................................................................................................................................................................9附录.............................................................................................................................................................................101一、引言1.1编写目的本文档是解决“迷宫问题”程序的组成部分，编写此文档的目的是：确定本程序的程序结构、数据的数据结构，以及相关算法，用来作为后期程序改进的参照。本文档的读者对象是：需求人员、程序设计员，测试人员。1.2参考资料二、需求规约2.1问题描述以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宫问题要求求出从入口（1，1）到出口（m,n）的一条通路，或得出没有通路的结论。迷宫的长度自定义。通过随机数组产生一个迷宫，然后打印其通路的路径。需要用到随机数组，一个链式栈的存储结构。2.2需求分析首先实现一个以链栈作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，资料名称作者文件编号、版本《数据结构与算法（C语言版）》严蔚敏2009年9月第4版《数据结构》刘畅、姚学峰2016年8月第一版《程序设计基础实例化翻转教程》刘华富、魏歌2016年8月第一版2求得的通路以三元组（i（y坐标），j（x坐标），d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，（0表示右，1表示下，2表示左，3表示上）。实现一条路径到达终点或者一条死路。首先，设计好一个链式栈的存储结构，然后元素(记录它的位置)入栈。然后找找路径。三、程序设计3.1概要设计迷宫问题存储结构算法实现链式栈存储结构实现随机数组产生迷宫和其他算法3.2详细设计3迷宫问题存储结构算法实现链式栈int_stack*int_stack_init()（建立栈）int_stack_free（释放栈）int_stack_count（计算存的个数）int_stack_isempty（判断栈是否为空）int_stack_clear（清空栈）int_stack_push（入栈）int_stack_pop（出栈）int_stack_top（取栈顶）int_stack_class_route（设置迷宫路径）int_stack_class_print（打印迷宫）int_stack_class_init（建立迷宫）1、建立迷宫是先定义一个数组，然后产生随机数对二求余，在数组外面包裹一层“墙”。2、打印迷宫很简单，用二个`for打印即可。3、设置路径就是将走过的地方进栈，然后进行标记。3.3数据结构设计存储结构：4…….214351、表示一个一级指针，structint_stack*。2、表示一个结构体，structint_stack{Structint_stack_node*top;Intcount;Intsize;//三个成员。}3、structint_stack_node的成员。struct_int_stack_element{Intx;//坐标x方向Inty;//坐标y方向Intd;//下一步走的方向用0、1、2、3分别表示右、下、左、上}4、结构体structint_stack_node{5Structint_stack_elemente;Structint_stack_node*next;}5、指针structint_stack_node*next;3.4关键算法1关键算法：定义一系列变量第一个while:判断四周是否有路可走d=-1,find=0第二个while:find==0&&d3d++Case0:right，find=1Case1:down,find=1Case2:left,find=1Case3:up,find=1t=int_stack_top(s);x=t.x;y=t.y;重新置点，下一个开走的点第二个while第一个`while第二个while结束第一个while结束6（1）、设置二个while循环，第一个while循环的条件是当前位置上下左右有路可走。（2）、第二个while循环的条件是标识find==0且switch语句条件d3。当前位置若有路可走就将find==1，重新进入第二个while循环，此时d的值也重新变为-1，当前位置入栈后就走到下一个位置。（3）、当前位置置为9，记录路径，而且走到下一个位置就不能