李麗萍，教巍巍

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

一、鏈表的知識重點

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

二、引入鏈表知識的原因

案例1：在C語言中，有一個名為a的數(shù)組，數(shù)組元素個數(shù)5個，即a[5]。每個數(shù)組元素已經(jīng)賦值?，F(xiàn)在想刪除第一個數(shù)據(jù)，如何處理？

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

案例2：同樣有5個數(shù)組元素已經(jīng)賦值，現(xiàn)在想在第一個數(shù)組元素和第二個數(shù)組元素之間插入一個數(shù)據(jù)，如何處理？

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

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

三、鏈表知識引入的難點

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

四、鏈表知識引入策略

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

（一）理論支撐

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

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

（二）教學方法的提案

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

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

1.戶外郊游要求

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

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

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

2.鏈表與戶外郊游的對應(yīng)關(guān)系。看下面的程序

程序中定義了一個結(jié)構(gòu)體類型，其中包括兩個成員，一個是用來存放數(shù)據(jù)的變量，另一個是與正在定義的結(jié)構(gòu)體類型相同的指針變量。

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

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

圖1 鏈表

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

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

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

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

五、鏈表的插入操作

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

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

圖2 鏈表的插入操作

六、鏈表的刪除操作

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

假設(shè)想刪除b 結(jié)點，如何操作呢？

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

圖3 鏈表的刪除操作

七、教學總結(jié)

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