迷宫求解数据结构课程设计.doc

数据结构课程设计题 目： 迷宫求解 班 级： 学 号： 作者姓名： 指导教师： 2012年12月11日目 录1需求分析.12概要设计.12.1数据结构.12.1.1逻辑结构.12.1.1存储结构.22.2.基本操作.3 2.2.1.迷宫中栈的基本操作.3 2.2.2.迷宫的抽象数据类型.32.2.3.本程序包含三个模块.43详细设计. .54调试与分析. .95用户手册96. 测试结果.107. 附录.128. 参考文献.129、心得体会1210、小组成员工作分配.13一、 需求分析(1) 以二维数组mazen+2m+2表示迷宫，其中：maze0j和mazen+1j(0=j=m+1)及mazei0和mazeim+1(0=i=j+1)为添加的一圈障碍。数组中以元素值为0的表示通路，1表示障碍，限定迷宫的大小，m，n=0数据关系：R1=|ai-1,aiD,i=2,n基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack（&S）初始条件：栈S 已存在。操作结果：销毁栈S。ClearStack(&S)初始条件：栈S 已存在。操作结果：将 S 清为空栈。StackLength(&S)初始条件：栈S 已存在。操作结果：返回栈 S 的长度。StackEmpty(&S)初始条件：栈S 已存在。操作结果：若 S 为空栈，则返回TRUE，否则返回FALSE。GetTop(S,&e)初始条件：栈S 已存在。操作结果：若栈 S 不空，则以e 返回栈顶元素。Push(&S,e)初始条件：栈S 已存在。操作结果：在栈 S 的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S 已存在。操作结果：删除 S 的栈顶元素，并以e 返回其值。StackTraverse(S,visit()初始条件：栈S 已存在。操作结果：从栈底到栈顶依次对 S 中的每个元素调用函数visit( )。ADT Stack2.1.2、存储结构1）顺序存储结构： 顺序栈：是利用一块地址连续的存储单元来存放栈中的元素，同时要利用一个指针top 来指示栈顶元素的位置。注：在本迷宫求解程序设计中用到的就是栈的顺序存储结构。/- 栈的顺序存储表示 -#define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize;SqStack; 2）链式存储结构 链式栈：链栈是指采用链式存储结构存储的栈。 链栈是一种特殊的单链表，即限定仅在表头进行插入和删除操作的单链表，因此链栈的结点结构与单链表的结点结构相同。2.2、基本操作2.2.1、迷宫中栈的基本操作：基本操作：InitStack(&S)操作结果：构造一个空栈S。StackEmpty(&S)初始条件：栈S 已存在。操作结果：若 S 为空栈，则返回TRUE，否则返回FALSE。GetTop(S,&e)初始条件：栈S 已存在。操作结果：若栈 S 不空，则以e 返回栈顶元素。Push(&S,e)初始条件：栈S 已存在。操作结果：在栈 S 的栈顶插入新的栈顶元素e。Pop(&S,&e)初始条件：栈S 已存在。操作结果：删除 S 的栈顶元素，并以e 返回其值。2.2.2、迷宫的抽象数据类型ADT MazeType数据对象 : D=ai,j|ai,j ,#、*，0=i=n+1, 0=j=m+1,m,n=20 数据关系 :R=ROW,LINEROW=|ai-1,j,ai,jD,i=1,m+1,j=0,n+1LINE=|ai-1,j,ai,jD,i=1,m+1,j=0,n+1 基本操作 :Status Pass(MazeType &maze,PosType curpos)初始条件: maze 存在迷宫, curpos 保存了当前位置的坐标操作结果: 如果可通,返回真,否则为假void FootPrint(MazeType &maze,PosType curpos)初始条件: maze 存在迷宫, curpos 保存了当前位置的坐标操作结果: 将当前坐标curpos处的maze值记为 足迹PosType NextPos(PosType CurPos,int di)初始条件: 各参数值已经定义操作结果: 求得以当前位置为栈顶的下一个方向的元素的坐标Status MazePath(SqStack &S, PosType start, PosType end) 初始条件: maze 存在迷宫地图操作结果: 为建立的迷宫找到一条路径ADT maze;2.2.3、本程序包含三个模块1）主函数模块：int main（） 初始化迷宫； 求解迷宫； 输出迷宫的解； return 0；2）栈实现模块实现栈的抽象殊绝类型3）迷宫实现模块实现迷宫的抽象数据类型各模块的调用关系如下：主函数模块迷宫模块栈模块4）求解迷宫中一条通路的伪码算法：设定当前位置的初值为入口位置；do 若当前位置可通， 则将当前位置插入栈顶； /纳入路径 若该位置是出口位置，则结束； /求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置；否则 若栈不空且栈位置尚有其他方向未被探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置； /后退一步，从路径中删去该通道块； 若栈不空，则重新测试新的栈顶位置； 直到找到一个可通的相邻块或出栈至栈空； while(栈不空)；栈空说明没有路径存在三、 详细设计1、 坐标位置类型typedef structint row;int line;PosType;2、 迷宫类型Status Pass(PosType CurPos)/判定当前位置是否可以通过，即是未曾走到过的通道块void FootPrint(PosType CurPos)/给当前可通过的位置标记PosType NextPos(PosType CurPos,int di)/探寻下一个位置，并标记方向Status MazePath(SqStack &S, PosType start, PosType end)/求解迷宫maze中，从入口start到出口end的一条路径，/如存在，返回OK，否则返回ERROR3、 栈类型typedef structint ord; /通道块在路径上的“序号”int di; /通道块在迷宫中的“坐标位置”PosType seat;/从此通道块走向下一通道块的“方向”SElemType; /栈的元素类型typedef structSElemType *base;/在构造栈之前和销毁之后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack;/栈定义栈的基本操作如下：void InitStack(SqStack &S)/初始化栈，设栈S为空栈（S.top=NULL）void Push(SqStack &S,SElemType e)/若分配空间成功，则在S 的栈顶插入新的栈顶元素e/否则增加栈栈的存储空间，再插入新的元素int GetTop(SqStack &S,SElemType e)/若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSEint Pop(SqStack &S,SElemType &e)/若栈不空，则删除S 的栈顶元素并以e 带回其值，且返回TRUE/否则返回FALSEint StackEmpty(SqStack S)/若S为空栈（S.top=NULL），则返回TRUE；否则返回FALSE具体部分操作的算法如下： void InitStack(SqStack &S) /初始化栈S为空栈（S.top=NULL）S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;/Initstackvoid Push(SqStack &S,SElemType e) /若分配空间成功，则在S 的栈顶插入新的栈顶元素e/否则增加栈栈的存储空间，再插入新的元素 if(S.top-S.base=S.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e;/Push4、 求解迷宫的伪码算法：Status MazePath(SqStack &S, PosType start, PosType end) /若迷宫maze中存在从入口start到出口end的通道，则/一条存放在栈中(从栈底到栈顶为从入口到出口的路径)，并返/回OK，否则返回ERRORPosType curpos;int curstep;SElemType e;InitStack(S);curpos = start;/设定“当前位置”为“初始位置” curstep = 1; /探索第一步 do if (Pass(curpos) /当前位置可以通过，即是未曾走到过的的通道块/留下足迹FootPrint(curpos); e.di =1;e.ord = curstep;e.seat= curpos;Push(S,e); /加入路径 if (curpos.row=end.row & curpos.line=end.line) return OK; /到达出口位置 curpos = NextPos(curpos, 1); curstep+;/探索下一步 else /当前位置不能通过 if (!StackEmpty(S) Pop(S,e);while (e.di=4 & !StackEmpty(S) FootPrint(e.seat); Pop(S,e); curstep-； if (e.diseat.rowp-seat.line=2;p+;/将有效路径的通道块全部标记为2或其他不为1或0的/值int i,flag=0;/打印出路径，周围用“#”围成一圈作围墙for(i=0;im+2;i+)printf(%c ,#);printf(n);for(i=1;in+1;i+) printf(%c ,#);for(int j=1;jm+1;j+)if(mazeij=2) printf(%c ,0);else printf( );printf(%c,#);printf(n);for(i=0;im+2;i+)printf(%c ,#);printf(nn);/printpathint main()/主函数SqStack S;int r,l;while(true)printf(创建一个迷宫，请输入迷宫长和宽(不得大于20):n);scanf(%d%d,&r,&l);if(r20|l20)printf(输入错误!);int i;printf(按行输入%d*%d数据(0代表可通,1代表不可通):n,r,l);for(i=0;il+2;i+)maze0i=1;for(i=1;ir+1;i+)mazei0=1;for(int j=1;jl+1;j+)scanf(%d,&mazeij);mazeil+1=1;for(i=0;imaze22-maze32-maze33-maze43-maze53-maze54-maze55-maze56，但是最后发现这样只有在入口在左上角，出口在右下角时，才可以正确输出。但是入口和出口是随机的，若是入口在右下角，出口在左上角，则也同样输出maze12-maze22-maze32-maze33-maze43-maze53-maze54-maze55-maze56，虽然这两个路径是一样的，但是有先后顺序，故最后没有输出这种形式，将这段代码注释了（源程序中有注释的代码）；2、本来是想设计成既可以手动输入迷宫又可以自动生成迷宫，但是感觉没有太大的用处，所以最后省略了，只保留了手动输入。3、在整个编写的过程中，出现过很多错误，包括一些标点符号的小错误，但是借助DEBUG调试器和数据观察窗口，很快找出来问题的所在。五、 用户手册1、 本程序的运行环境为 DOS 操作系统, 执行文件为：迷宫求解.exe.2、 进入演示程序后 , 即显示文本方式的用户界面:3、 根据提示输入迷宫大小及迷宫后,输入迷宫的行和列,回车后即可得到所 输入迷宫的解或者是显示“该迷宫找不到通路!”字样。六、 测试结果1、 输入长宽为5，6，入口为（1,2），出口为（5,6）的迷宫1 0 0 1 1 10 0 1 1 1 11 0 0 0 1 10 1 0 1 1 11 1 0 0 0 0求解结果：2、 输入长宽为4，5，入口为（1,1），出口为（4,5）的迷宫0 1 0 1 1