基于多維圖形數(shù)據(jù)結(jié)構(gòu)的連連看游戲程序設(shè)計(jì)方法探析

宋蘭霞+潘承毅+周作梅+洪保+孟萬堃

摘要：隨著大數(shù)據(jù)時(shí)代的到來，人們越來越重視大數(shù)據(jù)結(jié)構(gòu)，認(rèn)為程序設(shè)計(jì)的實(shí)質(zhì)是對確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法[1]。該文從多維圖形數(shù)據(jù)結(jié)構(gòu)的角度來討論連連看游戲程序設(shè)計(jì)方法，數(shù)據(jù)結(jié)構(gòu)清晰明了，用流程圖描述的連線消除算法正確、可讀、高效，促進(jìn)了大數(shù)據(jù)結(jié)構(gòu)發(fā)展，為數(shù)據(jù)結(jié)構(gòu)教學(xué)改革指明方向。

關(guān)鍵詞： 連連看；數(shù)據(jù)結(jié)構(gòu)；連線消除

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：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

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及他們之間的關(guān)系和操作等的學(xué)科，其發(fā)展并未終結(jié)；從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成程序設(shè)計(jì)方法學(xué)的主要內(nèi)容；從20世紀(jì)70年代中期到80年代初，各個(gè)版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)，研究非數(shù)值計(jì)算問題必將成為大勢所趨；目前，隨著大數(shù)據(jù)時(shí)代的到來，人們越來越重視數(shù)據(jù)結(jié)構(gòu)，認(rèn)為程序設(shè)計(jì)的實(shí)質(zhì)是對確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法，面向游戲問題的數(shù)據(jù)結(jié)構(gòu)也得到了研究和發(fā)展，如多維圖形數(shù)據(jù)結(jié)構(gòu)[1]。本文從多維圖形數(shù)據(jù)結(jié)構(gòu)的角度來討論連連看游戲程序設(shè)計(jì)方法，數(shù)據(jù)結(jié)構(gòu)清晰，用流程圖描述的算法正確、可讀、高效，促進(jìn)了大數(shù)據(jù)結(jié)構(gòu)的發(fā)展。

1 游戲玩法

玩家將兩個(gè)花色相同的圖片用不多于兩個(gè)拐點(diǎn)的連接線連起來把兩個(gè)圖片消除；如果游戲地圖上所有的圖片都被消除則游戲勝利；如果在規(guī)定時(shí)間內(nèi)游戲地圖上的圖片沒有被消除完則游戲失敗。

2 算法設(shè)計(jì)

算法是對特定問題求解步驟的一種描述2[1]，此游戲通過定義一個(gè)二維數(shù)組保存游戲地圖中每張圖片的編號和位置，根據(jù)三種連接方式實(shí)現(xiàn)兩個(gè)位置是否可以連通，用圖1所示流程圖描述算法。

3 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

相互之間存在多對多的關(guān)系、具有相同特性的數(shù)據(jù)元素的集合稱為圖形結(jié)構(gòu)，即在圖形結(jié)構(gòu)中結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)3[1]，由此，圖的應(yīng)用極為廣泛，游戲地圖就是一個(gè)圖形結(jié)構(gòu)，設(shè)地圖大小為550像素×950像素，是一個(gè)11行×19列的矩陣，可分成209個(gè)小方塊，每個(gè)小方塊可存放一張大小為50像素×50像素的圖片，本游戲地圖至多可存放209張圖片，其花色都有可能是相同的，因此是圖形結(jié)構(gòu)，由頂點(diǎn)集和邊集構(gòu)成。其中，每個(gè)頂點(diǎn)由三個(gè)域組成，分別保存游戲地圖中的一個(gè)圖片的行號、列號和編號值信息，定義的頂點(diǎn)結(jié)構(gòu)vertex如下所示。

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

我們需要用圖形結(jié)構(gòu)來保存游戲數(shù)據(jù)，并且二維數(shù)組是最合適的數(shù)據(jù)結(jié)構(gòu)。設(shè)游戲種類數(shù)為18，重復(fù)數(shù)為4，可使用二維數(shù)組表示法[1]來存儲游戲數(shù)據(jù)（見圖3），用0代表空格子，用1-18代表不同花色的方格，花色相同的方格用相同的編號表示，則連連看游戲就退化為如何從一個(gè)二維數(shù)組中找到可以消除的一對。

從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問一次，這一過程就叫圖的遍歷4，通常有深度優(yōu)先搜索和廣度優(yōu)先搜索兩條遍歷圖的路徑5[1]。從任意一個(gè)圖片開始，用圖的深度優(yōu)先遍歷或者廣度優(yōu)先遍歷搜索方法，找到和這個(gè)圖片配對的另一個(gè)圖片，即可從二維數(shù)組中找到一對可以消除的方格（編號都為18）。消除這一對圖片后（即置0），再從任意一個(gè)圖片開始，用圖的深度優(yōu)先遍歷或者廣度優(yōu)先遍歷搜索方法，找到和這個(gè)圖片配對的另一個(gè)圖片，即可從二維數(shù)組中找到第二對可以消除的方格（編號都為15）。消除這一對圖片后（即置0），再從任意一個(gè)圖片開始，用圖的深度優(yōu)先遍歷或者廣度優(yōu)先遍歷搜索方法，找到和這個(gè)圖片配對的另一個(gè)圖片，即可從二維數(shù)組中找到第三對可以消除的方格（編號都為13）。消除這一對圖片后（即置0），再從任意一個(gè)圖片開始，用圖的深度優(yōu)先遍歷或者廣度優(yōu)先遍歷搜索方法，找到和這個(gè)圖片配對的另一個(gè)圖片，即可從二維數(shù)組中找到第四對可以消除的方格（編號都為18）。消除這一對圖片后（即置0）對應(yīng)的數(shù)組如圖2所示，其對應(yīng)的游戲地圖如圖3所示。以此遞推。值得注意的是，由于消除兩個(gè)圖片時(shí)，連接線的拐點(diǎn)至多為兩個(gè)，因此搜索消除對的編號時(shí)，最大深度不能超過3。

4 結(jié)論

連連看是一款益智小游戲，可實(shí)現(xiàn)對兩個(gè)花色相同的圖片用不大于兩個(gè)拐點(diǎn)的連接線連在一起進(jìn)行消除，連線算法可讀，數(shù)據(jù)結(jié)構(gòu)清晰，為數(shù)據(jù)結(jié)構(gòu)教學(xué)改革提供借鑒[2]。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2007.

[2] 宋蘭霞.《數(shù)據(jù)結(jié)構(gòu)》教學(xué)方法探討[J].電腦知識與技術(shù)，2013，9（14）：3338-3339，3348.endprint