1. 数据

  1. 数据：数据是指对客观事物进行记录并且可以可以鉴别的抽象符号
  2. 数据元素：数据的基本单位，在计算机当中作为一个整体考虑
  3. 数据对象：具有相同性质的数据元素的集合
  4. 数据结构：计算机储存、组织数据的方式

2. 结构

  1. 逻辑结构：直接面向问题
    1. 集合
    2. 线性结构
    3. 树状结构
    4. 图结构
  2. 物理结构：面向计算机，数据元素的值+逻辑结构
    1. 连续设计：通过数据之间的相对位置来表示数据元素之间的逻辑关系
    2. 链接设计：通过存放的指针\(Pointer\)
  3. 逻辑结构和物理结构的区别和联系
    1. 区别：逻辑结构面向问题，物理结构面向计算机
    2. 联系：物理结构是面向计算机的具体的逻辑结构

3. 数据结构的运算

  1. 数据结构的组成部分
    • 逻辑结构：\(D\_S = (D , S)\)
    • 存储结构
    • 数据操作
  2. 数据结构的运算
    1. 会改变数据结构的运算操作
      1. 建立\((Create)\)一个数据结构
      2. 销毁\((Destroy)\)一个数据结构
      3. 从一个数据结构中删除\((Delete)\)一个数据元素
      4. 从一个数据结构中插入\((Insert)\)一个数据元素
    2. 不会改变数据结构本身的运算操作
      1. 对一个数据结构进行访问\((Access)\)
      2. 对一个数据结构中的元素进行修改\((Modify)\)
      3. 对数据结构中的所有元素进行排序\((Sort)\)
      4. 对一个数据结构进行查找\((Search)\)

4. 数据类型

  1. 数据类型：数据的取值范围 \(+\) 一系列操作
  2. 抽象数据类型\((ADT)\)：为了解决特定问题而定义的数据类型
  3. 二者的联系：数据类型是已定义好的抽象数据类型，抽象数据类型由数据类型组成

5. 算法

  1. 算法的概念：对特定问题求解方法的一种描述，是指令的有限序列
  2. 算法的特性
    1. 确定性：不能有二义性
    2. 可行性
    3. 输入/ 输出
    4. 有限性：一个算法总是在经历了有穷步的运算之后会终止
  3. 算法的描述方法
    1. 自然语言：用序号表示，避免自然段！
    2. 流程图
    3. 伪代码\((Pseudocode)\)
    4. 直接代码
  4. 评价算法的标准
    1. 正确性、可读性、通用性
    2. 健壮性\((Robustness)\)：有容错处理
    3. 效率与存储量需求：时间复杂度和空间复杂度
  5. 算法效率的分析
    1. 时间复杂度
      • \(\exists c>0,n>n_0,f(n) < cg(n)\)，则\(f(n) = O (g(n))\)
      • \(\exists c>0,n>n_0,f(n) > cg(n)\), 则\(f(n) = \Omega(g(n))\)
      • \(f(n) = O (g(n)) , f(n) = \Omega(g(n))\)，则\(f(n) = \Theta(g(n))\)
      • 常用的时间复杂度：\(O (1)<O (\log n)<O (n)<O (n\log n)<O (n^2)<O (n^3)<O (2^n)<O (n!)<O (n^n)\)
      • 简单的运算法则：
        • \(O (f)+O (g) = O (max(f,g))\)
        • \(O (f)\cdot O (g) = O (f*g)\)
        • \(O (cf(n)) = O (f(n))\)
    2. 空间复杂度