数据结构绪论

发表于   |   分类于   |  

摘要

数据结构的绪论部分，涉及最为基本的概念，以及算法评价。

基本概念

  • 数据
  • 数据元素：可有若干数据项组成
  • 数据对象：相同性质数据元素的集合
  • 数据类型
    • 原子类型
    • 结构类型
    • 抽象数据类型：抽象数据组织和与之相关的操作。可以用来定义一个完整的数据结构
  • 抽象数据类型（ADT）：通常包含数据对象，数据关系，基本操作
  • 数据结构：三要素：逻辑结构，存储结构和数据的运算
    • 逻辑结构：线性结构和非线性结构
    • 存储结构：
      • 顺序存储：优：随机存储，缺：外部碎片
      • 链接存储：优：没有碎片，缺：只能顺序存储
      • 索引存储：优：检索速度快，缺：附加索引表
      • 散列存储：优：Hash存储，缺：存储冲突

  • 数据的运算：定义是针对逻辑结构进行的，实现是针对存储结构的

  • 注意点

    • 链式存储设计时，节点内的存储单元地址一定是连续的

算法以及算法评价

  • 算法

    • 5个特性
      • 有穷性
      • 确定性
      • 可行性
      • 输入
      • 输出

  • 算法效率的度量

    • 时间复杂度

      • 类别: 最好时间、平均时间、最坏时间
      • 加法规则: T(n) = T1(n)+T2(n) = O(f(n))+O(g(n)) = O(max(f(n)，g(n))
      • 乘法规则: T(n) = T1(n)T2(n) = O(f(n))+O(g(n)) = O(f(n)g(n))
      • 常见渐近时间: O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n)
        < O(n!) < O(n^n)

    • 空间复杂度

      • 原地工作: S(n) = O(1)

    • 注意点

      • 执行次数 or 时间复杂度
      • 是否为大O(n)