1、 数据结构 课程设计报告 课题名称：课题名称：_迷宫问题迷宫问题_ _ 班级：班级：_计算机计算机 3 3 班班_ _ 学学 号：号：_ _ 20102010 年年 6 6 月月 一、课题名称：迷宫问题一、课题名称：迷宫问题 二、课题设计的基本思想，原理和算法描述二、课题设计的基本思想，原理和算法描述 所谓求迷宫问题， 就是在一个指定的迷宫中求出从入口到出口的所谓求迷宫问题， 就是在一个指定的迷宫中求出从入口到出口的 路径，在求解时，我们先从入口出发，顺某一方向向前试探，若路径，在求解时，我们先从入口出发，顺某一方向向前试探，若 能走通，则继续往前走，否则，沿原路退回，换一个方向再继续能走通，
2、则继续往前走，否则，沿原路退回，换一个方向再继续 试探，直至所有可能的通路都试试探，直至所有可能的通路都试探完为止。探完为止。 三、源程序及注释三、源程序及注释 #include #define Maxsize 500 #define M 4 #define N 4 struct int i,j,di; /当前方块行号、当前方块行号、 列号、下一可走相邻方位的方位号列号、下一可走相邻方位的方位号 quMaxsize,pathMaxsize; /定义栈、定义栈、最小最小 路径存放路径存放 int top=-1; /初始化栈顶初始化栈顶 指针指针 int mgpath(int xi,int yi,
3、int xe,int ye,int mgM+2N+2) /求解路径为求解路径为 (xi.yi)-(xe,ye) /此处放置此处放置 前面顺序前面顺序栈的定义栈的定义 int num=0; int i,j,k,di,find,minlenth=Maxsize; top+; /初始化栈初始化栈 qutop.i=xi; qutop.j=yi; /取栈顶方块取栈顶方块 qutop.di=-1; /找到了出口，找到了出口， 输出路径输出路径 mg11=-1; printf(“迷宫路径如下：迷宫路径如下：n“); while(top-1)/栈不为空时循环栈不为空时循环 i=qutop.i;j=qutop.j; di=qutop.di; if(i=xe printf(“第第%d 条路径条路径:n“,num); for(k=0;k=top;k+) pathk=quk; printf(“t(%d,%d)“,quk.i,quk.j); if(k+1)%5=0) /每输出每输出 5
