資料結構（二）
Tire樹
高效地存儲和查找字元串的集合的資料結構。
1.存儲
在根節點之後像一棵樹一樣依次延伸，沒有就建立，有就沿着走下去；
例如我們存儲abcdef,abdef,aced,bcdf,bcff,abc這些字元串，我們還需要在一個字元串結尾處标記來确認查找。
如下圖所示：
2.查找
例如查找aced,依次從根節點往下找都是存在的，而且結尾處有标記則查找到了；再例如查找abcf,我們從c找f這部是不存在的是以查找不了；例如查找abcd，雖然都能找到但結尾處沒有标記是以查找不了。
代碼實作存儲和查找：
字元串統計
建議看圖了解
#include <iostream>
using namespace std;
const int N = 100010;
//son[N][26]中的26表示每個節點最多向外擴充出26個點即26個英文字母
int son[N][26],cnt[N],idx; //cnt[i]表示以i結尾的字元串個數，idx即為用到的節點
char str[N];
void insert(char *str)
{
int p = 0;
for(int i = 0; str[i]; i++) //當字元串結尾不為'\0'即不結束時
{
int u = str[i] - 'a' ; //把a~z的字母映射成0~25的數字
if(!son[p][u]) son[p][u] = ++idx; //下一節點沒有要存儲的字母的話就建立
p = son[p][u]; //不管建立與否，繼續指派走下一節點
cnt[p] ++; //p最終即為字元串的結尾字母，個數++
}
int query(char *str)
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if(!son[p][u]) return 0; //不存在子節點即找不到該字元串
p = son[p][u]; //走回去
}
return cnt[p];
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char op[2];
scanf("%s%s",op,str);
if(*op == 'I') insert(str);
else printf("%d\n",query(str));
}
return 0;
}
最大異或對
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 3100010;
int n;
int a[N], son[M][2], idx;
void insert(int x)
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int &s = son[p][x >> i & 1]; //&: 二進制“與”(都為1時，結果是1，否則是0。)
if (!s) s = ++ idx;
p = s;
}
}
int search(int x)
{
int p = 0, res = 0;
for (int i = 30; i >= 0; i -- )
{
int s = x >> i & 1;
if (son[p][!s])
{
res += 1 << i;
p = son[p][!s];
}
else p = son[p][s];
}
return res;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
{
scanf("%d", &a[i]);
insert(a[i]);
}
int res = 0;
for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));
printf("%d\n", res);
return 0;
}
并查集
用于合并兩個集合，以及查詢兩元素是否在同一集合下
連通塊中點的個數
此題增加了判斷集合個數
#include <iostream>
using namespace std;
const int N = 100010;
int p[N],cnt[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) p[i] = i,cnt[i] = 1; //初始化根節點,且表明目前集合個數為1
while(m--)
{
string op;
int a,b;
cin >> op;
if(op == "C")
{
cin >> a >> b;
a = find(a),b=find(b);
if(a!=b)
{
p[a] = b;
cnt[b] += cnt[a];
}
}
else if(op == "Q1")
{
cin >> a >> b;
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}
堆
是一棵完全二叉樹
除了最後一層節點外，上面所有節點都是滿的不存在空的，最後一層節點是從左到右排列
小根堆：每個點都是小于等于左右兒子的，是以根節點就是最小數
存儲方式：用一維數組
1為根節點，2x為左兒子 2x+1為右兒子
基本操作：down(x)往下調整 ；up(x)向上調整
在形成三角形的三個數中選擇最小的數和大的數交換，大的下下移，小的上移，并且上移隻要跟根節點比較即可。
操作：（下标從1開始）
1.插入一個數：在堆的最後一個數加上x,再不斷上移
2.求集合中的最小數：即第一個數
3.删除最小數：把最後一個元素覆寫到堆頂去，然後把最後一個元素删掉，最後down堆頂元素
4.删除任意一個數：和操作3相似，把第k個元素覆寫到堆頂，删除第k個元素，最後執行up或down操作
5.修改任意一個數：把第k個元素變成x，然後執行down或up操作
堆排序
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
swap(h[u], h[t]);
down(t);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
cnt = n;
for (int i = n / 2; i; i -- ) down(i);
while (m -- )
{
printf("%d ", h[1]);
h[1] = h[cnt -- ];
down(1);
}
puts("");
return 0;
}
增加了插入第k個元素
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 100010;
int h[N], ph[N], hp[N], cnt;
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
int main()
{
int n, m = 0;
scanf("%d", &n);
while (n -- )
{
char op[5];
int k, x;
scanf("%s", op);
if (!strcmp(op, "I"))
{
scanf("%d", &x);
cnt ++ ;
m ++ ;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
else if (!strcmp(op, "DM"))
{
heap_swap(1, cnt);
cnt -- ;
down(1);
}
else if (!strcmp(op, "D"))
{
scanf("%d", &k);
k = ph[k];
heap_swap(k, cnt);
cnt -- ;
up(k);
down(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}
return 0;
}