3

假设我有这样的结构:

typedef struct MyStruct{
  char *string1;
  int number1, number2, number3;
  char string2[11], string3[9];
  char *string4;
  char *string5;
}MyStruct;

程序会提示用户选择应该按哪个字段对数据进行排序。我很难想出一种有效地对数组进行排序的方法。我真的需要为每个字段编写单独的排序函数吗?必须有其他方法,因为编写 8 个函数,其中 2 个就足够了,看起来并不合理。

4

5 回答 5

6

qsort()从 向上看<stdlib.h>。它需要一个比较器功能。您可以为不同的排序顺序编写单独的比较器函数,但仍使用标准库qsort()进行排序。

例如:

int ms_cmp_string1(const void *vp1, const void *vp2)
{
    const MyStruct *ms1 = vp1;
    const MyStruct *ms2 = vp2;

    int cmp = strcmp(ms1->string1, ms1->string2);
    if (cmp != 0)
        return cmp;
    else if (ms1->number1 < ms2->number1)
        return -1;
    else if (ms1->number1 > ms2->number1)
        return +1;
    //...other comparisons as required...
    else
        return 0;
}

这是比较器的一个不错的大纲。这一个排序string1,然后按number1。您可以编写按不同字段排序的变体,也可以设计一个方案,按照您选择的顺序应用各种可能的测试。但是基本轮廓效果很好,适合在qsort()没有任何强制转换的情况下传递。

于 2013-06-05T07:04:26.460 回答
3

如果只需要 2 个函数,则不需要编写 8 个函数。构建您自己的 qsort 函数并将包含成员偏移量的最后一个参数发送到比较函数,然后在您的比较函数中,将指针 + 偏移量转换为正确的类型。

就像是:

int comp_int(const void *pa, const void *pb, size_t offset)
{
    const int *a = (const int *)((const char *)pa + offset);
    const int *b = (const int *)((const char *)pb + offset);

    return *a - *b;
}

int comp_string(const void *pa, const void *pb, size_t offset)
{
    const char *a = (const char *)pa + offset;
    const char *b = (const char *)pb + offset;

    return strcmp(a, b);
}

void swap(void *v[], int a, int b)
{
    void *temp;

    temp = v[a];
    v[a] = v[b];
    v[b] = temp;
}

void sort(void *v[], int left, int right, size_t offset, int (*comp)(const void *, const void *, size_t))
{
    int i, last;

    if (left >= right) return;
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left + 1; i <= right; i++) {
        if ((*comp)(v[i], v[left], offset) < 0)
            swap(v, ++last, i);
    }
    swap(v, left, last);
    sort(v, left, last - 1, offset, comp);
    sort(v, last + 1, right, offset, comp);
}

offsetof可以提供帮助

于 2013-06-05T07:12:23.253 回答
1

如果您使用的是 GNU C 库,则有一个名为 qsort_r() 的扩展,可让您将额外参数传递给比较函数。

于 2013-06-05T15:20:14.357 回答
1

使用一些宏:

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

struct data {
    int x, y, z;
};

#define comp(member) comp_##member
#define comp_build(member)                          \
int comp_##member(const void *pa, const void *pb)   \
{                                                   \
    const struct data *a = pa, *b = pb;             \
    return (a->member < b->member)  ? -1 : (a->member > b->member); \
}

comp_build(x)
comp_build(y)
comp_build(z)

int main(void)
{
    #define ROWS 3

    struct data v[] = {
        {3, 2, 1},
        {1, 3, 2},
        {2, 1, 3}
    };
    int i;

    puts("Unsorted");
    for (i = 0; i < ROWS; i++) printf("%d %d %d\n", v[i].x, v[i].y, v[i].z);
    qsort(v, ROWS, sizeof(struct data), comp(x));
    puts("Sorted by x");
    for (i = 0; i < ROWS; i++) printf("%d %d %d\n", v[i].x, v[i].y, v[i].z);
    puts("Sorted by y");
    qsort(v, ROWS, sizeof(struct data), comp(y));
    for (i = 0; i < ROWS; i++) printf("%d %d %d\n", v[i].x, v[i].y, v[i].z);
    puts("Sorted by z");
    qsort(v, ROWS, sizeof(struct data), comp(z));
    for (i = 0; i < ROWS; i++) printf("%d %d %d\n", v[i].x, v[i].y, v[i].z);

    return 0;
}
于 2013-06-05T12:42:55.730 回答
1

这是我的另一个答案中使用 qsort 的示例:

struct stringcase { char* string; void (*func)(void); };

void funcB1();
void funcAzA();

struct stringcase cases [] = 
{ { "B1", funcB1 }
, { "AzA", funcAzA }
};

struct stringcase work_cases* = NULL;
int work_cases_cnt = 0;

// comparator function
int stringcase_cmp( const void *p1, const void *p2 )
{
  return strcasecmp( ((struct stringcase*)p1)->string, ((struct stringcase*)p2)->string);
}

// prepare the data for searching
void prepare() {
  // allocate the work_cases and copy cases values from it to work_cases
  qsort( cases, i, sizeof( struct stringcase ), stringcase_cmp );
}
于 2013-06-05T07:09:23.953 回答