C语言MergeSort实现中自定义字典结构的内存分配问题

针对存储字符串和权重的dict结构实现归并排序时，在复制元素到临时字典阶段出现段错误，以下是问题分析和修复方案：

核心错误点分析 #

• 无效内存分配与指针覆盖：复制元素到临时字典时，你为每个item*额外分配内存，随后又用原字典的指针覆盖它，既造成内存泄漏，也完全没必要——Dict构造函数已经为wordlist分配了足够的指针数组空间。
• 未初始化变量致越界：右半部分复制循环中使用了未初始化的k，导致访问非法内存地址，触发段错误。
• 归并起始位置错误：合并阶段k的初始值设为leftlen是错误的，应该从start开始，否则会覆盖原字典的错误区间。
• 剩余元素处理指针误用：最后处理右半部分剩余元素时，错误引用了左字典的指针。
• 字符串内存分配长度不足：Item函数中分配字符串内存时未考虑\0终止符，会导致后续字符串复制越界。

修复后的完整代码 #

/////// DICTIONARY METHODS ////////
typedef struct {
  char *item;
  int weight;
} item;

typedef struct {
    item **wordlist;
    //track size of dictionary
    int size;
} dict;

//dict constructor
dict* Dict(int count){  
    //allocate space for dictionary
    dict* D = malloc(sizeof(dict));
    //allocate space for words
    D->wordlist = malloc(sizeof(item*) * count);
    //initial size
    D->size = 0;
    return D;
}

//word constructor
item* Item(char str[]){
    //allocate memory for struct
    item* W = malloc(sizeof(item));
    //allocate memory for string (include null terminator)
    W->item = malloc(sizeof(char) * (strlen(str) + 1));
    //copy input string into the item
    strcpy(W->item, str);
    W->weight = 0;
    return W;
}

void merge(dict* D, int start, int middle, int stop){
    //create ints to track lengths of left and right of array
    int leftlen = middle - start + 1;
    int rightlen = stop - middle;

    //create new temporary dicts to store the two sides of the array 
    dict* L = Dict(leftlen);
    dict* R = Dict(rightlen);

    int i, j, k;

    //copy elements start through middle into left dict
    for (i = 0; i < leftlen; i++){
        //直接复制指针即可，无需额外分配
        L->wordlist[i] = D->wordlist[start + i];
    }

    //copy elements middle+1 through stop into right dict
    for (j = 0; j < rightlen; j++){
        //使用j作为偏移量，避免未初始化变量问题
        R->wordlist[j] = D->wordlist[middle + 1 + j];
    }

    i = 0;
    j = 0;
    k = start; //从原数组的start位置开始合并

    while ((i < leftlen) && (j < rightlen)){
        if (strcmp(L->wordlist[i]->item, R->wordlist[j]->item) <= 0) {
            D->wordlist[k] = L->wordlist[i];
            i++;
            k++;
        } else {
            D->wordlist[k] = R->wordlist[j];
            j++;
            k++;
        }
    }

    //处理左半部分剩余元素
    while (i < leftlen){
        D->wordlist[k] = L->wordlist[i];
        i++;
        k++;
    }

    //处理右半部分剩余元素，修正指针为R
    while (j < rightlen){
        D->wordlist[k] = R->wordlist[j];
        j++;
        k++;
    }

    //释放临时字典的内存，避免内存泄漏
    free(L->wordlist);
    free(L);
    free(R->wordlist);
    free(R);
}

void mergeSort(dict* D, int start, int stop){
    if (start < stop) {
        int middle = start + (stop - start) / 2;
        mergeSort(D, start, middle);
        mergeSort(D, middle + 1, stop);
        merge(D, start, middle, stop);
    }
}

额外说明 #

• 修复后的代码在merge函数末尾添加了临时字典的内存释放逻辑，避免长期运行的内存泄漏问题。
• Item函数补充了strcpy来复制输入字符串，原代码仅分配内存但未拷贝内容，会导致后续字符串操作出现未知错误。

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