顺序表 发表于 2018-09-06 分类于 OI&ACM , 数据结构 , 线性表 本文字数: 5.9k 阅读时长 ≈ 5 分钟 【顺序表】线性表的顺序存储又称顺序表,其使用一组地址空间连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两元素在物理存储空间上也相邻 顺序表具有以下特点: 阅读全文 »
线性表 发表于 2018-09-03 分类于 OI&ACM , 数据结构 , 线性表 本文字数: 817 阅读时长 ≈ 1 分钟 【逻辑结构】线性表是具相同数据类型的 $n$ 个数据元素的有限序列,其中,相同数据类型意味着每个数据元素所占的存储空间相同,数据元素个数 $n$ 为线性表的长度,当 $n=0$ 时称为空表,反之 $n\neq 0$ 时称为非空表 一个非空表常记为: 阅读全文 »
算法及其时空复杂度 发表于 2018-09-03 分类于 OI&ACM , 算法基础 , 基础理论 本文字数: 532 阅读时长 ≈ 1 分钟 【算法】算法是对特定问题求解步骤的描述,是指令的有限序列,每个指令表示一或多个操作,其具有以下特性: 有穷性:能在有穷步、有穷时间内执行完毕 确定性:相同输入会获得相同输出 可行性:算法是可行的 输入:具有零到多个输入 输出:具有一到多个输出 阅读全文 »
数据结构的基本概念 发表于 2018-09-03 分类于 OI&ACM , 算法基础 , 基础理论 本文字数: 943 阅读时长 ≈ 1 分钟 【基本概念】数据结构的基本概念如下: 数据:信息载体,能输入到计算机且能被计算机识别处理的集合 数据元素:基本数据单位,作为一个整体考虑处理,由若干数据项组成 数据项:构成数据元素的、不可分割的最小单位 数据对象:数据的子集,具相同性质的元素的集合 数据结构:相互存在一种或多种特定关系的数据元素的集合 数据类型:一个值的集合与定义在此集合上的一组操作 原子类型:值不可再分,如 int、float、double 结构类型:值可分为若干成分,如 struct 抽象数据类型(ADT):数学化语言定义逻辑结构与运算,与具体实现无关,用于定义完整数据结构 阅读全文 »
带权并查集 发表于 2018-08-08 分类于 OI&ACM , 数据结构 , 并查集 本文字数: 1.1k 阅读时长 ≈ 1 分钟 【带权并查集】带权并查集是结点存有权值的并查集,每个元素的权值通常描述其与并查集中祖先的关系,这种关系如何合并,路径压缩时就如何压缩 与并查集相比,带权并查集可以推算集合内点的关系,而一般并查集只能判断属于某个集合 阅读全文 »
并查集的删除操作 发表于 2018-08-08 分类于 OI&ACM , 数据结构 , 并查集 本文字数: 706 阅读时长 ≈ 1 分钟 在并查集中,删除操作是指删除掉并查集中的一个结点 在所有结点都直接连接在根结点上的完美并查集上,理论上只要把要删除的节点的上级重新指向自己就可以了 但实际情况中,并查集形成的树的形态都是不可预估的,如果一个结点非叶结点,将该结点直接删除,会将其与其子孙结点一起删除 阅读全文 »
并查集的启发式合并 发表于 2018-08-04 分类于 OI&ACM , 数据结构 , 并查集 本文字数: 770 阅读时长 ≈ 1 分钟 【并查集的启发式合并】在并查集执行合并操作 Union(),将两个集合合并为一个时,无论将哪一个集合连接到另一集合的下面都是正确的,但不同的连接方法存在时间复杂度的差异 具体来说,如果将一棵结点数、深度都较小的集合树,连接到一棵更大的集合树下,显然相比于另一种连接方案,在接下来执行查找操作 Find() 时,时间复杂度会更小 阅读全文 »
并查集的路径压缩 发表于 2018-08-04 分类于 OI&ACM , 数据结构 , 并查集 本文字数: 834 阅读时长 ≈ 1 分钟 【概述】在并查集的寻找结点 x 的根结点的过程中,是不停的通过 father[] 数组去向上寻找其根结点 12345void Find (int x) { //递归实现 if (father[x] != x) //x不是集合的代表时 return Find(father[x]); //以当前结点的父结点进一步查询 return father[x];} 阅读全文 »
并查集及其基本操作 发表于 2018-08-02 分类于 OI&ACM , 数据结构 , 并查集 本文字数: 2.8k 阅读时长 ≈ 3 分钟 【概述】并查集(Union-Find Set)是一种用于分离集合操作的抽象数据类型,其处理的是集合(set)之间的合并及查询问题 在并查集中,借助一个数组 father[] 来表示每个结点的父结点,即 father[i] 存储结点 i 的父结点编号 阅读全文 »
置换选择排序与最佳归并树 发表于 2018-07-23 分类于 OI&ACM , 算法基础 , 排序 本文字数: 1.9k 阅读时长 ≈ 2 分钟 【引入】在 外部排序 中讨论过,增大归并路数 $k$ 或减少初始归并段个数 $r$,都可以减少归并趟数 $S$,进而减少 I/O 次数,以提高外部排序速度 若总的记录个数为 $n$,每个归并段长度为 $l$,则归并段个数 $\left \lceil \frac{n}{l} \rceil \right.$,采用内部排序得到的各个初始归并段,除最后一个外,长度都相同,其依赖于内部排序时可用内存工作区的大小 阅读全文 »