###### tags: `資訊科技`
# 資料結構與演算法(使用C++、ZeroJudge)
## 零、學習資料結構與演算法的目的
### 1. 資料結構討論「資料儲存的方式」
+ 如陣列、鏈結串列
### 2. 演算法討論「解決問題的想法」
+ 如排序方法、找質數的方法
:mega: 所選用的資料結構和演算法將影響程式的複雜度與效率
### 3.參考網站
+ [演算法與資料結構](http://alrightchiu.github.io/SecondRound/mu-lu-yan-suan-fa-yu-zi-liao-jie-gou.html)
+ [Algorithms and Data Structures](http://gousios.org/courses/algo-ds/)
<br />
## 一、資料結構
### 1. 堆疊
+ LIFO(last in first out)
+ [模擬程式](https://www.cs.usfca.edu/~galles/visualization/StackArray.html)
:::info
EX_1_1：執行下列堆疊程式，印出一堆堆疊操作後的堆疊內容。
:::
``` c=
stack<int> sk;
sk.push(5);
sk.push(3);
sk.pop();
sk.push(7);
sk.pop();
sk.push(4);
while(....) // 堆疊不空
{
.... // 印出堆疊最上面的元素
.... // pop掉這個元素
}
```
<br />
### 2. 佇列
+ FIFO(first in first out)
+ [模擬程式](https://www.cs.usfca.edu/~galles/JavascriptVisual/QueueArray.html)
:::info
EX_1_2：執行下列佇列程式，印出一堆佇列操作後的佇列內容。
:::
``` c=
queue<int> q;
q.push(5);
q.push(3);
q.pop();
q.push(7);
q.pop();
q.push(4);
while(....) // 佇列不空
{
.... // 印出佇列前面的元素
.... // pop掉這個元素
}
```
<br />
### 3. 樹
+ [模擬具有樹枝狀性質的資料](http://web.ntnu.edu.tw/~algo/Tree.html)，由節點與邊組成，例如家族族譜、電腦資料夾結構。
+ [二元樹](https://mark-lin.com/posts/20170309/#--binary-tree-)
+ [二元樹的走訪(Tree Traversal)](http://alrightchiu.github.io/SecondRound/binary-tree-traversalxun-fang.html#pre)(課本p4-7)
- [前序走訪(preOrder):先走訪樹根，然後左子樹，最後右子樹。](https://www.youtube.com/watch?v=jKUqfFgMatQ)
- [中序走訪(inOrder):先走訪左子樹，然後樹根，最後右子樹。](https://www.youtube.com/watch?v=PQUUzrvV-7M)
- [後序走訪(postOrder):先走訪左子樹，然後右子樹，最後樹根。](https://www.youtube.com/watch?v=_slTRpD1tIE)
<br/>
:::info
EX_1_3：下圖的前序、中序、後序走訪分別為？
:::
+ [二元搜尋樹](https://mark-lin.com/posts/20170309/#--binarysearch-tree-)(課本p4-12)
- [模擬程式](https://visualgo.net/en/bst)
:::info
EX_1_4：建立二元搜尋樹
依讀入順序 30, 15, 50, 35, 10, 25, 40, 20, 45 建立一個二元搜尋樹(binary search tree)。
:::
+ 樹的應用
- [遊戲樹(game tree)](https://commons.wikimedia.org/wiki/File:Tic-tac-toe-full-game-tree-x-rational.jpg)(課本p4-20)
- [霍夫曼編碼(Huffman Coding)](http://puremonkey2010.blogspot.com/2011/02/huffman-code.html)(課本p4-24)
:::info
EX_1_5：若一篇文章每個字母出現的次數為：a:8，b:7，c:3，d:4，e:5。
建立Huffman Tree(次數小的結點放左邊)，並求每個字母的Huffman Code。
a->11
b->
c->
d->
e->00
:::
<br />
### 4. 圖
+ [圖形是「頂點」(vertex)和邊(edge)所組成](https://mark-lin.com/posts/20170311/)
+ 圖常用的表示法
- [相鄰矩陣表示法(Adjacency Matrix)](http://web.ntnu.edu.tw/~algo/Graph.html#3)(課本p5-10)
- [相鄰串列表示法(Adjacency Lists)](http://web.ntnu.edu.tw/~algo/Graph.html#4)
+ 圖的搜尋(課本p5-12)
- [深度優先搜尋(Depth First Search,DFS)](https://jason-chen-1992.weebly.com/home/-graph-searching-methods)：以堆疊(Stack)、遞迴來實作。(類似樹的前序走訪)
* [模擬程式1](https://visualgo.net/en/dfsbfs?slide=1)
* [模擬程式2](https://www.cs.usfca.edu/~galles/visualization/DFS.html)
* [Animation of Graph DFS](https://www.youtube.com/watch?v=NUgMa5coCoE)
- [廣度優先搜尋(Breadth First Search,BFS)](http://simonsays-tw.com/web/DFS-BFS/BreadthFirstSearch.html)：以佇列(Queue)來實作。
* [模擬程式1](https://visualgo.net/en/dfsbfs?slide=1)
* [模擬程式2](https://www.cs.usfca.edu/~galles/visualization/BFS.html)
* [Animation of Graph BFS](https://www.youtube.com/watch?v=x-VTfcmrLEQ)
:::info
EX_1_6：[下圖的DFS與BFS走訪順序為(子節點以字母序走訪)](https://docs.google.com/drawings/d/1WHsqYwHsgG8ILC-MXCpo6S_oZ_5LdhjZ25-PAldwXkA/edit?usp=sharing)？
DFS： 將走訪順序標示在字母「上」。
線條以「黑色箭頭」代表往下探尋，以「白色箭頭」代表回溯上一個點。
BFS： 將階層編號(紅色)標示在字母「下」。
:::
+ 圖的應用1-[最小生成樹(minimum spanning tree)](https://www.itread01.com/content/1545066724.html)(課本p5-23)
- Kruskal演算法為一個使用貪婪法 (greedy method) 的演算法，一開始為一空樹，每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入樹中，直到所有點皆在樹中即完成。
- Prim演算法與Dijkstra演算法類似，屢次找出不在樹上，離樹最近的點。
:::info
EX_1_7：畫出下圖的最小生成樹，其權重總和為？++**28**++
:::
+ 圖的應用2-[最短路徑(一個頂點到多頂點Dijkstra)](http://puremonkey2010.blogspot.com/2013/05/alg-info-dijkstras-algorithm-shortest.html)(課本p6-20)
:::info
EX_1_8：畫出下圖的相鄰陣列，以Dijkstra演算法，求A到各點的最短路徑(以Excel表格表示)？++**0 8 6 4 3 1 5**++
:::
<br />
## 二、演算法
### 1. 演算法效能
+ [運算能力](https://buzzorange.com/techorange/2019/09/11/solve-sums-of-three-cubes/)
- 費式數列-遞迴 vs. 陣列
- 搜尋-循序 vs. [二分搜尋](https://www.cs.usfca.edu/~galles/visualization/Search.html)
+ [時間複雜度](https://jason-chen-1992.weebly.com/home/time-space-complexity)
- [常見的六種時間複雜度與演算法](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E5%BE%9E%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6%E8%AA%8D%E8%AD%98%E5%B8%B8%E8%A6%8B%E6%BC%94%E7%AE%97%E6%B3%95-%E4%B8%80-b46fece65ba5)
+ 大O記號(Big-O notation)
- 令f(n) 與g(n) 是由非負整數對應至實數的函數，若存在正實數常數c 和正整數常數n~0~，使n≧n~0~時，f(n) ≦ cg(n) 成立，則我們說 f(n)=O(g(n))。
- 若f(n)=3n^2^+2，g(n)=n^2^ (n~0~=2, c=4)。f(n)=O(n^2^)
<br />
### 2.求質數演算法效能比較
:::info
EX_2_1：[d237: 質數合](https://zerojudge.tw/ShowProblem?problemid=d237)
以『[埃拉托斯特尼篩法](https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)』讓本題的速度更快。
:::
``` c=
int main()
{
int n=2000000;
bool prime[n+1]; // 區域變數只能到200萬左右，更大要改為全域變數。
fill(prime,prime+n+1,1); // 全部先設為1(true)，假設都是質數。需含入algorithm標頭檔
for (int i=2;i<=sqrt(n);i++) // 檢查到<=√n即可
if ........ // 如果i是質數
for ........ // 如果i是質數，則篩掉它的倍數。(從i^2開始，每次+i)
prime[....]=....; // i的倍數不為質數
long long sum=0;
for(int i=2;i<=2000000;i++)
if(prime[i])
sum+=i;
cout << sum << endl;
return 0;
}
```
### 3. 排序(sort)
+ [思考排序的演算法(1)](https://zh.wikipedia.org/wiki/十三張) [(2)](https://kopu.chat/2017/06/22/插入排序insertion-sort/)
+ [模擬程式](https://visualgo.net/en/sorting?slide=1)
+ [Bubble Sort](https://medium.com/@mingjunlu/understanding-bubble-sort-7aa4567986ae)
+ [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms)
:::info
EX_2_2：練習 bubble sort
:::
``` c=
for ........ // 6個數字排序只需5個循環
{
........ // 每次比較索引值0 1、1 2、2 3、3 4、4 5的數字
{
if (num[....] > num[....]) // 如果左邊比右邊大
{
........ // num[j]和num[j+1]交換
........
........
}
}
}
Q：for 內圈寫完後(將最大值移至最右的位子)，複製貼上5次，程式碼會正確嗎？
```
### 4. 二分搜尋(binary search)
+ [模擬程式](https://www.cs.usfca.edu/~galles/visualization/Search.html)
### 5. 分而治之(Divid and Conquer)
+ [合併排序(Merge Sort)1](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e)、[合併排序2](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)
Sign in with Wallet
Connect another wallet