第1章 绪论-数据结构

前驱：①如果能找到p的父节点，且p是左孩子，则p的父节点为其前驱；②如果能找到p的父节点，且p是右孩子，其左兄弟为空，则p的父节点即为其前驱。

第一章 绪论 数据结构 王道考研系列

• 数据结构
  • 数据结构的基本概念
    • 数据
      • 是信息的载体
      • 是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合
    • 数据元素
      • 数据项
        • 一个数据元素可由若干数据组成，数据项是构成数据元素的不可分割的最小单位
      • 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理
    • 数据对象
      • 具有相同性质的数据元素的集合，是数据的一个子集
    • 数据结构
      • 是相互之间存在一种或多种特定关系的数据元素的集合
      • 同一个数据对象里的数据元素，可以组成不同的数据结构
      • 不同的数据元素，可以组成相同的数据结构
    • 数据类型
      • 原子类型
        • bool类型
          • 值的范围：true、false
          • 可进行操作：与、或、非
        • int类型
          • 值的范围：-2147483648 ~ 2147483647
          • 可进⾏操作：加、减、乘、除、模运算
      • 结构类型
        • struct结构体
      • 抽象数据类型ADT
        • 是抽象数据组织及与之相关的操作
        • 定义一个ADT，就是在“定义”一种数据结构
  • 数据结构三要素
    • 1. 若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。
    • 2. 数据的存储结构会影响存储空间分配的方便程度
    • 3. 数据的存储结构会影响对数据运算的速度 (Eg：在b和d之间插入新元素c)
    • 逻辑结构
      • 线性结构（一对一）
        • 一般线性表
        • 受限线性表
          • 栈
          • 队列
          • 串
        • 线性表推广
          • 数组
      • 非线性结构
        • 集合结构
          • 各个元素同属一个集合，别无其他关系
        • 树形结构（一对多）
          • 一般树
          • 二叉树
        • 图状结构（多对多）
          • 有向图
          • 无向图
    • 数据的运算
      • 结合逻辑结构、实际需求来定义基本运算
    • 存储结构（物理结构）
      • 顺序存储
        • 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
      • 链式存储
      • 索引存储
      • 散列存储
      • 非顺序存储
• 算法
  • 什么是算法
    • 程序=数据结构+算法
      • 数据结构是要处理的信息
      • 算法是处理信息的步骤
  • 算法的五个特性
    • 有穷性
      • 有穷时间内能执行完
        • 算法是有穷的
          • 用有限步骤解决某个特定的问题
        • 程序可以是无穷的
          • 如：微信是程序，不是算法
    • 确定性
      • 相同输入只会产生相同输出
    • 可行性
      • 可以用已有的基本操作实现算法
    • 输入
      • 一个算法有零个或多个输入
      • 丢给算法处理的结果
    • 输出
      • 一个算法有一个或多个输出
      • 算法处理的结果
  • “好”好算法的特质
    • 正确性
      • 能正确解决问题
    • 可读性
      • 对算法的描述要让其他人也得看懂
    • 健壮性
      • 算法能处理一些异常状况
    • 高效率与低存储量需求
      • 即算法执行省时、省内存
      • 时间复杂度低、空间复杂度低
  • 效率的度量
    • 时间复杂度
      • 如何计算
        • 1.找到一个基本操作（最深层循环）
        • 2.分析该基本操作的执行次数x与问题规模n的关系x=f(n)
        • 3.x的数量级O(x)就是算法时间复杂度T(n)
      • 常用技巧
        • 加法规则
          • 多项相加，只保留最高阶的项，且系数变为1
        • 乘法规则
          • 多项相乘都保留
        • 常对幂指阶
          • O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) <O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
      • 三种复杂度
        • 最坏时间复杂度
          • 最坏情况下算法的时间复杂度
        • 平均时间复杂度
          • 所有输入示例等概率出现的情况下，算法的期望运行时间
        • 最好时间复杂度
          • 最好情况下算法的时间复杂度
    • 空间复杂度
      • 如何计算
        • 普通程序
          • 1.找到所占空间大小与问题规模相关的变量
          • 2.分析所占空间x与问题规模n的关系x=f(n)
          • 3.x的数量级O(n)就是算法空间的复杂度
        • 递归程序
          • 1.找到递归调用的深度x与问题规模n的关系x=f(n)
          • 2.x的数量级O(n)就是算法空间复杂度S(n)
          • 空间复杂度 = 递归调用的深度
      • 常用技巧
        • 加法规则
          • T(n) = T₁(n) + T₂(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
        • 乘法规则
          • T(n) = T₁(n)×T₂(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))
        • “常对幂指阶”
          • O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) <O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)