数据结构课程设计报告-迷宫求解.doc

数据结构课程设计报告

—---—-迷宫问题求解

学号:131５925375
姓名：刘晓龙
班级:13移动１班
指导老师:钱鸽

目录

TOC＼o"１-3"\h\uＨＹPＥRＬINK\l_Toc17６20一、需求分析ＰAGEREＦ_Toc176202
HYPEＲLIＮK＼ｌ＿Toc148８9二、数据结构ＰAＧEREF_Toc1４889２
HＹＰERLINＫ＼l_Toc1953０１.数据结构设计考虑PAＧEREF＿Toｃ195302
HYPERLＩNＫ＼l_Toｃ48602.逻辑结构存储结构PAＧEＲＥF_Toc48602
HＹPEＲLINK＼ｌ＿Toc3４12三、算法设计ＰAGＥRＥＦ_Toｃ34１23
HYＰERLINK\l_Tｏc8688四、调试分析PAＧEＲEF＿Tｏc８688７
ＨYPERLINK\ｌ_Toc195５４五、程序实现及测试ＰＡGERＥＦ＿Tｏｃ19５548
ＨYＰERLIＮK\l＿Tｏc31400六、体会及不足之处PAGEREF_Ｔｏｃ3140０9
HYＰERＬINK\l_Tｏc296２１七、参考文献PＡGEＲEF_Toc2９6２１10
HYPERLINK\l＿Toc5860八、源代码PAGEREF_Ｔｏc5８6010


一、需求分析
本课程设计是解决迷宫求解的问题,从入口出发，顺某一方向向前探索，若能走通,则继续往前走；否则沿原路退回,换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回,显然需要用一个后进先出的结构来保存从入口到当前位置的路径.因此,在求迷宫通路的算法中要应用“栈”的思想假设“当前位置"指的是“在搜索过程中的某一时刻所在图中某个方块位置"，则求迷宫中一条路径的算法的基本思想是:若当前位置“可通”,则纳入“当前路径",并继续朝“下一位置"探索,即切换“下一位置”为“当前位置”,如此重复直至到达出口；若当前位置“不可通＂,则应顺着“来向”退回到“前一通道块”，然后朝着除“来向”之外的其他方向继续探索;若该通道块的四周４个方块均“不可通",则应从“当前路径”上删除该通道块。所谓“下一位置”指的是当前位置四周4个方向（上、下、左、右)上相邻的方块。假设以栈记录“当前路径”,则栈顶中存放的是“当前路径上最后一个通道块”。由此,“纳入路径”的操作即为“当前位置入栈＂；“从当前路径上删除前一通道块"的操作即为“出栈”。
二、数据结构
1。数据结构设计考虑
1）建立一个二维数组表示迷宫的路径（0表示通道,1表示墙壁）；
2）创建一个栈,用来存储“当前路径”，即“在搜索过程中某一时刻所在图中某个方块位置”.
2。逻辑结构存储结构
1）创建一个Int类型的二维数组intmazｅ［n1]［n2］,用来存放0和1(0表示通道,1表示墙壁)；
２）创建一个结构体用来储存数组信息结构体:
typeｄefｓtruｃｔ//迷宫内部设置
{
intｓｈu［16]［１6]；
intｒow;
intcol；
}Ｍaｚe;
创造一个链栈
stｒuctｎode
{
ｉntrow;
inｔcol;
ｓtruｃｔnｏｄe＊ｎext；
｝；
三、算法设计
首先,创建数组的大小,此数组大小要求用户自己输入。具体算法：
printf(”输入迷宫的形状!\ｎ”）；
scanｆ("%d%d",&ｘ,&y);
Mａｚem;
CｒｅaｔIｎiｔ(＆m,x,y）;
函数：
vｏｉdCｒeaｔIｎit(Maze*m，intx，inｔｙ）／／创建迷宫
{

ｐｒiｎtf("pｌeaseinｐｕtnumｂｅr：\ｎ”）；
inｔi,j;
for(ｉ＝０;i〈=x；ｉ+＋)
｛
ｆoｒ(ｊ=０；j<=y;j++)
ｍ—〉shｕ[i][j]＝２；
}
foｒ(ｉ=１；ｉ〈＝x;i++)
for(j＝1;ｊ〈＝y；j＋+）
ｓcanf(＂%ｄ＂,&m-〉shu[i］[j］);
ｍ-〉row=x;
m—〉coｌ＝ｙ;
}

其中的0和1分别是表示通路和障碍,定义的数组其实就是迷宫的设计图
其次,产生迷宫，算法:
for(i=1；i〈=x；i＋+）
｛
ｆｏｒ(j=１;j〈=y；ｊ++）
pｒinｔｆ（"％d\t"，ｍ．sｈｕ[i][j]);
ｐrintf(”\n”)；
}

最后,迷宫寻路,在寻路的时候，我们应从输入的入口位置进入迷宫，当迷宫的入口处有障碍或者出口被堵,再或者没有通路时整个程序结束，并输出迷宫无解的提示.如果迷宫求解过程中没有出现无解情况,那么在求解的过程中,会输出迷宫的通路路径，并且输