c - 将数组传递给函数时的双指针间接

Question

我想复习一下我的算法知识，我一直在使用以下书籍:Algorithms in a nutshell

在第 65 页，他们打印了一个插入排序算法。该算法非常简单易懂。我的问题来自他们实现它的方式。我主要使用托管语言 (C#/Java) 工作，所以我的指针功夫有点生疏。这是他们提供的代码示例:

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;
    }
}

这是我添加的一个工作示例:

int cmp(const void* t1, const void* t2) {
    if(t1 > t2) {
        return 1;
    }
    else if(t2 > t1) {
        return -1;
    }
    else {
        return 0;
    }
}

void main() {
    int values[] = { 51, 3, 5, 60, 9, 2, 7};

    sortPointers((void**)values, 7, cmp);

    for(int i = 0; i < 7; i++) {
        cout << values[i] <<  " ";
    }
}

虽然这有效，但我不完全理解为什么以及如何？另外，为什么 main 函数中的 (void **) 强制转换有效，为什么他们使用双指针间接寻址等？

回到学校时，我们唯一使用多重间接寻址的地方是在动态分配多维数组时。我所知道的唯一其他用途是，当您需要能够修改传递给方法的指针所在的地址时。

此外，我继续修改代码，使其看起来像这样，它工作得很好:

void sortPointers2(int* arr, int n, int (*cmp)(int, int)) {
    int j;
    for(j = 1; j < n; j++) {
        int i = j - 1;
        int value = arr[j];

        while(i >= 0 && cmp(arr[i], value) > 0) { 
            arr[i+1] = arr[i];
            i--;
        }

        arr[i+1] = value;
    }
}

int cmp2(int t1, int t2) {
    if(t1 > t2) {
        return 1;
    }
    else if(t2 > t1) {
        return -1;
    }
    else {
        return 0;
    }
}

void main() {
    int values[] = { 51, 3, 5, 60, 9, 2, 7};

    sortPointers2(values, 7, cmp2);

    for(int i = 0; i < 7; i++) {
        cout << values[i] <<  " ";
    }
}

我很确定我遗漏了一些基本和明显的东西。感谢您阅读本文并提出一两个想法。如果您需要任何其他详细信息，或者我弄乱了术语，请告诉我。

编辑:修复了第一个 cmp 函数中的拼写错误

Answer 1

如果我没看错的话，他们会使用 void ** 因为它实际上是 (void *)[];一组未类型化的内存。比较函数被赋予两个指向非类型化内存 (void *) 的指针，并被要求比较数据。

您不明白的是，在第一个示例中，您的数组应该是指针 数组，而不是值 数组。您的数组应如下所示:

int *val0 = malloc(sizeof(int)); *val0 = 51;
int *val1 = malloc(sizeof(int)); *val1 = 3;
// ... for all values
int *values[] = { val0, val1, val2, ... };

然后比较函数cmp 需要返回一个基于值 的比较值，而不是给定的指针。代码:

int cmp(const void* t1, const void* t2) {
    if((const int)(*t1) > (const int)(*t2)) {
        return 1;
    }
    else if((const int)(*t2) > (const int)(*t1)) {
        return -1;
    }
    else {
        return 0;
    }
}

这样，给定指向非类型化内存的指针，您的比较函数将在那些指针处找到两个整数，并比较这些值。

您的 cmp 函数与本书代码一起工作的唯一原因是因为您告诉排序函数您的数组充满了指向未类型化内存的指针，而实际上它只是一个整数数组。然后您的比较函数将获得指向内存的指针，这些指针实际上只是整数，然后比较指针就好像它们是值。在这种情况下，他们是。

本书的算法使用 void ** 的原因是因为那样它是通用的。 sort 函数可以获取一个包含任何数据的数组，并将通用数据提供给比较函数，该函数可以取消引用指针并根据需要解释这些地址处的数据。