数据结构

数据结构第一章，后续持续更新。

数据结构

• 绪论
  • 基本概念
    • 数据：客观事物的符号表示；指能输入到计算机中并被计算机程序处理的符号的总称
    • 数据元素：数据的基本单位；数据项：最小单位
    • 数据对象：性质相同的数据元素集合；数据结构：特定关系的数据元素结合
    • 数据类型
      • 原子类型
      • 结构类型
    • 抽象数据类型ADT
      • 定义一个ADT，就是定义了数据的逻辑结构、数据的运算，也就定义了一个数据结构
  • 数据结构三要素
    • 逻辑结构
      • 集合
      • 线性结构
      • 树形结构
      • 图结构（网状结构）
    • 物理结构（存储结构）
      • 顺序存储（逻辑上相邻的元素存储在物理位置上也相邻的存储单元)
      • 链式存储（物理位置可以不相邻；指针）
      • 索引存储（索引表）
      • 散列存储（哈希存储）
    • 数据的运算
      • 根据逻辑结构来定义，根据存储结构来实现
  • 算法
    • 定义：程序=数据结构+算法
      • 数据结构是要处理的信息
      • 算法是是处理信息的步骤
    • 五个特性
      • 有穷性
        • 有穷时间内执行完
          • 算法是有穷的
          • 程序可以是无穷 的
      • 确定性
        • 相同输入相同输出
      • 可行性
        • 已有的基本操作实现算法
      • 输入
      • 输出
    • 好算法的特质
      • 正确性
      • 可读性
      • 健壮性
        • 能处理一些异常情况
      • 高效率与低存储量需求
        • 算法执行省时，省内存
        • 时间、空间复杂度低
  • 时间复杂度
    • 计算
      • ①找到一个基本操作（最深层循环）
      • ②分析该操作的执行次数x与问题规模n的关系f(n)
      • ③O(x)
    • 技巧
      • 加法规则：O(f(n)+g(n)）=O(max{f(n),g(n)})
      • 乘法规则：O(f(n)xg(n)）=O(f(n)xg(n))
      • ”常对幂指阶“
    • 三种复杂度
      • 最坏
      • 最好
      • 平均
  • 空间复杂度
    • 递归调用的深度；注意分析