# 📝 Chapter 2 陣列結構
## 2-1 線性串列簡介
### 重點說明
線性串列是「資料有序排列」的集合。
每個元素只有一個前面、一個後面（頭尾除外）。
→ 目的在於表現串列中任兩個相鄰元素之間的關係。
- aᵢ₋₁ 是 aᵢ 的先行元素
- aᵢ₊₁ 是 aᵢ 的後繼元素
### 生活例子
像排隊：每個人都有固定的位置，前後關係明確。
英文字母：A,B,C,D...Z
### 儲存結構
**靜態資料結構**
- 特點：大小固定，在 **程式執行前(編譯時)** 就決定記憶體空間。
- 優點：存取快、結構簡單
- 缺點：彈性低，無法擴增或縮小、容易造成記憶體空間浪費
- 例子：陣列結構(Array)
```C#
int[] arr = new int[10]; // 陣列大小固定，不能增加元素
```
- 注意：有序串列(index)不等於儲存的資料內容是有序的
**動態資料結構**
- 特點：大小可變，可在 **程式執行時** 增加或刪減空間
- 優點：彈性大，適合資料量不固定的情況
- 缺點：存取速度可能比靜態慢，管理較複雜
- 例子：鏈結式結構
```C#
List<int> list = new List<int>(); // 可以隨時增加或刪除元素
list.Add(5);
list.RemoveAt(0);
```
### 討論題
👉 在生活中，你覺得哪些事情是「線性」的？為什麼？
👉 如果隊伍很常插隊或加人，順序表 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]`
- 只需知道「起始位址」+「元素大小」即可計算位置。
```C#
int[] arr = { 10, 20, 30, 40 };
```
#### 二維陣列：由「列 × 行」組成的表格。
**特性**
- 用兩個索引：`matrix[row, col]`
- 資料在記憶體中仍然是線性的（以 Row-major 排列）。
- 位址計算要以「每列的欄數」來換算位置。
```C#
int[,] matrix = new int[3, 4];
```
- 二維陣列下的記憶體位址一定要轉成「線性位置」
```markdown
Loc(aᵢⱼ) = a + n*(i−1)*d + (j−1)*d
```
|符號|意思|
|----|---|
| **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
:::
```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
- 舉例：學生每科的成績+各科加權=每位學生加權後的總分
- 轉置：把矩陣的列變成行，行變成列，變成新的矩陣
- 用途：調整資料方向，方便運算、分析或視覺化
- 稀疏矩陣：大部分都是 0 的矩陣，需要特殊儲存方式來節省記憶體並加快運算。
- 三項式資料結構進行壓縮儲存：只記有資料的項目(列、行、資料)
 
::: 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 不友好
:::
---
## 總結
- 陣列是資料結構，用來存任意資料。
- 矩陣是有「數學意義」的二維陣列。
- 多項式是數學函數，常用陣列或稀疏格式來儲存係數。
- 本章節學習目的是把「數學公式」或「大量資料」變成更容易計算、更有效率的資料結構，讓電腦更能理解並協助處理。
Sign in with Wallet
Connect another wallet