迷宫求解(有流程图).doc

一 需求分析1 以二维数组MazeType表示迷宫，在其周围加一圈围墙；数组中#表示障碍，_表示通路。2 程序引导用户初始化迷宫，输入其中的障碍；3 迷宫的入口和出口可以由用户自己设定。4 若迷宫有通路，则在其走过的路径上以.表示可以通过；5本程序可以求解多条路径。既在迷宫求解过程中记下所有的走过的位置；例如：*_#*_#*_#*_#*_#*_#*_#*_*二 系统设计1 设定栈的抽象数据类型定义基本操作：int InitStack(SqStack &S)操作结果：构造一个空栈S；int StackEmpty(SqStack S)初始条件：栈S已存在。操作结果：若栈为空则返回TRUE，否则返回FALSE；GETTOP（S，&e）初始条件：栈S已经存在；操作结果：若栈不为空，则以e返回栈顶元素。int Push(SqStack &S,SElemType e)初始条件：栈已经存在。操作结果：在栈的顶部插入新的栈顶元素；int Pop(SqStack &S,SElemType &e)初始条件：栈已经存在；操作结果：删除栈顶元素，并以E返回其值。2 设定迷宫的抽象数据类型为：基本操作：1 void CreatMaze(int r,int l)初始条件：MazeType maze已经存在，其中从第一行到最后一行，每一行的第一个元素和最后一个元素都为*，从第一列的到最后一列，每一列的第一个和最后一个元素的值为*；操作结果：构成迷宫的int型数组，以#表示障碍，_表示通路。2 mazepath(posit start,posit end)初始条件：迷宫已经初始化；操作结果：若迷宫中存在一条通路，则在程序运行过程中走过的路径赋值为1；并在入口处赋值为-1。若迷宫中不存在通路则打印 NO PATH。3print()初始条件：迷宫存在通路；操作结果；以数字数组的形式输出迷宫。4 footprint(posit a)操作结果：使迷宫的M的A点的值变为足迹。5 nextpos(posit c,int di)操作结果：调整迷宫行进的方向，寻找出路。3 本程序包括三个模块1）主程序模块int main()PosType start,end;int r,l;coutrl;CreatMaze(r,l);coutstart.rowstart.line;coutend.rowend.line;coutendl;if(MazePath(start,end)cout迷宫的通路：endl（其中*表示外墙，#表示迷宫内障碍物,.为通路）endlendl;PrintMaze(r,l);else cout迷宫没有通路！endl;free(S.base);return 0;2）栈模块3）迷宫模块各模块的调用关系如下：4）求解迷宫的通路的伪码算法：设定当前位置的处值为入口位置；DO若当前的位置可通。则将当前的位置插入栈顶；若该位置为出口位置，则结束；否则切换当前位置的东邻的为新的当前位置；否则若栈不为空且栈的顶位置尚有其他的方向没有被探索，则设定新的当前位置为沿顺时针方向旋转找到栈顶的位置的下一个相邻块；若栈不空但栈顶的四周均不可通过，则删去栈顶位置；若栈不为空，则重新测试新的栈顶位置；只至找到一个可通过的块至栈空；1 坐标的位置的类型typedef structint line;int row;PosType;2 迷宫类型void CreatMaze(int r,int l)/定义迷宫的墙为*，通路为_，障碍为#int i,j;for(i=0;ir;i+)mazei0=*;/左面墙mazeil-1=*;/右面墙for(j=1;jl-1;j+)maze0j=*;/上面墙mazer-1j=*;/下面墙for(i=1;ir-1;i+)for(j=1;jl-1;j+)mazeij=_;coutnum;cout请依次输入障碍物的坐标：endl;int x,y;for(i=1;ixy;mazexy=#;coutendl创建的迷宫的如下：endlendl;PrintMaze(r,l);coutendl;3 栈类型typedef structint ord; /通道块在路径上的序号PosType seat; /通道块在迷宫中的坐标位置int di; /从此通道块走向下一通道块的方向 东1；南2；西3；北4SElemType;4 迷宫的路径的算法int MazePath(PosType start,PosType end)InitStack(S);curpos=start;/ 设定当前位置为入口位置curstep=1;/第一步doif(Pass(curpos)/当前位置可以通过（未曾走过）FootPrint(curpos);/留下足迹e.ord=curstep;e.seat=curpos;e.di=1;Push(S,e);/加入路径if(curpos.row=end.row&curpos.line=end.line)/到达终点return TRUE;curpos=NextPos(curpos,1);/下一位置是当前位置的东邻curstep+;/探索下一步/ifelse/当前位置不能通过if(!StackEmpty(S)Pop(S,e);while(e.di=4&!StackEmpty(S)MarkPrint(e.seat);/留下不能通过的标志Pop(S,e);/退回一步/curstep-;/whileif(e.di4)e.di+;/换下一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);/设定当前位置是该新方向上的相邻块/if/if/elsewhile(!StackEmpty(S);return FALSE;三程序流程图前行左转右转后转否否否是是是是否输入数据是否合法输入障碍坐标输入迷宫障碍个数初始化用户输入迷宫大小右面是否有障碍左面是否有障碍前面是否有障碍用户输入入口与出口创建并输入迷宫是结束输出迷宫通路否是否达到终点四 代码#define STACK_INIT_SIZE 1000#define STACK_MORE 10#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#include #include #include #include #include typedef structint line;int row;PosType;typedef structint ord; /通道块在路径上的序号PosType seat; /通道块在迷宫中的坐标位置int di; /从此通道块走向下一通道块的方向 东1；南2；西3；北4SElemType;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;typedef int MazeType100100;MazeType maze;SqStack S;PosType curpos;SElemType e;int curstep;int InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit (OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;int StackEmpty(SqStack S)if(S.base=S.top)return TRUE;else return FALSE;int Push(SqStack &S,SElemType e)if(!S.base)exit (OVERFLOW);*S.top+=e;return OK;int Pop(SqStack &S,SElemType &e)if(S.top=S.base)return ERROR;e=*-S.top;return OK;int Pass(PosType curpos)if(mazecurpos.rowcurpos.line=_)return OK;else return ERROR;void FootPrint(PosType curpos)mazecurpos.rowcurpos.line=.;PosType NextPos(PosType curpos,int di)if(di=1)curpos.row+;else if(di=2)curpos.line-;else if(di=3)curpos.row-;else if(di=4)curpos.line+;return curpos;void MarkPrint(PosType curpos)mazecurpos.rowcurpos.line=;void PrintMaze(int row,int line)for(int i=0;irow;i+)for(int j=0;jline;j+)cout(char)mazeij ;coutendlendl;void CreatMaze(int r,int l)/定义迷宫的墙为*，通路为_，障碍为#int i,j;for(i=0;ir;i+)mazei0=*;/左面墙mazeil-1=*;/右面墙for(j=1;jl-1;j+)maze0j=*;/上面墙mazer-1j=*;/下面墙for(i=1;ir-1;i+)for(j=1;jl-1;j+)mazeij=_;coutnum;cout请依次输入障碍物的坐标：endl;int x,y;for(i=1;ixy;mazexy=#;coutendl创建的迷宫的如下：endlendl;PrintMaze(r,l);coutendl;int MazePath(PosType start,PosType end)InitStack(S);curpos=start;/ 设定当前位置为入口位置curstep=1;/第一步doif(Pass(curpos)/当前位置可以通过（未曾走过）FootPrint(curpos);/留下足迹e.ord=curstep;e.seat=curpos;e.di=1;Push(S,e);/加入路径if(curpos.row=end.row&curpos.line=end.line)/到达终点return TRUE;curpos=NextPos(curpos,1);/下一位置是当前位置的东邻curstep+;/探索下一步/ifelse/当前位置不能通过if(!StackEmpty(S)Pop(S,e);while(e.di=4&!StackEmpty(S)MarkPrint(e.seat);/留下不能通过的标志Pop(S,e);/退回一步/curstep-;/whileif(e.di4)e.di+;/换下一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);/设定当前位置是该新方向上的相邻块/if/if/elsewhile(!StackEmpty(S);return FALSE;int main()PosType start,end;int r,l;coutrl;CreatMaze(r,l);coutstart.rowstart.line;coutend.rowend.line;coutendl;if(MazePath(start,end)cout迷宫的通路：endl（其中*表示外墙，#表示迷宫内障碍物,.为通路）endlendl;PrintMaze(r,l);else cout迷宫没有通路！endl;free(S.base);return 0;五总结数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数 据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。数据结构课程的主要目的是介绍一些常用的数据结构，阐明数据结构内在的逻辑 关系，讨论它们在计算机中的存储表示，并结合各种数据结构，讨论对它们实行的各种 运算的实现算法。 通过这次数据结构课程设计，让我学到了好多东西。在实际操作过程中犯了一些错 误却让我有了意外的收获，所学数据结构理论知识得到了巩固。通过实际操作，学会数据结构程序编程的基本步骤、基本方法，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。现在终于挨到了写收获与体会的时候了，的确令人兴奋，看看自己的劳动成果，好开心。 一个星期前的现在，当听到老师布置给我们的题目时，我们都蒙了，这么难的题目我们怎么会啊，但我们只能尽我们自己