貪吃蛇游戲在線性數(shù)據(jù)結(jié)構(gòu)中的案例教學(xué)

鄭 馨，江克勤，程玉勝

（安慶師范大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽安慶246133）

數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)課程體系中占據(jù)非常重要的地位，是程序設(shè)計(jì)、操作系統(tǒng)、數(shù)據(jù)庫(kù)管理系統(tǒng)、軟件工程、編譯原理、人工智能等后續(xù)課程的基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程是一門理論與實(shí)踐并重的綜合性很強(qiáng)的課程[1]，在教學(xué)上存在諸多難點(diǎn)。如果采用傳統(tǒng)的“課堂集中教學(xué)+機(jī)房實(shí)踐”的教學(xué)模式[2]，不但教師感到枯燥乏味，而且無(wú)法提高學(xué)生的積極性。將案例教學(xué)法[3]引入數(shù)據(jù)結(jié)構(gòu)課程中，選擇并設(shè)計(jì)趣味性強(qiáng)、難易適中、與生活緊密結(jié)合的案例，引導(dǎo)學(xué)生在具體情境中主動(dòng)思考、積極討論，可以明顯改善教學(xué)效果。在數(shù)據(jù)結(jié)構(gòu)中，線性表、棧和隊(duì)列等線性結(jié)構(gòu)[4]在內(nèi)容上緊密連接、環(huán)環(huán)相扣；同時(shí)，線性結(jié)構(gòu)又是學(xué)生在數(shù)據(jù)結(jié)構(gòu)中接觸到的第一類邏輯結(jié)構(gòu)，也是后續(xù)非線性結(jié)構(gòu)的基礎(chǔ)，理解并掌握線性結(jié)構(gòu)的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，對(duì)后續(xù)數(shù)據(jù)結(jié)構(gòu)和算法的學(xué)習(xí)具有非常重要的意義。如果能在線性結(jié)構(gòu)教學(xué)中調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣，那么后續(xù)的學(xué)習(xí)無(wú)疑將事半功倍。然而，在現(xiàn)有的案例教學(xué)中，通常采用對(duì)每一種數(shù)據(jù)結(jié)構(gòu)分別設(shè)計(jì)相應(yīng)的案例方式，并沒(méi)有充分考慮不同數(shù)據(jù)結(jié)構(gòu)之前的關(guān)聯(lián)，特別是線性結(jié)構(gòu)之間的緊密聯(lián)系。鑒于此，本文就數(shù)據(jù)結(jié)構(gòu)的線性結(jié)構(gòu)進(jìn)行深入研究，對(duì)該部分的案例教學(xué)模式進(jìn)行探索。

1 以貪吃蛇游戲設(shè)計(jì)為案例的教學(xué)實(shí)施過(guò)程

貪吃蛇是一款經(jīng)典的休閑益智類手游，玩家通過(guò)上下左右控制蛇頭的方向?qū)ふ译S機(jī)出現(xiàn)的食物不斷增加貪吃蛇的長(zhǎng)度。貪吃蛇存在唯一一個(gè)蛇頭和蛇尾，除蛇頭和蛇尾外，蛇身中每個(gè)節(jié)點(diǎn)均有且僅有一個(gè)前驅(qū)和后繼，因此，貪吃蛇其實(shí)就是一種典型的線性結(jié)構(gòu)。線性表和隊(duì)列這兩類線性結(jié)構(gòu)的順序存儲(chǔ)表示和鏈?zhǔn)酱鎯?chǔ)表示都可以作為貪吃蛇的結(jié)構(gòu)體，然而，每種數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)過(guò)程各不相同，算法效率也有明顯差異。如果能引導(dǎo)學(xué)生自己分析、討論并動(dòng)手實(shí)踐，最終完成貪吃蛇游戲設(shè)計(jì)，可以將枯燥的教學(xué)轉(zhuǎn)化為快樂(lè)的教與學(xué)過(guò)程；同時(shí)，以貪吃蛇游戲這條主線串聯(lián)順序表、單鏈表、循環(huán)隊(duì)列和鏈隊(duì)這些線性結(jié)構(gòu)，既跳出了章節(jié)的限制，又把握了線性結(jié)構(gòu)的主脈絡(luò)，還起到了及時(shí)復(fù)習(xí)鞏固作用；同時(shí)，提倡一題多解，鼓勵(lì)學(xué)生自主學(xué)習(xí)，開(kāi)拓學(xué)生創(chuàng)新思維。

本文設(shè)計(jì)的案例涉及順序表、單鏈表、循環(huán)隊(duì)列和鏈隊(duì)列這4種線性結(jié)構(gòu)。在具體的教學(xué)實(shí)施過(guò)程中，采用由淺入深、與教材章節(jié)同步的方式，通過(guò)數(shù)據(jù)結(jié)構(gòu)知識(shí)講解、貪吃蛇關(guān)鍵算法實(shí)現(xiàn)、代碼解析、算法性能比較分析等步驟對(duì)該教學(xué)方式予以實(shí)施，如圖1所示。

圖1 以貪吃蛇游戲設(shè)計(jì)為案例的教學(xué)實(shí)施流程

為了實(shí)現(xiàn)更佳的教學(xué)效果，將貪吃蛇游戲簡(jiǎn)化為貪吃蛇結(jié)構(gòu)體、蛇移動(dòng)操作和吃食物操作的實(shí)現(xiàn)，可以使學(xué)生忽略繁雜的界面設(shè)計(jì)等編程問(wèn)題，而專注于數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)。在講述每個(gè)線性結(jié)構(gòu)相關(guān)知識(shí)之前，先通過(guò)貪吃蛇游戲演示，讓學(xué)生從數(shù)據(jù)結(jié)構(gòu)的角度重新看待貪吃蛇問(wèn)題，引導(dǎo)學(xué)生思考貪吃蛇的結(jié)構(gòu)如何實(shí)現(xiàn)、貪吃蛇移動(dòng)的過(guò)程是怎樣的、貪吃蛇怎樣吃食物，讓學(xué)生帶著問(wèn)題學(xué)習(xí)線性結(jié)構(gòu)的結(jié)構(gòu)體定義與基本操作等相關(guān)知識(shí)。介紹完一個(gè)線性結(jié)構(gòu)后，立即啟發(fā)學(xué)生討論如何利用該數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)貪吃蛇的結(jié)構(gòu)體，以及如何實(shí)現(xiàn)貪吃蛇移動(dòng)的操作，并分析算法的時(shí)間復(fù)雜度，直至所有線性結(jié)構(gòu)都討論完畢后得到最佳的實(shí)現(xiàn)方案。

2 順序表實(shí)現(xiàn)貪吃蛇

順序表是采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表，利用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素，其物理地址也相鄰。由于貪吃蛇的每一個(gè)結(jié)點(diǎn)是連續(xù)的，每個(gè)結(jié)點(diǎn)可以視作一個(gè)數(shù)據(jù)元素，因此，利用順序表實(shí)現(xiàn)貪吃蛇是非常直觀的：蛇頭即表頭，蛇尾即表尾。由于貪吃蛇能夠在一個(gè)二維平面上移動(dòng)，因此這里的數(shù)據(jù)元素不再僅僅是一個(gè)整型或字符型，而必須包含每個(gè)結(jié)點(diǎn)的橫、縱軸坐標(biāo)。同時(shí)，順序表表示貪吃蛇移動(dòng)的過(guò)程，也與順序表插入運(yùn)算中的元素依次后移有異曲同工之妙。除了蛇頭結(jié)點(diǎn)移動(dòng)的位置是由上下左右4個(gè)方向鍵控制之外，從蛇頭之后的結(jié)點(diǎn)直至最后一個(gè)結(jié)點(diǎn)均依次移動(dòng)到它前一個(gè)結(jié)點(diǎn)的位置上。而順序表表示的貪吃蛇吃食物的過(guò)程，則與順序表在第一個(gè)位置插入元素的運(yùn)算完全相同。因此，順序表實(shí)現(xiàn)貪吃蛇時(shí)，移動(dòng)和吃食物的時(shí)間復(fù)雜度都是O(n)。

首先，通過(guò)動(dòng)畫可以快速啟發(fā)學(xué)生將貪吃蛇抽象為順序表，將貪吃蛇移動(dòng)和吃食物的動(dòng)作抽象為順序表的插入運(yùn)算。要求學(xué)生參照書中順序表的結(jié)構(gòu)體給出貪吃蛇的結(jié)構(gòu)體。鼓勵(lì)學(xué)生給出多種結(jié)構(gòu)體并進(jìn)行對(duì)比分析；令學(xué)生自行投票，選出最受歡迎、最簡(jiǎn)潔的結(jié)構(gòu)體表示。接著，讓學(xué)生自己分析得出蛇移動(dòng)和吃食物的關(guān)鍵步驟，將其與順序表插入運(yùn)算進(jìn)行對(duì)比以發(fā)現(xiàn)相似之處，再引導(dǎo)學(xué)生參照插入運(yùn)算仿寫出該段關(guān)鍵代碼。然后，結(jié)合順序表表示的貪吃蛇結(jié)構(gòu)體給出實(shí)現(xiàn)該步驟的示例代碼，并帶領(lǐng)學(xué)生一一解讀。解讀時(shí)，可以將該代碼與往屆學(xué)生寫出的代碼進(jìn)行形式上和內(nèi)容上的對(duì)比，既讓學(xué)生從模仿開(kāi)始養(yǎng)成良好的編程習(xí)慣，又使學(xué)生從工程上理解即使同一個(gè)算法的實(shí)現(xiàn)過(guò)程也有高效和低效之分。最后，讓學(xué)生得出移動(dòng)和吃食物算法的時(shí)間復(fù)雜度，再次說(shuō)明順序表在頻繁插入運(yùn)算中的劣勢(shì)。

3 單鏈表實(shí)現(xiàn)貪吃蛇

單鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。單鏈表的特點(diǎn)是用一組任意的存儲(chǔ)單元來(lái)存放線性表的結(jié)點(diǎn)，這組存儲(chǔ)單元可以是連續(xù)的，也可以是非連續(xù)的。因此，單鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。順序表需預(yù)先分配好足夠大的連續(xù)存儲(chǔ)空間，即靜態(tài)分配；而單鏈表支持動(dòng)態(tài)分配，即在需要新的結(jié)點(diǎn)時(shí)再分配空間，因而更靈活。

單鏈表表示的貪吃蛇結(jié)點(diǎn)包括兩個(gè)域：數(shù)據(jù)域用來(lái)存儲(chǔ)結(jié)點(diǎn)的橫、縱軸坐標(biāo)，指針域用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接后繼結(jié)點(diǎn)的位置。單鏈表表示的貪吃蛇正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒇澇陨呱砩系膎個(gè)結(jié)點(diǎn)按其邏輯順序鏈接在一起的。用單鏈表實(shí)現(xiàn)貪吃蛇移動(dòng)的關(guān)鍵在于完成前驅(qū)結(jié)點(diǎn)與當(dāng)前結(jié)點(diǎn)的坐標(biāo)傳遞，其余步驟與順序表實(shí)現(xiàn)貪吃蛇的過(guò)程一致，時(shí)間復(fù)雜度也是O(n)。單鏈表實(shí)現(xiàn)貪吃蛇吃食物的操作則比順序表簡(jiǎn)單得多，與單鏈表插入操作完全一致，時(shí)間復(fù)雜度僅為O(1)。

單鏈表實(shí)現(xiàn)貪吃蛇重在對(duì)比單鏈表和順序表的異同，幫助學(xué)生從結(jié)構(gòu)體到具體運(yùn)算步驟上理解二者的差異。首先，仍然通過(guò)動(dòng)畫啟發(fā)學(xué)生將貪吃蛇抽象為單鏈表，重點(diǎn)體現(xiàn)每個(gè)結(jié)點(diǎn)在內(nèi)存中的變化，讓學(xué)生更直觀地理解單鏈表結(jié)點(diǎn)，特別是指針的含義。然后，讓學(xué)生仿照書中單鏈表結(jié)點(diǎn)的類型定義，修改先前順序表表示的貪吃蛇的結(jié)構(gòu)體，進(jìn)而得到單鏈表表示的貪吃蛇結(jié)構(gòu)體。通過(guò)比較結(jié)構(gòu)體，再次闡述順序表和單鏈表的不同。接著，讓學(xué)生在先前順序表實(shí)現(xiàn)貪吃蛇移動(dòng)和吃食物的函數(shù)的基礎(chǔ)上，指出該移動(dòng)函數(shù)中需要修改的語(yǔ)句并嘗試修改，緊接著給出修改后的參考代碼。通過(guò)解讀關(guān)鍵代碼，從具體操作上深入對(duì)比線性表和單鏈表的異同。通過(guò)分析線性表和單鏈表實(shí)現(xiàn)貪吃蛇移動(dòng)算法的時(shí)間復(fù)雜度，從算法效率上將二者再次進(jìn)行對(duì)比。最后，再次演示動(dòng)畫，讓學(xué)生仔細(xì)觀察蛇移動(dòng)過(guò)程中實(shí)際變化的結(jié)點(diǎn)，既為后續(xù)線性結(jié)構(gòu)設(shè)置懸念，激發(fā)學(xué)習(xí)興趣，又可以鍛練學(xué)生的主動(dòng)思維能力。

4 循環(huán)隊(duì)列實(shí)現(xiàn)貪吃蛇

循環(huán)隊(duì)列是隊(duì)列的一種順序表示和實(shí)現(xiàn)方法。隊(duì)列是一種限定性的線性表，限定插入在隊(duì)尾進(jìn)行，刪除在隊(duì)頭進(jìn)行。隊(duì)列的操作具有先進(jìn)先出（Fist In Fist Out，F(xiàn)IFO）的特征。而貪吃蛇移動(dòng)的過(guò)程就是不斷將蛇尾結(jié)點(diǎn)移至蛇頭處，即蛇尾結(jié)點(diǎn)出隊(duì)，新蛇頭結(jié)點(diǎn)入隊(duì)。因此，實(shí)際上貪吃蛇僅有兩個(gè)結(jié)點(diǎn)的位置發(fā)生了變化，而并不需要移動(dòng)所有的結(jié)點(diǎn)。因此貪吃蛇就是典型的隊(duì)列結(jié)構(gòu)，只不過(guò)隊(duì)頭應(yīng)設(shè)置在蛇尾，而蛇頭實(shí)際上是隊(duì)尾。在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)頭到隊(duì)尾的元素。由于隊(duì)列中隊(duì)頭和隊(duì)尾的位置是可變的，因此需要設(shè)置隊(duì)頭和隊(duì)尾兩個(gè)指針。為了克服“假上溢”現(xiàn)象，可以將順序隊(duì)列的數(shù)組看成一個(gè)首尾相接的圓環(huán)，即循環(huán)隊(duì)列。用循環(huán)隊(duì)列實(shí)現(xiàn)貪吃蛇的移動(dòng)操作比順序表和單鏈表都要快捷，時(shí)間復(fù)雜度僅為O(1)。

首先，揭秘在單鏈表實(shí)現(xiàn)貪吃蛇時(shí)設(shè)置的懸念，通過(guò)再次演示動(dòng)畫，重在突出變化的結(jié)點(diǎn)，揭示貪吃蛇移動(dòng)的實(shí)質(zhì)就是蛇尾結(jié)點(diǎn)出隊(duì)、新蛇頭結(jié)點(diǎn)入隊(duì)的過(guò)程；用循環(huán)隊(duì)列實(shí)現(xiàn)貪吃蛇吃食物的操作，就是新蛇頭結(jié)點(diǎn)入隊(duì)的過(guò)程。接著，令學(xué)生參照書中循環(huán)隊(duì)列的結(jié)構(gòu)體和入隊(duì)、出隊(duì)算法，再次改寫貪吃蛇移動(dòng)和吃食物的函數(shù)。然后，給出示例代碼并解讀，重點(diǎn)放在突出隊(duì)尾指針和隊(duì)頭指針循環(huán)變化上。最后，通過(guò)分析時(shí)間復(fù)雜度，就貪吃蛇游戲設(shè)計(jì)問(wèn)題將循環(huán)隊(duì)列與順序表和單鏈表的優(yōu)劣進(jìn)行對(duì)比，反復(fù)強(qiáng)化不同線性結(jié)構(gòu)的相關(guān)算法在學(xué)生腦海中的印象。

5 鏈隊(duì)列實(shí)現(xiàn)貪吃蛇

鏈隊(duì)列是隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的簡(jiǎn)稱。從結(jié)構(gòu)性上考慮，通常將隊(duì)頭指針和隊(duì)尾指針?lè)庋b在一個(gè)結(jié)構(gòu)中。鏈隊(duì)列與循環(huán)隊(duì)列在邏輯結(jié)構(gòu)上同屬隊(duì)列，因此，在貪吃蛇移動(dòng)和吃食物的算法上幾乎相同，仍是蛇尾結(jié)點(diǎn)出隊(duì)、新蛇頭結(jié)點(diǎn)入隊(duì)的過(guò)程，其時(shí)間復(fù)雜度均為O(1)；鏈隊(duì)列與單鏈表在物理結(jié)構(gòu)上同屬鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因此，在貪吃蛇移動(dòng)和吃食物操作的具體代碼實(shí)現(xiàn)上十分相似，鏈隊(duì)列入隊(duì)和出隊(duì)操作的本質(zhì)仍然是單鏈表結(jié)點(diǎn)的插入和刪除操作。因此，該部分的講解重點(diǎn)放在與單鏈表實(shí)現(xiàn)貪吃蛇的對(duì)比上。

由于已經(jīng)實(shí)現(xiàn)了單鏈表和循環(huán)隊(duì)列實(shí)現(xiàn)貪吃蛇的過(guò)程，學(xué)生對(duì)線性結(jié)構(gòu)的相關(guān)知識(shí)也有了一定程度的掌握，因此，不妨將鏈隊(duì)列實(shí)現(xiàn)貪吃蛇的過(guò)程放在實(shí)驗(yàn)課上，讓學(xué)生通過(guò)自主學(xué)習(xí)予以實(shí)現(xiàn)。通過(guò)學(xué)生自行閱讀代碼、理解代碼、運(yùn)行結(jié)果、編寫代碼、調(diào)試代碼，反復(fù)進(jìn)行上述步驟，讓學(xué)生自己在編碼中找到樂(lè)趣，發(fā)現(xiàn)解決問(wèn)題的快樂(lè)。由于學(xué)生編程能力參差不齊，為了使所有學(xué)生都能專注于數(shù)據(jù)結(jié)構(gòu)中的關(guān)鍵操作，并盡可能在課堂的有限時(shí)間內(nèi)獲得最大的收獲，可以預(yù)先實(shí)現(xiàn)順序表、單鏈表和循環(huán)鏈表實(shí)現(xiàn)貪吃蛇的全部代碼供學(xué)生參考，僅預(yù)留鏈隊(duì)列的關(guān)鍵算法讓學(xué)生填充，讓學(xué)生體會(huì)到自己編寫代碼并成功解決實(shí)際問(wèn)題的樂(lè)趣，同時(shí)還可以方便教學(xué)檢查。

6 結(jié)束語(yǔ)

本案例教學(xué)實(shí)踐精心設(shè)計(jì)了貪吃蛇游戲作為案例導(dǎo)入，充分體現(xiàn)了線性數(shù)據(jù)結(jié)構(gòu)知識(shí)體系的完整性、連續(xù)性和繼承性。通過(guò)分別利用順序表、單鏈表、循環(huán)隊(duì)列和鏈隊(duì)列實(shí)現(xiàn)貪吃蛇的關(guān)鍵操作，以一根主線串聯(lián)多個(gè)章節(jié)，將不同章節(jié)的共同點(diǎn)凝練出來(lái)，跳出了章節(jié)劃分的限制。通過(guò)一題多解，啟發(fā)學(xué)生從不同角度、不同思路、利用不同數(shù)據(jù)結(jié)構(gòu)，解決同一個(gè)問(wèn)題，從而鍛煉學(xué)生的創(chuàng)造性思維。對(duì)同類邏輯結(jié)構(gòu)之間、同類存儲(chǔ)結(jié)構(gòu)之間反復(fù)對(duì)比，使學(xué)生可以深入理解與吃透每個(gè)章節(jié)的重要概念與重要算法。通過(guò)簡(jiǎn)化的貪吃蛇游戲，充分調(diào)動(dòng)學(xué)生的學(xué)習(xí)熱情。貪吃蛇是一款經(jīng)典的手游，既具有較強(qiáng)趣味性和啟發(fā)性，又為大多數(shù)學(xué)生所熟悉，以該游戲?yàn)槔芤鸸缠Q，從初接觸數(shù)據(jù)結(jié)構(gòu)開(kāi)始即產(chǎn)生好奇心及學(xué)習(xí)相關(guān)知識(shí)的欲望。在簡(jiǎn)化貪吃蛇實(shí)現(xiàn)過(guò)程后，通過(guò)設(shè)計(jì)代碼填空，既可以使學(xué)生消除畏難情緒，勇于動(dòng)手編程，又有利于抓住本質(zhì)，重點(diǎn)難點(diǎn)精講。合理使用多種現(xiàn)代化教學(xué)手段，將書中抽象枯燥的靜態(tài)文字轉(zhuǎn)化為形象生動(dòng)的動(dòng)畫效果，立體化、全方位將不同知識(shí)點(diǎn)直觀地展現(xiàn)給學(xué)生，幫助學(xué)生更好地理解并消化知識(shí)，從而提升教學(xué)效果。