【读书笔记】数据结构与算法分析 - C 语言描述 - 第二部分 - 数据结构

2022/05/02    6 min read

第三章 基本数据结构

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

第四章 抽象数据结构

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

第五章 递归与树

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