0

我正在尝试使用 C 中的 qsort() 对二维数组进行排序。数组包含 3D 点数据，这些数据是使用 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
(...for 3,158,632 points)

我使用 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;
        }
    }
}

我想知道告诉 qsort 去“COLS * sizeof(double)”是否是错误的方法来处理我如何为 2D 数组分配内存？将这个问题视为一维数组是否会使其余部分工作？如果可能的话，我更愿意将其保留为二维数组。

4

3 回答 3

2

qsort期望排序的元素进入连续的内存块。您仍然可以将数据保存在 2D 数组中，如果您的所有单元构成可以解释为 1D 数组并与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

    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);
于 2013-04-22T23:56:40.997 回答
1

尝试使用结构来代替数据：

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

那么你只需要一个这种新类型的一维数组：

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;
            }
        }
    }
}

另外，请不要硬编码点数，而是计算您读入的数字。

于 2013-04-23T00:29:31.123 回答
1

这一切都不意味着没有像<stdio.h>,<stdlib.h>等标题的任何东西......

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

您的main. 因此fgetc，您的代码可能会丢失第一个值的最重要数字，这是一个微妙的错误。如果您想测试 EOF，请测试scanf（天哪！我没想到！我希望他们在手册中写了这些东西！呃，他们确实......）。文件末尾的示例比这更好，因为该示例确保三个值实际上由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;

...但是您的代码将它们作为整数进行比较，从而导致排序出现故障。的地址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;
}
于 2013-04-23T01:40:44.813 回答