3. 線性表
3.1 線性表(List): 零個或多個數(shù)據(jù)元素的有限序列
3.2 線性表的定義
若將線性表記為(a1, ... ,ai-1, ai, ai+1, ... , an), 則表中 ai-1 領先于 ai, ai, 領先于 ai+1, 稱ai-1是ai的直接前驅元素, ai+1 是 ai 的直接后繼元素. 當 i=1, 2, ... , n-1 時, ai 有且僅有一個直接后繼, 當 i=2, 3 , ... , n 時, ai 有且僅有一個直接前綴.
線性元素的個數(shù) n (n>=0) 定義為線性表的長度, 當 n = 0 時, 稱為空表
3.5 順序存儲結構的插入與刪除
- 線性表的順序存儲結構, 在存, 讀 數(shù)據(jù)時, 時間復雜度是 O[1]
- 插入, 刪除時, 時間復雜度為 O[n]
線性表順序存儲結構的優(yōu)缺點
- 優(yōu)點:
- 無需為表示表中元素之間的邏輯關系而增加二外的存儲空間
- 可以快速的存取表中任一位置的元素
- 缺點:
- 插入和刪除操作需要移動大量的元素
- 當線性表長度變化較大時, 難以確定存儲空間的容量
- 造成存儲空間的 "碎片"
鏈表
3.6 線性表的鏈式存儲結構
鏈式結構中, 除了要存儲數(shù)據(jù)元素信息外, 還要存儲它的后繼元素地址
為了表示每個元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關系, 對數(shù)據(jù)元素ai來說, 除了存儲本身的信息之外, 還需存儲一個指示其直接后繼的信息(即直接后繼的存儲位置). 我們把存儲元素信息的域稱為數(shù)據(jù)域, 把存儲直接后繼位置的域稱為指針域. 指針域中存儲的信息稱為指針或者鏈. 這兩部分信息組成數(shù)據(jù)元素ai的存儲映像, 稱為節(jié)點(Node)
n 個節(jié)點(ai的存儲映像)鏈接成一個鏈表, 即 為線性表(a1,a2,...an)的鏈式結構, 因為此鏈表的每個節(jié)點中只包含有一個指針域, 所以叫做單鏈表.
鏈表中第一個節(jié)點的存儲位置叫做頭指針, 最后一個節(jié)點為空(NULL 或者 ^)
單鏈表的第一個節(jié)點前附加一個節(jié)點,稱為頭節(jié)點(不是必須的). 不存儲任何信息, 指向第一個節(jié)點.
3.7 單鏈表的讀取
工作指針后移, 一個一個順序讀取.
3.8 單鏈表的插入與刪除
插入與刪除的時間復雜度都是O[1], 對于插入和刪除數(shù)據(jù)越頻繁的操作, 單列表的效率優(yōu)勢就越是明顯
3.9 單鏈表的整表創(chuàng)建
- 頭插法:
- 尾插法:
3.10 單鏈表的整表刪除
將鏈表中的所有元素依次刪除
3.11 單鏈表結構與順便存儲結構優(yōu)缺點
存儲分配方式
- 順便存儲結構用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素
- 單鏈表采用鏈式存儲結構,用一組任意的存儲單元存放線性表的元素
時間性能
- 查找:
- 順序存儲o(1)
- 單鏈表o(n)
- 插入和刪除
- 順序存儲結構需要平均移動表上一般的元素 時間為o(n)
- 單鏈表在得到某位置的指針后, 插入和刪除時間僅為o(1)
空間性能
- 順序存儲結構需要預分配存儲空間, 分大了 浪費, 分小了, 容易發(fā)生上溢
- 單鏈表不需要分配存儲空間, 只要有就可以分配, 元素個數(shù)也不受限制
結論:
- 若線性表需要頻繁查找, 很少進行插入和刪除操作時, 宜采用順序存儲結構. 若需要頻繁插入和刪除時, 宜采用單鏈表結構
- 當線性表中的元素個數(shù)變化較大或者根本不知道有多大時, 最好用單鏈表結構. 這樣可以不需要考慮存儲空間的大小問題. 而如果實現(xiàn)知道線性表的大致長度,如一年12個月, 一周就是星期一至星期天共七天, 用順序存儲結構效率會高很多
3.12 靜態(tài)鏈表
優(yōu)點: 在插入和刪除操作時, 只需要修改游標, 不需要移動元素, 從而改進了在順序存儲結構中的插入和刪除操作需要移動大量元素的缺點
缺點: 沒有解決連續(xù)存儲分配帶來的表長難以確定的問題
失去了順序存儲結構隨機存取的特性
3.13 循環(huán)鏈表
將單鏈表中終端節(jié)點的指針端由空指針改為指向頭節(jié)點, 就使整個單鏈表形成一個環(huán), 這種頭尾相接的單鏈表稱為單循環(huán)鏈表, 簡稱循環(huán)鏈表(circular linked list)
3.14 雙向鏈表
雙向列表插入, 要先完善插入元素的 next 和 prior 指向, 再完善其他的
3.15 總結
- 線性表
- 順序存儲結構
- 鏈式存儲結構
- 單鏈表
- 靜態(tài)鏈表
- 循環(huán)鏈表
- 雙向鏈表
