# **資料結構與演算法(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
下圖的前序、中序、後序走訪分別為？
:::
```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)。
:::
### 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)*
:::
## 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)來實作。
:::
### 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)*
:::
*[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演算法類似，屢次找出不在樹上，離樹最近的點。
:::
# *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;
}
```
Sign in with Wallet
Connect another wallet