如何对使用结构的指针数组进行排序? [英] How to qsort an array of pointers that use structs?

问题描述

我想按ID对指针数组进行排序.但是，由于我缺乏使用指针的经验，qsort无法正常工作.

I want to sort an array of pointers by Id's. However qsort fails to work because of my lack of experience with pointers.

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进行排序，但是我显然做错了.

I'm trying to sort using qsort, but I'm clearly doing something wrong.

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循环，我发现排序失败.

By using a for loop I see that the sorting failed.

插入功能:

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
.
.
.

推荐答案

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

When you use qsort() (or bsearch() or other similar functions), the pointers passed to your comparison function are of the type 'pointer to the array element type'. If you pass an array of int, the comparison function is passed int * (disguised as void *). Consequently, if you have an array of block *, the type passed to the comparator is a block ** (disguised as a void *).

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

Hence you need something like this (though there are other ways to write it too):

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 *)(包含大多数32位系统的类别)上的平台上使用sizeof(int).因此，您也需要将呼叫也固定为qsort()

However, there are other problems too. Your call to qsort is suspect; the size of the array elements is sizeof(db->data[0]) (assuming db is a variable of type database *), which is also sizeof(block *). In general, on 64-bit Unix and Windows systems in particular, sizeof(int) != sizeof(block *). You will get away with using sizeof(int) on platforms where sizeof(int) == sizeof(void *), a category which include most 32-bit systems. Therefore, you need to fix the call to qsort() too:

database *db = …initialization/allocation…;

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

MCVE

任何残留问题很可能与块指针数组的填充方式有关.这是一个MCVE(最小，完整，可验证的示例)，它显示了在块指针数组上进行的排序.假定您有可用的C99或C11编译器-它使用的不是C90中的复合文字".

MCVE

Any residual problems are most probably related to how the array of block pointers is populated. Here is an MCVE (Minimal, Complete, Verifiable Example) that shows the sort working on an array of block pointers. It assumes you have a C99 or C11 compiler available — it uses 'compound literals' which were not in 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);以确保产生输出.这在调试崩溃的程序时可能会有所帮助.请注意，输出以换行符终止，以帮助确保它们及时显示.

The dump_blocks() function follows a pattern I find very useful: the function takes a string tag that is printed first to identify which set of output is being dumped, and then prints all the relevant information from the data structure (using other dump_xxxxx() functions if appropriate). This can then be called in multiple places. If need be, I provide a FILE *fp output stream as a first argument; it didn't seem to be necessary here. It can also use fflush(fp); or fflush(stdout); or perhaps fflush(0); at the end of the function to ensure that the output is produced. This can help when debugging a program that's crashing. Note that the outputs are terminated with a newline to help ensure they appear in a timely manner.

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

这篇关于如何对使用结构的指针数组进行排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！