Minerno 
匿名 
Minerno
1.1 数据结构的基本概念
1.1.1 基本概念和术语
1. 数据
数据是信息的载体，被计算机程序识别和处理的符号的集合。
2. 数据元素
数据元素是数据的基本单位。通常作为一个个体。数据元素由若干个数据项组成，数据项是构成数据元素的不可分割的最小单位。
3. 数据对象
数据对象是具有相同性质的数据元素的集合，是一个数据的子集。
4. 数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1）原子类型：不可再分的数据类型。eg. bool、int等
2）结构类型：可再分解若干成分的数据类型。eg. struct结构体
3）抽象数据类型（ADT）：一个数学模型及定义在该数学模型上的一组操作。
5. 数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
1.1.2 数据结构三要素
1. 逻辑结构
逻辑结构是指数据元素之间的逻辑关系。
1）集合：同属一个集合，没有其他关系。
2）线性结构：只存在一对一的关系。
3）树形结构：存在一对多的关系。
4）图状结构或网状结构：存在多对多的关系。
2. 数据的存储结构
存储结构是指数据结构在计算机中的表示，也称物理结构。
1）顺序存储：相邻元素存储在相邻的物理位置。
2）链式存储：不要求存储在相邻的物理位置。
3）索引存储：存储元素信息的同时，还会建立附加的索引表。
4）散列存储：也称哈希表，根据元素的关键字直接计算出该元素的存储地址。
3. 数据的运算
基本运算：①查找第 i 个数据元素 ②在第 i 个位置插入元素 ③删除 ④修改
1.2 算法和算法评价
1.2.1 算法的基本概念
算法是对特定问题求解步骤的一种描述。程序 = 数据结构 + 算法。
五个重要特性：
1）有穷性
2）确定性
3）可行性
4）输入
5）输出
“好”算法应尽可能达到的目标：
1）正确性
2）可读性
3）健壮性
4）高效率与低存储需求
1.2.2 算法效率的度量
算法效率的度量是通过时间复杂度和空间复杂度来描述的。
1. 时间复杂度
问题规模：n
时间开销：T(n)
时间复杂度：
$$ T(n) = O(f(n)) \Leftrightarrow \lim_{n \to \infty} \frac{T(n)}{f(n)} = k $$
计算时间复杂度的两条规则：
1）加法规则：$T(n) = T_{1}(n)+T_{2}(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))$
2）乘法规则：$T(n) = T_{1}(n)\times T_{2}(n)=O(f(n))\times O(g(n))=O(f(n)\times g(n))$
常见的时间复杂度：
$$ O(1)<O(\log_{2}{n})<O(n)<O(n\log_{2}{n})<O(n^{2})<O(n^{3})<O(2^{n})<O(n!)<O(n^{n}) $$
2. 空间复杂度
空间复杂度 S(n)定义为该算法所需的存储空间。
$$ S(n) = O(g(n)) $$
算法原地工作是指算法所需的辅助空间为常量，即$O(1)$。