资源描述:
《数据结构迷宫课程设计.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、《数据结构》课程设计报告课题名称:__迷宫问题____________班级:_____计算机3班_____________学号:______________姓名:______于韬____________指导老师:________刘杰__________2010年6月一、课题名称:迷宫问题二、课题设计的基本思想,原理和算法描述所谓求迷宫问题,就是在一个指定的迷宫中求出从入口到出口的路径,在求解时,我们先从入口出发,顺某一方向向前试探,若能走通,则继续往前走,否则,沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。三、源程序及注释#include#define
2、Maxsize500#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[top].j=yi;//
3、取栈顶方块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("");}printf("");m
4、g[qu[top].i][qu[top].j]=0;if(top+15、].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;//该位置变为其他路径可走方向top--;
6、//该方块退栈}}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,0,0,1},{1,0
7、,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);}四、运行示例及结果分析五、调试和运行程序过程中产生的问题及采取的措施在调试的过程当中,对于最短路径和路径长度这一问题,书上都