數(shù)據(jù)結(jié)構(gòu)理論3---順序表章節(jié)
今日總結(jié)
錯題總結(jié)
? ?在一個長度為n的順序表中刪除第i個元素（1<=i<=n）時，需要向前移動(? ?)個元素。在這個過程中，第i個元素后面有 n-i 個元素，前面有i-1個元素，所以我們需要移動n-i個元素。
存儲密度：在數(shù)據(jù)結(jié)構(gòu)中，結(jié)點數(shù)據(jù)本身所占的存儲量和整個結(jié)點結(jié)構(gòu)所占的存儲量之比。
存儲密度?=?結(jié)點數(shù)據(jù)本身所占存儲量?/?整個結(jié)點結(jié)構(gòu)所占的存儲量
順序表的存儲密度等于1
單鏈表的存儲密度小于1
假設單鏈表的結(jié)點的數(shù)據(jù)占的存儲量為N，結(jié)點的指針域所占的存儲量為M，則存儲密度?=?N?/?(N+M)，所以單鏈表的密度是小于1的。
順序表的插入，刪除和查找的時間復雜度都是O(N)。
順序表結(jié)點的存儲地址計算公式：
第i個數(shù)據(jù)元素的存儲位置：Loc(ai)=Loc(ai)+(i-1)*l；1≤i≤n（l為每個元素需占l個存儲單元）
第（i+1）個數(shù)據(jù)元素的存儲位置Loc(ai+1)和第i個數(shù)據(jù)元素的存儲位置Loc(ai)的關系：Loc(ai+1)=Loc(ai)+l;
順序存儲方式的優(yōu)點是存儲密度大,數(shù)據(jù)存儲在連續(xù)的內(nèi)存空間中,但是插入、刪除運算效率低。
標簽：
