迷宫问题-数据结构与算法课程设计报告

合肥学院

计算机科学与技术系

课程设计报告

2008 ～2009 学年第二学期

课程 数据结构与算法

课程设计名称 迷宫问题

学生名称 陈建华

专业班级 08计本（2）班

指导教师 王昆仑

2010年6月

一、问题分析和任务定义

1．题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，完成迷宫的组织与存储，并实现迷宫的路由算法。即对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论

2.设计要求：(1)N和M是用户可配置的，缺省值为50和50。(2)迷宫的入口和出口分别在左上角和右下角。(3)求得的通路以二元组( i , j )的形式输出，其中（i, j）指示迷宫中的一个坐标。(4) 以二维数组存储迷宫数据。

3.问题描述：迷宫是一个矩形区域如图（a）所示，它有一个入口和一个出口，其内部包含能穿越的强或障碍。迷宫老鼠问题就是要寻找一条从入口到出口的路径。

对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。（1，1）表示入口位置，（n,m）表示出口位置；从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。

为了描述迷宫中位置（i,j）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。这样，如图（a）所示的迷宫就可以用图（b）所示的矩阵来描述。其中，a11=0表示入口,anm=0表示出口；若aij表示从入口到出口路径上的某个位置，则应该有aij=0

经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。

0 1 1 1 1 1 0 0 0 0

0 0 0 0 0 1 0 1 0 0

0 0 0 1 0 1 0 0 0 0

0 1 0 1 0 1 0 1 1 0

0 1 0 1 0 1 0 1 0 0

0 1 1 1 0 1 0 1 0 1

0 1 0 0 0 1 0 1 0 1

0 1 0 1 1 1 0 1 0 0

1 0 0 0 0 0 0 1 0 0

0 0 0 0 0 1 1 1 0 0

(a) (b)

4.测试用例：

手动绘制迷宫正确的输入数据：

0 0 0 0 1 0

1 1 1 0 1 0

0 1 0 0 0 1

1 0 1 1 1 1

手动绘制迷宫正确的输出结果：随机绘制迷宫错误的输出结果：此迷宫没有通路！

注：用一个二维数组表示迷宫，数组中的每个元素表示一个小方格，0和1分别表示迷宫中的通路和障碍。用（i，j）的形式表示迷宫中各个位置的坐标。

二、数据结构的选择和概要设计

1.数据结构的选择

解决此问题需要运用到链栈的数据结构。因为求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。所以，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。

2.数据结构的定义

（1）栈的定义

栈（stack）是只能对一端的数据元素进行操作，即限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。

栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出（List In First Out）的线性表。

栈是满足下列条件的数据结构：

（1）有限个具有相同数据类型的数据元素的集合，D={ai|i=1,2,3,…,n}，ai为数据元素。

（2）数据元素之间的关系R={< ai ，ai +1>|ai ，ai +1∈D}。

（3）a1为栈底元素，an为栈顶元素；入栈时，数据元素按a1，a2，…，an，的次序进栈，出栈的第一个元素应为栈顶元素an。

用途：用来保存从迷宫入口到迷宫出口的路径。

（2）迷宫坐标的定义：

typedef struct node//链栈结构

{

int row; //行

int col; //列

struct node * next;

}mlink;

用途：该结构体用来存储迷宫中的行坐标和列坐标。

（3）迷宫最大行列数定义：

#define MaxX 50 //迷宫最大行数

#define MaxY 50 //迷宫最大列数

用途：用来定义迷宫的最大尺寸为50*50。

2.函数之间关系：

在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpath（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将辅助数组初始为1，辅助数组中点为路径的重新赋值为0，然后根据情况输出图形界面。在自动生成迷宫时，用到了c语言随机函数，对于其它问题，和手动情况基本相同。

（三）详细设计（流程图表示）

主要对框架和主要的函数表示一下：

1.程序结构图：

选择菜单 开 始

调用行数列数输入函数

选择1

显示函数调用

结 束

选择2

选择3

出入口函数调用

判断函数调用

路径显示函数调用 Y N

路径判断函数调用

2：判断路径函数流程图：

四．上机调试

1.调试过程中遇到的错误和问题

（1）在编译框中显示“‘time’undeclared identifier”即没有定义‘time’函数。

双击错误信息，根据编译软件的提示找到了错误信息行然后发现在程序的的开头没有输入“#include。加一个该函数，编译通过。

（2）在编译框中显示“nonstandard extension used：zero-sized array in struct/union”

和“class ‘maze’has an illegal zero-sized array”两行错误。双击错误信息，找到开 始

输入出口和入口

判断入口是否为1

入口进栈 Y

显示无出路 N

返回到菜单 向其中一个方向寻找

判断是否为1

Y

定点进栈 判断是否为出口

出错的程序段，经过查阅资料发现，在利用顺序栈时，没有定义顺序栈的向量空间大小，导致程序出错。但不要对向量空间定义过大，否则会浪费空间。

（3）在没有语法上的错误，运行时出现死循环，在方向判断上的算法有点错误，就是入口进栈时，在下一个点上没有通路时，就会出栈，如果出栈的话，就会使判断的函数的条件符合，就不能继续的往下寻找，这就是算法的错误，在确认以后就容易修改了，定义一个指针指向栈的下一个地址，这时栈在判断时不会出现上述的情况了。改正以后算法运行正常。

（4）在图形输出上，原本想用一个二维数组来存储数据，但在运行出现错误，这就需要另一个辅助数组了，先对辅助数组进行初始化为一，找到通路就将辅助数组的值赋为0。这一步在算法上没有了错误。

（5）在通路显示上不符合要求，这就出现在输出函数上了，检查时发现，循环条件i和j是从0开始的，所以辅助数组内的行数和列数都要减1，在改正以后程序运行正常，即能正常输出正确的路径。

（6）在执行程序时发现输出迷宫路径坐标出现了重复。经过对上面出现的错误信息的仔细分析，发现在访问迷宫的某一位置后，没有对访问过的位置的值置1。即需要在程序的正确位置加入“g[i][j]=1”这一程序段，加入之后，这一问题便迎刃而解。

3.算法的时间和空间性能分析

由于链栈实际上是运算受限制的单链表。所以取栈顶元素运算的算法、置空栈运算的算法执行时间与问题的规模无关，则该算法的时间复杂度为O(1)；而其入栈运算的算法与出栈运算的算法相当于在链表的表尾进行插入和删除操作，不需要移动元素，时间复杂度也为O（1）。建立迷宫矩阵的时间复杂度为O（x*y）。在查找路径的过程中，最坏的情况下可能要考察每一个非障碍的位置。因此，查找路径的时间复杂度应为O（unblocked）。

链栈的入栈算法、出栈算法、取栈顶元素算法、置空栈算法执行时所需要的空间都是用于存储算法本身所用的指令、常数、变量，各个算法的空间性能均较好。只是对于存放顺序栈的向量空间大小的定义很难把握好，如果定义过大，会造成不必要的空间浪费。所以在定义时要慎重考虑。

4.算法设计、调试的经验和体会

在进行程序设计时，要有良好的设计风格。即要有恰当的标识符即模块名、变量名、常量名、子程序名等。这些名字应能反映它所代表的实际东西，应有一定的实际意义，使其能够见名知意，这样有助于程序员和其他人对程序的理解。同时在编写程序时，要对每一个程序段加上注释，这样可以有助于程序员和其他人对程序的理解，以便能熟练的操作程序。还有在编写程序时要注意对程序的视觉组织，因为一个程序写得密密麻麻，分不出层次常常是很难看懂的。也使得程序的正确性大大降低。

在进行程序设计时，仅仅有良好的设计风格还是远远不够的。还需要程序员有过硬的基本功。比如：在编写程序时，应避免过多的循环嵌套和条件嵌套。应利用括号使逻辑表达式

和算术表达式的运算次序清晰直观。要使程序模块化应使模块功能尽可能单一化，模块间的耦合性能够清晰可见，等等。

所谓程序调试，是将编制的程序投入实际运行前，用手工或编译程序等方法进行测试，修正语法错误和逻辑错误的过程。这是保证计算机程序正确性的必不可少的步骤。编完计算机程序，必须送入计算机中测试。

程序调试分以下几步进行：

第一步：用编译程序把编制的源程序按照一定的书写格式送到计算机中，编译程序会根据使用人员的意图对源程序进行增、删或修改。

第二步：把送入的源程序翻译成机器语言，即用编译程序对源程序进行语法检查并将符合语法规则的源程序语句翻译成计算机能识别的“语言”。如果经编译程序的检查，发现有