###### 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://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):先走訪樹根,然後左子樹,最後右子樹。](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://i.imgur.com/rzMHnHj.png =450x) ::: + [二元搜尋樹](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)? ![](https://i.imgur.com/0NMKz8g.png =460x) 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**++ ![](https://i.imgur.com/tjw9GuN.png =350x) ::: + 圖的應用2-[最短路徑(一個頂點到多頂點Dijkstra)](http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dijkstra.html)(課本p6-20) :::info EX_1_8:畫出下圖的相鄰陣列,以Dijkstra演算法,求A到各點的最短路徑(以Excel表格表示)?++**0 8 6 4 3 1 5**++ ![](https://i.imgur.com/f0wz9DD.jpg =270x) ::: <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^) ![](https://i.imgur.com/iXNlfVN.png =300x) <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)