如何使用本机qsort对C中的“int**”数组进行排序

Question

我一直找不到任何关于这个的问题，我想我想弄清楚这个有点疯狂。

我有以下代码：

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

int cmp_int(const void *a, const void *b)
{
  return * (int *)a - * (int *)b;
}

int main(int argc, char *argv[])
{
  int n = 10;
  int **arr = calloc(n, sizeof(int *));
  srand((unsigned int) time(NULL));
  for (int i = n-1; i >= 0; i--) {
    arr[i] = calloc(1, sizeof(int));
    *(arr[i]) = rand() % 1000;
  }
  for (int i = 0; i < n; i++)
    printf("%d ", *(arr[i]));
  printf("\n");
  qsort(arr, 10, sizeof(void *), cmp_int);
  for (int i = 0; i < n; i++)
    printf("%d ", *(arr[i]));
  printf("\n");
  free(arr);
  return 0;
}

这是超级基本的，对吧？根据手册页，第一个参数是指向基本元素的指针，第三个参数是大小。但是，我无法将数组作为排序结果。我仍然很困惑qort的第一个和第三个参数应该是什么，因为我怀疑这就是故障所在。

感谢您的帮助。

谢谢

编辑：我应该补充一点，这段代码显然没有错误检查，而且我试图使用双指针整数数组测试qort，所以虽然是的，但我可以使用一个不是这段代码预期目的的常规数组（它实际上是单独程序中更大段的一部分）。

Answer 1

您遇到的问题是未能考虑通过使用int**arr=calloc（n， sizeof*arr）为指针块分配创建的一个额外的间接级别；然后为单个int分配存储空间给带有arr[i]=calloc（1， sizeof*arr[i]）的每个指针。

由于qsort的int compare（const void*a，const void*b）compare函数需要一个指向被排序数组元素的指针，因此在需要在比较整数值之前取消引用两级间接引用的情况下，上面的a和b都将是指向int的指针。

而不是cmp_int，您实际上需要一个cmp_int_ptr比较函数。它可以写成：

int cmp_int_ptr (const void *a, const void *b)
{
    int *ai = *(int * const *)a,
        *bi = *(int * const *)b;

    return (*ai > *bi) - (*ai < *bi);
}

（注意：强制转换中的两个间接层次（int*const*）..也可以写成（int**），但要对应于参数类型（const void*），（int*const*）是合适的）

将其落实到位，为每个分配添加验证，并通过使用解引用指针本身来设置类型大小来清理您的calloc类型大小规范，您可以执行以下操作：

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

int cmp_int_ptr (const void *a, const void *b)
{
    int *ai = *(int * const *)a,
        *bi = *(int * const *)b;

    return (*ai > *bi) - (*ai < *bi);
}

int main (void) {

    int n = 10;
    int **arr = calloc (n, sizeof *arr);

    if (!arr) {
        perror ("calloc-arr");
        return 1;
    }

    srand((unsigned int) time(NULL));

    for (int i = 0; i < n; i++) {
        if (!(arr[i] = calloc (1, sizeof *arr[i]))) {
            perror ("calloc-arr[i]");
            return 1;
        }
        *(arr[i]) = rand() % 1000;
    }

    for (int i = 0; i < n; i++)
        printf (" %d", *(arr[i]));
    putchar ('\n');

    qsort (arr, 10, sizeof *arr, cmp_int_ptr);

    for (int i = 0; i < n; i++) {
        printf (" %d", *(arr[i]));
        free (arr[i]);              /* don't forget to free your int allocated */
    }
    putchar ('\n');

    free(arr);                      /* now free pointers */
}

示例使用/输出

$ ./bin/qsortptrtoint
 654 99 402 264 680 534 155 533 397 678
 99 155 264 397 402 533 534 654 678 680

仔细检查一下，如果有问题请告诉我。

Answer 2

你的节目让我头疼。没有得到正确排序的原因是比较函数错误。它需要是返回**（int**）a-**（int**）b 以获得正确的结果。

然而，这样解决问题是不值得的。至少列出一些问题：

• 如果不使用argc和argv，请不要声明它们
• 不需要在srand调用中强制转换
• 通过减法进行比较是个坏主意，因为它可能会溢出
• 应始终检查calloc返回的结果是否为空（内存不足）
• 根本不需要calloc。使用可变长度数组
• 不需要为int分配指针数组。只需分配一个int数组。那么你的比较就是这样
• qsort调用使用硬常数10，而不是n
• 通过解引用数组名称来指定元素大小的错误更少
• 最后释放“spine”数组，但从不释放整数元素
• 您应该分解出一个函数来打印数组

这是一个解决这些问题的版本。

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

int cmp_int(const void *va, const void *vb)
{
  int a = *(int *)va, b = *(int *) vb;
  return a < b ? -1 : a > b ? +1 : 0;
}

void print(int *a, int n) {
  for (int i = 0; i < n; ++i) printf("%d ", a[i]);
  printf("\n");
}

int main(void)
{
  int n = 10, a[n];
  srand(time(0));
  for (int i = 0; i < n; ++i) a[i] = rand() % 1000;
  print(a, n);
  qsort(a, n, sizeof a[0], cmp_int);
  print(a, n);
  return 0;
}