Как мне справиться с пустым указателем на массив для алгоритма сортировки? - PullRequest
Новая
       16

Как мне справиться с пустым указателем на массив для алгоритма сортировки?

0 голосов
/ 21 февраля 2020

Я пытаюсь сделать обобщенный c алгоритм быстрой сортировки в C, который принимает массив void в качестве входных данных. У меня вопрос, как мне справиться с индексацией в этом массиве. Ниже моя текущая попытка сделать это с моей функцией разделения. Мой код компилируется, но я знаю, что он не обращается к правильным указателям, и это приводит к ошибкам сегментации. 

static int partition(void *array, int left, int right, size_t elem_sz,
                  int (*comp) (const void*, const void*)) {
    // TODO
    void** arr = array;
    void* p = *(arr + left);
    int s = left;
    for (size_t i = left+1; i<=right; i++) {
      if ( (*comp)(*(arr + i), p) < 0 ) {
        s++;
        swap(*(arr + s), *(arr + i), elem_sz);
      }
    }
    swap(*(arr + left), *(arr + s), elem_sz);   
    return s;
}

Ответы [ 2 ]

2 голосов
/ 21 февраля 2020

Преобразование указателя вашего массива из void * в void ** не имеет смысла, так как у вас (скорее всего) нет массива void *.

Для правильной арифметики указателей c, вам нужно сначала преобразовать указатель в char *, поскольку вы не можете сделать арифметику указателя c на void *. Тогда, поскольку размер char равен 1, вам нужно умножить индекс на размер элемента, чтобы получить правильное смещение. 

static int lomuto(void *array, int left, int right, size_t elem_sz,
                  int (*comp) (const void*, const void*)) {
    char *arr = array;
    char *p = arr + left*elem_sz ;
    int s = left;
    for (size_t i = left+1; i<=right; i++) {
      if ( comp(arr + i*elem_sz, p) < 0 ) {
        s++;
        swap(arr + s*elem_sz, arr + i*elem_sz, elem_sz);
      }
    }
    swap(arr + left*elem_sz, arr + s*elem_sz, elem_sz);   
    return s;
}
0 голосов
/ 21 февраля 2020

Преобразуйте пустой указатель в указатель на символ, чтобы вы могли выполнить арифметику c над ним. char * используется потому, что char является наименьшим типом, а elem_sz будет кратно sizeof(char).

Вам не нужно разыменовывать указатели при вызове comp и swap, просто передавайте вычисленные указатели.

Все индексы и приращения необходимо умножить на elem_sz . 

static int lomuto(void *array, int left, int right, size_t elem_sz,
                  int (*comp) (const void*, const void*)) {
    char *arr = array;
    void *p = arr + left*elem_sz;
    int s = left*elem_size;
    for (size_t i = left+elem_size; i<=right*elem_size; i += elem_size) {
        if (comp(arr + i, p) < 0) {
            s++;
            swap(arr + s, arr + i, elem_sz);
        }
    }
    swap(arr + left, arr + s, elem_sz);   
    return s;
}

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

...