数据结构课程设计-迷宫问题

1、第一部分 第二部分 第三部分 第四部分 第五部分 第六部分 第七部分目录 需求分析 详细设计 调试分析 用户手册 测试结果 附录 参考文献需求分析1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到出 口的通路，并把这条通路显示出来；如果没有找到这样的通路给出没 有这样通路的信息。2、可以用一个mK n的长方阵表示迷宫，0和1分别表示迷宫中的 通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到 出口的通路，或得出没有通路的结论。3、 编写一个求解迷宫的非递归程序。求得的通路以三元组 (i , j , d)的形式输出，其中：(i , j)指示迷宫中的一个坐标，d表示走到下 一坐标

2、的方向。4、由于迷宫是任意给定的，所以程序要能够对给定的迷宫生成对应 的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内墙的 个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。二、详细设计1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发， 顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路 退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所 有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1, 1），出口点的下标为（n，n）。为处理方便起见，可在迷宫的四周加一圈障碍。 对于迷宫中任一位置，均可约

3、定有东、南、西、北四个方向可通。2、如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步， 如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通。3、所谓走不通不单是指遇到墙挡路，还有已经走过的路不能 重复走第二次”，它包括曾经走过而没有走通的路”。显然为了保证在任何位置上都能沿原路退回，需要用一个后进先出的结构即栈来保存从入口到当前位置的路径。并且在走出出口 之后，栈中保存的正是一条从入口到出口的路径。4、若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位 置”探索；若当前位置“不可

4、通”，则应顺着“来的方向”退回到“前 一通道块”，然后朝着除“来向”之外的其他方向继续探索；若该通 道块的四周四个方块均“不可通”，则应从“当前路径”上删除该通 道块。所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、 北）上相邻的方块。假设以栈 S记录“当前路径”，则栈顶中存放的 是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当 前位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。5、找通路的程序的关键部分可以表示如下:do若当前位置可通, 则将当前位置插入栈顶；纳入路径若该位置是出口位置，则算法结束；/此时栈中存放的是一条从入口位置到出口位置的路径 否

5、则切换当前位置的东邻方块为新的当前位置；否则若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为：沿顺时针方向旋转找到的栈顶位置的 下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/从路径中删去该通道块若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空； while （ 栈不空）；6、程序中用的数据结构解析：程序中用了顺序栈保存当前找到的路径， 当前位置不可通时,可以出栈，退回到前一个位置再继续探索通路，栈的定义如下:struct SqStackSElemType *base; /在栈构造之前和销毁之后，base的值为 NULLSElemType *t

6、op; /栈顶指针int stacksize; /当前已分配的存储空间，以兀素为单位； / 顺序栈栈中元素的类型结构程序中先定义了一个表示坐标的类型结构:struct PosType / 迷宫坐标位置类型int x; /行值int y; /列值;栈中元素的类型结构如下：struct SElemType /栈的元素类型int ord; /通道块在路径上的序号PosType seat; /通道块在迷宫中的坐标位置int di; /从此通道块走向下一通道块的方向(03表示东北);7、主函数的流程图三、调试分析1、对于程序的设计由简单到复杂，先设计一个整体的轮廓然后再慢 慢的增加程序的功能，这样能够有

7、效的减少错误，功能慢慢的增加， 在前一步的程序运行通过之后再继续增加功能， 这样在检查错误的时 候比较有目的性，提高写程序的效率。2、对于程序中的错误，如果遇到说变量没有定义或者数据结构没定 义的错误，可能是由于你在定义这种数据结构的变量时数据结构还没 有定义，也就是说在定义此数据结构的变量的语句要放在声明这种结 构体之后。3、在写程序时要注意printf和seanf语句的格式，格式不对会得不 到你想要的结果。4、写程序时一定要瞻前顾后，前后一致，包括名称、数据类型等等。四、用户手册在使用程序时严格按照程序给出的提示一步一步来，下面给出程 序正常执行的步骤：1、 程序会提示“请输入迷宫的行数，

8、列数（包括外墙）：”这时 就需要输入表示迷宫的二维数组的行数和列数， 需要注意的是由于我 们在迷宫周围加了一道墙，所以要输入的行列数要比实际表示迷宫的 行列数多两行两列。2、程序提示“请输入迷宫内墙单兀数：”此时需要输入迷宫中墙 的数目。3、程序提示“请依次输入迷宫内墙每个单元的行数，列数： ”此 时要输入迷宫中所有墙的坐标，我们用数组中的一个元素来表示墙。4、在输入了迷宫所有内墙的坐标后，程序会显示出迷宫的结构， 然后程序会提示“请输入起点的行数，列数：”此时需要输入所求通 路的起点坐标。5、程序提示“请输入终点的行数，列数：”此时需要输入所求通 路的终点的坐标。6、终点坐标输入完毕之后，程

9、序会显示出两种运行的结果，一种 是输出了迷宫的结构，此时迷宫中已包含了所找的通路，用连续的数 字表示出了通路在迷宫中是如何走的，此时迷宫中的 -1表示找通路 时走过的单元但是通路不通。注意：再输入内墙单元的坐标是一定要细心，不要错输，也不要 漏输。否则程序会出错。五、测试结果迷宫的测试数据如下：左上角（1，1）为入口，右下角（9，8）为出口00100010001000100000110101110010000100000100010101111001110001011100000012345678程序的测试结果为:1、程序的开始界面回* C:Usersz haoya ohuiDe skto p

10、De b u 匚11辻官 P.Id.exe3、输入内墙的个数之后hC:Use rszhaoya ohu iDes kt o pDe bug 迷言问 H.exeii 1in列4、再输入了所有内墙的坐标后，程序会给出迷宫的结构5、输入所求通路的起点坐标6、输入所求通路的终点坐标后会得到结果结果以迷宫的形式输出广C:Usersz haoya ohuiDE skto pDe bug 迷肓问鬆.电灼b1:数迂仃到1的的口工丄点点入1起贵1人人宫丄 青-14i諾T 111 9fe.八 1l-vnft1T514111110 0 01 B 0011110 171 18110 19 201111111去到的路径

11、用坐标表示如下:1 &2 1:2 1 结果用坐标和下一位值的方向表示* C:Usersz haoy ohu iDe skto pDebug ViiM 问 H .exe六、附录（附有完整的源程序）源程序如下：#i ncludestdio.h#i ncludestdlib.h#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1#defi ne ERROR 0#defi ne OVERFLOW -2typedef int Status;#define STACK_INIT_SIZE 10 /存储空间初始分配量#define STACKINCREMENT 2 /存储

12、空间分配增量struct PosType /迷宫坐标位置类型int x; / 行值int y; / 列值;struct SElemType /栈的元素类型int ord; /通道块在路径上的序号PosType seat; /通道块在迷宫中的坐标位置int di; /从此通道块走向下一通道块的方向（03表示东北） ；struct SqStackSElemType *base; /在栈构造之前和销毁之后，base的值为NULLSElemType *top; / 栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位; /顺序栈SqStack S;#define MAXLENGT

13、H 25 /设迷宫的最大行列为 25 typedef int MazeTypeMAXLENGTHMAXLENGTH; /迷宫数组行列/全局变量MazeType m; /迷宫数组int curstep=1; /当前足迹,初值为1Status In itStack(SqStack &S) /构造一个空栈Sif(!(S.base=(SEIemType *)malloc(STACK_INIT_SIZE*sizeof(SEIemType) exit(OVERFLOW); /存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status St

14、ackEmpty(SqStack S) /若栈S为空栈，则返回TRUE，否则返回FALSE if(S.top=S.base)return TRUE;elsereturn FALSE;Status Push(SqStack & S,SElemType e) /插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize) / 栈满，追加存储空间S.base=(SEIemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SEIemType); if(!S.base)exit(OVERFLOW); /存储分配失败S.t

15、op=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top)+=e;return OK;Status Pop(SqStack & S,SElemType &e) /若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERRORif(S.top=S.base)return ERROR;e=*-S.top;return OK;Status Pass(PosType b) /当迷宫m的b点的序号为0(可通过路径),return OK;否则，return ERROR if(mb.xb.y=0)return OK;elsereturn

16、ERROR;void FootPri nt(PosType a) /使迷宫m的a点的序号变为足迹(curstep) ma.xa.y=curstep;PosType NextPos(PosType c,i nt di) /根据当前位置及移动方向，返回下一位置PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量，列增量/移动方向，依次为东南西北c.x+=direcdi.x;c.y+=direcdi.y;return c;void MarkPri nt(PosType b) /使迷宫m的b点的序号变为-1(不能通过的路径) mb.xb.y=-1;Status MazePat

17、h(PosType start,PosType end)算法 3.3 /若迷宫maze中存在从入口 start到出口 end的通道，则求得一条 /存放在栈中(从栈底到栈顶)，并返回TRUE ;否则返回FALSE PosType curpos;Ini tStack(S);SElemType e;curpos=start;doif(Pass(curpos) /当前位置可以通过，即是未曾走到过的通道块FootPri nt(curpos); / 留下足迹e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(S,e); /入栈当前位置

18、及状态curstep+; / 足迹加 1if(curpos.x=end.x&curpos.y=end.y) / 到达终点(出口) return TRUE;curpos=NextPos(curpos,e.di);else /当前位置不能通过if(!StackEmpty(S)Pop(S,e); /退栈到前一位置curstep-;while(e.di=3&!StackEmpty(S) / 前一位置处于最后一个方向(北) MarkPrint(e.seat); /留下不能通过的标记(-1)Pop(S,e); / 退回一步curstep-;if(e.di3) /没到最后一个方向(北)e.di+; /换下一

19、个方向探索Push(S,e);curstep+;curpos=NextPos(e.seat,e.di); 设定当前位置是该新方向上的相邻块while(!StackEmpty(S);return FALSE;void Prin t(i nt x,i nt y) /输出迷宫的解int i,j;for(i=0;ix;i+)for(j=0;jvy;j+)prin tf(%3d,mij);prin tf(n);void mai n()PosType begi n,end;int i,j,x,y,x1,y1;SElemType a;SqStack T;In itStack(T);printf(请输入迷宫的行数，列数(包括外墙):); sca nf(%d%d, &x,&y);for(i=0;iy;i+) /定义周边值为0(同墙) m0i=1;