数据结构迷宫课程设计

《数据结构》课程设计报告

课题名称：__迷宫问题_______ _____ 班级：_____软件二班____________ 学 号：____101842168__________ 姓 名：______何宇___________ 指导老师：________储岳中__________

2012年6月3号

一、课题名称：迷宫问题

二、课题设计的基本思想，原理和算法描述

所谓求迷宫问题，就是在一个指定的迷宫中求出从入口到出口的路径，在求解时，我们先从入口出发，顺某一方向向前试探，若能走通，则继续往前走，否则，沿原路退回，换一个方向再继续试探，直至所有可能的通路都试探完为止。

三、源程序及注释

#include

#define Maxsize 500 #define M 4 #define N 4 struct { 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\ for(k=0;k<=top;k++) { path[k]=qu[k]; printf(\

if((k+1)%5==0) //每输出5个方块后换一行

printf(\ }

printf(\

mg[qu[top].i][qu[top].j]=0; if(top+1

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; //修改原栈顶元素di top++; //将可走相邻方块进栈 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\

printf(\最短路径长度为：%d\\n\ printf(\最短路径为：\\n\ for(k=0;k<=minlenth;k++) { printf(\ if((k+1)%5==0) printf(\ } printf(\ return(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(\ printf(\ }

mgpath(1,1,M,N,mg); }

//没有可走路径，返回0

四、运行示例及结果分析

五、调试和运行程序过程中产生的问题及采取的措施

在调试的过程当中，对于最短路径和路径长度这一问题，书上都给出了例子，且在课件和书本的第三章都有一定的解释，这一问题我们可以依据书本的提示来解决，但若要输出所有的路径，我们就得另外进行考虑，全部输出，就是将内容逐一输出，沿着这一思路，在参考C语言以及C++的相关内容，得到我们可以用FOR语句来对其进行解决。

六、对课题相关算法的讨论、分析，改进设想

本课题在一些问题上可以有多种算法，比如说，在输出所有路径这一问题上，我们就可以采用当型循环来做，但相对于当型循环，FOR语句循环比较方便，同时，在迷宫数组的中，我们也采用

其他格式。

七、总结

本次课题需要我们对问题做进一步的分析，且需要我们参考不同书本以及课外的相关知识，需要我们对其做进一步的融合，且本次课题中的每一步都有不同的问题，这就需要我们应用不同的知识来对其进行解决，总体来说，就是我们要应用不同的知识解决不同的问题，且要对其进行融合，来时不同的问题变成一个问题，不同的知识可以相互结合，来解决一个问题。

八、参考文献

数据结构课件中的第三章中的迷宫问题的解决方法，以及课本第三章中的迷宫问题的算法列举，还有C语言以及C++书本的中的循环语句，以及数组和指针还有嵌套循环方面的知识，以及书本和课外其他方面的知识。

#include

#define Maxsize 500 #define M 4 #define N 5 struct { 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\ for(k=0;k<=top;k++) { path[k]=qu[k]; printf(\ if((k+1)%5==0) printf(\ }

printf(\

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) { 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; //找(i,j)下一可走方块 //找下一方位 //找到下一可走相邻方块 //找到一可走相邻方块 //修改原栈顶元素di

top++; //将可走相邻方块进栈 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\ printf(\ return(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(\ printf(\ }

mgpath(1,1,M,N,mg); }

//没有可走路径，返回0

本文来源：https://www.bwwdw.com/article/h5wr.html