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

　　關鍵詞：鏈式存儲結構;數據結構;存儲結構;教學方法

　　1 鏈式存儲結構的概念

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

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

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

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

　　2 鏈式存儲結構的特點

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

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

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

　　3 鏈式存儲結構的定義

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

　　4 鏈式存儲結構的操作

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

　　5 結束語

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

　　參考文獻：

　　[1] 薩特吉,薩尼. [M]. 數據結構、算法與應用 C++語言描述[M] 王立柱,劉志紅,譯.2版. 北京：機械工業出版社, 2015.

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

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

　　《數據結構中鏈式存儲結構的教學探討》來源：《電腦知識與技術》，作者：周張蘭。