---
# System prepended metadata

title: 【資結CH2陣列】陣列v.s.鏈結串列
tags: [資料結構]

---

## 【資結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
 

