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

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

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

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

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

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

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

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

　　數(shù)據(jù)結(jié)構(gòu)和算法是計算機科學和工程的基礎[1] ，任何一個算法的設計取決于數(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)點的基礎。授課時，可以通過比喻和類比等方式幫助學生掌握其優(yōu)缺點。

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

　　2.2 優(yōu)點鏈式存儲結(jié)構(gòu)借助地址來表示數(shù)據(jù)元素之間的關系，數(shù)據(jù)元素在存儲時是按非順序的方式存儲的，因此彌補了順序存儲結(jié)構(gòu)的不足。為使學生更清楚地了解鏈式存儲結(jié)構(gòu)的優(yōu)點，授課時可采用與順序存儲結(jié)構(gòu)相比較的方式從以下兩個方面來講解。第一，鏈式存儲結(jié)構(gòu)存儲元素時所需存儲單元是動態(tài)申請的，不必擔心操作過程中隨數(shù)據(jù)量變化而引起的存儲空間不足或浪費問題。在順序存儲結(jié)構(gòu)中，存儲空間由一組連續(xù)的存儲單元組成，因此，存儲容量受限。然而，鏈式存儲結(jié)構(gòu)采用需要存儲一個元素就動態(tài)申請一個存儲單元的方式，存儲單元可以是連續(xù)的，也可以是非連續(xù)的。第二，在插入和刪除操作時不需要移動數(shù)據(jù)元素，并且插入、刪除操作靈活。在鏈式存儲結(jié)構(gòu)中，由于數(shù)據(jù)元素之間的關系是借助地址來表示的，因此在進行插入、刪除操作時，只需要改變地址就可以實現(xiàn)數(shù)據(jù)元素之間關系的變化。相對于順序存儲結(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ù)據(jù)元素類型為ElemType，則結(jié)點類型定義用C語言[3] 描述如下： struct LNode{ ElemType data; struct LNode *next; }; 這里的指針next在定義時采用了遞歸定義，由于指針指向的是結(jié)點，因此定義為結(jié)點類型struct LNode。另外，當所有結(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)。學生在初始學習時很容易在定義指針類型上犯錯，不清楚指針究竟該定義成什么類型。其實，指針定義成什么類型完全取決于指針指向的對象類型。比如，單鏈表中指針next的類型是結(jié)點類型 struct LNode 而不是數(shù)據(jù)元素類型 ElemType，因為指針指向的是將數(shù)據(jù)元素封裝成包含數(shù)據(jù)域和指針域的結(jié)點而不是一個數(shù)據(jù)元素。

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

　　當使用鏈式存儲結(jié)構(gòu)時，常常需要實現(xiàn)創(chuàng)建、插入、刪除、查找等操作。但是，無論哪種鏈式存儲結(jié)構(gòu)，其多數(shù)操作的實現(xiàn)主要還是單鏈表插入、刪除操作的延伸和擴展。因此只要熟練掌握鏈表的插入和刪除，就能實現(xiàn)其它更為復雜的操作。舉例說明，設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)插入時出錯。當實現(xiàn)鏈式存儲結(jié)構(gòu)的刪除操作時，執(zhí)行語句也很簡單。設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ù)域擴充后有更為復雜的操作。然而，只要將最基本的單鏈表的插入和刪除操作掌握好，就可以在實現(xiàn)其它鏈式存儲結(jié)構(gòu)操作時輕松應對。

　　5 結(jié)束語

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

　　參考文獻：

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

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

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

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