基于多维图形数据结构的连连看游戏程序设计方法探析

宋兰霞+潘承毅+周作梅+洪保+孟万堃

摘要：随着大数据时代的到来，人们越来越重视大数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法[1]。该文从多维图形数据结构的角度来讨论连连看游戏程序设计方法，数据结构清晰明了，用流程图描述的连线消除算法正确、可读、高效，促进了大数据结构发展，为数据结构教学改革指明方向。

关键词： 连连看；数据结构；连线消除

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）28-0065-02

Abstract：With the arrival of the big data era，people pay more and more attention to the big data structure，and think that the essence of programming is to design a good structure and a good algorithm to determine the problem.This paper from the multidimensional graphic data structure point of view to discuss the Lianliankan game programming method.The data structure is clear.It is described by the flow chart of the line elimination algorithm correct，readable and efficient.It promotes the development of large data structures.It provides direction for the teaching reform of data structure.

Key words：lianliankan；data structure； line elimination

數据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科，其发展并未终结；从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成程序设计方法学的主要内容；从20世纪70年代中期到80年代初，各个版本的数据结构著作相继出现，研究非数值计算问题必将成为大势所趋；目前，随着大数据时代的到来，人们越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法，面向游戏问题的数据结构也得到了研究和发展，如多维图形数据结构[1]。本文从多维图形数据结构的角度来讨论连连看游戏程序设计方法，数据结构清晰，用流程图描述的算法正确、可读、高效，促进了大数据结构的发展。

1 游戏玩法

玩家将两个花色相同的图片用不多于两个拐点的连接线连起来把两个图片消除；如果游戏地图上所有的图片都被消除则游戏胜利；如果在规定时间内游戏地图上的图片没有被消除完则游戏失败。

2 算法设计

算法是对特定问题求解步骤的一种描述2[1]，此游戏通过定义一个二维数组保存游戏地图中每张图片的编号和位置，根据三种连接方式实现两个位置是否可以连通，用图1所示流程图描述算法。

3 数据结构设计

相互之间存在多对多的关系、具有相同特性的数据元素的集合称为图形结构，即在图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关3[1]，由此，图的应用极为广泛，游戏地图就是一个图形结构，设地图大小为550像素×950像素，是一个11行×19列的矩阵，可分成209个小方块，每个小方块可存放一张大小为50像素×50像素的图片，本游戏地图至多可存放209张图片，其花色都有可能是相同的，因此是图形结构，由顶点集和边集构成。其中，每个顶点由三个域组成，分别保存游戏地图中的一个图片的行号、列号和编号值信息，定义的顶点结构vertex如下所示。

type struct vertex{int row；int col；int info；}vertex；

我们需要用图形结构来保存游戏数据，并且二维数组是最合适的数据结构。设游戏种类数为18，重复数为4，可使用二维数组表示法[1]来存储游戏数据（见图3），用0代表空格子，用1-18代表不同花色的方格，花色相同的方格用相同的编号表示，则连连看游戏就退化为如何从一个二维数组中找到可以消除的一对。

从图中某一顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次，这一过程就叫图的遍历4，通常有深度优先搜索和广度优先搜索两条遍历图的路径5[1]。从任意一个图片开始，用图的深度优先遍历或者广度优先遍历搜索方法，找到和这个图片配对的另一个图片，即可从二维数组中找到一对可以消除的方格（编号都为18）。消除这一对图片后（即置0），再从任意一个图片开始，用图的深度优先遍历或者广度优先遍历搜索方法，找到和这个图片配对的另一个图片，即可从二维数组中找到第二对可以消除的方格（编号都为15）。消除这一对图片后（即置0），再从任意一个图片开始，用图的深度优先遍历或者广度优先遍历搜索方法，找到和这个图片配对的另一个图片，即可从二维数组中找到第三对可以消除的方格（编号都为13）。消除这一对图片后（即置0），再从任意一个图片开始，用图的深度优先遍历或者广度优先遍历搜索方法，找到和这个图片配对的另一个图片，即可从二维数组中找到第四对可以消除的方格（编号都为18）。消除这一对图片后（即置0）对应的数组如图2所示，其对应的游戏地图如图3所示。以此递推。值得注意的是，由于消除两个图片时，连接线的拐点至多为两个，因此搜索消除对的编号时，最大深度不能超过3。

4 结论

连连看是一款益智小游戏，可实现对两个花色相同的图片用不大于两个拐点的连接线连在一起进行消除，连线算法可读，数据结构清晰，为数据结构教学改革提供借鉴[2]。

参考文献：

[1] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2007.

[2] 宋兰霞.《数据结构》教学方法探讨[J].电脑知识与技术，2013，9（14）：3338-3339，3348.endprint