順序表和鏈式表儲存結構研究

【摘要】資料結構是指相互之間存在著一種或多種關係的資料元素的集合和該集合中資料元素之間的關係組成。本文主要研究的是常用的資料結構線性表，線性表分為順序表和鏈式表。**了這兩種儲存結構的邏輯結構、物理結構、資料結構的運算及對比分析。

【關鍵詞】資料結構；線性表；順序表；鏈式表；儲存結構；運算

1 線性表的概述

線性表（linear list）是最簡單且最常用的一種資料結構。這種結構具有下列特點：存在乙個唯一的沒有前驅的（頭）資料元素；存在乙個唯一的沒有後繼的（尾）資料元素；此外，每乙個資料元素均有乙個直接前驅和乙個直接後繼資料元素。

1.1 線性表的邏輯結構

線性表是有限元素（a1，a2，a3，…，an）有序序列的集合，a1，a2，…，an 都是完全相同結構的資料型別，同時它們之間的排列嚴格有序，其中任何元素都對應唯一的前驅以及唯一的後繼。這樣乙個序列可以有查詢、刪除、插入佇列任何位置的資料操作。

1.2 線性表的物理結構

順序線性表是用一定大小的資料來存放線性表，陣列長度代表線性表的長度，元素在陣列的位置代表元素**性表的位置。但對陣列中元素不能跳躍插入，因為線性表中元素是順序且連線著的，不像陣列中間可以空元素。同時刪除元素時，必須大量移動剩下的元素，因為必須實現其連續性。

插入元素同樣需要大量移動資料。因此這樣儲存的執行效率並不夠高。所以對於有著頻繁插入和刪除運算的線性表，是不適合採用順序儲存的。

鏈式線性表是通過動態分配，分配物理上不一定相鄰的儲存單元。為表示他們的連續性連線性，再在分配這個儲存單元時，附加一部分儲存單元———指標域來指出這個元素的後繼元素的儲存位址。鏈式儲存結構又分為單鏈表、迴圈鍊錶和雙向鍊錶等。

這樣的鏈式儲存多節省了操作的時間，但需要更多的儲存空間。

2 順序線性表

2.1 順序表及其儲存結構

用一組位址連續的儲存單元依次存放線性表裡的資料元素。用這種方法儲存的線性表簡稱順序表。