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

《数据结构课程设计报告-迷宫算法》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-迷宫算法（24页珍藏版）》请在金锄头文库上搜索。

1、沈阳航空航天大学课课 程程 设设 计计 报报 告告课程设计名称：数据结构课程设计数据结构课程设计课程设计题目：迷宫算法 院（系）：计算机学院专 业：计算机科学与技术班 级：学 号：姓 名： 指导教师： 沈阳航空航天大学课程设计报告 I 目目 录录1 1 课程设计介绍课程设计介绍.11.1 课程设计内容1 1.2 课程设计要求12 2 课程设计原理课程设计原理.22.1 课设题目粗略分析2 2.2 原理图介绍3 2.2.1 功能模块图3 2.2.2 流程图分析33 数据结构分析数据结构分析.93.1 存储结构9 3.2 算法描述94 4 调试与分析调试与分析.114.1 调试过程11 4.2 程

2、序执行过程11参考文献参考文献.13附附 录（关键部分程序清单）录（关键部分程序清单）.14沈阳航空航天大学课程设计报告 1 1 1 课程设计介绍课程设计介绍1.11.1 课程设计内容课程设计内容编写算法能够生成迷宫，并且求解迷宫路径（求解出任意一条到出口的路径即可）：1. 迷宫用上下左右四种走法；2. 迷宫的大小和复杂程度可以由用户定义；3. 入口出口也由用户自己选择。1.21.2 课程设计要求课程设计要求1.不必演示求解过程，只需要输出迷宫求解的路径；2.参考相应资料完成课设。沈阳航空航天大学课程设计报告 2 2 2 课程设计原理课程设计原理2.12.1 课设题目粗略分析课设题目粗略分析根

3、据课设题目要求，拟将整体程序分为四大模块。以下是四个模块的大体分析：1 建立迷宫：要建立迷宫首先就要建立存储结构，这里我用栈的方式建立的。根据用户输入的迷宫的大小（我设置的最大值为 25 可以根据要求调解） ；2 设置迷宫：这里将 0 设置围墙，1 是可以通过的路径，-1 是不可以通过路径，外墙是以设计好的，内墙需要用户来设置，障碍的难度可由用户自行定义；3 寻找路径：寻找路径我设置了四个方向0,1,1,0,0,-1,-1,0移动方向,依次为东南西北，首先向东走，若不成功则转换方向，成功则继续前进，将走过的路径进行标记，然后存入栈中；4 输出结果：输出的结果分为两种，一种是用户建立的迷宫主要是

4、让用户检查是否符合要求，第二种输出的是寻找完后的路径，路径用 1 2 3 4来表示。沈阳航空航天大学课程设计报告 3 2.22.2 原理图介绍原理图介绍2.2.12.2.1 功能模块图功能模块图迷宫求解建 立 迷 宫设 置 迷 宫寻 找 路 径输 出 结 果图 2.1 功能模块图如图 2.1 所示 沈阳航空航天大学课程设计报告 4 2.2.2 流程图分析流程图分析1.建立迷宫开始构建一个空栈InitStack(SqStack *S)判断栈是否为空N建立迷宫,将所有的周边值设为 mx1y1=0;结束输入迷宫的行数x和列数 yY图 2.2 建立迷宫函数流程图沈阳航空航天大学课程设计报告 5 2.

5、设置迷宫图 2.3 设置迷宫函数流程图设置迷宫内部，将内墙设为mx1y1=0，开始结束输入迷宫的内墙数j,和具体位置x1 y1输入迷宫的指点和终点 函数输出已建 立好的迷宫供用户检查沈阳航空航天大学课程设计报告 6 3. 寻找路径可以通过FootPrint(curpos); / 留下足迹，入栈Push(足迹 加一curstep+; 继续进行判断输入迷宫的起点和终点的坐标输出此通路输入i,j结束开始输出迷宫图 2.5 输出结果函数流程图沈阳航空航天大学课程设计报告 8 3 数据结构分析数据结构分析3.13.1 存储结构存储结构定义一个整型数组 PosType 用来存储行列的值。 typedef

6、struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03 表示东北) SElemType; 栈的存储结构：#define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct SqStack SElemType *base;/ 在栈构造之前和销毁之后，base 的值为 NULL SElemType *top;/ 栈顶指针 int sta

7、cksize;/ 当前已分配的存储空间，以元素为单位 SqStack;/ 顺序栈3.23.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

8、;Status StackEmpty(SqStack S)沈阳航空航天大学课程设计报告 9 / 若栈 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 , (*S).stacksize + STACKINCREME

9、NT) * 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;2.查找路径的算法，简单算法说明如下：Status

10、MazePath(PosType start,PosType end) / 若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回 1；否则返回 0 沈阳航空航天大学课程设计报告 10 InitStack( curpos=start; curstep=1;doif(Pass(curpos)/ 当前位置可以通过，即是未曾走到过的通道块 FootPrint(curpos); / 留下足迹 e =( curstep, curpos,1);Push( / 入栈当前位置及状态 if(curpos.x=end.xcurpos=NextPos(

11、curpos,e.di);else/ 当前位置不能通过 if(!StackEmpty(S)Pop( / 退栈到前一位置 curstep-; / 前一位置处于最后一个方向(北) while(e.di=3 Pop( /留下不能通过的标记(-1) , 退回一步if(e.di#include#include#include/ 迷宫坐标位置类型typedef struct int x;/ 行值 int y;/ 列值 PosType;#define MAXLENGTH 25 / 设迷宫的最大行列为 25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列 ty

12、pedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从此通道块走向下一通道块的方向(03 表示东北) SElemType;/ 全局变量 MazeType m; / 迷宫数组int curstep=1; / 当前足迹,初值为 1 #define STACK_INIT_SIZE 10/ 存储空间初始分配量 #define STACKINCREMENT 2/ 存储空间分配增量 / 栈的顺序存储表示 typedef struct SqStackSElemType *base;/ 在栈构造之

13、前和销毁之后，base 的值为 NULL SElemType *top;/ 栈顶指针 int stacksize;/ 当前已分配的存储空间，以元素为单位 SqStack; / 顺序栈沈阳航空航天大学课程设计报告 17 /构造一个空栈 Sint InitStack(SqStack *S)/ 为栈底分配一个指定大小的存储空间(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base;/ 栈底与栈顶相同表示一个空栈(*S).stacksiz

14、e = STACK_INIT_SIZE;return 1;/ 若栈 S 为空栈（栈顶与栈底相同的） ，则返回 1，否则返回 0。int StackEmpty(SqStack S)if(S.top = S.base)return 1;elsereturn 0;/插入元素 e 为新的栈顶元素。int Push(SqStack *S, SElemType e)if(*S).top - (*S).base = (*S).stacksize) / 栈满，追加存储空间(*S).base = (SElemType *)realloc(*S).base , (*S).stacksize + STACKINCREMENT) * sizeof(SElemType);if( !(*S).base )exit(0);(*S).top = (*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;*(*S).top)+=e;return 1;/若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 1；否则返回 0。int Pop(SqStack *S,SElemType *e)沈阳航空航天大学课程设计报告