??他心中三分傷感、三分留戀、又有三分寬慰，望著她的背影消失在黑暗之中，他知道殷離這一生，永遠會記著蝴蝶谷中那個一身狠勁的少年，她是要去找尋他，她自然找不到，但也可以說，她早已尋到了，因為那個少年早就藏在她的心底，張無忌心頭忽然涌起三句話來：“生死修短，豈能強求？予惡乎知悅生之非惑邪？予惡乎知惡死之非弱喪而不知歸者邪？予惡乎知夫死者不悔其始之蘄生乎？”
第二章 線性表
- 前言
- 定義和特點
- 型別定義
- 線性表的順序表示和實作
- 線性表的鏈式表示和實作
- 順序表和鏈表的比較
- 線性表的應用
- 總結
前言
??線性結構的基本特點是除第一個元素無直接前驅,最后一個元素無直接后繼之外,其他每個資料元素都有一個前驅和后繼,線性表是最基本最常用的一種線性結構,同時也是其他資料結構的基礎,尤其是單鏈表,是貫穿整個資料結構課程的基本技術,因此,接下來和博主一起走進線性表的邏輯結構,存盤結構,以及它的相關運算,將為大家梳理一下它的思維導圖,歡迎大家查漏補缺!
定義和特點
A.定義:
用資料元素的有限序串列示
（a1, a2, … ai-1，ai， ai＋1 ，…, an）
B.特點:
對于非空的線性表或線性結構
存在唯一的一個被稱作"第一個"的資料元素
存在唯一的一個被稱作"最后一個"的資料元素
除第一個之外,結構中每一個資料元素均只有一個前驅
除最后一個之外,結構中的每一個資料元素均只有一個后繼
型別定義
1).資料物件
2).資料關系
3).線性表的重要基本操作
1. 初始化
2. 取值
3. 查找
4. 插入
5. 洗掉
線性表的順序表示和實作
A.概念:
順序存盤定義
把邏輯上相鄰的資料元素存盤在物理上相鄰的存盤單元中的存盤結構
順序存盤方法
用一組地址連續的存盤單元依次存盤線性表的元素，可通過陣列V[n]來實作
B.特點:
（1）利用資料元素的存盤位置表示線性表中相鄰資料元素之間的前后關系，即線性表的邏輯結構與存盤結構一致
（2）在訪問線性表時，可以快速地計算出任何一個資料元素的存盤地址，因此可以粗略地認為，訪問每個元素所花時間相等
??線性表優缺點:
線性表的鏈式表示和實作
A.概念:
線性表的鏈式表示又稱為非順序映像或鏈式映像
B.特點:
（1）結點在存盤器中的位置是任意的，即邏輯上相鄰的資料元素在物理上不一定相鄰
（2）訪問時只能通過頭指標進入鏈表，并通過每個結點的指標域向后掃描其余結點，
所以尋找第一個結點和最后一個結點所花費的時間不等
??相關術語:
1.結點
資料元素的存盤映像，由資料域和指標域兩部分組成
2.鏈表
n 個結點由指標鏈組成一個鏈表，它是線性表的鏈式存盤映像，稱為線性表的鏈式存盤結構
3.單鏈表
結點只有一個指標域的鏈表，稱為單鏈表或線性鏈表
4.雙鏈表
有兩個指標域的鏈表，稱為雙鏈表
5.回圈鏈表
首尾相接的鏈表稱為回圈鏈表
6.頭指標
是指向鏈表中第一個結點的指標
7.首元結點
是指鏈表中存盤第一個資料元素a1的結點
7.頭結點
是在鏈表的首元結點之前附設的一個結點；資料域內只放空表標志和表長等資訊
??鏈表中設定頭結點作用:
????⒈便于首元結點的處理
????⒉便于空表和非空表的統一處理
??線性表的鏈式的優缺點:
??型別:
???? 單鏈表
???? 回圈鏈表
???? 雙向鏈表
順序表和鏈表的比較
A.空間性能的比較
1.存盤空間
順序表:
預先分配，會導致空間閑置或溢位現象
鏈表:
動態分配，不會出現存盤空間閑置或溢位現象
2.存盤密度
順序表:
不用為表示結點間的邏輯關系而增加額外的存盤開銷，存盤密度等于1
鏈表:
需要借助指標來體現元素間的邏輯關系，存盤密度小于1
B.時間性能的比較
1.存取元素
順序表:
隨機存取，按位置訪問元素的時間復雜度為O(1)
鏈表:
順序存取，按位置訪問元素時間復雜度為O(n)
2.插入、洗掉
順序表:
平均移動約表中一半元素，時間復雜度為O(n)
鏈表:
不需移動元素，確定插入、洗掉位置后，時間復雜度為O(1)
線性表的應用
A.線性表的合并
B.有序表的合并:
要求:
1.將這兩個有序鏈表合并成一個有序的單鏈表，
2.要求結果鏈表仍使用原來兩個鏈表的存盤空間, 不另外占用其它的存盤空間，
3.表中允許有重復的資料，
總結
??葵花寶典秘籍,掌握順序表和鏈式表的查找、插入和洗掉演算法、鏈表的創建演算法,并能夠設計出線性表應用的常用演算法,比如線性表的合并,能夠從時間復雜度與空間復雜度的角度比較兩種存盤結構的不同特點以及其適用場合,明確優缺點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/316637.html
標籤：其他