数据结构迷宫课程设计

《数据结构迷宫课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程设计报告课题名称：__迷宫问题____________班级：_____计算机3班_____________学号：____20090805344__________姓名：______于韬____________指导老师：________刘杰__________2010年6月一、课题名称：迷宫问题二、课题设计的基本思想，原理和算法描述所谓求迷宫问题，就是在一个指定的迷宫中求出从入口到出口的路径，在求解时，我们先从入口出发，顺某一方向向前试探，若能走通，则继续往前走，否则，沿原路退回，换一个方向再继续试探，直至所有可能的通路都试探完为止。三、源程序及注释#include

2、o.h>#defineMaxsize500#defineM4#defineN4struct{inti,j,di;//当前方块行号、列号、下一可走相邻方位的方位号}qu[Maxsize],path[Maxsize];//定义栈、最小路径存放inttop=-1;//初始化栈顶指针intmgpath(intxi,intyi,intxe,intye,intmg[M+2][N+2])//求解路径为(xi.yi)->(xe,ye){//此处放置前面顺序栈的定义intnum=0;inti,j,k,di,find,minlenth=Maxsize;top++;//初始化栈qu[top].i=xi;qu[t

3、op].j=yi;//取栈顶方块qu[top].di=-1;//找到了出口，输出路径mg[1][1]=-1;printf("迷宫路径如下：");while(top>-1)//栈不为空时循环{i=qu[top].i;j=qu[top].j;di=qu[top].di;if(i==xe&&j==ye){num++;printf("第%d条路径:",num);for(k=0;k<=top;k++){path[k]=qu[k];printf("t(%d,%d)",qu[k].i,qu[k].j);if((k+1)%5==0)//每输出5个方块后换一行printf("");}print

4、f("");mg[qu[top].i][qu[top].j]=0;if(top+1

5、e2:i=qu[top].i+1;j=qu[top].j;break;case3:i=qu[top].i;j=qu[top].j-1;break;}if(mg[i][j]==0)find=1;//找到下一可走相邻方块}if(find==1)//找到一可走相邻方块{qu[top].di=di;//修改原栈顶元素ditop++;//将可走相邻方块进栈qu[top].i=i;qu[top].j=j;qu[top].di=-1;mg[i][j]=-1;//值制为-1，避免重复走到该方块}else//没有相邻方块可走，退出栈{mg[qu[top].i][qu[top].j]=0;//该位置变为其他路

6、径可走方向top--;//该方块退栈}}printf("路径条数：%d",num);printf("最短路径长度为：%d",minlenth);printf("最短路径为：");for(k=0;k<=minlenth;k++){printf("t(%d,%d)",path[k].i,path[k].j);if((k+1)%5==0)printf("");}printf("");return(0);//没有可走路径，返回0}voidmain(){inti,j;intmg[M+2][N+2]={{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,

7、0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1}};printf("迷宫图如下：");for(i=0;i<=M+1;i++){printf("");for(j=0;j<=N+1;j++)printf("%d",mg[i][j]);printf("");}mgpath(1,1,M,N,mg);}四、运行示例及结果分析五、调试和运行程序过程中产生的问题及采取的措施在调试的过程当中，对于最短路径和路