使用qsort對C中的可變長度字串的多維陣列進行排序

我有一個軟體可以生成一個相當大的文本檔案，其中包含有關目錄中檔案的資訊。通常有幾千個檔案。每個人都有一組資訊條目，看起來像：

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 中使用陣列和指標做的事情要多一點。

提前致謝。

編輯：對于感興趣的各方，上面的代碼雖然沒有優化，但至少是功能性的。有關可能改進的建議，請參閱此處的答案。

uj5u.com熱心網友回復：

您的代碼中有多個問題：

• 您應該測驗fopen可能無法打開檔案。

• char cr;應該是int cr;處理所有 257 個可能回傳的值getc()，假設是 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);
  }
  

uj5u.com熱心網友回復：

許多擔憂——我只提一個

計數線

不要計算行數。（放棄第 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);

標籤：数组 C 细绳 排序 指针

上一篇：在python中作為切片傳遞給enumerate()時是否形成了新的陣列副本？

下一篇：排序串列多個鍵和上最近的值