数据结构与算法分析：C语言描述（第2版）

前言

《数据结构与算法分析：C语言描述》是计算机科学领域的经典教材，由 Mark Allen Weiss 教授编写。本书以C语言为实现工具，系统阐述了数据结构的设计原理、算法分析方法及实际应用场景，是学习数据结构与算法的权威参考资料。

本笔记基于第2版内容，进行了深度扩展和专业优化，不仅对核心知识点、关键算法实现、时间复杂度分析及应用场景进行详细梳理，还增加了以下专业内容：

适用人群

  • 计算机科学专业学生：希望深入理解数据结构与算法底层原理的学生
  • 软件工程师：需要在实际项目中选择和实现高效数据结构与算法的工程师
  • 系统软件开发者：需要编写高性能系统代码的开发者
  • 算法竞赛选手：参加算法竞赛的选手，需要掌握高效算法实现
  • 技术面试官：需要评估候选人算法能力的面试官
  • 教育工作者：教授数据结构与算法课程的教师

核心价值

  • 底层原理：深入剖析数据结构的底层实现原理和算法设计思想
  • 性能优化：详细分析各种数据结构和算法的性能特性，提供优化策略
  • 实际应用：结合实际项目场景，讲解数据结构与算法的选择和使用
  • 代码质量：提供高质量的C语言实现，注重代码的可读性、健壮性和效率
  • 专业深度：涵盖高级数据结构和算法，如平衡树、图算法、高级排序等
  • 理论与实践：平衡理论分析和实践实现，帮助读者建立完整的知识体系

技术特点

  • C语言实现：使用标准C语言实现各种数据结构和算法，注重内存管理和指针操作
  • 时间复杂度分析：详细的时间复杂度推导和分析，包括最坏情况、平均情况和最好情况
  • 空间复杂度分析：分析各种数据结构的空间开销和内存使用模式
  • 性能对比：对比不同数据结构和算法在不同场景下的性能表现
  • 代码优化：提供代码优化技巧和性能调优建议
  • 错误处理：注重代码的错误处理和边界情况处理

本笔记的目标是帮助读者不仅掌握数据结构与算法的基本概念和实现方法，更能深入理解其设计原理和性能特性，从而能够在实际项目中选择和实现高效的数据结构与算法，编写出更优质的代码。

1. 算法分析基础

1.1 基本概念

  • 数据结构：数据元素之间的组织关系，决定了数据的存储方式和操作方法。

    • 逻辑结构：数据元素之间的逻辑关系（如线性结构、树形结构、图形结构）。
    • 物理结构：数据在计算机内存中的存储方式（如连续存储、离散存储）。
    • 抽象数据类型（ADT）：定义数据的逻辑结构、操作和特性的数学模型。

  • 算法：解决特定问题的有限步骤集合，需满足以下五大特征：

    • 有穷性：算法在有限步骤后必然终止。
    • 确定性：每一步操作都有明确的定义，无歧义。
    • 可行性：每一步操作都可以通过有限次数的基本操作实现。
    • 输入：算法接受零个或多个输入。
    • 输出：算法产生至少一个输出。

  • 时间复杂度：衡量算法执行时间随输入规模 ( n ) 增长的变化趋势，忽略常数因子和低阶项。

    • 渐进时间复杂度：当输入规模 ( n ) 趋近于无穷大时的时间复杂度。
    • 大O记号：表示算法时间复杂度的上界。
    • 大Ω记号：表示算法时间复杂度的下界。
    • 大Θ记号：表示算法时间复杂度的紧界（同时是上界和下界）。

  • 空间复杂度：衡量算法所需额外空间（除输入外）随输入规模增长的变化趋势。

    • 辅助空间：算法执行过程中临时使用的空间。
    • 原地算法：空间复杂度为 ( O(1) ) 的算法，不需要额外辅助空间。

1.2 大O记号的数学定义

  • 大O记号：若存在正常数 ( c ) 和 ( n_0 )，使得当 ( n \geq n_0 ) 时，有 ( T(n) \leq c \cdot f(n) )，则称 ( T(n) = O(f(n)) )。

    • 含义：算法的执行时间最多是 ( f(n) ) 的常数倍，描述了算法时间复杂度的上界。
    • 示例：( 3n^2 + 2n + 1 = O(n^2) )，因为存在 ( c=4 ) 和 ( n_0=1 )，使得 ( 3n^2 + 2n + 1 \leq 4n^2 ) 对所有 ( n \geq 1 ) 成立。

  • 大Ω记号：若存在正常数 ( c ) 和 ( n_0 )，使得当 ( n \geq n_0 ) 时，有 ( T(n) \geq c \cdot f(n) )，则称 ( T(n) = \Omega(f(n)) )。

    • 含义：算法的执行时间至少是 ( f(n) ) 的常数倍，描述了算法时间复杂度的下界。

  • 大Θ记号：若存在正常数 ( c_1, c_2 ) 和 ( n_0 )，使得当 ( n \geq n_0 ) 时，有 ( c_1 \cdot f(n) \leq T(n) \leq c_2 \cdot f(n) )，则称 ( T(n) = \Theta(f(n)) )。

    • 含义：算法的执行时间与 ( f(n) ) 同阶，描述了算法时间复杂度的紧界。

1.3 常见时间复杂度比较

按增长率从小到大排序：

( O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) )

  • 常数时间 ( O(1) )：操作时间与输入规模无关，如数组访问、哈希表查找（平均情况）。
  • 对数时间 ( O(\log n) )：操作时间与输入规模的对数成正比，如二分查找、平衡二叉树操作。
  • 线性时间 ( O(n) )：操作时间与输入规模成正比，如线性查找、遍历数组。
  • 线性对数时间 ( O(n \log n) )：操作时间与输入规模的对数乘积成正比，如快速排序、归并排序、堆排序。
  • 平方时间 ( O(n^2) )：操作时间与输入规模的平方成正比，如冒泡排序、插入排序、选择排序。
  • 立方时间 ( O(n^3) )：操作时间与输入规模的立方成正比，如矩阵乘法的朴素实现。
  • 指数时间 ( O(2^n) )：操作时间与输入规模的指数成正比，如子集和问题的暴力解法。
  • 阶乘时间 ( O(n!) )：操作时间与输入规模的阶乘成正比，如旅行商问题的暴力解法。

1.4 时间复杂度分析方法

  1. 循环分析：

    • 单层循环：时间复杂度为循环次数，如 ( O(n) )。
    • 嵌套循环：时间复杂度为各层循环次数的乘积，如双层循环 ( O(n^2) )，三层循环 ( O(n^3) )。
    • 非嵌套循环：时间复杂度为各循环次数的最大值，如 ( O(n) + O(n^2) = O(n^2) )。
    • 递减循环：循环变量每次减少固定比例，时间复杂度为 ( O(\log n) )，如二分查找。

  2. 递归分析：

    • 递归树法：将递归过程展开为树结构，计算各层的时间复杂度之和。
    • 主定理（Master Theorem）：用于分析分治算法的时间复杂度，适用于形如 ( T(n) = aT(n/b) + f(n) ) 的递归关系式。
    • 代入法：猜测时间复杂度，然后通过数学归纳法证明。

  3. 最坏/平均/最好情况分析：

    • 最坏情况：算法在输入规模 ( n ) 下的最大执行时间，如线性查找的 ( O(n) )。
    • 平均情况：算法在所有可能输入下的期望执行时间，需考虑输入概率分布，如线性查找的 ( O(n/2) = O(n) )。
    • 最好情况：算法在输入规模 ( n ) 下的最小执行时间，如线性查找的 ( O(1) )。

  4. ** amortized分析（均摊分析）**：

    • 聚合分析：计算所有操作的总时间，然后除以操作次数。
    • 核算法：为每个操作分配一个”信用”，用于支付未来操作的时间。
    • 势能法：定义一个势能函数，用于衡量系统的”势能”，势能的变化反映操作的时间。

1.5 示例：时间复杂度计算

示例1：计算数组元素和（( O(n) )）

1
2
3
4
5
6
7
8
// 计算数组元素和
int sum(int arr[], int n) {
    int total = 0;              // 1次
    for (int i = 0; i < n; i++) {  // n次循环
        total += arr[i];         // 1次/循环，共n次
    }
    return total;               // 1次
}

时间复杂度分析：

  • 初始化变量：1次操作
  • 循环：n次迭代，每次1次加法操作
  • 返回结果：1次操作
  • 总操作次数：( 1 + n + 1 = n + 2 )
  • 时间复杂度：( O(n) )（忽略常数项和低阶项）

示例2：嵌套循环（( O(n^2) )）

1
2
3
4
5
6
7
8
// 打印所有可能的数对
void printPairs(int n) {
    for (int i = 0; i < n; i++) {    // n次外层循环
        for (int j = 0; j < n; j++) {  // n次内层循环/外层循环，共n²次
            printf("%d %d\n", i, j);  // 1次/内层循环
        }
    }
}

时间复杂度分析：

  • 外层循环：n次迭代
  • 内层循环：每次外层循环执行n次迭代
  • 总操作次数：( n \times n = n^2 )
  • 时间复杂度：( O(n^2) )

示例3：二分查找（( O(\log n) )）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 二分查找（假设数组已排序）
int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 避免整数溢出
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

时间复杂度分析：

  • 每次循环将搜索范围缩小一半
  • 最多需要 ( \log_2 n ) 次循环
  • 时间复杂度：( O(\log n) )

示例4：归并排序（( O(n \log n) )）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 归并两个已排序的子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 创建临时数组
    int L[n1], R[n2];
    
    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    
    // 归并临时数组回原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    
    // 复制剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 归并排序
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // 避免整数溢出
        
        // 递归排序左半部分
        mergeSort(arr, left, mid);
        // 递归排序右半部分
        mergeSort(arr, mid + 1, right);
        // 归并两个已排序的部分
        merge(arr, left, mid, right);
    }
}

时间复杂度分析：

  • 递归关系式：( T(n) = 2T(n/2) + O(n) )
  • 使用主定理：( a=2, b=2, f(n)=O(n) )
  • 因为 ( f(n) = O(n^{\log_b a}) = O(n^1) )，所以 ( T(n) = O(n \log n) )
  • 时间复杂度：( O(n \log n) )

1.5 空间复杂度分析

  • 示例1：线性搜索

    • 空间复杂度：( O(1) )（只使用常数级辅助空间）

  • 示例2：归并排序

    • 空间复杂度：( O(n) )（需要额外的临时数组）

  • 示例3：递归函数

    • 空间复杂度：( O(n) )（递归调用栈的深度）

  • 示例4：动态规划

    • 空间复杂度：( O(n^2) )（二维动态规划表）
    • 优化后：( O(n) )（只使用一维动态规划表）

1.6 算法优化策略

  1. 时间优化：

    • 选择更高效的算法：如使用快速排序代替冒泡排序
    • 减少时间复杂度：如使用哈希表将查找时间从 ( O(n) ) 优化到 ( O(1) )
    • 减少常数因子：如循环展开、内联函数、编译器优化
    • 避免重复计算：如使用记忆化技术缓存中间结果

  2. 空间优化：

    • 使用原地算法：如原地排序算法
    • 减少数据结构的空间开销：如使用位压缩技术
    • 复用空间：如使用双指针技术减少辅助空间
    • 垃圾回收：及时释放不再使用的内存

  3. 代码优化：

    • 减少函数调用：避免频繁的函数调用开销
    • 减少内存访问：利用缓存局部性，减少缓存未命中
    • 使用合适的数据结构：根据操作特点选择合适的数据结构
    • 并行化：利用多核处理器进行并行计算

2. 线性表

2.1 数组

  • 静态数组：

    • 定义：编译时固定大小，内存连续分配的同类型元素集合。
    • 优点：
      • 随机访问时间复杂度 ( O(1) )（通过索引直接访问）
      • 内存布局紧凑，缓存利用率高
      • 实现简单，空间开销小
    • 缺点：
      • 插入/删除操作时间复杂度 ( O(n) )（需要移动元素）
      • 容量固定，无法动态调整
      • 可能造成内存浪费（分配的空间大于实际需要）

  • 动态数组：

    • 定义：运行时通过 malloc/realloc 动态分配内存，可根据需要自动扩容。
    • 优点：
      • 容量可动态调整，适应数据量变化
      • 保持随机访问时间复杂度 ( O(1) )
      • 空间利用率较高（按需扩容）
    • 缺点：
      • 插入/删除操作时间复杂度 ( O(n) )
      • 扩容操作可能导致内存拷贝，影响性能
      • 需要手动管理内存，容易出现内存泄漏

  • 扩容策略：

    • 翻倍扩容：每次扩容为原容量的2倍，平均时间复杂度 ( O(1) )（均摊分析）
    • 线性扩容：每次扩容固定大小，时间复杂度 ( O(n) )
    • 混合扩容：结合翻倍和线性扩容的优点

  • 内存管理：

    • 内存分配：使用 malloc/calloc 分配内存
    • 内存重分配：使用 realloc 调整内存大小
    • 内存释放：使用 free 释放内存，避免内存泄漏
    • 内存对齐：考虑数据类型的内存对齐要求，提高访问速度

动态数组实现示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
// 动态数组结构体
typedef struct {
    int *data;   // 数据指针
    int size;    // 当前元素个数
    int capacity;// 容量
} DynamicArray;

/**
 * 初始化动态数组
 * @param arr 动态数组指针
 * @param initialCapacity 初始容量
 * @return 成功返回0，失败返回-1
 */
int initArray(DynamicArray *arr, int initialCapacity) {
    if (arr == NULL || initialCapacity <= 0) {
        return -1;
    }
    
    arr->data = (int *)malloc(initialCapacity * sizeof(int));
    if (arr->data == NULL) {
        return -1; // 内存分配失败
    }
    
    arr->size = 0;
    arr->capacity = initialCapacity;
    return 0;
}

/**
 * 扩容动态数组
 * @param arr 动态数组指针
 * @param newCapacity 新容量
 * @return 成功返回0，失败返回-1
 */
int resizeArray(DynamicArray *arr, int newCapacity) {
    if (arr == NULL || newCapacity <= arr->size) {
        return -1;
    }
    
    int *newData = (int *)realloc(arr->data, newCapacity * sizeof(int));
    if (newData == NULL) {
        return -1; // 内存重分配失败
    }
    
    arr->data = newData;
    arr->capacity = newCapacity;
    return 0;
}

/**
 * 插入元素（若容量不足则扩容）
 * @param arr 动态数组指针
 * @param index 插入位置
 * @param value 插入值
 * @return 成功返回0，失败返回-1
 */
int insertArray(DynamicArray *arr, int index, int value) {
    if (arr == NULL || index < 0 || index > arr->size) {
        return -1; // 参数无效
    }
    
    // 检查容量，不足则扩容
    if (arr->size >= arr->capacity) {
        int newCapacity = arr->capacity * 2;
        if (resizeArray(arr, newCapacity) != 0) {
            return -1; // 扩容失败
        }
    }
    
    // 移动元素
    for (int i = arr->size; i > index; i--) {
        arr->data[i] = arr->data[i-1];
    }
    
    // 插入新元素
    arr->data[index] = value;
    arr->size++;
    return 0;
}

/**
 * 删除元素
 * @param arr 动态数组指针
 * @param index 删除位置
 * @param value 输出参数，存储被删除的值
 * @return 成功返回0，失败返回-1
 */
int deleteArray(DynamicArray *arr, int index, int *value) {
    if (arr == NULL || index < 0 || index >= arr->size) {
        return -1; // 参数无效
    }
    
    // 保存被删除的值
    if (value != NULL) {
        *value = arr->data[index];
    }
    
    // 移动元素
    for (int i = index; i < arr->size - 1; i++) {
        arr->data[i] = arr->data[i+1];
    }
    
    arr->size--;
    
    // 可选：当元素个数远小于容量时，缩小容量
    if (arr->size <= arr->capacity / 4 && arr->capacity > 4) {
        int newCapacity = arr->capacity / 2;
        resizeArray(arr, newCapacity);
    }
    
    return 0;
}

/**
 * 查找元素
 * @param arr 动态数组指针
 * @param value 查找值
 * @return 找到返回索引，未找到返回-1
 */
int searchArray(DynamicArray *arr, int value) {
    if (arr == NULL) {
        return -1;
    }
    
    for (int i = 0; i < arr->size; i++) {
        if (arr->data[i] == value) {
            return i;
        }
    }
    
    return -1;
}

/**
 * 获取元素
 * @param arr 动态数组指针
 * @param index 索引
 * @param value 输出参数，存储获取的值
 * @return 成功返回0，失败返回-1
 */
int getArray(DynamicArray *arr, int index, int *value) {
    if (arr == NULL || index < 0 || index >= arr->size || value == NULL) {
        return -1;
    }
    
    *value = arr->data[index];
    return 0;
}

/**
 * 设置元素
 * @param arr 动态数组指针
 * @param index 索引
 * @param value 新值
 * @return 成功返回0，失败返回-1
 */
int setArray(DynamicArray *arr, int index, int value) {
    if (arr == NULL || index < 0 || index >= arr->size) {
        return -1;
    }
    
    arr->data[index] = value;
    return 0;
}

/**
 * 释放动态数组
 * @param arr 动态数组指针
 */
void freeArray(DynamicArray *arr) {
    if (arr != NULL) {
        free(arr->data);
        arr->data = NULL;
        arr->size = 0;
        arr->capacity = 0;
    }
}

/**
 * 打印动态数组
 * @param arr 动态数组指针
 */
void printArray(DynamicArray *arr) {
    if (arr == NULL || arr->size == 0) {
        printf("Array is empty\n");
        return;
    }
    
    printf("Array: [");
    for (int i = 0; i < arr->size; i++) {
        printf("%d", arr->data[i]);
        if (i < arr->size - 1) {
            printf(", ");
        }
    }
    printf("] (size: %d, capacity: %d)\n", arr->size, arr->capacity);
}

性能分析：

  • 时间复杂度：

    • 随机访问：( O(1) )
    • 插入/删除（中间位置）：( O(n) )
    • 插入/删除（末尾）：均摊 ( O(1) )（考虑扩容开销）
    • 查找：( O(n) )

  • 空间复杂度：

    • 存储元素：( O(n) )
    • 辅助空间：( O(1) )

  • 均摊分析：

    • 插入操作的均摊时间复杂度为 ( O(1) )，因为扩容操作虽然耗时 ( O(n) )，但每插入 ( n ) 个元素才会发生一次扩容

优化策略：

  • 扩容策略：使用翻倍扩容策略，平衡时间复杂度和空间复杂度
  • 内存管理：及时释放不再使用的内存，避免内存泄漏
  • 缓存优化：考虑数据局部性，提高缓存命中率
  • 边界检查：添加参数验证和边界检查，提高代码健壮性
  • 泛型实现：使用 void * 实现泛型动态数组，提高代码复用性

2.2 链表

  • 链表的基本概念：

    • 定义：由一系列节点组成，每个节点包含数据和指向下一个节点的指针（单链表）或同时包含指向前一个节点的指针（双链表）。
    • 优点：
      • 插入/删除操作时间复杂度 ( O(1) )（已知位置时）
      • 无需预分配内存，空间利用率高
      • 动态调整大小，适应数据量变化
    • 缺点：
      • 随机访问时间复杂度 ( O(n) )（需要遍历）
      • 额外的指针开销，空间利用率低于数组
      • 缓存局部性差，访问速度慢于数组

  • 链表的分类：

    • 单链表：每个节点包含数据和指向下一节点的指针，只能单向遍历
    • 双链表：每个节点额外包含指向前一节点的指针，支持双向遍历
    • 循环链表：尾节点指向头节点，形成环结构，适合环形队列等场景
    • 双向循环链表：结合双链表和循环链表的特点，支持双向遍历和环形操作

  • 链表的内存管理：

    • 节点分配：使用 malloc 为每个节点分配内存
    • 节点释放：使用 free 释放节点内存，避免内存泄漏
    • 内存碎片：频繁的插入和删除可能导致内存碎片
    • 内存池：使用内存池减少内存分配和释放的开销

  • 链表的性能分析：

    • 时间复杂度：
      • 插入/删除（已知位置）：( O(1) )
      • 插入/删除（未知位置）：( O(n) )（需要查找位置）
      • 查找：( O(n) )
      • 遍历：( O(n) )
    • 空间复杂度：( O(n) )（存储n个节点和n个指针）

单链表完整操作实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
// 单链表节点结构
typedef struct Node {
    int data;
    struct Node *next;
} Node;

/**
 * 创建新节点
 * @param data 节点数据
 * @return 新节点指针，失败返回NULL
 */
Node *createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

/**
 * 插入节点到链表头部
 * @param head 链表头指针的指针
 * @param data 节点数据
 * @return 成功返回0，失败返回-1
 */
int insertAtHead(Node **head, int data) {
    if (head == NULL) {
        return -1;
    }
    
    Node *newNode = createNode(data);
    if (newNode == NULL) {
        return -1;
    }
    
    newNode->next = *head;
    *head = newNode;
    return 0;
}

/**
 * 插入节点到链表尾部
 * @param head 链表头指针的指针
 * @param data 节点数据
 * @return 成功返回0，失败返回-1
 */
int insertAtTail(Node **head, int data) {
    if (head == NULL) {
        return -1;
    }
    
    Node *newNode = createNode(data);
    if (newNode == NULL) {
        return -1;
    }
    
    if (*head == NULL) {
        *head = newNode;
        return 0;
    }
    
    Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return 0;
}

/**
 * 插入节点到指定位置（索引从0开始）
 * @param head 链表头指针的指针
 * @param position 插入位置
 * @param data 节点数据
 * @return 成功返回0，失败返回-1
 */
int insertAtPosition(Node **head, int position, int data) {
    if (head == NULL || position < 0) {
        return -1;
    }
    
    if (position == 0) {
        return insertAtHead(head, data);
    }
    
    Node *current = *head;
    for (int i = 0; i < position - 1 && current != NULL; i++) {
        current = current->next;
    }
    
    if (current == NULL) {
        fprintf(stderr, "Position out of bounds\n");
        return -1;
    }
    
    Node *newNode = createNode(data);
    if (newNode == NULL) {
        return -1;
    }
    
    newNode->next = current->next;
    current->next = newNode;
    return 0;
}

/**
 * 删除链表头部节点
 * @param head 链表头指针的指针
 * @return 成功返回0，失败返回-1
 */
int deleteAtHead(Node **head) {
    if (head == NULL || *head == NULL) {
        fprintf(stderr, "List is empty\n");
        return -1;
    }
    
    Node *temp = *head;
    *head = (*head)->next;
    free(temp);
    return 0;
}

/**
 * 删除链表尾部节点
 * @param head 链表头指针的指针
 * @return 成功返回0，失败返回-1
 */
int deleteAtTail(Node **head) {
    if (head == NULL || *head == NULL) {
        fprintf(stderr, "List is empty\n");
        return -1;
    }
    
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return 0;
    }
    
    Node *current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    
    free(current->next);
    current->next = NULL;
    return 0;
}

/**
 * 删除指定位置的节点
 * @param head 链表头指针的指针
 * @param position 删除位置
 * @return 成功返回0，失败返回-1
 */
int deleteAtPosition(Node **head, int position) {
    if (head == NULL || *head == NULL || position < 0) {
        return -1;
    }
    
    if (position == 0) {
        return deleteAtHead(head);
    }
    
    Node *current = *head;
    for (int i = 0; i < position - 1 && current->next != NULL; i++) {
        current = current->next;
    }
    
    if (current->next == NULL) {
        fprintf(stderr, "Position out of bounds\n");
        return -1;
    }
    
    Node *temp = current->next;
    current->next = current->next->next;
    free(temp);
    return 0;
}

/**
 * 删除指定值的节点
 * @param head 链表头指针的指针
 * @param value 要删除的值
 * @return 成功返回0，失败返回-1
 */
int deleteByValue(Node **head, int value) {
    if (head == NULL || *head == NULL) {
        fprintf(stderr, "List is empty\n");
        return -1;
    }
    
    if ((*head)->data == value) {
        return deleteAtHead(head);
    }
    
    Node *current = *head;
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }
    
    if (current->next == NULL) {
        fprintf(stderr, "Value not found\n");
        return -1;
    }
    
    Node *temp = current->next;
    current->next = current->next->next;
    free(temp);
    return 0;
}

/**
 * 查找节点（返回索引，未找到返回-1）
 * @param head 链表头指针
 * @param value 要查找的值
 * @return 找到返回索引，未找到返回-1
 */
int searchNode(Node *head, int value) {
    int index = 0;
    Node *current = head;
    while (current != NULL) {
        if (current->data == value) {
            return index;
        }
        current = current->next;
        index++;
    }
    return -1;
}

/**
 * 获取链表长度
 * @param head 链表头指针
 * @return 链表长度
 */
int getListLength(Node *head) {
    int length = 0;
    Node *current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

/**
 * 反转链表
 * @param head 链表头指针的指针
 * @return 成功返回0，失败返回-1
 */
int reverseList(Node **head) {
    if (head == NULL) {
        return -1;
    }
    
    Node *prev = NULL;
    Node *current = *head;
    Node *next = NULL;
    
    while (current != NULL) {
        next = current->next;  // 保存下一个节点
        current->next = prev;  // 反转当前节点的指针
        prev = current;        // 移动prev指针
        current = next;        // 移动current指针
    }
    
    *head = prev;  // 更新头指针
    return 0;
}

/**
 * 检测链表是否有环
 * @param head 链表头指针
 * @return 有环返回1，无环返回0
 */
int hasCycle(Node *head) {
    if (head == NULL || head->next == NULL) {
        return 0;
    }
    
    Node *slow = head;      // 慢指针，每次移动一步
    Node *fast = head->next; // 快指针，每次移动两步
    
    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) {
            return 0;  // 快指针到达链表尾部，无环
        }
        slow = slow->next;        // 慢指针移动一步
        fast = fast->next->next;  // 快指针移动两步
    }
    
    return 1;  // 快慢指针相遇，有环
}

/**
 * 查找链表的中间节点
 * @param head 链表头指针
 * @return 中间节点指针
 */
Node *findMiddleNode(Node *head) {
    if (head == NULL) {
        return NULL;
    }
    
    Node *slow = head;  // 慢指针，每次移动一步
    Node *fast = head;  // 快指针，每次移动两步
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;        // 慢指针移动一步
        fast = fast->next->next;  // 快指针移动两步
    }
    
    return slow;  // 慢指针指向中间节点
}

/**
 * 打印链表
 * @param head 链表头指针
 */
void printList(Node *head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    Node *current = head;
    printf("List: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

/**
 * 释放链表
 * @param head 链表头指针的指针
 */
void freeList(Node **head) {
    if (head == NULL) {
        return;
    }
    
    Node *current = *head;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }
    *head = NULL;
}

双链表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
// 双链表节点结构
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

/**
 * 创建新的双链表节点
 * @param data 节点数据
 * @return 新节点指针，失败返回NULL
 */
DNode *createDNode(int data) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return NULL;
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

/**
 * 插入节点到双链表头部
 * @param head 双链表头指针的指针
 * @param data 节点数据
 * @return 成功返回0，失败返回-1
 */
int insertDNodeAtHead(DNode **head, int data) {
    if (head == NULL) {
        return -1;
    }
    
    DNode *newNode = createDNode(data);
    if (newNode == NULL) {
        return -1;
    }
    
    if (*head == NULL) {
        *head = newNode;
        return 0;
    }
    
    newNode->next = *head;
    (*head)->prev = newNode;
    *head = newNode;
    return 0;
}

/**
 * 插入节点到双链表尾部
 * @param head 双链表头指针的指针
 * @param data 节点数据
 * @return 成功返回0，失败返回-1
 */
int insertDNodeAtTail(DNode **head, int data) {
    if (head == NULL) {
        return -1;
    }
    
    DNode *newNode = createDNode(data);
    if (newNode == NULL) {
        return -1;
    }
    
    if (*head == NULL) {
        *head = newNode;
        return 0;
    }
    
    DNode *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    current->next = newNode;
    newNode->prev = current;
    return 0;
}

/**
 * 删除双链表头部节点
 * @param head 双链表头指针的指针
 * @return 成功返回0，失败返回-1
 */
int deleteDNodeAtHead(DNode **head) {
    if (head == NULL || *head == NULL) {
        fprintf(stderr, "List is empty\n");
        return -1;
    }
    
    DNode *temp = *head;
    if ((*head)->next == NULL) {
        *head = NULL;
    } else {
        *head = (*head)->next;
        (*head)->prev = NULL;
    }
    
    free(temp);
    return 0;
}

/**
 * 删除双链表尾部节点
 * @param head 双链表头指针的指针
 * @return 成功返回0，失败返回-1
 */
int deleteDNodeAtTail(DNode **head) {
    if (head == NULL || *head == NULL) {
        fprintf(stderr, "List is empty\n");
        return -1;
    }
    
    DNode *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    if (current->prev == NULL) {
        *head = NULL;
    } else {
        current->prev->next = NULL;
    }
    
    free(current);
    return 0;
}

/**
 * 打印双链表
 * @param head 双链表头指针
 */
void printDList(DNode *head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    DNode *current = head;
    printf("List: ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

/**
 * 释放双链表
 * @param head 双链表头指针的指针
 */
void freeDList(DNode **head) {
    if (head == NULL) {
        return;
    }
    
    DNode *current = *head;
    DNode *next = NULL;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    *head = NULL;
}

链表的应用场景：

  1. 动态数据结构：需要频繁插入和删除操作的场景
  2. 内存管理：如操作系统的内存分配器
  3. 缓存实现：如LRU缓存（最近最少使用）
  4. 图形算法：如邻接表表示图
  5. 文件系统：如FAT文件系统的链式结构
  6. 数据库：如B+树索引的链表结构
  7. 消息队列：如基于链表的消息队列实现

链表的优化策略：

  1. 哨兵节点：使用头哨兵和尾哨兵简化边界条件处理
  2. 双向链表：在需要频繁双向遍历的场景下使用
  3. 循环链表：在需要环形操作的场景下使用
  4. 内存池：使用内存池减少内存分配和释放的开销
  5. 排序链表：在需要保持有序的场景下使用
  6. 跳表：在需要快速查找的场景下使用，时间复杂度可优化到 ( O(og n) )

2.3 栈（Stack）

  • 栈的基本概念：

    • 定义：后进先出（LIFO, Last-In-First-Out）的数据结构，仅允许在栈顶进行插入（push）和删除（pop）操作。
    • 核心操作：
      • push：将元素压入栈顶
      • pop：从栈顶弹出元素
      • peek：查看栈顶元素而不弹出
      • isEmpty：检查栈是否为空
      • isFull：检查栈是否已满
    • 特点：
      • 操作受限，只能在栈顶进行操作
      • 时间复杂度：所有操作均为 ( O(1) )
      • 空间复杂度：( O(n) )，其中n为栈的最大容量

  • 栈的实现方式：

    • 数组栈：

      • 优点：实现简单，访问速度快，内存连续
      • 缺点：容量固定，可能溢出或浪费空间
      • 适用场景：数据量固定，需要快速访问的场景

    • 链表栈：

      • 优点：容量动态调整，无溢出风险
      • 缺点：有额外指针开销，访问速度稍慢
      • 适用场景：数据量不确定，需要动态调整容量的场景

  • 栈的应用场景：

    • 表达式求值：如中缀表达式转后缀表达式，计算后缀表达式
    • 括号匹配：检查表达式中的括号是否匹配
    • 函数调用：存储函数调用的返回地址和局部变量
    • 深度优先搜索（DFS）：遍历图或树的结构
    • 回溯算法：如迷宫求解、八皇后问题
    • 内存管理：如栈内存的分配和释放
    • 编辑器的撤销操作：存储操作历史，支持撤销功能
    • 浏览器历史记录：前进和后退功能的实现

数组栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
// 数组栈结构
typedef struct {
    int *data;   // 数据数组
    int top;     // 栈顶索引（-1表示空栈）
    int capacity;// 容量
} ArrayStack;

/**
 * 初始化栈
 * @param stack 栈指针
 * @param capacity 栈容量
 * @return 成功返回0，失败返回-1
 */
int initStack(ArrayStack *stack, int capacity) {
    if (stack == NULL || capacity <= 0) {
        return -1;
    }
    
    stack->data = (int *)malloc(capacity * sizeof(int));
    if (stack->data == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return -1;
    }
    
    stack->top = -1;
    stack->capacity = capacity;
    return 0;
}

/**
 * 判断栈是否为空
 * @param stack 栈指针
 * @return 为空返回1，不为空返回0
 */
int isEmpty(ArrayStack *stack) {
    return stack != NULL && stack->top == -1;
}

/**
 * 判断栈是否已满
 * @param stack 栈指针
 * @return 已满返回1，未满返回0
 */
int isFull(ArrayStack *stack) {
    return stack != NULL && stack->top == stack->capacity - 1;
}

/**
 * 入栈
 * @param stack 栈指针
 * @param value 要入栈的值
 * @return 成功返回0，失败返回-1
 */
int push(ArrayStack *stack, int value) {
    if (stack == NULL || isFull(stack)) {
        fprintf(stderr, "Stack overflow\n");
        return -1;
    }
    
    stack->data[++stack->top] = value;
    return 0;
}

/**
 * 出栈
 * @param stack 栈指针
 * @param value 输出参数，存储出栈的值
 * @return 成功返回0，失败返回-1
 */
int pop(ArrayStack *stack, int *value) {
    if (stack == NULL || isEmpty(stack) || value == NULL) {
        fprintf(stderr, "Stack underflow\n");
        return -1;
    }
    
    *value = stack->data[stack->top--];
    return 0;
}

/**
 * 获取栈顶元素
 * @param stack 栈指针
 * @param value 输出参数，存储栈顶的值
 * @return 成功返回0，失败返回-1
 */
int peek(ArrayStack *stack, int *value) {
    if (stack == NULL || isEmpty(stack) || value == NULL) {
        fprintf(stderr, "Stack is empty\n");
        return -1;
    }
    
    *value = stack->data[stack->top];
    return 0;
}

/**
 * 获取栈大小
 * @param stack 栈指针
 * @return 栈的大小
 */
int getStackSize(ArrayStack *stack) {
    return stack != NULL ? stack->top + 1 : 0;
}

/**
 * 扩容栈
 * @param stack 栈指针
 * @param newCapacity 新容量
 * @return 成功返回0，失败返回-1
 */
int resizeStack(ArrayStack *stack, int newCapacity) {
    if (stack == NULL || newCapacity <= stack->capacity) {
        return -1;
    }
    
    int *newData = (int *)realloc(stack->data, newCapacity * sizeof(int));
    if (newData == NULL) {
        fprintf(stderr, "Memory reallocation failed\n");
        return -1;
    }
    
    stack->data = newData;
    stack->capacity = newCapacity;
    return 0;
}

/**
 * 释放栈
 * @param stack 栈指针
 */
void freeStack(ArrayStack *stack) {
    if (stack != NULL) {
        free(stack->data);
        stack->data = NULL;
        stack->top = -1;
        stack->capacity = 0;
    }
}

/**
 * 打印栈
 * @param stack 栈指针
 */
void printStack(ArrayStack *stack) {
    if (stack == NULL || isEmpty(stack)) {
        printf("Stack is empty\n");
        return;
    }
    
    printf("Stack: [");
    for (int i = 0; i <= stack->top; i++) {
        printf("%d", stack->data[i]);
        if (i < stack->top) {
            printf(", ");
        }
    }
    printf("] (top: %d, capacity: %d)\n", stack->top, stack->capacity);
}

链表栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
// 栈节点结构
typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

// 链表栈结构
typedef struct {
    StackNode *top;  // 栈顶指针
    int size;        // 栈大小
} LinkedStack;

/**
 * 初始化链表栈
 * @param stack 栈指针
 * @return 成功返回0，失败返回-1
 */
int initLinkedStack(LinkedStack *stack) {
    if (stack == NULL) {
        return -1;
    }
    
    stack->top = NULL;
    stack->size = 0;
    return 0;
}

/**
 * 创建新的栈节点
 * @param data 节点数据
 * @return 新节点指针，失败返回NULL
 */
StackNode *createStackNode(int data) {
    StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return NULL;
    }
    
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

/**
 * 入栈
 * @param stack 栈指针
 * @param value 要入栈的值
 * @return 成功返回0，失败返回-1
 */
int pushLinkedStack(LinkedStack *stack, int value) {
    if (stack == NULL) {
        return -1;
    }
    
    StackNode *newNode = createStackNode(value);
    if (newNode == NULL) {
        return -1;
    }
    
    newNode->next = stack->top;
    stack->top = newNode;
    stack->size++;
    return 0;
}

/**
 * 出栈
 * @param stack 栈指针
 * @param value 输出参数，存储出栈的值
 * @return 成功返回0，失败返回-1
 */
int popLinkedStack(LinkedStack *stack, int *value) {
    if (stack == NULL || stack->top == NULL || value == NULL) {
        fprintf(stderr, "Stack underflow\n");
        return -1;
    }
    
    StackNode *temp = stack->top;
    *value = temp->data;
    stack->top = temp->next;
    free(temp);
    stack->size--;
    return 0;
}

/**
 * 获取栈顶元素
 * @param stack 栈指针
 * @param value 输出参数，存储栈顶的值
 * @return 成功返回0，失败返回-1
 */
int peekLinkedStack(LinkedStack *stack, int *value) {
    if (stack == NULL || stack->top == NULL || value == NULL) {
        fprintf(stderr, "Stack is empty\n");
        return -1;
    }
    
    *value = stack->top->data;
    return 0;
}

/**
 * 判断链表栈是否为空
 * @param stack 栈指针
 * @return 为空返回1，不为空返回0
 */
int isEmptyLinkedStack(LinkedStack *stack) {
    return stack != NULL && stack->top == NULL;
}

/**
 * 获取链表栈大小
 * @param stack 栈指针
 * @return 栈的大小
 */
int getLinkedStackSize(LinkedStack *stack) {
    return stack != NULL ? stack->size : 0;
}

/**
 * 释放链表栈
 * @param stack 栈指针
 */
void freeLinkedStack(LinkedStack *stack) {
    if (stack != NULL) {
        StackNode *current = stack->top;
        while (current != NULL) {
            StackNode *temp = current;
            current = current->next;
            free(temp);
        }
        stack->top = NULL;
        stack->size = 0;
    }
}

/**
 * 打印链表栈
 * @param stack 栈指针
 */
void printLinkedStack(LinkedStack *stack) {
    if (stack == NULL || isEmptyLinkedStack(stack)) {
        printf("Stack is empty\n");
        return;
    }
    
    printf("Stack: [");
    StackNode *current = stack->top;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) {
            printf(", ");
        }
        current = current->next;
    }
    printf("] (size: %d)\n", stack->size);
}

栈的应用：表达式求值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
/**
 * 检查字符是否为运算符
 * @param ch 字符
 * @return 是运算符返回1，否则返回0
 */
int isOperator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

/**
 * 获取运算符优先级
 * @param op 运算符
 * @return 优先级值
 */
int getPriority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}

/**
 * 计算两个数的运算结果
 * @param a 第一个数
 * @param b 第二个数
 * @param op 运算符
 * @return 运算结果
 */
int calculate(int a, int b, char op) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
        case '/':
            return a / b;
        default:
            return 0;
    }
}

/**
 * 计算后缀表达式
 * @param expr 后缀表达式字符串
 * @return 计算结果
 */
int evaluatePostfix(char *expr) {
    ArrayStack stack;
    initStack(&stack, 100);
    
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        
        if (isdigit(ch)) {
            // 处理多位数
            int num = 0;
            while (isdigit(expr[i])) {
                num = num * 10 + (expr[i] - '0');
                i++;
            }
            i--;
            push(&stack, num);
        } else if (isOperator(ch)) {
            int b, a;
            pop(&stack, &b);
            pop(&stack, &a);
            int result = calculate(a, b, ch);
            push(&stack, result);
        }
    }
    
    int result;
    pop(&stack, &result);
    freeStack(&stack);
    return result;
}

/**
 * 中缀表达式转后缀表达式
 * @param infix 中缀表达式字符串
 * @param postfix 输出参数，存储后缀表达式
 */
void infixToPostfix(char *infix, char *postfix) {
    ArrayStack stack;
    initStack(&stack, 100);
    int j = 0;
    
    for (int i = 0; infix[i] != '\0'; i++) {
        char ch = infix[i];
        
        if (isdigit(ch)) {
            // 处理操作数
            while (isdigit(infix[i])) {
                postfix[j++] = infix[i++];
            }
            postfix[j++] = ' ';
            i--;
        } else if (ch == '(') {
            // 左括号直接入栈
            push(&stack, ch);
        } else if (ch == ')') {
            // 右括号，弹出栈中元素直到遇到左括号
            int op;
            while (!isEmpty(&stack) && peek(&stack, &op) == 0 && op != '(') {
                pop(&stack, &op);
                postfix[j++] = (char)op;
                postfix[j++] = ' ';
            }
            pop(&stack, &op); // 弹出左括号
        } else if (isOperator(ch)) {
            // 运算符，弹出栈中优先级大于等于当前运算符的元素
            int op;
            while (!isEmpty(&stack) && peek(&stack, &op) == 0 && getPriority((char)op) >= getPriority(ch)) {
                pop(&stack, &op);
                postfix[j++] = (char)op;
                postfix[j++] = ' ';
            }
            push(&stack, ch);
        }
    }
    
    // 弹出栈中剩余的运算符
    int op;
    while (!isEmpty(&stack) && peek(&stack, &op) == 0) {
        pop(&stack, &op);
        postfix[j++] = (char)op;
        postfix[j++] = ' ';
    }
    
    postfix[j] = '\0';
    freeStack(&stack);
}

栈的性能分析：

  • 数组栈：

    • 时间复杂度：
      • push：( O(1) )
      • pop：( O(1) )
      • peek：( O(1) )
      • isEmpty：( O(1) )
      • isFull：( O(1) )
    • 空间复杂度：( O(n) )，其中n为栈的最大容量

  • 链表栈：

    • 时间复杂度：
      • push：( O(1) )
      • pop：( O(1) )
      • peek：( O(1) )
      • isEmpty：( O(1) )
    • 空间复杂度：( O(n) )，其中n为栈中元素的个数

栈的优化策略：

  1. 动态扩容：对于数组栈，当容量不足时自动扩容
  2. 内存池：对于链表栈，使用内存池减少内存分配和释放的开销
  3. 泛型实现：使用 void * 实现泛型栈，提高代码复用性
  4. 线程安全：在多线程环境下，添加互斥锁保证栈的线程安全
  5. 边界检查：添加参数验证和边界检查，提高代码健壮性
  6. 缓存优化：对于数组栈，考虑数据局部性，提高缓存命中率
  7. 预分配策略：根据预期的栈大小，合理设置初始容量

2.4 队列（Queue）

  • 队列的基本概念：

    • 定义：先进先出（FIFO, First-In-First-Out）的数据结构，允许在队尾插入（enqueue），在队头删除（dequeue）。
    • 核心操作：
      • enqueue：将元素插入队尾
      • dequeue：从队头移除元素
      • peek：查看队头元素而不移除
      • isEmpty：检查队列是否为空
      • isFull：检查队列是否已满
    • 特点：
      • 操作受限，只能在队尾插入，队头删除
      • 时间复杂度：所有操作均为 ( O(1) )
      • 空间复杂度：( O(n) )，其中n为队列的最大容量

  • 队列的实现方式：

    • 数组队列：

      • 普通数组队列：简单但存在”假溢出”问题
      • 循环数组队列：通过取模运算实现循环，避免”假溢出”问题
      • 优点：实现简单，访问速度快，内存连续
      • 缺点：容量固定，可能溢出或浪费空间
      • 适用场景：数据量固定，需要快速访问的场景

    • 链表队列：

      • 单链表队列：使用头指针和尾指针管理
      • 双链表队列：支持双向操作，但通常不必要
      • 优点：容量动态调整，无溢出风险
      • 缺点：有额外指针开销，访问速度稍慢
      • 适用场景：数据量不确定，需要动态调整容量的场景

  • 队列的应用场景：

    • 广度优先搜索（BFS）：遍历图或树的结构
    • 任务调度：如操作系统的进程调度、线程池任务调度
    • 缓冲区管理：如网络数据传输、磁盘I/O操作
    • 打印机队列：管理打印任务的顺序
    • 消息队列：在分布式系统中传递消息
    • 事件处理：如GUI事件处理、游戏事件系统
    • 请求排队：如Web服务器处理客户端请求

循环队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
// 循环队列结构
typedef struct {
    int *data;   // 数据数组
    int front;   // 队头索引
    int rear;    // 队尾索引（下一个插入位置）
    int capacity;// 容量
    int size;    // 当前元素个数
} CircularQueue;

/**
 * 初始化循环队列
 * @param queue 队列指针
 * @param capacity 队列容量
 * @return 成功返回0，失败返回-1
 */
int initQueue(CircularQueue *queue, int capacity) {
    if (queue == NULL || capacity <= 0) {
        return -1;
    }
    
    queue->data = (int *)malloc(capacity * sizeof(int));
    if (queue->data == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return -1;
    }
    
    queue->front = 0;
    queue->rear = 0;
    queue->capacity = capacity;
    queue->size = 0;
    return 0;
}

/**
 * 判断队列是否为空
 * @param queue 队列指针
 * @return 为空返回1，不为空返回0
 */
int isQueueEmpty(CircularQueue *queue) {
    return queue != NULL && queue->size == 0;
}

/**
 * 判断队列是否已满
 * @param queue 队列指针
 * @return 已满返回1，未满返回0
 */
int isQueueFull(CircularQueue *queue) {
    return queue != NULL && queue->size == queue->capacity;
}

/**
 * 入队
 * @param queue 队列指针
 * @param value 要入队的值
 * @return 成功返回0，失败返回-1
 */
int enqueue(CircularQueue *queue, int value) {
    if (queue == NULL || isQueueFull(queue)) {
        fprintf(stderr, "Queue overflow\n");
        return -1;
    }
    
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->size++;
    return 0;
}

/**
 * 出队
 * @param queue 队列指针
 * @param value 输出参数，存储出队的值
 * @return 成功返回0，失败返回-1
 */
int dequeue(CircularQueue *queue, int *value) {
    if (queue == NULL || isQueueEmpty(queue) || value == NULL) {
        fprintf(stderr, "Queue underflow\n");
        return -1;
    }
    
    *value = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    return 0;
}

/**
 * 获取队头元素
 * @param queue 队列指针
 * @param value 输出参数，存储队头的值
 * @return 成功返回0，失败返回-1
 */
int peekQueue(CircularQueue *queue, int *value) {
    if (queue == NULL || isQueueEmpty(queue) || value == NULL) {
        fprintf(stderr, "Queue is empty\n");
        return -1;
    }
    
    *value = queue->data[queue->front];
    return 0;
}

/**
 * 获取队列大小
 * @param queue 队列指针
 * @return 队列大小
 */
int getQueueSize(CircularQueue *queue) {
    return queue != NULL ? queue->size : 0;
}

/**
 * 扩容队列
 * @param queue 队列指针
 * @param newCapacity 新容量
 * @return 成功返回0，失败返回-1
 */
int resizeQueue(CircularQueue *queue, int newCapacity) {
    if (queue == NULL || newCapacity <= queue->capacity) {
        return -1;
    }
    
    int *newData = (int *)malloc(newCapacity * sizeof(int));
    if (newData == NULL) {
        fprintf(stderr, "Memory reallocation failed\n");
        return -1;
    }
    
    // 复制现有元素
    int count = 0;
    int i = queue->front;
    while (count < queue->size) {
        newData[count++] = queue->data[i];
        i = (i + 1) % queue->capacity;
    }
    
    free(queue->data);
    queue->data = newData;
    queue->front = 0;
    queue->rear = queue->size;
    queue->capacity = newCapacity;
    return 0;
}

/**
 * 释放队列
 * @param queue 队列指针
 */
void freeQueue(CircularQueue *queue) {
    if (queue != NULL) {
        free(queue->data);
        queue->data = NULL;
        queue->front = 0;
        queue->rear = 0;
        queue->capacity = 0;
        queue->size = 0;
    }
}

/**
 * 打印队列
 * @param queue 队列指针
 */
void printQueue(CircularQueue *queue) {
    if (queue == NULL || isQueueEmpty(queue)) {
        printf("Queue is empty\n");
        return;
    }
    
    printf("Queue: [");
    int i = queue->front;
    int count = 0;
    while (count < queue->size) {
        printf("%d", queue->data[i]);
        if (count < queue->size - 1) {
            printf(", ");
        }
        i = (i + 1) % queue->capacity;
        count++;
    }
    printf("] (front: %d, rear: %d, size: %d, capacity: %d)\n", 
            queue->front, queue->rear, queue->size, queue->capacity);
}

链表队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
// 队列节点结构
typedef struct QueueNode {
    int data;
    struct QueueNode *next;
} QueueNode;

// 链表队列结构
typedef struct {
    QueueNode *front;  // 队头指针
    QueueNode *rear;   // 队尾指针
    int size;          // 队列大小
} LinkedQueue;

/**
 * 初始化链表队列
 * @param queue 队列指针
 * @return 成功返回0，失败返回-1
 */
int initLinkedQueue(LinkedQueue *queue) {
    if (queue == NULL) {
        return -1;
    }
    
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    return 0;
}

/**
 * 创建新的队列节点
 * @param data 节点数据
 * @return 新节点指针，失败返回NULL
 */
QueueNode *createQueueNode(int data) {
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return NULL;
    }
    
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

/**
 * 入队
 * @param queue 队列指针
 * @param value 要入队的值
 * @return 成功返回0，失败返回-1
 */
int enqueueLinked(LinkedQueue *queue, int value) {
    if (queue == NULL) {
        return -1;
    }
    
    QueueNode *newNode = createQueueNode(value);
    if (newNode == NULL) {
        return -1;
    }
    
    if (queue->rear == NULL) {
        // 队列为空
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        // 队列不为空
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    
    queue->size++;
    return 0;
}

/**
 * 出队
 * @param queue 队列指针
 * @param value 输出参数，存储出队的值
 * @return 成功返回0，失败返回-1
 */
int dequeueLinked(LinkedQueue *queue, int *value) {
    if (queue == NULL || queue->front == NULL || value == NULL) {
        fprintf(stderr, "Queue underflow\n");
        return -1;
    }
    
    QueueNode *temp = queue->front;
    *value = temp->data;
    
    if (queue->front == queue->rear) {
        // 队列只有一个元素
        queue->front = NULL;
        queue->rear = NULL;
    } else {
        // 队列有多个元素
        queue->front = queue->front->next;
    }
    
    free(temp);
    queue->size--;
    return 0;
}

/**
 * 获取队头元素
 * @param queue 队列指针
 * @param value 输出参数，存储队头的值
 * @return 成功返回0，失败返回-1
 */
int peekLinkedQueue(LinkedQueue *queue, int *value) {
    if (queue == NULL || queue->front == NULL || value == NULL) {
        fprintf(stderr, "Queue is empty\n");
        return -1;
    }
    
    *value = queue->front->data;
    return 0;
}

/**
 * 判断链表队列是否为空
 * @param queue 队列指针
 * @return 为空返回1，不为空返回0
 */
int isEmptyLinkedQueue(LinkedQueue *queue) {
    return queue != NULL && queue->size == 0;
}

/**
 * 获取链表队列大小
 * @param queue 队列指针
 * @return 队列大小
 */
int getLinkedQueueSize(LinkedQueue *queue) {
    return queue != NULL ? queue->size : 0;
}

/**
 * 释放链表队列
 * @param queue 队列指针
 */
void freeLinkedQueue(LinkedQueue *queue) {
    if (queue != NULL) {
        QueueNode *current = queue->front;
        while (current != NULL) {
            QueueNode *temp = current;
            current = current->next;
            free(temp);
        }
        queue->front = NULL;
        queue->rear = NULL;
        queue->size = 0;
    }
}

/**
 * 打印链表队列
 * @param queue 队列指针
 */
void printLinkedQueue(LinkedQueue *queue) {
    if (queue == NULL || isEmptyLinkedQueue(queue)) {
        printf("Queue is empty\n");
        return;
    }
    
    printf("Queue: [");
    QueueNode *current = queue->front;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) {
            printf(", ");
        }
        current = current->next;
    }
    printf("] (size: %d)\n", queue->size);
}

队列的应用：广度优先搜索（BFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// 假设我们有一个图的邻接表表示
typedef struct Graph {
    int vertices;
    int **adjMatrix; // 邻接矩阵
} Graph;

/**
 * 初始化图
 * @param graph 图指针
 * @param vertices 顶点数
 * @return 成功返回0，失败返回-1
 */
int initGraph(Graph *graph, int vertices) {
    if (graph == NULL || vertices <= 0) {
        return -1;
    }
    
    graph->vertices = vertices;
    graph->adjMatrix = (int **)malloc(vertices * sizeof(int *));
    if (graph->adjMatrix == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return -1;
    }
    
    for (int i = 0; i < vertices; i++) {
        graph->adjMatrix[i] = (int *)calloc(vertices, sizeof(int));
        if (graph->adjMatrix[i] == NULL) {
            fprintf(stderr, "Memory allocation failed\n");
            return -1;
        }
    }
    
    return 0;
}

/**
 * 添加边
 * @param graph 图指针
 * @param src 源顶点
 * @param dest 目标顶点
 * @param weight 边的权重
 * @return 成功返回0，失败返回-1
 */
int addEdge(Graph *graph, int src, int dest, int weight) {
    if (graph == NULL || src < 0 || src >= graph->vertices || dest < 0 || dest >= graph->vertices) {
        return -1;
    }
    
    graph->adjMatrix[src][dest] = weight;
    graph->adjMatrix[dest][src] = weight; // 无向图
    return 0;
}

/**
 * 广度优先搜索
 * @param graph 图指针
 * @param start 起始顶点
 */
void bfs(Graph *graph, int start) {
    if (graph == NULL || start < 0 || start >= graph->vertices) {
        return;
    }
    
    // 标记顶点是否被访问
    int *visited = (int *)calloc(graph->vertices, sizeof(int));
    if (visited == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        return;
    }
    
    // 初始化队列
    LinkedQueue queue;
    initLinkedQueue(&queue);
    
    // 标记起始顶点为已访问并入队
    visited[start] = 1;
    enqueueLinked(&queue, start);
    
    printf("BFS traversal starting from vertex %d: ", start);
    
    while (!isEmptyLinkedQueue(&queue)) {
        int vertex;
        dequeueLinked(&queue, &vertex);
        printf("%d ", vertex);
        
        // 遍历所有相邻顶点
        for (int i = 0; i < graph->vertices; i++) {
            if (graph->adjMatrix[vertex][i] != 0 && !visited[i]) {
                visited[i] = 1;
                enqueueLinked(&queue, i);
            }
        }
    }
    
    printf("\n");
    
    // 释放资源
    free(visited);
    freeLinkedQueue(&queue);
}

队列的性能分析：

  • 循环队列：

    • 时间复杂度：
      • enqueue：( O(1) )
      • dequeue：( O(1) )
      • peek：( O(1) )
      • isEmpty：( O(1) )
      • isFull：( O(1) )
    • 空间复杂度：( O(n) )，其中n为队列的最大容量

  • 链表队列：

    • 时间复杂度：
      • enqueue：( O(1) )
      • dequeue：( O(1) )
      • peek：( O(1) )
      • isEmpty：( O(1) )
    • 空间复杂度：( O(n) )，其中n为队列中元素的个数

队列的优化策略：

  1. 动态扩容：对于循环队列，当容量不足时自动扩容
  2. 内存池：对于链表队列，使用内存池减少内存分配和释放的开销
  3. 泛型实现：使用 void * 实现泛型队列，提高代码复用性
  4. 线程安全：在多线程环境下，添加互斥锁保证队列的线程安全
  5. 边界检查：添加参数验证和边界检查，提高代码健壮性
  6. 缓存优化：对于循环队列，考虑数据局部性，提高缓存命中率
  7. 批量操作：支持批量入队和批量出队操作，减少函数调用开销
  8. 优先级队列：在需要优先级的场景下，实现优先级队列（如使用堆）

3. 树结构

3.1 二叉树

  • 定义：每个节点最多有两个子节点（左子树和右子树）的树结构。
  • 遍历方式：
    • 前序遍历：根 → 左 → 右
    • 中序遍历：左 → 根 → 右
    • 后序遍历：左 → 右 → 根
    • 层序遍历：按层从左到右访问（使用队列实现）

二叉树遍历实现（递归与非递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
// 二叉树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode *createTreeNode(int data) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 前序遍历（递归）
void preorderTraversal(TreeNode *root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// 前序遍历（非递归，使用栈）
void preorderTraversalIterative(TreeNode *root) {
    if (root == NULL) return;
    ArrayStack stack;
    initStack(&stack, 100); // 假设最大深度为100
    push(&stack, (int)root); // 注意：这里将指针转换为int存储，实际应用中需使用指针栈
    while (!isEmpty(&stack)) {
        TreeNode *node = (TreeNode *)pop(&stack);
        printf("%d ", node->data);
        // 先压右子树，再压左子树（栈后进先出）
        if (node->right != NULL) {
            push(&stack, (int)node->right);
        }
        if (node->left != NULL) {
            push(&stack, (int)node->left);
        }
    }
    freeStack(&stack);
}

// 中序遍历（递归）
void inorderTraversal(TreeNode *root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// 中序遍历（非递归，使用栈）
void inorderTraversalIterative(TreeNode *root) {
    if (root == NULL) return;
    ArrayStack stack;
    initStack(&stack, 100);
    TreeNode *current = root;
    while (current != NULL || !isEmpty(&stack)) {
        // 遍历左子树到底
        while (current != NULL) {
            push(&stack, (int)current);
            current = current->left;
        }
        // 访问根节点
        current = (TreeNode *)pop(&stack);
        printf("%d ", current->data);
        // 遍历右子树
        current = current->right;
    }
    freeStack(&stack);
}

// 后序遍历（递归）
void postorderTraversal(TreeNode *root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%d ", root->data);
    }
}

// 后序遍历（非递归，使用栈）
void postorderTraversalIterative(TreeNode *root) {
    if (root == NULL) return;
    ArrayStack stack1, stack2;
    initStack(&stack1, 100);
    initStack(&stack2, 100);
    push(&stack1, (int)root);
    while (!isEmpty(&stack1)) {
        TreeNode *node = (TreeNode *)pop(&stack1);
        push(&stack2, (int)node);
        // 先压左子树，再压右子树（栈1弹出顺序为根→右→左，栈2压入顺序为根→右→左，弹出顺序为左→右→根）
        if (node->left != NULL) {
            push(&stack1, (int)node->left);
        }
        if (node->right != NULL) {
            push(&stack1, (int)node->right);
        }
    }
    while (!isEmpty(&stack2)) {
        TreeNode *node = (TreeNode *)pop(&stack2);
        printf("%d ", node->data);
    }
    freeStack(&stack1);
    freeStack(&stack2);
}

// 层序遍历（使用队列）
void levelOrderTraversal(TreeNode *root) {
    if (root == NULL) return;
    CircularQueue queue;
    initQueue(&queue, 100);
    enqueue(&queue, (int)root); // 注意：指针转换
    while (!isQueueEmpty(&queue)) {
        TreeNode *node = (TreeNode *)dequeue(&queue);
        printf("%d ", node->data);
        if (node->left != NULL) {
            enqueue(&queue, (int)node->left);
        }
        if (node->right != NULL) {
            enqueue(&queue, (int)node->right);
        }
    }
    freeQueue(&queue);
}

3.2 二叉搜索树（BST）

  • 性质：左子树所有节点值小于根节点，右子树所有节点值大于根节点（无重复值）。
  • 操作：
    • 查找：从根节点开始，根据值大小向左/右子树递归查找，时间复杂度 ( O(h) )（( h ) 为树高）。
    • 插入：从根节点开始，根据值大小找到插入位置（叶子节点），时间复杂度 ( O(h) )。
    • 删除：分三种情况：
      1. 叶子节点：直接删除。
      2. 仅有一个子节点：用子节点替换该节点。
      3. 有两个子节点：用右子树最小节点（或左子树最大节点）替换该节点，再删除替换节点。

二叉搜索树实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// 查找节点
TreeNode *searchBST(TreeNode *root, int value) {
    if (root == NULL || root->data == value) {
        return root;
    }
    if (value < root->data) {
        return searchBST(root->left, value);
    } else {
        return searchBST(root->right, value);
    }
}

// 插入节点
TreeNode *insertBST(TreeNode *root, int value) {
    if (root == NULL) {
        return createTreeNode(value);
    }
    if (value < root->data) {
        root->left = insertBST(root->left, value);
    } else if (value > root->data) {
        root->right = insertBST(root->right, value);
    }
    // 忽略重复值
    return root;
}

// 查找最小节点（右子树最小节点用于删除操作）
TreeNode *findMin(TreeNode *root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// 删除节点
TreeNode *deleteBST(TreeNode *root, int value) {
    if (root == NULL) {
        return root;
    }
    // 查找节点
    if (value < root->data) {
        root->left = deleteBST(root->left, value);
    } else if (value > root->data) {
        root->right = deleteBST(root->right, value);
    } else {
        // 情况1：叶子节点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        // 情况2：仅有一个子节点
        else if (root->left == NULL) {
            TreeNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        // 情况3：有两个子节点
        TreeNode *temp = findMin(root->right); // 找右子树最小节点
        root->data = temp->data;              // 替换值
        root->right = deleteBST(root->right, temp->data); // 删除替换节点
    }
    return root;
}

3.3 AVL树（平衡二叉搜索树）

  • 定义：左右子树高度差（平衡因子）的绝对值不超过1的二叉搜索树。
  • 平衡因子：左子树高度 - 右子树高度（范围：-1, 0, 1）。
  • 平衡调整：通过旋转操作维持平衡，共四种情况：
    1. LL型：左子树的左子树插入节点导致不平衡 → 右旋。
    2. RR型：右子树的右子树插入节点导致不平衡 → 左旋。
    3. LR型：左子树的右子树插入节点导致不平衡 → 先左旋左子树，再右旋根节点。
    4. RL型：右子树的左子树插入节点导致不平衡 → 先右旋右子树，再左旋根节点。

AVL树旋转操作实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// 计算树高
int height(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

// 计算平衡因子
int getBalanceFactor(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    return height(root->left) - height(root->right);
}

// 右旋操作（LL型调整）
TreeNode *rightRotate(TreeNode *y) {
    TreeNode *x = y->left;
    TreeNode *T2 = x->right;
    // 执行旋转
    x->right = y;
    y->left = T2;
    // 更新高度（实际应用中应存储高度以避免重复计算）
    height(y);
    height(x);
    return x; // 新的根节点
}

// 左旋操作（RR型调整）
TreeNode *leftRotate(TreeNode *x) {
    TreeNode *y = x->right;
    TreeNode *T2 = y->left;
    // 执行旋转
    y->left = x;
    x->right = T2;
    // 更新高度
    height(x);
    height(y);
    return y; // 新的根节点
}

// AVL树插入（自动平衡）
TreeNode *insertAVL(TreeNode *root, int value) {
    // 1. 执行标准BST插入
    if (root == NULL) {
        return createTreeNode(value);
    }
    if (value < root->data) {
        root->left = insertAVL(root->left, value);
    } else if (value > root->data) {
        root->right = insertAVL(root->right, value);
    } else {
        return root; // 忽略重复值
    }
    // 2. 计算平衡因子
    int balance = getBalanceFactor(root);
    // 3. 根据平衡因子调整
    // LL型：右旋
    if (balance > 1 && value < root->left->data) {
        return rightRotate(root);
    }
    // RR型：左旋
    if (balance < -1 && value > root->right->data) {
        return leftRotate(root);
    }
    // LR型：先左旋左子树，再右旋根节点
    if (balance > 1 && value > root->left->data) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }
    // RL型：先右旋右子树，再左旋根节点
    if (balance < -1 && value < root->right->data) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

3.4 堆（Heap）

  • 定义：完全二叉树，满足父节点值大于等于（大顶堆）或小于等于（小顶堆）子节点值。
  • 操作：
    • 插入：将新元素插入到堆末尾，然后上浮调整（与父节点比较交换，直到满足堆性质）。
    • 删除堆顶：将堆末尾元素移到堆顶，然后下沉调整（与子节点比较交换，直到满足堆性质）。
    • 构建堆：从最后一个非叶子节点开始，依次下沉调整。
  • 应用：堆排序、优先队列、图算法（Dijkstra最短路径）。

大顶堆实现与堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// 下沉调整（大顶堆）
void heapify(int arr[], int n, int i) {
    int largest = i;      // 初始化largest为根
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2;// 右子节点
    // 如果左子节点大于根
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点大于当前largest
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果largest不是根
    if (largest != i) {
        // 交换
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

// 构建大顶堆
void buildHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始，依次下沉调整
    int lastNonLeaf = (n / 2) - 1;
    for (int i = lastNonLeaf; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

// 堆排序（升序）
void heapSort(int arr[], int n) {
    // 1. 构建大顶堆
    buildHeap(arr, n);
    // 2. 依次取出堆顶元素（最大值）
    for (int i = n - 1; i > 0; i--) {
        // 交换堆顶（最大值）与堆末尾元素
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        // 对剩余堆进行下沉调整
        heapify(arr, i, 0);
    }
}

4. 图结构

4.1 图的表示

  • 邻接矩阵：二维数组 adj[i][j] 表示顶点 ( i ) 到顶点 ( j ) 的边（有权值则存储权值，否则存储0/1）。适合稠密图，空间复杂度 ( O(V^2) )，时间复杂度 ( O(1) ) 访问边。
  • 邻接表：数组 adj，其中 adj[i] 是顶点 ( i ) 的邻接顶点链表。适合稀疏图，空间复杂度 ( O(V+E) )，时间复杂度 ( O(1) ) 访问邻接顶点。

邻接表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 邻接表节点结构
typedef struct AdjNode {
    int dest;     // 目标顶点
    int weight;   // 边权（无向图或无权图可省略）
    struct AdjNode *next;
} AdjNode;

// 邻接表结构
typedef struct Graph {
    int V;        // 顶点数
    AdjNode **adj;// 邻接表数组
} Graph;

// 创建邻接表节点
AdjNode *createAdjNode(int dest, int weight) {
    AdjNode *newNode = (AdjNode *)malloc(sizeof(AdjNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph *createGraph(int V) {
    Graph *graph = (Graph *)malloc(sizeof(Graph));
    graph->V = V;
    graph->adj = (AdjNode **)malloc(V * sizeof(AdjNode *));
    for (int i = 0; i < V; i++) {
        graph->adj[i] = NULL;
    }
    return graph;
}

// 添加边（有向图）
void addEdge(Graph *graph, int src, int dest, int weight) {
    // 添加 src → dest 的边
    AdjNode *newNode = createAdjNode(dest, weight);
    newNode->next = graph->adj[src];
    graph->adj[src] = newNode;
}

// 添加边（无向图，双向添加）
void addUndirectedEdge(Graph *graph, int src, int dest, int weight) {
    addEdge(graph, src, dest, weight);
    addEdge(graph, dest, src, weight);
}

// 打印图
void printGraph(Graph *graph) {
    for (int i = 0; i < graph->V; i++) {
        AdjNode *temp = graph->adj[i];
        printf("Vertex %d: ", i);
        while (temp != NULL) {
            printf("-> (%d, %d) ", temp->dest, temp->weight);
            temp = temp->next;
        }
        printf("\n");
    }
}

// 释放图
void freeGraph(Graph *graph) {
    for (int i = 0; i < graph->V; i++) {
        AdjNode *temp = graph->adj[i];
        while (temp != NULL) {
            AdjNode *prev = temp;
            temp = temp->next;
            free(prev);
        }
    }
    free(graph->adj);
    free(graph);
}

4.2 图的遍历

  • 深度优先搜索（DFS）：从起点出发，递归访问所有可达顶点，标记已访问，避免重复。
  • 广度优先搜索（BFS）：从起点出发，按层访问所有可达顶点，使用队列实现。

DFS与BFS实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// DFS递归实现
void DFS(Graph *graph, int start, int visited[]) {
    // 标记当前顶点为已访问
    visited[start] = 1;
    printf("%d ", start);
    // 递归访问所有邻接顶点
    AdjNode *temp = graph->adj[start];
    while (temp != NULL) {
        int dest = temp->dest;
        if (!visited[dest]) {
            DFS(graph, dest, visited);
        }
        temp = temp->next;
    }
}

// BFS实现（使用队列）
void BFS(Graph *graph, int start) {
    // 初始化访问标记数组
    int *visited = (int *)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }
    // 初始化队列
    CircularQueue queue;
    initQueue(&queue, graph->V);
    // 标记起点为已访问并入队
    visited[start] = 1;
    enqueue(&queue, start);
    while (!isQueueEmpty(&queue)) {
        // 出队并访问
        int current = dequeue(&queue);
        printf("%d ", current);
        // 入队所有未访问的邻接顶点
        AdjNode *temp = graph->adj[current];
        while (temp != NULL) {
            int dest = temp->dest;
            if (!visited[dest]) {
                visited[dest] = 1;
                enqueue(&queue, dest);
            }
            temp = temp->next;
        }
    }
    free(visited);
    freeQueue(&queue);
}

4.3 最短路径算法

  • Dijkstra算法：单源最短路径算法，适用于边权为正的图。使用优先队列优化，时间复杂度 ( O(E \log V) )。
  • Floyd-Warshall算法：多源最短路径算法，使用动态规划实现，时间复杂度 ( O(V^3) )，适用于小图。

Dijkstra算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Dijkstra算法（邻接表实现，使用优先队列）
void dijkstra(Graph *graph, int start) {
    // 距离数组（初始化为无穷大）
    int *dist = (int *)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        dist[i] = INT_MAX;
    }
    dist[start] = 0; // 起点距离为0
    // 优先队列（存储顶点及其距离，按距离排序）
    // 注：实际应用中应使用最小堆，这里简化处理
    int *visited = (int *)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; i++) {
        visited[i] = 0;
    }
    for (int count = 0; count < graph->V - 1; count++) {
        // 选择距离最小的未访问顶点
        int minDist = INT_MAX, u;
        for (int v = 0; v < graph->V; v++) {
            if (!visited[v] && dist[v] <= minDist) {
                minDist = dist[v];
                u = v;
            }
        }
        // 标记为已访问
        visited[u] = 1;
        // 更新邻接顶点的距离
        AdjNode *temp = graph->adj[u];
        while (temp != NULL) {
            int v = temp->dest;
            int weight = temp->weight;
            if (!visited[v] && dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
            temp = temp->next;
        }
    }
    // 打印最短路径
    printf("Vertex\tDistance from Source\n");
    for (int i = 0; i < graph->V; i++) {
        printf("%d\t%d\n", i, dist[i]);
    }
    free(dist);
    free(visited);
}

4.4 最小生成树（MST）

  • Prim算法：从单个顶点开始，逐步添加连接树与非树顶点的最小边，时间复杂度 ( O(E \log V) )。
  • Kruskal算法：按边权排序，依次添加边，使用并查集避免环，时间复杂度 ( O(E \log E) )。

Kruskal算法实现（使用并查集）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
// 边结构
typedef struct Edge {
    int src;    // 源顶点
    int dest;   // 目标顶点
    int weight; // 边权
} Edge;

// 并查集结构
typedef struct UnionFind {
    int *parent;
    int *rank;
} UnionFind;

// 初始化并查集
UnionFind *initUnionFind(int V) {
    UnionFind *uf = (UnionFind *)malloc(sizeof(UnionFind));
    uf->parent = (int *)malloc(V * sizeof(int));
    uf->rank = (int *)malloc(V * sizeof(int));
    for (int i = 0; i < V; i++) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
    }
    return uf;
}

// 查找根节点（路径压缩）
int find(UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

// 合并两个集合（按秩合并）
void unionSets(UnionFind *uf, int x, int y) {
    int xRoot = find(uf, x);
    int yRoot = find(uf, y);
    if (xRoot == yRoot) return;
    // 秩小的树合并到秩大的树
    if (uf->rank[xRoot] < uf->rank[yRoot]) {
        uf->parent[xRoot] = yRoot;
    } else if (uf->rank[xRoot] > uf->rank[yRoot]) {
        uf->parent[yRoot] = xRoot;
    } else {
        uf->parent[yRoot] = xRoot;
        uf->rank[xRoot]++;
    }
}

// 比较边权（用于排序）
int compareEdges(const void *a, const void *b) {
    Edge *edgeA = (Edge *)a;
    Edge *edgeB = (Edge *)b;
    return edgeA->weight - edgeB->weight;
}

// Kruskal算法
void kruskalMST(Graph *graph) {
    int V = graph->V;
    // 收集所有边
    int E = 0;
    for (int i = 0; i < V; i++) {
        AdjNode *temp = graph->adj[i];
        while (temp != NULL) {
            E++;
            temp = temp->next;
        }
    }
    Edge *edges = (Edge *)malloc(E * sizeof(Edge));
    int edgeIndex = 0;
    for (int i = 0; i < V; i++) {
        AdjNode *temp = graph->adj[i];
        while (temp != NULL) {
            edges[edgeIndex].src = i;
            edges[edgeIndex].dest = temp->dest;
            edges[edgeIndex].weight = temp->weight;
            edgeIndex++;
            temp = temp->next;
        }
    }
    // 按边权排序
    qsort(edges, E, sizeof(Edge), compareEdges);
    // 初始化MST
    Edge *mst = (Edge *)malloc((V - 1) * sizeof(Edge));
    int mstIndex = 0;
    // 初始化并查集
    UnionFind *uf = initUnionFind(V);
    // 依次添加边
    for (int i = 0; i < E && mstIndex < V - 1; i++) {
        Edge currentEdge = edges[i];
        int srcRoot = find(uf, currentEdge.src);
        int destRoot = find(uf, currentEdge.dest);
        // 若不形成环，则添加到MST
        if (srcRoot != destRoot) {
            mst[mstIndex++] = currentEdge;
            unionSets(uf, srcRoot, destRoot);
        }
    }
    // 打印MST
    printf("Edges in MST:\n");
    int totalWeight = 0;
    for (int i = 0; i < mstIndex; i++) {
        printf("%d - %d (weight: %d)\n", mst[i].src, mst[i].dest, mst[i].weight);
        totalWeight += mst[i].weight;
    }
    printf("Total weight of MST: %d\n", totalWeight);
    free(edges);
    free(mst);
    free(uf->parent);
    free(uf->rank);
    free(uf);
}

5. 排序算法

5.1 简单排序（时间复杂度 ( O(n^2) )）

  • 冒泡排序：相邻元素比较交换，每轮将最大元素冒泡到末尾。
  • 插入排序：将元素插入到已排序部分的正确位置，适合小规模或基本有序数据。
  • 选择排序：每轮选择最小元素与当前位置交换，交换次数少。

插入排序实现

1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 将大于key的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

5.2 高效排序（时间复杂度 ( O(n \log n) )）

  • 归并排序：分治思想，将数组分为两半递归排序，再合并，稳定排序。
  • 快速排序：选择 pivot 划分数组为两部分，递归排序，平均性能优异，非稳定排序。
  • 堆排序：利用大顶堆特性，依次取出堆顶元素，非稳定排序。

归并排序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    // 创建临时数组
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));
    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    // 合并临时数组到原数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    // 复制剩余元素
    while (i < n1) {
        arr[k++] = L[i++];
    }
    while (j < n2) {
        arr[k++] = R[j++];
    }
    free(L);
    free(R);
}

// 归并排序
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 避免溢出
        // 递归排序左半部分
        mergeSort(arr, left, mid);
        // 递归排序右半部分
        mergeSort(arr, mid + 1, right);
        // 合并
        merge(arr, left, mid, right);
    }
}

5.3 排序算法比较

排序算法最好时间复杂度最坏时间复杂度平均时间复杂度空间复杂度稳定性
冒泡排序( O(n) )( O(n^2) )( O(n^2) )( O(1) )稳定
插入排序( O(n) )( O(n^2) )( O(n^2) )( O(1) )稳定
选择排序( O(n^2) )( O(n^2) )( O(n^2) )( O(1) )不稳定
归并排序( O(n \log n) )( O(n \log n) )( O(n \log n) )( O(n) )稳定
快速排序( O(n \log n) )( O(n^2) )( O(n \log n) )( O(\log n) )不稳定
堆排序( O(n \log n) )( O(n \log n) )( O(n \log n) )( O(1) )不稳定

6. 查找算法

6.1 顺序查找

  • 线性查找：遍历数组，时间复杂度 ( O(n) )，适用于无序数据。

6.2 二分查找

  • 条件：有序数组，时间复杂度 ( O(\log n) )。
  • 实现：递归或迭代方式。

二分查找实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 二分查找（迭代）
int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免溢出
        if (arr[mid] == target) {
            return mid; // 找到目标
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标在右半部分
        } else {
            right = mid - 1; // 目标在左半部分
        }
    }
    return -1; // 未找到
}

// 二分查找（递归）
int binarySearchRecursive(int arr[], int left, int right, int target) {
    if (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            return binarySearchRecursive(arr, mid + 1, right, target);
        } else {
            return binarySearchRecursive(arr, left, mid - 1, target);
        }
    }
    return -1;
}

6.3 哈希表

  • 哈希函数：将键映射到哈希表索引，如取余法（key % tableSize）、乘法哈希法（(key * A) % 1 取小数部分乘表长）。
  • 冲突处理：
    • 链地址法：每个索引存储一个链表，冲突元素添加到链表中。
    • 开放定址法：冲突时寻找下一个空闲位置（线性探测、二次探测、双重哈希）。
  • 操作时间复杂度：平均 ( O(1) )，最坏 ( O(n) )（链地址法链表过长或开放定址法聚集）。

链地址法哈希表实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// 哈希表节点结构
typedef struct HashNode {
    int key;
    int value;
    struct HashNode *next;
} HashNode;

// 哈希表结构
typedef struct HashTable {
    int size;
    HashNode **table;
} HashTable;

// 创建哈希表节点
HashNode *createHashNode(int key, int value) {
    HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// 创建哈希表
HashTable *createHashTable(int size) {
    HashTable *hashTable = (HashTable *)malloc(sizeof(HashTable));
    hashTable->size = size;
    hashTable->table = (HashNode **)malloc(size * sizeof(HashNode *));
    for (int i = 0; i < size; i++) {
        hashTable->table[i] = NULL;
    }
    return hashTable;
}

// 哈希函数（取余法）
int hashFunction(int key, int size) {
    return key % size;
}

// 插入键值对
void insertHash(HashTable *hashTable, int key, int value) {
    int index = hashFunction(key, hashTable->size);
    // 检查是否已存在该键
    HashNode *current = hashTable->table[index];
    while (current != NULL) {
        if (current->key == key) {
            current->value = value; // 更新值
            return;
        }
        current = current->next;
    }
    // 插入新节点到链表头部
    HashNode *newNode = createHashNode(key, value);
    newNode->next = hashTable->table[index];
    hashTable->table[index] = newNode;
}

// 查找值
int searchHash(HashTable *hashTable, int key) {
    int index = hashFunction(key, hashTable->size);
    HashNode *current = hashTable->table[index];
    while (current != NULL) {
        if (current->key == key) {
            return current->value; // 找到值
        }
        current = current->next;
    }
    return -1; // 未找到
}

// 删除键值对
void deleteHash(HashTable *hashTable, int key) {
    int index = hashFunction(key, hashTable->size);
    HashNode *current = hashTable->table[index];
    HashNode *prev = NULL;
    while (current != NULL) {
        if (current->key == key) {
            if (prev == NULL) {
                // 删除头节点
                hashTable->table[index] = current->next;
            } else {
                // 删除中间节点
                prev->next = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

// 释放哈希表
void freeHashTable(HashTable *hashTable) {
    for (int i = 0; i < hashTable->size; i++) {
        HashNode *current = hashTable->table[i];
        while (current != NULL) {
            HashNode *temp = current;
            current = current->next;
            free(temp);
        }
    }
    free(hashTable->table);
    free(hashTable);
}

7. 高级数据结构

7.1 B树与B+树

  • B树：多路搜索树，每个节点包含多个键和子节点指针，适用于磁盘等外部存储（减少I/O操作）。
    • 性质：根节点至少有2个子节点，非根节点至少有 ( m/2 ) 个子节点（( m ) 为阶数），所有叶节点在同一层。
  • B+树：B树变种，所有数据存储在叶节点，叶节点形成链表，适合范围查询。
    • 优势：叶节点链表支持顺序访问，查询效率更高。

7.2 红黑树

  • 性质：
    1. 每个节点为红色或黑色。
    2. 根节点为黑色。
    3. 叶节点（NIL）为黑色。
    4. 红色节点的子节点为黑色。
    5. 从根到叶节点的黑色节点数相同（黑高相同）。
  • 操作：插入和删除时通过旋转和变色维持平衡，时间复杂度 ( O(\log n) )。
  • 应用：C++ STL中的 map、set，Linux内核的进程调度。

7.3 伸展树

  • 特点：通过旋转将最近访问的节点移到根，利用局部性原理（最近访问的节点可能再次被访问），均摊时间复杂度 ( O(\log n) )。
  • 伸展操作：包括单旋转、之字形旋转和一字形旋转，将访问节点移到根。

7.4 斐波那契堆

  • 结构：由多个最小堆组成的森林，支持合并、插入、删除最小值等操作，均摊时间复杂度优于二叉堆。
  • 优势：插入和合并操作的均摊时间复杂度为 ( O(1) )，删除最小值为 ( O(\log n) )。
  • 应用：图算法（如Prim和Dijkstra的优化）。

8. 算法设计技术

8.1 贪心算法

  • 策略：每一步选择当前最优解，希望全局最优。
  • 适用条件：
    1. 贪心选择性质：局部最优选择可导致全局最优。
    2. 最优子结构：问题的最优解包含子问题的最优解。
  • 示例：活动选择问题（选择最多不重叠活动）、霍夫曼编码（最优前缀编码）、最小生成树（Kruskal和Prim算法）。

8.2 动态规划

  • 策略：将问题分解为子问题，存储子问题解避免重复计算。
  • 适用条件：
    1. 重叠子问题：子问题重复出现。
    2. 最优子结构：问题的最优解包含子问题的最优解。
  • 步骤：
    1. 定义状态。
    2. 推导状态转移方程。
    3. 初始化边界条件。
    4. 计算最优解。
  • 示例：0-1背包问题、最长公共子序列（LCS）、最短路径（Floyd-Warshall算法）。

0-1背包问题动态规划实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 0-1背包问题（动态规划）
int knapsack(int W, int weights[], int values[], int n) {
    // dp[i][w]：前i个物品，背包容量w时的最大价值
    int dp[n + 1][W + 1];
    // 初始化边界条件（0个物品时价值为0）
    for (int w = 0; w <= W; w++) {
        dp[0][w] = 0;
    }
    // 填充dp数组
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i - 1] <= w) {
                // 选择或不选择第i个物品
                dp[i][w] = (values[i - 1] + dp[i - 1][w - weights[i - 1]]) > dp[i - 1][w] 
                           ? (values[i - 1] + dp[i - 1][w - weights[i - 1]]) 
                           : dp[i - 1][w];
            } else {
                // 不选择第i个物品
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

8.3 分治算法

  • 策略：将问题分解为独立子问题，递归解决后合并结果。
  • 适用条件：问题可分解为规模更小的子问题，子问题解可合并为原问题解。
  • 示例：归并排序、快速排序、大整数乘法、Strassen矩阵乘法。

8.4 回溯算法

  • 策略：尝试所有可能的解，通过剪枝避免无效路径。
  • 适用条件：组合优化问题，解空间较大但可通过剪枝减少搜索空间。
  • 示例：八皇后问题、迷宫问题、子集和问题。

9. 实际应用与性能优化

9.1 数据结构选择原则

  • 根据操作频率：
    • 频繁查找：哈希表、平衡树（红黑树、AVL树）。
    • 频繁插入/删除：链表、二叉搜索树。
    • 频繁顺序访问：数组、链表。
  • 根据数据规模：
    • 小数据：数组（空间效率高）。
    • 大数据：链表、动态数组（无容量限制）。
  • 根据内存限制：
    • 空间紧张：紧凑结构（数组）。
    • 空间充足：操作高效结构（哈希表）。

9.2 性能优化技巧

  • 缓存优化：
    • 时间局部性：最近访问的数据可能再次被访问，使用缓存。
    • 空间局部性：连续访问的数据应存储在连续内存（如数组）。
  • 代码优化：
    • 内联函数：减少函数调用开销。
    • 循环展开：减少循环控制开销。
    • 避免不必要的计算：预处理、缓存中间结果。
  • 并行计算：
    • 多线程：利用多核CPU。
    • GPU加速：适合并行度高的计算（如矩阵乘法）。

10. 总结

《数据结构与算法分析：C语言描述》第2版是一本系统讲解数据结构与算法的经典教材，通过C语言实现，帮助读者理解数据结构的设计原理和算法分析方法。本书的核心价值在于：

  1. 理论与实践结合：不仅讲解概念，还提供C语言实现示例，便于理解与应用。
  2. 时间复杂度分析：贯穿全书的复杂度分析，帮助读者评估算法性能。
  3. 算法设计思路：从问题分析到算法设计，培养解决问题的思维能力。
  4. 高级数据结构：覆盖B树、红黑树等高级结构，拓展知识面。

通过学习本书，读者可以掌握数据结构与算法的核心原理，提高代码效率，为解决复杂问题打下坚实基础。在实际编程中，应根据具体场景选择合适的数据结构和算法，平衡时间复杂度与空间复杂度，编写高效、可维护的代码。

数据结构与算法是计算机科学的基础，无论编程语言如何变化，其核心原理始终不变。掌握好数据结构与算法，不仅可以提高编程能力，还可以培养逻辑思维能力，为未来的职业发展奠定坚实基础。

参考资料

  • 《数据结构与算法分析：C语言描述》（第2版），Mark Allen Weiss 著
  • C语言标准库文档
  • 算法可视化工具：Visualgo（https://visualgo.net/）
  • 数据结构与算法在线课程：Coursera、edX