qsort для массива структур

Я пытаюсь отсортировать структуру ниже, учитывая намерение отсортировать их частоту ошибок, сохраняя при этом информацию о sid и did. Хотя ошибки компиляции нет, я получаю ошибку сегмента во время выполнения. Интересно, что пошло не так....

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

struct linkdata {
    int sid;
    int did;
    double err;
};
typedef struct linkdata LD;
typedef int (*qsort_func_t)(const void *, const void *);

static int compareByErr (const void * a, const void * b)
{
    fprintf(stderr, "aerr=%.3f, berr=%.3f\n", (*(LD**)a)->err, (*(LD**)b)->err);
    int aerr = (*(LD**)a)->err;
    int berr = (*(LD**)b)->err;

    return aerr - berr;
}

int main() {

    int idx;
    int numnode;
    struct linkdata* perr;
    qsort_func_t qsort_func = compareByErr;

    numnode = 3;
    perr = (LD*) malloc (numnode*numnode*sizeof(LD));

    perr[0].sid = 0; perr[0].did = 1; perr[0].err = 0.642; 
    perr[1].sid = 0; perr[1].did = 2; perr[1].err = 0.236; 
    perr[2].sid = 0; perr[2].did = 3; perr[2].err = 0.946;
    idx = 3;

    qsort(perr, idx, sizeof(perr), compareByErr);

    int i;
    for (i=0; i<idx; i++){
       fprintf(stderr,"err[%d][%d] = %.3f\n", perr[i].sid, perr[i].did, perr[i].err);            
    }

    free(perr); 
}

c qsort
person twfx    schedule 06.09.2012    source источник

Ответы (3)


arrow_upward
2
arrow_downward

В коде много ошибок.

1. сравнить по ошибке

Параметры a и b функции compareByErr являются объектами LD*, а не LD**. Вы сделали ненужное разыменование. Попробуйте изменить эту функцию на:

static int compareByErr (const void * a, const void * b)
{
    fprintf(stderr, "aerr=%.3f, berr=%.3f\n", ((LD*)a)->err, ((LD*)b)->err);
    int aerr = ((LD*)a)->err;
    int berr = ((LD*)b)->err;

    return aerr - berr;
}

2. сравнить по ошибке

Есть еще одна проблема: вы неявно конвертируете double в int. Поскольку все эти «ошибки» равны 0.???, все они будут усечены до 0. Делая весь массив несортированным. Измените его на:

    double aerr = ((LD*)a)->err;
    double berr = ((LD*)b)->err;

    return aerr < berr ? -1 : aerr > berr ? 1 : 0;

3. маллок

Вы выделяете 32 узла, но нужны только 3. Измените это на

perr = (LD*) malloc (numnode * sizeof(LD));

4. сортировка

Третий аргумент — это размер каждого элемента массива, а не sizeof(perr), который представляет собой размер указателя (4 байта). Измените эту строку на:

qsort(perr, idx, sizeof(*perr), compareByErr);
//                      ^

чтобы получить размер элемента.

idx кажется ненужным. Вы можете просто использовать numnode здесь.

person kennytm    schedule 06.09.2012

arrow_upward
2
arrow_downward

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

Чего они не упомянули, так это того, что вы также используете неправильный sizeof для сортировки. Поскольку массив представляет собой массив структур, вы должны указать qsort, что размер члена равен размеру структуры. Изменить sizeof perr на sizeof *perr

Кроме того, преобразование чисел с плавающей запятой в целые перед их сравнением приводит к тому, что все они равны, потому что все они равны нулю...

person Alan Curry    schedule 06.09.2012

arrow_upward
1
arrow_downward

Вы неправильно обрабатываете аргументы обратного вызова вашего компаратора.

Этот:

fprintf(stderr, "aerr=%.3f, berr=%.3f\n", (*(LD**)a)->err, (*(LD**)b)->err);

должно быть:

{
  const LD *lda = a, *ldb = b;

  fprintf(stderr, "aerr=%.3f, berr=%.3f\n", lda->err, ldb->err);
  /* ... */
}

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

Далее это:

int aerr = (*(LD**)a)->err;
int berr = (*(LD**)b)->err;

return aerr - berr;

обожающе краток, но он может скрыть проблемы целочисленного переполнения, которые немного пугают. Я бы порекомендовал:

return (a->err < b->err) ? -1 : a->err > b->err;

Это использует явный литерал для генерации значения -1, полагаясь на сравнения, генерирующие 0 или 1 для двух других случаев.

person unwind    schedule 06.09.2012