从BST删除struct record*并清理链表字段时遇代码错误求助

需求说明 #

从BST中删除对应uid的struct record*类型记录n，需完成以下操作：

• 从其他记录的friends链表（以list_records* friends为头节点）中移除n，并释放对应链表节点内存
• 释放n自身的friends链表所有节点内存
• 返回被删除节点的副本；若节点不存在，返回status为-1的dummy记录

问题描述 #

我编写了如下代码，free_memory为指定内存释放函数：

• 注释代码报错：Verification failed. Ensure that there aren't duplicates in friend list
• 未注释代码报错：Integrity was violated
  已排查多日未发现逻辑问题，恳请帮忙定位bug。

struct record delete_record_bst(char uid[MAX_LEN])
{
    struct record* found = search_record(uid, bst_root);
    if (found == NULL) {
        struct record dummy = { .status = -1 };
        return dummy;
    }
    struct list_records* tmp = found->friends;
    // while (tmp!= NULL) {
    //     struct record* friend_record = tmp->record;
    //     if (friend_record != NULL) {
    //         struct list_records* friend_list = friend_record->friends;
    //         deleteNode(friend_list, found);
    //     }
    //     tmp = tmp->next;
    // }
    // struct record deleted_value = *found;
    // struct list_records* tmp1 = found->friends;
    // while (tmp1 != NULL) {
    //     struct list_records* next = tmp1->next;
    //     free_memory(tmp1);
    //     tmp1 = next;
    // }
    // bst_root = delete(bst_root, found);
    // num_bst_nodes--;
    // free_memory(found);
    // return deleted_value;
    struct list_records* prev=NULL;
    while (tmp!=NULL){
        struct record* friend_record=tmp->record;
        deleteNode(friend_record->friends,found);
        prev=tmp;
        tmp=tmp->next;
        free_memory(prev);
    }
    bst_root=delete(bst_root,found);
    num_bst_nodes--;
    return *found;
}

struct record* delete(struct record *bst_root,struct record *r){
    if (bst_root == NULL) {
      return NULL;
    }
    if (cmp_uid(bst_root->uid,r->uid)==0) {
        if (bst_root->left == NULL) {
            struct record *ret = bst_root->right;
            free_memory(bst_root);
            return ret;
        }
        else if (bst_root->right == NULL) {
            struct record *ret = bst_root->left;
            free_memory(bst_root);
            return ret;
        }
        else if (bst_root->right != NULL && bst_root->left != NULL) {
            struct record *min_node = find_min(bst_root->right);
            struct record* left1=bst_root->left;
            struct record* right1=bst_root->right;
            memcpy(bst_root,min_node,sizeof(struct record)); 
            bst_root->left=left1;
            bst_root->right=right1;
            bst_root->right = delete(bst_root->right, min_node);
            return bst_root;
        }
    }
    else if (cmp_uid(r->uid,bst_root->uid)>0) {
        bst_root->right = delete(bst_root->right, r);
    }
    else {
        bst_root->left = delete(bst_root->left, r);
    }
    return bst_root;
}

void deleteNode(struct list_records* head,struct record* r)
{
    struct list_records* temp = head;
    struct list_records* prev=NULL;
    if (temp != NULL && cmp_record(temp->record,r)==0) {
        head = temp->next;
        free_memory(temp);
        return;
    }
    while (temp != NULL && cmp_record(temp->record,r)!=0) {
        prev = temp;
        temp = temp->next;
    }
    if (temp != NULL){
        prev->next = temp->next;
        free_memory(temp);
    }
}

问题定位与修复方案 #

1. 未注释代码的致命错误：访问已释放内存

未注释代码中，delete函数会调用free_memory(bst_root)释放found指向的内存，但之后执行return *found，属于非法访问已释放内存，直接触发Integrity was violated错误。必须先复制节点副本，再释放原节点。

2. deleteNode函数传参错误

deleteNode的第一个参数是值传递的struct list_records* head，函数内部修改head = temp->next无法同步到外部的friend_record->friends指针。如果要删除的是friend链表的头节点，外部头指针不会更新，导致链表残留无效节点，这也是注释代码报重复错误的原因。需改为传指针的指针：

void deleteNode(struct list_records** head, struct record* r)
{
    if (*head == NULL) return;

    struct list_records* temp = *head;
    struct list_records* prev = NULL;

    // 删除头节点
    if (cmp_record(temp->record, r) == 0) {
        *head = temp->next;
        free_memory(temp);
        return;
    }

    // 查找目标节点
    while (temp != NULL && cmp_record(temp->record, r) != 0) {
        prev = temp;
        temp = temp->next;
    }

    // 删除节点
    if (temp != NULL) {
        prev->next = temp->next;
        free_memory(temp);
    }
}

3. delete函数的memcpy逻辑错误

直接用memcpy复制整个struct record会覆盖原节点的子树指针和friends链表指针，导致内存泄漏或野指针。应只复制数据字段（如uid），保留原节点的子树和链表关联：

struct record* delete(struct record *bst_root, struct record *r){
    if (bst_root == NULL) {
        return NULL;
    }

    int cmp_result = cmp_uid(bst_root->uid, r->uid);
    if (cmp_result == 0) {
        if (bst_root->left == NULL) {
            struct record *ret = bst_root->right;
            free_memory(bst_root);
            return ret;
        } else if (bst_root->right == NULL) {
            struct record *ret = bst_root->left;
            free_memory(bst_root);
            return ret;
        }

        // 仅复制数据字段，而非整个结构体
        struct record *min_node = find_min(bst_root->right);
        memcpy(bst_root->uid, min_node->uid, MAX_LEN);
        // 复制其他必要数据字段（如status等）

        bst_root->right = delete(bst_root->right, min_node);
        return bst_root;
    } else if (cmp_uid(r->uid, bst_root->uid) > 0) {
        bst_root->right = delete(bst_root->right, r);
    } else {
        bst_root->left = delete(bst_root->left, r);
    }
    return bst_root;
}

4. 修正后的delete_record_bst函数

struct record delete_record_bst(char uid[MAX_LEN])
{
    struct record* found = search_record(uid, bst_root);
    if (found == NULL) {
        struct record dummy = { .status = -1 };
        return dummy;
    }

    // 先复制返回副本，避免后续释放原节点后访问非法内存
    struct record deleted_value = *found;
    deleted_value.friends = NULL; // 清空副本的链表指针

    // 从所有好友的链表中移除当前节点
    struct list_records* tmp = found->friends;
    while (tmp != NULL) {
        struct record* friend_record = tmp->record;
        if (friend_record != NULL) {
            deleteNode(&friend_record->friends, found);
        }
        tmp = tmp->next;
    }

    // 释放当前节点的friends链表
    tmp = found->friends;
    while (tmp != NULL) {
        struct list_records* next = tmp->next;
        free_memory(tmp);
        tmp = next;
    }

    // 从BST中删除节点并释放内存
    bst_root = delete(bst_root, found);
    num_bst_nodes--;
    free_memory(found);

    return deleted_value;
}

内容的提问来源于stack exchange，提问作者Ash