## 【資結CH2陣列】陣列v.s.鏈結串列

### 陣列和鏈結串列比較

<br/>

| 項目 | 陣列 | 鏈結串列|
| ---------- | -------- | -------- |
| 佔用記憶體 | <font color="#0000FF">連續</font>記憶體 | 可以非連續 |
| 資料型態 | 需相同 | 各節點可以不同 |
| 插入修改刪除元素 | 麻煩 | 方便 |
| 動態增減空間 | 無法 | 可以 |
| 存取方式 | <font color="#0000FF">循序</font>存取 & <font color="#0000FF">隨機</font>存取 | 支援<font color="#0000FF">循序</font>存取 |
| 存取速度 | 快 | 慢 |

<br/>

### 陣列的位址

<br/>

**一維陣列的表示**

假設 $\alpha$ 表示陣列起始位置， W 表示每一個陣列元素所佔的空間
若陣列A宣告 A [ l1 ... u1 ] 則位址公式為
LOC( A [ i ] )= α + ( i - l1 ) W

<br/>

舉個例子
int A[3...7] ; α = 1000 ; Ｗ = 4 bytes
若要計算 A[5] 的位址
LOC(A[5])=1000+(5−3)⋅4=1000+2⋅4=1000+8= 1008

<br/>

**二維陣列的表示**

陣列A若宣告為 A [ l1..u1 , l2..u2 ] 令 a = u1 - l1 +1 ; b = u2 - l2 +1
則為位址公式為 LOC( A [ i , j ] ) = α + ( i - l1 ) bW +( j - l2 ) W

<br/>

舉個例子
int A [ 2..4 , 1..3 ] ; α = 1000 ; Ｗ = 4 bytes
若要計算 A [ 3,2 ] 的位址
LOC ( A [ 3,2 ] )= 1000 + ( 3 − 2 ) ⋅ 3 ⋅ 4 + ( 2 − 1 ) ⋅ 4
= 1000 + 1 ⋅ 12 + 1 ⋅ 4 = 1000 + 12 + 4 = 1016