c - 如何对使用结构的指针数组进行排序？

Question

我想按 ID 对指针数组进行排序。但是 qsort 无法工作，因为我缺乏使用指针的经验。

typedef struct block{
    int Id;
    char * name;
} block;

typedef struct {
    block ** data;
    int size_array;
} database;

if( ( database = malloc(sizeof(database)) ) == NULL ) {
    printf("Error: malloc failed\n");
    exit(EXIT_FAILURE);
}

if( ( database->data = malloc( sizeof( block * ) * database->size_array ) ) == NULL ) {
    exit(EXIT_FAILURE);
}

for( i = 0; i < database->size_array; i++ ) {
    DB->data[i] = NULL;
}

我正在尝试使用 qsort 进行排序，但我显然做错了什么。

int compare(const void * a, const void * b ){
    const block * eval1 = a;
    const block * eval2 = b;

    if (eval1->Id < eval2->Id){
        return(-1);
    }

    else if (eval1->Id > eval2->Id)
        return 1;

    return 0;
}

调用代码:

    qsort(database->data, database->size_array, sizeof(int), compare);
    for(i = 0; i<DB->database->size_array; i++) {
        if(database->data[i] != NULL)
            printf("Id: %d\n", database->data[i]->Id);

    }

通过使用 for 循环，我发现排序失败了。

插入函数:

void insertE(int Id, char * name){
    block * item = malloc(sizeof(block));
    item->name = malloc(strlen(name)+1);
    strcpy(item->name, name);
    item->Id = Id;
}

当前输出:

Id: 13
Id: 243
Id: 121
Id: 87
.
.
.

Answer 1

当您使用qsort()(或bsearch() 或其他类似函数)时，传递给您的比较函数的指针属于“指向数组的指针”类型元素类型'。如果传递一个int的数组，比较函数传递的是int *(伪装成void *)。因此，如果您有一个 block * 数组，则传递给比较器的类型是一个 block **(伪装成 void *) .

因此你需要这样的东西(尽管也有其他的写法):

int compare(const void *a, const void *b)
{
    const block *eval1 = *(block **)a;
    const block *eval2 = *(block **)b;

    if (eval1->Id < eval2->Id)
        return(-1);
    else if (eval1->Id > eval2->Id)
        return 1;
    return 0;
}

但是，还有其他问题。您对 qsort 的调用是可疑的；数组元素的大小是sizeof(db->data[0])(假设db是database *类型的变量)，这也是 sizeof(block *)。通常，特别是在 64 位 Unix 和 Windows 系统上，sizeof(int) != sizeof(block *)。您可以在 sizeof(int) == sizeof(void *) 平台上使用 sizeof(int)，该类别包括大多数 32 位系统。因此，您还需要修复对 qsort() 的调用:

database *db = …initialization/allocation…;

qsort(db->data, db->size_array, sizeof(db->data[0]), compare);

MCVE

任何残留问题很可能与 block 指针数组的填充方式有关。这是一个 MCVE ( Minimal, Complete, Verifiable Example )，它显示了对 block 指针数组的排序。它假定您有可用的 C99 或 C11 编译器 — 它使用 C90 中没有的“复合文字”。

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

typedef struct block
{
    int Id;
    char *name;
} block;

typedef struct
{
    block **data;
    int size_array;
} database;

static int compare(const void *a, const void *b)
{
    const block *eval1 = *(block **)a;
    const block *eval2 = *(block **)b;

    if (eval1->Id < eval2->Id)
        return(-1);
    else if (eval1->Id > eval2->Id)
        return 1;
    return 0;
}

static void dump_blocks(const char *tag, int nblocks, block * *blocks)
{
    printf("%s:\n", tag);
    for (int i = 0; i < nblocks; i++)
        printf("Id: %3d - %s\n", blocks[i]->Id, blocks[i]->name);
    putchar('\n');
}

int main(void)
{
    block *b[] =
    {
        &(block){232, "RDQDLY"     },
        &(block){347, "XRZDMGJAZ"  },
        &(block){827, "QBYCVGQ"    },
        &(block){790, "VXSPDUX"    },
        &(block){245, "QRZEGGKAHD" },
        &(block){717, "YGKRPIGFM"  },
        &(block){691, "SREIUBHVS"  },
        &(block){754, "ZCFLESX"    },
        &(block){868, "WESFFWMJ"   },
        &(block){291, "QCSAGIHQJ"  },
    };
    database *db = &(database){ &b[0], sizeof(b) / sizeof(b[0]) };

    dump_blocks("Before sort", db->size_array, db->data);
    qsort(db->data, db->size_array, sizeof(db->data[0]), compare);
    dump_blocks("After sort", db->size_array, db->data);

    return 0;
}

dump_blocks() 函数遵循我发现非常有用的模式:该函数采用一个字符串标记，该标记首先被打印以标识正在转储的输出集，然后打印所有相关信息来自数据结构(如果合适，使用其他 dump_xxxxx() 函数)。然后可以在多个地方调用它。如果需要，我提供一个 FILE *fp 输出流作为第一个参数；这里似乎没有必要。它还可以在函数末尾使用 fflush(fp); 或 fflush(stdout); 或者 fflush(0); 来确保产生输出。这在调试崩溃的程序时很有帮助。请注意，输出以换行符终止，以帮助确保它们及时出现。

示例输出:

Before sort:
Id: 232 - RDQDLY
Id: 347 - XRZDMGJAZ
Id: 827 - QBYCVGQ
Id: 790 - VXSPDUX
Id: 245 - QRZEGGKAHD
Id: 717 - YGKRPIGFM
Id: 691 - SREIUBHVS
Id: 754 - ZCFLESX
Id: 868 - WESFFWMJ
Id: 291 - QCSAGIHQJ

After sort:
Id: 232 - RDQDLY
Id: 245 - QRZEGGKAHD
Id: 291 - QCSAGIHQJ
Id: 347 - XRZDMGJAZ
Id: 691 - SREIUBHVS
Id: 717 - YGKRPIGFM
Id: 754 - ZCFLESX
Id: 790 - VXSPDUX
Id: 827 - QBYCVGQ
Id: 868 - WESFFWMJ