# 資料結構
1. 本章以難易度區分，由低至高。
2. 配合洪逸資結第七版。
3. 本章以研究所考古為主。

## 1.基礎知識 ( Recursive、Performance )

### **<font color="red">（ Hint ）</font>**
* Time Complex
* Recursive and Example

### **<font color="red">（ 解釋 ）</font>**
### Time Complex

時間複雜度，判斷演算法孰優孰劣的依據，粗略分為:
Big-O、Omega、Theta

本章介紹的方式為：
Recursion Tree
Master Theorem



### Recursive and Example

考題幾乎都是針對問題寫出遞迴：
1. 數學題
2. 資結後面的章節
3. 河內塔與Permutation列印

Hint : 前面兩項太雜不介紹，這邊只介紹第三個

<font color="red">**河內塔**</font>

<font color="red">**Permutation**</font>

## 2.陣列、鏈結串列

### **<font color="red">（ Hint ）</font>**
* Array 位址計算
* Link List 種類、基本操作
* Generalize List
* 多項式表示
* Sparse Matrix

### **<font color="red">（ 解釋 ）</font>**
### Array位址計算

### Linked List

**( 種類 )**

1. Single Linked List

3. Circular Linked List ( 頭接尾 )

5. Double Linked List ( Node有兩個Linked )

**( 基本操作 )**

1. Length ( 求整條長度 )


基本概念 : 用count計數，並讓point持續向下。

3. Reduce ( 回收整條 )

4. Invert ( 反轉 )

## 3.堆疊、佇列

### **<font color="red">（ Hint ）</font>**
* Stack and Queue Define
* Permutaion ( +ab... )
* Prefix、Infix、Postfix
* 應用
* 互相製作演算法 ( 本章忽略，考古題可現場拆 )

### **<font color="red">（ 解釋 ）</font>**
### Stack and Queue

<font color="red">**Stack**</font>

<font color="red">**Queue**</font>

### Permutation
給一序列資料，再給一個空的Stack，我們可以藉由push進去pop出來的動作，交換原本資料的前後順序，而這就被稱作Stack Permutation。

來個常見的例題：
For a given sequence of elements {𝐴, 𝐵, 𝐶}, please write down its stack permutation.

答案(請反白)：
* ABC；<font color="white">push 𝐴, pop 𝐴, push 𝐵, pop 𝐵, push 𝐶, pop C</font>
* ACB；<font color="white">push 𝐴, pop 𝐴, push 𝐵, push C, pop C, pop B</font>
* BAC；<font color="white">push 𝐴, push 𝐵, pop B, pop A, push C, pop C</font>
* BCA；<font color="white">push 𝐴, push 𝐵, pop B, push C, pop C, pop A</font>
* CBA；<font color="white">push 𝐴, push 𝐵, push C, pop C, pop B, pop A</font>

### Prefix、Infix、Postfix

### Stack 與 Queue 互相製作
<font color="red">Queue using Stack :</font>

一個stack 叫s1 ， 另一個stack叫 s2。

enQueue 代表 放東西。
enQueue 裡的寫法 :
如果 s1 不是空的，s2就會push (s1的pop)
像是s1 現在是1(stack的top) 2 3 4 5(5代表最後放，在stack的最底端) 。
會變成
s2 : 5(stack的top) 4 3 2 1
s1:空的
之後 s1.push(x) ，s1: 6 (新增的數字)
如果s2不是空的 ，就
s1.push(s2.pop());
s1 會變成 1(stack的top) 2 3 4 5 6

## 4.搜尋與排列

### **<font color="red">（ Hint ）</font>**
* Define Sort and Search relationship
* Sort（ 初等排序、高等排序 ）

### **<font color="red">（ 解釋 ）</font>**
### Sort and Search

搜尋分為兩個 Linear 與 Binary ， Linear 就是一個一個慢慢查
而 Binary 就是先用 Sort 做排序才搜尋

### Sort
<font color="red">**初階排序 ( O(n^2) )**</font>

1. Insertion Sort ( 插撲克牌 )


2. Select Sort ( 挑最小的交換 )


3. Bobble Sort ( 像氣泡一樣大的會往上浮 )


<font color="red">**高階排序 ( O(nlgn) )**</font>

1. Quick Sort


2. Merge Sort


3. Heap Sort


<font color="red">**線性排序 ( O(n) )**</font>

前面的初階與高階排序都是透過比較而得到結果，而排序還有另外一個方式
透過類似分析值域的方式來排列大小


Radix Sort 依個位、十位、百位放進桶子內就可以排列完畢

<font color='red'>**常見排序函數比較**</font>


## 5.雜湊

### **<font color="red">（ Hint ）</font>**
* Define Hash
* Hash Function
* Overflow Handle

### **<font color="red">（ 解釋 ）</font>**
### Hash

透過特定算法將資料放進特定格子，此種方法稱為 Hash Function

### Hash Function Design

Function 的設計應盡量避免造成：
Collision : Hash Function 算出來之格子已有資料了
OverFlow : 發生 Collision 後，此 Bucket 也沒有空格

函式有很多，常見的有：
1. Middle Square ( 平方後取中間的數字 )
2. Division ( 除法 )
3. Folding addition ( 將數字切成相同片段並相加 )
4. Digits Analysis ( 分析數字的值域 )

### Overflow Handle

1. Linear Probing：(H(x) + i) % B
2. Quadratic Probing：(H(x) + i ^ 2) % B
3. Double Hashing：(H1(x) + i * H2(x)) % B
4. Chain：Linked List
5. Rehashing：若發生則換別的 Hash Function

## 6.圖形


### **<font color="red">（ Hint ）</font>**
* Articulation point ( 關節點 )
* DFS. BFS.
* 儲存結構 ( Adjacency Matrix, Multi lists )
* minimum spaning tree method ( Kruskal, Primes )
* Shortest Path method ( Dijkstra, Ballman ford, Floyd Warshall )
* AOV, AOE

### **<font color="red">（ 解釋 ）</font>**
### 關節點( Articulation point )
Def : 將關節點拆開可以將圖分成兩個。 ( u : parent , v : child )

Method : 找出關節點需以已下步驟

1. 將圖轉換成DFS, 並將順序記錄下來。
2. 新增一個表格加入前述的順序，並新增Low。
3. Low就是目前節點所能找到的最老祖先。
4. 比對 L[v] >= d[u]。

### 深度與廣度優先( DFS, BFS )
Def : 如果以樹來解釋，DFS主要依賴著<font color="red">**樹高**</font>搜尋，BFS主要依賴<font color="red">**樹寬**</font>搜尋。

Method :
DFS : （ 假設起點為2, 令數字小的優先 ）


1. 從起點開始沿著子點瘋狂往下鑽探。
2. 若往下已沒有子點可找, 則返回最初交叉點, 往另一邊。
（ 答案 ： 2 - 5 - 9 - 4 - 7 - 2 - 6 - 5 - 11 ）

BFS : （ 與上述條件相同, 圖片相同 ）

1. 從起點開始先找與起點相差一條邊的點。
2. 將點全部列入後, 開始找兩條、三條、以此類推直到沒有。
（ 答案 ： 2 - 5 - 7 - 2 - 6 - 9 - 4 - 5 - 11 ）

### 儲存結構

Def : 儲存結構分成三個Adjacency Matrix、Adjacency Lists、 Adjacency MultiLists。

Method :
Adjacency Matrix :


列出去否連接的陣列 （ 紀錄是否 ）

Adjacency Lists :


紀錄與哪些點有連接 （ 紀錄點 ）

Adjacency MultiLists :


此結構分成點與邊結構，點結構指向第一個出現此點的邊結構。
而邊結構紀錄了 ：
1. 第一點
2. 第二點
3. 下一個出現第一點的邊結構
4. 下一個出現第二點的邊結構

### minimum Spaning Tree

Def : 生成樹（ Spaning Tree ）的意思是將圖做成沒有Cycle的圖，而最小生成樹就是當路徑有Weight時，整個圖的Weight最小。

Method:
<font color="red">Kruskal</font>（ 以線為考量 ）:


此演算法的方式為每一輪都先找目前圖中最小的線，然後判斷是否有無Cycle。

<font color="red">Prim</font>（ 以點為考量 ）:


1. 找一點出發，並列表權重
2. 將與此點相連的點之線Weight寫上，其餘不相連則為無限大
3. 從出發點挑小的線Weight一一拜訪

Hint: 與 Dijastra 很像

### Shortest Path Method

Def : 此章共有三個方法 Dijastra、Bellman Ford、Floyd Warshall 。

Method :
<font color="red">Dijastra</font>


與Prim基本一樣，以圖片來說從A點當出發點，紀錄目前可以連接的點
並且不斷更新前面的邊

特性：
1. 不能有負的 Weight 因為此演算法會一直挑小的
2. 此法為 Single Source Shortest Path
3. 此法為貪婪演算法，每次都需要挑小的

處理角度：
以點為出發點，一個點兩個點開始延伸到N個點，挑選點的方式為貪婪演算法

<font color="red">Bellman Ford</font>


與第一個很像，不同點在於第一個方法每一輪都要挑小的，而此法可以隨機挑選
每一輪都增加一個邊，直到做完 N-1 次（ 總邊數 ）

特性：
1. 可處理負邊，並偵測負迴圈（ 愈跑愈小 ）
2. 此法為 Dynamic Programming

處理角度：
以邊為出發點，每一輪增加一個邊，從一個邊增加到 N-1

<font color="red">Floyd Warshall</font>

上面兩個方法都是單點到其他點的最短位置，而此方法則是任兩點之間的
最短路徑
其實任兩點之間的最短路徑可以用上面兩個方法跑n次得出結果
可是 Dijastra 沒辦法處理負邊而 Bellman 則是速度太慢 O(N x V)
而且 Bellman 也不能存在負的迴圈，若有負邊則 O(n^4)

而此方法再有負邊的情況只需 O(n^3)


Floyd Warshall 的定義式，請看以下例子：
（ 定義式要稍微記一下，考古有類似的題目 ）


左上角A^-1為初始階段，搭配定義式每一次的更新都需要：
1. 路徑的長度每一個都需要比較
2. 以下開始舉例：
A[1][0] = 4
判斷 min{A[1][0] , A[1][0] + A[0][0]}

A[1][2] = 無限
判斷 min{A[1][2] , A[1][0] + A[0][2]}
因為 min{無限 , 4 + 3} = 7
所以更新為 7


以下自己練習看看


參考來源：https://www.youtube.com/watch?v=6wPIMMuPxUw
### AOV, AOE

AOV ( Active on Vertex )、AOE ( Active on Edge )
AOV 指的是活動在點上這邊比較多考到的是拓墣法，因為這邊太簡單
所以不多作介紹


這張圖是 AOE，代表活動作用在邊上，而邊上就會如圖所示顯現權重，若一個點
有兩條邊指向則代表這兩條邊都需要完成才能繼續

Hint : 這邊最重要的是找出 Critical Path 與判斷哪些工作可以 Delay
Critical Path 就是 Start 到 End 長度最長經過的路徑
以此題為例最長的路徑為 { A,D,E,F,G }
所以 Critical Path 長度為 20
而所有最長路徑經過的點都為 Critical task



## 7.樹 ( 二元樹、高階樹 )

### **<font color="red">（ Hint ）</font>**
*

### **<font color="red">（ 解釋 ）</font>**

###### tags: `研究所`