无法正确排序二维字符数组

Question

我从文件中获取最多 100 个字符串，并将它们放入一个二维字符数组中。 STRING_LEN = 1000

char** read_from_file(char* fname, int * size)  {

    FILE *fp = fopen(fname, "r");

    int lines = 0;
    while(fscanf(fp, "%s", buff) != EOF) {
        lines++;
    }
    *size = lines;
    if(*size > 100) {
        *size = 100;
    }

    rewind(fp);

    char** file_array = malloc(*size * sizeof(char*));

        int counter;
        for(counter = 0; counter < *size; counter++) {
            file_array[counter] = malloc((STRING_LEN + 1) * sizeof(char));
        }
    for(counter = 0; counter < *size; counter++) {
           fscanf(fp, "%s", &file_array[counter]);
        }

    fclose(fp);
    return file_array;
}

快速排序将按字符串长度排序。

void quick_sort(char** words, int first, int last) {

    int pivot, j, i;
    char *temp = malloc((STRING_LEN + 1)* sizeof(char));

    if(first < last) {
        pivot = first;
        i = first;
        j = last;

        while(i < j) {
            while(strlen(&words[i]) <= strlen(&words[pivot]) && i < last)
                i++;
            while(strlen(&words[j]) > strlen(&words[pivot]))
                j--;

                if(i < j) {
                    strcpy(temp, &words[i]);
                    strcpy(&words[i], &words[j]);
                    strcpy(&words[j], temp);
                }
        }

        strcpy(temp, &words[pivot]);
        strcpy(&words[pivot], &words[j]);
        strcpy(&words[j], temp);
        free(temp);
        quick_sort(words, first, j-1);
        quick_sort(words, j+1, last);
    }
}

快速排序功能对于某些文件可以正常工作，但对于其他文件，信息会失真。文件内容

car 
x 
house 
door 
ash 
a 
elephantback 
back

快速排序后

x 
a 
ash 
car 
back 
door 
house 
elephanthouse

如您所见，最后一个单词已经重新排列，如果文件中有更多单词，它会变得更糟。为什么 strcpy 会这样组合单词？

Answer 1

这里的问题是您将字符串从一个数组复制到另一个数组，但每个数组的 space 刚好够它包含的字符串。因此，例如，如果您尝试将 5 个字符的字符串复制到仅分配了 3 个字符的 space，则会超出分配的内存，导致未定义的行为。

与其复制整个字符串，不如复制指针：

temp = words[i];
words[i] = words[j];
words[j] = temp;
...
temp = words[pivot];
words[pivot] = words[j];
words[j] = temp;

编辑：

显然我错过了所有字符串都分配了相同（大）数量的 space。所以这不是未定义行为的原因。正如 Joachim Pileborg 在他的回答中提到的那样，使用像 &words[j] 这样的表达式是根本原因。

尽管如此，如上所述交换指针比复制实际字符串更有效，并且因为它解决了相同的错误代码行，它仍然会解决问题。

Answer 2

您的排序函数中有 未定义的行为：表达式 &words[j] returns 指向存储在 words[j] 的指针的指针，即它是类型 char ** 而不是 char *。删除所有这些地址运算符，仅使用 words[j] 获取指向字符串的指针。

无法正确排序二维字符数组

Unable to sort 2d character array correctly

c

string

quicksort