c中的多维数组的qsort导致段错误

Question

我想在C中使用qsort（）对二元数组进行排序。数组包含三维点数据，它是使用fscanf从文件读入的。我的编程技巧是相当有限的，但我有非常大的数据集，我需要处理。如果我的代码很糟糕，请提前抱歉。

23127.947，23127.947，23127.947
523127.790，523127.790，523127.790
523127.747，523127.747，523127.747
523127.761，523127.761，523127.761
523127.768，523127.768，523127.768
（...为3158632点）

我已经使用printf来隔离我的代码中的问题似乎是导致分段错误的qsort（）行。从我读过的Stack Overflow的其他问题可以看出，我的“比较”函数可能会出现问题。做一维数组的例子看起来很简单，但我看到的二维数组的例子并没有进入比较其他维度（先是X，那么如果X1 = X2，比较Y，那么如果Y1 = Y2，则比较Z）。

int main(int argc, char *argv[]) { 
    int i,j,c; 
    double x,y,z; 
    int ROWS = 3158632; 
    int COLS = 3; 
    char buffer[100]; 

    double** data = Make2DDoubleArray(ROWS, COLS); 

    //Open the plot file to read in, and have an output write file 
    FILE *fp = fopen("Plot_1-2.txt","r"); 

    if(fp == NULL) { 
     printf("Can't open file\n"); 
     exit; 
    } 

    fgets(buffer, 100, fp); //Ignore header 

    for(i=0; ; i++){ 
     if ((c = fgetc(fp)) == EOF){ 
      break; 
     } 
     fscanf(fp,"%lf, %lf, %lf",&x, &y, &z); 
     data[i][0] = x; 
     data[i][1] = y; 
     data[i][2] = z; 
    } 

    printf("First 5 unsorted numbers:\n"); 
    for(j=0;j<5;j++){ 
     printf("Line %d: %.3lf, %.3lf, %.3lf\n",j, data[j][0], data[j][0], data[j][0]); 
    } 
    printf("Last 5 unsorted numbers:\n"); 

    for(j=ROWS-5;j<ROWS;j++){ 
     printf("Line %d: %.3lf, %.3lf, %.3lf\n",j, data[j][0], data[j][0], data[j][0]); 
    } 

    /* Sort array using Quicksort algorithm: */ 
    printf("Sorting...\n"); 
    qsort(data, ROWS, COLS*sizeof(double), &compare); 

    printf("First 10 sorted numbers:\n"); 
    for(j=0;j<10;j++){ 
     printf("Line %d: %.3lf, %.3lf, %.3lf\n",j, data[j][0], data[j][0], data[j][0]); 
    } 

    fclose(fp); 

    for (i=0; i<ROWS; i++){ 
     free(data[i]); 
    } 
    free(data); 

    return 0; 
} 

double** Make2DDoubleArray(int arraySizeX, int arraySizeY) { 
    double** theArray; 
    int i; 
    theArray = (double**) malloc(arraySizeX*sizeof(double*)); 
    for (i = 0; i < arraySizeX; i++) 
     theArray[i] = (double*) malloc(arraySizeY*sizeof(double)); 
    return theArray; 
} 

int compare(const void *arg1, const void *arg2) { 
    //double a, b, c, d, e, f; 
    double *a = (double*)arg1; 
    double *b = (double*)arg2; 
    double *c = ((double*)arg1 + 1); 
    double *d = ((double*)arg2 + 1); 
    double *e = ((double*)arg1 + 2); 
    double *f = ((double*)arg2 + 2); 

    if(a > b) 
     return 1; 
    else if(a < b) 
     return -1; 
    else { 
     if(c > d) 
      return 1; 
     else if(c < d) 
      return -1; 
     else { 
      if(e > f) 
       return 1; 
      else if(e < f) 
       return -1; 
      else 
       return 0; 
     } 
    } 
} 

我想知道如果告诉快速排序去“COLS *的sizeof（双）”是错误的方式与我如何分配给二维数组的存储办呢？将这个问题视为一维数组会使其余部分工作吗？如果可能的话，我宁愿将它保留为二维数组。

Answer 1

这并不意味着没有任何头部像<stdio.h>，<stdlib.h>等..

请解释exit;。我想你的意思是exit(0);。

main有几个问题。由于fgetc，您的代码可能会丢失您的第一个值的最重要的数字，这是一个微妙的错误。如果你想测试EOF，测试返回值scanf（Jee！我没有想到！我希望他们在手册中写下这些东西！ Duh，他们做...）。文件末尾的示例比这更好，因为该示例确保实际上由fscanf解析了三个值。

for(size_t i=0; fscanf(fp,"%lf, %lf, %lf",&x, &y, &z) != EOF; i++){ 
    data[i][0] = x; 
    data[i][1] = y; 
    data[i][2] = z; 
} 

您的Make2DDoubleArray函数存在问题。它分配了多个不相交的数组，其中qsort无法处理。一步分配数组不是更简单吗？

void *Make2DDoubleArray(size_t x) { 
    double (*theArray)[3] = malloc(x * sizeof *theArray); 
    return theArray; 
} 

theArray被声明为指向3个双打数组的指针。你甚至不需要这个Make2DDoubleArray。

compare函数存在问题。

double *a = (double*)arg1; 
double *b = (double*)arg2; 

a和b是指针，

if(a > b) 
    return 1; 
else if(a < b) 
    return -1; 

...但你的代码比较它们为整数，渲染的那种malfunctional。 array[0]的地址将始终小于array[1]的地址。

---

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

int main(int argc, char *argv[]) { 
    int j,c; 
    double x,y,z; 
    size_t ROWS = 3158632; 
    size_t COLS = 3; 
    char buffer[100]; 
    double (*theArray)[COLS] = malloc(ROWS * sizeof *theArray); 

    //Open the plot file to read in, and have an output write file 
    FILE *fp = fopen("Plot_1-2.txt","r"); 

    if(fp == NULL) { 
     printf("Can't open file\n"); 
     exit(0); 
    } 

    fgets(buffer, 100, fp); //Ignore header 

    for(size_t i=0; fscanf(fp,"%lf, %lf, %lf", &x, &y, &z) == 3; i++){ 
     data[i][0] = x; 
     data[i][1] = y; 
     data[i][2] = z; 
    } 

    printf("First 5 unsorted numbers:\n"); 
    for(size_t j=0; j<5; j++){ 
     printf("Line %zu: %.3lf, %.3lf, %.3lf\n", j, data[j][0], data[j][0], data[j][0]); 
    } 
    puts("Last 5 unsorted numbers:"); 

    for(size_t j=ROWS-5; j<ROWS; j++){ 
     printf("Line %zu: %.3lf, %.3lf, %.3lf\n", j, data[j][0], data[j][0], data[j][0]); 
    } 

    /* Sort array using Quicksort algorithm: */ 
    puts("Sorting..."); 
    qsort(data, ROWS, sizeof *data, compare); 

    puts("First 10 sorted numbers:"); 
    for(size_t j=0;j<10;j++){ 
     printf("Line %zu: %.3lf, %.3lf, %.3lf\n", j, data[j][0], data[j][0], data[j][0]); 
    } 

    fclose(fp); 
    free(data); 

    return 0; 
} 

int compare(const void *arg1, const void *arg2) { 
    double (*x)[3] = arg1; 
    double (*y)[3] = arg2; 

    if ((*x)[0] > (*y)[0]) 
     return 1; 
    else if ((*x)[0] < (*y)[0]) 
     return -1; 
    else if ((*x)[1] > (*y)[1]) 
     return 1; 
    else if ((*x)[1] < (*y)[1]) 
     return -1; 
    else if ((*x)[2] > (*y)[2]) 
     return 1; 
    else if ((*x)[2] < (*y)[2]) 
     return -1; 
    else 
     return 0; 
} 

Answer 2

qsort期望排序的元素进入连续的内存块。如果所有的单元格都构成一个连续的内存块，并且可以解释为一维数组并与qsort一起使用，则仍然可以将数据保留在二维数组中。

不像您在Make2DDoubleArray中那样为每行分别分配内存，而是一次为所有行分配内存。然后，除了您现在返回的内容：指向行的指针数组;您还必须返回（使用逐个指针）包含所有行的内存块。

你的每一行

for (i = 0; i < arraySizeX; i++) 
    theArray[i] = (double*) malloc(arraySizeY*sizeof(double)); 

分配内存，而你可以在一个步骤

double *cells = malloc(sizeof(double) * arraySizeX * arraySizeY); 
if (cells == NULL) { ... } 
for (i = 0; i < arraySizeX; i++) 
    theArray[i] = &cells[arraySizeY * i]; 

然后分配内存，您将有两个数组：数组的指针到你行现在（在您的代码中称为theArray）;和一个新的一维数组，保持所有行（不是指向行的指针，而是指向数组的单元格）（ ，实际上，所有单元格都是 ，其中每行，一个三元组都是一个数据点），可以用于qsort（在我的代码为cells）。

然后，通过后者 - cells（而不是 data）以快速排序

qsort(cells, ROWS * COLS, sizeof(double), &compare); 

还要注意的是，在这个问题

qsort(data, ROWS, COLS*sizeof(double), &compare); 

在代码中调用是错误的，因为你没有排序数量为 ROWS的行，每行的大小为 COLS*sizeof(double)。

编辑：呃，我的道歉。我误解了你有一个二维条目数组，但现在我看到COLS代表了一个单元格的字段。在这种情况下，您最好使用@ SpacedMonkey的解决方案。 仅供参考，我的回答也将工作，那么你会打电话的qsort像你这样，但对细胞

qsort(cells, ROWS, COLS*sizeof(double), &compare); 

Answer 3

尝试使用结构的数据，而不是：

typedef struct { 
    double x; 
    double y; 
    double z; 
} point_data; 

然后你只需要这种新型的1个维数组：

point_data *array = malloc(linesRead * sizeof *array); 

和你比较功能仍然相当类似：

int compare(const void *arg1, const void *arg2) { 
    point_data *point1 = arg1, 
       *point2 = arg2; 

    if (point1->x > point2->x) { 
     return 1; 
    else if (point1->x < point2->x) { 
     return -1; 
    } else { 
     if (point1->y > point2->y) { 
      return 1; 
     else if (point1->y < point2->y) { 
      return -1; 
     } else { 
      if (point1->z > point2->z) { 
       return 1; 
      else if (point1->z < point2->z) { 
       return -1; 
      } else { 
       return 0; 
      } 
     } 
    } 
} 

而且，请不要硬编码点的数量，而不是指望你在阅读次数。