c - Qsorting 二维指针数组

Question

我正在尝试使用 qsort 对二维指针数组进行排序。我现在唯一的问题是最初我使用的是静态声明的数组，现在切换到指针。我几乎很想切换到结构，但顽固地认为我无法让它工作。

到目前为止，我 malloc 了二维指针数组[array2d[m][3] 是预期的大小]:

     int **array2d;

     array2d = (int**)malloc((m)*sizeof(int*));

     for(i=0; i<=m; i++)
       array2d = [i]=(int*)malloc(3*sizeof(int));
     qsort(array2d, m, 3*sizeof(int**),comp);

我的比较是:

int comp(const void* left, const void*right)                                                                                  
{

  const int *a = *(const int**)left;
  const int *b = *(const int**)right;

  return a-b;
}

虽然我不确定如何构造比较以使用 2d 指针。

Answer 1

根据您提供的代码片段，我假设您正在尝试分别对矩阵的每一行进行排序。我注意到的第一件事是矩阵的列(第 2 个索引)的内存分配存在错字。

numRow x numColumns 矩阵的正确内存分配如下:

/* loop counter */
int i;

/* dynamic array sizes */
const int numRow = 5;
const int numColumns = 25;

/* allocate the row pointers */
int **dynamic2d = (int **)malloc(numRow * sizeof(int *));

/* for each row pointer */
for(i = 0; i < numRow; i++)
{
    /* allocate columns */
    dynamic2d[i] = (int *)malloc(numColumns * sizeof(int));
}

接下来，您将无法仅调用一次 qsort(..) 方法。该方法需要一个“平面”或一维数组。您需要为矩阵的每一行分别调用 qsort(...) 方法。如下所示:

/* sort array */
for(i = 0; i < numRow; i++)
    qsort(dynamic2d[i], numElements, sizeof(int *), comp);

最后，您的比较器方法有误。此方法具有严格的规则，需要遵守这些规则才能正常工作。当前 specifications说，“如果第一个参数被认为分别小于、等于或大于第二个参数，则应用程序应确保函数返回小于、等于或大于 0 的整数。如果两个成员比较同样，它们在排序数组中的顺序是未指定的。"

这是一个简单的修复。只需编写产生这些结果的逻辑，如下所示:

int comp(const void* firstArg, const void* secondArg)
{
   /* get the values of the arguments */
   int first = *(int *)firstArg;
   int second = *(int *)secondArg;

   /* return the value as expected by the qsort() method */
   if(first < second)
   {
      return 1;
   }
   else if(second < first)
   { 
     return -1;
   }

   return 0;
}

最后要注意的是，这将从大到小排序。 如果您想要从最小到最大，请不要在比较器中切换逻辑。排序不会返回准确的结果。正确的方法是从后向前读取数组，如下所示:您可以交换比较器中的参数以更改排序顺序或从后向前读取结果。

int comp(const void* firstArg, const void* secondArg)
{
    /* get the values of the arguments */
    int first = *(int *)secondArg;
    int second = *(int *)firstArg;
    ...
}

或

/* print greatest to smallest */
for(i = 0; i < numRow; i++)
{
    /* start at front and work to back */
    for(j = 0; j < numColumns; j++)
        printf("%d ", dynamic2d[i][j]);
    printf("\n");
}

/* print smallest to greatest */
for(i = 0; i < numRow; i++)
{
    /* start at back and work to front */
    for(j = numColumns- 1; j >= 0; j--)
        printf("%d ", dynamic2d[i][j]);
    printf("\n");
}

希望这对您有所帮助!如果您需要将整个矩阵作为一个整体进行排序……那完全是另一回事。