迷宫问题系统的设计和实现.doc

迷宫问题系统的设计和实现.doc迷宫问题的设计与实现

以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。本程序主要是对任意给定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。

:
迷宫中存在通路和障碍,为了方便迷宫的创建,可用0表示通路,用1表示障碍,这样迷宫就可以用0、1矩阵来描述。
:
迷宫是一个矩形区域,可以使用二维数组表示迷宫,这样迷宫的每一个位置都可以用其行列号来唯一指定,但是二维数组不能动态定义其大小,我们可以考虑先定义一个较大的二维数组maze[M+2][N+2],然后用它的前m行n列来存放元素,即可得到一个m×n的二维数组,这样(0,0)表示迷宫入口位置,(m-1,n-1)表示迷宫出口位置。
注:其中M,N分别表示迷宫最大行、列数,本程序M、N的缺省值为39、39,当然,用户也可根据需要,调整其大小。
:
首先从迷宫的入口开始,如果该位置就是迷宫出口,则已经找到了一条路径,搜索工作结束。否则搜索其上、下、左、右位置是否是障碍,若不是障碍,就移动到该位置,然后再从该位置开始搜索通往出口的路径;若是障碍就选择另一个相邻的位置,并从它开始搜索路径。为防止搜索重复出现,则将已搜索过的位置标记为2,同时保留搜索痕迹,在考虑进入下一个位置搜索之前,将当前位置保存在一个队列中,如果所有相邻的非障碍位置均被搜索过,且未找到通往出口的路径,则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法,如果找到路径,则为最短路径。

因为迷宫可行路径之间存在线性关系,并且需要在端点处进行增删操作,因此采用队列结构类型存储迷宫可行路径的信息。下面给出队列结构的ADT的定义。
队列结构的ADT的定义
ADT Queue{
数据对象:D={ai|ai∈ElemSet,t=1,2……,n, n>=0}
数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,……,n}
基本操作:
InitQueue(&Q)
操作结果:创建一个空队列Q
Destroy Queue (&Q)
初始条件:队列Q已存在
操作结果:队列Q被销毁
ClearQueue(&Q)
初始条件:队列Q已存在
操作结果:队列Q清为空栈
QueueEmpty(Q)
初始条件:队列Q已存在
操作结果:若队列Q为空栈,则返回TRUE,否则FALSE
QueueLength(Q)
初始条件:队列Q已存在
操作结果:返回Q的元素个数,即队列的长度
GetHead(Q,&e)
初始条件:队列Q已存在且非空
操作结果:用e返回Q的队头元素
EnQueue(&Q,e)
初始条件:队列Q已存在
操作结果:插入元素e为新的队尾元素
DeQueue(&Q,&e)
初始条件:队列Q已存在且非空
操作结果:删除Q的队头元素,并用e返回其值
QueueTraverse(Q,visit() )
初始条件:队列Q已存在且非空
操作结果:从队头到队尾依次对Q的每个数据元素调用函数visit()。一旦visit()失败,则操作失败。
}ADT Queue
系统功能模块设计
迷宫问题系统