一 線性表

1.線性表定義

線性表是n個元素的有限序列，通常記為(a1，a2，…，an)。
特點：

• 存在惟一的表頭和表尾。
• 除了表頭外，表中的每一個元素均只有惟一的直接前驅。
• 除了表尾外，表中的每一個元素均只有惟一的直接后繼。

2.線性表的存儲結構

(1)順序存儲

是用一組地址連續的存儲單元依次存儲線性表中的數據元素，從而使得邏輯關系相鄰的兩個元素在物理位置上也相鄰。

• 優點：可以隨機存取表中的元素

• 缺點：插入和刪除操作需要移動大量的元素。

在線性表的順序存儲結構中，第i個元素ai的存儲位置為：

LOC(ai)= LOC(a1)+(i-1)×L

其中LOC(a1)是表中第一個元素的存儲位置，L是表中每個元素所占空間的大小。

(2)鏈式存儲

鏈式存儲是指用結點來存儲數據元素，結點的空間可以是連續的，也可以是不連續的，因此存儲數據元素的同時必須存儲元素之間的邏輯關系。
結點空間只有在需要的時候才申請，無須