1

我想复习我的算法知识，我一直在使用以下书：简而言之算法

在第 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] <<  " ";
    }
}

虽然这可行，但我不完全理解为什么以及如何？另外，为什么主函数中的 (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 函数中的错字

4

1 回答 1

2

如果我正确地遵循了这个例子，他们会使用 avoid **因为它真的是 a (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需要根据values返回一个比较值，而不是给出的指针。代码：

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是因为您告诉排序函数您的数组充满了指向无类型内存的指针，而实际上它只是一个整数数组。然后，您的比较函数将获得指向内存的指针，这些指针实际上只是整数，然后将指针作为值进行比较。在这种情况下，他们是。

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

于 2013-07-09T21:42:54.017 回答