第1章 绪论

1. 数据结构的基本概念

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机识别和处理的符号的集合。
数据类型

• 原子类型：其值不可再分的数据类型。
• 结构类型：其值可以再分解为若干成分的数据类型。
• 抽象数据类型（ADT）：对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括三方面内容：逻辑结构、存储结构和数据的运算。一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

2. 数据结构的三要素

2.1 逻辑结构

逻辑结构与数据的存储无关，是独立于计算机的。数据的逻辑结构分为线性结构和非线性结构。
典型的线性结构：线性表。
典型的非线性结构：集合、树和图。

2.2 存储结构

存储结构是指数据结构在计算机中的表示，也称物理结构。数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。

1. 顺序存储
   优点：可以实现随机存取，每个元素占用最少的存储空间。
   缺点：只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
2. 链式存储
   优点：不会出现碎片现象，能充分利用所有存储单元。
   缺点：每个元素因存储指针而占用额外的存储空间，且只能实现顺序存取。
3. 索引存储
   优点：检索速度快。
   缺点：附加的索引表额外占用存储空间。另外，增加和删除数据时也要修改索引表，因而会花费较多时间。
4. 散列存储
   优点：检索、增加和删除结点的操作都很快。
   缺点：若散列函数不好，则可能出现元素存储单元冲突，而解决冲突会增加时间和空间的开销。

2.3 数据的运算

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

3. 算法的基本概念

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。

1. 有穷性：执行有穷步之后结束
2. 确定性：指令必须有确切的含义
3. 可行性：基本运算执行有限次来实现
4. 输入
5. 输出

4. 算法效率的度量

4.1 时间复杂度

算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法的时间复杂度记为T(n)=O(f(n))。O的含义是T(n)的数量级。
在分析一个程序的时间复杂性时，有以下两条规则：

1. 加法规则：T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
2. 乘法规则：T(n)=T1(n)×T2(n)=O(f(n))×O(g(n))=O(f(n)×g(n))

常见的渐近时间复杂度为：O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

4.2 空间复杂度

算法的空间复杂度S(n)定义为该算法所需的存储空间，S(n)=O(g(n))，只需分析除输入和程序之外的额外空间。
算法原地工作是指算法所需的辅助空间为常量，即O(1)。