# 資料結構初探
[TOC]
## 一、複雜度分析
- 如果 $\dfrac{f(n)}{g(n)}$ 在 $n$ 趨近於無限大時趨近於0，則 $f(n)$ 比 $g(n)$ 大。
- 如果 $\dfrac{f(n)}{g(n)}$ 在 $n$ 趨近於無限大時趨近於無限大，則 $f(n)$ 比 $g(n)$ 小。
- 否則為一樣量級。
### 複雜度的概念
- 假設所有操作都花費**一樣**的時間
- 把所有操作需要的「**次數**」都計算出來
- 看看量級的大小(**複雜度**)，並且評估執行時間
### Big-O (大O符號)
記為 $O(f(n))$，其中$f(n)$是複雜度量級的上界(Upper Bound)。假設實際運算時間為$g(n)$，那麼在$n$ 趨近於無限大時，有$\dfrac{f(n)}{g(n)}$趨近於某常數或者$\dfrac{f(n)}{g(n)}$趨近於無限大。
Ex.
> - $3n^3 + 5n^2 + 10n + 3 \in O(n^3)$
> - $f(n) \in O(n^2)$，則$f(n) \in O(n^3)$
> - $1000 \in O(1)$
>==> 取最緊的 Upper Bound
### Little-o (小o符號)
記為 $o(f(n))$，其中$f(n)$是複雜度量級的**嚴格**上界。假設實際運算時間為$g(n)$，那麼在$n$ 趨近於無限大時，有$\dfrac{f(n)}{g(n)}$趨近於某常數或者$\dfrac{f(n)}{g(n)}$趨近於無限大。
Ex.
> - $3n^3 + 5n^2 + 10n + 3 \notin o(n^3)$
> - $3n^3 + 5n^2 + 10n + 3 \in o(n^4)$
> - $f(n) \in o(n^2)$，則$f(n) \in o(n^3)$
### Big-omega
記為 $\Omega(f(n))$，其中$f(n)$為複雜度量級的下界(Lower Bound)。
Ex.
> - $3n^3 + 5n^2 + 10n + 3 \in \Omega(n^3)$
> - $f(n) \in \Omega(n^2)$，則$f(n) \in \Omega(n^3)$
### Little-omega
記為 $\omega(f(n))$，其中$f(n)$為複雜度量級的**嚴格**下界(Lower Bound)。
Ex.
> - $3n^3 + 5n^2 + 10n + 3 \in \omega(n^3)$
> - $f(n) \in \omega(n^2)$，則$f(n) \notin \omega(n^3)$
### Big-theta
記為 $\Theta(f(n))$，其中$f(n)$為複雜度量級的**嚴格上下界**(完全相同)。
Ex.
> - $3n^3 + 5n^2 + 10n + 3 \in \Theta(n^3)$
> - $3n^3 + 5n^2 + 10n + 3 \notin \Theta(n^4)$
> - $3n^3 + 5n^2 + 10n + 3 \notin \Theta(n^2)$
<hr>
## 二、基礎資料結構
資料結構是指如何在電腦中儲存資料，通常是(多種)演算法+(多種)資料結構。
對於不同用途選擇不同資料結構 :
- 時間複雜度
- 空間複雜度
- coding複雜度
常見操作: push(放進一個元素)、pop(拿出一個元素)、query(各種查詢)。
<br>
### Stack (堆疊)
性質為 First In Last Out (FILO)，資料存取同一方向。實作使用陣列或Linked list。
#### 陣列實作
- 用一個變數 top 紀錄頂端的位置 (堆疊個數)
- top=-1 表示 stack 是空的 (有些初始值為0)
- push: top+1
- pop: top-1
- 堆疊為滿時，則不可再加入 ; 為空時，則不可再取出
<br>
### Queue (佇列)
性質為 First In First Out (FIFO) 或是 First Come First Service (FCFS)，資料存取不同方向，分類有單向或環狀。實作使用陣列或Linked list。
#### 陣列實作
- 用一個變數 front 紀錄最前面的元素的「前一格」位置
- 用一個變數 rear 紀錄最後面的元素的位置
- front == rear 表示 queue 是空的
- push: rear+1
- pop: front+1
產生問題: 一個元素一旦被pop，該位置無法再放新元素。
解決方法:
- rear 到陣列最後時，將所有元素平移到前方 (不是好方法 -> 所有元素都需移動)
- 使用環狀queue (也就是更改rear位置)
- 使用Linked list
<br>
### Stack vs Queue
<img src="https://miro.medium.com/v2/resize:fit:1400/1*zKnDkJpL-4GQ36kzrDiODQ.png"><br>
### 佇列 vs 環狀佇列
#### 佇列
- front的初始值 = -1 , rear的初始值 = -1
- 判斷佇列為空 `rear == front`
- 判斷佇列為滿 `rear = maxSize -1`
#### 環形佇列
- front的初始值 = 0 , rear的初始值 = 0
- 需預留一個儲存單元來判斷佇列是否為空還是滿
- 判斷佇列為空 `rear == front`
- 判斷佇列為滿 `(rear+1) % maxSize == front`
- 判斷佇列的有效數據個數 `(rear + maxSzie - front) % maxSize`
> Q : front = 0，rear = 5，maxSize = 7，共有幾個有效數據?
>
> A : (5+7-0) % 7 = 5 ，共有五個有效數據。
**為什麼不是6？** 因為rear會指向最後一個元素的後一個位置。
<br>
### Linked List (鏈結串列)
基本單元為 Node(data+pointer)，將很多 Node 接起來，head指標指向第一個Node，最後一個指標指向 NULL。(也就是每個元素指紀錄它的下一個元素，外部指紀錄起點(head))
**動態宣告記憶體**的方式(與陣列不同的是，陣列一開始就宣告固定記憶體了，動態宣告的方式不會浪費記憶體，需要的時候再跟系統取用)，不能隨機存取(random access) (也就是要從第一個開始走)，分類有單向、雙向或環狀。
<img src='https://media.geeksforgeeks.org/wp-content/uploads/20220816144425/LLdrawio.png'><br>
#### 實作
先定義一個 struct/class Node，作為linked list的節點，裡面存 data 和一個指向下一個 Node 的 pointer。
使用時只需要一個變數head紀錄linked list的起點就可以了。
```c++=
#include <studio.h>
struct Node {
int _data;
Node* _next;
};
int main() {
Node* head;
return 0;
}
```
- **用 linked list 實做 stack**
用 count 來記錄節點數、top 指向排頭節點
- push: 在 top 前面插入一個節點
- pop: 刪除 top 指向的節點
<img src='https://abhinavranaweb.files.wordpress.com/2020/06/stack-ds.png?w=1067&h=566&crop=1'><br>
- **用 linked list 實作 queue**
要多紀錄linked list的尾端(rear)
- push: 在 rear 後面插入一個節點
- pop: 刪除 front 指向的節點
<img src='https://media.geeksforgeeks.org/wp-content/uploads/Operations-on-Circular-Queue.png'><br>
- **Linked list v.s. Array v.s. Dynamic array**
<img src="https://i.stack.imgur.com/Ly4Fp.jpg">
<hr>
## 三、Recursion
需指定終止條件，避免陷入無窮迴圈。
範例 : n! 實作
```c++=
int nLevel(n) {
if (n == 0) return 1; // 設定條件
else return n * nLevel(n-1);
}
```
<br>
### Iteration v.s. Recursion
<img src='https://cdn-media-1.freecodecamp.org/images/1*QrQ5uFKIhK3jQSFYeRBIRg.png'><br><br>
### 費式數列
將大問題拆分成小問題 $\implies$ 分而治之(Divide and Conquer)
<img src='https://learning.juice.codes/api/images/dvcNK'><br>
### 河內塔
將 $n$ 層積木從 $a$ 移動到 $c$ (左移到右)，所需次數為 $n = 2^n - 1$
圖片過程示例 :
[[數學公式講解](https://youtu.be/0lDXv0Y6ClQ?si=xe7Ml0akNEzvIaK-)] [[程式算法講解](https://youtu.be/iN_U9ozdCD4?si=dzhboEUJRVC_PNQ1)]
<img src='https://pic.pimg.tw/f74461036/1495536756-3594624128.png'>
```c++=
#include <iostream>
#include <iomanip>
using namespace std;
void Hanoi(int n, char A, char B, char C);
// Hanoi( n 層積木, from, pass, to )
void Hanoi(int n, char X, char Y, char Z)
{
if (n == 1)
{
count << n << ":" << X << "-->" << Z << endl;
return;
}
Hanoi( n-1, X, Z, Y);
count << n << ":" << X << "-->" << Z << endl;
Hanoi( n-1, Y, X, Z);
return;
}
```
<hr>
## 四、Flood Fill
- 用 queue 來做，類似全部領域都同時涉略，並且一層一層學深入，被稱為廣度優先搜索 (Breath-first search, BFS)
- 用 stack 來做，類似先一口氣專精某個領域，鑽研完才鑽研其他領域，被稱為深度優先搜索 (Depth-first search, DFS)
<img src='https://upload.wikimedia.org/wikipedia/commons/8/89/Recursive_Flood_Fill_8_%28aka%29.gif' text-align:center>
<hr>
## 五、Tree
### 性質
- 任何一點都可以當 root
- 任兩點恰有一條不經過重複點的路徑
- 一棵有 $N$ 個節點的樹恰有 $N-1$ 條邊
### 紀錄
利用 Linked List 或 Dynamic array 動態紀錄 :
```c++=
#include <stdio.h>
#include <vector>
using namespace std;
struct Node{
int _data;
vector<Node*> _child;
};
```
另一個常見的方法，當給定每個點的編號時 :
```c++=
using namespace std;
int data[SIZE];
vector<int> child[SIZE];
```
優點 : 只需要編號，不需要 Pointer
### Binary Tree
- 每個節點最多只有兩個子節點
- 第 $k$ 層最多有 $2^k$ 個節點
- 一棵深度為 $k$ 的 binary tree 最多有 $2^{k+1}-1$ 個節點
```c++=
struct Node{
int _data;
Node *_lchild, *_rchild; /*左子節點和右子節點*/
}
```
### Binary Tree 遍歷
分為 : 前序、中序、後序
差別 : 在什麼時候印出一個node的值
- **前序**
```c++=
void dfs(Node* node){
node -> printData();
if(node -> _lchild != NULL)
dfs(node -> _lchild);
if(node -> _rchild != NULL)
dfs(node -> _rchild);
}
```
```c++=
output: 1 2 4 5 3 6
```
- 中序
```c++=
void dfs(Node* node){
if(node -> _lchild != NULL)
dfs(node -> _lchild);
node -> printData();
if(node -> _rchild != NULL)
dfs(node -> _rchild);
}
```
```c++=
output: 4 5 2 1 3 6
```
- 後序
```c++=
void dfs(Node* node){
if(node -> _lchild != NULL)
dfs(node -> _lchild);
if(node -> _rchild != NULL)
dfs(node -> _rchild);
node -> printData();
}
```
```c++=
output: 4 5 2 6 3 1
```
### Complete binary tree
- 除了最後一層，每一層都是填滿的
- 最後一層的元素盡量往左靠
- Complete Binary Tree 的時間效率會比 Non-Complete Binary Tree 的效率高
#### 儲存方式
- 編號為 $k$ 的兩個 child 編號分別為 ```2k``` 和 ```2k+1```
- 編號為 $k$ 的 parent 編號為 ```k/2```
- 一個有 $n$ 個元素的 complete binary tree 的深度約為 $log_2(n)$
<img src='https://miro.medium.com/v2/resize:fit:1200/1*CMGFtehu01ZEBgzHG71sMg.png'><br>
<hr>
## 六、Heap
### Priority Queue
如果不希望 pop 出來的是最先進去或最後進去的，而是根據「權重」大小
#### 基本操作
- push : 將一個元素放進 priority queue 中
- top : 詢問現在 priority queue 中權重最大的元素
- pop : 將 priority queue 中權重最大的元素拿掉
陣列是沒有序的，top 找到最大值是 $O(n)$，pop 找到最大值是 $O(n)$，將最後一個元素補回來進空格是 $O(1)$，push 是 $O(1)$，整體複雜度是 $O(n)$。
<br>
微改良 : 保持陣列的第一個元素是權重最大的。
- push 放進去是 $O(1)$，和第一個元素(最大值)比較是 $O(1)$，複雜度是 $O(1)$。
- top : 陣列第一個元素就是最大值 $O(1)$。
- pop : 第一個元素最大的 pop，找到剩下元素中的最大值 $O(n)$。
整體複雜度還是 $O(n)$。
#### 分組作法
將 $k$ 個數字分成一組，並記錄這些數字中權重最大的
- top : 比較每組的最大值是 $O(\frac{n}{k})$。
- pop : 找到最大值 pop 掉是 $O(\frac{n}{k})$，最後一個元素補上是 $O(n)$，找到組中最大的元素是 $O(k)$。整體來看是 $O(\frac{n}{k}) + O(k)$，視k的大小而定。
選擇 $k=\sqrt{n}$
- push : $O(1)$、top : $O(\sqrt{n})$、pop : $O(\sqrt{n})$
### Heap
heap 其實就是一棵 complete binary tree，性質為**父節點的權重不小於子節點的權重**。
將元素放進 tree 是 $O(1)$，和父節點比較是 $O(1) * log(n)$ (較大元素往上放，直到權重不大於父節點，最多比較 $log(n)$ 次)。
- push : $O(log(n))$
- top : $O(1)$
- pop : $O(log(n))$
整體複雜度是 $O(log(n))$。
<br><hr>
## 七、枚舉
### BFS
過程中的所有節點都必須記錄下來。
- 方法一 :
每個節點都詳細記錄對應的路徑。
推入新節點和每個節點所需的空間為 $O(路徑長)$
- 方法二 :
在每個節點紀錄該節點的父親以及路徑上的最末元素，在輸出時直接順著父親指針走回去，就可以輸出解了。
推入新節點和每個節點所需空間為 $O(1)$
### DFS
直接開一個 stack 紀錄當前節點的路徑。
**狀態空間很大的情況使用DFS**
<br><hr>
## 八、貪心
### 證明架構
1. 為了方便表示與比較，先用代數表達出問題與解答的數學模型
2. 假設我們的算法給出的解 $S$ 是錯的，那麼存在真正的最優解 $S'$，且 $|S'|<|S|$
3. 如果有兩個編號分別為 $i,j$ (編號就代表事件的順序) 滿足 「 $i < j$ 且 $i$ 吃的比 $j$ 快」，我們就說這兩個形成一對「逆序對」。既然最優解 $S' \neq S$，那麼 $S'$ 裡面一定存在相鄰的兩元素形成逆序對
4. 透過把這兩個順序交換，獲得方案 $S'_1$，證明 $|S'_1| \leq |S|$
5. 如果 $S'_1$ 中還存在相鄰逆序，則再把該對逆序元素交換形成 $S'_2$，類似 4 的證明可知 $|S'_2| \leq |S'_1|$
6. 不斷重複類似 5 的步驟，直到當前的解 $S'_x$ 中部存在相鄰逆序。此時 $S'_x$ 必定不存在任何逆序對，從而有 $S'_x = S$
7. 於是有 $|S| \leq |S'_x| \leq |S'_{x-1}| \leq ... \leq |S'_1| \leq |S'|$，即$|S|<|S'|$，與 $|S'|<|S|$ 的假設矛盾，從而證明 $S$ 是最佳解。
<br>
### 最優編碼樹
1. 一定不會只有一個子節點的節點
> 否則會直接用這個節點的子節點取代它自己，依舊是合法編碼樹，但空間消耗更小
2. 頻率越高的字元對應的葉節點深度越淺
> 否則交換兩者的位置，空間消耗更小
3. 必定存在一棵最優編碼樹，使得頻率最低的兩個字元對應的葉節點形成兄弟
> 由性質 1 可知深度最大的一層至少有兩個節點
> 由性質 2 可確定頻率最低的兩個字元皆位於深度最大的一層
> 如果兩者並非兄弟，則把他們位置換成兄弟，解的優劣不變
<br><hr>
## 九、Sort 介紹
### A. 內部排序 vs 外部排序
#### 內部排序 (Internal Sort)
資料量少、可以將資料一次全部置於 memory 中進行排序。
> 例如: Bubble Sort, Insertion Sort, Quick Sort, Heap Sort, Radix Sort, Selection Sort
#### 外部排序 (External Sort)
資料量大，無法一次全部置於 memory 中，需要藉助外部儲存體(ex. Disk)保存進行排序。
採用的策略為 **排序 - 合併**，在排序階段，先讀入能放入內存中的數據量，將其排序輸出到一個臨時文件，以此類推，整個數據形成多個有序的臨時文件，最後在合併階段將這些臨時文件排序為一個大的有序文件，即排序結果。
> 例如: Merge Sort (利用 Selection Tree 結構輔助)、M-way Search Tree、B Tree
<br>
### B. Stable vs Unstable Sorting Method
在輸入資料中，有可能存在多筆相同的資料，例如: 100、23、54、data_1、data_2、39 (data_1 和 data_2 are the same)。經過某個排序演算法後，**若是能保證 data_1 仍在 data_2 之前，則這個演算法稱為 Stable** ; 反之若是無法保證 (data_2 有可能在 data_1) 之前，則稱為 **Unstable**。
**Unstable 的演算法代表會有不必要的 swap**，會造成多餘的計算，而 Unstable 排序演算法不一定比 Stable 慢 (例如 Quick Sort)。
<br>
### C. 初等排序 vs 高等排序
兩者差別在於**時間複雜度**。
#### 初等排序
在初等排序中的平均時間複雜度為 $O(n^2)$。
例如 : Selection Sort、Insertion Sort、Bubble Sort
#### 高等排序
在高等排序中的平均時間複雜度為 $O(nlogn)$
例如 : Quick Sort、Merge Sort、Heap Sort
<br>
### D. Linear-Time Sorting Algorithm (線性時間排序)
與前面提到的演算法差別在於，排序技巧並非採用 Comparison-based (透過「小於或等於」的操作來確定兩個元素的序列前後)。
非比較排序的演算法像是 Radis Sort、Bucket Sort、Counting Sort。
<br>
### E. Selection Sort、Insertion Sort、Bubble Sort
這三種排序方法，都會將排序對象分為兩部分 : 已排序與未排序。
#### 實作範例的比較函數
```c++=
#define SWAP(x, y) { int t; t = x; x = y; y = t; }
int ascending(int a, int b) return a - b;
int descending(int a, int b) return -ascending(a, b);
```
- #### Selection Sort
如果排序是由小而大，則從**後端未排序部分選擇一個[最小值]**，並**放入前端已排序部分的[最後一個]** (若是由大而小，則反之)。
> 有一序列排序前為 70、80、31、37、10、1、48、60、33、85
>
>\[1\] 80 31 37 10 70 48 60 33 85（選出最小值 1）
\[1 10\] 31 37 80 70 48 60 33 85（選出最小值 10）
\[1 10 31\] 37 80 70 48 60 33 85（選出最小值 31）
\[1 10 31 33\] 80 70 48 60 37 85（選出最小值 33）
\[1 10 31 33 37\] 70 48 60 80 85（選出最小值 37）
\[1 10 31 33 37 48\] 70 60 80 85（選出最小值 48）
\[1 10 31 33 37 48 60\] 70 80 85（選出最小值 60）
\[1 10 31 33 37 48 60 70\] 80 85（選出最小值 70）
\[1 10 31 33 37 48 60 70 80\] 85（選出最小值 80）
\[1 10 31 33 37 48 60 70 80 85\]（選出最小值 85）
#### 範例實作
```c++=
// selectedIdx -> 從未排序陣列中選出最小的值
// selectedIdx(待排序陣列, 未排序的頭, 未排序的尾, 比較函數)
int selectedIdx(int* arr, int from, int to, int(*compar)(int, int))
{
int selected = from;
for (int i=from+1; i<to; i++)
{
if (compar(arr[i], arr[selected]) < 0) selected = i;
}
return selected;
}
// Selection Sort(待排序陣列, 陣列長度, 比較函數)
void selectionSort(int* arr, int len, int(*compar)(int, int))
{
for (int i=0; i<len; i++)
{
int selected = selectedIdx(arr, i, len, compar);
if (selected != i) SWAP(arr[i], arr[selected]);
}
}
```
<br>
- #### Insertion Sort
從**後端未排序部分取得[最前端的值]**，**插入前端已排序部分的[適當位置]**
> 有一序列排序前為 77、67、8、6、84、55、85、43、67
>
>\[77 92\] 67 8 6 84 55 85 43 67（將 77 插入 92 前）
\[67 77 92\] 8 6 84 55 85 43 67（將 67 插入 77 前）
\[8 67 77 92\] 6 84 55 85 43 67（將 8 插入 67 前）
\[6 8 67 77 92\] 84 55 85 43 67（將 6 插入 8 前）
\[6 8 67 77 84 92\] 55 85 43 67（將 84 插入 92 前）
\[6 8 55 67 77 84 92\] 85 43 67（將 55 插入 67 前）
\[6 8 55 67 77 84 85 92\] 43 67（將 85 插入 92 前）
\[6 8 43 55 67 77 84 85 92\] 67（將 43 插入 55 前）
\[6 8 43 55 67 67 77 84 85 92\]（將 67 插入 77 前）
如果資料量很小或是有大智的排序，插入排序經常作為快速排序(Quick Sort)的補充。
##### 範例實作
```c++=
// insertedIdx -> 找出未排序的第一個元素位置應該放入的位置
// insertedIdx(待排序陣列, 未排序的第一個元素, 比較函數)
int insertedIdx(int* arr, int eleIdx, int(*compar)(int, int))
{
for (int i=0; i<eleIdx; i++)
{
if (compar(arr[i], arr[eleIdx]) > 0) break;
}
return i;
}
// insert -> 將比插入值大的元素，往後移一個位置，再把插入值放到適當位置
// insert(待排序陣列, 插入值當前的位置, 插入值應該放的位置)
void insert(int* arr, int eleIdx, int inserted)
{
int ele = arr[eleIdx];
for (int i=eleIdx; i>inserted; i--)
{
arr[i] = arr[i-1];
}
arr[inserted] = ele;
}
// Insertion Sort(待排序陣列, 陣列長度, 比較函數)
void insertionSort(int* arr, int len, int(*compar)(int, int))
{
for (int i=0; i<len; i++)
{
int inserted = insertedIdx(arr, i, compar);
if (inserted != i) insert(arr, i, inserted);
}
}
```
<br>
- #### Bubble Sort
若是由小到大，**以[比較相鄰元素]的方式，將較大元素交換至右端**，因此**較大元素會不斷往右移動**，直到適當位置。
> 有一序列排序前為 95、27、90、49、80、58、6、9、18、50
>
> 27 90 49 80 58 6 9 18 50 \[95\]（95 浮出）
27 49 80 58 6 9 18 50 \[90 95\]（90 浮出）
27 49 58 6 9 18 50 \[80 90 95\]（80 浮出）
27 49 6 9 18 50 \[58 80 90 95\]（58 浮出）
27 6 9 18 49 \[50 58 80 90 95\]（50 浮出）
6 9 18 27 \[49 50 58 80 90 95\]（49 浮出）
6 9 18 \[27 49 50 58 80 90 95\]（27 浮出）
6 9 \[18 27 49 50 58 80 90 95\]（18 浮出）
6 \[9 18 27 49 50 58 80 90 95\]（9 浮出）
\[6 9 18 27 49 50 58 80 90 95\]（6 浮出）
#### 範例實作
```c++=
// bubbleTo -> 從未排序陣列中，找出最大元素，將其浮到最右方
// bubbleTo(待排序陣列, 未排序的最右方位置, 比較函數)
void bubbleTo(int* arr, int to, int(*compar)(int, int))
{
for (int i=0; i<to-1; i++)
{
if (compar(arr[i+1], arr[i]) < 0) SWAP(arr[i+1], arr[i]);
}
}
// Bubble Sort(待排序陣列, 陣列長度, 比較函數)
void bubbleSort(int* arr, int len, int(*compar)(int, int))
{
for (int i=0; i<len; i++) bubbleTo(arr, len-i, compar);
}
```
<br>
#### 程式執行
需合併前面程式碼
```c++=
#include <bits/stdc++.h>
#define LEN 8
void print(int* arr, int len)
{
for (int i=0; i<len; i++) cout << arr[i] << " ";
cout << endl;
}
int main()
{
int number[LEN] = {10, 9, 1, 2, 5, 3, 8, 7};
selectionSort(number, LEN, ascending);
print(number, LEN);
insertionSort(number, LEN, descending);
print(number, LEN);
bubbleSort(number, LEN, ascending);
print(number, LEN);
return 0;
}
```
#### 執行結果 :
```c++=
1 2 3 5 7 8 9 10
10 9 8 7 5 3 2 1
1 2 3 5 7 8 9 10
```
Sign in with Wallet
Connect another wallet