将void指针元素复制到void指针数组时出现元素重复复制问题

问题背景 #

我在C89环境中实现了参数风格与qsort一致的TreeSort函数，签名如下：

void TreeSort(void* base, size_t num, size_t size, int (*compare)(const void*, const void*))

已完成BST节点定义、插入逻辑及排序框架，但将BST数据写回原数组base时，出现元素重复复制的问题。目前已确认：

• 硬编码数组索引写入时，结果完全正常；
• BST中序遍历打印的内容是正确的，说明树结构本身无问题；
• 怀疑问题出在写入数组时的ptr指针递增操作上。

核心问题分析 #

最可能的原因是递归写入时指针传递方式错误，或者void*的算术运算不符合C89标准，导致写入位置没有正确偏移：

1. C89标准不允许void*直接进行加减运算（void无明确内存大小），部分编译器（如VS2022）的扩展支持可能导致行为异常；
2. 如果递归中传递的是指针副本，对副本的递增操作不会影响上层递归的指针位置，最终所有写入都会覆盖初始的base地址，造成重复。

修复方案 #

方案1：使用指针的指针传递写入位置（推荐，无全局依赖） #

修改中序写入函数，通过void**传递指针，确保递归中能修改上层的指针值：

void inorder_write(Node* node, void** ptr, size_t size) {
    if (node == NULL) return;
    inorder_write(node->left, ptr, size);
    // 转换为char*进行内存拷贝与地址偏移
    memcpy(*ptr, node->data, size);
    *ptr = (char*)*ptr + size;
    inorder_write(node->right, ptr, size);
}

在TreeSort函数中调用时：

void TreeSort(void* base, size_t num, size_t size, int (*compare)(const void*, const void*)) {
    // ... 构建BST的逻辑 ...
    void* current_ptr = base;
    inorder_write(root, &current_ptr, size);
    // ... 释放BST节点的逻辑 ...
}

方案2：使用索引计数器（适合简单场景） #

通过传递索引变量的指针，计算每个元素的写入地址：

void inorder_write(Node* node, void* base, size_t size, size_t* idx) {
    if (node == NULL) return;
    inorder_write(node->left, base, size, idx);
    // 按索引计算目标地址
    void* dest = (char*)base + (*idx) * size;
    memcpy(dest, node->data, size);
    (*idx)++;
    inorder_write(node->right, base, size, idx);
}

调用时初始化索引：

size_t current_idx = 0;
inorder_write(root, base, size, &current_idx);

验证建议 #

1. 在写入逻辑中添加地址打印，确认每次写入的内存地址是否按size大小递增；
2. 检查BST节点存储的data指针是否正确指向原数组的元素（避免节点存储的是同一个临时变量地址）；
3. 确保释放BST节点时不会误修改原数组数据。

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