「Data Structure」

「Skill」

C++ 数据结构 (一) 绪论 (1) 计算 -「Skill - Data Structure」

讲义下载: 《清华大学数据结构讲义》 引例 计算对象: 规律、技巧 计算目标: 高效、低耗 绳索计算机及其算法 输入: 任给直线 l 及其上一点 A 输出: 经过 A 做 l 的一条垂线 算法 取 12 段等长的绳索, 首尾联接成环 从 A 点起, 将 4 段绳索沿 l 伸直并固定于 B 沿另一个方向找到第 3 段绳索的终点 C 移动点 C, 将剩余...

C++ 数据结构 (一) 绪论 (2) 计算模型 -「Skill - Data Structure」

算法分析的两个主要方面 正确性: 算法功能与问题要求一致 数学证明 ? 成本: 运行时间 + 存储空间 如何度量 ? 如何比较 ? 考察 令 $ T_A (P) = 算法 A 求解问题实例 P 的计算成本 $ 意义不大, 可能出现的问题实例太多 如何归纳概括 ? 观察 问题实例的规模, 往往...

C++ 数据结构 (一) 绪论 (3) 复杂度 -「Skill - Data Structure」

大 O 记号 当 $ n \gg 2 $ 后, 对于规模为 $ n $ 输入, 算法: 需要执行的基本操作次数: $ T(n) = ? $ 需占用的存储单元数: $ S(n) = ? $ (通常不考虑) $ T(n) = O( f(n) ) $ $ if \ \exists c > 0, 当 \ n \gg 2 \ 后, 有 \...

C++ 数据结构 (一) 绪论 (4) 算法分析 -「Skill - Data Structure」

主要任务 算法分析的两个主要任务: 正确性 (不变性 * 单调性), 复杂度 C++ 等高级语言的 基本指令, 均等效于常数条 RAM 的 基本指令 在渐进意义下, 二者大体相当于: 分支转向: goto 算法的灵魂, 出于结构化考虑, 被隐藏了 ...

C++ 数据结构 (一) 绪论 (5) 迭代与递归 (1) -「Skill - Data Structure」

To iterate is human, to recurse, divine. 迭代乃人工, 递归方神通 数组求和: 迭代 问题 计算任意 n 个整数之和 实现 逐一取出每个元素, 累加之 1 2 3 4 5 int sum(int A[], int n) { int sum = 0; // O(1) for (int i = 0; i < n; i...

C++ 数据结构 (一) 绪论 (5) 迭代与递归 (2) -「Skill - Data Structure」

数组倒置 问题描述 任给数组 A[0, n), 将其前后颠倒 统一接口: void reverse(int *A, int lo, int hi); 递归版 1 2 3 4 5 6 void reverse(int *A, int lo, int hi) { if (lo < hi) { // 问题规模的奇偶性不变, 需要两个递归基 swap(A[lo], A[h...

C++ 数据结构 (一) 绪论 (5) 迭代与递归 (3) -「Skill - Data Structure」

Find Two Max 问题描述 从数组区间 A[lo, hi) 中找出最大的两个整数 A[x1] 和 A[x2], 且 A[x1] ≥ A[x2] 元素比较的次数要求尽可能少 迭代法一 1 2 3 4 5 6 7 8 9 10 11 12 void max2(int A[], int lo, int hi, int &x1, int &x2) // 1 <...

C++ 数据结构 (一) 绪论 (6) 动态规划 (1) -「Skill - Data Structure」

【注】fib() 意为斐波那契额数列算法 fib(): 递归 $ fib(n) = fib(n-1) + fib(n-2): {0, 1, 1, 2, 3, 5, 8 …} $ 1 2 3 int fib(n) { return (2 > n) ? n : fib(n - 1) + fib(n - 2); } fib(): 递推方程 \[\begin{aligned} ...

C++ 数据结构 (一) 绪论 (6) 动态规划 (2) -「Skill - Data Structure」

最长公共子序列 子序列 (Subsequence): 由序列中若干字符, 按原相对次序构成 最长公共子序列 (Longest Common Subsequence): 两个序列公共子序列中的最长者 LCS(): 递归 对于序列 A[0, n] 和 B[0, m], LCS(A, B) 有三种情况 递归基: 若 n = -1 或 m = -1, 则取作空序列 ...

C++ 数据结构 (二) 向量 (1) 接口与实现 -「Skill - Data Structure」

ADT VS DS 抽象数据类型 (Abstract Data Type) :数据模型 + 定义在该模型上的一组操作 抽象定义 外部的逻辑特性 操作 & 语义 一种定义 不考虑时间复杂度 ...

C++ 数据结构 (二) 向量 (2) 扩容向量 -「Skill - Data Structure」

静态空间管理 开辟内部数组 _elem[] 并使用一段地址连续的物理空间 _capacity: 总容量 _size: 当前的实际规模 n 若采用静态空间管理策略, 容量 _capacity 固定, 则有明显的不足 上溢 (overflow): _elem[] 不足以存放所有...

C++ 数据结构 (二) 向量 (3) 无序向量 -「Skill - Data Structure」

元素访问 (循秩访问) 通过 V.get(r) 和 V.put(r, e) 接口, 可以读、写向量元素 但就便捷性而言, 远不如数组元素的访问方式: A[r] 是否可沿用借助下标的访问方式? 为此, 需重载下标操作符 1 2 template <typename T> T & Vector<T>::operator[](Rank r) const {...

C++ 数据结构 (二) 向量 (4) 有序向量 -「Skill - Data Structure」

有序性及其甄别 无序/有序序列中, 任意/总有一对相邻元素顺序/逆序 因此, 相邻逆序对的数目, 可用以度量向量的逆序程度 1 2 3 4 5 6 7 template <typename T> // 返回逆序相邻元素对的总数 int Vector<T>::disordered() const { int n = 0; // 计数器 for (int i...

C++ 数据结构 (二) 向量 (7) 起泡排序 -「Skill - Data Structure」

排序器: 统一入口 1 2 3 4 5 6 7 8 9 void Vector<T>::sort(Rank lo, Rank hi) { // 区间 [lo, hi) switch (rand() % 5) { // 视具体问题的特点灵活选取或扩充 case 1: bubbleSort(lo, hi); break; // 起泡排序 case 2: s...