###### tags: `資訊科技`
# 資料結構與演算法(使用C++)
## 一、學習資料結構與演算法的目的
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)
- [[C++] STL 容器 (一) - 基本介紹](http://larry850806.github.io/2016/06/06/STL1/)
- C++ 堆疊(Stack)常用的方法
| 名稱 | 意義 |
|:-----|:----------|
|stack<int> sk |建立一個int型別的stack|
|sk.size() |堆疊元素數量|
|sk.empty() |判斷堆疊是否為空|
|sk.push(x) |從堆疊「頂端」加入一個元素x|
|sk.pop() |刪除堆疊頂端元素|
|sk.top() |取得堆疊頂端元素|
:::info
EX_01：10進位轉2進位(以STL stack實作)。11->1011
:::
``` javascript=
int main()
{
stack<int> sk; // 需含入 stack 標頭檔
int n;
cin >> n;
while (....) // n大於0
{
........ // 將n除以2的餘數push進堆疊
........ // 將n除以2
}
while (........) // 堆疊內還有元素
{
cout << ........ // 印出堆疊頂端元素
........ // 將堆疊頂端元素移除
}
}
```
2. ### 佇列
- FIFO(first in first out)
- C++ 佇列(Queue)常用的方法
| 名稱 | 意義 |
|:--------|:----------|
|queue<int> q |建立一個int型別的queue|
|q.size() |佇列元素數量|
|q.empty() |判斷是否為空|
|q.push(x) |從佇列「後端」加入一個元素x|
|q.pop() |從「前端」刪除一個元素|
|q.front() |取得前端元素|
|q.back() |取得後端元素|
:::info
EX_02：[ZeroJudge e183: 10940 - Throwing cards away II](https://zerojudge.tw/ShowProblem?problemid=e183)
給你一疊有1~n編號的牌(1在最上面，n在最下面)，在牌數大於1的時候執行以下操作：「丟掉最上面的牌，並把現在最上面的的牌放到最下面。」
求最後剩下的那張牌編號為?(7->6、10->4)
:::
``` javascript=
int main()
{
........ // 宣告一個int型別的queue，名為q，需含入 queue 標頭檔
int n;
cin >> n;
for (int i=1;i<=n;i++)
........ // 將牌的編號(1 2 3 …)依序push入佇列
while ( ........ ) // 當佇列size>1時繼續執行
{
........ // 將最上面的牌丟掉
........ // 將次張牌重新放入佇列尾端
........ // 將次張牌丟掉
}
cout << ........ // 印出剩下的那張牌
return 0;
}
```
3. ### 樹
- [模擬具有樹枝狀性質的資料](http://www2.csie.ntnu.edu.tw/~u91029/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):先走訪樹根，然後左子樹，最後右子樹。
* 中序走訪(inOrder):先走訪左子樹，然後樹根，最後右子樹。
* 後序走訪(postOrder):先走訪左子樹，然後右子樹，最後樹根。
<br/>
:::info
EX_03：下圖的前序、中序、後序走訪分別為？(先以人工走訪，再用程式驗証)
:::
``` javascript=
#include<iostream>
using namespace std;
int data[7]={0,1,2,3,4,5,6}; // 全域變數
void preorder(int i) // 前序，void表示沒有回傳值
{
if(i>=7)
return;
else
{
cout << data[i] << " ";
preorder(2*i+1);
preorder(2*i+2);
}
/*
if(i<7)
{
cout << data[i] << " ";
preorder(i*2+1);
preorder(i*2+2);
}
*/
}
void inorder(int i) // 中序
{
if(i>=7)
return;
else
{
........
........
........
}
}
........ // 後序
{
if .......
.......
else
{
........
........
........
}
}
int main(void)
{
preorder(0);
cout << endl;
inorder(0);
cout << endl;
postorder(0);
cout << endl;
}
/*
前序(preOrder)：
中序(inOrder)：
後序(postOrder)：
*/
```
- [二元搜尋樹](https://mark-lin.com/posts/20170309/#--binarysearch-tree-)(課本p4-12)
:::info
EX_04：建立二元搜尋樹
依讀入順序 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_05：若一篇文章每個字母出現的次數為，a:8，b:7，c:3，d:4，e:5，建立Huffman Tree(次數小的結點放左邊)，並求每個字母的Huffman Code。
a->11
b->
c->
d->
e->00
:::
4. ### 圖
- [圖形是「頂點」(vertex)和邊(edge)所組成](https://mark-lin.com/posts/20170311/)
- 圖常用的表示法
* [相鄰矩陣表示法(Adjacency Matrix)](http://web.ntnu.edu.tw/~algo/Graph.html#3)(課本p5-10)
* 相鄰串列表示法(Adjacency Lists)
- 圖的搜尋(課本p5-12)
* [深度優先搜尋(Depth First Search,DFS)](https://jason-chen-1992.weebly.com/home/-graph-searching-methods)：以堆疊(Stack)、遞迴來實作。(類似樹的前序走訪)
* [廣度優先搜尋(Breadth First Search,BFS)](http://simonsays-tw.com/web/DFS-BFS/BreadthFirstSearch.html)：以佇列(Queue)來實作。
:::info
EX_06_1：下圖的DFS與BFS走訪順序為(子節點以字母序走訪)？
DFS：A B C F H ...
BFS：A B C D E ...
:::
:::info
EX_06_2：[ZeroJudge c129: 00572 - Oil Deposits](https://zerojudge.tw/ShowProblem?problemid=c129)。
以DFS找出@相鄰土地有@有幾塊。
:::
``` javascript=
#include <iostream>
using namespace std;
int visited[100][100]={0};
char mp[100][100];
int r,c; // 全域變數
void dfs(int i,int j)
{
if(i<0 || i>=r || .... || .... || .... || ....) // i(列)、j(欄)超出邊界、此點已被拜訪過、此點沒油
return;
visited[i][j]=1;
dfs(i-1, j-1); // 左上。螢幕左上角為原點，往下、往右為正。 先看列(數學上的y)，後看欄(數學上的x)
dfs(i-1, j); // 上
dfs(...., ....); // 右上
........ // 左
........ // 右
........ // 左下
........ // 下
........ // 右下
}
int main()
{
int cnt=0;
cin >> r >> c;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
cin >> mp[i][j];
for ........ // 第 i 列
{
for ........ // 第 j 欄
{
if(........) // 目前座標沒被拜訪過 而且 有油
{
dfs(.... , ....); // 從此點開始DFS
cnt++;
}
}
}
cout << cnt << endl;
// 地圖、visited陣列輸出
// Bonus：visited陣列以編號標出不同的油田
return 0;
}
測資(ans=4)
9 10
@@*@*@@*@@
@@*@**@*@*
*@@@****@@
*@@@**@**@
***@*@****
@@@@@*@*@@
@*@@**@@@*
@*@*******
@***@@@@**
```
:::info
EX_06 (Bonus)：[ZeroJudge d626: 小畫家真好用](https://zerojudge.tw/ShowProblem?problemid=d626)。
以DFS找出油漆桶能上色的範圍。
:::
- 圖的應用
* [最短路徑(一個頂點到多頂點Dijkstra)](http://puremonkey2010.blogspot.com/2013/05/alg-info-dijkstras-algorithm-shortest.html)(課本p6-20)
:::info
EX_07：畫出下圖的相鄰陣列，以Dijkstra演算法，求A到各點的最短路徑(以Excel表格表示)？++**0 8 6 4 3 1 5**++
:::
* [最小生成樹(minimum spanning tree)](https://www.itread01.com/content/1545066724.html)(課本p5-23)
(1). Kruskal演算法為一個使用貪婪法 (greedy method) 的演算法，一開始為一空樹，每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入樹中，直到所有點皆在樹中即完成。
(2). Prim演算法與Dijkstra演算法類似，屢次找出不在樹上，離樹最近的點。
:::info
EX_08：畫出下圖的最小生成樹，其權重總和為？++**28**++
:::
<br />
## 三、演算法
1. ### 演算法效能
- [運算能力](https://buzzorange.com/techorange/2019/09/11/solve-sums-of-three-cubes/)
* 循序搜尋 v.s. 二分搜尋
- [時間複雜度](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)
- 求質數演算法效能比較
:::info
EX_09_1：求10萬內的質數。註解18行(並在上一行加分號)->1.411 sec
:::
``` javascript=
int main()
{
int n=100000;
for (int i=2;i<=n;i++)
{
bool prime=true;
for ........ // 測試2~i-1是否為其因數
{
if ........ // 如果j為i的因數
{
........ // prime 設為 false
........ // 跳出此層迴圈
}
}
if ........ // 如果i不是質數
cout << i << " ";
}
return 0;
}
```
:::info
EX_09_2：求100萬內的質數。註解18行(並在上一行加分號)->0.902 sec
:mega:
1. 如果一個數是合數，它的最小質因數會小於等於它的平方根。
2. 因為成對出現的因數中，一個會≦√n，而另一個會≧√n。因此只要檢查≦√n中是否有n的因數即可。
:::
``` javascript=
int main()
{
int n=1000000;
for (int i=2;i<=n;i++)
{
bool prime=true;
for (int j=2; ........ ;j++) // 測試2~√i是否為其因數，sqrt需含入cmath標頭檔
{
if ........ // 如果j為i的因數
{
........ // prime 設為 false
........ // 跳出此層迴圈
}
}
if ........ // 如果i是質數
cout << i << " ";
}
return 0;
}
```
:::info
EX_10：[埃拉托斯特尼篩法](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)(課本p3-5)，求1000萬以內的質數。註解15行(並在上一行加分號)->0.155 sec
:::
``` javascript=
int main()
{
int n=10000000;
bool prime[10000001]; // 區域變數只能到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的倍數不為質數
for (int i=2;i<=n;i++)
if ........ // 如果i是質數
cout << i << " ";
return 0;
}
```
<br />
2. ### 分而治之(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)
:::info
EX_11：[ZeroJudge d219: 00374 - Big Mod](https://zerojudge.tw/ShowProblem?problemid=d219)
對相當大的b、p、m，請寫一個有效率的演算法來計算 r = b^p mod m ( 1 <= b、p、m <= 32767 )
b=2、p=8、m=10 → r=6
b=2、p=10、m=10 → r=4
b=17、p=1765、m=3 → r=2
:::
:mega: [分配律](https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4)：(A\*B)%M=[ (A%M)\*(B%M) ]%M→B^P^%M=[ (B^P/2^%M)\*(B^P/2^%M) ]%M
EX：4\*5%3=(4%3)\*(5%3)、5\*8%3=(5%3)\*(8%3)%3
``` javascript=
int dc(int b,int p,int m)
{
if ........ // p分割到1時停止
return ........
else
{
if ........
return ........ // p為偶數，( b^(p/2)%m * b^(p/2)%m ) % m
else
........ // p為奇數要比偶數時多乘一次b
}
}
int main()
{
int b,p,m;
while(cin >> b >> p >> m)
cout << dc(b,p,m) << endl;
return 0;
}
```
Sign in with Wallet
Connect another wallet