使用 qsort 对 C 中可变长度字符串的多维数组进行排序

Question

我有一个软件可以生成一个相当大的文本文件，其中包含有关目录中文件的信息。通常有几千个文件。每个人都有一组信息条目，看起来像：

number
number
IMPORTANT NUMBER
info
info
info
info
info

这些重复。对于目录中的每个文件，文本文件将具有相同的八行。

我应该按重要数字、第 3 行出现的值、第 3+8 行、第 3 + 8*2 行等对这个文本文件进行排序

目前，我正在将它们读入多维字符数组，如下所示：

[number][number][IMPORTANT NUMBER 1][info][info][info][info][info]
[number][number][IMPORTANT NUMBER 2][info][info][info][info][info]
[number][number][IMPORTANT NUMBER 3][info][info][info][info][info]
[number][number][IMPORTANT NUMBER 4][info][info][info][info][info]

等等

想法是按重要数字升序对每组 8 个条目进行排序。例如，如果我的数组如下所示：

[number2][number2][2][info2][info2][info2][info2][info2]
[number3][number3][3][info3][info3][info3][info3][info3]
[number1][number1][1][info1][info1][info1][info1][info1]
[number4][number4][4][info4][info4][info4][info4][info4]

排序后看起来像：

[number1][number1][1][info1][info1][info1][info1][info1]
[number2][number2][2][info2][info2][info2][info2][info2]
[number3][number3][3][info3][info3][info3][info3][info3]
[number4][number4][4][info4][info4][info4][info4][info4]

...使用 arr[2] 中的值 (1,2,3,4...) 进行排序。

问题是存储在其他列中的信息的大小往往不同。 arr[3] 可能有 30 个字符的长度。 arr[4] 的长度可能超过 5000。对大量数据执行此操作加起来足够快，以至于我不想只分配最大长度的集合大小，特别是如果我只是在大多数情况下，一次只使用其中的一小部分。

我找到了很多关于使用 qsort 的好答案，但很少有关于对大型多维字符串数组进行排序的答案。我也喜欢使用 qsort，因为我不想重新发明轮子，而且我怀疑我写的任何东西是否有效。

如果有人能阐明如何实现这一点，我将不胜感激。

当前代码是：

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define FIELDS 8

int compare(const void *row1, const void *row2);

int main(int argc, char *argv[])
{
    // (1) - Open File
    const char fname[] = "arrayFile.txt";

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

    printf("Opened file: %s\n", fname); 

    // (2) - Count Lines
    char cr;
    size_t lines = 0;
    while (cr != EOF)
    {
        if (cr == '\n') 
        {
            lines++;
        }
        cr = getc(fp);
    } 
    rewind(fp);

    // (3) - Populate Array
    char *data[lines / FIELDS][FIELDS];
    lines = lines / FIELDS;
    size_t n;

    for (int i = 0; i < lines; i++) 
    {
        for (int j = 0; j < FIELDS; j++)
        {
            data[i][j] = NULL;
            size_t n = 0;
            getline(&data[i][j], &n, fp);
        }    
    }

    // (4) - Print Array Before
    for (int i = 0; i < lines; i++) 
    {
        for (int j = 0; j < FIELDS; j++)
        {
            printf("%s", data[i][j]);
        }
    }

    printf("\n\nNot sorted\n\n");

    // (5) - Sort Array
    qsort(data, lines, sizeof(data[0]), compare);

    printf("\n\nsorted\n\n");

    // (6) - Print Array After
    for (int i = 0; i < lines; i++) 
    {
        for (int j = 0; j < FIELDS; j++)
        {
            printf("%s", data[i][j]);
            free(data[i][j]);
        }
    }

    // Close File
    fclose(fp);

    printf("\n\nNumber of files: %ld\n", lines);
    printf("\n\nNumber of lines: %ld\n", lines * FIELDS);

    return 0;
}

int compare(const void *row1, const void *row2)
{
    const char *(*a)[8] = row1;
    const char *(*b)[8] = row2;

    return strcmp((*a)[2], (*b)[2]);
}

不幸的是（并且可以预见），这会在排序时产生分段错误。我估计这是由于我处理指针和索引的方式所致，但是逃避我的确切原因。

这似乎是了解如何为未来做好事的真正有用的东西，但它比我个人以前尝试在 C 中使用数组和指针做的要多一些。

提前致谢。

编辑：对于感兴趣的各方，上面的代码虽然没有优化，但至少可以正常运行。有关可能改进的建议，请在此处查看答案。

第二次编辑：事实证明，通过 system() 命令对其进行排序也是一个可行的选择，并且占用的内存要少得多 space。这可以通过类似的方式完成：

char cmd[50];
sprintf(cmd, "sort -o destinationFileName sourceFileName");
system(cmd);

系统可以为您完成。

Answer 1

很多问题 - 我只提一个

计数线

不计算行数。（删除第 2 步。）与其进行 2 次传递，不如使用 1 次传递并根据需要调整 data。

一些未经测试的代码给 OP 一个想法：

  char *(*data)[FIELDS] = NULL;
  size_t records_n = 0;  // Allocation total
  size_t records_i;      // Allocation used

  for (records_i = 0; records_i < SIZE_MAX; records_i++) {
    if (records_i == records_n) {
      size_t records_new_n = records_n * 2 + 1;  // Double the allocation
      char *(*newdata)[FIELDS] = realloc(data, sizeof data[0] * records_new_n);
      if (newdata == NULL) {
        free(data);
        fprintf(stderr, "Out of memory.\n");
        exit(EXIT_FAILURE);
      }
      data = newdata;
      records_n = records_new_n;
    }
    int f;
    for (f = 0; f < FIELDS; f++) {
      data[records_i][f] = NULL;
      size_t n = 0;
      if (getline(&data[records_i][f], &n, fp) == -1) {
        if (f == 0) {
          break;
        }
        fprintf(stderr, "Record ended early.\n");
        break; // Or maybe fail?
      }
      // Lop off potential '\n'
      if (n > 0 && data[records_i][f][n - 1] == '\n') {
        data[records_i][f][--n] = 0;
      }
    }
    if (f < FIELDS) {
      break;
    }
  }
  // Perhaps right-size data to records_i here?  Not shown.

  // ... Use data

  // When all done, free all lines allocated (not shown) and ...
  free(data);

Answer 2

您的代码中存在多个问题：

您应该测试 fopen 可能无法打开文件。
char cr; 应该是 int cr; 来处理 getc() 返回的所有 257 个可能的值，假设是 8 位字节。
cr 在 while (cr != EOF) 的第一次迭代期间未初始化。你应该把这个循环写成：
```
  int cr;
  while ((cr = getc(fp)) != EOF) {
      lines += (cr == '\n');
  }
```
如 chux 所述，读取整个文件的初始传递是不必要的，您应该在读取文件时重新分配数组。
char *data[lines / FIELDS][FIELDS]; 可能定义了一个对于自动存储来说太大的数组，导致 堆栈溢出
size_t 的正确格式说明符是 %zu，而不是 %ld。 size_t 不是 long，甚至可能没有相同的大小或参数传递约定。
compare 函数在类型转换中使用了太多的间接寻址。尽管您的类型转换除了 const 正确性外可能还不错，但对于大多数程序员而言，它们很难掌握。您应该使用更简单的方法：
```
int compare(const void *row1, const void *row2) {
     char * const *a = row1;
     char * const *b = row2;

     return strcmp(a[2], b[2]);
}
```

但是请注意，上述函数将按字典顺序对重要数字进行排序，将 11 放在 1 和 2 之间。您可能需要数字顺序：

int compare(const void *row1, const void *row2) {
     char * const *a = row1;
     char * const *b = row2;
     long na = strtol(a, NULL, 10);
     long nb = strtol(b, NULL, 10);
     return (na > nb) - (na < nb);
}

使用 qsort 对 C 中可变长度字符串的多维数组进行排序

Using qsort to sort a multidimensional array of variable-length strings in C

c

arrays

sorting

string

pointers