###### 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
:::

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)
:::

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：下圖的前序、中序、後序走訪分別為？(先以人工走訪，再用程式驗証)


:::

        #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找出@相鄰土地有@有幾塊。
:::

        #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
:::

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的因數即可。
:::

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
:::

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

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;
}