数据结构迷宫课程设计
- 格式：doc
- 大小：97.00 KB
- 文档页数：9
《数据结构》课程设计报告课题名称：__迷宫问题_______ _____班级：_____计算机3班_____________学号：____20090805344__________姓名：______于韬____________指导老师：________刘杰__________2010年6月一、课题名称：迷宫问题二、课题设计的基本思想，原理和算法描述所谓求迷宫问题，就是在一个指定的迷宫中求出从入口到出口的路径，在求解时，我们先从入口出发，顺某一方向向前试探，若能走通，则继续往前走，否则，沿原路退回，换一个方向再继续试探，直至所有可能的通路都试探完为止。
三、源程序及注释#include <stdio.h>#define Maxsize 500#define M 4#define N 4struct{int i,j,di; //当前方块行号、列号、下一可走相邻方位的方位号}qu[Maxsize],path[Maxsize]; //定义栈、最小路径存放int top=-1; //初始化栈顶指针int mgpath(int xi,int yi,int xe,int ye,int mg[M+2][N+2]) //求解路径为(xi.yi)->(xe,ye){ //此处放置前面顺序栈的定义int num=0;int i,j,k,di,find,minlenth=Maxsize;top++; //初始化栈qu[top].i=xi;qu[top].j=yi; //取栈顶方块qu[top].di=-1; //找到了出口，输出路径mg[1][1]=-1;printf("迷宫路径如下：\n");while(top>-1)//栈不为空时循环{i=qu[top].i;j=qu[top].j;di=qu[top].di;if(i==xe&&j==ye){num++;printf("第%d条路径:\n",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("\n");}printf("\n\n");mg[qu[top].i][qu[top].j]=0;if(top+1<minlenth){minlenth=top+1;for(int c=0;c<=top;c++)path[k]=qu[k];}top--;i=qu[top].i;j=qu[top].j;di=qu[top].di;}find=0;while(di<=4&&find==0) //找(i,j)下一可走方块{di++; //找下一方位switch(di){case 0: i=qu[top].i-1; j=qu[top].j;break;case 1: i=qu[top].i; j=qu[top].j+1;break;case 2: i=qu[top].i+1; j=qu[top].j;break;case 3: 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--; //该方块退栈}}printf("路径条数：%d\n",num);printf("\n最短路径长度为：%d\n",minlenth);printf("\n最短路径为：\n");for(k=0;k<=minlenth;k++){printf("\t(%d,%d)",path[k].i,path[k].j);if((k+1)%5==0)printf("\n");}printf("\n");return(0); //没有可走路径，返回0}void main(){int i,j;int mg[M+2][N+2]={{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},{1,0,0,0,1,1},{1,1,0,0,0,1}};printf("迷宫图如下：\n");for(i=0;i<=M+1;i++){printf(" ");for(j=0;j<=N+1;j++)printf("%d ",mg[i][j]);printf("\n");}mgpath(1,1,M,N,mg);}四、运行示例及结果分析五、调试和运行程序过程中产生的问题及采取的措施在调试的过程当中，对于最短路径和路径长度这一问题，书上都给出了例子，且在课件和书本的第三章都有一定的解释，这一问题我们可以依据书本的提示来解决，但若要输出所有的路径，我们就得另外进行考虑，全部输出，就是将内容逐一输出，沿着这一思路，在参考C语言以及C++的相关内容，得到我们可以用FOR语句来对其进行解决。
六、对课题相关算法的讨论、分析，改进设想本课题在一些问题上可以有多种算法，比如说，在输出所有路径这一问题上，我们就可以采用当型循环来做，但相对于当型循环，FOR语句循环比较方便，同时，在迷宫数组的中，我们也采用其他格式。
七、总结本次课题需要我们对问题做进一步的分析，且需要我们参考不同书本以及课外的相关知识，需要我们对其做进一步的融合，且本次课题中的每一步都有不同的问题，这就需要我们应用不同的知识来对其进行解决，总体来说，就是我们要应用不同的知识解决不同的问题，且要对其进行融合，来时不同的问题变成一个问题，不同的知识可以相互结合，来解决一个问题。
八、参考文献数据结构课件中的第三章中的迷宫问题的解决方法，以及课本第三章中的迷宫问题的算法列举，还有C语言以及C++书本的中的循环语句，以及数组和指针还有嵌套循环方面的知识，以及书本和课外其他方面的知识。
#include <stdio.h>#define Maxsize 500#define M 4#define N 5struct{int i,j,di; //当前方块行号、列号、下一可走相邻方位的方位号}qu[Maxsize],path[Maxsize]; //定义栈、最小路径存放int top=-1; //初始化栈顶指针int mgpath(int xi,int yi,int xe,int ye,int mg[M+2][N+2]) //求解路径为(xi.yi)->(xe,ye){ //此处放置前面顺序栈的定义int num=0;int i,j,k,di,find;top++; //初始化栈qu[top].i=xi;qu[top].j=yi; //取栈顶方块qu[top].di=-1; //找到了出口，输出路径mg[1][1]=-1;printf("迷宫路径如下：\n");while(top>-1) //栈不为空时循环{i=qu[top].i;j=qu[top].j;di=qu[top].di;if(i==xe&&j==ye){num++;printf("第%d条路径:\n",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)printf("\n");}printf("\n\n");mg[qu[top].i][qu[top].j]=0;for(int c=0;c<=top;c++){path[k]=qu[k];}top--;i=qu[top].i;j=qu[top].j;di=qu[top].di;}find=0;while(di<=4&&find==0) //找(i,j)下一可走方块{di++; //找下一方位switch(di){case 0: i=qu[top].i-1; j=qu[top].j;break;case 1: i=qu[top].i; j=qu[top].j+1;break;case 2: i=qu[top].i+1; j=qu[top].j;break;case 3: 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--; //该方块退栈}}printf("路径条数：%d\n",num);printf("\n");return(0); //没有可走路径，返回0}void main(){int i,j;int mg[M+2][N+2]={{1,1,1,1,1,1,1},{1,0,0,0,1,0,1},{1,0,1,0,0,1,1},{1,0,0,0,0,0,1},{1,1,1,1,1,0,1}};printf("迷宫图如下：\n");for(i=0;i<=M+1;i++){printf(" ");for(j=0;j<=N+1;j++)printf("%d ",mg[i][j]);printf("\n");}mgpath(1,1,M,N,mg);}。
