# 資料結構 by: hush --- ## 介紹 ---- 電腦儲存資料的方法 可以想成是容器 ---- 以下將介紹實用的幾種資料結構 以及如何用STL召喚它們 --- ## 陣列(Array) ---- 太簡單所以不介紹，直接講超好用的工具**vector** ---- 中文叫向量(怪名字)，~~有了他array就沒用了~~，是一種動態大小的陣列，可以$O(1)$從後方新增元素 ，或是重新宣告大小 ---- | 常用函式 | 功能 | | --------------- | ------------------------------------ | | emplace_back(x) | 將元素x加入到vector後方 | | [i] | 查詢第i個位置的值 | | size() | 回傳vector有幾個元素 | | clear() | 清空vector的元素 | | resize(n[, x]) | 把vector大小變成n個[新增的元素填入x] | ---- 範例 ```cpp= #include<bits/stdc++.h> //#include<vector> using namespace std; int main() { vector<int> v(4,1);//v = {1, 1, 1, 1} cout << v[1] << '\n'; //1 v.emplace_back(7);//v = {1, 1, 1, 1, 7} cout << v[4] << '\n'; //7 } ``` --- ## 堆疊(Stack) ---- Stack 是一種後進先出（Last-In-First-Out, LIFO）的資料結構，每次取出的元素是最晚放進去的元素。  感謝Programiz的圖 ---- STL函式的stack可以實現這種資料結構 ---- | 常用函式 | 功能 | | -------- | ------------------------ | | empty() | 回傳stack是否為空 | | size() | 回傳stack有幾個元素 | | push(x) | 將元素x加入到stack的頂端 | | pop() | 將stack頂端的元素彈出(刪除) | | top() | 查詢stack的頂端的元素 | p.s.: 沒有clear() ---- 有空可以練習手刻，範例： ```cpp= int Stack[MAXN],head=-1; bool empty() { return head==-1; } void push(int x) { Stack[++head]=x; } void pop() { if (!empty()) head--; else cout << "pop T^T\n"; //不該執行到這行 } int top() { if (!empty()) return Stack[head]; cout << "top T^T\n"; //不該執行到這行 return 0; } ``` ---- - 練習題： [CSDC31](https://csdc.tw/problem/31/) [CSDC_Stack](https://csdc.tw/problems/?tag=stack) 拿去魔改遞迴 ---- CSDC31 AC code ```cpp= #include<bits/stdc++.h> //#include <stack> #define int long long using namespace std; signed main() { stack<int> s; string cmd; int n; while (cin >> cmd) { if (cmd[1]=='u') //push { cin >> n; s.push(n); } else //pop { cout << s.top() << endl; s.pop(); } } } ``` --- ## 佇列(Queue) ---- Queue 是一種先進先出（First-In-First-Out, FIFO）的資料結構，每次取出的元素是最早放進去的元素。  感謝Programiz的圖 ---- STL函式的queue可以實現這種資料結構 ---- | 常用函式 | 功能 | | -------- | -------------------- | | empty() | 回傳queue是否為空 | | size() | 回傳queue有幾個元素 | | push(x) | 將元素x加入queue的後端 | | pop() | 將queue前端的元素彈出(刪除) | | front() | 查詢queue的前端的元素 | | back() | 查詢queue的後端的元素 | p.s.: 從後端放入，一樣沒有clear() ---- 有空可以練習手刻，範例： ```cpp= int Queue[MAXN],front=0,back=-1; bool empty() { return front-1==back; } void push(int x) { Queue[++back]=x; } void pop() { if (!empty()) front++; else cout << "pop T^T\n"; //不該執行到這行 } int front() { if (!empty()) return Queue[front]; cout << "front T^T\n"; //不該執行到這行 return 0; } ``` ---- - 練習題： [CSDC155](https://csdc.tw/problem/155/) --- ## 鏈結串列(Linked-list) ---- Linked-list 是支援$O(1)$從容器中間(或前後)插入、刪除的線性資料結構，利用指標連結下一個元素。  感謝programiz的圖 ---- STL函式的list可以實現這種資料結構(雙向鏈結) ---- | 常用函式 | 功能 | | -------- | ------------------------ | | insert(it, x)| 將元素x加入到迭代器it的**前方** | | earse(it)| 將迭代器it指向的元素移除 | | emplace_back(x) | 將元素x加入到list後方 | | emplace_front(x) | 將元素x加入到list前方 | | pop_back() | 將list後方的元素彈出 | | pop_front() | 將list前方的元素彈出 | | front() | 查詢list的前端的元素 | | back() | 查詢list的後端的元素 | ---- 有空可以練習手刻，理論上應該用指標存下一個node(節點)，但是競賽上通常直接用陣列存 $next[i]=j代表節點i連接的下一個節點為j$ ---- 範例： ```cpp= int next[MAXN],head=0,tail=0; //單向鏈結, MAXN為最大數值(不能重複) void build() { memset(next,-1,sizeof(next)); } bool empty() { return nextp[head]==-1; } void push_back(int x) { next[tail]=x, next[x]=-1,tail=x; } void pop_front() { if (!empty()) { int tmp=head; head=next[head]; nxt[tmp]=-1; return } cout << "pop T^T\n"; //不該執行到這行 } void insert(int p,int x) { next[x]=next[p]; next[p]=next[x]; //順序不能錯 } void earse(int p) { if (head==p) head=next[head]; for (int i=head; next[i]!=-1; i=mext[i]) if (next[i]==p) { next[i]=next[p]; return; } } ``` ---- - 練習題： [zj_a870](https://zerojudge.tw/ShowProblem?problemid=a870) [zj_b938](https://zerojudge.tw/ShowProblem?problemid=b938) ---- zj_a870 AC code ```cpp= #include<bits/stdc++.h> #define int long long #define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0); using namespace std; list<string> a; //改成vector時間變兩倍 string cmd,x,n; signed main() { colinorz; while (cin >> cmd) { if (cmd[0]=='S') break; if (cmd[0]=='A' && cin >> x) a.emplace_back(x); else if (cmd[0]=='R' && cin >> x) { auto it=find(a.begin(),a.end(),x); if (it!=a.cend()) a.erase(it); } else { cin >> x >> n; a.emplace(find(a.begin(),a.end(),n),x); } } for (string& i : a) cout << i << ' '; } ``` --- ## 集合(Set) ---- Set 是一種不重複且有序的資料結構，常用來$O(log n)$找某個值是否出過，但常數偏大 ---- STL函式的set可以實現這種資料結構 ---- | 常用函式 | 功能 | | --------- | --------------- | | size() | 回傳set有幾個元素 | | insert(x) | 將元素x加入到set中 | | earse(it) | 將迭代器it指向的元素移除 | | count(x) | 回傳set有幾個x(只有0或1) | | lower_bound(x) | 對元素二分搜回傳$\ge$x的最小值 | ---- 手刻使用紅黑樹，或是hash table，不建議手刻除非你要做自主學習之類 ---- - 練習題： [zj_b050](https://zerojudge.tw/ShowProblem?problemid=b050) --- ## 映射(Map) ---- Map 是一種關聯式容器，用來存key-value(鍵-值對)，同時key不重複且有序的，常用來$O(log n)$去映射某些東西，但常數偏大 ---- STL函式的Map可以實現這種資料結構 ---- | 物件 | 功能 | | ------ |:---------- | | first | map的第一個型別(key) | | second | map的第二個型別(value) | ---- | 常用函式 | 功能 | | -------------- |:------------------------ | | size() | 回傳map在幾個元素 | | [x] | 取得x的對應值(也可用來賦值) | | insert({x,y}) | 將鍵值對x, y加入到map中 | | earse(it) | 將迭代器it指向的元素移除 | | count(x) | 回傳map有幾個key=x(只有0或1) | | lower_bound(x) | 對key二分搜回傳$\ge$x的最小值 | p.s.: 用[]賦值會覆蓋原先的值，insert則不會 ---- 手刻也是使用紅黑樹，或是hash table，不建議手刻除非你要做自主學習之類 ---- - 練習題： [zj_b515](https://zerojudge.tw/ShowProblem?problemid=b515) --- ## 堆積(Heap) ---- Heap 是一種完全二元樹，滿足每個節點都$>$它的所有子孫，常用來維護一個序列的極值$(O(log\ n))$ ---- STL函式的priority_queue可以實現這種資料結構 ---- | 常用函式 | 功能 | | -------- | ------------------------ | | push(x)| 將元素x加入到pq裡 | | pop() | 將pq裡最大的元素彈出 | | top() | 查詢pq裡最大的元素彈出 | ---- 有空可以練習手刻，範例我之後打上去 ---- 範例： ```cpp= ``` ---- - 練習題： [CSDC403](https://csdc.tw/problem/403/) ---- AC code ```cpp= #include<bits/stdc++.h> #define int long long #define itn int #define endl '\n' #define colinorz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0); #define pii pair<int,int> #define fi first #define se second using namespace std; priority_queue<pii> pq; signed main() { int n; cin >> n; while (n--) { int n,v; cin >> n >> v; pq.emplace(pii(v,n)); } int q; cin >> q; while (q--) { int c; cin >> c; if (c==1) cout << pq.top().se << endl; else if (c==2) { cout << pq.top().se << endl; pq.pop(); } else { int n,v; cin >> n >> v; pq.emplace(pii(v,n)); } } } ``` --- # 謝謝大家