稀疏集初始化malloc调用错误求助：单元测试运行不通过

原代码核心错误点 #

• 内存分配逻辑完全颠倒：不需要分别为两个数组分配struct sparse_set实例，struct sparse_set是整个稀疏集的管理结构体，应当先分配1个该结构体实例，再为其内部的稠密数组、稀疏数组成员分配对应内存
• malloc大小计算错误：sizeof(capacity)获取的是capacity变量本身的类型字节大小（如int类型为4字节），并非数组所需容量。稠密数组大小应为capacity * 存储元素的类型大小，稀疏数组大小应为(max_value + 1) * 索引类型大小
• 返回值逻辑错误：C语言逗号表达式仅返回最后一个值，原写法无法同时返回两个数组指针，应当返回初始化完成的struct sparse_set管理结构体的指针作为稀疏集句柄
• 结构体设计冗余：struct sparse_set中的sparseSetPtr成员无存在必要，管理结构体本身的指针即可作为对外暴露的句柄

修正后的实现 #

首先调整结构体定义，补充必要的元数据字段：

// 提前定义类型别名
typedef struct sparse_set* sparse_set_ptr;
typedef int sparse_set_index_t;
typedef int sparse_set_elem_t;

struct sparse_set {
    sparse_set_elem_t *d_arr; // 稠密数组，存储实际元素，大小为capacity
    sparse_set_index_t *s_arr; // 稀疏数组，存储元素在稠密数组的索引，大小为max_value+1
    sparse_set_index_t size; // 当前已存储元素数量，用于增删操作的边界判断
    sparse_set_index_t capacity; // 最大可存储元素数量
    sparse_set_elem_t max_value; // 可存储的最大元素值
};

修正后的初始化函数实现：

sparse_set_ptr ss_init(sparse_set_index_t capacity, sparse_set_elem_t max_value) {
    // 1. 分配稀疏集管理结构体内存
    sparse_set_ptr set = malloc(sizeof(struct sparse_set));
    if (set == NULL) return NULL;

    // 2. 分配稠密数组内存：最多存capacity个元素
    set->d_arr = malloc(capacity * sizeof(sparse_set_elem_t));
    if (set->d_arr == NULL) {
        free(set);
        return NULL;
    }

    // 3. 分配稀疏数组内存：取值范围[0, max_value]共max_value+1个位置
    set->s_arr = malloc((max_value + 1) * sizeof(sparse_set_index_t));
    if (set->s_arr == NULL) {
        free(set->d_arr);
        free(set);
        return NULL;
    }

    // 4. 初始化基础属性
    set->size = 0;
    set->capacity = capacity;
    set->max_value = max_value;
    // 稀疏数组所有位置初始化为无效索引-1，方便后续查找判断元素是否存在
    for (sparse_set_index_t i = 0; i <= max_value; i++) {
        set->s_arr[i] = -1;
    }

    return set;
}

额外注意事项 #

• 后续实现增删查操作时必须保证两个数组的数据同步：插入元素时，将元素存在d_arr的size位置，同时将s_arr[元素值]设为当前size，再将size自增；删除元素时可将待删元素和d_arr最后一个元素交换，更新s_arr中两个元素对应的索引值，再将size自减
• 用完稀疏集需要配套销毁函数，依次释放s_arr、d_arr、管理结构体本身的内存，避免内存泄漏

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