摘要：鏈式存儲結(jié)構(gòu)是數(shù)據(jù)在計算機中的一種存儲方式，是數(shù)據(jù)結(jié)構(gòu)課程中重要的教學(xué)內(nèi)容。然而，掌握鏈式存儲結(jié)構(gòu)并靈活使用是不容易的。在分析平時教學(xué)中學(xué)生學(xué)習(xí)鏈式存儲結(jié)構(gòu)時常出現(xiàn)的問題的基礎(chǔ)上，分別在概念、特點、定義和操作四個方面探討了講授鏈式存儲結(jié)構(gòu)的方法和技巧。

　　關(guān)鍵詞：鏈式存儲結(jié)構(gòu);數(shù)據(jù)結(jié)構(gòu);存儲結(jié)構(gòu);教學(xué)方法

　　1 鏈式存儲結(jié)構(gòu)的概念

　　掌握鏈式存儲結(jié)構(gòu)的概念是學(xué)習(xí)各種不同數(shù)據(jù)結(jié)構(gòu)的鏈式表示和實現(xiàn)的前提。因此，教學(xué)中首先要讓學(xué)生明白什么是鏈式存儲結(jié)構(gòu)。相對于可使用數(shù)組實現(xiàn)的順序存儲結(jié)構(gòu)來說，學(xué)生在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前不僅對鏈式存儲結(jié)構(gòu)的概念是陌生的，而且大多對實現(xiàn)鏈式結(jié)構(gòu)的基礎(chǔ)知識如結(jié)構(gòu)體、指針等也不熟練。因此，在教學(xué)中深入淺出地將鏈式存儲結(jié)構(gòu)概念講解清楚很重要。講授時可按數(shù)據(jù)的結(jié)構(gòu)、存儲結(jié)構(gòu)再到鏈式存儲結(jié)構(gòu)的順序從外到內(nèi)逐層深入地方式講解，以幫助學(xué)生理解概念。

　　1.1 結(jié)構(gòu)結(jié)構(gòu)指數(shù)據(jù)元素之間的一種或多種關(guān)系，關(guān)系可能是線性的，也可能是非線性的。常見的基本結(jié)構(gòu)分為四類，分別是集合、線性表、樹和圖。當(dāng)然，通常所說的關(guān)系是指數(shù)據(jù)元素之間的邏輯關(guān)系即數(shù)據(jù)的邏輯結(jié)構(gòu)。簡單地理解，結(jié)構(gòu)就是關(guān)系。

　　1.2 存儲結(jié)構(gòu)為了在計算機中實現(xiàn)操作，除了分析數(shù)據(jù)元素之間的關(guān)系即得到數(shù)據(jù)的邏輯結(jié)構(gòu)外，還要考慮它們在計算機中如何存儲。數(shù)據(jù)元素和關(guān)系在計算機中的表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。簡單地理解，存儲結(jié)構(gòu)就是數(shù)據(jù)在計算機中的存儲方式。

　　1.3 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)是通過記錄元素的位置來表示元素與元素之間邏輯關(guān)系的一種存儲結(jié)構(gòu)。比如，在線性結(jié)構(gòu)中，若兩個邏輯上相鄰的數(shù)據(jù)元素在實際存儲時不相鄰，則可以通過將后一個元素所在的位置記錄到前一個元素來實現(xiàn)兩個數(shù)據(jù)元素之間的前后關(guān)系。若是非線性結(jié)構(gòu)，同樣可以通過記錄位置的方式實現(xiàn)兩個元素之間的非線性關(guān)系，比如雙親和孩子的關(guān)系、鄰接點關(guān)系等。其中，位置是存儲元素的地址即指針。在靜態(tài)鏈表中，位置是數(shù)組的下標。

　　2 鏈式存儲結(jié)構(gòu)的特點

　　數(shù)據(jù)結(jié)構(gòu)和算法是計算機科學(xué)和工程的基礎(chǔ)[1] ，任何一個算法的設(shè)計取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于數(shù)據(jù)的存儲結(jié)構(gòu)[2] 。因此，只有掌握了數(shù)據(jù)存儲結(jié)構(gòu)的特點，才能根據(jù)實際情況使用合適地存儲結(jié)構(gòu)來實現(xiàn)算法。作為一種非順序存儲結(jié)構(gòu)，鏈式結(jié)構(gòu)有著其自身的特點，掌握這些特點是靈活使用鏈式存儲結(jié)構(gòu)并充分發(fā)揮其優(yōu)點的基礎(chǔ)。授課時，可以通過比喻和類比等方式幫助學(xué)生掌握其優(yōu)缺點。

　　2.1 什么是鏈鏈式存儲結(jié)構(gòu)的特點體現(xiàn)在“鏈”字上。所謂“鏈”，可以想象為用一根繩將原本有一定關(guān)系的數(shù)據(jù)元素串起來，通過“鏈” 可以訪問與指定數(shù)據(jù)元素有關(guān)系的其它元素。舉個線性結(jié)構(gòu)的例子來說明如何鏈接，比如，同學(xué)A的后面是同學(xué)B，即A是 B前驅(qū)或者說B是A的后繼。排座位時，為了能體現(xiàn)出兩者的前后關(guān)系，若A坐在某個位置，則可以將B直接安排在A的后面，這樣A直接往后就可以找到后面的同學(xué)B了。當(dāng)然，也可以選擇另一種方式，即B不直接坐在A的后面，而是坐在任何一個空位上，只要將他所坐的位置告訴A，這樣A同樣可以找到 B了。這個例子里，兩個數(shù)據(jù)元素之間的先后關(guān)系不是在存儲時直接體現(xiàn)出來而是通過記錄位置完成的。可以想象，當(dāng)多個數(shù)據(jù)元素都按這種方式存儲時就類似用一個鏈串起了所有的元素，用這種方式存儲的線性表就稱為鏈表。當(dāng)然，“鏈”不僅可以表示線性關(guān)系，還可以將“鏈”進行擴展，根據(jù)需要實現(xiàn)如樹、圖等其它更復(fù)雜的關(guān)系的表示。

　　2.2 優(yōu)點鏈式存儲結(jié)構(gòu)借助地址來表示數(shù)據(jù)元素之間的關(guān)系，數(shù)據(jù)元素在存儲時是按非順序的方式存儲的，因此彌補了順序存儲結(jié)構(gòu)的不足。為使學(xué)生更清楚地了解鏈式存儲結(jié)構(gòu)的優(yōu)點，授課時可采用與順序存儲結(jié)構(gòu)相比較的方式從以下兩個方面來講解。第一，鏈式存儲結(jié)構(gòu)存儲元素時所需存儲單元是動態(tài)申請的，不必擔(dān)心操作過程中隨數(shù)據(jù)量變化而引起的存儲空間不足或浪費問題。在順序存儲結(jié)構(gòu)中，存儲空間由一組連續(xù)的存儲單元組成，因此，存儲容量受限。然而，鏈式存儲結(jié)構(gòu)采用需要存儲一個元素就動態(tài)申請一個存儲單元的方式，存儲單元可以是連續(xù)的，也可以是非連續(xù)的。第二，在插入和刪除操作時不需要移動數(shù)據(jù)元素，并且插入、刪除操作靈活。在鏈式存儲結(jié)構(gòu)中，由于數(shù)據(jù)元素之間的關(guān)系是借助地址來表示的，因此在進行插入、刪除操作時，只需要改變地址就可以實現(xiàn)數(shù)據(jù)元素之間關(guān)系的變化。相對于順序存儲結(jié)構(gòu)來說，不需要將待插入的數(shù)據(jù)元素位置空出，也不需要將刪除的數(shù)據(jù)元素位置補上。

　　3 鏈式存儲結(jié)構(gòu)的定義

　　在數(shù)據(jù)結(jié)構(gòu)中，常見的鏈式存儲結(jié)構(gòu)有單鏈表、循環(huán)鏈表、雙向鏈表、十字鏈表、二叉鏈表和鄰接表等，不同的鏈式存儲結(jié)構(gòu)可用來滿足不同的數(shù)據(jù)結(jié)構(gòu)的表示和實現(xiàn)。然而，無論哪一種數(shù)據(jù)結(jié)構(gòu)，若要使用鏈式存儲結(jié)構(gòu)，首先要完成它在計算機中的表示，即該鏈式存儲結(jié)構(gòu)所需的結(jié)構(gòu)體類型定義。通常，鏈式存儲結(jié)構(gòu)的結(jié)構(gòu)體類型包括兩部分：一是為存儲數(shù)據(jù)元素而封裝成結(jié)點的結(jié)點類型，二是描述該鏈式結(jié)構(gòu)的結(jié)構(gòu)類型。比如，在單鏈表中，為了實現(xiàn)將后一個數(shù)據(jù)元素的地址記錄到前一個數(shù)據(jù)元素中，需要將數(shù)據(jù)元素封裝成一個結(jié)點，這個結(jié)點存儲數(shù)據(jù)元素的值和其后繼元素所在的地址。因此，自定義一個結(jié)構(gòu)體類型即結(jié)點類型struct LNode，它包含兩個域，分別為數(shù)據(jù)域data和指向下一個結(jié)點的指針next。設(shè)數(shù)據(jù)元素類型為ElemType，則結(jié)點類型定義用C語言[3] 描述如下： struct LNode{ ElemType data; struct LNode *next; }; 這里的指針next在定義時采用了遞歸定義，由于指針指向的是結(jié)點，因此定義為結(jié)點類型struct LNode。另外，當(dāng)所有結(jié)點連接成一個鏈表后，這個鏈表就構(gòu)成了單鏈表，單鏈表也需要通過定義來描述其作為一個線性表所具有的特征，比如第一個數(shù)據(jù)元素的地址、數(shù)據(jù)元素個數(shù)等。顯然，若有一個指針L 指向鏈表的第一個結(jié)點(頭結(jié)點或首元結(jié)點)，則通過此指針就可以找到整個鏈表，類似于數(shù)組的首地址，這個指向鏈表的指針 L 稱為頭指針，頭指針指向的是結(jié)點，因此定義為 struct LNode類型。它的類型定義如下： struct LNode *L; 顯然，對于一個單鏈表來說，只要有了頭指針就可以找到鏈表并訪問所有元素。因此對整個鏈表而言，定義一個頭指針即可，其它屬性如數(shù)據(jù)元素個數(shù)可以通過計數(shù)操作來實現(xiàn)。學(xué)生在初始學(xué)習(xí)時很容易在定義指針類型上犯錯，不清楚指針究竟該定義成什么類型。其實，指針定義成什么類型完全取決于指針指向的對象類型。比如，單鏈表中指針next的類型是結(jié)點類型 struct LNode 而不是數(shù)據(jù)元素類型 ElemType，因為指針指向的是將數(shù)據(jù)元素封裝成包含數(shù)據(jù)域和指針域的結(jié)點而不是一個數(shù)據(jù)元素。

　　4 鏈式存儲結(jié)構(gòu)的操作

　　當(dāng)使用鏈式存儲結(jié)構(gòu)時，常常需要實現(xiàn)創(chuàng)建、插入、刪除、查找等操作。但是，無論哪種鏈式存儲結(jié)構(gòu)，其多數(shù)操作的實現(xiàn)主要還是單鏈表插入、刪除操作的延伸和擴展。因此只要熟練掌握鏈表的插入和刪除，就能實現(xiàn)其它更為復(fù)雜的操作。舉例說明，設(shè)q指向鏈表中的結(jié)點A，p指向待插入的結(jié)點B。若要將 B 插入到 A 之后，執(zhí)行 p→next=q→next 和 q→next=p 兩條語句即可。為了保證能正確地完成元素的插入，實現(xiàn)插入語句時需滿足“先連上，后斷開”的原則，即先使用p→next=q→next 將待插入的結(jié)點 B 連到鏈表中(結(jié)點 A 的后面)，然后再執(zhí)行 q→next=p，將A的后繼鏈從鏈表中斷開并連到B上。這兩條語句不能顛倒，若將兩條語句的順序顛倒，即先將A的指針指向 B，那么A后繼鏈就斷掉了，B就無法再連接到鏈表中。因此，插入操作中需要按“先連上，再斷開”的順序進行，只要記住了這個原則就可避免實現(xiàn)插入時出錯。當(dāng)實現(xiàn)鏈式存儲結(jié)構(gòu)的刪除操作時，執(zhí)行語句也很簡單。設(shè)p指向鏈表中的結(jié)點A，若要刪除A后面的結(jié)點B，執(zhí)行p→ next=p→next→next即可。但是，實際操作中，往往還需要將刪除結(jié)點的元素值帶回，因此多引入一個指針q，讓q先指向待刪除的結(jié)點B，即執(zhí)行q=p→next，然后再執(zhí)行p→next=q→next，將 B從鏈表中刪除。這樣，即使B已經(jīng)從鏈表中刪除，但是結(jié)點B 還是由q指向，因為B的地址存在q中，此時只要在釋放q之前把q→data賦值給某個變量就可以通過該變量繼續(xù)使用刪除的數(shù)據(jù)元素。因此，在刪除操作中，由被刪除的數(shù)據(jù)元素值是否還需要使用來決定刪除語句。如果不需要，執(zhí)行p→next=p→ next→next即可。但是，若還需要使用被刪除的元素值，則多引入一個輔助的指針 q，同時執(zhí)行 q=p→next 和 p→next=q→next 兩條語句。相對單鏈表來說，其它的鏈式存儲結(jié)構(gòu)可能在指針域或數(shù)據(jù)域擴充后有更為復(fù)雜的操作。然而，只要將最基本的單鏈表的插入和刪除操作掌握好，就可以在實現(xiàn)其它鏈式存儲結(jié)構(gòu)操作時輕松應(yīng)對。

　　5 結(jié)束語

　　在處理數(shù)據(jù)時，不僅要學(xué)會分析數(shù)據(jù)的邏輯結(jié)構(gòu)，還應(yīng)能使用合適的存儲結(jié)構(gòu)來高效地實現(xiàn)算法。在數(shù)據(jù)結(jié)構(gòu)中，盡管有多種不同的鏈式存儲結(jié)構(gòu)如單鏈表、雙鏈表、循環(huán)鏈表、二叉鏈表、鄰接表和十字鏈表等，但這些存儲結(jié)構(gòu)畢竟是有限的，不一定能滿足實際應(yīng)用的需求。因此，學(xué)習(xí)鏈式存儲結(jié)構(gòu)是學(xué)習(xí)借助地址表示數(shù)據(jù)元素之間關(guān)系的思維方法，即學(xué)習(xí)“鏈式”思維。當(dāng)用“鏈式”思維解決存儲問題時，即使沒有已有的鏈式存儲結(jié)構(gòu)可供使用，也能根據(jù)需要去自行設(shè)計。

　　參考文獻：

　　[1] 薩特吉,薩尼. [M]. 數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用 C++語言描述[M] 王立柱,劉志紅,譯.2版. 北京：機械工業(yè)出版社, 2015.

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

　　[3] 譚浩強. C 語言程序設(shè)計[M]. 2 版. 北京：清華大學(xué)出版社, 1999.

　　《數(shù)據(jù)結(jié)構(gòu)中鏈式存儲結(jié)構(gòu)的教學(xué)探討》來源：《電腦知識與技術(shù)》，作者：周張?zhí)m。