###### 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://i.imgur.com/sbgxlao.png =100x) - [二元樹](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:下圖的前序、中序、後序走訪分別為?(先以人工走訪,再用程式驗証) ![](https://i.imgur.com/J1qqaQ1.png =350x) ::: ``` 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走訪順序為(子節點以字母序走訪)? ![](https://i.imgur.com/JGKRYVy.png =450x) 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://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dijkstra.html)(課本p6-20) :::info EX_07:畫出下圖的相鄰陣列,以Dijkstra演算法,求A到各點的最短路徑(以Excel表格表示)?++**0 8 6 4 3 1 5**++ ![](https://i.imgur.com/f0wz9DD.jpg =270x) ::: * [最小生成樹(minimum spanning tree)](https://www.itread01.com/content/1545066724.html)(課本p5-23) (1). Kruskal演算法為一個使用貪婪法 (greedy method) 的演算法,一開始為一空樹,每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入樹中,直到所有點皆在樹中即完成。 (2). Prim演算法與Dijkstra演算法類似,屢次找出不在樹上,離樹最近的點。 :::info EX_08:畫出下圖的最小生成樹,其權重總和為?++**28**++ ![](https://i.imgur.com/tjw9GuN.png =350x) ::: <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; } ```