09年自考《數據結構》各章要點一[3]

　　第二章 線性表

　　線性表是由n≥個數據元素組成的有限序列n=是空表;非空表只能有一個開始結點有且只能有一個終端結點

　　線性表上定義的基本運算

　　·構造空表Initlist(L)

　　·求表長Listlength(L)

　　·取結點GetNode(Li)

　　·查找LocateNode(Lx)

　　·插入InsertList(Lxi)

　　·刪除Delete(Li)

　　順序表是按線性表的邏輯結構次序依次存放在一組地址連續的存儲單元中在存儲單元中的各元素的物理位置和邏輯結構中各結點相鄰關系是一致的地址計算LOCa(i)=LOCa()+(i)*d;(首地址為)

　　在順序表中實現的基本運算

　　·插入平均移動結點次數為n/;平均時間復雜度均為O(n)

　　·刪除平均移動結點次數為(n)/;平均時間復雜度均為O(n)

　　線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同為了能正確表示結點間的邏輯關系在存儲每個結點值的同時還存儲了其後繼結點的地址信息(即指針或鏈)這兩部分信息組成鏈表中的結點結構 一個單鏈表由頭指針的名字來命名

[]  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/22843.html