数据结构设计报告总结

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

课题名称： 迷宫设计 专业班级： 学 号： 姓 名： 指导老师：

2010年12月

一、课题名称

迷宫问题(栈和队列)

求迷宫问题就是求出从入口到出口的所有路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。

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

1，给点一个迷宫图，求一条从指定入口到出口的路径。假设迷宫如图所示 {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},

{1,1,1,1,1,1}。对于图中的每个方块，用0表示通道，用1表示墙。所求的路径是最短路径，即在求得的路径上不能重复出现同一个通道块。

为了表示迷宫，设置一个数组mg。为了算法方便，在一般的迷宫外围加了一条围墙，迷宫对应的迷宫数组mg，如上图所示，由于迷宫四周加了一条围墙，因此mg的行数列数均加2 （int mg[M+2][N+2]=）

2, 在算法中用到的栈采用顺序栈存储结构，即将栈定义为： struct { int i;int j;int di;

} Stack[MaxSize],path[MaxSize];

int top=-1;

3，建立如下主函数调用下述算法： void main() { printf(\迷宫所有路径如下:\\n\ mgpath(); }

三、源程序及注释

#include

#define M 4 //行数 #define N 4 //列数

#define MaxSize 100 //栈最多元素个数

int mg[M+2][N+2]={ //一个迷宫,其四周要加上均为1的外框

{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}, {1,1,1,1,1,1} }; struct { int i;int j;int di;

} Stack[MaxSize],path[MaxSize]; //定义栈和存放最短路径的数组 int top=-1; //栈顶指针 int count=1; //路径数计数 int minlen=MaxSize; //最短路径长度

void mgpath() //路径为:(1,1)->(M,N) { int i,j,di,find,k; top++; Stack[top].i=1; Stack[top].j=1; Stack[top].di=-1;mg[1][1]=-1; //初始结点进栈 while(top>-1) //栈不空时循环 { i=Stack[top].i;j=Stack[top].j;di=Stack[top].di; if (i==M && j==N) //找到了出口,输出路径 { printf(\ for (k=0;k<=top;k++) { printf(\ \ if((k+1)%5==0) printf(\ //输出时每5个结点换一行 } printf(\ if(top+1

find=0; while(di<4 && find==0) //找下一个可走结点 { di++; //找下一个方位 switch(di) { case 0:i=Stack[top].i-1;j=Stack[top].j;break; case 1:i=Stack[top].i;j=Stack[top].j+1;break; case 2:i=Stack[top].i+1;j=Stack[top].j;break; case 3:i=Stack[top].i,j=Stack[top].j-1;break; } if (mg[i][j]==0) find=1; } if (find==1) { Stack[top].di=di; top++; Stack[top].i=i; Stack[top].j=j; Stack[top].di=-1; mg[i][j]=-1; } else { mg[Stack[top].i][Stack[top].j]=0; 走结点 top--; } } printf(\最短路径如下:\\n\ printf(\长度: %d\\n\ printf(\路径: \ for (k=0;k

void main() { printf(\迷宫所有路径如下:\\n\ mgpath(); }

//找到了下一个可走结点 //修改原栈顶元素的di值 //下一个可走结点进栈 //避免重复走到该结点 //没有路径可走,则退栈 //让该位置变为其他路径可 //将该方块退栈 //输出时每5个结点换一行

四、运行示例及结果分析

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

用数组表示迷宫，用顺序栈存储数据。

程序中用到最下长度变量minlen，将最大变量maxsize赋值给minlen，比较所有最短路径，找出最下路径。

if(top+1

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

求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。

求解迷宫(1,1)到(M-2,N-2)路径的过程是:先将入口进栈(初始方位设置为-1),在栈不空时循环:取栈顶方块(不退栈),若该方块是出口,则输出栈中方块即为路径。否则,找下一个可走的相邻方块,若不存在这样的方块,则退栈。若存在这样的方块,则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈(初始方位设置为-1)。

为了保证试探的可走相邻方块不是已走路径上的方块,如(i,j)已进栈,在试探(i+1,j)

的下一可走方块时,又试探到(i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的mg数组元素值改为-1(变为不可走的相邻方块),当退栈时(表示没有可走相邻方块),将其恢复为0。

七、总结

栈的主要特点是“后进先出”，因此栈也称为后进先出表。运用栈对迷宫进行编程，可以很快的找到最短路径的长度，算出最短路径。

八、参考文献

【1】 李春葆，伊为民，李蓉蓉，将晶钰，喻丹丹. 数据结构教程（第3版）.北京：清华

大学出版社，2009.

【2】 李春葆，伊为民，李蓉蓉，将晶钰，喻丹丹. 数据结构教程（第3版）上机实验指

导.北京：清华大学出版社，2009.

【3】 李春葆，曾慧，张植民. 数据结构程序设计题典. 北京：清华大学出版社，2002.

的下一可走方块时,又试探到(i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的mg数组元素值改为-1(变为不可走的相邻方块),当退栈时(表示没有可走相邻方块),将其恢复为0。

七、总结

栈的主要特点是“后进先出”，因此栈也称为后进先出表。运用栈对迷宫进行编程，可以很快的找到最短路径的长度，算出最短路径。

八、参考文献

【1】 李春葆，伊为民，李蓉蓉，将晶钰，喻丹丹. 数据结构教程（第3版）.北京：清华

大学出版社，2009.

【2】 李春葆，伊为民，李蓉蓉，将晶钰，喻丹丹. 数据结构教程（第3版）上机实验指

导.北京：清华大学出版社，2009.

【3】 李春葆，曾慧，张植民. 数据结构程序设计题典. 北京：清华大学出版社，2002.

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