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

1、数据结构课程设计报告-迷宫算法 沈阳航空航天高校 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：迷宫算法 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导老师： 目 录 1 课程设计介绍 . 1 1.1 课程设计内容 . 1 1.2 课程设计要求 . 1 2 课程设计原理 . 2 2.1 课设题目粗略分析 . 2 2.2 原理图介绍 . 3 2.2.1 功能模块图 . 3 2.2.2 流程图分析 . 4 3 数据结构分析 . 8 3.1 存储结构 . 8 3.2 算法描述 . 8 4 调试与分析 . 11 4.1 调试过程 . 11 4

2、.2 程序执行过程 . 11 1 课程设计介绍 1.1 课程设计内容 编写算法能够生成迷宫，并且求解迷宫路径（求解出任意一条到出口的路径即可）： 1. 迷宫用上下左右四种走法； 2. 迷宫的大小和简单程度可以由用户定义； 3. 入口出口也由用户自己选择。 1.2 课程设计要求 1. 不必演示求解过程，只需要输出迷宫求解的路径；2. 参考相应资料完成课设。 2 课程设计原理 2.1 课设题目粗略分析 依据课设题目要求，拟将整体程序分为四大模块。以下是四个模块的大体分析： 1 建立迷宫：要建立迷宫首先就要建立存储结构，这里我用栈的方式建立的。依据用户输入的迷宫的大小（我设置的最大值为25可以依据要

3、求调解）； 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 流程图分析 1. 建立迷

4、宫 图2.2建立迷宫函数流程图 2. 设置迷宫 图2.3 设置迷宫函数流程图 3. 查找路径 图2.4 查找路径函数流程图 4.输出结果 图2.5 输出结果函数流程图 3 数据结构分析 3.1 存储结构 定义一个整型数组PosType用来存储行列的值。 typedef struct / 栈的元素类型 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从今通道块走向下一通道块的方向(03表示东北) SElemType; 栈的存储结构： #define STACK_INIT_SIZE 10 / 存储空间初始安排量 #defin

5、e STACKINCREMENT 2 / 存储空间安排增量 / 栈的挨次存储表示 typedef struct SqStack SElemType *base; / 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已安排的存储空间，以元素为单位 SqStack; / 挨次栈 3.2 算法描述 1.栈的基本操作的算法，简洁算法说明如下： Status InitStack(SqStack *S) / 构造一个空栈S，为栈底安排一个指定大小的存储空间 Status StackEmpty(SqStack S) (*S)

6、.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if( !(*S).base ) exit(0); (*S).top = (*S).base; / 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE; return 1; / 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。 Status Push(SqStack *S, SElemType e) / 插入元素e为新的栈顶元素。 if(*S).top - (*S).base = (*S).stacksize) / 栈满

7、，追加存储空间 = (SElemType *)realloc(*S).base , (*S).stacksize + if(S.top = S.base) return 1; else return 0; (*S).base STACKINCREMENT) * sizeof(SElemType); Status Pop(SqStack *S,SElemType *e) / 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。 2. 查找路径的算法，简洁算法说明如下： Status MazePath(PosType start,PosType end) / 若迷宫maze中存在从入

8、口start到出口end的通道，则求得一条 if(*S).top = (*S).base) return 0; *e = *-(*S).top; return 1; *(*S).top)+=e; return 1; if( !(*S).base ) exit(0); (*S).top = (*S).base+(*S).stacksize; (*S).stacksize += STACKINCREMENT; / 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 InitStack(S); curpos=start; curstep=1; do if(Pass(curpos)/ 当前位置可以通过，

9、即是未曾走到过的通道块 else/ 当前位置不能通过 if(!StackEmpty(S) Pop(S,e); / 退栈到前一位置 curstep-; / 前一位置处于最终一个方向(北) FootPrint(curpos); / 留下痕迹 e =( curstep, curpos,1); Push(S,e); / 入栈当前位置及状态 if(curpos.x=end.xcurpos.y=end.y) / 到达终点(出口) return 1; curpos=NextPos(curpos,e.di); while(e.di=3!StackEmpty(S) MarkPrint(e.seat); Pop(

10、S,e); /留下不能通过的标记(-1) , 退回一步 if(e.di3) / 没到最终一个方向(北) e.di+; Push(S,e);/ 换下一个方向探究 curpos=NextPos(e.seat,e.di); / 设定当前位置是该新方向 上的相邻块 while(!StackEmpty(S); return 0; 4 调试与分析 4.1 调试过程 在调试程序是主要遇到一下几类问题： 1. 选择存储结构的问题：刚接到课设题目的时候，我就在想用什么来实现迷宫的存储。用线性表还是数组，最终综合考虑决定用栈和数组结合的方式来实现，用数组来建立迷宫和输出迷宫，用栈来查找路径并将生成的路径压入到栈中

11、，由于栈有先入后出的优点，所以比较简单实现。 2. 如何建立迷宫和怎么设置迷宫的问题：首先迷宫要有肯定的范围怎么才能让迷宫有序的进行，于是我将迷宫的外围和障碍设置为0，全部的可走路径设置为1，这样迷宫就清楚可见。 3. 如何去查找路径问题 ：这是整个程序的核心。通过查找书籍得到了一个算法：若当前位置“可通”，则纳入当前路径，并连续朝下一位置搜索，即切换下一位置为当前位置，如此重复到达出口；若不行通，就退回到前一通道，然后连续查找其他方向；若均不行通，则删除此路径。 4. 界面问题：这里就是运用了switch(n)语句来实现的，这样增加了程序的有用性。 4.2程序执行过程 系统用法说明： 1消失

12、界面后选择1，进行迷宫大小的设计（这里设计3*3大小的）：如图4.1所示 图4.1 2. 然后选择2，开头设计迷宫的内部：如图4.2所示 图4.2 3. 选择3，观看设计的是否满足你的要求：如图4.3所示 图4.3 4. 选择4，输入迷宫的起点和终点：如图4.4所示 图4.4 5. 选择5，查看结果（路径由1.2.3.4.5表示出来）：如图4.5所示 图4.5 6选择0，退出程序。 附 录（关键部分程序清单） 程序代码 #includestdio.h #includestdlib.h #includestring.h #includemalloc.h / 迷宫坐标位置类型 typedef st

13、ruct #define MAXLENGTH 25 / 设迷宫的最大行列为25 typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宫数组行列 typedef struct / 栈的元素类型 / 全局变量 MazeType m; / 迷宫数组 int curstep=1; / 当前痕迹,初值为1 #define STACK_INIT_SIZE 10 / 栈的挨次存储表示 typedef struct SqStack SElemType *base; SElemType *top; int stacksize; / 在栈构造之前和销毁之后，base的值为NULL

14、 / 栈顶指针 / 当前已安排的存储空间，以元素为单位 / 存储空间初始安排量 #define STACKINCREMENT 2 / 存储空间安排增量 int ord; / 通道块在路径上的序号 PosType seat; / 通道块在迷宫中的坐标位置 int di; / 从今通道块走向下一通道块的方向(03表示东北) int x; int y; / 行值 / 列值 PosType; SElemType; SqStack; / 挨次栈 / / 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。 int StackEmpty(SqStack S) / / 若栈不空，则删除S的栈顶元素，用e

15、返回其值，并返回1；否则返回0。 int Pop(SqStack *S,SElemType *e) if(*S).top - (*S).base = (*S).stacksize) / 栈满，追加存储空间 *(*S).top)+=e; return 1; (*S).base = (SElemType *)realloc(*S).base , (*S).top = (*S).base+(*S).stacksize; (*S).stacksize += STACKINCREMENT; (*S).stacksize + STACKINCREMENT) * sizeof(SElemType); exi

16、t(0); if( !(*S).base ) 插入元素e为新的栈顶元素。 int Push(SqStack *S, SElemType e) if(S.top = S.base) else return 0; return 1; / 为栈底安排一个指定大小的存储空间 (*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if( !(*S).base ) (*S).top = (*S).base; / 栈底与栈顶相同表示一个空栈 (*S).stacksize = STACK_INIT_SIZE; return 1;

17、exit(0); 构造一个空栈S int InitStack(SqStack *S) / 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为痕迹 / 当迷宫m的b点的序号为1(可通过路径)，return 1; 否则，return 0。 int Pass(PosType b) void FootPrint(PosType a) / 使迷宫m的a点的序号变为痕迹(curstep)，表示经过 / 依据当前位置及移动方向，返回下一位置 PosType NextPos(PosType c,int di) / 使迷宫m的b点的序号变为-1(不能通过的路径) void MarkPrint(Po

18、sType b) / 若迷宫maze中存在从入口start到出口end的通道，则求得一条 / 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end) SqStack S; PosType curpos; SElemType e; mb.xb.y=-1; PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量 / 移动方向,依次为东南西北 c.x+=direcdi.x; c.y+=direcdi.y; return c; ma.xa.y=curstep; if(mb.xb.y=1) else

19、 return 0; return 1; if(*S).top = (*S).base) return 0; *e = *-(*S).top; / 这个等式的+ * 优先级相同，但是它们的运算方式，是自右向左 return 1; / 输出迷宫的结构 void Print(int x,int y) InitStack(S); curpos=start; do if(Pass(curpos) / 当前位置可以通过，即是未曾走到过的通道块 else / 当前位置不能通过 if(!StackEmpty(S) Pop(S,e); / 退栈到前一位置 curstep-; while(e.di=3!Stac

20、kEmpty(S) / 前一位置处于最终一个方向(北) if(e.di3) / 没到最终一个方向(北) e.di+; / 换下一个方向探究 Push(S,e); curstep+;/ 设定当前位置是该新方向上的相邻块 curpos=NextPos(e.seat,e.di); MarkPrint(e.seat); / 留下不能通过的标记(-1) Pop(S,e); / 退回一步 curstep-; FootPrint(curpos); / 留下痕迹 e.ord=curstep; e.seat.x=curpos.x; e.seat.y=curpos.y; e.di=0; Push(S,e); /

21、入栈当前位置及状态 curstep+; / 痕迹加1 if(curpos.x=end.xcurpos.y=end.y) / 到达终点(出口) return 1; curpos=NextPos(curpos,e.di); while(!StackEmpty(S); return 0; void main() PosType begin,end; int i,j,x,y,x1,y1,n,k; do int i,j; for(i=0;ix;i+) for(j=0;jy;j+) printf(%3d,mij); printf(n); system(cls); /清屏函数 printf( welcome nnn); printf( 1请输入迷宫的行数,列数(包括外墙)n); printf( 2请输入迷宫内墙单元数n); printf( 3迷宫结构如下n); printf( 4输入迷宫的起点和终点n); printf( 5输出结果n); printf( 0退出n); printf(nn请选择 ); scanf(%d,n); switch(n) case 1: printf(请输入迷