---
# System prepended metadata
title: 資料結構
tags: [研究所]
---
# 資料結構
1. 本章以難易度區分，由低至高。
2. 配合洪逸資結第七版。
3. 本章以研究所考古為主。
## 1.基礎知識 ( Recursive、Performance )
### **（ Hint ）**
* Time Complex
* Recursive and Example
### **（ 解釋 ）**
### Time Complex
時間複雜度，判斷演算法孰優孰劣的依據，粗略分為:
Big-O、Omega、Theta
本章介紹的方式為：
Recursion Tree
Master Theorem
### Recursive and Example
考題幾乎都是針對問題寫出遞迴：
1. 數學題
2. 資結後面的章節
3. 河內塔與Permutation列印
Hint : 前面兩項太雜不介紹，這邊只介紹第三個
**河內塔**
**Permutation**
## 2.陣列、鏈結串列
### **（ Hint ）**
* Array 位址計算
* Link List 種類、基本操作
* Generalize List
* 多項式表示
* Sparse Matrix
### **（ 解釋 ）**
### 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.堆疊、佇列
### **（ Hint ）**
* Stack and Queue Define
* Permutaion ( +ab... )
* Prefix、Infix、Postfix
* 應用
* 互相製作演算法 ( 本章忽略，考古題可現場拆 )
### **（ 解釋 ）**
### Stack and Queue
**Stack**
**Queue**
### Permutation
給一序列資料，再給一個空的Stack，我們可以藉由push進去pop出來的動作，交換原本資料的前後順序，而這就被稱作Stack Permutation。
來個常見的例題：
For a given sequence of elements {𝐴, 𝐵, 𝐶}, please write down its stack permutation.
答案(請反白)：
* ABC；push 𝐴, pop 𝐴, push 𝐵, pop 𝐵, push 𝐶, pop C
* ACB；push 𝐴, pop 𝐴, push 𝐵, push C, pop C, pop B
* BAC；push 𝐴, push 𝐵, pop B, pop A, push C, pop C
* BCA；push 𝐴, push 𝐵, pop B, push C, pop C, pop A
* CBA；push 𝐴, push 𝐵, push C, pop C, pop B, pop A
### Prefix、Infix、Postfix
### Stack 與 Queue 互相製作
Queue using Stack :
一個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.搜尋與排列
### **（ Hint ）**
* Define Sort and Search relationship
* Sort（ 初等排序、高等排序 ）
### **（ 解釋 ）**
### Sort and Search
搜尋分為兩個 Linear 與 Binary ， Linear 就是一個一個慢慢查
而 Binary 就是先用 Sort 做排序才搜尋
### Sort
**初階排序 ( O(n^2) )**
1. Insertion Sort ( 插撲克牌 )
2. Select Sort ( 挑最小的交換 )
3. Bobble Sort ( 像氣泡一樣大的會往上浮 )
**高階排序 ( O(nlgn) )**
1. Quick Sort
2. Merge Sort
3. Heap Sort
**線性排序 ( O(n) )**
前面的初階與高階排序都是透過比較而得到結果，而排序還有另外一個方式
透過類似分析值域的方式來排列大小
Radix Sort 依個位、十位、百位放進桶子內就可以排列完畢
**常見排序函數比較**
## 5.雜湊
### **（ Hint ）**
* Define Hash
* Hash Function
* Overflow Handle
### **（ 解釋 ）**
### 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.圖形
### **（ Hint ）**
* Articulation point ( 關節點 )
* DFS. BFS.
* 儲存結構 ( Adjacency Matrix, Multi lists )
* minimum spaning tree method ( Kruskal, Primes )
* Shortest Path method ( Dijkstra, Ballman ford, Floyd Warshall )
* AOV, AOE
### **（ 解釋 ）**
### 關節點( Articulation point )
Def : 將關節點拆開可以將圖分成兩個。 ( u : parent , v : child )
Method : 找出關節點需以已下步驟
1. 將圖轉換成DFS, 並將順序記錄下來。
2. 新增一個表格加入前述的順序，並新增Low。
3. Low就是目前節點所能找到的最老祖先。
4. 比對 L[v] >= d[u]。
### 深度與廣度優先( DFS, BFS )
Def : 如果以樹來解釋，DFS主要依賴著**樹高**搜尋，BFS主要依賴**樹寬**搜尋。
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:
Kruskal（ 以線為考量 ）:
此演算法的方式為每一輪都先找目前圖中最小的線，然後判斷是否有無Cycle。
Prim（ 以點為考量 ）:
1. 找一點出發，並列表權重
2. 將與此點相連的點之線Weight寫上，其餘不相連則為無限大
3. 從出發點挑小的線Weight一一拜訪
Hint: 與 Dijastra 很像
### Shortest Path Method
Def : 此章共有三個方法 Dijastra、Bellman Ford、Floyd Warshall 。
Method :
Dijastra
與Prim基本一樣，以圖片來說從A點當出發點，紀錄目前可以連接的點
並且不斷更新前面的邊
特性：
1. 不能有負的 Weight 因為此演算法會一直挑小的
2. 此法為 Single Source Shortest Path
3. 此法為貪婪演算法，每次都需要挑小的
處理角度：
以點為出發點，一個點兩個點開始延伸到N個點，挑選點的方式為貪婪演算法
Bellman Ford
與第一個很像，不同點在於第一個方法每一輪都要挑小的，而此法可以隨機挑選
每一輪都增加一個邊，直到做完 N-1 次（ 總邊數 ）
特性：
1. 可處理負邊，並偵測負迴圈（ 愈跑愈小 ）
2. 此法為 Dynamic Programming
處理角度：
以邊為出發點，每一輪增加一個邊，從一個邊增加到 N-1
Floyd Warshall
上面兩個方法都是單點到其他點的最短位置，而此方法則是任兩點之間的
最短路徑
其實任兩點之間的最短路徑可以用上面兩個方法跑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.樹 ( 二元樹、高階樹 )
### **（ Hint ）**
*
### **（ 解釋 ）**
###### tags: `研究所`