数据结构课程设计 - 迷宫(2)

时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。而进行课程设计实践操作能够使我们更好地巩固课本知识，对课本知识有更深一步的了解，了解迷宫求解相关方面的知识，能小组合作完成较为简单的程序的设计并独立完成课程设计的论文，通过课程设计，达到增强巩固数据结构知识的目的，使知识更加全面化，系统化。

选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种看法导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。

数据结构课程设计是学习数据结构课程的一个重要的环节，能巩固和加深课堂教学中所学习到的内容，提高学生学习的实践和实际工作能力，为以后的学习奠定好的基础和学习态度及方法。通过课程设计，使学生加强团队合作的意识，并且能够综合运用课本知识来解决实际问题，加强分析问题、解决问题和动手的能力。

- 5 -

第2章 总体设计

2.1课题设计的总体思路

（1）

程序的设计，首先要考虑迷宫的表示，这是一个二维关系图，典型的存储方式是选择二维数组，数据元素的值只有两种状态，所以取值为0或1，其中0表示通路，1表示墙壁即此路不通，这里将二维数组取名为map，将最外面一圈设为墙壁，作为一个封闭图形，只留下入口点和出口点为通路。

（2）

图形的显示就可以根据数组元素的值来确定，如果是人工探索，则根据按键来确定探索物的位置坐标，利用循环语句即可实现；如果是人工探索，则根据按键来确定探索物的位置坐标，利用循环语句即可实现；如果是系统自动检索，并在8个方向检索，则问题相对复杂，采用递归的方法实现。

（3） 迷宫—作为线性结构的典型应用，大多数是用递归方法实现，用0代表通路，

1代表此路不通。本程序采用了一个美观逼真的迷宫图，而且是随机生成的，迷宫的大小为N*N，N预定义为常数，修改N的数值，可以改变迷宫的大小（只要不超过屏幕显示范围），用白色表示可走的路，蓝色表示此路不可以通过，并画出整个程序的流程图，让整个程序的设计思路一目了然。

（4） 若设定的迷宫存在通路，如果采用的是系统自动探索的运行方式，则会显示

出所走过的路径；如果采用的是人工探索方式，没有记录所走过的路径，只显示找的通路信息；

（5） 程序执行的命令为：生成迷宫、求解迷宫、输出迷宫的解。

- 6 -

2.2整个程序的流程图

开始预定义主函数MAIN()定义二维数组Map[n][n]清除clrscr输出字符串并初始化随机生成迷宫（Mandrand）判断字符串（if）手动搜索PeopleFind()输出结果Result()关闭图像close()结束

图2-1 整个程序的流程图

- 7 -

自动搜索FingWay()

2.3 课题设计界面

图2-2 人工探索通路图

系统运行首先出现提示字符串“please select hand（1）else auto”，询问是选择人工 探索还是系统自动探索，当用户出现字符1按回车键后出现一个迷宫图，红色矩形块（表示探索物）出现在左上角，这是可以按代表8个方向的字符选择通路，遇到墙壁不能通行，按回车键结束探索，如果这是探索物移动到右下角出口，则显示找到通路信息，否则显示没有找到通路信息，在提示信息后，如果输入的字符不是1 ，则系统自动查找通路，如果没有找到通路，则显示没有找到通路信息，如果找到通路，则用红色标记走过的路径

- 8 -

第3章 详细设计

3.1 main（）主函数

首先，确定是进行人工探索还是系统自动探索，通过输入字符来选定，选定之后调用图形初始化函数，紧接着调用迷宫生成函数及迷宫显示函数，然后根据输入的字符调用人工探索函数或自动探索函数。探索完毕进行处理，最后关闭图形系统，程序结束。

if(ch=='1')

PeopleFind(map);//人工搜索 else

FindWay(map,1,1);//系统自动从下标1,1的地方开始搜索

3.2 Init（）初始化函数

由于迷宫图是在图形方式显示的，所以要进行图形初始化工作。

3.3 MapRand（）迷宫生成函数

用数组map表示一个迷宫，要随机生成迷宫，数组元素的值利用随机函数生成0或1的数。将最外面一圈设为墙壁即不可通过，作为一个封闭图形，只留下入口点和出口点为通路。

for(i=0;i

for(j=0;j

if(i==0||i==N-1||j==0||j==N-1)//最外面一圈为墙壁 map[1][j]=1; else

if(i==1&&j==1||i==N-2||&&j==N-2)//出发点与终点表示为可走的 map[i][j]=0; else

map[i][j]=random(2);//其他的随机生成0或1 } }

3.4 PrMap（）迷宫显示函数

根据数组map的值输出迷宫图，利用函数setfillstyle（）设置图形实体填充样式，

- 9 -