数据结构绪论

1.1 数据结构的基本概念

数据、数据元素、数据项、数据对象

数据：信息的载体，能被计算机识别、存储和处理的符号总称。例如整数、字符、声音、图像等。
数据元素：数据的基本单位，在程序中作为一个整体处理。例如学生表中的一条学生记录是一个数据元素。
数据项：数据元素由若干数据项组成，数据项是数据的最小单位。例如学生记录中的学号、姓名、性别等。
数据对象：性质相同的数据元素的集合，是数据的一个子集。例如所有学生的集合是一个数据对象。

举例：在"学生信息管理系统"中，全体学生的信息是数据，每个学生的记录是一个数据元素，学号、姓名、年龄是数据项，所有学生的集合是数据对象。

数据结构

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。简单来说，数据结构 = 数据 + 结构，研究的是如何组织和存储数据。

1.2 数据结构三要素

数据结构包含三个要素：逻辑结构、存储结构、数据运算。

逻辑结构

逻辑结构是指数据元素之间的逻辑关系，与计算机的存储无关。分为四类：

集合结构：数据元素之间没有明确的关系，仅属于同一个集合。
线性结构：数据元素之间存在一对一的关系，如线性表、栈、队列。
树形结构：数据元素之间存在一对多的关系，如树、二叉树。
图形结构：数据元素之间存在多对多的关系，如图。

用数学语言描述：逻辑结构可以用二元组 (D, R) 表示，其中 D 是数据元素的集合，R 是 D 上的关系集合。

存储结构（物理结构）

存储结构是指数据在计算机内存中的存储方式。主要有四种：

存储方式	描述	优点	缺点
顺序存储	用连续的存储单元依次存储	随机存取方便	插入删除需移动大量元素
链式存储	用任意存储单元存储，通过指针关联	插入删除方便	存储密度低，需额外空间存指针
索引存储	建立索引表，索引项指向数据存放位置	查找速度快	需额外空间维护索引表
散列存储	根据关键字通过散列函数计算存储位置	查找速度极快	可能产生冲突，不易处理范围查询

数据运算

数据运算即对数据施加的操作，包括：

基本操作：创建、销毁、查找、插入、删除、修改等。
运算的定义：在逻辑结构上定义，指明功能。
运算的实现：在存储结构上实现，指明具体步骤。

📌 408考点提示：常以选择题考查数据结构三要素的区别，以及逻辑结构与存储结构的对应关系。例如：给出一种结构问属于哪种逻辑结构，或给出存储方式问属于哪种存储结构。

1.3 数据类型与抽象数据类型

数据类型

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例如 C 语言中的 int 类型，包括整数集合和加减乘除等操作。

抽象数据类型（ADT）

ADT 是一个数据模型以及定义在该模型上的一组操作。ADT 的定义只关心"做什么"，不关心"怎么做"，实现了封装和信息隐藏。

ADT 的定义格式：

ADT 抽象数据类型名 {
  数据对象：数据对象的定义
  数据关系：数据关系的定义
  基本操作：操作的定义
} ADT 抽象数据类型名

现实类比：把 ADT 想象成"自动售货机"。你只关心投币、选商品、取货（操作），不需要知道售货机内部如何识别硬币、如何传送商品（实现细节）。

1.4 算法与算法评价

算法的定义

算法是对特定问题求解步骤的一种描述，是指令的有限序列。算法必须满足五个特性：

特性	说明
有穷性	算法必须在有限步后结束
确定性	每条指令无歧义，相同输入产生相同输出
可行性	每条指令都可以通过已有操作实现
输入	有零个或多个输入
输出	有一个或多个输出

算法的评判标准

正确性：算法能正确解决问题。
可读性：算法易于理解。
健壮性：能处理异常输入。
效率与低存储量需求：时间效率高、空间占用少。

💡 记忆技巧：五个特性记作"有确可输出"，其中"有"=有穷性、"确"=确定性、"可"=可行性、"输"=输入、"出"=输出。

1.5 时间复杂度分析

大O表示法

时间复杂度是算法中基本操作执行次数的数量级，用大O表示法描述。T(n) = O(f(n)) 表示当 n 趋于无穷大时，T(n) 的上界是 f(n) 的常数倍。

常见的时间复杂度（按增长速度升序排列）：

复杂度	名称	示例
O(1)	常数阶	数组随机访问
O(log n)	对数阶	二分查找
O(n)	线性阶	顺序查找
O(n log n)	线性对数阶	快速排序、归并排序
O(n²)	平方阶	冒泡排序、选择排序
O(n³)	立方阶	矩阵乘法（朴素）
O(2ⁿ)	指数阶	斐波那契数列递归
O(n!)	阶乘阶	旅行商问题（暴力法）

时间复杂度分析方法

找基本操作：找到最内层的循环操作。
分析执行次数：计算基本操作的执行次数。
取数量级：忽略低阶项和常数系数，取最高阶。

示例1：单层循环

for (i = 0; i < n; i++) {
    a[i] = 0;  // 基本操作
}

基本操作执行 n 次，T(n) = O(n)。

示例2：双层循环

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        a[i][j] = 0;  // 基本操作
    }
}

基本操作执行 n×n = n² 次，T(n) = O(n²)。

示例3：对数阶

for (i = 1; i < n; i = i * 2) {
    // 基本操作
}

设执行 k 次后条件不满足，则 2^k ≥ n，k = log₂n，T(n) = O(log n)。

示例4：递归函数的时间复杂度

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

T(n) = T(n-1) + T(n-2) + O(1)，解为 T(n) = O(2ⁿ)。

三种复杂度分析

最坏时间复杂度：算法在最坏情况下的时间复杂度（常用）。
平均时间复杂度：所有可能输入等概率出现时的时间复杂度。
最好时间复杂度：算法在最理想情况下的时间复杂度（极少使用）。

1.6 空间复杂度分析

空间复杂度 S(n) 表示算法运行时所需的存储空间数量级。

要点：

包括输入数据占用空间、程序代码占用空间、辅助变量占用空间。
通常只考虑额外空间（除输入数据外的空间）。
原地工作（in-place）算法的空间复杂度为 O(1)。

示例1：常量空间

int sum(int a[], int n) {
    int s = 0;  // 辅助变量
    for (int i = 0; i < n; i++) s += a[i];
    return s;
}

辅助空间为常数个变量，S(n) = O(1)。

示例2：线性空间

int* copy(int a[], int n) {
    int *b = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) b[i] = a[i];
    return b;
}

辅助数组 b 占用 n 个 int 空间，S(n) = O(n)。

示例3：递归的空间复杂度

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n-1);
}

递归深度为 n，每层需一个栈帧，S(n) = O(n)。

复杂度的对比与理解

为了正确分析算法复杂度，需要记住以下几个原则：

常数系数不影响数量级：O(2n) = O(n)，O(100n²) = O(n²)
低阶项可以忽略：O(n² + n) = O(n²)
嵌套循环：内外层循环次数相乘
并列循环：各段复杂度取最大值
递归算法：需要建立递推关系式求解

常见递推关系式的求解：

T(n) = T(n-1) + O(1) → O(n)
T(n) = T(n-1) + O(n) → O(n²)
T(n) = 2T(n/2) + O(n) → O(n log n)（归并排序）
T(n) = T(n/2) + O(1) → O(log n)（二分查找）
T(n) = T(n-1) + T(n-2) + O(1) → O(2ⁿ)

常用复杂度大小比较

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

在 n 较大时，不同复杂度的差距非常显著。例如 n=10⁶ 时：

O(log n) ≈ 20 次操作
O(n) ≈ 10⁶ 次操作
O(n²) ≈ 10¹² 次操作（不可接受）

📌 408考点提示：时间复杂度是必考内容，常见题型包括：

分析循环嵌套的时间复杂度（注意循环变量的变化规律）
分析递归函数的时间复杂度（常见递推式：T(n) = T(n-1) + O(n) → O(n²)）
比较不同算法的时间复杂度
给代码段选择正确的时间复杂度

⚠️ 易错点：

不要遗漏循环条件中的变量变化，如 i = i * 2 是 O(log n)，不是 O(n)。
多层循环嵌套并不一定就是 O(n²)，如内层循环次数变化的情况。
递归算法的空间复杂度要考虑递归调用栈的深度。

1.7 题型示例

例题1：分析以下代码的时间复杂度。

int i = 1, k = 0;
while (i < n) {
    k++;
    i = i + 2;
}

解：每次循环 i 增加 2，设循环执行 m 次后 i ≥ n，则 1 + 2m ≥ n，m ≥ (n-1)/2。所以 T(n) = O(n)。

例题2：分析以下代码的时间复杂度。

for (i = 0; i < n; i++) {
    for (j = i; j < n; j++) {
        a[i][j] = 0;
    }
}

解：i=0 时内层执行 n 次，i=1 时执行 n-1 次，...，i=n-1 时执行 1 次。总次数 = n + (n-1) + ... + 1 = n(n+1)/2，T(n) = O(n²)。

例题3：分析以下代码的时间复杂度。

int func(int n) {
    if (n <= 1) return 1;
    return func(n-1) + func(n-2);
}

解：设 T(n) 为 func(n) 的执行时间，则 T(n) = T(n-1) + T(n-2) + O(1)。递归展开类似于斐波那契数列，是指数增长。T(n) = O(2ⁿ)。

例题4：分析以下代码的时间复杂度。

int i = 1;
while (i <= n) {
    for (int j = 1; j <= i; j++) {
        // 基本操作
    }
    i = i * 2;
}

解：外层循环 i 以指数增长（1, 2, 4, 8, ...），执行 k 次后 2^(k-1) ≤ n，k = log₂n + 1。内层循环次数随 i 变化：i=1 时 1 次，i=2 时 2 次，i=4 时 4 次，... 总次数 = 1 + 2 + 4 + ... + 2^(k-1) = 2^k - 1 ≤ 2n - 1 T(n) = O(n)。

复杂度的实际意义

理解复杂度有助于在实际编程中选择合适的数据结构和算法。例如：

当 n = 1000 时，O(n) 需要 1000 次操作，而 O(n²) 需要 1,000,000 次操作——差距悬殊。
这就是为什么大规模数据处理中，O(n log n) 的排序算法（快排、归并）优于 O(n²) 的排序算法（冒泡、选择）。
指数级 O(2ⁿ) 算法在 n > 30 时几乎不可用，需要寻找多项式时间的近似算法。

题型归纳

408 中复杂度分析题有几种常见的套路模式：

模式1：线性搜索型——单层循环，循环变量步长为 1

for (i = 0; i < n; i++) { ... }

T(n) = O(n)

模式2：搜索范围减半型——循环变量每次翻倍或减半

for (i = 1; i < n; i = i * 2) { ... }
for (i = n; i > 0; i = i / 2) { ... }

T(n) = O(log n)

模式3：矩形遍历型——双层循环，内外层都到 n T(n) = O(n²)

模式4：三角遍历型——双层循环，内层起始随外层变化

for (i = 0; i < n; i++)
    for (j = i; j < n; j++) { ... }

T(n) = O(n²)

模式5：分治递归型——T(n) = aT(n/b) + f(n)，套用主定理

主定理（Master Theorem）：T(n) = aT(n/b) + f(n)，其中 a ≥ 1，b > 1：

若 f(n) = O(n^(log_b(a)-ε))，则 T(n) = Θ(n^log_b(a))
若 f(n) = Θ(n^log_b(a))，则 T(n) = Θ(n^log_b(a) × log n)
若 f(n) = Ω(n^(log_b(a)+ε))，且 af(n/b) ≤ cf(n)，则 T(n) = Θ(f(n))

例题5：分析以下代码的时间复杂度。

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        for (k = 0; k < n; k++) {
            c[i][j] += a[i][k] * b[k][j];
        }
    }
}

解：三重循环嵌套，每层执行 n 次。总次数 = n × n × n = n³。T(n) = O(n³)。

本章总结

数据结构的三要素是贯穿全书的线索，时间/空间复杂度分析是所有算法学习的基础。408考试中，复杂度分析几乎每年都会出现，务必熟练掌握。理解"逻辑结构决定功能，存储结构决定效率"这一核心思想，对后续学习至关重要。

数据结构绪论