绪论

算法特性

  1. 有穷性
  2. 确定性
  3. 可行性
  4. 输入
  5. 输出

算法设计的要求

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 效率与低存储量需求

线性表

顺序表示

若以线性表表示集合并进行集合的各种运算，应先对表中元素进行排序。

链式表示

  1. 线性链表/单链表
  2. 静态链表
  3. 循环链表
  4. 双向链表

一元多项式的表示及相加

栈和队列

栈

  • 顺序栈
  • 链栈

栈的应用

  • 数制转换
  • 括号匹配的检验
  • 行编辑程序
  • 迷宫求解
  • 表达式求值
  • 递归

栈与递归的实现

队列

  • 链队列
  • 循环队列

离散事件模拟

串（略）

数组和广义表

数组

n 维数组的映像函数：$ LOC(j_1, j_2, ..., j_n) = LOC(0, 0, ..., 0) + \Sigma_{i = 1}^n c_i j_i $，其中 $ c_n = L, c_{i - 1} = b_i \cdot c_i, 1 < i \le n $。

由于计算各个元素存取位置的时间相等，所以存取数组中任一元素的时间也相等。我们称具有这一特点的存储结构为随机存储结构。

矩阵的压缩存储

  • 特殊矩阵
  • 稀疏矩阵
    • 稀疏因子: m x n 矩阵中有 t 个非零元，称 t / m / n 为稀疏因子，不越过 0.05 时为稀疏矩阵
    1. 三元组顺序表
      • 转置
        1. 按照转置矩阵中三元组的次序依次在原矩阵中找到相应的三元组进行转置；
          • 时间复杂度 O(列数 X 非零元数)
        2. 快速转置：按照原矩阵中三元组的次序进行转置，并将转置后的三元组置入转置矩阵中恰当的位置。
          • 需要先求得原矩阵中每列每一个非零元在转置矩阵中的行位置
          • 时间复杂度 O(列数 + 非零元数)
    2. 行逻辑链接的顺序表：带各行第一个非零元的位置表
      • 乘法 M X N = Q
        • 对 M 每一行：对该行每个非零元，按列找 N 对应行所有非零元，累加乘积，后压缩到 Q 中。
        • 时间复杂度 O(M行数 X N列数 + M非零元数 X N非零元数 / N.行数)
    3. 十字链表：三元组 + 右指针 + 下指针
      • 相加

广义表

第一个元素为表头，其余元素组成的表为表尾。

树和二叉树

二叉树的性质

  1. 在二叉树的第 k 层上至多有 2^(k - 1) 个结点（k >= 1）。
  2. 深度为 k 的二叉树至多有 2^k - 1 个结点（k >= 1）。
  3. 对任何一棵二叉树，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 = n2 + 1。
  4. 具有 n 个结点的完全二叉树的深度为 ceil(log2(n + 1)) = floor(log2(n)) + 1。
  5. 如果对一棵有 n 个结点的完全二叉树的结点从上到下并从左到右编号，则对任一结点 i（1, ..., n），有
    1. i = 1，则结点为根，无 parent；i > 1，则 parent 为 floor(i / 2)；
    2. 2i > n，则无左孩子，否则为 2i；
    3. 2i + 1 > n，则无右孩子，否则为 2i+1。

性质 5 可以由下面更一般的性质推出。 对一棵完全二叉树的结点从下到下并从左到右编号 1, ..., n，则对任一结点 i，其左孩子（如果有）为 2i。

二叉树的存储结构

顺序存储结构：仅适用于完全二叉树。

二叉树的遍历

  • 递归
  • 非递归

线索二叉树：左指针指向左孩子或前驱，右指针指向右孩子或后继。

树的存储结构

  1. 双亲表示法 -> parent
  2. 孩子表示法 -> childlist
  3. 孩子兄弟表示法/二叉链表表示法 -> { first_child, next_sibling }
    • 所以给定一棵树，可以找到唯一的一棵二叉树与之对应，且根结点右子树为空。
    • 森林的先序和中序遍历即为其对应的二叉树的先序和中序遍历。

树与等价问题（略）

最优二叉树/赫夫曼树

带权路径长度最短的树

赫夫曼树的构造方法：不断合并根结点权重最小的的两棵树为一棵新树，新树根权重为两个根结点权重之和。

回溯法与树的遍历（略）

树的计数（略）

Page Not Found

Try to search through the entire repo.