C / C++ / 系统课时
检查项目复杂度和内存问题
检查项目复杂度和内存问题
任务管理器功能跑通后,还要确认它在任务数量增长时不会突然变慢,也不会因动态内存错误变得不稳定。本节从链表、哈希索引和堆三个核心结构入手,核对时间复杂度、所有权、数组边界、扩容与释放路径,并用 Sanitizer 做一次动态验证。
学习目标
- 能写出新增、查找、删除和优先级操作的主要时间复杂度,并发现不必要的线性扫描。
- 能明确任务对象、哈希桶节点和堆数组的内存所有权,避免泄漏、越界和重复释放。
- 能使用编译器 Sanitizer 对越界、释放后访问和重复释放进行动态检查。
先把复杂度账算清楚
设任务数为 ,哈希桶数为 。如果项目同时维护链表、哈希表和二叉堆,常见目标复杂度如下:
| 操作 | 合理实现 | 主要复杂度 |
|---|---|---|
| 按 ID 查找 | 哈希表定位桶,再处理冲突链 | 平均 ,最坏 |
| 遍历全部任务 | 顺序扫描链表或数组 | |
| 插入优先级堆 | 追加后向上调整 | |
| 查看最高优先级 | 读取堆顶 | |
| 删除堆顶 | 末尾元素移到堆顶后向下调整 | |
| 按 ID 删除任务 | 哈希定位任务,但同步删除堆元素若先线性找位置 | 常见为 |
重点不是让所有操作都变成 ,而是确认实现与设计预期一致。例如已经有哈希索引,却仍在每次按 ID 查询时遍历链表,就等于没有利用索引;如果删除任意任务时需要在线性扫描堆中找位置,这个 成本应被明确记录,而不是误写成 。
明确谁负责释放任务对象
链表、哈希表和堆如果都保存同一个 Task *,最危险的问题不是“指针多”,而是“谁拥有它”。建议只指定一个结构拥有 Task 对象,其余结构只保存非拥有型指针或任务 ID。销毁索引时只释放索引自己的节点或数组,不能再次释放共享的 Task。

检查删除路径时,要从一个任务被移除的入口一路追踪到最终 free。如果哈希桶节点、堆数组和链表节点都引用同一任务,应先从各索引中移除引用,再由唯一所有者释放任务。反过来先 free(task) 再让堆或哈希表继续访问该指针,会形成 use-after-free。
检查堆数组和哈希桶边界
动态数组要始终维护 0 <= size <= capacity。写入 items[size] 之前必须确保容量足够;realloc 失败时不能直接覆盖原指针,否则原内存地址会丢失。下面是片段示例,假设已有 Heap 类型,其中 items 为指针数组,capacity 为当前容量。
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
static bool heap_reserve(Heap *heap, size_t need) {
if (need <= heap->capacity) {
return true;
}
size_t new_capacity = heap->capacity == 0 ? 8 : heap->capacity;
while (new_capacity < need) {
if (new_capacity > SIZE_MAX / 2) {
return false;
}
new_capacity *= 2;
}
Task **tmp = realloc(heap->items, new_capacity * sizeof *tmp);
if (tmp == NULL) {
return false;
}
heap->items = tmp;
heap->capacity = new_capacity;
return true;
}哈希表也要检查桶下标是否始终落在 [0, bucket_count)。最常见的安全写法是先确保 bucket_count > 0,再使用 hash % bucket_count。销毁哈希表时,需要释放每条冲突链上的索引节点,最后再释放桶数组;是否释放节点引用的 Task,则必须服从前面的所有权约定。
用 Sanitizer 跑一次动态检查
GCC 或 Clang 可以在测试构建中同时启用 AddressSanitizer 和 UndefinedBehaviorSanitizer。下面是命令模板;执行前把 <PATH> 替换为项目目录,把 <SOURCE_FILES> 替换为项目实际的 .c 源文件列表。
cd "<PATH>"
cc -std=c11 -Wall -Wextra -Wpedantic -g -O1 -fsanitize=address,undefined -fno-omit-frame-pointer <SOURCE_FILES> -o taskmgr
ASAN_OPTIONS=detect_leaks=1 ./taskmgr预期结果
编译成功时编译器不输出错误。
程序正常结束时可以有自身业务输出,但不应出现 AddressSanitizer 或 UndefinedBehaviorSanitizer 的错误诊断。实际路径和源文件名会因项目而异。如果出现 heap-buffer-overflow,优先检查堆数组容量、哈希桶下标和循环边界;出现 heap-use-after-free 时检查删除后是否仍有索引持有旧指针;出现 double-free 时检查是否有两个结构都把同一个 Task 当成所有者。
按释放路径完成验收
最后不要只验证“退出时没有崩溃”。先创建多批任务,再执行查找、优先级调整、删除和重复扩容,确保每条修改路径都被覆盖。删除任务后再次按 ID 查询应明确返回“未找到”,堆中也不应残留指向已释放任务的指针。
项目可以用三条不变量收口:所有索引下标都在合法范围内;每块动态内存都有且只有一个明确的释放责任方;结构变化后复杂度仍与设计一致。静态检查复杂度和所有权,再用 Sanitizer 覆盖真实运行路径,才能把“能运行”提升为“可长期运行”。