C / C++ / 系统课时
删除任务并同步多个结构
删除任务并同步多个结构
一个内存任务管理器往往同时用链表保存任务、哈希表按 ID 定位、最大堆负责优先级调度。删除任务时只改其中一个结构会留下悬空指针或“幽灵任务”。本节用同一任务对象被多个结构引用的方式,完成一次一致的删除操作。
学习目标
- 理解多种数据结构共享同一批任务时的一致性风险。
- 实现“哈希定位 → 移出堆 → 移除索引 → 脱链 → 释放内存”的删除流程。
- 能通过不变量和验证步骤发现悬空指针、重复记录与遗漏更新。
一致性问题的本质
链表、哈希表和优先队列解决的是不同问题:链表便于遍历全部任务,哈希表便于按 ID 查找,最大堆便于取得最高优先级。最安全的做法不是在三个结构里复制三份 Task,而是只分配一个 Task 对象,让各结构保存它的指针。
删除时必须先让所有结构停止引用该对象,最后才能 free。如果先释放内存,再去更新堆或哈希表,后续访问就是未定义行为;如果漏掉某个结构,则查询结果和调度结果会互相矛盾。

把位置元数据放回任务对象
为了让最大堆删除任意任务仍保持 ,任务对象记录 heapIndex。堆交换两个元素时同步更新这两个索引,因此通过哈希表拿到 Task * 后,可以直接定位它在堆中的位置,不必再做 扫描。
下面的完整示例使用双向链表保存全部任务、拉链哈希表按 ID 索引、最大堆调度优先级。删除函数本身不申请新内存,因此找到任务后,各更新步骤都可以在已有数据上完成。
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define HEAP_CAPACITY 16
#define HASH_SIZE 17
typedef struct Task {
int id;
const char *title;
int priority;
size_t heapIndex;
struct Task *prev;
struct Task *next;
struct Task *hashNext;
} Task;
typedef struct {
Task *items[HEAP_CAPACITY];
size_t size;
} MaxHeap;
typedef struct {
Task *head;
Task *buckets[HASH_SIZE];
MaxHeap heap;
size_t count;
} TaskManager;
static size_t hash_id(int id) {
return (size_t)id % HASH_SIZE;
}
static void heap_swap(MaxHeap *heap, size_t a, size_t b) {
Task *tmp = heap->items[a];
heap->items[a] = heap->items[b];
heap->items[b] = tmp;
heap->items[a]->heapIndex = a;
heap->items[b]->heapIndex = b;
}
static void sift_up(MaxHeap *heap, size_t index) {
while (index > 0) {
size_t parent = (index - 1) / 2;
if (heap->items[parent]->priority >= heap->items[index]->priority) {
break;
}
heap_swap(heap, parent, index);
index = parent;
}
}
static void sift_down(MaxHeap *heap, size_t index) {
for (;;) {
size_t left = index * 2 + 1;
size_t right = index * 2 + 2;
size_t largest = index;
if (left < heap->size &&
heap->items[left]->priority > heap->items[largest]->priority) {
largest = left;
}
if (right < heap->size &&
heap->items[right]->priority > heap->items[largest]->priority) {
largest = right;
}
if (largest == index) {
break;
}
heap_swap(heap, index, largest);
index = largest;
}
}
static bool heap_push(MaxHeap *heap, Task *task) {
if (heap->size == HEAP_CAPACITY) {
return false;
}
task->heapIndex = heap->size;
heap->items[heap->size] = task;
heap->size++;
sift_up(heap, task->heapIndex);
return true;
}
static void heap_remove(MaxHeap *heap, Task *task) {
size_t index = task->heapIndex;
size_t last = heap->size - 1;
if (index != last) {
heap_swap(heap, index, last);
}
heap->size--;
if (index < heap->size) {
size_t parent = index == 0 ? 0 : (index - 1) / 2;
if (index > 0 &&
heap->items[index]->priority > heap->items[parent]->priority) {
sift_up(heap, index);
} else {
sift_down(heap, index);
}
}
}
static Task *hash_find(TaskManager *manager, int id) {
Task *cur = manager->buckets[hash_id(id)];
while (cur != NULL && cur->id != id) {
cur = cur->hashNext;
}
return cur;
}
static void hash_insert(TaskManager *manager, Task *task) {
size_t bucket = hash_id(task->id);
task->hashNext = manager->buckets[bucket];
manager->buckets[bucket] = task;
}
static void hash_remove(TaskManager *manager, Task *task) {
size_t bucket = hash_id(task->id);
Task **link = &manager->buckets[bucket];
while (*link != NULL && *link != task) {
link = &(*link)->hashNext;
}
if (*link == task) {
*link = task->hashNext;
}
}
static bool add_task(TaskManager *manager, int id,
const char *title, int priority) {
if (hash_find(manager, id) != NULL) {
return false;
}
Task *task = malloc(sizeof(*task));
if (task == NULL) {
return false;
}
*task = (Task){
.id = id,
.title = title,
.priority = priority,
.prev = NULL,
.next = manager->head,
.hashNext = NULL
};
if (!heap_push(&manager->heap, task)) {
free(task);
return false;
}
if (manager->head != NULL) {
manager->head->prev = task;
}
manager->head = task;
hash_insert(manager, task);
manager->count++;
return true;
}
static bool delete_task(TaskManager *manager, int id) {
Task *task = hash_find(manager, id);
if (task == NULL) {
return false;
}
/* 先清理所有外部引用,最后才释放任务对象。 */
heap_remove(&manager->heap, task);
hash_remove(manager, task);
if (task->prev != NULL) {
task->prev->next = task->next;
} else {
manager->head = task->next;
}
if (task->next != NULL) {
task->next->prev = task->prev;
}
manager->count--;
free(task);
return true;
}
static void destroy_manager(TaskManager *manager) {
Task *cur = manager->head;
while (cur != NULL) {
Task *next = cur->next;
free(cur);
cur = next;
}
}
int main(void) {
TaskManager manager = {0};
if (!add_task(&manager, 201, "修复支付告警", 100) ||
!add_task(&manager, 202, "整理周报", 30) ||
!add_task(&manager, 203, "更新依赖", 70)) {
fprintf(stderr, "初始化任务失败\n");
destroy_manager(&manager);
return 1;
}
printf("删除前最高优先级: #%d %s\n",
manager.heap.items[0]->id,
manager.heap.items[0]->title);
printf("删除 #201: %s\n",
delete_task(&manager, 201) ? "成功" : "失败");
printf("哈希索引查找 #201: %s\n",
hash_find(&manager, 201) == NULL ? "不存在" : "仍存在");
printf("删除后最高优先级: #%d %s\n",
manager.heap.items[0]->id,
manager.heap.items[0]->title);
printf("当前任务数: %zu\n", manager.count);
destroy_manager(&manager);
return 0;
}预期输出
删除前最高优先级: #201 修复支付告警
删除 #201: 成功
哈希索引查找 #201: 不存在
删除后最高优先级: #203 更新依赖
当前任务数: 2删除顺序为什么重要
推荐顺序是先通过哈希表定位对象,再从最大堆移除、从哈希索引移除、从链表脱链,最后释放内存。这里最重要的规则不是某个具体容器先于另一个,而是 free 必须最后发生,并且函数返回成功前,所有结构都不再引用目标对象。
heap_remove 还要维护另一个不变量:每次交换堆元素,都必须同步两个任务的 heapIndex。只交换指针却忘记更新索引,会让下一次按 ID 删除任务时定位到错误位置,随后可能删除无关任务。
如何验证多个结构已经同步
删除成功至少要验证三个维度:哈希查找不到该 ID;堆顶和后续调度中不再出现该任务;链表遍历计数与管理器的 count 一致。示例已经验证前两项和总数,项目中还可以在调试构建里加入遍历断言,持续检查“链表任务数 = 哈希可达任务数 = 堆元素数”。
如果以后加入“修改优先级”“批量删除”或“持久化”,仍应先定义这些跨结构不变量,再设计更新顺序。单个数据结构的操作正确,不等于整个任务管理器状态一致;真正需要维护的是多个视图对同一个任务集合的共同约束。