Alex_McAvoy

想要成为渔夫的猎手

【顺序表】

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

顺序表具有以下特点:

阅读全文 »

【逻辑结构】

线性表是具相同数据类型的 $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.$,采用内部排序得到的各个初始归并段,除最后一个外,长度都相同,其依赖于内部排序时可用内存工作区的大小

阅读全文 »