数据结构绪论

算法时间复杂度,空间复杂度，数据结构基本概念，算法特性，数据对象，数据对象上关系的集合，数据对象基本操作的集合

绪论

• 基本概念和术语
  • 数据、数据元素、数据项、数据对象
    • 数据(Date)
      • 客观事务的符号表示，是所有能输入到计算机中并能被计算机程序处理的符号的总称。
    • 数据元素（Date Element）
      • 数据的基本单位，在计算机中通常作为一个整体考虑。用于完整的描述一个对象。
    • 数据项（Date Item）
      • 是组成数据元素的、有独立含义的、不可分割的最小单位。如学生的学号
    • 数据对象(Data Object)
      • 性质相同的数据元素的集合，是数据的一个子集。
  • 数据结构
    • 定义
      • 相互之间存在一种或多种关系的数据元素的集合。结构即是元素之间的关系
    • 组成
      • 逻辑结构
        • 从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的
        • 二要素
          • 数据元素
          • 关系
            • 数据元素之间的逻辑关系
              • 集合结构
                • 数据元素之间除同属一个结构之外，无其他关系。
              • 线性结构
                • 数据元素之间存在一对一的关系。按入学时间排列的学生信息表
              • 树结构
                • 元素之间存在一对多的关系。
              • 图结构、网状结构
                • 元素之间存在多对多关系。
        • 数据的逻辑结构
          • 线性结构
            • 线性表
              • 一般线性表
                • 线性表
              • 特殊线性表
                • 栈与队列
                • 字符串
              • 线性表的推广
                • 数组
                • 广义表
          • 非线性结构
            • 树结构
              • 树
              • 二叉树
            • 图结构
              • 有向图
              • 无向图
            • 集合结构
      • 存储结构
        • 定义
          • 数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。把数据对象存储到计算机时，通常要求存储各数据元素的数据，又要存储数据元素之间的逻辑关系。
        • 基本存储结构
          • 顺序存储结构
            • 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。通常借助数组。
            • 缺点
              • 要求元素依次存放在一片连续的存储空间中。
              • 容易产生存储碎片（无法利用的小存储块）
            • 优点
              • 随机存取
              • 存储密度大
          • 链式存储结构
            • 无需连续存储空间，但为了表示结点之间的关系，需要给每个节点附加指针字段，用于存储后继元素的存储地址。通常借助指针。
            • 借助指针来表示元素之间的逻辑关系。
            • 优点
              • 不会出现碎片现象，能充分利用存储空间
            • 缺点
              • 存储密度低（每个节点要多存储一个指向下一个元素存地址的指针）
              • 只能顺序存取。
          • 索引存储
            • 在存储元素信息的同时，还建立相应的索引表。索引表中每项称为索引项，索引项一般形式是（关键字，地址）
            • 优点：
              • 检索速度快
            • 缺点
              • 附加的索引表占用额外的存储空间
              • 增加、删除数据时要修改索引表，会浪费大量时间。
          • 散列存储
            • 根据元素的关键字直接计算出该元素的存储地址，又称哈希存储。
            • 优点
              • 检索快
              • 增加、删除快
            • 缺点
              • 若散列函数不好，则可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
      • 数据运算
        • 包括运算的定义和实现
          • 定义依赖于逻辑结构
          • 实现依赖于存储结构。
  • 数据类型和抽象数据类型
    • 数据类型
      • 一个值的集合和定义在这个值集合上的一组操作的总称。如整型，上有加减乘除
    • 抽象数据类型
      • 由用户定义的、表示应用问题的数据模型以及定义在这个模型上的一组操作的总称。
      • 具体内容
        • 数据对象
        • 数据对象上关系的集合
        • 数据对象基本操作的集合
• 算法和算法分析
  • 算法定义及特性
    • 算法
      • 为了解决某类问题而规定的一个有限长的操作序列。
      • 五个特性
        • 有穷性
          • 一个算法必须总是在有执行有穷步后结束，且每一步都必须在有穷时间内完成
        • 确定性
          • 对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者和阅读者都能明确其含义及如何执行。
        • 可行性
          • 算法的所有操作都可以通过已经实现了的基本操作运算执行有限次来实现。
        • 输入
          • 一个算法有零个或多个输入。
        • 输出
          • 一个算法有一个或多个输出，他们是算法进行信息加工后得到的结果。无输出的算法没有任何意义。
  • 评价算法优劣的基本标准
    • 正确性
      • 合理输入，有正确输出
    • 可读性
      • 便于理解和阅读
    • 健壮性
      • 输入非法，能适当的做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出。
    • 高效性
      • 由时间复杂度、空间复杂度衡量。
  • 算法时间复杂度
    • 问题规模和语句频度
      • 问题规模
        • 算法求解问题输入量的多少，是问题大小的本质表示，一般用n表示。一般情况下n越大，算法执行时间越长。
      • 语句频度
        • 一条语句重复执行次数称作语句频度
        • 设每条语句执行一次所需时间均是单位时间，则一个算法的执行时间可以由该算法中所有语句频度之和来度量。
    • 算法的时间复杂度定义
      • 使用算法中基本语句的执行次数来度量算法的工作量。
      • 基本执行语句
        • 算法中重复执行次数和算法的执行时间成正比的语句。对算法运行时间贡献最大。
      • 一般情况下基本语句的执行次数是问题规模n的某个函数f( n ),算法的时间复杂度记为T(n)= O(f(n))
      • 常用最坏时间复杂度衡量算法时间复杂度
      • 影响因素
        • 问题规模n
        • 数据逻辑结构
        • 数据存储结构
        • 待处理数据的初态
  • 算法空间复杂度
    • 空间复杂度
      • 算法所需存储空间的度量。
      • 也是问题规模n的一个函数
      • 若算法执行时所需的辅助空间相对于输入量而言是一个常数，则称这个算法为原地工作，空间复杂度为O( 1 )
• 数据结构是一门研究非数值计算程序设计中操作对象，以及这些对象之间的关系和操作的学科。