《迷宫问题的求解数据结构课程设计》由会员分享,可在线阅读,更多相关《迷宫问题的求解数据结构课程设计(33页珍藏版)》请在金锄头文库上搜索。
1、数据结构课程设计设计说明书 迷宫问题求解学生姓名马东学号1021024068班级信管103成绩指导教师李婧数学与计算机科学学院2012年3月2日数据结构课程设计评阅书题 目迷宫问题求解学生姓名马东学号1021024068指导教师评语及成绩成绩: 教师签名: 年 月 日答辩教师评语及成绩成绩: 教师签名: 年 月 日教研室意见总成绩: 室主任签名: 年 月 日注:指导教师成绩60%,答辩成绩40%,总成绩合成后按五级制记入。课程设计任务书20112012学年第二学期专业: 信息管理与信息系统 学号: 1021024068 姓名: 马东 课程设计名称: 数据结构课程设计 设 计 题 目: 迷宫问题
2、求解 完 成 期 限:自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计依据、要求及主要内容(可另加附页):设计要求:设计内容:输入一个任意大小的迷宫数据,设置入口、出口及障碍,借助栈结构求解走出迷宫的路径并输出。逻辑设计:对问题描述中涉及的操作对象定义相应的数据类型,并按照以数据结构为中心的原则划分模块,定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明),各个主要模块的算法,并画出模块之间的调用关系图;详细设计:定义相应的存储结构并写出各函数的伪码算法。在这个过程中,要综合考虑系统功能,使得
3、系统结构清晰、合理、简单和易于调试,抽象数据类型的实现尽可能做到数据封装,基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精,写出数据存储结构的类型定义,写出函数形式的算法框架;程序编码:把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言,使程序中逻辑概念清楚;程序调试与测试:采用自底向上,分模块进行,即先调试低层函数。能够熟练掌握调试工具的各种功能,设计测试数据确定疑点,通过修改程序来证实它或绕过它。调试正确后,认真整理源程序及其注释,形成格式和风格良好的源程序清单和结果;结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及
4、其输出结果。算法的时间、空间复杂性分析;编写课程设计报告;以上要求中前三个阶段的任务完成后,先将设计说明数的草稿交指导老师面审,审查合格后方可进入后续阶段的工作。设计工作结束后,经指导老师验收合格后将设计说明书打印装订,并进行答辩。指导教师(签字): 教研室主任(签字): 批准日期: 年 月 日摘 要由计算机解迷宫时,通常用的是穷举求解的方法,即从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路反回,换一个方向继续探索,直至所有可行的通路都探索到为止。为了保证在任何位置上都能沿原路返回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。显然要用到栈。关键词:迷宫;穷举;
5、栈; 目 录1 课题描述12 问题分析和任务定义23 数据结构分析 3存储结构3算法描述34 流程图 65 程序编码106 程序测试与运行过程1919197 结果分析25 总结26 参考文献271 课题描述 本课程设计是解决迷宫求解的问题,从入口出发,顺某一方向向前探索,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续探索,直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此,在求迷宫通路的算法中要应用“栈”的思想假设“当前位置”指的是“在搜索过程中的某一时刻所在图中某个方块位置”,则求迷宫中一条路径的算法的
6、基本思想是:若当前位置“可通”,则纳入“当前路径”,并继续朝“下一位置”探索,即切换“下一位置”为“当前位置”,如此重复直至到达出口;若当前位置“不可通”,则应顺着“来向”退回到“前一通道块”,然后朝着除“来向”之外的其他方向继续探索;若该通道块的四周4个方块均“不可通”,则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置四周4个方向(东、南、西、北)上相邻的方块。假设以栈S记录“当前路径”,则栈顶中存放的是“当前路径上最后一个通道块”。由此,“纳入路径”的操作即为“当前位置入栈”;“从当前路径上删除前一通道块”的操作即为“出栈”。2 问题分析和任务定义根据课设题目要求,拟将整体
7、程序分为四大模块。以下是四个模块的大体分析: 1 建立迷宫:要建立迷宫首先就要建立存储结构,这里我用数组的方式建立的。根据用户输入的迷宫的大小(我设置的最大值为25可以根据要求调解); 2 设置迷宫:这里将0设置围墙,1是可以通过的路径,-1是不可以通过路径,外墙是以设计好的,内墙需要用户来设置,障碍的难度可自行定义; 3 寻找路径:寻找路径我设置了四个方向0,1,1,0,0,-1,-1,0移动方向,依次为东南西北,首先向东走,若不成功则转换方向,成功则继续前进,将走过的路径进行标记,然后存入栈中; 4 输出结果:输出的结果分为两种,一种是用户建立的迷宫主要是让用户检查是否符合要求,第二种输出
8、的是寻找完后的路径,路径用1 2 3 4来表示。3 数据结构分析存储结构定义一个整型数组PosType用来存储行列的值。typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03表示东北) SElemType; 栈的存储结构:#define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct SqStackSElemTy
9、pe *base;/ 在栈构造之前和销毁之后,base的值为NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间,以元素为单位 SqStack;/ 顺序栈 算法描述 1.栈的基本操作的算法,简单算法说明如下:Status InitStack(SqStack *S)/构造一个空栈S,为栈底分配一个指定大小的存储空间(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base;/ 栈底
10、与栈顶相同表示一个空栈(*S).stacksize = STACK_INIT_SIZE;return 1;Status StackEmpty(SqStack S) / 若栈S为空栈(栈顶与栈底相同的),则返回1,否则返回0。if(S.top = S.base) return 1;else return 0;Status Push(SqStack *S, SElemType e)/插入元素e为新的栈顶元素。if(*S).top - (*S).base = (*S).stacksize) / 栈满,追加存储空间 (*S).base = (SElemType *)realloc(*S).base ,
11、 (*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base ) exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;return 1;Status Pop(SqStack *S,SElemType *e)/若栈不空,则删除S的栈顶元素,用e返回其值,并返回1;否则返回0。if(*S).top = (*S).base) return 0;*e = *-(*S).top;return 1;1. 查