多态中如何使用函数指针？

Question

我希望能够使用多态性中的函数指针对数组进行排序。更不用说，我这样做只是为了看看事情是如何运作的等等。

Answer 1

这是一个简单的通用排序接口，通过该接口实现的插入排序，以及一些演示其用法的测试代码：

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

struct sort_interface {
    // number of elements
    size_t nmemb;

    // passed through to 'arg' of compare() and swap()
    void *arg;

    // compares elements at 'i' and 'j'
    int (*compare)(void *arg, size_t i, size_t j);

    // swaps elements at 'i' and 'j'
    void (*swap)(void *arg, size_t i, size_t j);
};

static void insertion_sort (struct sort_interface iface)
{
    for (size_t i = 0; i < iface.nmemb; i++) {
        size_t j = i;
        while (j > 0) {
            if (iface.compare(iface.arg, j - 1, j) <= 0) {
                break;
            }
            iface.swap(iface.arg, j - 1, j);
            j--;
        }
    }
}

static int func_comparator (void *arg, size_t i, size_t j)
{
    int *arr = arg;

    if (arr[i] < arr[j]) {
        return -1;
    }
    if (arr[i] > arr[j]) {
        return 1;
    }
    return 0;
}

static void func_swap (void *arg, size_t i, size_t j)
{
    int *arr = arg;

    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int main (int argc, char *argv[])
{
    int arr[] = {7, 6, 8, 2, 9, 1, 156, 1, 62, 1671, 15};
    size_t count = sizeof(arr) / sizeof(arr[0]);

    struct sort_interface iface;
    iface.nmemb = count;
    iface.arg = arr;
    iface.compare = func_comparator;
    iface.swap = func_swap;

    insertion_sort(iface);

    for (size_t i = 0; i < count; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

您可能还想看看 C 标准库的 qsort() 函数，它也使用函数指针比较器，但与上面相比有些限制。特别是，它假设您正在对连续数组进行排序，并且如果您有指向元素或其成员的指针，那么这些指针将被破坏（但上面的接口允许您修复 swap() 中的指针）。

下面是如何使用 qsort() 接口的示例，以及使用与 qsort() 相同接口的插入排序实现：

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

static void insertion_sort (void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))
{
    char temp[size];

    for (size_t i = 0; i < nmemb; i++) {
        size_t j = i;
        while (j > 0) {
            char *x = (char *)base + (j - 1) * size;
            char *y = (char *)base + j * size;
            if (compar(x, y) <= 0) {
                break;
            }
            memcpy(temp, x, size);
            memcpy(x, y, size);
            memcpy(y, temp, size);
            j--;
        }
    }
}

static int int_comparator (const void *ve1, const void *ve2)
{
    const int *e1 = ve1;
    const int *e2 = ve2;

    if (*e1 < *e2) {
        return -1;
    }
    if (*e1 > *e2) {
        return 1;
    }
    return 0;
}

int main (int argc, char *argv[])
{
    int arr[] = {7, 6, 8, 2, 9, 1, 156, 1, 62, 1671, 15};
    size_t count = sizeof(arr) / sizeof(arr[0]);

    qsort(arr, count, sizeof(arr[0]), int_comparator); // or insertion_sort()

    for (size_t i = 0; i < count; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}