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

《数据结构课程设计――迷宫问题课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、迷宫问题——王欣歆20080564一.需求设计：以一个m*m的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口的通道，或得出没有通路的结论。二.概要设计：存储结构：采用了数组以及结构体来存储数据，在探索迷宫的过程屮用到的栈，属于顺序存储结构。/*八个方向的数组表示形式*/intmove[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,1}}；/*用结构体表示位置*/structposition{intx,y;};positionstac

2、k[m*m+l];基本算法：走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西南、两、西北、北、东北8个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果8个方向都走不通或曾经到达过，则退回一步，在原來的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了山口处，则说明找到了一条通路：若退冋到了入口处，则说明不存在通路。用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出U点在位

3、置（mzm）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的边界；第1行第1列元素和第m行第m列元素置成“0”，表示迷宫的入口和出口；其余元素值用随机函数产生。假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有8个。如果用二维数组move记录8个方向上行T标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位貫坐标可利用move数组确定：x=x+move[i][0]y=y+move[i][l]7:来83k2从迷宫的入

4、口位置开始，沿图示方向顺序依次进行搜索。在搜索过程中，每前进一步，在所到位置处做标记“"（表示这个位置在通路上），并将该位置的坐标压入找屮。每次后退的时候，先将当前所在位罝处的通路标记“"改成死路标记“X”（表示这个位置曾到达过但走不通，以后不要重复进入），然后将该位置的坐标从栈顶弹出。搜索到出口位置时，数组屮那些伉为“"的元素形成一条通路。三.详细设计：源程序：/*迷宫问题走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西南、西、西北、北、东北个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一

5、步，在新位置上继续进行搜索；如果个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了出U处，则说明找到了一条通路；若退回到了入U处，则说明不存在通路。用一个字符类型的二维数组表示迷宫，数组屮每个元素取值''0〃（表示通路）或''1〃（表示墙壁）。迷宫的入口点在位賈（1,1）处，出口点在位賈（m,m）处。这个算法，为其寻找一条从入U点到出U点的通路。*/#include#include#include#include<

6、time•h>intmain（）{intm=l;while（m!=0）{printf（"输入m,使得为m*m的方阵迷宫（m〉0输入0时退出：）n）;scanf（"%d",&m）;/*设定n*n的方阵迷宫*//*数组的形式表示八个方向*/intmove[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};/*用结构体表示位置*/structposition{intx,y;}；/*用于记录和输出迷宫探路中相关符号，包括1.*/charmaze[m+2][m+2];

7、/*用栈来存储探路过程屮的数据*/positionstack[m*m+l];inttop;/*栈顶*/inti,x,y,ok;positionp;/*二维数组的第0行、第m+l行、第0列、第ni+l列元素全置成”1”，表示迷宮的边界；第1行第1列元素和第m行第m列元素置成”0”，表示迷宫的入口和出口；其余元素值用随机函数产生。*/srand(time(0));for(x=l;x<=m;x++)for(y=l;y<=m;y++)maze[x][y]=48+rand()%2;maze[1][1]=10';maze[m][m]=101;fo

8、r(x=0;x<=m+l;x++){maze[x][0]=’1’；maze[x][m+1]=111;}for(y=0;y<=m+l;y++){maze[0][y]=,11;maze[m+1][y]=111;}p.x=l;