Необходимо отсортировать динамический массив указателей по структурам с возможными указателями NULL среди них - PullRequest
Новая
       66

Необходимо отсортировать динамический массив указателей по структурам с возможными указателями NULL среди них

0 голосов
/ 12 февраля 2019

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

У меня есть две структуры, CAR и CARLIST: CARLIST имеет массив указателей на CARS.И я просто не могу понять это правильно.

СПАСИБО за любую помощь ... 

typedef struct Car {
    int parked_Total_Minutes;
    char rz[10];
} CAR;

typedef struct CarList {
    CAR **p_cars;
    unsigned int count;
    unsigned int size;
} CARLIST;

int Compare_ParkedTime(const void *a, const void *b) {
     if (a == NULL)
          return -1;

     if (b == NULL)
          return 1;

     CAR *aa = *(CAR* const *)a;
     CAR *bb = *(CAR* const *)b;

     return  (bb->parked_Total_Minutes < aa->parked_Total_Minutes) - (aa->parked_Total_Minutes < bb->parked_Total_Minutes);
}

int main() {
    ....
    CARLIST *p_AllCars = (CARLIST *)malloc(sizeof(CARLIST));
    p_AllCars->count = 0;
    p_AllCars->size = 10;
    p_AllCars->p_cars = malloc(p_AllCars->size * sizeof(CAR *));

    for(int i = 0; i < p_AllCars->size; i++)
         p_AllCars->p_cars[i] = NULL;

    ... other logic generating cars ...

    qsort((void*)p_AllCars->p_cars, p_AllCars->size, sizeof(CAR*), Compare_ParkedTime);

    ...
}

Ответы [ 3 ]

0 голосов
/ 12 февраля 2019

Функция сравнения получает указатели внутри массива для сортировки.Сначала вы должны прочитать указатели из этого массива, а затем проверить на NULL.

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

Вот исправленная версия функции сравнения: 

int Compare_ParkedTime(const void *a, const void *b) {
    /* read the pointer values */
    CAR *aa = *(CAR * const *)a;
    CAR *bb = *(CAR * const *)b;

    /* sort NULL pointers to the end of the array */
    if (aa == NULL)
        return (bb != NULL);
    if (bb == NULL)
        return -1;

    /* sort by increasing value of parked_Total_Minutes. swap aa and bb for decreasing order */
    return (bb->parked_Total_Minutes < aa->parked_Total_Minutes) -
           (aa->parked_Total_Minutes < bb->parked_Total_Minutes);
}
0 голосов
/ 12 февраля 2019

Если достоверность переданных указателей проверяется внутри функции сравнения, эти проверки выполняются каждый раз, когда эта функция выполняется во время сортировки.Любой указатель может быть проверен несколько раз для одного и того же условия.

Если вместо этого массив «санирован» перед сортировкой, перемещая все значения NULL в конце: 

size_t remove_nulls(CAR **cars, size_t n)
{
    // Find the first NULL (thanks again, @chqrlie)
    size_t count = 0;
    while(count < n && cars[count])
    {
        ++count;
    }

    // Move the elements to 'fill' the blanks
    for (size_t i = count; i < n; ++i)
    {
        if ( cars[i] )
        {
            cars[count] = cars[i];
            ++count;
        }
    }

    // The last pointers must be overwritten
    for (size_t i = count; i < n; ++i)
        cars[i] = NULL;

    // Returns the number of valid pointers
    return count;
}

Затем, как chqrlie отметил, что вы можете удалить пустые проверки из функции сравнения и отсортировать только действительные указатели.

0 голосов
/ 12 февраля 2019

Спасибо вам ВСЕМ !!!Я наконец смог создать сортировку по вашим ответам.Большое спасибо НМ и Джонатану Леффлеру.

Сортировка выглядит так ... 

int Compare_ParkedTime( const void* a, const void* b ){
    CAR *aa = *(CAR* const *)a;
    CAR *bb = *(CAR* const *)b;


    if (aa == NULL && bb == NULL)return 0;
    if (aa == NULL)return 1;
    if (bb == NULL)return  -1;

    return  (aa->parked_Total_Minutes < bb->parked_Total_Minutes) - (bb->parked_Total_Minutes < aa->parked_Total_Minutes);
}
...