数据结构基础（三）-创新互联

• 集合，数学中默认指无序集，用于表达元素的聚合关系。两个元素只有属于同一个集合与不属于同一集合两种关系。

  创新互联公司-专业网站定制、快速模板网站建设、高性价比余姚网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式余姚网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖余姚地区。费用合理售后完善，十多年实体公司更值得信赖。

常见实现方式

unordered_set,unordered_map,并查集,哈希表,启发式可并堆

• 在实际应用中，可能需要关心集合元素顺序。集合上定义偏序关系（即≤号），可构成一个偏序集。有序性作为重要规律，可引入算法（如二分法）提升运行效率。

偏序集实现方式

set，map，二叉排序树（平衡二叉树）

并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。

P1551 亲戚

题目描述：

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

规定：xx 和 yy 是亲戚，yy 和 zz 是亲戚，那么 xx 和 zz 也是亲戚。如果 xx，yy 是亲戚，那么 xx 的亲戚都是 yy 的亲戚，yy 的亲戚也都是 xx 的亲戚。

思路:

1.初始化每个人的祖先就是自己

2.输入两个人,然后将两个人的祖先合并

3.输入,判断两个人的祖先是否相同(查找两个人的祖先是否相同),输出判断的结果

这个题目是一个模板题，我们使用数组 fa 来存储“代表”。代表具有传递性。当查找代表时，需要递归地向上，直到代表为自身。

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

当合并两个元素时，需先判断两者是否属于同一集合。若否，则将其中一个集合的代表设置为另一方的代表。

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

main函内容

// 初始化
for (int i = 1; i<= n; ++i)
    fa[i] = i;
    // 合并亲属关系
    for (int i = 0; i< m; ++i) {
    cin >>x >>y;
    join(x, y);
}
// 根据代表是否相同，查询亲属关系
for (int i = 0; i< p; ++i) {
    cin >>x >>y;
if (find(x) == find(y))
    cout<< "Yes"<< endl;
else
    cout<< "No"<< endl;
}

即成功AC题目

1. • 按秩合并

在执行合并操作时，将更小的树连接到更大的树上，这样的优化方式就称为“按秩合并”

2. • 路径压缩

在执行查找的过程中，扁平化树的结构，这样的优化方式称为“路径压缩“

// 一定不要忘了初始化，每个元素单独属于一个集合

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) { // 合并两个集合
    // 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是有效的
    }
}

以上为路径压缩优化后的并查集模板。

在并查集中同时使用上面的这两种优化方法，会将查找与合并的平均时间复杂度降低到常数水平（渐进最优算法）。

“散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

1.字符串哈希：任意两个字符串两两比较时间上必然是不可取的，时间复杂度。时间只允许处理每一个字符串仅一次。

2. 哈希函数：理论表明，并不是任意选择 Hash 函数都能取得同样的效果。

使用较大的质数作为模数

模数越大，空间越多，越难以冲突。

同时，由于质数除了1和自身外没有其他因子，包含乘除运算

的 Hash 函数不会因为有公因子而导致不必要的 Hash 冲突。

使用复杂的 Hash 函数

直接取模是最简单的方式。

但复杂的 Hash 函数可使值域分布更均匀，降低冲突的可能。

模运算可以将数值折叠到一个小区间内。但是还有一个问题，折叠之后，不同的数可能映射到同一个区域，这一现象称为 Hash 冲突。

Hash有三种解决方法：

1. 使用稳健的 Hash 函数，效率最高，冲突率最高

2. 使用十字链表，完全解决冲突，效率较低

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

使用链表（或 std::vector 等结构）将 Hash 冲突的元素保存起来。

这样，查找一个元素时只需要与 Hash 冲突的较少元素进行比较。

vectorhash[maxh];

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

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

用这种方式可以完全解决 Hash 冲突问题。但是查找元素的复杂度会有所上升（取决于 Hash 冲突的次数）。

string s; // ......
int hash = 0;
for (int i = 0; s[i]; i++)
    // 计算base进制下模mod的值作为hash值
    hash = ((long long)hash * base + s[i]) % mod;

unordered_sets; //创建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; // 创建一个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; // 创建T1到T2的映射
// 其中T1称为键key，T2称为值value
m.insert({a,b});// 创建映射a->b
m.erase(a); // 删除key为a的映射
m.erase(it); // 删除it所指的映射
m.end(); // 返回末位哨兵的迭代器
m.find(x); // 寻找键x；若不存在则返回m.end()
m.empty(); // 判断是否为空
m.size(); // 返回映射数目
m[a] = b; // 修改a映射为b；若不存在则创建

mapm; // 创建一个T1到T2的映射
// 其中T1称为键key，T2称为值value
m.insert({a,b});// 创建映射a->b
m.erase(a); // 删除key为a的映射
m.erase(it); // 删除it所指的映射
m.end(); // 返回末位哨兵的迭代器
m.find(x); // 寻找键x；若不存在则返回m.end()
m.empty(); // 判断是否为空
m.size(); // 返回映射数目
m[a] = b; // 修改a映射为b；若不存在则创建
m.upper_bound(x); // 查询大于x的最小键
m.lower_bound(x); // 查询不小于x的最小键

//我们可以使用数组来做这个题目，但是很明显数据计算时间复杂度后会超时，由题目可以看每一个key都有一个value，我们就可以使用map来做这个题目，大大降低
#include