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