5

First, I defined a dynamic array with 2 columns and 10 row. The integer number is set to 10 here just for example.

int** array;
int number = 10;

array = malloc(number * sizeof(int*));

for (i = 0; i < number; i++)
    array[i] = malloc(2 * sizeof(int));

Then I try to use qsort() on it.

qsort( array, number, sizeof array[0], compare );

This is my compare function. It sorts by the integer values in the first column, then sorts by the second column while preserving the order in the first column. E.g. "0 2, 1 7, 0 1" will become "0 1, 0 2, 1 7".

int compare ( const void *pa, const void *pb ) {
    int (*a)[1] = pa;
    int (*b)[1] = pb;
    if ( (a[0][0] < b[0][0]) || (a[0][0] == b[0][0])&&(a[1][0] < b[1][0]) ) return -1;
    if ( (a[0][0] > b[0][0]) || (a[0][0] == b[0][0])&&(a[1][0] > b[1][0]) ) return +1;
    return 0;
}

Question

This worked with a static array. I know it doesn't work now because I have a dynamic array, which is an array of pointers.

How can I adapt this code to work with the dynamically created multi-dimensional array?

4

6 回答 6

14

示例代码

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

int compare ( const void *pa, const void *pb ) {
    const int *a = *(const int **)pa;
    const int *b = *(const int **)pb;
    if(a[0] == b[0])
        return a[1] - b[1];
    else
        return a[0] - b[0];
}
/*
#define NUMCMP(x,y) (((x) < (y)) ? -1 : ((x) > (y)) ? 1 : 0)

int compare ( const void *pa, const void *pb ) {
    const int (*a)[2] = *(const int (**)[2])pa;
    const int (*b)[2] = *(const int (**)[2])pb;
    int tmp;
    if((tmp=NUMCMP((*a)[0], (*b)[0]))==0)
        return NUMCMP((*a)[1], (*b)[1]);
    else
        return tmp;
}
*/    
int main(void){
    int **array;
    int number = 10;
    int i;

    array = malloc(number * sizeof(int*));
    for (i = 0; i < number; i++){
        array[i] = malloc(2 * sizeof(int));
        array[i][0] = rand()%20;
        array[i][1] = rand()%20;
    }
    for(i = 0;i < number;++i)
        printf("%2d, %2d\n", array[i][0], array[i][1]);

    printf("\n");

    qsort(array, number, sizeof array[0], compare);

    for(i = 0;i < number;++i)
        printf("%2d, %2d\n", array[i][0], array[i][1]);

    return 0;
}

什么 *(const int **)pa

数组 = {(int *), (int *), (int *), ... , (int *) }

qsort 需要每个元素的地址为元素（用于交换等。因为元素的大小和数量以及起始地址因为只有给定的信息）。

例如 &(int *), &(int *)

所以(int **)传递给函数比较。

调用compare(int **, int **) &(int*)在 argint**

比较函数原型是cmp(const void*, const void*)

cast(const int**)pa被强制转换为传递的原始指针。

*((const int **)pa)是取消引用原始元素指针（int*）

于 2013-06-19T22:49:30.513 回答
0

由于您现在有一个指针数组，因此比较函数的参数将是指向指针的指针。像这样使用它们：

int *const *a = pa;
int *const *b = pb;

现在你有a两个b指向你正在排序的数组的指针。每一个都指向排序函数要求您检查的单个元素。您可以使用*aand *bor访问这些元素a[0]，b[0]但永远不要使用a[1]or b[1]。如果 sort 函数要求您比较数组中的第一个元素 ( *a) 和数组中的第五个元素 ( *b)，a[1]并且b[1]是数组的第二个和第六个元素 - 与您应该进行的比较完全无关。

在第一级取消引用之后，您可以做任何您需要做的事情来检查被比较的元素。由于您的数组元素本身是指向数组（每个 2int个）的指针，因此ints 可以作为a[0][0] a[0][1] b[0][0] b[0][1]. 请注意，这是与您的相反的顺序a[1][0]and b[1][0]。

将它们写成(*a)[0]这样会提醒人们第一级间接是“单元素仅访问”指针。我不确定这是否会使整个事情变得更清楚。

于 2013-06-19T22:42:46.613 回答
0 
const int *a = *(const int **)pa;
const int *b = *(const int **)pb;

@BLUEPIXY，这是不正确的。正好

const int *a = pa;
const int *b = pb;

因为 pa 是 const void * (array[0]) 并且它很好地转换为 const int *

于 2021-01-29T17:59:40.763 回答
0 
const int (*a)[2] = *(const int (**)[2])pa;
const int (*b)[2] = *(const int (**)[2])pb;

@BLUEPIXY，这是不正确的。正好

const int (*a)[2] = (int(*)[])pa;
const int (*b)[2] = (int(*)[])pb;
于 2021-01-29T18:02:46.793 回答
0

我遇到了这个线程来寻找我的同上问题，最后我做了下面的事情。

static int compareMatrixElements(const void *p1, const void *p2)
{
    return ((*(int const *) p1) - (*(int const *) p2));
}

void sortMatrix(int** matrix, int r, int c)
{
    int sort_matrix[r][c];

    for(int i = 0; i < r; i++) {

        memcpy(sort_matrix[i], matrix[i], c * sizeof(int));
    }

    qsort(sort_matrix, r*c, sizeof(int), compareMatrixElements);

    for(int i = 0; i < r; i++) {

        memcpy(matrix[i], sort_matrix[i], c * sizeof(int));
    }
}

在我上面的代码中，我直接使用了 qsort API，可以在连续内存上使用这个 api 或任何其他排序算法，但是如果你有一个矩阵，其行是指向其列的内存的指针（就像在我的情况下以及在这个线程的问题中描述的）。因此，我将这样的矩阵复制到一个连续的内存中，在该连续内存上运行排序并将排序后的元素复制回矩阵。

上面的解决方案对我有用，我认为它可能对其他人有帮助，所以我发布了它，建议对此进行任何改进。

于 2017-03-05T21:07:54.890 回答
-1

对于这个静态数组，sizeof array[0] 将是“2 * sizeof(int)”。

int array[10][2];

对于这个指向指针的指针，sizeof array[0] 将是“sizeof(int*)”。sizeof array[0][0] 将是“sizeof(int)”，对于这个指向指针的指针。

int **array;

所以，首先你不能使用“qsort(array, number, sizeof array[0], compare);” 在指针对指针实现的情况下。

于 2013-06-19T23:18:55.690 回答