数据结构课程设计报告迷宫算法.doc

课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：迷宫算法 院（系）：计算机学院 专 业：计算机科学与技术 班 级学 号：2010040101107  目 录 1 课程设计介绍 1 1.1 课程设计内容 1 1.2 课程设计要求 1 2 课程设计原理 2 2.1 课设题目粗略分析 2 2.2 原理图介绍 3 2.2.1 功能模块图 3 2.2.2 流程图分析 3 3 数据结构分析 9 3.1 存储结构 9 3.2 算法描述 9 4 调试与分析 11 4.1 调试过程 11 4.2 程序执行过程 11 参考文献 13 附 录（关键部分程序清单） 14  1 课程设计介绍 1.1 课程设计内容 编写算法能够生成迷宫，并且求解迷宫路径（求解出任意一条到出口的路径即可）： 迷宫用上下左右四种走法； 迷宫的大小和复杂程度可以由用户定义； 入口出口也由用户自己选择。 1.2 课程设计要求 不必演示求解过程，只需要输出迷宫求解的路径； 参考相应资料完成课设。 2 课程设计原理 2.1 课设题目粗略分析 根据课设题目要求，拟将整体程序分为四大模块。以下是四个模块的大体分析： 1 建立迷宫：要建立迷宫首先就要建立存储结构，这里我用栈的方式建立的。根据用户输入的迷宫的大小（我设置的最大值为25可以根据要求调解）； 2 设置迷宫：这里将0设置围墙，1是可以通过的路径，-1是不可以通过路径，外墙是以设计好的，内墙需要用户来设置，障碍的难度可由用户自行定义； 3 寻找路径：寻找路径我设置了四个方向{0,1},{1,0},{0,-1},{-1,0}移动方向,依次为东南西北，首先向东走，若不成功则转换方向，成功则继续前进，将走过的路径进行标记，然后存入栈中； 4 输出结果：输出的结果分为两种，一种是用户建立的迷宫主要是让用户检查是否符合要求，第二种输出的是寻找完后的路径，路径用1 2 3 4···来表示。 2.2 原理图介绍 2.2.1 功能模块图 图2.1 功能模块图 如图2.1所示 2.2.2 流程图分析 建立迷宫 图2.2建立迷宫函数流程图 2. 设置迷宫 图2.3 设置迷宫函数流程图 3. 寻找路径 图2.4 寻找路径函数流程图 4.输出结果 图2.5 输出结果函数流程图 3 数据结构分析 3.1 存储结构 定义一个整型数组PosType用来存储行列的值。 typedef struct // 栈的元素类型 { int ord; // 通道块在路径上的＂序号＂ PosType seat; // 通道块在迷宫中的＂坐标位置＂ int di; // 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) }SElemType; 栈的存储结构： #define STACK_INIT_SIZE 10 // 存储空间初始分配量 #define STACKINCREMENT 2 // 存储空间分配增量 // 栈的顺序存储表示 typedef struct SqStack { SElemType *base; // 在栈构造之前和销毁之后，base的值为NULL SElemType *top; // 栈顶指针 int stacksize; // 当前已分配的存储空间，以元素为单位 }SqStack; // 顺序栈 3.2 算法描述 1.栈的基本操作的算法，简单算法说明如下： Status InitStack(SqStack *S) {// 构造一个空栈S，为栈底分配一个指定大小的存储空间 (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if( !(*S).base ) exit(0); (*S).top = (*S).base; // 栈底与栈顶相同表示一个空栈 (*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 = (SE