c - 按 C 中的第一列对动态分配的二维数组进行排序

Question

我有一个大型二维 double 组，我想按第一列排序。该数组需要动态内存分配，因为它很大 (2GB)。

下面是我使用随机数作为示例的损坏代码的简化示例。

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

int Double_Compare_Function ();

int main()
{
    srand(time(0));
    int p = 0; //property index
    int number_properties = 6; // number_properties
    long long n = 0; //node index
    long long number_nodes = 5; //number of nodes

    /* Declare array */
    double **properties_array;
    properties_array = malloc(number_nodes * sizeof(double*));
    for (n=0; n<number_nodes; n++) {
        properties_array[n] = malloc(number_properties * sizeof(double));
    }

    /* Fill array with numbers */
    for (n=0; n<number_nodes; n++) {
        for (p=0; p<number_properties; p++) {
            properties_array[n][p] = rand();
        }
    }

    printf("Initial array...\n");
    for (n=0; n<number_nodes; n++) {
        printf("%lli: ", n);
        for (p=0; p<number_properties; p++){
            printf("%.1f ", properties_array[n][p]);
        }
        printf("\n");
    }

    /* Sort array */
    qsort(properties_array, (int)number_nodes, number_properties*sizeof(double), Double_Compare_Function);

    printf("Sorted array...\n");
    for (n=0; n<number_nodes; n++) {
        printf("%lli: ", n);
        for (p=0; p<number_properties; p++){
            printf("%.1f ", properties_array[n][p]);
        }
        printf("\n");
    }

    return(0);
}

int Double_Compare_Function (const void * a, const void * b) {
    if (*(double*)a > *(double*)b) return 1;
    else if (*(double*)a < *(double*)b) return -1;
    else return 0;
}

输出

程序编译没有错误(随机数生成警告除外)。它似乎指向我不打算指向的内存。

Initial array...
0: 17189.0 13476.0 24803.0 23588.0 9169.0 13351.0
1: 20992.0 15638.0 23138.0 8580.0 32516.0 24064.0
2: 27139.0 23745.0 19237.0 19279.0 19262.0 25303.0
3: 19407.0 24529.0 23675.0 3102.0 23878.0 5831.0
4: 15299.0 3845.0 27278.0 17467.0 28106.0 6918.0
Sorted array...
0: 17189.0 13476.0 24803.0 23588.0 9169.0 13351.0
1: 19262.0 25303.0 13104405306123376000000000000000000000000.0 0.0 32516.0 24064.0
2: 27139.0 23745.0 1361751537953832600000000000000000000000000000000000000000000000000000.0 0.0 20992.0 15638.0
3: 19407.0 24529.0 23675.0 3102.0 23878.0 5831.0
4: 15299.0 3845.0 27278.0 17467.0 28106.0 6918.0

问题已回答。

Answer 1

您的问题是您不能qsort 一个由pointer-to-pointer 制成的对象作为数组，因为分配的地址在内存中不连续。相反，您需要声明和分配一个指向 double [number_properties] 数组的指针，并在一次调用中为节点和属性分配，以确保对象在内存中是连续的，例如

    /* Declare array */
    double (*properties_array)[6];
    properties_array = malloc(number_nodes * number_properties * sizeof(double));
    if (!properties_array) {
        perror ("malloc-properties_array");
        return 1;
    }

(注意:从技术上讲，这是一个 指向 double [number_properties] 的 VLA 的指针，除非使用整数常量来指定 number_properties -- 从您声明 number_properties 的方式看不清楚，但随后在代码中使用了整数常量。请注意，如果您选择在代码中使用 VLA，该功能是实现定义的功能从 C11 开始

现在你的qsort比较可以写成:

int Double_Compare_Function (const void * a, const void * b) {
    if (*(double * const *)a > *(double * const *)b) return 1;
    else if (*(double * const *)a < *(double * const *)b) return -1;
    else return 0;
}

示例使用/输出

$ ./bin/doublecmp
Initial array...
0: 2058999144.0 1013160096.0 499880968.0 1375376710.0 1398189150.0 579626176.0
1: 35952305.0 349854458.0 1000340925.0 1397136257.0 2028006902.0 877319625.0
2: 579560718.0 745830077.0 766399485.0 1052819099.0 1279742925.0 80594279.0
3: 390212763.0 603717917.0 1542566382.0 654797188.0 957950686.0 807072250.0
4: 1163825233.0 1748173998.0 261624942.0 152991913.0 269595164.0 2130895736.0
Sorted array...
0: 35952305.0 349854458.0 1000340925.0 1397136257.0 2028006902.0 877319625.0
1: 390212763.0 603717917.0 1542566382.0 654797188.0 957950686.0 807072250.0
2: 579560718.0 745830077.0 766399485.0 1052819099.0 1279742925.0 80594279.0
3: 1163825233.0 1748173998.0 261624942.0 152991913.0 269595164.0 2130895736.0
4: 2058999144.0 1013160096.0 499880968.0 1375376710.0 1398189150.0 579626176.0

速记比较函数

请注意，您还可以编写相同的双重比较函数作为条件结果的单个返回，例如

int Double_Compare_Function (const void * a, const void * b)
{
    return (*(double * const *)a > *(double * const *)b) -
           (*(double * const *)a < *(double * const *)b);
}