C 語言程序設計中鏈表的教學方法

李麗萍，教巍巍

(遼寧工業大學 電子與信息工程學院，遼寧 錦州 121001)

一、鏈表的知識重點

所謂鏈表，是指由同一類型的若干個結構體類型數據(每一個數據稱為一個“結點”)通過指向同一類型的結構體的指針變量，將分散在各個不連續存儲區域中的各個結點依次連接起來[1]。結點中的成員必須具備以下特點：其一，必須有數據項，即必須有對用戶有用的數據；其二，必須有指針域，即用來存放下一個結點地址的一個指針類型數據項。鏈表分為單向鏈表、雙向鏈表和循環鏈表，本文只介紹單向鏈表。單向鏈表要求：必須有一個存放第一結點地址的頭指針，通過頭指針能找到第一個結點；還要有若干個結點，每一個結點的其中一個成員必須是存放同一類型結構體結點的指針域，這樣可以通過指針域中的地址找到下一個結點。通過這種方式，實現多個結點首尾相連。

二、引入鏈表知識的原因

案例1：在C語言中，有一個名為a的數組，數組元素個數5個，即a[5]。每個數組元素已經賦值。現在想刪除第一個數據，如何處理？

常用的方法：從第二個數組元素值開始依次前移一個位置，即用后面數組元素的值覆蓋前面的數組元素的值。采用這樣的方法，5個數需要執行4次移動操作；那么有100個數組元素，則需要執行99次移動操作，這顯然不是一個好的解決問題的方法。

案例2：同樣有5個數組元素已經賦值，現在想在第一個數組元素和第二個數組元素之間插入一個數據，如何處理？

常用的方法：從第五個數組元素值開始依次后移一個位置，即將第5個數組元素值移動到第六個位置，依次后移，直到把第二個數組元素值移動到第三個位置為止，然后將要插入的數據放到第二個位置。采用這樣的方法，5個數，需要執行4次移動操作；那么有100個數組元素，則需要執行99次移動操作，這顯然也不是一個好的解決問題的方法。

為了解決大量數據插入或刪除的問題，用前面學過的知識處理太繁瑣，因此，引入了鏈表這個知識。鏈表在進行插入和刪除等一些操作中比數組更加便捷、高效，因此在實際應用中使用非常廣泛。

三、鏈表知識引入的難點

鏈表綜合了C語言中順序結構、選擇結構、循環結構、數組、指針、結構體等等諸多知識，與之前所學知識不同的地方是結構體變量包含多個成員，而想成功建立鏈表，要求其中的一個成員必須是指向正在定義的結構體類型的指針變量[2]，因此很多學習C語言的學生普遍反映鏈表很難學。

四、鏈表知識引入策略

通過對上述難點的分析，并反思日常教學中面對的學生理解知識困難的情況，將回歸教育心理學的本源與聯系C語言程序設計教學的特點相結合，對教學方法進行革新。

（一）理論支撐

1.當代建構主義學習觀。當代建構主義認為，學生的學習是在自身原有經驗基礎上的再建構。即教學并非知識的傳遞而是知識的處理和轉換，尤其強調學習的主動建構性、社會互動性和情境性。所以，在教學中應該積極將新的學習知識與學生自身狀況進行結合。這種結合一方面要關注學生已有的儲備知識，這種知識可以是專業理論上的，也可以是社會生活上的；另一方面，這種結合是一定要上升到學生的現實實踐中去的，這與當今實用型人才的培養動向也是高度一致的[3]。本文采用大家都熟悉的師生戶外郊游事例，講解靜態鏈表的建立、刪除和插入。將鏈表知識進行生活化描述、情境性講解，能夠幫助學生對知識的理解和掌握。

2.認知派學習理論。認知派的代表人物奧蘇貝爾認為，人的學習包含著一種認知結構的遷移。認知結構即學生頭腦中形成的知識結構，這種知識結構一部分是知識經驗，包括從前的學習和經驗；另一部分是指，經驗是有組織地存儲于頭腦中的。所以教學應該借助于先行組織者這一橋梁，通過引導性的材料來促進學生的理解。這種材料既要與學習任務關聯，又要與學生頭腦中已有的知識結構相關聯。只有這樣，才能實現知識的遷移，形成新知識。

（二）教學方法的提案

如何讓學生很容易地理解、掌握鏈表部分知識呢？可以通過師生戶外郊游的教學方法，讓學生透徹理解鏈表的真正含義。在講解單向鏈表的知識時引用案例，將鏈表結構進行生活化描述：

假設休息日李老師和4 名同學小紅、小明、小麗和小倩一起戶外郊游。老師不允許大家帶手機，除老師外的所有人必須帶食物。老師只會記住小紅的家庭住址，小紅只記住小明的家庭住址，小明只記住小麗的家庭住址，小麗只記住小倩的家庭住址。休息日，李老師先找到小紅同學，然后和她一起去找她記住地址的同學，依次類推……最后5 人一起出發。

1.戶外郊游要求

（1）教師最先出發，她只記住第一位學生的地址，不帶食物；

（2）第一位到第三位學生要記住一名學生的地址，還要帶食物；

（3）第四位學生只需帶食物，不用記住任何人的地址。

2.鏈表與戶外郊游的對應關系。看下面的程序

程序中定義了一個結構體類型，其中包括兩個成員，一個是用來存放數據的變量，另一個是與正在定義的結構體類型相同的指針變量。

在主函數中定義了一個指向結構體類型的指針變量head 和四個結構體類型的變量a,b,c,d。在鏈表中，每一個結構體變量稱為一個結點，指針變量head 中存放第一個結點的地址，稱為頭指針。

在這個程序中有a,b,c,d四個結點。每一個結點都有兩個成員，例如，a.num成員用來存放數據4，a.next成員用來存放b成員的地址。下面給出head頭指針和四個結點之間的相互關系的示意圖，也就是鏈表（圖1）。

圖1 鏈表

由圖1 可以驚奇地發現，指針變量head 和四個結點a,b,c,d 與一個教師和四名學生的對應關系非常相似！指針變量head 中只存放變量a的地址。同樣，教師只有小紅的家庭地址，沒有帶食物。

結點a,b,c，每一個變量都有兩個成員。一個成員用來存放有用的數據，另外一個成員用來存放下一個結點的地址。同樣，小紅、小明和小麗每個人都既需要帶食物，還要有另外一個同學的地址。

結點d，只需要給數據成員賦值即可，指針變量內容為空。同樣，小倩只需要帶食物即可，不需要記其他同學的地址。鏈表的執行方式也與師生郊游出行時的聯絡方式相似。通過頭指針head的內容可以找到結點a，由結點a的指針域a.next的內容可以找到結點b，以此類推。最后結點d的指針域d.next 值為空，鏈表斷開。同樣，老師手里有小紅的地址可以找到小紅，小紅手里有小明的地址可以找到小明，以此類推。最后小倩手里沒有任何人的地址，說明人已經全部集合完畢。

老師可以找到任意一名學生，同樣，從頭指針head 出發，可以找到任意一個結點。老師和學生們集合完畢，大手拉小手，可以愉快地去擁抱大自然了。現在我們也完成了單鏈表的建立。

五、鏈表的插入操作

假設小暉也想去郊游，他家住在小紅和小明之間的位置，那怎么更改行動計劃呢？

可以將小暉家的地址給小紅，小明家的地址給小暉，問題就解決了。假設想在結點a 和結點b 之間插入一個結點p，如何操作呢？同理，將結點p的地址&p 賦值給a.next，將結點b的地址&b 賦值給p.next。這樣就可以將結點p 插入到結點a 和b之間了，如圖2 所示。

圖2 鏈表的插入操作

六、鏈表的刪除操作

假設小麗家里有事不能去郊游了，怎么更改計劃呢？非常簡單，將小倩家的地址給小明，問題就解決了。

假設想刪除b 結點，如何操作呢？

同理，將結點c的地址&c 賦值給a.next。這樣就可以將結點b 從鏈表中刪除，如圖3 所示。

圖3 鏈表的刪除操作

七、教學總結

將鏈表知識進行生活化描述，將深奧的知識賦予了生活化的氣息，幫助學生理解和掌握。對于教育教學，不能只局限于書本知識，更要打破學生與書本之間的隔閡。教師是以學科知識的邏輯為出發點，站在理論的基礎上思考教學；而學生的學科知識儲備量較少，理論的應用也明顯不足，很難在理論知識的角度上進行融會貫通。因此，教師的作用就是打破教材理論與學生經驗之間的壁壘，更好地促進學生理解。本文中所探討的，對難點理論進行生活化描述的方法，也只是其中一種展示，相信以后一定會有更多的研究對本領域進行擴展。