C - Сортировать несколько массивов как один с универсальной функцией - PullRequest
Новая
       1

C - Сортировать несколько массивов как один с универсальной функцией

0 голосов
/ 25 июня 2018

Мне нужно отсортировать несколько массивов как один с помощью универсальной функции, которая получает параметры с помощью эллипсов.

Я попытался поместить все элементы в один массив, отсортировать его и затем поместить результаты в следующие массивы.

Это прототип функции: 

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

int n : количество элементов в каждом массиве.

intm : размер в байтах каждого элемента в массиве.

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

Любая помощь будет оценена!

Ответы [ 4 ]

0 голосов
/ 25 июня 2018

Это можно сделать, даже не вызывая * alloc функции.Вам нужно:

  • пользовательский контейнер, который может перебирать указанное количество массивов с указанным количеством элементов, где указатели на эти массивы хранятся в va_list «объекте».
  • пользовательская функция быстрой сортировки, которая будет использовать этот контейнер для доступа к элементам массива

Я написал контейнер arrs, который инициализируется числом массивов, количеством элементов в каждом массиве,размер элемента массива и указатель va_list на первый массив.
Затем я использовал некоторую функцию быстрой сортировки, которую я нашел в сети (использовал одну из здесь ), и переписывал ее, чтобы всякий раз, когда онавызывает arr[n] он вызывает мою функцию доступа к элементу контейнера.
Полный код здесь: 

#include <stdint.h>
#include <stdio.h>
#include <assert.h>
#include <stdarg.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stddef.h>

/* arrs_s --------------------------------------------------------- */

/**
 * arrs_s structure holds numOfArrays arrays each with numOfElemsInArrays of size size
 * starting in variable argument list va
 */
struct arrs_s {
    size_t numOfArrays;
    size_t numOfElemsInArrays;
    size_t membSize;
    va_list va;
};
/**
 * Intializes arrs_s object
 */
void arrs_init(struct arrs_s *t, size_t numOfArrays, size_t numOfElemsInArrays, size_t membSize, va_list va)
{
    assert(t != NULL);
    assert(membSize != 0);
#ifndef NDEBUG
    // assert all arrays in va_list are not NULL
    va_list va2;
    va_copy(va2, va);
    for (size_t i = numOfArrays; i; --i) {
        assert(va_arg(va2, void*) != NULL);
    }
    va_end(va2);
#endif

    t->numOfArrays = numOfArrays;
    t->numOfElemsInArrays = numOfElemsInArrays;
    t->membSize = membSize;
    va_copy(t->va, va);

}
/**
 * Bassically calls va_end
 */
void arrs_fini(struct arrs_s *t)
{
    va_end(t->va);
}
/**
 * Gets the pointer to element number pos
 */
void *arrs_get(struct arrs_s *t, size_t pos)
{
    assert(pos < t->numOfArrays * t->numOfElemsInArrays);
    size_t n = pos/t->numOfElemsInArrays;
    const size_t m = pos%t->numOfElemsInArrays;

    // get n element in a va list
    va_list va;
    va_copy(va, t->va);
    void *ret;
    while (n--) {
        ret = va_arg(va, void*);
    }
    ret = va_arg(va, void*);
    va_end(va);

    assert(ret != NULL);
    return (void*)(&((char*)ret)[t->membSize * m]);
}
/**
 * Get single element size, maybe should be refactored to arrs_membsize...
 */
size_t arrs_size(struct arrs_s *t)
{
    return t->membSize;
}

/* qsort --------------------------------------------------------- */

/**
 * Swap size bytes of memory between a and b
 */
static inline
void gSortAll_swap(void *a, void *b, size_t size)
{
#if 1 || C99_VLA
    char tmp[size];
    memcpy(tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, tmp, size);
#else
    char c;
    char *ca = a;
    char *cb = b;
    while (size--) {
        c = *ca;
        *ca++ = *cb;
        *cb++ = c;
    }
#endif
}

// rewritten from from https://beginnersbook.com/2015/02/quicksort-program-in-c/
static
void qSortAll_in(struct arrs_s *t, int (*cmp)(const void *, const void *),
            size_t first, size_t last)
{
   if (first < last){
      void * const pivot = arrs_get(t, first);
      size_t i = first;
      size_t j = last;

      while (i < j) {
          while (cmp(arrs_get(t, i), pivot) <= 0 && i < last) {
              ++i;
          }
          while (cmp(arrs_get(t, j), pivot) > 0) {
              j--;
          }
          if (i < j) {
              gSortAll_swap(arrs_get(t, i), arrs_get(t, j), arrs_size(t));
          }
      }
      gSortAll_swap(arrs_get(t, j), pivot, arrs_size(t));

      if (j > 0) {
          qSortAll_in(t, cmp, first, j - 1);
      }
      assert(j != SIZE_MAX);
      qSortAll_in(t, cmp, j + 1, last);
   }
}

void qSortAll(size_t numOfArrays, size_t numOfElemsInArrays,
        size_t size, int (*cmp)(const void*, const void *), /*void *base,*/ ...)
{
    assert(cmp != NULL);

    if (numOfArrays == 0 || numOfElemsInArrays == 0)
        return;

    va_list va;
    struct arrs_s t;

    va_start(va, cmp);
    arrs_init(&t, numOfArrays, numOfElemsInArrays, size, va);

    qSortAll_in(&t, cmp, 0, numOfArrays * numOfElemsInArrays - 1);

    arrs_fini(&t);
    va_end(va);
}

/* main -------------------------------------------------------------- */

void printarr(int *a, size_t s)
{
    printf(" %p[%zu] = ", a, s);
    while (s--) {
        printf("%d,", *a++);
    }
    printf("\n");
}

static int cmp(const void *a, const void *b)
{
    const int ia = *(int*)a;
    const int ib = *(int*)b;
    return ia == ib ? 0 : ia < ib ? -1 : 1;
}

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

#if 0 || TEST
    srand(time(NULL));
    for (size_t i = 0; i < sizeof(a)/sizeof(a[0]); ++i) {
        a[i] = rand()&0xff;
        b[i] = rand()&0xff;
        c[i] = rand()&0xff;
    }
#endif

    printf("Unsorted:\n");
    printarr(a, sizeof(a)/sizeof(a[0]));
    printarr(b, sizeof(b)/sizeof(b[0]));
    printarr(c, sizeof(c)/sizeof(c[0]));
    printf("\n");

    qSortAll(3, 5, sizeof(int), cmp, a, b, c);

    printf("Sorted:\n");
    printarr(a, sizeof(a)/sizeof(a[0]));
    printarr(b, sizeof(b)/sizeof(b[0]));
    printarr(c, sizeof(c)/sizeof(c[0]));
    printf("\n");

    return 0;
}

Пример вывода: 

Unsorted:
 0x1fff000360[5] = 17,2,7,8,1,
 0x1fff000380[5] = 3,6,5,14,11,
 0x1fff0003a0[5] = 12,9,10,1,4,

Sorted:
 0x1fff000360[5] = 1,1,2,3,4,
 0x1fff000380[5] = 5,6,7,8,9,
 0x1fff0003a0[5] = 10,11,12,14,17,
0 голосов
/ 25 июня 2018

Для каждого va_start().

должна быть пара va_end().

В вашей функции gSortAll() вы начинаете новый блок va_start(), прежде чем предыдущий был закончен с va_end(): 

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);
0 голосов
/ 25 июня 2018

Используя ваш код 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;
}

Вывод такой же, как и раньше.

Была предыдущая версия этого вопроса (только для 10K пользователей), котораяв конечном итоге он был сбит с толку и удален (но он был представлен другим идентификатором пользователя).Это продолжение одного из двух ответов, которые я написал на этот вопрос, два из которых необходимы из-за путаницы.

0 голосов
/ 25 июня 2018

Вы должны убедить себя, что каждый фрагмент вашего кода действительно необходим и делает то, для чего предназначен. Это также поможет разделить ваш код на несколько меньшие значимые примитивы, которые вы можете тестировать и отлаживать изолированно.

Советы:

  • возможно предварительно выделить временное пространство один раз
  • insert() может помочь с шагом сбора-копирования, точно так же, как это делает со скаттер-копией
  • есть библиотечные функции для выполнения работы для insert() и sort()
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...