数据结构

数据结构(清华大学出版社)第一章绪论思维导图，包括数据结构课程结构与术语、数据结构的研究内容、抽象数据类型等。

第一章 绪

• 1.课程属性与术语
  • 数据结构是程序的重要组成部分
  • 数据结构是提升编程能力的必备
  • 数据结构与术语
    • 结构
    • 数据结构
    • 数据
      • 数据元素
      • 数据项
      • 数据对象
  • 数据结构决定算法
    • 程序与数据的关系
    • 程序数据结构与算法的关系
• 2.数据结构的研究内容
  • 数据结构的分类
    • 逻辑结构
      • 定义
      • 典型的逻辑结构
        • 非线性结构
          • 集合结构
            • 数据元素属于同一个集合
            • 数据元素之间没有其他关系
          • 树结构
            • 数据元素属于同一个集合
            • 数据元素之间存在着一对多的关系
            • 前驱、后继
          • 图结构
            • 数据元素属于同一个集合
            • 数据元素之间存在着多对多的关系
            • 前驱、后继
        • 线性结构
          • 数据元素属于同一个集合
          • 数据元素之间存在着一对一的关系
      • 好的逻辑结构满足的特点
        • 正确地反映问题域内数据元素之间地关系
        • 有利于问题地求解
    • 存储结构/物理结构
      • 定义
      • 特点
        • 存储数据元素
        • 存储数据元素之间的逻辑关系
      • 典型的存储/物理结构
        • 顺序存储结构
          • 定义
          • 特点
            • 采用不连续的存储空间
            • 随机访问
            • 需要预先估计所需的存储空间，申请之后不能延扩。 申请少了，不够用；申请多了，会造成浪费。
        • 链式存储结构
          • 定义
          • 特点
            • 采用连续的存储空间
            • 不需要预估所需的存储空间，可以无限延扩
            • 需要额外的空间存储指针，以存储数据元素之间的逻辑关系
      • 好的存储方法要求
        • 存储数据元素
        • 存储元素的逻辑关系
    • 逻辑机构与物理结构的关系
  • 非数值计算问题
    • 计算机求解问题的一般步骤
  • 算法的设计与实现
  • 数据结构与程序设计的关系
• 3.抽象数据类型
  • 定义
    • 格式
    • 三要素
      • 数据元素
      • 数据元素之间的关系
      • 操作
        • 操作名
        • 参数列表
        • 初始条件
        • 操作功能
        • 操作结果
        • 等
  • 实现
• 4.算法与算法分析
  • 算法概念
    • 定义
    • 特性
      • 有穷性
      • 确定性
      • 可行性
      • 输入
      • 输出
    • 算法的优劣考量
      • 正确性
      • 可读性
      • 健壮性
      • 高效性
  • 算法描述
    • 定义
    • 描述方法
      • 其他方法
        • 自然语言描述
        • 流程图描述
        • 程序设计语言
        • 伪码描述
      • 推荐方法
        • 类语言
  • 算法性能分析
    • 定义
      • 分析两方面内容
        • 时间性能
        • 空间性能
      • 分析工具
        • 渐进复杂度中的算符O
    • 1.度量工具O
    • 2.算法效率度量方法
      • 事前分析法(用这个)
      • 事后统计法
    • 3.算法的时间复杂度
      • 度量算法的时间性能
      • 主要因素
        • 算法的选用策略
        • 问题规模
      • 频度
        • 整个算法的语句频度计算方法
          • 直接计算
          • 通过方程求解
          • 等概率分析
          • 最坏情况分析
          • 最好情况
      • 定义
    • 4.算法的空间复杂度
      • 度量算法的空间性能
      • 主要因素
        • 辅助变量所占的空间
      • 定义