線性表的鍊式儲存結構

對於順序結構的缺點，我們有沒有什麼好的解法呢？

我們今天要介紹的線性表的鍊式儲存結構就可以很好的解決順序結構的缺點，一起來看。

鍊式儲存結構，又叫連結儲存結構。在電腦中用一組任意的儲存單元儲存線性表的資料元素(這組儲存單元可以是連續的,也可以是不連續的).

#基本介紹

它不要求邏輯上相鄰的元素在物理位置上也相鄰。因此它沒有順序存儲結構所具有的弱點,但也同時失去了順序表可隨機訪問的優點.

特點

1、比順序儲存結構的儲存密度小(鍊式儲存結構中每個結點都由資料域與指標域兩部分組成，相比順序存儲結構增加了存儲空間)。

2、邏輯上相鄰的節點物理上不必相鄰。

3、插入、刪除靈活 (不必移動節點，只要改變節點中的指標)。

4、查找節點時鍊式儲存要比順序儲存慢。

5、每個節點由資料域和指標域組成。

6、由於簇是隨機分配的，這也使資料刪除後覆蓋幾率降低，恢復可能會提高。

推薦課程：C語言教學。

線性表的最後一個元素是沒有直接後繼的，所以在鍊式儲存中，我們將最後一個結點的指標域設定為null.

下面我們來看單鍊錶的具體程式碼實現

typedef struct LNode{     
    ElemType data;          //数据域    
    struct LNode *next;     //指针域，用来指向本节点的直接后继
 }LNode,*LinkList;           //定义节点，以及头指针

 很多同學分不清頭指針，頭結點，以及第一個結點之間的關係和區別，我們下面簡單地區分下。

頭指標：是指向鍊錶的指針，如果鍊錶有頭結點，它會指向頭結點

頭結點：第一個結點之前的一個輔助結點，其next指向第一個結點

第一個結點：就是一個結點，data變數存放第一個數據，next指標變數指向第二個結點

#這裡要注意的就是頭指標是一個鍊錶的必要元素，而頭結點卻不是，那麼頭結點存在的意義是什麼呢？

個人的理解就是讓第一個結點的插入操作和刪除操作和後面結點的操作一致，否則我們在修改第一個結點的時候，就需要修改頭指標。

如果沒有頭結點，頭指標直接指向第一個結點。

以上是線性表的鍊式儲存結構的詳細內容。更多資訊請關注PHP中文網其他相關文章！