鄭 馨，江克勤，程玉勝

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 鏈隊列實現(xiàn)貪吃蛇

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

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

6 結(jié)束語

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