需要对指向结构的动态指针数组进行排序，其中可能包含 NULL 指针

Question

我正在尝试找出如何对指向结构的指针数组进行排序，其中可能包含空指针。但是我无法解决这个问题，并且在排序后总是崩溃。

我有两个结构，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);

    ...
}

Answer 1

谢谢大家！！！我终于能够根据您的答案创建排序。非常感谢 n.m 和 Jonathan Leffler。

排序看起来像这样...

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

Answer 2

比较函数获取待排序数组内部的指针。您应该首先从该数组中读取指针，然后测试 NULL.

如果两个指针都是 NULL，你应该 return 0 并且可能使空指针大于其他值。

这是比较函数的更正版本：

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

Answer 3

如果在比较函数内部检查传递的指针的有效性，则每次在排序时执行此函数时都会执行这些检查。任何指针都可以针对相同条件进行多次测试。

如果数组在排序之前是 "sanitized"，通过移动末尾的所有 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 指出的那样，您可以从比较函数中删除 NULL 检查并仅对有效指针进行排序。

需要对指向结构的动态指针数组进行排序，其中可能包含 NULL 指针

Need to sort dynamic array of pointers to structs with possible NULL pointers among them

c

struct

pointers

qsort