数据结构_1绪论

参考王道计算机考研课程，自主总结归纳相关知识点，干货满满，有需要的朋友赶紧收藏吧！

数据结构

• 绪论
  • 数据结构在学什么
    • 程序代码将现实世界的问题信息化
    • 用计算机高效地处理这些信息从而创造价值
  • 数据结构
    • 基本概念
      • 数据
      • 数据元素、数据项
      • 数据对象、数据结构
      • 数据类型、抽象数据类型
    • 三要素
      • 学习任何一种数据结构时应该关注的三个方面
      • 逻辑结构
        • 数据元素之间的逻辑关系，与数据的存储无关，独立于计算机
        • 线性结构
          • 一对一
        • 集合
          • 除了同属一个集合，元素间无关系
        • 树形结构
          • 一对多
        • 图结构（网状结构）
          • 多对多
        • 非线性结构
      • 物理结构（储存结构）
        • 数据结构在计算机中的表示（包括数据元素的表示和关系的表示） 用计算机语言实现的逻辑结构
        • 顺序存储
        • 链式存储
        • 索引储存
        • 散列存储
        • 非顺序存储
      • 数据的运算
        • 根据逻辑结构来定义、根据存储结构来实现
  • 算法的基本概念
    • 什么是算法
      • 程序=数据结构+算法
        • 程序设计： 设计一个好的数据结构 设计一个好的算法
        • 数据结构是要处理的信息
        • 算法是处理信息的步骤
    • 五个特性
      • 算法必须具备的特性
      • 有穷时间内能执行完
        • 算法是有穷的
        • 程序可以是无穷的
      • 确定性
        • 相同输入只会产生相同输出
      • 可行性
        • 可用已有的基本操作实现
      • 输入
        • 可为零（helloworld程序）
      • 输出
        • 算法处理的结果
    • “好”算法的特质
      • 正确性
        • 正确解决问题
      • 可读性
        • 对算法的描述要让其他人也看得懂（伪代码/文字）
      • 健壮性
        • 能处理一些异常状况
          • 如输入非法数据时，好的算法能够正确处理，而不至于程序崩溃
      • 高效率与低存储量需求
        • 时间复杂度低，空间复杂度低
    • 效率的度量
      • 预备知识
        • 复杂度取决于最高次幂的阶数（系数与低次幂可忽略）
          • 算法的性能问题只有在n很大时才会暴露出来
      • 时间复杂度
        • 如何计算
          • 1. 找到一个基本操作（最深层循环）
          • 2. 分析该基本操作的执行次数x与问题规模n的关系x=f(n)
          • 3. x的数量级O(x)就是算法时间复杂度T(n)
            • O(x):同阶无穷大（自变量趋于无穷时，分子分母比值为一个常数C）
        • 三种复杂度
          • 最坏时间复杂度
            • 考虑输入数据“最坏”的情况
          • 平均时间复杂度
            • 考虑所有输入数据都等概率出现的情况
          • 最好时间复杂度
            • 考虑输入数据“最好”的情况
      • 空间复杂度
        • 普通程序
          • 1. 找到所占空间大小与问题规模相关的变量
          • 2. 分析所占空间x与问题规模n的关系x=f(n)
          • 3. x的数量级O(x)就是算法时间复杂度S(n)
            • O(x):同阶无穷大（自变量趋于无穷时，分子分母比值为一个常数C）
          • 概要
        • 递归程序
          • 1. 找到递归调用的深度x与问题规模n的关系x=f(n)
          • 2. x的数量级O(x)就是算法时间复杂度S(n)
          • 概要
        • 有的算法各层函数所需存储空间不同，分析方法略有区别
      • 常用技巧
        • 加法规则
          • 
            • 取阶数最大
        • 乘法规则
          • 
            • 保留最高阶乘积项
        • 常对幂指阶
          •