《数据结构课程设计迷宫求解》由会员分享，可在线阅读，更多相关《数据结构课程设计迷宫求解（21页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计数据结构课程设计迷宫求解 院 系： 网络工程 班 级： 网络09 1班 姓 名： 合 作 者： 指导教师： 2010 年 12 月 20 日数据结构课程设计任务书一、题目： 迷宫求解二、设计要求（1）李斌（组长）、尚贺和张雪城组成设计小组。（2）小组成员分工协作完成。要求每个成员有自己相对独立的模块，同时要了解其他组员完成的内容。（3）查阅相关资料，自学具体课题中涉及到的新知识。（4）采用结构化、模块化程序设计方法设计，功能要完善，界面美观。（5）所设计的系统要至少应用一个课程中或者与其密切相关的算法。（6）按要求写出课程设计报告。其主要内容包括：封皮、课程设计任务书，指导教师
2、评语与成绩、目录、概述、软件总体设计、详细设计、软件的调试、总结、附录：带中文注释的程序清单、参考文献。报告一律用A4纸打印，中文字体为宋体，西文字体用Time New Roma，一律用小四号字，行距采用“固定值”18磅，首行缩进2字符。总体设计应配合软件总体模块结构图来说明软件应具有的功能。详细设计阐述本人设计模块部分的设计思想、应用到的理论和算法、程序流程等等，调试的叙述应配合出错场景的抓图来说明出现了哪些错误，如何解决的。（7）课程设计报告中的软件总体设计、详细设计、软件的调试等主体内容要以文字描述、图表等形式为主，可配以主要核心代码，在附录中附程序清单。三、课程设计工作量由于是设计小组
3、团结协作完成设计任务，一般每人的程序量在200行有效程序行左右，不得抄袭。四、课程设计工作计划2010年12月20日，指导教师讲课，学生根据题目准备资料；2010年12月21日，设计小组进行总体方案设计和任务分工；2010年12月22日2010年12月27日，每人完成自己承担的程序模块并通过独立编译；2010年12月28日2009年12月30日，将各模块集成为一个完整的系统，并录入足够的数据进行调试运行；2010年12月31日，验收、开始撰写报告；2011年01月4日前，提交课程设计报告。 指导教师签章： 教研室主任签章 数据结构课程设计指导教师评语与成绩指导教师评语：课程设计表现成绩： 课程
4、设计验收成绩： 课程设计报告成绩： 课程设计 总成绩： 指导教师签章 2011年 01 月 04 日目 录第1章 概述51.1 性能需求51.2 功能需求5第2章 概要设计62.1 功能模块设计62.2 算法分析与设计7第3章 详细设计83.1 迷宫求解功能模块设计83.2 文件的存取模块设计8第4章 调试分析与测试结果104.1 调试分析104.2 测试结果10第5章 总结13参考文献14附录15第1章 概述1.1 性能需求随着社会经济和人们物质生活的不断提高，人们对精神生活的需求也越来越高，在现今社会里，人们对诸如智商、情商等的重视无疑反映了对精神生活的态度。当然具体到我们每个人来说，想必
5、大多数人小时候都曾玩过魔方、迷宫吧。作为这种智力游戏，人们是百玩不厌的。正是鉴于这种需求，本设计应用计算机语言及其算法，将人的意志赋予机器实现，使人们不必再陷于枯燥的重复劳动，从而将更多的精力投入到对未知领域的探索上。1.2 功能需求本设计的关键在于将人的想法自能化，由所编软件自动的搜索可行路径。因此，软件必须拥有自动搜索并记录可行路径的功能，除此之外，软件还应设置人机交互接口，以便能够人为的建立迷宫图；软件要能保存以输入的迷宫图，并能调取外部现有的迷宫图；当然对于迷宫问题还有很多要考虑的地方，比如由用户自己来探索可行路径，但由于本设计侧重于迷宫求解的算法设计，并非以游戏的形式为初衷，定有不全
6、之处。第2章 概要设计2.1 功能模块设计本设计主要分为个模块：初始化栈模块、迷宫建立模块、迷宫求解模块、文件的保存与调取模块。1. 初始化栈模块，由InitStack(SqStack &S)、Push(SqStack &S,SElemType e)、Pop(SqStack &S,SElemType &e)、StackEmpty(SqStack S)函数构成，此模块是解决问题的关键算法，贯穿整个设计的始终。2. 迷宫建立模块，由initmaze(int mazeMN)构成，此模块用于用户自己设计并建立迷宫。3. 迷宫求解模块：由MazePath(PostType start,PostType
7、end,int mazeMN,int diradd42)构成，此模块是基于栈的特点与迷宫实际相结合来实现的。4. 文件的保存与调取模块：由File_Save(int maze50,int x,int y)、File_Get(int mazeMN)构成，此模块用来存储用户建立的迷宫，并方便其调取外部的现有迷宫。流程图如下：开 始初始化栈模块迷宫建立模块迷宫求解模块文件的保存与调取模块结 束2.2 算法分析与设计栈：假设栈S=(a1,a2,an),则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,an的次序进栈，退栈的第一个元素为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，
8、栈又称为后进先出的线性表。由于计算机解谜宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。首先，迷宫图用方块表示，每个方块或为通道，或为墙。所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。假设“当前位置”指的是“在搜索过程中某一时刻所在图中某个方块位置”，则求迷宫中一条路径的算法的基本思想是：若当前位置“可通”，则纳
9、入“当前路径”，并继续朝“下一位置”探索，即切换“下一位置”为“当前位置”，如此重复直至到达出口；若当前位置“不可通”，则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周4个方块均“不可通”，则应从“当前路径”上删除该通道块。所谓“下一位置”指的是“当前位置”四周4个方向（东、南、西、北）上相邻的方块。假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径”上最后一个通道块。由此，“纳入路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。其中需要说明的是，所谓当前位置可通，指的是未曾走到过的通道块，即要求该方块位置不
10、仅是通道块，而且既不在当前路径上（否则所求路径就不是简单路径），也不是曾经纳入路径的通道块（否则只能在死胡同内转圈）。此软件的主要实现均是按照上述分析设计而成。第3章 详细设计3.1 迷宫求解功能模块设计此模块主要由函数MazePath(PostType start,PostType end,int mazeMN,int diradd42)来实现，当然此功能实现主要基于对栈的操作。模块用：typedef structint x;int y;PostType;typedef structint x,y;int d;/*1表示右，2表示下，3表示左，4表示上*/SElemType;来表示坐标类型及
11、迷宫中每一方块的属性（包括坐标、下一步的方向），用1和0分别表示墙和通路并用二维数组存储，从而将实际问题转化成数学模型，方便程序的设计，以实现其自能化。具体的程序实现可参见附录。3.2 文件的存取模块设计此模块由File_Save(int maze50,int x,int y)、File_Get(int mazeMN)来实现，此功能主要是对文件的操作。其中FILE *fp;是对文件指针的定义，if(fp = fopen(str,w)=NULL)return;和if(fp=fopen(str,rb)=NULL)return;分别是以写和读的方式打开文件，以便对文件进行相应的操作，最后以fclos
12、e(fp);来关闭文件。以向文件中写数据为例的部分程序实现如下：FILE *fp;int i,j;char str=;coutstr;if(fp = fopen(str,w)=NULL)return;fprintf(fp,%d ,x);fprintf(fp,%d ,y);fprintf(fp,n);for(i = 0;i x;i +)for(j = 0;j y;j +)fprintf(fp,%d ,mazeij);fprintf(fp,n);fclose(fp);具体功能的程序实现可参见附录。(文件存储流程图如下)开 始定义文件指针fp输入字符串str定义i ,j以“w”打开文件成功？返回空Y向文件中输出数据x ,yi = 0Yix？i = 0jy？NYj+向文件输出mazeiji+关闭文件结 束第4章 调试分析与测试结果4.1 调试分析1. 迷宫求解模块：此模块的调试主要在于迷宫中每个方块出栈入栈的时机及对栈本身的操作。2. 文件的存取模块：此模块的调试主要在于对文件输入、输出操作及文件打开不成功时的应对。4.2 测试结果1迷宫求解模块：根据调试分析进行测试预期结果：程序能够自动搜索下一步的方向，并能记录已经走过的方向。实际测试结果：程序只能沿着固定的方向搜索，而不能退回到该方块继续从其他方向开始搜索。程序部分代码如下：while(!StackE
