【概述】

在并查集的寻找结点 x 的根结点的过程中，是不停的通过 father[] 数组去向上寻找其根结点

1
2
3
4
5

void Find (int x) { //递归实现
    if (father[x] != x) //x不是集合的代表时
        return Find(father[x]); //以当前结点的父结点进一步查询
    return father[x];
}

【概述】

并查集（Union-Find Set）是一种用于分离集合操作的抽象数据类型，其处理的是集合（set）之间的合并及查询问题

在并查集中，借助一个数组 father[] 来表示每个结点的父结点，即 father[i] 存储结点 i 的父结点编号

【引入】

在 外部排序 中讨论过，增大归并路数 $k$ 或减少初始归并段个数 $r$，都可以减少归并趟数 $S$，进而减少 I/O 次数，以提高外部排序速度

若总的记录个数为 $n$，每个归并段长度为 $l$，则归并段个数 $\left \lceil \frac{n}{l} \rceil \right.$，采用内部排序得到的各个初始归并段，除最后一个外，长度都相同，其依赖于内部排序时可用内存工作区的大小

【signal 信号】

对于一个进程来说，通过给予该进程一个信号（signal），可以告知该进程要做什么

通过 man7 signal 可以查看 Linux 中支持的所有 signal 信号，常见的信号如下表

【工作管理的概念】

工作管理（Job Control）是在登录系统取得 Bash Shell 后，在单一终端机下同时进行多个工作的行为管理

在进行工作管理的行为中，其实每个工作都是目前 Bash 的子进程，即彼此之间存在相关系，也就是说，无法以工作管理的方式由 tty1 的环境去管理 tty2 的 Bash

【ps 命令】

命令格式

ps 命令可用于查看当前系统正在运行的进程，其命令格式为：ps [选项]

【程序与进程】

在 Linux 中，程序一般放置于磁盘中，然后通过用户的执行来触发，触发后会加载到内存中称为一个个体，这个个体即被称为进程

为了让系统可对进程进行管理，系统会给予这个进程的触发者的权限与属性，并包括进程所需要的脚本、文件数据等，最后再给予一个 PID，系统会根据 PID 来判断该进程是否具有权限进行工作

【例行性工作调度】

在 Linux 中，存在两种工作调度方式，一种是例行性的，即每隔一定周期执行的工作，另一种是突发性的，即这次工作完成后就结束调度

在 Linux 中，例行性工作调度依靠 Crond 服务的支持，通过 crontab 命令来实现

【单一工作调度】

在 Linux 中，存在两种工作调度方式，一种是例行性的，即每隔一定周期执行的工作，另一种是突发性的，即这次工作完成后就结束调度

在 Linux 中，单一工作调度依靠 atd 服务的支持，通过 at 命令来实现

【PAM 模块】

在过去，当想要对用户进行验证时，需要用户输入用户名、密码，然后通过自行编写的程序来判断账号密码是否匹配

因此，经常要使用不同的机制来判断账号密码，这使得一台主机上有多个不同的认证系统，可能造成账号密码不同步的验证问题