「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++ 数据结构 (二) 向量 (5) 二分查找 -「Skill - Data Structure」

【注】二分查找的前提是有序向量, 亦或有序线性表 接口 1 2 3 4 5 6 template <typename T> // 查找算法同一接口, 0 <= lo < hi <= _size Rank Vector<T>::search(T const &e, Rank lo, Rank hi) const { return (ra...

C++ 数据结构 (二) 向量 (6) 斐波那契查找 -「Skill - Data Structure」

【注】斐波那契查找是在二分查找的基础上根据斐波那契数列进行分割的 思路及原理 二分查找版本A的效率仍有改进的余地, 因为不难发现 转向左、右分支前的关键码 比较次数 不等, 而 递归深度 却相同 若能通过 递归深度 的不均衡, 对 转向成本 的不均衡进行补偿 平均查找长度应能进一步缩短 … 比如, 若设 n = fib(k) - 1, 则可取 mi = fib(k - 1) - ...

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...

C++ 数据结构 (二) 向量 (8) 归并排序 -「Skill - Data Structure」

归并排序 原理 分治策略 序列一分为二 $ O(1) $ 子序列递归排序 $ 2 * T(\frac{n}{2}) $ 合并有序子序列 $ O(n) $ 若真能如此,归并排序的运行时间应该是 $ O(n * \log n) $ 实现 1 2 3 4 5 6 7 8 template <typename T> void Vector<T>::merg...

C++ 数据结构 (三) 列表 (2) 无序列表 -「Skill - Data Structure」

秩到位置 是否可以模仿向量的循秩访问方式? 可以,比如,通过重载下标操作符 1 2 3 4 5 6 template <typename T> // assert: 0 <= r < size T List<T>::operator[](Rank r) const { // O(r),效率低下,可偶尔为之,却不宜常用 Posi(T) p = fi...

C++ 数据结构 (三) 列表 (1) 接口与实现 -「Skill - Data Structure」

从静态到动态 根据是否修改数据结构, 所有操作大致分为两类方式: 静态:仅读取, 数据结构的内容及组成一般不变, 如 get、search 动态:需写入, 数据结构的局部或整体将改变, 如 insert、remove 与操作方式相对应的, 数据元...

C++ 数据结构 (三) 列表 (3) 有序列表 -「Skill - Data Structure」

唯一化 1 2 3 4 5 6 7 8 9 10 template <typename T> int List<T>::uniquify() { // 成批剔除重复元素 if (_size < 2) return 0; // 平凡列表自然无重复 int oldSize = _size; // 记录原规模 ListNodePosi(T) p = fi...

C++ 数据结构 (三) 列表 (4) 选择排序 -「Skill - Data Structure」

实例 实现: selectionSort() 1 2 3 4 5 6 7 8 9 10 // 对列表中起始于位置 p 的连续 n 个元素做选择排序,valid(p) &amp;&amp; rank(p) + n <= size template <typename T> void List<T>::selectionSort(Posi(T...

C++ 数据结构 (三) 列表 (5) 插入排序 -「Skill - Data Structure」

构思 始终将序列看成两部分: Sorted Unsorted L[0, r) L[r, n) 【初始化】 |S| = r = 0, 空序列无所谓有序 【迭代】关注并处理 e = L[r], 在 S 中确定 适当位置 插入 e, 得到有序的 L[0, r] 【不变性】随着 r ...

C++ 数据结构 (四) 栈与队列 (1) 栈接口与实现 -「Skill - Data Structure」

操作与接口 操作实例 LIFO: Last In First Out 实现 栈既然属于序列的特例,故可直接基于向量或列表派生 1 2 3 4 5 6 7 template <typename T> class Stack : public Vector<T> { // 由向量派生 public: // size()、empty() 以及其他开放接...

C++ 数据结构 (四) 栈与队列 (2) 栈应用 (1) 进制转换 -「Skill - Data Structure」

典型应用场合 逆序输出 (conversion) 输出次序与处理过程颠倒, 递归深度和输出长度不易预知 递归嵌套 (stack permutation + parenthesis) 具有自相似性的问题可递归描述, 但分支位置和嵌套深度不固定 延迟缓冲 (evaluation) 线性扫描算法模式中, 在预读...

C++ 数据结构 (四) 栈与队列 (2) 栈应用 (2) 栈混洗与括号匹配 -「Skill - Data Structure」

典型应用场合 逆序输出 (conversion) 输出次序与处理过程颠倒, 递归深度和输出长度不易预知 递归嵌套 (stack permutation + parenthesis) 具有自相似性的问题可递归描述, 但分支位置和嵌套深度不固定 延迟缓冲 (evaluation) 线性扫描算法模式中, 在预读...

C++ 数据结构 (四) 栈与队列 (2) 栈应用 (3) 中缀表达式 -「Skill - Data Structure」

典型应用场合 逆序输出 (conversion) 输出次序与处理过程颠倒, 递归深度和输出长度不易预知 递归嵌套 (stack permutation + parenthesis) 具有自相似性的问题可递归描述, 但分支位置和嵌套深度不固定 延迟缓冲 (evaluation) 线性扫描算法模式中, 在预读...

C++ 数据结构 (四) 栈与队列 (2) 栈应用 (4) 逆波兰表达式 -「Skill - Data Structure」

典型应用场合 逆序输出 (conversion) 输出次序与处理过程颠倒, 递归深度和输出长度不易预知 递归嵌套 (stack permutation + parenthesis) 具有自相似性的问题可递归描述, 但分支位置和嵌套深度不固定 延迟缓冲 (evaluation) 线性扫描算法模式中, 在预读...

C++ 数据结构 (四) 栈与队列 (3) 队列接口与实现 -「Skill - Data Structure」

操作与接口 队列 (queue) 也是受限的序列: 先进先出 (FIFO)、后进后出 (LILO) 只能在队尾插入 (查询): enqueue() + rear() 只能在队头删除 (查询): dequeue() + front() 操作实例 模板类 队列既然属于序列的特列,故亦可直接基于向量或列表派生 1 2 3 4 5 6 7 template <typena...

C++ 数据结构 (五) 二叉树 (1) 树 -「Skill - Data Structure」

应用 层次关系的表示 表达式: RPN 文件系统 URL … 有根树 树是特殊的图 $ T = (V, E) $, 节点数 $ \vert V \vert = n $, 边数 $ \vert E \vert = e $ 指定任一节点 $ r \in V $ 作为根后, $ T $ 即称作有根树 (r...

C++ 数据结构 (五) 二叉树 (2) 树的表示 -「Skill - Data Structure」

接口 节点 功能 root() 根节点 parent() 父节点 firstChild() 长子 nextSibling() 兄弟 ...

C++ 数据结构 (五) 二叉树 (3) 二叉树概述 -「Skill - Data Structure」

二叉树 节点度数 不超过2 的树称作二叉树 (binary tree) 同一节点的孩子和子树,均以左、右区分 lChild() ~ lSubtree() rChild() ~ rSubtree() 隐含有序 基数 深度为 $ k $ 的节点,至多 $ 2^k $ 个 含 $ n $ 个节点、高度为 $ h $ 的二叉树中,$ h < n < 2^(h+1)$ ...

C++ 数据结构 (五) 二叉树 (4) 二叉树实现 -「Skill - Data Structure」

BinNode: 模板类 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #define BinNodePosi(T) BinNode<T>* // 节点位置 template <typename T> struct BinNode { BinNodePosi(T) parent, lChild, rChild; // 父亲、左孩子、右孩子 ...

C++ 数据结构 (五) 二叉树 (5) 先序遍历 -「Skill - Data Structure」

遍历规则 按照某种次序访问树中各节点,每个节点被访问恰好一次 $ T = V \cup L \cup R $ 遍历结果 ~ 遍历过程 ~ 遍历次序 ~ 遍历策略 先序 中序 后序 层次 (广度) **V** | L | R L | **V** | R ...

C++ 数据结构 (五) 二叉树 (6) 中序遍历 -「Skill - Data Structure」

递归 1 2 3 4 5 6 7 template <typename T, typename VST> void traverse(BinNodePosi(T) x, VST &visit) { if (!x) return; traverse(x -> lChild, visit); visit(x -> data); traverse(...

C++ 数据结构 (五) 二叉树 (7) 层次遍历 -「Skill - Data Structure」

实现 1 2 3 4 5 6 7 8 9 10 11 template <typename T, typename VST> void BinNode<T>::travLevel(VST &visit) { // 二叉树层次遍历 Queue<BinNodePosi(T)> Q; // 引入辅助队列 Q.enqueue(this); // ...

C++ 数据结构 (六) 图 (1) 概述 -「Skill - Data Structure」

邻接、关联 G = (V; E) vertex: n = |V| edge|arc : e = |E| 邻接关系 (adjacency): 相邻接的两个顶点之间的关系 关联关系 (incideace): 顶点与邻接边之间的关系 无向、有向 若邻接顶点 U 和 V 的次序无所谓 则 (U, V) 为无向边 (undirected edge) 例: 若 U 是 V 的好友,...

C++ 数据结构(六)图(2)邻接矩阵 -「Skill - Data Structure」

Graph 模板类 1 2 3 4 5 6 7 8 9 10 11 12 13 14 template <typename Tv, typename Te> // 顶点类型、边类型 class Graph { private: void reset() { // 所有顶点、边的辅助信息复位 for (int i = 0; i < n; i++) {...