邏輯結構上一個接一個的數據,在實際存儲時,並沒有像順序表那樣也相互緊挨著。恰恰相反,數據隨機分布在內存中的各個位置,這種存儲結構稱為線性表的鏈式存儲。
由於分散存儲,為了能夠體現出數據元素之間的邏輯關係,每個數據元素在存儲的同時,要配備一個指針,用於指向它的直接後繼元素,即每一個數據元素都指向下一個數據元素(最後一個指向NULL(空))。
如圖所示,當每一個數據元素都和它下一個數據元素用指針連結在一起時,就形成了一個鏈,這個鏈子的頭就位於第一個數據元素,這樣的存儲方式就是鏈式存儲。
線性表的鏈式存儲結構生成的表,稱作「鍊表」。
鍊表中數據元素的構成
每個元素本身由兩部分組成:
本身的信息,稱為「數據域」;指向直接後繼的指針,稱為「指針域」。這兩部分信息組成數據元素的存儲結構,稱之為「結點」。n個節點通過指針域相互連結,組成一個鍊表。
由於每個節點中只包含一個指針域,生成的鍊表又被稱為 線性鍊表 或 單鍊表。
鍊表中存放的不是基本數據類型,需要用結構體實現自定義:
typedefstructLink{char elem;//代表數據域structLink* next;//代表指針域,指向直接後繼元素}link;線性表的鏈式存儲相比於順序存儲,有兩大優勢:
鏈式存儲的數據元素在物理結構沒有限制,當內存空間中沒有足夠大的連續的內存空間供順序表使用時,可能使用鍊表能解決問題。(鍊表每次申請的都是單個數據元素的存儲空間,可以利用上一些內存碎片)鍊表中節點之間採用指針進行連結,當對鍊表中的數據元素實行插入或者刪除操作時,只需要改變指針的指向,無需像順序表那樣移動插入或刪除位置的後續元素,簡單快捷。鍊表和順序表相比,不足之處在於,當作遍歷操作時,由於鍊表中節點的物理位置不相鄰,使得計算機查找起來相比較順序表,速度要慢。
#未來計劃#