第一章概论

数据结构第一章概论的思维导图，数据:客观事物的符号表示；指能输入到计算机中并被计算机程序处理的符号的总称

第一章概论

• 数据结构
  • 基本概念
    • 数据:客观事物的符号表示；指能输入到计算机中并被计算机程序处理的符号的总称
    • 数据元素：数据的基本单位；数据项：最小单位
    • 数据对象：性质相同的数据元素集合；数据结构：特定关系的数据元素结合
    • 数据类型
      • 原子类型
      • 结构类型
    • 操作：处理事物的动作集合
    • 逻辑结构：数据对象的逻辑组织关系
  • 抽象数据类型ADT
    • 定义一个ADT，就是定义了数据的逻辑结构、数据的运算，也就定义了一个数据结构)
  • 数据结构三要素
    • 逻辑结构
      • 集合
      • 线性结构
      • 树形结构
      • 图结构（网状结构）
    • 物理结构（数据存储结构）
      • 顺序存储（逻辑上相邻的元素存储在物理位置上也相邻的存储单元）
      • 链式存储（物理位置可以不相邻；指针）
      • 索引存储（索引表）
      • 散列存储（哈希存储）
    • 数据的运算：根据逻辑结构来定义，根据存储结构来实现
• 算法：解决问题步骤的有限集合
  • 空间复杂度：递归调用的深度；注意分析
  • 时间复杂度
    • 计算方法
      • 1、找出语句频率最大的那条语句作为基本语句
      • 2、计算基本语句的频度得到问题规模
      • 3、数量集用“O”表示
    • 计算技巧
      • 加法规则:O(f(n)+g(n)) =O(max{f(n).g(n)))
      • 乘法规则:O(f(n*g(n))=O(f(n)*g(n))
      • 常对幂指阶
      • 嵌套循环为乘
      • while（i<=n) i=i*x log以x为底n的对数
    • 三种复杂度
      • 最好
      • 最坏
      • 平均
  • 渐进表示法：分析算法复杂度的增长趋势