数据结构

把逻辑上相邻的元素存储在物理位置上相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现、逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。

数据结构

• 基本概念
  • 数据
  • 数据元素，数据项
  • 数据对象，数据结构
    • 数据对象是具有同同性质的数据元素的集合，是数据的一个子集。
    • 数据结构是具有相互之间存在一种或多种特定关系的数据元素的集合。
  • 数据类型，抽象数据类型（ADT）
    • 数据类型是一个值的集合和定义在此集合上的一组操作的总称。
      • 原子类型
        • 其值不可再分的数据类型。
          • bool
          • int
      • 结构类型
        • 其值可以再分解为若干成分的数据类型。
    • 抽象数据类型是抽象数据组织及与之相关的操作。
• 三要素
  • 逻辑结构
    • 集合
    • 线性结构
    • 图形结构
    • 树形结构
  • 物理结构（存储结构）
    • 顺序存储
      • 把逻辑上相邻的元素存储在物理位置上相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现
    • 链式存储
      • 逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
        • 
    • 索引存储
      • 在存储元素信息的同时，还建立附加的索引表，所以表中的每项称为索引项，索引项的一般形式是（关键字，地址）。
    • 散列存储
      • 根据元素的关键字，直接计算出该元素的存储地址又称哈希存储。
  • 数据运算
• 算法
  • 算法的特性
    • 有穷性。
      • 一个算法必须总在执行有穷步之后结束。且每一步都可以在有穷时间内完成。
        • 算法是有穷的
        • 程序可以是无穷的
    • 确定性
      • 算法中每条指令必须有确切的含义，对于相同的输入。只能得出相同的输出。
    • 可行性
      • 算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
    • 输入
      • 一个算法有零个或多个输入，这些输入取决于某个特定的对象的集合。
    • 输出
      • 一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
  • 好算法的特质。
    • 可读性
    • 正确性
    • 健壮性。
    • 高效率与低存储量需求。
  • 算法的效率的度量
    • 时间复杂度
    • 空间复杂度