線性表 :
是 n(n>=0) 個相同特性數(shù)據(jù)元素的有序序列 .
? 順序存儲結(jié)構(gòu)和實現(xiàn)
線性表的順序存儲結(jié)構(gòu) , 可以隨機存取 . 邏輯上相鄰的兩個元素 , 在物理存儲上也是相鄰的 . 順序存儲表示 :
( 見源代碼 ) 基本操作在順序表上的實現(xiàn)
( 見源代碼 )
四大基本操作 :
(1) ?? 構(gòu)造一個空的線性表
( 簡單 )
(2) ?? 順序表的插入算法 .
算法分析 :
時間主要耗費在移動元素上 , 與問題的規(guī)模 (N) 和你插入元素的具體位置有關(guān) , 即插入元素位置越靠近 , 位序 1, 消耗的時間也就越多 . 設(shè)在位序 i 插入元素的概率位 pi=1/(n+1), 移動元素的個數(shù)為 ,(n-i+1):
????? 那么在長度為 n 的順序表中 , 插入一個元素 , 所需移動元素的期望值為 :
????? E = ∑ P i*(n-i+1)???? (i=1,2,3,..,n+1)
????? ?=n/2;
平均移動表中的一半元素 . 時間復(fù)雜度 O( n )
(3) ?? 順序表的刪除算法 .
算法分析 :
同上 , E = ∑ q i*(n-i)???? (i=1,2,3,..,n+1) qi=1/n
????? ? =(n-1)/2;
時間復(fù)雜度為 O (n);
(4) ?? 定位算法 .
算法分析 :
基本操作是進行兩個元素之間的比較 , 假設(shè)存在該元素為 a i( 1 ≤ i ≤ n), 則比較的次數(shù)為 i, 否則為 n, 所以算法時間復(fù)雜度為 O(n); 順序存儲結(jié)構(gòu)的性能小結(jié) :
優(yōu)點 :
(1) ?? 可以隨機存取 , 順序表中的數(shù)據(jù)元素 .
(2) ?? 存儲空間連續(xù) , 不必要增加額外的存儲空間 . 比如如果你以鏈?zhǔn)浇Y(jié)構(gòu)存儲 , 那么你就不得不增加一個指針域 .
缺點 :
(1) 插入和刪除一個元素 , 需要移動大量元素 , 耗費時間 .
(2) 初始化順序表的時候 , 要預(yù)先分配一個最大空間 . 有時候會使存儲空間得不到充分利用 .
(3) 容量難以擴充 .