---
# System prepended metadata

title: "\U0001F4DD Chapter 2 陣列結構"
tags: [資料結構]

---

# 📝 Chapter 2 陣列結構

## 2-1 線性串列簡介
### 重點說明
線性串列是「資料有序排列」的集合。
每個元素只有一個前面、一個後面（頭尾除外）。
→ 目的在於表現串列中任兩個相鄰元素之間的關係。
- aᵢ₋₁ 是 aᵢ 的先行元素
- aᵢ₊₁ 是 aᵢ 的後繼元素

### 生活例子

像排隊：每個人都有固定的位置，前後關係明確。
英文字母：A,B,C,D...Z


### 儲存結構
**靜態資料結構**
- 特點：大小固定，在 **程式執行前(編譯時)** 就決定記憶體空間。
- 優點：存取快、結構簡單
- 缺點：彈性低，無法擴增或縮小、容易造成記憶體空間浪費
- 例子：陣列結構(Array)
```C#
int[] arr = new int[10]; // 陣列大小固定，不能增加元素
```

- 注意：有序串列(index)不等於儲存的資料內容是有序的 
![image](https://hackmd.io/_uploads/S1vGpi9ebl.png)


**動態資料結構**
- 特點：大小可變，可在 **程式執行時** 增加或刪減空間
- 優點：彈性大，適合資料量不固定的情況
- 缺點：存取速度可能比靜態慢，管理較複雜
- 例子：鏈結式結構

```C#
List<int> list = new List<int>(); // 可以隨時增加或刪除元素
list.Add(5);
list.RemoveAt(0);
```

![image](https://hackmd.io/_uploads/SyLjb39lZg.png)


### 討論題
👉 在生活中，你覺得哪些事情是「線性」的？為什麼？
👉 如果隊伍很常插隊或加人，順序表 vs 鏈結表哪個比較適合？
👉 你覺得「順序性」會帶來哪些優點？哪些限制？

----
## 2-2 認識陣列

### 重點說明
陣列是固定大小、連續記憶體空間的資料結構。
特性：
- O(1) 隨機存取（可直接用 index 找到元素）
- 大小固定，建立後不能動
- 插入刪除成本高，常伴隨移動資料

著重在 **資料的存放方式** 的描述

### 陣列五大屬性

|名稱|說明|用途|ㄧ維陣列例子|二維陣列例子|
|---|---|---|---|---|
|**起始位址 (Base Address)**|陣列在記憶體中的第一個元素的位置|計算其他元素的位址|假設是 `0x1000` |假設是 `0x2000`|
|**維度 (Dimension)**|陣列的維度，例如 1D、2D、3D|用於多維陣列的座標計算|1D|2D|
|**索引上下限 (Index Bounds)**|每個維度的最小與最大索引，例如 0~4|決定有效索引範圍|0 ~ 4|第 1 維 0~2，第 2 維 0~3|
|**陣列元素個數 (Number of Elements)**|陣列中實際存放的元素數量|例如 5 個元素|5|3 × 4 = 12|
|**陣列型態 (Element Type)**|每個元素的資料型態，例如 int、float|決定每個元素占多少 bytes|`int`（4 bytes）|`int`（4 bytes）|

```C#
int[] arr = new int[5] { 10, 20, 30, 40, 50 }; //一維陣列

int[,] matrix = new int[3, 4]; //二維陣列
``` 

- 五大屬性主要目的是 **讓 CPU 做「位址計算 (Address Calculation)」**
- 電腦記憶體位置通常以線性順序遞增，以程式語言又劃分成：
**以列為主** → C#、C++/C、Java、PASCAL
**以行為主** → Fortran

### 生活例子
像「冰箱的蛋盒」：12 格固定位置，每格都能快速找到，但如果想多放一個蛋就不行。

### 討論題
👉 什麼情況下你會選擇用「固定大小」的資料結構？
👉 陣列插入刪除為何慢？你會怎麼向完全不懂程式的人解釋？
👉 如果你在設計一個 App，需要常常搜尋但不常插入，你會不會選陣列？

---
### 陣列種類
#### 一維陣列：只有一個方向（線性排列）的資料結構。
**特性**
- 用一個索引存取：`arr[i]`
- 只需知道「起始位址」+「元素大小」即可計算位置。
![image](https://hackmd.io/_uploads/SkxRo2cg-g.png)

```C#
int[] arr = { 10, 20, 30, 40 };
```
    
#### 二維陣列：由「列 × 行」組成的表格。
**特性** 
- 用兩個索引：`matrix[row, col]`
- 資料在記憶體中仍然是線性的（以 Row-major 排列）。
- 位址計算要以「每列的欄數」來換算位置。
 ![image](https://hackmd.io/_uploads/B1se2R9xbg.png)

```C#
int[,] matrix = new int[3, 4];
```

- 二維陣列下的記憶體位址一定要轉成「線性位置」
```markdown
Loc(aᵢⱼ) = a + n*(i−1)*d + (j−1)*d
```
![image](https://hackmd.io/_uploads/HJp5hA5lbl.png)

|符號|意思|
|----|---|
| **Loc(aᵢⱼ)** | 第 i 列 j 行的元素在記憶體中的實際位址 |
| **a**        | 陣列起始位址（base address）   |
| **n**        | 每列有幾個元素（column count）  |
| **i**        | 第 i 列                  |
| **j**        | 第 j 行                  |
| **d**        | 每個元素的大小（bytes）         |

:::warning
記憶體計算上需要扣掉一的原因是，計算起始點為「零」，就如同計算間隔數的概念相同。
:::

#### 三維陣列：多了一個深度（Depth）的資料空間。(立體的)
**特性**
- 索引方式：`cube[layer, row, col]`
- 記憶體仍然是一條線，只是用三層轉換。
- 位址計算需先算「每層有多少元素」。
- 記憶體位址計算：特定座標的陣列元素，在記憶體的一維位址是哪裡 
```sql
宣告A為 (1:x,1:y,1:z)的三圍陣列，求(i,j,k)位置 
以列為主:
Loc(A[i,j,k])=記憶體起始位置(BA)
                +(i-1)*y*z*單位空間
                +(j-1)*z*單位空間
                +(k-1)*單位空間
以行為主
    Loc(A[i,j,k])=記憶體起始位置(BA)
                +(k-1)*x*y*單位空間
                +(j-1)*z*單位空間
                +(i-1)*單位空間
  ```
:::info 
:star:  索引範圍 (C#不適用)：每一維的「索引範圍」是從哪到哪  ex：標示(2:5)=範圍為2~5
:star:  計算記憶體位置時要使用「大小」= 索引上界-索引下界+1
:star:  單位空間：每個陣列元素佔的記憶體大小 ex：int=4Bytes
:::

![image](https://hackmd.io/_uploads/H1QcjJjlZg.png)

```c#
int[,,] cube = new int[2, 3, 4];
```


#### N維陣列：可以想像成 1D、2D、3D 的延伸，一直擴展到更多維度。
**特性**
- 存取需要 N 個索引：`data[i1, i2, i3, i4, i5]`
- 用公式以「每一維的大小」換算記憶體位址。
```c#
int[,,] cube = new int[2, 3, 4];
```

#### 陣列總結
| 陣列          | 說明       | 用途例子        | 索引數量 |
| ----------- | -------- | ----------- | ---- |
| **一維 (1D)** | 一條線性資料   | 成績列表、身高列表   | 1 個  |
| **二維 (2D)** | 表格、矩陣    | Excel、影像像素  | 2 個  |
| **三維 (3D)** | 有深度的立體資料 | 醫學影像、RGB 影像 | 3 個  |
| **N維**      | 多維度資料    | AI張量、統計資料   | N 個  |


---
## 2-3 矩陣與深度學習
###  重點說明：
- 矩陣是「二維陣列」的結構（row × column），表示物體在3D世界中的移動方向。
:bulb: 三維陣列會以向量x,y,z軸表示，除了表示移動方向，也代表物體的大小。
- 矩陣可以是資料儲存，也可以進行資料運算。
- 著重的是 **結構與維度** 的描述
- 稀疏矩陣，是為了把「巨大資料」壓縮成「有效率的結構」

### 常見矩陣操作：
- 相加：兩個矩陣的行數與列數必須相同，相加完也需相同。
- 相乘：A矩陣的欄數必須等於B矩陣的列數才能相乘。商會等於C矩陣(A列數xB行數)，每個A矩陣的欄位必須與每個B矩陣的列數相乘後並相加，會取得到C矩陣的值。
    - 核心概念：矩陣相乘可以把「多組資料」一次套用「多組規則」，得到新結果。
    - 用途：把資料A套用規則B → 產生新結果 C
    - 舉例：學生每科的成績+各科加權=每位學生加權後的總分
![image](https://hackmd.io/_uploads/HJ9MXa8WZe.png)
- 轉置：把矩陣的列變成行，行變成列，變成新的矩陣
    - 用途：調整資料方向，方便運算、分析或視覺化
- 稀疏矩陣：大部分都是 0 的矩陣，需要特殊儲存方式來節省記憶體並加快運算。
    - 三項式資料結構進行壓縮儲存：只記有資料的項目(列、行、資料)
![image](https://hackmd.io/_uploads/SJ4sFaLbbg.png) ![image](https://hackmd.io/_uploads/HyN2Kp8ZWg.png)
:::    warning
利用三項式資料結構進行稀疏矩陣儲存時，第一列的資料會代表著儲存規則。
從上圖範例：0列的資料代表著矩陣式6*6的大小，資料數只有8項。
:::

- 種類：
    - 上三角形矩陣：對角線以下都是0的矩陣
        只存 i ≤ j 的元素，長度 = N(N+1)/2
        `k = N*i - (i*(i-1))/2 + (j - i)`
    - 下三角形矩陣：對角線以上都是0的矩陣
        只存 i ≥ j 的元素，長度 = N(N+1)/2
        `k = i*(i+1)/2 + j`
    - 帶狀矩陣：上三角形矩陣的狀況下，右上方元素也為0的矩陣，其餘每行都有3個元素

### 陣列VS矩陣
| 特性 | 陣列（Array）| 矩陣（Matrix）|
| -- | -- | -- |
| 維度 | 一維、二維、甚至多維 | 二維或多維（通常二維）|
| 用途 | 儲存資料、方便索引(找資料) | 儲存資料 + 數學運算（加、乘、轉置）  |
| 運算 | 沒有內建數學意義的運算，通常靠迴圈手動操作|有明確的數學運算規則（矩陣乘法、轉置、稀疏矩陣運算等） |
| 例子 | `int[] a = {1,2,3}` 或 `int[,] b = new int[3,4]` | `C = A × B` 或 `B = A^T`|

:::warning
C# 本身沒有提供專門的矩陣類別，但可以透過多維陣列或陣列的陣列來表示矩陣；若要進行矩陣運算，通常需要自己實作或使用第三方數學套件。
:::

### 生活例子
- 地鐵路網圖：橫線代表列車方向（row），直線代表站點（column）。
- 每個交會點就是一個 matrix[i][j]。
- 地鐵路網圖本身是一個二維資料格子（陣列）
- 當你用它做數學運算或圖論計算時，它就變成矩陣。(比如最短路徑計算)

### 討論題
👉 你如何直覺理解「矩陣乘法」？（不要求數學，只問理解方式）

---
## 2-4 認識多項式
### 重點說明
多項式由「係數 + 次方」組成。
使用陣列儲存可快速存取：**第 i 格就是 x^i 的係數**。

多項式如：
    `P(x) = 4x³ + 2x¹ + 7`
    
可以利用兩種方式進行儲存：
#### 陣列：用以儲存係數
 `A = [7, 2, 0, 4]`
`index` = 次方，`value` = 係數

陣列非常適合用來存處多項式，因為：
- 位置固定
- 查找係數快
- 計算加減乘法結構清楚

這種資料結構背後強調「映射」概念：
- index → exponent (指數)
- value → coefficient (係數)

#### 多項式表示法
- 最高次方+係數
`A = {3, 4, 0, 2, 7}`
:::warning
第一項代表的是最高指數
:::
- 非零項次
`A = {3, 4 , 3, 2, 1, 7, 0}`
:::warning
第一項代表最高指數，在紀錄時會將指數和係數都寫出來，指忽略係數為零的資料。
:::

### 補充內容 (2025/12/5)
✔ **變成資料，就可以用資料結構處理**
    加法、乘法、微分……全部變成「陣列操作」。

✔ **很多演算法都依賴多項式的結構**
例：
   - Horner’s Rule → 將多項式快速計算
   - FFT → 快速多項式乘法，現代密碼學、影像壓縮都用
   - 內插、擬合、曲線逼近 → 機器學習也會用到
   - 數值方法 → 牛頓法、逼零等

多項式並不是為了算 x，而是： ***把「連續的數學問題」變成「離散的資料問題」。***

:::spoiler 具體例子：**找字串「ABC」在「ZZABCD」裡的出現位置**
1. 先定義多項式編碼規則
    | 字元 | 編碼 |
    | -- | -- |
    | A  | 1  |
    | B  | 2  |
    | C  | 3  |
    | Z  | 26 |
2. 把字串變成多項式（係數）
   ```c#
    A      B      C   
    ↓      ↓      ↓   
    1·x² + 2·x¹ + 3·x⁰
   ```
3. 代入 x=31 (其他也可以) ※早期最常使用的質數
   計算結果為 `1·31²+ 2·31¹ + 3·31⁰ = 1·961 + 62 + 3 = 1026`
   
4. 把目標字串「ZZABCD」也轉成多項式窗口
    ```c#
    Z    Z   A   B   C   D
    26  26   1   2   3   4
   ```
5. 接下來以3字母為單位開始尋找
    - 窗口 1：「ZZA」
       `26·31² + 26·31¹ + 1 = … (算完 = 25069)`
        不等於 1026 ⇒ 不是
    - 窗口 2：「ZAB」
        `26·31² + 1·31¹ + 2 = … (算完 = 25115)`
        不等於 1026 ⇒ 不是
    - 窗口 3：「ABC」
        `1·31² + 2·31¹ + 3 = 1026`
        ✔ 找到了！
6. 總結公式
   `newHash = (oldHash - 頭字元·x²)·x + 新字元`
    因為它是地道的「係數 × xᵏ」組成，才能這樣滑動、更新、比對。
    - 不用比對字元
    - 不用逐字掃描
    - 不用重新計算整段值
    
:::

### 討論題
👉 你覺得把多項式視為「一堆係數」而不是「一堆 x 的次方運算」是不是比較容易理解？
:::spoiler GPT解答
是的。

| 原因                | 說明           |
| ----------------- | ------------ |
| 係數是資料，不需想像 x 的運算  | 減少抽象思考       |
| 所有多項式運算都只是係數操作    | 本質上就是陣列操作    |
| 電腦只處理係數，不真的處理 x^n | 與 CPU 模型完全一致 |
| 認知負擔低             | 不需要記公式的「形狀」  |
| 與線代與程式的資料結構自然一致   | 容易串進更大系統     |

:::
👉 為什麼用 index 來代表次方，是一個有效率的設計？
:::spoiler GPT解答
1. 因為「次方」本身就是自然對應「位置」的概念
2. 陣列索引是 O(1) 的：直接跳到該次方
3. CPU cache 友好：連續記憶體帶來高效運算
4. 空間與儲存結構簡單
5. 數學式與程式結構直覺一樣
6. 多項式運算的時間複雜度更穩定
    - 多項式乘法為例：
        - 使用 list/index → O(n²) 明確且可預期
        - 使用 dictionary → O(n² * 查找成本)，實際上更慢，而且 cache 不友好
:::
---
## 總結
- 陣列是資料結構，用來存任意資料。
- 矩陣是有「數學意義」的二維陣列。
- 多項式是數學函數，常用陣列或稀疏格式來儲存係數。
- 本章節學習目的是把「數學公式」或「大量資料」變成更容易計算、更有效率的資料結構，讓電腦更能理解並協助處理。

