没有合适的资源？快使用搜索试试~ 我知道了~

首页数据结构课程设计——迷宫问题

数据结构课程设计——迷宫问题

数据结构

迷宫问题

附加代码

课程设计

5星 · 超过95%的资源需积分: 20 20 下载量 44 浏览量更新于2023-03-16 评论 3 收藏 400KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

17页

利用二维数组来表示迷宫,用1表示一堵墙,用0表示通路,为了不出界在迷宫的周围需添加一堵墙;先创建迷宫,然后给出要求通路的起点和终点,求出一条通路，通路在迷宫中以数字编号即1,2,3……给出，另外还给出了通路中各个点的坐标！

资源详情

资源评论

资源推荐

raw.doc

第一部分需求分析

第二部分详细设计

第三部分调试分析

第四部分用户手册

第五部分测试结果

第六部分附录

第七部分参考文献

raw.doc

一、需求分析

1、对于给定的一个迷宫，给出一个出口和入口，找一条从入口到

出口的通路，并把这条通路显示出来；如果没有找到这样的通路给

出没有这样通路的信息。

2、可以用一个 m×n 的长方阵表示迷宫，0 和 1 分别表示迷宫中

的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入

口到出口的通路，或得出没有通路的结论。

3 、编写一个求解迷宫的非递归程序。求得的通路以三元组

(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d 表示

走到下一坐标的方向。

4、由于迷宫是任意给定的，所以程序要能够对给定的迷宫生成对

应的矩阵表示，所以程序的输入包括了矩阵的行数、列数、迷宫内

墙的个数、迷宫内墙的坐标、所求的通路的入口坐标、出口坐标。

二、详细设计

1、计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺

着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路

退回，换一个方向继续探索，直至出口位置，求得一条通路。假如

所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通

路。

可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出

raw.doc

口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障

碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可

通。

2、如果在某个位置上四个方向都走不通的话，就退回到前一个位

置，换一个方向再试，如果这个位置已经没有方向可试了就再退一

步，如果所有已经走过的位置的四个方向都试探过了，一直退到起

始点都没有走通，那就说明这个迷宫根本不通。

3、所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路不

能重复走第二次"，它包括"曾经走过而没有走通的路"。

　　显然为了保证在任何位置上都能沿原路退回，需要用一个"后进

先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口

之后，栈中保存的正是一条从入口到出口的路径。

4、若当前位置“可通”，则纳入“当前路径”，并继续朝“下一位置”探

索；若当前位置“不可通”，则应顺着“来的方向”退回到“前一通道块”，

然后朝着除“来向”之外的其他方向继续探索；若该通道块的四周四个

方块均“不可通”，则应从“当前路径”上删除该通道块。

所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、

北）上相邻的方块。假设以栈 S 记录“当前路径”，则栈顶中存放的

是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前

位置入栈”；“从当前路径上删除前一通道块”的操作即为“出栈”。

5、找通路的程序的关键部分可以表示如下：

do{

raw.doc

若当前位置可通，

则{

　　将当前位置插入栈顶；　　　　　　// 纳入路径

　　若该位置是出口位置，则算法结束；

　　// 此时栈中存放的是一条从入口位置到出口位置的路径

　　否则切换当前位置的东邻方块为新的当前位置；

}

否则

{

　　若栈不空且栈顶位置尚有其他方向未被探索，

　则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下

一相邻块；

　若栈不空但栈顶位置的四周均不可通，

　则{ 删去栈顶位置；　　　　// 从路径中删去该通道块

　　　若栈不空，则重新测试新的栈顶位置，

　　直至找到一个可通的相邻块或出栈至栈空；

　　}

} while (栈不空)；

6、程序中用的数据结构解析：

① 程序中用了顺序栈保存当前找到的路径，当前位置不可通时，

可以出栈，退回到前一个位置再继续探索通路，栈的定义如下：

剩余16页未读，继续阅读

蟹蛛

2023-07-25

这份文件在描述算法原理时用词准确，避免了晦涩难懂的术语，非常适合初学者阅读。

unity迷宫数据结构

sky__blue

粉丝: 1
资源: 6

上传资源快速赚钱

我的内容管理收起

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

会员权益专享

数据结构课程设计——迷宫问题

评论5

会员权益专享

最新资源

数据结构课程设计——迷宫问题

评论5

迷宫--数据结构课程设计

数据结构C语言迷宫课程设计报告

数据结构课程设计-迷宫求解.docx

c语言迷宫问题数据结构课程设计

数据结构课程设计迷宫问题的心得体会

数据结构——迷宫问题用C++完整版

数据结构课程设计迷宫问题

数据结构迷宫求解问题课程设计

数据结构c语言版课程设计走迷宫

数据结构c语言迷宫求解问题课程设计

数据结构栈的应用迷宫求解课程设计

python数据结构课程设计实例游戏

数据结构迷宫游戏课程设计

python数据结构课程设计

数据结构课程设计-走迷宫游戏

迷宫求解数据结构课程设计

数据结构栈的应用迷宫问题

c语言数据结构迷宫问题

用栈解决迷宫问题的课程设计

unity迷宫数据结构

会员权益专享

最新资源