---
# System prepended metadata

title: 資料結構與演算法(C++)
tags: [資訊]

---

# **資料結構與演算法(C++)**

# *I 資料結構*

## 1. 堆疊

:::info

+ LIFO(last in first out)

```cpp=
\#include <stack>
```

+ *[[C++] STL 容器 (一) - 基本介紹](http://larry850806.github.io/2016/06/06/STL1/)*

| 名稱 | 意義 |
|:-----|:----------|
|stack\<int> sk|建立一個int型別的stack|
|sk.size()   |堆疊元素數量|
|sk.empty()  |判斷堆疊是否為空|
|sk.push(x)  |從堆疊「頂端」加入一個元素x|
|sk.pop()    |刪除堆疊頂端元素|
|sk.top()    |取得堆疊頂端元素|

:::

### EX_01 10進位轉2進位(以STL stack實作)

```cpp=
#include <iostream>
#include <stack>

using namespace std;

int main()
{
    stack<int> sk;
    int n;
    cin >>n;

    while(n>0)
    {
        sk.push(n%2);
        n=n/2;
    }

    while(!sk.empty())
    {
        cout << sk.top();
        sk.pop();
    }

    return 0;
}
```

## 2. 佇列

:::info

+ FIFO(first in first out)

```cpp=
#include <queue>
```

| 名稱    | 意義 |
|:--------|:----------|
|queue\<int> q |建立一個int型別的queue|
|q.size()     |佇列元素數量|
|q.empty()    |判斷是否為空|
|q.push(x)    |從佇列「後端」加入一個元素x|
|q.pop()      |從「前端」刪除一個元素|
|q.front()    |取得前端元素|
|q.back()     |取得後端元素|

:::

### EX_02

:::info
給你一疊有1~n編號的牌(1在最上面，n在最下面)，在牌數大於1的時候執行以下操作：「丟掉最上面的牌，並把現在最上面的的牌放到最下面。」
求最後剩下的那張牌編號為?
:::

```cpp=
#include <iostream>
#include <queue>

using namespace std;

int main()
{
    queue<int> q;
    int n;
    cin >> n;

    for(int i=1;i<=n;i++)
        q.push(i);

    while(q.size()>1)
    {
        q.pop();
        q.push(q.front());
        q.pop();
    }
    cout << q.front() << endl;

    return 0;
}
```

## 3. 樹

:::info

+ 前序走訪(preOrder):先走訪樹根，然後左子樹，最後右子樹。
+ 中序走訪(inOrder):先走訪左子樹，然後樹根，最後右子樹。
+ 後序走訪(postOrder):先走訪左子樹，然後右子樹，最後樹根。
+ *[二元樹](https://mark-lin.com/posts/20170309/)*

:::

### EX_03

:::info
下圖的前序、中序、後序走訪分別為？
![ ](https://i.imgur.com/DeeJjSy.jpg)

:::

```cpp=
#include <iostream>

using namespace std;

int data[7]={0,1,2,3,4,5,6};

    void preorder(int i)
        {
            if(i<7)
            {
                cout << data[i] << " ";
                preorder(i*2+1);
                preorder(i*2+2);
            }
        }

    void inorder(int i)
        {
            if(i<7)
            {
                inorder(i*2+1);
                cout << data[i] << " ";
                inorder(i*2+2);
            }
        }

    void postorder(int i)
        {
            if(i<7)
            {
                postorder(i*2+1);
                postorder(i*2+2);
                cout << data[i] << " ";
            }
        }

         int main(void)
        {
            preorder(0);
            cout << endl;
            inorder(0);
            cout << endl;
            postorder(0);
            cout << endl;
        }
```

### EX_04 建立二元搜尋樹

:::info
依讀入順序 30, 15, 50, 35, 10, 25, 40, 20, 45 建立一個二元搜尋樹(binary search tree)。
![](<https://i.imgur.com/OwEZYlp.jpg> =300x)

:::

### EX_05 求每個字母的Huffman Code

:::info
若一篇文章每個字母出現的次數為，a=8 b=7 c=3 d=4 e=5，建立Huffman Tree(次數小的字母結點放左邊)，並求每個字母的Huffman Code。

+ *[霍夫曼編碼(Huffman Coding)](http://puremonkey2010.blogspot.com/2011/02/huffman-code.html)*

![](<https://i.imgur.com/6cA02aY.jpg> =500x)

:::

## 4. 圖

:::info

+ 圖形是「頂點」(vertex)和邊(edge)所組成
  + 圖常用的表示法
    + *[相鄰陣列表示法(Adjacency Matrix)](http://www.csie.ntnu.edu.tw/~u91029/Graph.html)*
    + 相鄰串列表示法(Adjacency Lists)
  + 圖的搜尋
    + *[深度優先搜尋(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)來實作。
![](<https://i.imgur.com/E9ZtULC.jpg> =300x)
:::

### EX_06

```cpp=
#include <iostream>

using namespace std;

int visited[100][100]={0};
char mp[100][100];
int r,c;
int cnt=0;

void dfs(int i,int j)
{
    if(i<0 || i>=r || j<0 || j>=c || visited[i][j]!=0 || mp[i][j]=='*')
         return;
    visited[i][j]=cnt+1;

    dfs(i+1, j-1);
    dfs(i+1, j);
    dfs(i+1, j+1);
    dfs(i, j-1);
    dfs(i, j+1);
    dfs(i-1, j-1);
    dfs(i-1, j);
    dfs(i-1, j+1);
}

int main()
{

    cin >> r>>c;

    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            cin >> mp[i][j];

    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            if(visited[i][j]==0 && mp[i][j]=='@')
            {
                dfs(i,j);
                cnt++;
            }
        }
    }

    cout << cnt << endl;

    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cout << visited[i][j];
        }
        cout << endl;
    }
    return 0;
}

/*
DFS:a b c f e d g

BFS:a b c d e f g
*/

/* 測資(ans=4)
9 10
@@*@*@@*@@
@@*@**@*@*
*@@@****@@
*@@@**@**@
***@*@****
@@@@@*@*@@
@*@@**@@@*
@*@*****@*
@**@*@****
*/
```

### EX_07 畫出下圖的相鄰陣列，以Dijkstra演算法，求A到各點的最短路徑？

:::info

+ *[最短路徑(一個頂點到多頂點Dijkstra)](http://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dijkstra.html)*

![](<https://i.imgur.com/f0wz9DD.jpg> =270x)

:::

*[Excel表格](https://drive.google.com/open?id=1KXoYjX6TqQjoLH7jeL639tvv1MwA8Pnr)*

### EX_08 畫出下圖的最小生成樹，其權重總和為？

:::info

+ *[最小生成樹(minimum spanning tree)](https://www.itread01.com/content/1545066724.html)*

  1. Kruskal演算法為一個使用貪婪法 (greedy method) 的演算法，一開始 為一空樹，每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入 樹中，直到所有點皆在樹中即完成。
  2. Prim演算法與Dijkstra演算法類似，屢次找出不在樹上，離樹最近的點。
 ![](<https://i.imgur.com/tjw9GuN.png> =350x)
:::

![](<https://i.imgur.com/XFuYhUI.jpg> =400x)

# *II 演算法*

## 1. 演算法效能

### EX_09 求500萬內的質數

:::info

+ [時間複雜度](https://jason-chen-1992.weebly.com/home/time-space-complexity)

:::

```cpp=
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n=5000000;

    for(int i=2;i<=n;i++)
    {
        bool prime=true;

        for(int j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {
                prime=false;
                break;
            }
        }
        if(prime)
            cout << i << " ";
    }
    return 0;
}
```

### EX_10 求1億以內的質數

:::info

+ [埃拉托斯特尼篩法](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)

```cpp=
1. #include <algorithm>
2. fill(陣列頭,陣列尾,數值);填入數值
```

:::

```cpp=
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;
bool Prime[100000001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n=100000000;
    fill(Prime,Prime+n+1,1);
    Prime[1]=false;

    for(int i=2;i<=sqrt(n);i++)
        if(Prime[i])
            for(int j=i*i;j<=n;j+=i)
                Prime[j]=false;

    for(int i=1;i<=n;i++)
        if(Prime[i])
            cout << i << " ";
    return 0;
}
```

## 2. 分而治之(Divid and Conquer)

:::success

+ [合併排序(Merge Sort)](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)
+ [排序法動畫](https://https://www.toptal.com/developers/sorting-algorithms)

:::

### EX_11

:::info

+ 對相當大的b、p、m，請寫一個有效率的演算法來計算 r = b^p mod m ( 1 <= b、p、m <= 32767 )

:::

:::danger

+ (A\*B)%C=(A%C)\*(B%C)→(B^P^)%M=(B^P/2^%M)*(B^P/2^%M)

:::

```cpp=
#include <iostream>

using namespace std;

int dc(int b,int p,int m)
{
    if(p==1)
        return b%m;
    else
        {
            int half=dc(b,p/2,m);

            if(p%2==0)
                return (half%m)*(half%m);
            else
                return (half%m)*(half%m)*(b%m);
        }
}

int main()
{
    int b,p,m;

    while(cin >> b >> p >> m)
    {
        cout << dc(b,p,m) << endl;
    }
    return 0;
}
```
