算法

1.1 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

優(yōu)缺點(diǎn)

1. 順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（邏輯與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必須是連續(xù)的。

    優(yōu)點(diǎn)：存儲(chǔ)密度大（＝1），存儲(chǔ)空間利用率高
   
    缺點(diǎn)：插入或刪除元素時(shí)不方便
   

2. 鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針

    優(yōu)點(diǎn)：插入或刪除元素時(shí)很方便，使用靈活
   
    缺點(diǎn)：存儲(chǔ)密度?。?lt;1），存儲(chǔ)空間利用率低
   

場(chǎng)景

1. 順序表適宜于做查找這樣的靜態(tài)操作
2. 鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作
3. 若線(xiàn)性表的長(zhǎng)度變化不大，且其主要操作是查找，則采用順序表
4. 若線(xiàn)性表的長(zhǎng)度變化較大，且其主要操作是插入、刪除操作，則采用鏈表

順序表與鏈表的比較

• 基于空間的比較

  • 存儲(chǔ)分配的方式
    • 順序表的存儲(chǔ)空間是靜態(tài)分配的
    • 鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的
  • 存儲(chǔ)密度 = 結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量/結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量
    • 順序表的存儲(chǔ)密度 = 1
    • 鏈表的存儲(chǔ)密度 < 1

• 基于時(shí)間的比較

  • 存取方式
    • 順序表可以隨機(jī)存取，也可以順序存取
    • 鏈表是順序存取的
  • 插入/刪除時(shí)移動(dòng)元素個(gè)數(shù)
    • 順序表平均需要移動(dòng)近一半元素
    • 鏈表不需要移動(dòng)元素，只需要修改指針