1.1 数据结构基本概念
1.1.1 基本概念和术语
-
数据（data）：
- 是对客观事物的符号化表示
- 指能被输入计算机并被计算机处理的符号总称（集合）
- 信息的载体
- 能被计算机识别、存储和加工
分类：数值型和非数值型
-
数据元素（data element）：
是数据的基本单位，通常作为一个整体进行考虑和处理，用于完整地描述一个对象，一个数据元素可由若干数据项组成，如一条学生记录为一个数据元素，其由学号、姓名、性别等数据项组成。
-
数据项（data item）：
数据项是数据元素不可分割的最小单位
- 由多个属性组成的数据项又称为“组合项”
-
数据对象（data object）：
具有相同性质的数据元素的集合，是数据的一个子集，如整数数据对象就是一个集合
- 同一个数据对象中的数据元素可以根据不同的逻辑关系组成不同的数据结构
-
数据结构（data structure）：
数据结构是相互之间存在一种或多种特定关系的数据元素的集合
- 同样的数据元素，可组成不同的数据结构
- 不同的数据元素，可组成相同的数据结构
- 数据元素相互间的关系称为结构，数据结构包含三方面内容：逻辑结构、存储结构、数据的运算
-
数据类型：
数据类型是一个值的集合和定义在此集合上的一组操作的总称，分为原子类型和结构类型
原子类型： 值不可再分的数据类型，如bool、int类型
结构类型： 值可再分解为若干成分（分量）的数据类型，如struct结构体
-
抽象数据类型（ADT）：
ADT 用数字化的语言定义数据的逻辑结构、定义运算，也就是定义了一个数据结构（与具体的实现无关，因为需要确定存储结构才能实现数据结构）
1.1.2 数据结构三要素
-
数据结构三要素从数据元素出发，包括逻辑结构、存储结构（物理结构）和数据的运算
-
逻辑结构和数据的运算是在定义一种数据结构，存储结构则是关于如何用计算机实现这种数据结构
-
数据的逻辑结构和存储结构是密不可分的两方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构
-
数据的逻辑结构：
指数据元素之间的逻辑关系，即从逻辑关系上描述数据。与数据如何存储无必然关联，是独立于计算机的，是从具体问题抽象出来的数学模型，如学生信息表中的学生按学号顺序排列。
数据的逻辑结构分为线性结构和非线性结构
线性结构： 有且仅有一个开始和终端结点，每个结点最多只有一个直接前趋和后继，如线性表（栈、队列、串）
非线性结构： 一个结点可能有多个直接前趋和直接后继，如集合、树、图
-
数据的存储结构（物理结构）：
指数据结构在计算机中的存储表示（也称映像），包括数据元素的表示和关系的表示。
常见的四种存储结构：（优缺点见书P3）
-
顺序存储： 将逻辑上相邻的元素存储在物理位置业相邻的存储单元中
-
链式存储： 逻辑上相邻的元素在物理位置上也可以不相邻，通过指针来表示元素之间的逻辑关系
-
索引存储： 在存储元素信息的同时，建立附加的索引表
-
散列存储： 根据元素的关键字直接计算出元素的存储地址，又称哈希存储
链式存储、索引存储、散列存储统称为非顺序存储（离散存储）
数据的存储结构会影响存储空间分配的方便程度以及对数据运算的速度
-
-
数据的运算：
针对于某种逻辑结构，结合实际需求，定义基本运算，如数据的增删改查等
运算的定义是针对逻辑结构的，指出运算的功能
运算的实现是针对存储结构的，指出运算的具体操作步骤
1.2 算法
1.2.1 算法的基本概念
-
程序 = 数据结构 + 算法
-
算法： 是对特定问题求解步骤的一种描述，关注如何高效地处理数据以解决实际问题
（数据结构和算法的关系可比喻为“做番茄炒蛋”，数据结构是提供的食材，算法则是将食材制作出菜品的步骤）
-
算法的 5 个重要特性：
- 有穷性：算法必须在又穷步后结束，且每一步可在有穷时间内完成
- 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得到相同的输出
- 可行性：算法中描述的操作都可通过已实现的基本运算执行有限次来实现
- 输入：一个算法有零个或多个输入
- 输出：一个算法有一个或多个输出，输出与输入有某种特定关系
-
算法效率的度量是通过时间复杂度和空间复杂度来描述的
（算法的优劣则要综合考虑时空效率、算法的五个重要特性等方面来综合考量）
1.2.2 时间复杂度
-
算法的时间复杂度：是在事前预估算法时间开销 \(T(n)\) 与问题规模 \(n\) 的关系（ \(T\) 表示“time”）.
-
算法例1：
void loveYou(int n){int i=1; // (1)while(i<=n){ // (2)i++; // (3)printf("I Love You %d\n", i); // (4)}printf("I Love You More Than %d\n", n); // (5) }int main(){loveYou(3000);/* (1) --1次(2) --3001次(3) --3000次(4) --3000次(5) --1次T(3000) = 1 + 3001 + 2*3000 + 1可得时间开销与问题规模的关系：T(n) = 3n+3只考虑高阶部分：T(n) = O(n)*/ } -
算法的时间度量：
\(T(n) = O(f(n))\)，大 O 表示“同阶”，同等数量级，即 \(T(n) = O(f(n)) \Leftrightarrow \lim_{n \to \infty}\frac{T(n)}{f(n)} = k(常数)\)
-
加法规则：
\(T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(\max(f(n),g(n)))\)，多项相加，只保留最高阶项，系数变为1
-
乘法规则：
\(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_2n)<O(n)<O(n\log_2n)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)\)
-
计算时间复杂度总结：
(1) 顺序执行的代码对时间复杂度影响小，可忽略
(2) 只需挑取循环中一个基本操作分析其执行次数与 n 的关系即可
(3) 当存在多层嵌套循环，通常只需关注嵌套最深的循环循环了几次
(4) 通常需要考虑的是最坏时间复杂度和平均时间复杂度
1.2.3 空间复杂度
- 主要来自辅助空间、递归调用栈等，结合后续章节学习