数据结构设计报告总结

《数据结构》课程设计报告课题名称迷宫设计专业班级学号指导老师____________________2010年12月

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

二、课题设计的基本思想，原理和算法描述1,给点一个迷宫图，求一条从指定入口到出口的路径假设迷宫如图所示{111,1,1,1},{1,0』』},{1,0』,0,0』},{1,0,0,0」』},{1,1,0,0,04,{1,1,1,1,1,1}对于图中的每个方块，用表示通道，用1表示墙所求的路径是最短路径,即在求得的路径上不能重复出现同一个通道块为了表示迷宫，设置一个数组mg为了算法方便，在一般的迷宫外围加了一条围墙，迷宫对应的迷宫数组mg,如上图所示，由于迷宫四周加了一条围墙，因此mg的行数列数均加2int mg[M+2][N+2]=2,在算法中用到的栈采用顺序栈存储结构，即将栈定义为structint i;int j;int di;}Stack[MaxSize],path[MaxSize];int top=-1;3,建立如下主函数调用下述算法void mainprintf迷宫所有路径如下如mgpath;#include stdio.h

三、源程序及注释#define M4#define N4#define MaxSize100〃行数//列数int〃栈最多元素个数mg[M+2][N+2]={外〃一个迷宫，其四周要加上均为1的框{L0,0,OJ,1},{1,0」』},1,1,0,0,0,1,{1,1,1』」」};structint i;int j;int di;}Stack[MaxSize],path[MaxSize];int top-1;〃定义栈和存放最短路径的数组〃栈顶指针int count=l;〃路径数计数int minlen=MaxSize;〃最短路径长度void mgpath〃路径为为int i,j,di,find,k;top++;Stack|top].i=l;Stack[top].j=l;Stack[top],di=-l;mg[l][l]=-l;whiletop-l〃初始结点进栈〃栈不空时循环i=Stack[top].i;j=Stack[top].j;di=Stack[topl.di;〃找到了出口，输出路径if i==M j==N printf,%4d:,count++;for k=0;k=top;k++printfn%d,%d n,Stack[k].i,Stack[k]j;ifk+l%5=0printfn\n\tH;〃输出时每5个结点换一行；printf”\n iftop+lminlen for k=0;k=top;k++path[k]=Stack[k];minlen=top+l;〃比较找最短路径mg[Stack[top].i][Stack[top].j]=0;点top-;i=Stack[top].i;j=Stack[top|.j;di=Stack[top].di;〃让该位置变为其他路径可走结find=O;whiledi4find==O〃找下一个可走结点{di++;〃找下一个方位switchdi|case0:i=Stack[top].i-l;j=Stack[top].j;break;case1:i=Stack[top].i;j=Stack[top].j+1;break;case2:i=Stack[topJ.i+l;j=Stack[top].j;break;case3:i=Stack[top].ij=Stack|top].j-l;break;if mg[i][j]=O find=l;〃找到了下一个可走结点if find=l{Stack[top].di=di;〃修改原栈顶元素的di值〃下一个可走结点进栈top++;Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;mg[i][j]=-l;〃避免重复走到该结点else〃没有路径可走,则退栈〃让该位置变为其他路径可mg[Stack[top].i|[Stack|top|.j]=0;走结点top-;〃将该方块退栈printf最短路径如下如”;printf长度%d\n\minlen;printf“路径”；for k=O;kminlen;k++printfn%d,%d n,path[k].i,path[k].j;〃输出时每5个结点换一行ifk+l%5==0printfn\n\tn;}printfu\nn;void mainprintf迷宫所有路径如下:\n mgpath;

四、运行示例及结果分析

五、调试和运行程序过程中产生的问题及采取的措施用数组表示迷宫，用顺序栈存储数据程序中用到最下长度变量minlen,将最大变量maxsize赋值给minlen,比较所有最短路径，找出最下路径iftop+lminlen{fork=0;k=top;k++path[k]=Stack[k];minlen=top+l;

六、对课题相关算法的讨论、分析，改进设想求迷宫问题就是求出从入口到出口的路径在求解时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回，换一个方向再继续试探,直至所有可能的通路都试探完为止为了保证在任何位置上都能沿原路退回称为回溯，需要用一个后进先出的栈来保存从入口到当前位置的路径求解迷宫1,1到M-2,N-2路径的过程是:先将入口进栈初始方位设置为-1,在栈不空时循环:取栈顶方块不退栈，若该方块是出口，则输出栈中方块即为路径否则，找下一个可走的相邻方块,若不存在这样的方块,则退栈若存在这样的方块,则将其方位保存到栈顶元素中，并将这个可走的相邻方块进栈初始方位设置为-1为了保证试探的可走相邻方块不是已走路径上的方块,如i,j已进栈,在试探i+1,j的下一可走方块时，又试探到（i,j）,这样可能会引起死循环,为此,在一个方块进栈后，将对应的mg数组元素值改为T（变为不可走的相邻方块）,当退栈时（表示没有可走相邻方块），将其恢复为0

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

八、参考文献

[1]李春葆，伊为民，李蓉蓉，将晶铳，喻丹丹.数据结构教程（第3版）.北京清华大学出版社，

2009.

[2]李春葆，伊为民，李蓉蓉，将晶锌，喻丹丹.数据结构教程（第3版）上机实验指导.北京清华大学出版社，

2009.

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

2002.。