Сортировка массива указателей на структуры с помощью qsort

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

У меня есть эта структура:

struct access_data{
    int sector;
    int arrival_time;
    int checked;
    int processed;
};

Я создаю массив указателей access_data из файла таким образом, чтобы они были отсортированы по времени прибытия, но позже мне нужно отсортировать их по секторам, поэтому у меня есть следующее:

int compare_data(const void* a, const void* b){
    if (((access_data*)a)->sector < ((access_data*)b)->sector)
        return 1;
    else if (((access_data*)a)->sector > ((access_data*)b)->sector)
        return -1;
    else
        return 0;
}

void scan(access_data* data[], int len, int sec_to_sec_seek){
    qsort(data, len, sizeof(access_data*), &compare_data);

    show_data(data, len);
}

show_data просто печатает данные, но я получаю следующее на примере ввода; опять же, отсортированные уже по времени прибытия:

data[0]: arrival_time: 7, sector: 3
data[1]: arrival_time: 6, sector: 8
data[2]: arrival_time: 5, sector: 6
data[3]: arrival_time: 4, sector: 5
data[4]: arrival_time: 3, sector: 12
data[5]: arrival_time: 2, sector: 10
data[6]: arrival_time: 1, sector: 1
data[7]: arrival_time: 0, sector: 2

Просто сортировка не по секторам, а по обратному времени прихода. Я действительно в полной растерянности, что может быть причиной такого поведения.


c struct qsort
person wdonahoe    schedule 15.05.2014    source источник
comment
Опубликуйте минимальный тестовый пример.   -  person Oliver Charlesworth    schedule 16.05.2014

Ответы (3)


arrow_upward
22
arrow_downward

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

В этом случае вам не хватает уровня косвенности. Вы также изменили направление.

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

int compare_pointed_to_data(const void* a, const void* b) {
    // a is a pointer into the array of pointers
    struct access_data *ptr_to_left_struct = *(access_data**)a;
    struct access_data *ptr_to_right_struct = *(access_data**)b;

    if ( ptr_to_left_struct->sector < ptr_to_right_struct->sector)
        return -1;
    else if (ptr_to_left_struct->sector > ptr_to_right_struct->sector)
        return 1;
    else
        return 0;
}
person Avi Berger    schedule 15.05.2014
comment
Большое спасибо. Это исправило мою проблему. :-). Ах, это было больно. - person FernandoZ; 25.02.2017
comment
Это все исправило! - person murage kibicho; 24.07.2021

arrow_upward
1
arrow_downward

Ошибка 1

printf("size=%d",sizeof(access_data*));

печатает 4, ожидаемо: 16. Это была самая большая проблема: сортировка 8 раз по 4 байта, а не 8 раз по 16.

странность 2

qsort() ожидает указатель на данные, но scan() получает указатель на указатель на данные. Рекомендуемое исправление:

void scan(access_data data[], int len, int sec_to_sec_seek){
    qsort(data, len, sizeof(access_data), &compare_data);
    show_data(data, len);
}

Оптимизация 3

Ваше compare_data() равно

int compare_data(const void* a, const void* b){
    return ((access_data*)b)->sector - ((access_data*)a)->sector;
}

Моя полная рабочая программа:

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

struct access_data {
    int sector;
    int arrival_time;
    int checked;
    int processed;
};
typedef struct access_data access_data;
void show_data(access_data*data, int len) {
        printf("Showing size=%d",sizeof(access_data*));
        for(int i=0;i<len;i++) {printf("data[%d]: arrival_time: %d, sector: %d\n",i,data[i].arrival_time,data[i].sector);}
}

int compare_data(const void* a, const void* b){
        return ((access_data*)b)->sector - ((access_data*)a)->sector;
}
int compare_data1(const void* a, const void* b){
    if (((access_data*)a)->sector < ((access_data*)b)->sector)
        return 1;
    else if (((access_data*)a)->sector > ((access_data*)b)->sector)
        return -1;
    else
        return 0;
}

void scan(access_data data[], int len, int sec_to_sec_seek){
    qsort(data, len, sizeof(access_data), &compare_data);

    show_data(data, len);
}

int main() {
        printf("START\n");
        access_data data[8]={
                {3,4,5,6},
                {2,1,5,5},
                {1,1,3,6},
                {4,4,5,4},
                {5,4,3,4},
                {6,2,5,6},
                {7,2,5,4},
                {0,4,5,6}
        };
        scan(data,8,  0);
}
person MKaama    schedule 15.05.2014
comment
OP передает массив указателей на функцию scan(). Было бы неверно предполагать, что он может легко изменять части кода. - person this; 16.05.2014
comment
@self В тексте он говорит массив структур. Это то, что я написал. Мы не видим его кода. - person MKaama; 16.05.2014
comment
пустое сканирование (доступ_данные * данные [] - person this; 16.05.2014

arrow_upward
0
arrow_downward

Проблема здесь в том, что вы говорите QSort сортировать массив указателей, и в результате параметры в компараторе являются указателями на указатели.

int compare_data(const void* _a, const void* _b){
    access_data *a = *(access_data**)_a, *b = *(access_data**)_b;
    if ((a)->sector < (b)->sector)
        return 1;
    else if ((a)->sector > (b)->sector)
        return -1;
    else
        return 0;
}

void scan(access_data* data[], int len, int sec_to_sec_seek){
    qsort(data, len, sizeof(access_data*), &compare_data);

    show_data(data, len);
}

Дайте мне знать, если у вас остались вопросы

person ASKASK    schedule 15.05.2014