c++ - 有人可以告诉我这是如何在 main() 中实现的吗？（关于 void 指针的问题）

Question

我从 Algorithms in a nut shell 得到了下面的片段

void sortPointers (void **ar, int n,
int (*cmp)(const void *, const void *)) {

int j;

for (j = 1; j < n; j++) {
   int i = j-1;
   void *value = ar[j];
   while (i >= 0 && cmp (ar[i], value) > 0) {
   ar[i+1] = ar[i];
   i--;
}

ar[i+1] = value;
}
}

https://www.amazon.com/Algorithms-Nutshell-OReilly-George-Heineman/dp/059651624X

它们不提供 main() 的实现

sortPointers

所以我在弄清楚 **ar 做什么时遇到了一些问题

当我试图做一个测试代码

**arrPtr = x 

它返回您不能在 int * 上强制转换 void ** 的错误。

这让我感到惊讶，因为这本书清楚地表明你将一个数组输入到函数中。

int main()
{
    var x[3] = { 2 , 4 , 3};

    void **arrPtr = x[0];



    return 0;
}

还有一个附带问题。

void *value = ar[j]; 

这是不需要的步骤吗？CMP 函数能够将 ar[i] 作为参数，它不应该能够按原样采用 ar[j] 吗？

标签： c++c

Answer 1

在 C 语言中，我们有一个函数qsort，它是对数组进行排序的通用函数。它可以对所有类型的数组进行排序（例如 int 数组、double 数组甚至自定义结构数组）。它所需要的只是用户提供一个“比较”功能来比较两个元素。

sortPointers似乎几乎相同，只是它不对元素数组进行排序，而是对指向元素的指针数组进行排序。

据我所知，我的想法是像这样使用它：

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

int cmp(const void * a, const void * b)
{
    int* pa = (int*)a;
    int* pb = (int*)b;
    if (*pa > *pb) return 1;
    if (*pa < *pb) return -1;
    return 0;
}

void sortPointers (void **ar, int n,
                   int (*cmp)(const void *, const void *)) 
{
    int j;

    for (j = 1; j < n; j++) {
       int i = j-1;
       void *value = ar[j];
       while (i >= 0 && cmp (ar[i], value) > 0) {
           ar[i+1] = ar[i];
           i--;
        }

        ar[i+1] = value;
    }
}

void pp(int **ar, int n)
{
    for(int i=0; i<n; ++i) 
        printf("Address %p holds the value %p and points to %d, i.e. arr[%d] points to %d\n", (void*)(&ar[i]), (void*)ar[i], *ar[i], i, *ar[i]);
}

#define ELEM 3

int main(void)
{
    int* arr[3];
    for(int i=0; i<ELEM; ++i) arr[i] = malloc(sizeof(int));
    *arr[0] = 5;
    *arr[1] = 8;
    *arr[2] = 2;

    pp(arr, ELEM);
    sortPointers((void**)arr, ELEM, cmp);
    printf("------------------------\n");
    pp(arr, ELEM);

    for(int i=0; i<ELEM; ++i) free(arr[i]);

    return 0;
}

输出：

Address 0x7fff9a7d0270 holds the value 0xeeb010 and points to 5, i.e. arr[0] points to 5
Address 0x7fff9a7d0278 holds the value 0xeeb030 and points to 8, i.e. arr[1] points to 8
Address 0x7fff9a7d0280 holds the value 0xeeb050 and points to 2, i.e. arr[2] points to 2
------------------------
Address 0x7fff9a7d0270 holds the value 0xeeb050 and points to 2, i.e. arr[0] points to 2
Address 0x7fff9a7d0278 holds the value 0xeeb010 and points to 5, i.e. arr[1] points to 5
Address 0x7fff9a7d0280 holds the value 0xeeb030 and points to 8, i.e. arr[2] points to 8

但是，整个功能似乎是在浪费时间。标准qsort可以为你做到这一点，那么为什么要编写一个特殊的函数呢？如上所述，qsort可以对所有类型的数组进行排序，因此它也可以对指针数组进行排序。比较功能只需要有点不同。只需使用qsort如下：

// Compare function
int cmp_qsort(const void * a, const void * b)
{
    int** pa = (int**)a;
    int** pb = (int**)b;
    if (**pa > **pb) return 1;
    if (**pa < **pb) return -1;
    return 0;
}

// Call from main like:
qsort(arr, ELEM, sizeof(int*), cmp_qsort);

输出将是相同的（除了每次运行时都会更改的地址），并且您不需要像sortPointers.