各位抱歉，由於最近筆者時間分配不佳，導致文章來不及在鐵人賽第三天達成
不過如果我有空閒，一樣會繼續寫作
簡單說，它是一種對資料的有系統的整理，
通常一個資料結構的誕生是為了另在其之上運作的演算法，能更好的進行操作，或是為了提昇演算法的效率，甚至是為了方便解釋演算法的運作(抽象化)。
每種資料結構一般都是針對：新增，刪除，修改，查詢 這些功能的效率及操作上的追求。
要搭公車之前，都是先排隊進入公車站，等到公車到來時，在從公車站出去搭上公車；
由此，公車站可以作為一種資料結構，人可類比為欲儲存之資料
source
此種資料結構稱作隊列 (queue)；擁有先進先出 (first in, first out) 的特性，
例如在郵局要辦事，會先從機器拿號碼紙等叫號，這時候就是用 Queue 去儲存編號。
下面給出隊列的簡易實作程式碼：
int Q[maxn], front_idx = 0, back_idx = 0;
void enqueue(int data)
{ Q[back_idx++] = data; }
int front()
{ return Q[front_idx]; }
bool empty()
{ return front_idx == back_idx; }
void dequeue()
{ if(!empty()) front_idx++; }
當我們操作多次 enqueue 與 dequeue，會使得 front_idx 最終會碰到陣列邊界，這樣會導致能儲存的資料量變小。
觀察發現，當 front_idx 增加，相當於丟掉以前的資料，這時候就有舊的空間空出來了，該如何使用這塊舊空間呢？
直接的，讓 back_idx 碰到邊界後回去初始位置就可以了： 這種資料結構稱作環狀隊列
還有種變種隊列，叫做雙端隊列(Double ended queue)，他可以從前面或後面 enqueue 或 dequeue。
考慮將一堆鬆餅每次只放一片疊到盤子上，則最後放上去的鬆餅將會是最上層的鬆餅，如果要吃也會依序從最上層開始拿。
source
此種鬆餅(資料)的放法，拿法，是種稱做堆疊 (stack) 的資料結構；有後進先出 (last in, first out) 的特性，
下面給出隊列的簡易實作程式碼：
int S[maxn], top_idx = -1;
void push(int data)
{ S[++top_idx] = data; }
int top()
{ return S[top_idx]; }
bool empty()
{ return top_idx == -1; }
void pop()
{ if(!empty()) top_idx--; }
玩某些撲克牌遊戲時常常會有要在手中整理牌的動作，將一張牌拿起與將一張牌插到某個位置，支援這兩個行為的資料結構稱為連結串列 (Linked list)
source
連結串列比較複雜點，我們需要造出兩種結構：
struct node {
int data;
node *prev, *next;
} *list[maxn];
list[0] 不當一般資料使用，它用來指向連接串列的頭for (int i = 0; i < N; i++) {
node *p = new node;
if(i) {
list[i-1]->next = list[i] = p;
list[i]->prev = list[i-1];
} else list[0] = p;
}
list[0]->perv = list[N-1];
list[N-1]->next = list[0];
在最後我將 list[0](head_pointer) 與串列尾部連接起來，是為了下面兩個函式寫法上的方便(?
當擁有這樣的結構，拔除節點和插入節點只需要 O(1)：
void remove(int idx) {
list[idx]->prev->next = list[idx]->next;
list[idx]->next->prev = list[idx]->prev;
list[idx]->next = list[idx]->prev = NULL;
}
void insert(int idx1, int idx2) {
list[idx2]->next = list[idx1]->next;
list[idx1]->next = list[idx2];
list[idx2]->next->prev = list[idx2];
list[idx2]->prev = list[idx1];
圖 (Graph)，是一個由邊 (Edge)集合與點 (Vertex)集合所組成的資料結構。
Graph 的術語：
在討論圖的邊，常會有 u 是邊起點與 v 是邊終點的慣例用符
通常 graph 用鄰接表 (adjacency list)或鄰接矩陣 (adjacency matrix)儲存資料
struct edge {
int u, v, w; //兩個相鄰點與邊權重
edge(int a, int b, int c): u(a), v(b), w(c){}
};
vector<edge> graph;
int main() {
:
.
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &u, &v, &w);
graph.push_back(edge(u, v, w));
}
}
int graph[MAXN][MAXN];
int main() {
:
.
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &u, &v, &w);
graph[u][v] = w;
}
}
樹 (Tree)，這個資料結構在圖像化看起來像顆倒掛的樹，根在上，而葉子在下。
Tree 的術語及特點：
中文稱互斥集(複數)，是指兩兩集合之間並沒有相同元素的一群集合。
常用來處裡"分類"問題；實作此資料結構我們可以稱作併查森林 (Union-Find Forest)。
一般在做集合操作，最直觀的想法就是將每個集合有哪些元素，都用 Array, Vector, Binary Search tree 或 List 紀錄起來
而一般常見的集合操作有，新增、刪除、(取)聯集、取交集、取集合大小，可以稍微思考一下這些操作的複雜度要多少。
但併查森林則是將紀錄方式從 "每個集合有哪些元素" 改為 "每個元素屬於哪個集合" (這操作太神啦
void disjoin_set_init() {
for (int v = 1; v <= N; v++) group[v] = v;
}
int Find(int v) {
if (v == group[v]) return v;
return group[v] = Find(group[v]); //Path Compression
}
假設有 1 ~ 5 元素，其中 1、2 一組，3、4、5 一組。
我下 Find(5) 指令，那麼他要回傳給我 3group[v] = Find(group[v]); 因為在子節點回溯時順便把最上層 group 的標號(也就是 3)給了所有有拜訪過的節點，
於是 disjoint set 的關係圖變成：
void Union(int u, int v) {
group[Find(u)] = Find(v);
}
若對下圖這樣的情況，我做 Union(4, 2);
則上圖會變為下圖這樣：
還有種方式稱作 Union by rank，將 rank 大的樹合併到 rank 小的樹下，可以加快許多。
練習：
UVa OJ 10583 Ubiquitous Religions
UVa OJ 11987 Almost Union-Find
稍微抱怨一下，IT邦為什麼沒有 latex 可以用QQ
而且超連結貌似含一些特殊字元就會失效QQ
希望之後能少耍點廢，盡量產文章和打比賽
老實說覺得這樣一篇的內容好像有點多，是不是應該拆成幾份談會比較好啊（
在之後未來某篇應該會介紹更高級的資料結構，例如 heap, RMQ, BIT, treap 之類的
如果內容有錯誤，請大家幫個忙指正一下！
那麼感謝大家觀看，咱們改天見！
編輯框上面好像有個「加入數學公式」，雖然還是超級不方便但可以將就一下XD
哦哦哦，這已經比打好截圖在貼上好很多了d(`･∀･)b
iThome鐵人賽
看影片追技術