数据结构算法第一章概述

数据结构算法第一章概述的思维导图，数据就是指能够被计算机识别、存储和加工处理的信息的载体；数据项是具有独立含义的最小标识单位；数据元素是数据的基本单位，可以由若干个数据项组成。

概述

• 数据结构的用处和概念
  • 术语
    • 数据
      • 就是指能够被计算机识别、存储和加工处理的信息的载体。
    • 数据项
      • 是具有独立含义的最小标识单位。
    • 数据元素
      • 是数据的基本单位，可以由若干个数据项组成。
  • 程序
    • 算法
      • 好的算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出
      • 程序设计的实质：是对实际问题选择一种好的数据结构，设计一个好的算法
      • 算法的优劣性：
        • 算法是正确的 执行算法的时间 执行算法的存储空间(主要是辅助存储空间) 算法易于理解、编码、调试
    • 数据结构
      • 逻辑结构
        • 从逻辑结构上描述数据，独立于计算机
          • 线性结构
          • 非线性结构
            • 树形结构
            • 图形结构
      • 存储结构
        • 逻辑结构用计算机语言的实现
          • 顺序存储
            • 数组
              • 优点
                • 存储效率高
                • 随机存储
                • 不占用额外的存储空间
              • 缺点
                • 不便于数据修改，对元素的插入、修改
          • 链接存储
            • 链表
              • 优点
                • 便于修改
              • 缺点
                • 空间利用率低
          • 索引存储
            • 索引表
              • 优点
                • 查找效率高
              • 缺点
                • 要建立索引表，增加了空间开销
          • 散列存储
            • 如散列表
              • 优点
                • 查找速度快
      • 数据的运算
        • 对数据实施的操作，常见的有增删改查
        • 检索、插入、删除、更新、排序
        • 定义在逻辑结构上，每种逻辑结构都有一个运算集合
• 算法的描述和分析
  • 算法的五个准则
    • 输入和输出
    • 有穷性
    • 确定性
    • 可行性
• 算法复杂度
  • 子主题
    • 时间复杂度
      • 算法的总执行次数X每次花费的时间
      • 取决于问题的规模和执行次数
    • 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。
    • 评价一个算法的时间性能时，主要标准就是：算法的渐近时间复杂度。
    • 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。
    • 时间复杂度按数量级递增排列依次为：常数阶 0(1)、对数阶 0(log2n)、线性阶 0(n)、线性对数阶 0(nlog2n)、平方阶 0(n²)、立方阶 0(n³)、……k 次方阶 0(n^k)、指数阶 0(2^n)。
    • 空间复杂度：是某个算法的空间耗费，它是该算法所求解问题规模 n 的函数
    • 算法复杂度：算法的时间复杂度和空间复杂度合称算法复杂度。
• 抽象数据类型ADT
  • P
    • D中数据运算的基本运算集
  • D
    • 数据对象
  • R
    • D上的关系集
• 存储结构的考虑因素：访问效率、安全保密、修改频率