## 1 数据结构的基本概念

### 1.1 基本概念和术语

* 数据：信息的载体，描述客观事物属性，能被计算机识别处理的符号集合。
* 数据元素：数据的基本单位，作为一个元素进行考虑和处理。
* 数据类型：一个值的集合和定义以及一组操作的总称，分类：
  * 原子类型
  * 结构类型
  * 抽象数据类型
* 数据结构：数据元素之间的特定关系。
  * 包括三个方面：逻辑结构、存储结构、数据的运算

### 1.2 数据结构三要素

数据的**逻辑结构**：数据元素之间的逻辑关系，独立于计算机，分为以下两类：

* 线性结构
  * 线性表
  * 栈
  * 队列
  * 数组
* 非线性结构
  * 集合
  * 树
  * 图

数据的**存储结构**：数据结构在计算机中的表示（映像），也称**物理结构**。

* 顺序存储
* 链式存储
* 索引存储
* 散列存储

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

### 1.3 算法和算法评价

算法：特定问题求解步骤一种描述

特征：有穷性、确定性、可行性、输入、输出

优秀算法的标准：正确性、可读性、健壮性、效率与低存储量需求

效率的度量：时间复杂度、空间复杂度