迷宫问题课程设计报告.docx

《迷宫问题课程设计报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计报告课程设计题目：小组成员何保平（8）蔡聪聪（9）吴俊文（0）班级专业软件工程指导教师高永平2016年01月05日一、任务可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。二、问题分析迷宫问题采用试探法求解，即从入口出发，在当前位置任选一个方向向前试探，若下一位置可通（即该位置为从未走过的通道块）则继续试探行进；若当前位置的所有方向均不通（为墙体或已走过的通道块）时，则按原路返回上一位置，重新选择其他方向继续试探前进。这样不断试探前进，知道到达迷宫出口则求解了一种可行

2、的路径；若沿入口的所有方向都不能到达出口，则说明此迷宫不存在可行路径。这种经试探可行则行进，不可行则返回重新试探的方法，则可以作为该问题的求解方法。三、具体实现1.迷宫实现用一个二维数组代表迷宫，数组的值用1或0表示，1表示不通，0表示可通。2.过程实现用一个栈存储探索过程中生成的路径，若当前位置可通时，则将其入栈纳入路径；而当返回前一位置时，则进行出栈操作。四、源代码（一）头文件1、数组位置的定义#includeusingnamespacestd;typedefstruct//位置类定义

3、{intx;//行下标inty;//列下标}posType;typedefstruct//路径栈中元素定义类型{posTypepos;//路径中的通道位置intdirc;//从前一位置到该位置的行进方向，值1~4分别代表右，下，左，上}SElemType;2、栈的定义，以及栈的相应函数的定义#defineStackSpaceIncr20typedefstruct{SElemType*base;inttop;intstackSize;}SqStack;//栈intInitSqStack(SqStack&S,in

4、tInitSize)//初始{S.base=(SElemType*)malloc(InitSize*sizeof(SElemType));if(!S.base)return-2;S.stackSize=InitSize;S.top=0;return1;}boolstackIsEmpty(SqStackS)//判空{if(!S.top)returntrue;elsereturnfalse;}intPush(SqStack&S,SElemTypee)//入栈{SElemType*newbase;if(S.top=

5、=S.stackSize){newbase=(SElemType*)realloc(S.base,(S.stackSize+1)*sizeof(SElemType));if(!newbase)return-2;S.base=newbase;S.stackSize+=1;}S.base[S.top]=e;S.top++;return1;}intPop(SqStack&S,SElemType&e)//出栈{if(!S.top)return0;S.top--;e=S.base[S.top];return1;}int

6、getTop(SqStackS,SElemType&e){if(!S.top)return0;e=S.base[S.top-1];return1;}intstackEmpty(SqStackS){if(!S.top)return1;elsereturn0;}intstackLength(SqStackS){returnS.top;}（二）主函数以及实现#include"Status.h"#include"Stack.h"#includeusingnamespacestd;#defineRo

7、w12#defineCol12posTypenextPos(posTypecurPos,intd)//返回curPos沿方向d行进的下一位置{posTypepos;switch(d){case1:pos.x=curPos.x;pos.y=curPos.y+1;break;//向右case2:pos.x=curPos.x+1;pos.y=curPos.y;break;//向下case3:pos.x=curPos.x;pos.y=curPos.y-1;break;//向右case4:pos.x=curPos.x-

8、1;pos.y=curPos.y;break;//向上}returnpos;}boolcanGo(posTypepos,intM[Row][Col])//判断pos位置是否可通{if(M[pos.x][pos.y]==0)//为为走过的通道块returntrue;elsereturnfalse;}boolMaze(intM[Row][Col],posTypeend,posTypestart)//对于