數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)（三）-創(chuàng)新互聯(lián)

• 集合，數(shù)學(xué)中默認(rèn)指無(wú)序集，用于表達(dá)元素的聚合關(guān)系。兩個(gè)元素只有屬于同一個(gè)集合與不屬于同一集合兩種關(guān)系。

  創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比余姚網(wǎng)站開(kāi)發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式余姚網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋余姚地區(qū)。費(fèi)用合理售后完善，十多年實(shí)體公司更值得信賴。

常見(jiàn)實(shí)現(xiàn)方式

unordered_set,unordered_map,并查集,哈希表,啟發(fā)式可并堆

• 在實(shí)際應(yīng)用中，可能需要關(guān)心集合元素順序。集合上定義偏序關(guān)系（即≤號(hào)），可構(gòu)成一個(gè)偏序集。有序性作為重要規(guī)律，可引入算法（如二分法）提升運(yùn)行效率。

偏序集實(shí)現(xiàn)方式

set，map，二叉排序樹(shù)（平衡二叉樹(shù)）

并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（disjoint sets）的合并及查詢問(wèn)題。

P1551 親戚

題目描述：

若某個(gè)家族人員過(guò)于龐大，要判斷兩個(gè)是否是親戚，確實(shí)還很不容易，現(xiàn)在給出某個(gè)親戚關(guān)系圖，求任意給出的兩個(gè)人是否具有親戚關(guān)系。

規(guī)定：xx 和 yy 是親戚，yy 和 zz 是親戚，那么 xx 和 zz 也是親戚。如果 xx，yy 是親戚，那么 xx 的親戚都是 yy 的親戚，yy 的親戚也都是 xx 的親戚。

思路:

1.初始化每個(gè)人的祖先就是自己

2.輸入兩個(gè)人,然后將兩個(gè)人的祖先合并

3.輸入,判斷兩個(gè)人的祖先是否相同(查找兩個(gè)人的祖先是否相同),輸出判斷的結(jié)果

這個(gè)題目是一個(gè)模板題，我們使用數(shù)組 fa 來(lái)存儲(chǔ)“代表”。代表具有傳遞性。當(dāng)查找代表時(shí)，需要遞歸地向上，直到代表為自身。

int find(int x) { // 查詢集合的“代表”
    if (x == fa[x])return x;
    return find(fa[x]);
}

當(dāng)合并兩個(gè)元素時(shí)，需先判斷兩者是否屬于同一集合。若否，則將其中一個(gè)集合的代表設(shè)置為另一方的代表。

void join(int c1, int c2) { // 合并兩集合
    // f1為c1的代表，f2為c2的代表
    int f1 = find(c1), f2 = find(c2);
    if (f1 != f2) fa[f1] = f2;
}

main函內(nèi)容

// 初始化
for (int i = 1; i<= n; ++i)
    fa[i] = i;
    // 合并親屬關(guān)系
    for (int i = 0; i< m; ++i) {
    cin >>x >>y;
    join(x, y);
}
// 根據(jù)代表是否相同，查詢親屬關(guān)系
for (int i = 0; i< p; ++i) {
    cin >>x >>y;
if (find(x) == find(y))
    cout<< "Yes"<< endl;
else
    cout<< "No"<< endl;
}

即成功AC題目

1. • 按秩合并

在執(zhí)行合并操作時(shí)，將更小的樹(shù)連接到更大的樹(shù)上，這樣的優(yōu)化方式就稱為“按秩合并”

2. • 路徑壓縮

在執(zhí)行查找的過(guò)程中，扁平化樹(shù)的結(jié)構(gòu)，這樣的優(yōu)化方式稱為“路徑壓縮“

// 一定不要忘了初始化，每個(gè)元素單獨(dú)屬于一個(gè)集合

void init() {
    for (int i = 1; i<= n; i++)
        f[i] = i;
}
int find(int x) { // 查詢集合的“代表”
    if (x == fa[x])return x;
    return fa[x] = find(fa[x]); // 路徑壓縮
}
void join(int c1, int c2) { // 合并兩個(gè)集合
    // f1為c1的代表，f2為c2的代表
    int f1 = find(c1), f2 = find(c2);
    if (f1 != f2) {
        if (size[f1]< size[f2]) // 取較大者作為代表
            swap(f1, f2);
        fa[f2] = f1;
        size[f1] += size[f2]; // 只有“代表”的size是有效的
    }
}

以上為路徑壓縮優(yōu)化后的并查集模板。

在并查集中同時(shí)使用上面的這兩種優(yōu)化方法，會(huì)將查找與合并的平均時(shí)間復(fù)雜度降低到常數(shù)水平（漸進(jìn)最優(yōu)算法）。

“散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問(wèn)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，這加快了查找速度。這個(gè)映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

1.字符串哈希：任意兩個(gè)字符串兩兩比較時(shí)間上必然是不可取的，時(shí)間復(fù)雜度。時(shí)間只允許處理每一個(gè)字符串僅一次。

2. 哈希函數(shù)：理論表明，并不是任意選擇 Hash 函數(shù)都能取得同樣的效果。

使用較大的質(zhì)數(shù)作為模數(shù)

模數(shù)越大，空間越多，越難以沖突。

同時(shí)，由于質(zhì)數(shù)除了1和自身外沒(méi)有其他因子，包含乘除運(yùn)算

的 Hash 函數(shù)不會(huì)因?yàn)橛泄蜃佣鴮?dǎo)致不必要的 Hash 沖突。

使用復(fù)雜的 Hash 函數(shù)

直接取模是最簡(jiǎn)單的方式。

但復(fù)雜的 Hash 函數(shù)可使值域分布更均勻，降低沖突的可能。

模運(yùn)算可以將數(shù)值折疊到一個(gè)小區(qū)間內(nèi)。但是還有一個(gè)問(wèn)題，折疊之后，不同的數(shù)可能映射到同一個(gè)區(qū)域，這一現(xiàn)象稱為 Hash 沖突。

Hash有三種解決方法：

1. 使用穩(wěn)健的 Hash 函數(shù)，效率最高，沖突率最高

2. 使用十字鏈表，完全解決沖突，效率較低

3. 使用 Multi-Hash，折中的方法

使用鏈表（或 std::vector 等結(jié)構(gòu)）將 Hash 沖突的元素保存起來(lái)。

這樣，查找一個(gè)元素時(shí)只需要與 Hash 沖突的較少元素進(jìn)行比較。

vectorhash[maxh];

// 以下是插入集合的方式，查找也是類似

void int insert(x){
    int h = f(x); //計(jì)算哈希值
    for (int i == 0, sz=hash[h].size(); i

用這種方式可以完全解決 Hash 沖突問(wèn)題。但是查找元素的復(fù)雜度會(huì)有所上升（取決于 Hash 沖突的次數(shù)）。

string s; // ......
int hash = 0;
for (int i = 0; s[i]; i++)
    // 計(jì)算base進(jìn)制下模mod的值作為hash值
    hash = ((long long)hash * base + s[i]) % mod;

unordered_sets; //創(chuàng)建Type類型的集合
s.insert(x); // 插入元素x
s.erase(x); // 刪除值為x的元素
s.erase(it); // 刪除it所指的元素
s.end(); // 返回末位哨兵的迭代器
s.find(x); // 查詢x；不存在則返回s.end()
s.empty(); // 判斷是否為空
s.size(); // 返回集合的大小

sets; // 創(chuàng)建一個(gè)Type類型的集合
s.insert(x); // 插入元素x
s.erase(x); // 刪除值為x的元素
s.erase(it); // 刪除it所指的元素
s.end(); // 返回末位哨兵的迭代器
s.find(x); // 查詢x；不存在則返回s.end()
s.empty(); // 判斷是否為空
s.size(); // 返回集合的大小
s.upper_bound(x); // 查詢大于x的最小元素
s.lower_bound(y); // 查詢不小于x的最小元素

unordered_mapm; // 創(chuàng)建T1到T2的映射
// 其中T1稱為鍵key，T2稱為值value
m.insert({a,b});// 創(chuàng)建映射a->b
m.erase(a); // 刪除key為a的映射
m.erase(it); // 刪除it所指的映射
m.end(); // 返回末位哨兵的迭代器
m.find(x); // 尋找鍵x；若不存在則返回m.end()
m.empty(); // 判斷是否為空
m.size(); // 返回映射數(shù)目
m[a] = b; // 修改a映射為b；若不存在則創(chuàng)建

mapm; // 創(chuàng)建一個(gè)T1到T2的映射
// 其中T1稱為鍵key，T2稱為值value
m.insert({a,b});// 創(chuàng)建映射a->b
m.erase(a); // 刪除key為a的映射
m.erase(it); // 刪除it所指的映射
m.end(); // 返回末位哨兵的迭代器
m.find(x); // 尋找鍵x；若不存在則返回m.end()
m.empty(); // 判斷是否為空
m.size(); // 返回映射數(shù)目
m[a] = b; // 修改a映射為b；若不存在則創(chuàng)建
m.upper_bound(x); // 查詢大于x的最小鍵
m.lower_bound(x); // 查詢不小于x的最小鍵

//我們可以使用數(shù)組來(lái)做這個(gè)題目，但是很明顯數(shù)據(jù)計(jì)算時(shí)間復(fù)雜度后會(huì)超時(shí)，由題目可以看每一個(gè)key都有一個(gè)value，我們就可以使用map來(lái)做這個(gè)題目，大大降低
#include