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

《迷宫问题-数据结构与算法课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2008～2009学年第二学期课程数据结构与算法课程设计名称迷宫问题学生名称陈建华专业班级08计本（2）班指导教师王昆仑2010年6月一、问题分析和任务定义1．题目：迷宫的生成与路由。生成一个N*M（N行M列）的迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，完成迷宫的组织与存储，并实现迷宫的路由算法。即对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论2.设计要求：(1)N和M是用户可配置的，缺省值为50和50。(2)迷宫的入口和出口分别在左上角和右下角。(3)求得的通路以二元组(i,

2、j)的形式输出，其中（i,j）指示迷宫中的一个坐标。(4)以二维数组存储迷宫数据。3.问题描述：迷宫是一个矩形区域如图（a）所示，它有一个入口和一个出口，其内部包含能穿越的强或障碍。迷宫老鼠问题就是要寻找一条从入口到出口的路径。对这样的矩形迷宫，可以用N*M的矩阵来描述，N和M分别代表迷宫的行数和列数。这样，迷宫中的每一个位置都可以用行号和列号来指定。（1，1）表示入口位置，（n,m）表示出口位置；从入口到出口的路径则是由一个位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居。为了描述迷宫中位置（i,j

3、）处有无障碍，规定：当位置（i,j）处有一个障碍时，其值为1，否则为0。这样，如图（a）所示的迷宫就可以用图（b）所示的矩阵来描述。其中，a11=0表示入口,anm=0表示出口；若aij表示从入口到出口路径上的某个位置，则应该有aij=0经分析，一个简单的求解方法是：从入口出发，沿某一方向进行探索，若能走通，则继续向前走；否则沿原路返回，换一方向再进行搜索，直到所有可能的通路都探索到为止。即所谓的回溯法。011111000000000101000001010000010101011001010101000111010101010001010101

4、0111010010000001000000011100(a)(b)4.测试用例：手动绘制迷宫正确的输入数据：000010111010010001101111手动绘制迷宫正确的输出结果：随机绘制迷宫错误的输出结果：此迷宫没有通路！注：用一个二维数组表示迷宫，数组中的每个元素表示一个小方格，0和1分别表示迷宫中的通路和障碍。用（i，j）的形式表示迷宫中各个位置的坐标。二、数据结构的选择和概要设计1.数据结构的选择解决此问题需要运用到链栈的数据结构。因为求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。由于计算机解迷宫时，通常用的是“穷举求解”

5、的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。所以，在求迷宫通路的算法中应用“栈”也就是自然而然的事了。2.数据结构的定义（1）栈的定义栈（stack）是只能对一端的数据元素进行操作，即限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有特殊含义，称为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。栈的修改是按后进先出的原

6、则进行的。因此，栈又称为后进先出（ListInFirstOut）的线性表。栈是满足下列条件的数据结构：（1）有限个具有相同数据类型的数据元素的集合，D={ai

7、i=1,2,3,…,n}，ai为数据元素。（2）数据元素之间的关系R={

8、ai，ai+1∈D}。（3）a1为栈底元素，an为栈顶元素；入栈时，数据元素按a1，a2，…，an，的次序进栈，出栈的第一个元素应为栈顶元素an。用途：用来保存从迷宫入口到迷宫出口的路径。（2）迷宫坐标的定义：typedefstructnode//链栈结构{introw;//行intcol;//列s

9、tructnode*next;}mlink;用途：该结构体用来存储迷宫中的行坐标和列坐标。（3）迷宫最大行列数定义：#defineMaxX50//迷宫最大行数#defineMaxY50//迷宫最大列数用途：用来定义迷宫的最大尺寸为50*50。2.函数之间关系：在该程序中，首先进入的是菜单选择，在菜单中有3种选择，选1是手动输入迷宫函数；选2是随机自动生成迷宫；选3是退出程序。在手动生成迷宫时，有两种输出方式，一是矩阵输出，二是图形输出。在矩阵输出时，直接将数组中的数进行输出，在图形输出时，则要判断该点的情况，然后输入迷宫的出入口，再调用mgpat

10、h（）函数进行判断是否存在路径，如果存在则将路径经过的点进行输出，并且将经过的点进入到辅助数组中（辅助数组是辅助图形界面的输出），并且将