【顺序表】

线性表的顺序存储又称顺序表，其使用一组地址空间连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两元素在物理存储空间上也相邻

顺序表具有以下特点：

【逻辑结构】

线性表是具相同数据类型的 $n$ 个数据元素的有限序列，其中，相同数据类型意味着每个数据元素所占的存储空间相同，数据元素个数 $n$ 为线性表的长度，当 $n=0$ 时称为空表，反之 $n\neq 0$ 时称为非空表

一个非空表常记为：

【算法】

算法是对特定问题求解步骤的描述，是指令的有限序列，每个指令表示一或多个操作，其具有以下特性：

• 有穷性：能在有穷步、有穷时间内执行完毕
• 确定性：相同输入会获得相同输出
• 可行性：算法是可行的
• 输入：具有零到多个输入
• 输出：具有一到多个输出

【基本概念】

数据结构的基本概念如下：

1. 数据：信息载体，能输入到计算机且能被计算机识别处理的集合
2. 数据元素：基本数据单位，作为一个整体考虑处理，由若干数据项组成
3. 数据项：构成数据元素的、不可分割的最小单位
4. 数据对象：数据的子集，具相同性质的元素的集合
5. 数据结构：相互存在一种或多种特定关系的数据元素的集合
6. 数据类型：一个值的集合与定义在此集合上的一组操作
   • 原子类型：值不可再分，如 int、float、double
   • 结构类型：值可分为若干成分，如 struct
   • 抽象数据类型(ADT)：数学化语言定义逻辑结构与运算，与具体实现无关，用于定义完整数据结构

【带权并查集】

带权并查集是结点存有权值的并查集，每个元素的权值通常描述其与并查集中祖先的关系，这种关系如何合并，路径压缩时就如何压缩

与并查集相比，带权并查集可以推算集合内点的关系，而一般并查集只能判断属于某个集合

在并查集中，删除操作是指删除掉并查集中的一个结点

在所有结点都直接连接在根结点上的完美并查集上，理论上只要把要删除的节点的上级重新指向自己就可以了

但实际情况中，并查集形成的树的形态都是不可预估的，如果一个结点非叶结点，将该结点直接删除，会将其与其子孙结点一起删除

【并查集的启发式合并】

在并查集执行合并操作 Union()，将两个集合合并为一个时，无论将哪一个集合连接到另一集合的下面都是正确的，但不同的连接方法存在时间复杂度的差异

具体来说，如果将一棵结点数、深度都较小的集合树，连接到一棵更大的集合树下，显然相比于另一种连接方案，在接下来执行查找操作 Find() 时，时间复杂度会更小

【概述】

在并查集的寻找结点 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.$，采用内部排序得到的各个初始归并段，除最后一个外，长度都相同，其依赖于内部排序时可用内存工作区的大小