C - 使用通用函数将多个数组作为一个数组排序

Question

我需要使用通过省略号获取参数的通用函数对多个数组进行排序。

我尝试将所有元素放在一个数组中，对其进行排序，然后将结果推送到以下数组中。

这是函数的原型(prototype):

void gSortAll(int n, int m, int(*cmp)(void*,void*),void* base,...);

int n:每个数组中元素的个数。

int m:数组中每个元素的字节大小。

cmp:比较函数，用于比较特定类型。

void* base:第一个要排序的数组，后面是带省略号的其他数组，然后是 NULL。

假设我用这些数组调用函数:

int a[] = {17,2,7,8,1};
int b[] = {3,6,5,14,11};
int c[] = {12,9,10,1,4};

排序函数之后的数组应该是:

int a[] = {1,1,2,3,4};
int b[] = {5,6,7,8,9};
int c[] = {10,11,12,14,17};

我已经开始输入函数了:

int cmpInt(void *a, void *b) {
    return *(int*)a > *(int*)b;
}

void swap(void* p, void* q, int size) { 
    char *pt = (char *)p;
    char *qt = (char *)q;
    char c;
    while(size--) {
        c = *pt;
        *pt = *qt;
        *qt = c;
        pt++;
        qt++;
    }
}

void insert(void* from, void* to, int size) { 
    char *pt = (char *)from;
    char *qt = (char *)to;
    while(size--) {
        *qt = *pt;
        pt++;
        qt++;
    }
}

void sort(void* arr, int size, int sizeType, int(*f)(void *, void *)) {
    int i,j;
    for (i=0; i<size; i++) {
        for (j=0; j<size-1; j++) {
            if(f((char*)arr+j*sizeType,(char*)arr+j*sizeType+sizeType)>0) {
                swap((char*)arr+j*sizeType,(char*)arr+j*sizeType+sizeType, sizeType);
            }
        }
    }
}

// n: number of elements in array
// m: size in bytes of element
// cmp: compare function
// base: the first array
void gSortAll(int n, int m, int(*cmp)(void*,void*),void* base,...) {
    void** arr = malloc(0);
    int count = 0;
    int i;
    void* item;
    va_list param;
    va_start(param, base);
    for(i=0;i<n;i++) {
        arr = realloc(arr, m*(count+1));
        arr[count] = (char*)base+i*m;
        count++;
    }
    va_start(param, base);
    while((item=va_arg(param, void*))!=NULL) {
        for(i=0;i<n;i++) {
            arr = realloc(arr, m*(count+1));
            arr[count] = (char*)item+i*m;
            count++;
        }
    }
    va_end(param);
    sort(arr, count, m, cmp);
    va_start(param, base);
    for(i=0;i<n;i++) insert(arr+i*m, base+i*m, m);
    va_start(param, base);
    while((item=va_arg(param, void*))!=NULL) {
        for(i=0;i<n;i++) insert(arr+i*m, item+i*m, m);
    }
    va_end(param);
}

int main() {
    int a[] = {17,2,7,8,1};
    int b[] = {3,6,5,14,11};
    int c[] = {12,9,10,1,4};
    gSortAll(sizeof(a)/sizeof(a[0]), sizeof(a[0]), *cmpInt, a, b, c, NULL);
    return 0;
}

任何帮助将不胜感激!

Answer 1

逐字使用您的 sort 代码(以及一些但不是所有的支持函数)，这是 gSortAll() 的变体，其签名略有不同。它避免了显式的 void *base 参数，因此不必对其进行特殊处理。

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

static void sort(void *arr, int size, int sizeType, int (*f)(void *, void *));

/* Changed (simplified) function signature */
static void gSortAll(int n, int m, int (*cmp)(void *, void *), ...)
{
    void *item;
    va_list param;

    /* How many arrays? */
    va_start(param, cmp);
    size_t num_arrays = 0;
    while ((item = va_arg(param, void *)) != 0)
        num_arrays++;
    va_end(param);

    if (num_arrays == 0)
        return;

    void *arr = malloc(num_arrays * n * m);
    if (arr == 0)
        return;

    /* Copy data into allocated array */
    va_start(param, cmp);
    void *data = arr;
    while ((item = va_arg(param, void *)) != 0)
    {
        memmove(data, item, n * m);
        data = (char *)data + n * m;
    }
    va_end(param);

    sort(arr, n * num_arrays, m, cmp);

    /* Copy data from allocated array */
    va_start(param, cmp);
    data = arr;
    while ((item = va_arg(param, void *)))
    {
        memmove(item, data, n * m);
        data = (char *)data + n * m;
    }
    va_end(param);

    free(arr);
}

static int cmpInt(void *a, void *b)
{
    return *(int *)a > *(int *)b;
}

static void swap(void *p, void *q, int size)
{
    char *pt = (char *)p;
    char *qt = (char *)q;
    char c;
    while (size--)
    {
        c = *pt;
        *pt = *qt;
        *qt = c;
        pt++;
        qt++;
    }
}

static void sort(void *arr, int size, int sizeType, int (*f)(void *, void *))
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {
            if (f((char *)arr + j * sizeType, (char *)arr + j * sizeType + sizeType) > 0)
            {
                swap((char *)arr + j * sizeType, (char *)arr + j * sizeType + sizeType,
                     sizeType);
            }
        }
    }
}

/* Non-generic code */
static void dump_array(const char *tag, size_t size, int data[size])
{
    printf("%s (%zu):  ", tag, size);
    for (size_t i = 0; i < size; i++)
        printf("%5d", data[i]);
    putchar('\n');
}

int main(void)
{
    int a[] = {17, 2, 7, 8, 1};
    int b[] = {3, 6, 5, 14, 11};
    int c[] = {12, 9, 10, 1, 4};

    printf("Before\n");
    dump_array("A", 5, a);
    dump_array("B", 5, b);
    dump_array("C", 5, c);

    gSortAll(sizeof(a) / sizeof(a[0]), sizeof(a[0]), *cmpInt,
             (void *)a, (void *)b, (void *)c, (void *)NULL);

    printf("After\n");
    dump_array("A", 5, a);
    dump_array("B", 5, b);
    dump_array("C", 5, c);

    /* random -n 12 10 99 | commalist -B 4 -w -W3 -n 12 -b 'int w[] = { ' -T ' };' */
    int w[] = {  86,  86,  48,  40,  39,  29,  69,  71,  30,  15,  46,  19, };
    int x[] = {  21,  43,  11,  85,  82,  81,  41,  46,  33,  32,  15,  43, };
    int y[] = {  91,  19,  82,  33,  25,  83,  36,  85,  75,  65,  37,  57, };
    int z[] = {  39,  61,  65,  83,  26,  82,  30,  81,  30,  34,  22,  82, };

    printf("Before\n");
    dump_array("W", 12, w);
    dump_array("X", 12, x);
    dump_array("Y", 12, y);
    dump_array("Z", 12, z);

    gSortAll(sizeof(w) / sizeof(w[0]), sizeof(w[0]), *cmpInt,
             (void *)w, (void *)x, (void *)y, (void *)z, (void *)NULL);

    printf("After\n");
    dump_array("W", 12, w);
    dump_array("X", 12, x);
    dump_array("Y", 12, y);
    dump_array("Z", 12, z);

    return 0;
}

它使用 memmove() — 如果您愿意，可以使用 memcpy() — 将单独的数组复制到它创建的单个数组中，并复制排序后的数组数据返回到单独的数组。

示例输出:

Before
A (5):     17    2    7    8    1
B (5):      3    6    5   14   11
C (5):     12    9   10    1    4
After
A (5):      1    1    2    3    4
B (5):      5    6    7    8    9
C (5):     10   11   12   14   17
Before
W (12):     86   86   48   40   39   29   69   71   30   15   46   19
X (12):     21   43   11   85   82   81   41   46   33   32   15   43
Y (12):     91   19   82   33   25   83   36   85   75   65   37   57
Z (12):     39   61   65   83   26   82   30   81   30   34   22   82
After
W (12):     11   15   15   19   19   21   22   25   26   29   30   30
X (12):     30   32   33   33   34   36   37   39   39   40   41   43
Y (12):     43   46   46   48   57   61   65   65   69   71   75   81
Z (12):     81   82   82   82   82   83   83   85   85   86   86   91

在 Valgrind 的健康状况良好的情况下运行。

如果你绝对必须有 void *base 参数，那么你必须在代码中单独处理它，这很愚蠢，因为命名参数不会为函数的用户提供任何好处并且强加一些实现成本。

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

static void sort(void *arr, int size, int sizeType, int (*f)(void *, void *));

/* Changed (simplified) function signature */
static void gSortAll(int n, int m, int (*cmp)(void *, void *), void *base, ...)
{
    void *item;
    va_list param;

    if (base == 0)
        return;

    /* How many arrays? */
    va_start(param, base);
    size_t num_arrays = 1;      // base is counted too
    while ((item = va_arg(param, void *)) != 0)
        num_arrays++;
    va_end(param);

    void *arr = malloc(num_arrays * n * m);
    if (arr == 0)
        return;

    /* Copy data into allocated array */
    void *data = arr;
    memmove(data, base, n * m);
    data = (char *)data + n * m;
    va_start(param, base);
    while ((item = va_arg(param, void *)) != 0)
    {
        memmove(data, item, n * m);
        data = (char *)data + n * m;
    }
    va_end(param);

    sort(arr, n * num_arrays, m, cmp);

    /* Copy data from allocated array */
    data = arr;
    memmove(base, data, n * m);
    data = (char *)data + n * m;
    va_start(param, base);
    while ((item = va_arg(param, void *)))
    {
        memmove(item, data, n * m);
        data = (char *)data + n * m;
    }
    va_end(param);

    free(arr);
}

static int cmpInt(void *a, void *b)
{
    return *(int *)a > *(int *)b;
}

static void swap(void *p, void *q, int size)
{
    char *pt = (char *)p;
    char *qt = (char *)q;
    char c;
    while (size--)
    {
        c = *pt;
        *pt = *qt;
        *qt = c;
        pt++;
        qt++;
    }
}

static void sort(void *arr, int size, int sizeType, int (*f)(void *, void *))
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {
            if (f((char *)arr + j * sizeType, (char *)arr + j * sizeType + sizeType) > 0)
            {
                swap((char *)arr + j * sizeType, (char *)arr + j * sizeType + sizeType,
                     sizeType);
            }
        }
    }
}

/* Non-generic code */
static void dump_array(const char *tag, size_t size, int data[size])
{
    printf("%s (%zu):  ", tag, size);
    for (size_t i = 0; i < size; i++)
        printf("%5d", data[i]);
    putchar('\n');
}

int main(void)
{
    int a[] = {17, 2, 7, 8, 1};
    int b[] = {3, 6, 5, 14, 11};
    int c[] = {12, 9, 10, 1, 4};

    printf("Before\n");
    dump_array("A", 5, a);
    dump_array("B", 5, b);
    dump_array("C", 5, c);

    gSortAll(sizeof(a) / sizeof(a[0]), sizeof(a[0]), *cmpInt,
             (void *)a, (void *)b, (void *)c, (void *)NULL);

    printf("After\n");
    dump_array("A", 5, a);
    dump_array("B", 5, b);
    dump_array("C", 5, c);

    /* random -n 12 10 99 | commalist -B 4 -w -W3 -n 12 -b 'int w[] = { ' -T ' };' */
    int w[] = {  86,  86,  48,  40,  39,  29,  69,  71,  30,  15,  46,  19, };
    int x[] = {  21,  43,  11,  85,  82,  81,  41,  46,  33,  32,  15,  43, };
    int y[] = {  91,  19,  82,  33,  25,  83,  36,  85,  75,  65,  37,  57, };
    int z[] = {  39,  61,  65,  83,  26,  82,  30,  81,  30,  34,  22,  82, };

    printf("Before\n");
    dump_array("W", 12, w);
    dump_array("X", 12, x);
    dump_array("Y", 12, y);
    dump_array("Z", 12, z);

    gSortAll(sizeof(w) / sizeof(w[0]), sizeof(w[0]), *cmpInt,
             (void *)w, (void *)x, (void *)y, (void *)z, (void *)NULL);

    printf("After\n");
    dump_array("W", 12, w);
    dump_array("X", 12, x);
    dump_array("Y", 12, y);
    dump_array("Z", 12, z);

    return 0;
}

此输出与之前相同。

^{有一个 previous version of this question (仅限 10K 用户)最终被混淆和删除(但它是由不同的用户 ID 提交的)。这是我为那个问题写的两个答案之一的扩展——两个是必要的，因为混淆。}