《数据结构》第一章-绪论

《数据结构》第一章-绪论知识梳理，包括数据结构的基本概念、算法和算法评价两部分内容。

绪论

• 数据结构的基本概念
  • 1. 基本概念和术语
    • 数据
      • 信息的载体，描述客观事物属性的数
    • 数据元素
      • 数据的基本单元，由若干数据项组成
        • 数据项：构成数据元素的最小单位
    • 数据对象
      • 具有相同性质的数据元素的集合
    • 数据类型
      • 原子类型
      • 结构类型
      • 抽象数据类型
        • 抽象数据组织及与之相关的操作
    • 数据结构
      • 相互之间存在一种或多种特定关系的数据元素的集合
  • 2. 数据结构的三要素
    • 逻辑结构：数据元素之间的逻辑关系
      • 线性结构
      • 集合
      • 树形结构
      • 图状结构（网状结构）
    • 存储结构：数据结构在计算机中的表示（又称映像），又称物理结构
      • 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
        • 优点：可以实现随机存取，占用存储空间少
        • 缺点：只能使用相邻的一整块存储单元，可能产生外碎片
      • 链式存储：借助指示元素存储地址的指针来表示元素之间的逻辑关系
        • 优点：不会出现碎片，充分利用所有存储单元
        • 缺点：指针占用额外空间，且只能实现顺序存取
      • 索引存储：在存储元素信息的同时，还建立附加的索引表
        • 优点：检索速度快
        • 缺点：索引表占用额外空间；增删数据时需修改索引表，更费时
      • 散列存储（哈希存储）：根据元素的关键词直接计算出该元素的存储地址
        • 优点：检索、增删结点操作都很快
        • 缺点：若散列函数不好，则可能出现元素存储单元冲突，造成额外的时空开销
    • 数据的运算
      • 运算的定义
        • 针对逻辑结构，指出运算的功能
      • 运算的实现
        • 针对存储结构，指出运算的具体操作步骤
• 算法和算法评价
  • 概念
    • 定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列
    • 特征
      • 有穷性
      • 确定性
      • 可行性
      • 输入
      • 输出
    • 目标
      • 正确性
      • 可读性
      • 健壮性
      • 效率与低存储量需求
  • 算法效率的度量
    • 时间复杂度
      • 基本公式：
        • T(n)——算法中所有语句的频度之和
        • f(n)——算法中基本运算的频度
        • O——数量级
        • 公式定义：若T(n)和f(n)是定义在正整数集合上的两个函数，则存在正常数C和n0，使得当n>=n0时，都满足0=<T(n)=<Cf(n)
      • 分类
        • 最坏时间复杂度
        • 平均时间复杂度
        • 最好时间复杂度
      • 运算规则
        • a. 加法规则
        • b. 乘法规则
      • 常见的渐进时间复杂度
    • 空间复杂度
      • 定义：算法耗费的存储空间
      • 公式：
      • 算法原地工作是指算法所需的辅助空间为常量，即O(1)