数据结构知识汇总

本导图汇总了数据结构第一章的知识点，包括数据、数据元素、数据结构、数据类型、抽象数据类型、算法定义与特征、评估算法的基本标准。

第一章绪论

• 1.1数据结构的研究内容
  • 是一门研究非数值型计算的程序
• 1.21数据，数据元素，数据项和数据对象
  • 数据：是客观事物的符号，是所有能输入计算机中并能被计算机程序处理的符号的总称
  • 数据元素：是数据的基本单位（结点）
    • 数据元素之间存在的关系
      • 一对一
      • 一对多
      • 多对多
  • 数据项：是组成数据元素的，独立的，不可分割的最小单位
  • 数据对象：是性质相同的数据元素的集合，是数据的一个子集
• 1.22数据结构
  • 定义：是相互之间存在一种或多种特定关系的数据元素的集合
  • 逻辑结构：与数据的存储无关，独立于计算机。（唯一）
    • 线性结构：有且仅有开始和一个终端结点
      • 线性表
        • 一般线性表
          • 线性表
        • 特殊线性表
          • 栈与队列
          • 字符串
        • 线性表的推广
          • 数组
          • 广义表
    • 非线性结构：一个结点，可能有多个直接前趋和直接后继
      • 树结构
        • 树
        • 二叉树
      • 图结构
        • 有向图
        • 无向图
      • 集合结构
  • 存储结构：数据元素及其关系在计算机存储器中的存储方式（不唯一）
    • 顺序存储结构：借助相对位置来表示数据元素间的关系
      • Loc（ai）=Loc(ai)+(i-1)*k
    • 链式存储结构：用指针来表示数据元素间逻辑关系
  • 数据的运算：插入，查找，删除，排序，修改
• 1.23数据类型:是一个值的集合和定义在这个直集上的一组操作的总称
• 1.23抽象数据类型：一般由用户定义的
  • 数据对象
  • 数据对象上关系的集合
  • 对数据对象的基本操作的集合
  • ADT
    • D:数据对象
    • S：D上的关系
    • P：D上的操作数
• 1.43算法的空间复杂度
  • 定义：是指算法编写成程序后，在计算机中运算时所需存储空间大小的度量(辅助空间)
  • 公式：S(n)=O(f(n))
• 1.43算法的时间复杂度
  • 事后统计法
    • 缺点
      • 必须把算法转化成可执行的程序
      • 时空开销的测算依赖于计算机软硬件等环境因素
  • 事前分析估算法
  • 时间复杂度
    • T（n）=O(f(n))
    • 问题规模随n的增大，执行时间增长
  • 算法时间复杂度的举例
    • 常量阶
    • 线性阶
    • 平方阶
    • 立方阶
    • 对数阶
  • 最好时间复杂度：算法计算量可能达到的最小值
  • 最坏时间复杂度：算法计算量可能达到的最大值
  • 平均时间复杂度：按照实例以等概率出现时，算法计算量的加权平均值
• 1.42评价算法的基本标准
  • 正确性
  • 可读性
  • 健壮性
    • 当输入的数据非法时，好的算法能适当的做出正确的反应和相应的处理
  • 高效性
    • 时间：执行效率高
    • 空间：存储容量合理
• 1.41算法定义与特征
  • 定义：是为了解决某种问题而规定的一个有限长的操作序列
  • 特征
    • 有穷性
    • 确定性
    • 有效性
    • 输入
    • 输出