資料結構之線性表

資料結構之線性表

什麼是線性表？

線性表是資料結構中最簡單的一種排序方式，在一個線性表中，除了首尾外，其他的資料元素都是首尾呼應的。

線性表的特點

• 存在唯一的表頭和表尾
• 除了表頭外，表中的每一個元素均隻有唯一的直接前驅
• 除了表尾外，表中的每一個元素均隻有唯一的直接後繼

線性表的存儲結構

順序存儲

是用一組位址連續存儲單元依次存儲線性表中的資料元素，進而使得邏輯關系相鄰的兩個元素在實體位置上也相鄰。

就比如說 課堂上的位置，1号座位的上面肯定是2号。

• 優點：讀取速度快
• 删除和添加速度慢

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

Loc(ai)=Loc(a1)+(i-1)*L
           

鍊式存儲

• 優點：删除、添加快
• 缺點：查詢速度慢

其他連結清單結構

1. 雙向連結清單：每個結點包含兩個指針，指明直接前驅和直接後繼元素，可在兩個方向上周遊連結清單。
2. 循環連結清單：表尾結點的指針指向表中的第一個結點，可在任何位置上開始周遊整個連結清單。
3. 靜态連結清單：借助數組來描述線性表的鍊式存儲結構。