第三章 基本数据结构

  • 客户-接口-实现
  • 数组：
    • 固定有序
    • 存储空间相邻：适合访问而不是操纵
    • 两种常见错误：
    • 引用了无意义的 a[i] 内容
    • 没有保证 i 非负且小于数组大小
    • 查找（索引）：在链表中需要遍历，效率不高
    • 与向量（矢量）对应
    • 二维数组：矩阵 + 主序
  • 链表：
    • 逻辑有序
    • 高效重排数据项：适合操纵而不是访问
    • 可优雅地增大和缩小
    • 自引用结构 + 循环结构
    • 末尾节点的实现细节：
    • 不指向任何节点的空链接
    • 指向不包含元素节点的哑元节点
    • 循环链表：指向第一个节点（首节点）
    • 在开头保留头节点：
    • 无数据域
    • 链域指向真正的第一个节点
    • 好处：把链表指针作为参数，使函数可修改链表，可接受或返回一个空表
    • 不保留头节点时：把指向输入链表的指针作为参数，返回输出链表的指针。这种方法适合递归链表
    • 插入：在数组中需要移动元素，效率不高
    • 删除：遍历
    • 两种常见错误：
    • 引用了未定义的指针
    • 使用了无意中修改了的指针
    • 双向链表：
    • 主要意义：只有一个节点的信息，仍然可以删除该节点
    • 适用情况：
      • 节点作为参数传递
      • 节点中有其它链接，且是其它数据结构的一部分
    • 空闲链表
    • 多重链表
  • 字符串：
    • 字典顺序
  • 图的表示：
    • 邻接矩阵（数组）：
    • 适合稠密图（边数多）
    • 无向图时矩阵对称
    • 检查两个顶点间是否有边相连：常量
    • 邻接表（链表）：
    • 适合稀疏图（边数少）
    • 处理所有边：正比于 V+E，而不是邻接矩阵的 V^2

第四章 抽象数据结构

  • 广义队列（generalized queue）：
    • 操作：插入、删除
    • 随机队列：随机（等概率）得到一个项、随机删除一个项
    • 双端队列：在任何一端进行插入、删除
    • 优先队列：删除最小（最大）键
    • 符号表：删除与给定键相等的项
    • 下推栈（Push-down stack）：
    • 操作：pop、push
    • 函数调用机制
    • 后进先出（LIFO）
    • 实现：
      • 数组：
      • 固定空间：最大项的个数
      • 链表：
      • 灵活空间：所用空间与项的个数成正比
      • 栈的大小变化很大时使用
    • 先进先出队列（FIFO）：
    • 实现：
      • 数组：在头、尾分别维持两个索引
      • 链表：在头、尾分别维持两个指针

第五章 递归与树

  • 递归：
    • 归纳基础
    • 归纳假设
  • 非递归程序 = 递归程序 + 栈
  • 分治法：基本递归模式
  • 动态规划：实现递归程序的一般性方法
  • 循环：表现为递归
  • 递归的深度：取决于输入
  • 消除尾递归
  • 分治法：每个递归调用处理一半
    • 步骤：
    • 分片，合并
    • 在处理一半之后跟进
    • 与数字的二进制表示紧密相关
    • 组合-分治法：自底向上
  • 背包问题：最优决策
  • 动态规划：消除递归中的重复计算（存储函数值）
    • 自底向上：预先计算值
    • 自顶向上：存储已知的值，在之后的计算中优先选择
  • 树、顶点、边、路径：
    • 森林：不相交的多个树
    • 树的定义：根到叶节点都是唯一路径
    • 图的定义：不是唯一路径
  • 父节点、子节点、叶节点
  • 树的种类：
    • 无序树（自由树）：树中任意节点的子节点之间没有顺序关系，边的集合
    • 有序树：树中任意节点的子节点之间有顺序关系
    • 二叉树：
      • 联赛
      • 形状平衡时性能好
  • 树的遍历：
    • 前序：先根后左右。对应栈
    • 中序：先左中根后右
    • 后序：先左右后根
    • 层序：从上到下，从左到右。对应队列
  • 图的遍历（由树的遍历推广得到）：
    • 深度优先搜索（DFS）：对应栈
    • 广度优先搜索（BFS）：对应队列，对应层序遍历