数据结构-绪论(1)

1.1 数据结构的基本概念

数据：信息的载体

数据元素：数据的基本单位，通常作为一个整体进行考虑，一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合

数据对象：具有相同性质的数据元素的集合，是数据的一个子集。

数据结构的三要素：逻辑结构、数据的运算、物理结构

数据的逻辑结构

  • 集合
  • 线性结构
  • 树形结构
  • 图形结构（网状结构）

数据的物理结构（存储结构）

  • 顺序存储（物理上连续）
  • 链式存储（物理上离散）
  • 索引存储
  • 哈希存储/散列存储

存储结构会影响存储空间分配的方便程度和数据运算的速度

数据的运算：施加在数据上的运算，包括运算的定义和实现。

运算的定义是针对逻辑结构的，运算的实现是针对存储结构的。

数据类型：一个值的集合和定义在此集合上的一组操作的总称

  • 原子类型。其值不可再分的数据类型。
  • 结构类型。其值可被分解为若干成分的数据类型

抽象数据类型(ADT)：抽象数据组织及与之相关的操作。

1.2 算法的基本概念

程序=数据结构+算法

算法：对特定问题求解步骤的一种描述，它是指令的有限序列。

算法的特性

  • 有穷性

  • 确定性

  • 可行性

  • 输入输出

算法是否好，取决于：

  • 正确性
  • 可读性
  • 健壮性
  • 高效率与低存储量需求

算法的时间复杂度

  • 加法规则

    \(T(n)=T_1(n)+T_2(n)=O(f(n))+O(g(n))=O(\max(f(n,g(n))))\)

  • 乘法规则

    \(T(n)=T_1(n)\times T_2(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))\)

比较算法的时间复杂度谁更高，判断 \(x\rightarrow \infty\) 时 \(f(x)\) 和 \(g(x)\) 的比值。

算法的空间复杂度

空间复杂度 \(S(n)\) 表示算法在运行过程中的所需的额外存储空间，是问题规模 \(n\) 的函数，记为 \[ S(n) = O(g(n)) \]