# 初階資料結構 - 講師：覃毅翔 --- ## 進入課程之前 先來講講複雜度的概念 詳細說明可以看[這裡](https://www.csie.ntu.edu.tw/~sprout/algo2020/homework/week2.pdf) * O * $\Omega$ * $\Theta$ * o * $\omega$ ---- ## Big-O 表示複雜度的上界 對於$f(n)$找到一個函數$g(x)$ $\begin{array}{clcr}f(n)\in O(g(n))\\若且唯若\\\exists c,n_0\in\mathbb{R}^+,\forall n\geq n_0有f(n) \leq cg(n) \end{array}$ ---- ## Big-O 看個範例 $f(n)=87n^2+31415926n+7122$ 當n很大的時候，可以想像31415926n+7122會遠小於$87^2$，而87又是一個常數，我們可以說 $f(n)\in O(n^2)$ ---- ## Big-$\Omega$ 有上界就會有下界 對於$f(n)$找到一個函數$g(x)$ $\begin{array}{clcr}f(n)\in \Omega(g(n))\\若且唯若\\\exists c,n_0\in\mathbb{R}^+,\forall n\geq n_0有f(n) \geq cg(n) \end{array}$ ---- ## Big-$\Theta$ 最嚴格的函數，求複雜度其實都是用這個 需同時滿足 $f(n)\in O(g(n))$ $f(n)\in \Omega (g(n))$ 才可以說 $f(n)\in \Theta (g(n))$ --- ## 先備知識 * C++語法 * 陣列 * 指標 * 如何GOOGLE --- ## 關於資料結構 * push：將資料存入資料結構中 * pop：將資料從資料結構中取出 * query：各種查詢( Ex:size(), empty() ) * 分清楚每個資料結構的push、pop語法 ---- ## 關於資料結構 * 資料結構是一種工具，在程式設計上我們根據不同用途來選擇不同的資料結構，並考慮其時間、空間，甚至是 coding 複雜度。 * 由於他是一種工具，儘管某些題目純需要資料結構就能 AC，但其實它們常常需要搭配不同的演算法來解題。 --- ## 關於資料結構 #### STL * C++內建會有許多方便的資料結構模板，稱為標準模板庫(<font color="#f00">S</font>tandard <font color="#f00">T</font>emplate <font color="#f00">L</font>ibrary) * 它可以讓你很方便的使用資料結構，但由於某須些特殊的原因還是學習一下實做資料結構的方式會比較好(? --- ## 關於資料結構 #### 迭代器(iterator) * 類似struct的東東 * 宣告一個迭代器，必須在把模板打完後在後面加上::iterator 變數名稱 EX : list< int >::iterator x; * 迭代器的元素 : *x * 迭代器的位址 : &x ---- ```cpp #include<bits/stdc++.h> using namespace std; int main(){ list<int> li; li.push_back(1); li.push_back(2); li.push_back(3); list<int>::iterator E, B; E=li.end(); B=li.begin(); cout << "B: " << &B << " " << *B << "\n"; cout << "E: " << &E << " " << *E << "\n"; B++, E--; cout << "B: " << &B << " " << *B << "\n"; cout << "E: " << &E << " " << *E << "\n"; } ``` <span> ```cpp B: 0x70fdd0 1 E: 0x70fde0 0 B: 0x70fdd0 2 E: 0x70fde0 3 ``` <!-- .element: class="fragment" data-fragment-index="1" --></span> ---- 但auto就可以做完所有的事了 ```cpp #include<bits/stdc++.h> using namespace std; int main(){ list<int> li; li.push_back(1); li.push_back(2); li.push_back(3); auto E, B; E=li.end(); B=li.begin(); cout << "B: " << &B << " " << *B << "\n"; cout << "E: " << &E << " " << *E << "\n"; B++, E--; cout << "B: " << &B << " " << *B << "\n"; cout << "E: " << &E << " " << *E << "\n"; } ``` --- ## Stack * 堆疊 * first in last out * 疊盤子 ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ---- ## Stack #### STL ```cpp #include<stack> //標頭檔 int main(){ T data; stack<T> s; //建構式 s.push(data); //將data移入stack中 s.pop(); //將最後加入的元素從stack中移除 s.top(); //回傳最後加入的元素 s.size(); //回傳stack內的元素個數 s.empty(); //回傳stack內是否為空 } ``` ---- ## Stack #### 實做 ```cpp int s[MAXN], top=-1; void push(int data){ s[++top]=data; } void pop(){ if(top==-1) return; top--; } int query(){ assert(top>-1); return s[top]; } ``` ---- ## Stack #### 習題 1. [(ZJ b923)](https://zerojudge.tw/ShowProblem?problemid=b923) 實作 stack 2. [(ZJ c123)](https://zerojudge.tw/ShowProblem?problemid=c123) stack 的應用 4. [(ZJ a565)](https://zerojudge.tw/ShowProblem?problemid=a565) stack 的應用 5. [(ZJ a813)](https://zerojudge.tw/ShowProblem?problemid=a813) stack 的經典應用 --- ## Queue * 佇列 * first in first out * 排隊 ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ---- ## Queue #### STL ```cpp #include<queue> //標頭檔 int main(){ T data; queue<T> q; //建構式 q.push(data); //將data移入queue中 q.pop(); //將最後加入的元素從queue中移除 q.front(); //回傳最後加入的元素 } ``` ---- ## Queue #### 實做 ```cpp int q[MAXN], l=0, r=-1; void push(int data){ q[++r]=data; } void pop(){ if(r<1) return; l++; } int query(){ assert(r>=1); return q[l]; } ``` ---- ## Queue * 你各位想一下，如果不斷地 push、再 pop， 那 queue 不就會讀到不該讀的記憶體了? ---- ## Queue * 你各位想一下，如果不斷地 push、再 pop， 那 queue 不就會讀到不該讀的記憶體了? * 於是環狀queue就出現啦 ---- ## Queue #### 環狀queue實做 ```cpp int q[MAXN], l=0, r=-1; void push(int data){ q[(++r)%MAXN]=data; } void pop(){ if(r<1) return; l++; } int query(){ assert(r>=1); return q[l%MAXN]; } ``` ---- ## Queue #### 習題 1. [(UVA 10935)](https://vjudge.net/problem/UVA-10935) 實做 queue 2. [(ZJ c223)](https://zerojudge.tw/ShowProblem?problemid=c223) queue 的演算法優化 --- ## Linked List * 鏈結串列 * 基本單元:Node(data + pointer) * 將很多Node接起來 * 指標互相指來指去 * 先熟悉struct跟pointer再來學如何實做 ----  ---- ## Linked List #### STL ```cpp #include<list> //標頭檔 int main(){ T data; list<T> l; //建構式 l.push_front(data); //將data移入list的最前面 l.push_back(data); //將data移入list的最後面 l.pop_front(); //將list最前面的元素移除 l.pop_back(); //將list最後面的元素移除 l.front(); //回傳list最前面的元素 l.back(); //回傳list最後面的元素 l.insert(iterator it,n,data); //在it指的那項的前面插入n個data並回傳指向data的迭代器。 //可不輸入n值，預設為插入一個。 //複雜度 O(n)。 l.erase(iterator first,iterator last) //把 [first,last) 刪掉，如果沒有指定 last，會視為只刪除 first //回傳 last。 //複雜度與砍掉的數量呈線性關係 } ``` ---- ## Linked List #### 實做 實做不難，懂指標就好 ```cpp struct node{ int data; node *back=null, *next=null; } ``` ---- ## Linked List #### 習題 1. [(ZJ b938)](https://zerojudge.tw/ShowProblem?problemid=b938) 實做linked list 2. [(ZJ d718)](https://zerojudge.tw/ShowProblem?problemid=d718) 大型模擬 3. [(TIOJ 1225)](https://tioj.ck.tp.edu.tw/problems/1225) 搭配greedy --- ## Vector * 動態陣列 * STL簡單好用 * 實做蠻複雜的，有興趣自己GOOGLE ---- ## Vector #### STL ```cpp #include<vector> //標頭檔 int main(){ T data; vector<T> v; //建構式 v.push_back(data); //將data移入vector的最後面 v.pop_back(); //將vector最後面的元素移除 v[i]; //回傳第i個元素 v.back() //回傳vector最後面的元素 v.resize(n,T a) //強制將vector的長度改為n，若比原本長，則後面加a直到長度為n， //若比原本短則將多出的部分捨去,若無指定a將會預設為T的預設值。 v1(比較運算子)v2 //回傳比較v1、v2字典序的結果，複雜度O(max(v1_size, v2_size)) } ``` --- ## String * 原身是vector< char > * 因為很常用，所以就拿出來優化 ---- ## String #### STL ```cpp #include<string>//標頭檔 int main(){ string s1, s2;//建構式 s1=s2;//讓s1變的跟s2一樣，複雜度通常是O(size_s1+size_s2) s1+=s2;//在s1的尾端加上s2，複雜度通常是O(size_s1+size_s2) getline(cin, s1, char c); //輸入字串至s1，直到讀到字元c。未指定c時讀至換行符號 } ``` ---- ## String #### 習題 1. [(ZJ a011)](https://zerojudge.tw/ShowProblem?problemid=a011) getline的應用 2. [(ZJ d098)](https://zerojudge.tw/ShowProblem?problemid=d098) Hint : stringstream --- ## Deque 雙向佇列 ---- ## Deque #### STL ```cpp #include<deque> //標頭檔 int main(){ T data; deque<T> dq; //建構式 dq.push_front(data); //將data移入deque的最前面 dq.push_back(data); //將data移入deque的最後面 dq.pop_front(data); //將deque最後面的元素移除 dq.pop_back(data); //將deque最後面的元素移除 } ``` ---- ## Deque #### 習題 1. [(TIOJ 1566)](https://tioj.ck.tp.edu.tw/problems/1566) 2. [(TIOJ 1618)](https://tioj.ck.tp.edu.tw/problems/1618) --- ## Pair 把兩個變數綁起來的方便工具，支援字典序比較。 ---- ## Pair #### STL ```cpp #include<utility> //標頭檔 int main(){ T1 a; T2 b; pair<T1, T2> p; //建構式，S1跟S2可為不同型態 p.first(); //回傳p的第一個值 p.second(); //回傳p的第二個值 make_pair(T1 a, T2 b); //回傳一個(a, b)的pair } ``` --- ## Priority Queue #### 優先佇列 * 維護一群數字的極值 * 插入數字 * 刪除極值 * 詢問極值 ---- ## Priority Queue #### STL ```cpp #include<queue> //標頭檔 int main(){ T data; priority_queue<int> pq; //最大堆建構式(維護最大值)(top=最大值) priority_queue<int, vector<int>, less<int>> pq; //最大堆建構式(維護最大值)(top=最大值) priority_queue<int, vector<int>, greater<int>> pq; //最小堆建構式(維護最小值)(top=最小值) pq.push(data); //加入元素data，複雜度O(log size) pq.pop(); //刪除極值，複雜度O(log size) pq.top(); //回傳最大值，複雜度O(1); } ``` ---- ## Priority Queue #### 習題 1. [(ZJ 606)](https://zerojudge.tw/ShowProblem?problemid=b606) 2. [(TIOJ 1911)](https://tioj.ck.tp.edu.tw/problems/1911) 3. [(TIOJ 1231)](https://tioj.ck.tp.edu.tw/problems/1231) --- ## Balance Search Tree * 查找是否存在元素x * 查找大於x的最小值 * 查找小於x的最大值 * set、map ---- ## Set * O(log size)插入、刪除、查找元素 * 保證不存在重複元素 * 通稱元素的值為鍵值(Key) ---- ## Set #### STL ```cpp #include<set> //標頭檔 int main(){ T data; set<T> s; //建構子 s.insert(data); //加入元素data，複雜度O(log size) s.erase(iterator first, iterator last); //刪除[first,last)，若無指定last則只刪除first //複雜度O(log size+元素個數)。 s.erase(data); //刪除鍵值data，複雜度O(log size); s.find(data); //回傳指向鍵值data的迭代器，若不存在則回傳s.end() //複雜度O(log size) s.lower_bound(data); //回傳指向第一個鍵值大於等於data的迭代器，複雜度O(log size) s.upper_bound(data); //回傳指向第一個鍵值等於data的迭代器，複雜度O(log size) } ``` ---- ## Map #### STL ```cpp #include<map> int main(){ T1 k; map<T1, T2> m; pair<T1, T2> data; m[k]; /* 存取鍵值k對應的值 若k沒有對應的值，會插入一個元素，使k對應到預設值並回傳之 複雜度O(log size) */ m.insert(data) /* 若沒有鍵值為data.first的值 插入一個鍵值為data.first的值對應到data.second 回傳一個pair，first是指向剛插入的元素的迭代器、second是true 若已經有了 回傳一個pair，first是指向原先元素的迭代器、second是false 複雜度 O(log size)。 */ } ``` ---- ## Map #### 習題 [(ZJ d518)](https://zerojudge.tw/ShowProblem?problemid=d518):map+string。 [(TIOJ 1911)](https://tioj.ck.tp.edu.tw/problems/1911):multiset [(TIOJ 1161)](https://tioj.ck.tp.edu.tw/problems/1161) [(TIOJ 1221)](https://tioj.ck.tp.edu.tw/problems/1221) ---- ## Balance Search Tree #### 缺點 1. 常數過大 2. 無法重複存取元素 ---- ## Balance Search Tree #### 缺點 1. 常數過大 (O(log size))。 * 改成 unordered_set 、 unordered_map ，即可降低常數 (可說是少掉一個 log)。 * 差異:喪失掉 lower_bound 及 upper_bound 的功能，迭代器只能做 ++ 運算，遍歷的時候也不會依據大小遍歷 (原本會)。 * 需注意:標頭檔為 <unordered_set> 和 <unordered_map> ---- 2. 無法存取重複元素。 * 改成 multiset，multimap即可加入重複元素。 * 差異:map 喪失掉下標功能 (m[k]) * equal_range(k)會回傳一個iterator的pair，第一項代表lower_bound(k)，第二項代表 upper_bound(k)。這兩項迭代器之間的項就是那些鍵值是k的項 * count(k)會回傳鍵值 k 的元素有幾個。 * erase(k)會把鍵值是k的全部刪光，所以如果只要刪一個的話必須改成s.erase(s.find(k)) --- ## Bitset 由於 bool 陣列的大量使用和記憶體缺陷 (一個 bool 用到的記憶體其實跟 char 一樣大)，於是他被拿了出來並做了極好的優化。 ---- ## Bitset #### STL ```cpp #include<bitset> //標頭檔 int main(){ bitset<N> b(a); //用a初始化一個長度為N(不可為變數)的bitset //a可以是unsignedlong、string或C式字串 //如果沒有指定a，或者如果b有一些地方沒被a初始化，那些地方預設為0 b.count(); //回傳b有幾個位元是1。複雜度 O(N) b[i]; //存取第i位 b.set(); //將所有位元設成1。複雜度 O(N) b.reset(); //將所有位元設成0。複雜度 O(N) b.flip(); //將所有位元的0、1互換。複雜度 O(N) b.to_string(); //回傳一個字串和b的內容一樣。複雜度 O(N) b.to_ulong(); //回傳一個 unsigned long 和b的內容一樣(在沒有溢位的範圍內) //複雜度 O(N) b.to_ullong(); //同上，改成unsigned long long b(位元運算); //不管是一元還是二元的位元運算都可以。 //如果是兩個 bitset 的二元位元運算，兩個 bitset 的長度需一致 //複雜度 O(N) } ``` ---- ## Bitset bitset 不是容器，而且它也沒有迭代器。通常而言，如果要估計常數的話，相較於直接使用陣列，空間是 1/8、count 約是 1/6、位元運算約是 1/30。當然這些都不是絕對的。要注意的是，上述的複雜度沒有明文規定，不過通常是如此。