数据结构小组课题——迷宫

《数据结构小组课题——迷宫》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构—迷宫求解迷宫问题最早出现在古希腊神话屮。据说，半人半兽的英雄西修斯在克里特的迷宫屮勇敢地杀死半人半牛的怪物，并循着绳索逃出迷宫。希腊史学家希罗多德曾探访过那里。他描述说，整个迷宫由12座帯顶院落构成，所有的院落都由通道连接，形成3000个独立的“室”。后来的参观者也说，一旦进入迷宫，如果没有向导，根本无望走出。历史上，人们认为迷宫具有魔力。后來，迷宫成为游戏。在如今计算机非常普及的情况下，迷宫又以游戏程序的形式呈现在我们日常使用的电脑上。解题思路解析：在迷宫问题屮，一个迷宫用二维数组maze[size][size]来存储，对当前

2、位置（探索过程中某一时亥U所在的位置）记为maze[curpos.row][curpos.line],如果maze[curpos.row][curpos」ine]=0贝9有通路，女U果maze[curpos.row][curpos」ine]=1贝!j无通路。从入口star出发，可沿四个方向前进。试探方向的变化N(i-1,j)w(i,j-1)芷置（i,j）E(i,j+1)S(i+1,j)0表示E、1W、3表示N。如果遇到“0”则可前进，遇“1”则受阻；按此规则求入口到某一确定出口表示S、2表示的一条路径。算法的基本思想是：从迷宫的入口出发，

3、进行判断，若当前位置可通（未走过的“0”），则将当前位置插入栈顶，然后判断此位置是否为出口位置，如果是则结束整个运算，若不是出口位置，改变当前位置到他的右临位置（即E方向）；否则如果当前位置不通,这时若栈不空且栈顶位置尚有其他位置未搜索，则设定新的当前位置为栈顶位置的下一邻块，若栈不空且栈顶位置四周不通，则删去栈顶位置，若栈不空，则重新测试新的栈顶位置,直到找到一个可通的邻块或栈空，如此重复判断，直到找到一条从入口到出口的一条路径或得到无路径的信息。—・需求分析问题描述：以一个size*size的长方阵表示迷宫，（）和1分别表示迷宫屮的通

4、路和障碍。设计一个程序，对任意设定输入的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。a、输入的形式和输入值的范围：以0,1输入表示迷宫，0为通路，1为障碍。向电脑输入由0和1组成的二维数组，数组的行号列号相同且都为size（1=

5、无通道时显示“找不到通路”。d、测试数据：由后面调试分析详细说明。概要设计1.数据结构的定义为实现输出迷宫路径需用到栈，下面定义栈的抽象数据类型：栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top），相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。假设栈S=（a1,a2,-,an）,则称a1为栈底元素，an为栈顶元素。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（ListInFirstOut）的线性表。（简称L・FO结构）ADTStack{数据对象:D=

6、{ai

7、aieElemSet,i=1n>=0}数据关系：R1={

8、ai-1,aieD,i=2,...,n,}约定an端为栈顶，端为栈底。在迷宫问题中，假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入可以走的路径”的操作即为“当前位置入栈”；“从当前路径上删除前一通道块"的操作即为'出栈覽2.程序模块（1）迷宫和栈的定义：typedefenum{ERROR,OK}Status;typedefstruct{introw;//row表示“行”号intline;//line表示“列”号JPo

9、sType;〃位置的元素类型typedefstruct{intord;〃该通道在路径上的“序号”PosTypeseat;〃通道块在迷宫中的“坐标位置”intdi;〃从此通道走向下以通道块的“方向”JSEIemType;〃栈的元素类型typedefstructSEIemType*base;SEIemType*top;intstacksize;JSqStack;(2)构造一个空栈S：〃在构造之前和销毁之后，base的值为NULL〃栈顶指针〃当前已分配的存储空间StatuslnitStack(SqStack&S){S.base=(SEIemTy

10、pe*)malloc(100*sizeof(SEIemType));if(!S.base)returnERROR;〃存储分配失败S.top=S.base;S.stacksize=100;ret