数据结构课程设计——迷宫问题课程设计报告.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构课程设计——迷宫问题课程设计报告.pdf》由会员分享,可在线阅读,更多相关《数据结构课程设计——迷宫问题课程设计报告.pdf(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、迷宫问题王欣歆20080564 一需求设计:以一个 m*m 的方阵表示迷宫,0 和 1 分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口的通道,或得出没有通路的结论。二概要设计:存储结构:采用了数组以及结构体来存储数据,在探索迷宫的过程中用到的栈,属于顺序存储结构。/*八个方向的数组表示形式*/int move82=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;/*用结构体表示位置*/struct position int x,y;position stackm*m+1;基本算法:走迷宫的过程可以模拟为一个搜索的过程:每到一处,总让它按东
2、、东南、南、西南、西、西北、北、东北8 个方向顺序试探下一个位置;如果某方向可以通过,并且不曾到达,则前进一步,在新位置上继续进行搜索;如果 8 个方向都走不通或曾经到达过,则退回一步,在原来的位置上继续试探下一位置。每前进或后退一步,都要进行判断:若前进到了出口处,则说明找到了一条通路;若退回到了入口处,则说明不存在通路。用一个字符类型的二维数组表示迷宫,数组中每个元素取值“0”(表示通路)或“1”(表示墙壁)。迷宫的入口点在位置(1,1)处,出口点在位置(m,m)处。设计一个模拟走迷宫的算法,为其寻找一条从入口点到出口点的通路。二维数组的第0 行、第 m+1 行、第0 列、第 m+1 列元
3、素全置成“1”,表示迷宫的边界;第 1 行第 1 列元素和第m 行第 m 列元素置成“0”,表示迷宫的入口和出口;其余元素值用随机函数产生。假设当前所在位置是(x,y)。沿某个方向前进一步,它可能到达的位置最多有8 个。如果用二维数组move 记录 8 个方向上行下标增量和列下标增量,则沿第i 个方向前进一步,可能到达的新位置坐标可利用move 数组确定:x=x+movei0 y=y+movei1 从迷宫的入口位置开始,沿图示方向顺序依次进行搜索。在搜索过程中,每前进一步,在所到位置处做标记“(表示这个位置在通路上),并将该位置的坐标压入栈中。每次后退的时候,先将当前所在位置处的通路标记“改成
4、死路标记“”(表示这个位置曾到达过但走不通,以后不要重复进入),然后将该位置的坐标从栈顶弹出。67851432x y o 搜索到出口位置时,数组中那些值为“的元素形成一条通路。三详细设计:源程序:/*迷宫问题走迷宫的过程可以模拟为一个搜索的过程:每到一处,总让它按东、东南、南、西南、西、西北、北、东北个方向顺序试探下一个位置;如果某方向可以通过,并且不曾到达,则前进一步,在新位置上继续进行搜索;如果个方向都走不通或曾经到达过,则退回一步,在原来的位置上继续试探下一位置。每前进或后退一步,都要进行判断:若前进到了出口处,则说明找到了一条通路;若退回到了入口处,则说明不存在通路。用一个字符类型的二
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 迷宫 问题 报告
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内