数据结构-绪论

数据结构-绪论知识梳理，包括数据结构定义、逻辑结构、抽象数据类型、算法及其描述、算法分析等内容。

绪论

• 什么是数据结构
  • 数据结构定义
    • 数据结构：数据元素+数据元素之间的关系
    • • 逻辑结构
      • 存储结构
      • 运算
  • 逻辑结构
    • 类型
      • 集合
      • 线性结构
        • 除开始元素、终端元素，其余元素有且仅有一个前驱和一个后继
      • 树形结构
        • 除开始元素外，每个元素只有一个前驱，除终端元素外，每个元素有一个或多个后继。
      • 图形结构
  • 存储结构
    • 顺序存储结构
      • 定义：采用一组连续的存储单元存放元素
      • 特点
        • 存储效率高，逻辑关系可以隐含，没有占用额外的存储空间
        • 支持随机存取（根据序号可以直接计算出存储地址）
        • 不便于数据的修改，比如插入、删除操作
    • 链式存储结构
      • 定义：每个逻辑元素用一个内存结点存放，结点地址不连续
      • 特点
        • 便于数据修改，修改结点时仅需修改指针域，而不必移动结点
        • 存储空间利用率低，因为有一部分存放指针
        • 不能随机存取，因为数据存储物理上不连续
    • 索引存储结构
      • 定义：存储元素信息时附加建立索引表，索引表仅存储关键字和元素地址，便于查找
    • 哈希/散列存储
      • 定义：根据元素的关键字通过哈希函数计算出一个值作为元素的存储地址，便于查找（空间换时间）
  • 数据类型
    • 数据类型
      • 基本数据类型
      • 数组
      • 结构体
      • 共用体
    • 存储空间的分配
      • 静态存储空间分配
      • 动态存储空间分配
  • 抽象数据类型
    • 数据对象
    • 数据关系
    • 基本运算
• 算法及其描述
  • 算法
    • 定义：对特定问题求解步骤的描述，是指令的有限序列
    • 特点
      • 有穷性
      • 确定性
      • 可行性
      • 有输入：0或多个
      • 有输出：1或者多个
• 算法分析
  • 时间复杂度
    • 算法频度T(n)
    • 时间复杂度用T(n)的数量级表示，即T(n)=O(f(n))，其中O指的是数量级
    • 定义：随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同
    • NP问题：只能用指数级时间复杂度算法求解的问题
  • 空间复杂度
    • 定义：一个算法运行过程中临时占用存储空间的大小
• 数据结构+算法=程序