使用归并排序对结构体数组进行排序

Question

我有一个名为product的结构和一个产品数组。

我正在尝试使用归并排序按产品价格对数组进行排序，但问题是我的代码没有交换任何内容，我不明白为什么。如果有人能帮助我，我会非常感激。

结构：

typedef struct product {
    int ident;      /* idp of a product */
    char desc[64];  /* string that describes a product eg. "bread" */
    int price;      /* price of the product */
    int weight;     /* weight of the product eg. 2kg */
    int quant;      /* quantity of the product in stock */
    int state_prod; /* state of a product, if 1 it is in the system else is 0 and is not in the sistem */
} product;

归并排序算法

void mergesort_price(product a[], int left, int right) {
    int m = (right + left) / 2;
    if (right <= left)
      return;
    mergesort_price(a, left, m);
    mergesort_price(a, m + 1, right);
    merge_price(a, left, m, right);
}

void merge_price(product a[], int left, int m, int right) { 
    int i, j, k;
    for (i = m + 1; i > left; i--) 
        aux[i - 1] = a[i - 1];
    for (j = m; j < right; j++)
        aux[right + m - j] = a[j + 1];
    for (k = left; k <= right; k++)
        if (aux[j].price < aux[i].price || i > m)
            a[k] = aux[j--];
        else
        if ((aux[j].price == aux[i].price) || i > m) {
            if ((aux[j].ident < aux[i].ident) || i > m) {
                a[k] = aux[j--];
            }
        } else
            a[k] = aux[i++];
}

例子：

我的输入：

desc: pao, price:2, weight: 2, quant:200
desc: ovos, price:1, weight: 1, quant:100
desc: iscas, price:3, weight: 3, quant:300
desc: fiambre, price:2, weight: 2, quant:200
desc: queijo, price:2, weight: 2, quant:200

正确的输出：

desc: ovos, price:1, weight: 1, quant:100
desc: pao, price:2, weight: 2, quant:200
desc: fiambre, price:2, weight: 2, quant:200
desc: queijo, price:2, weight: 2, quant:200
desc: iscas, price:3, weight: 3, quant:300

程序：

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

#define MAX_PROD 10000 /* max products in the system */

typedef struct product {
   int ident;      /* idp of a product */
   char desc[64];  /* string that describes a product eg. "bread" */
   int price;      /* price of the product */
   int weight;     /* weight of the product eg. 2kg */
   int quant;      /* quantity of the product in stock */
   int state_prod; /* state of a product, if 1 it is in the system else is 0 and is not in the system */
} product;

product p1 = { 0, "pao", 2, 2, 200, 1 };
product p2 = { 1, "ovos", 1, 1, 100, 1 };
product p3 = { 2, "iscas", 3, 3, 300, 1 };
product p4 = { 3, "bacon", 2, 5, 400, 1 };
product p5 = { 4, "abacate", 2, 6, 500, 1 };

product sistem[5] = {};  /* array that contains the products */
product sistem2[5] = {}; /* Will be used has a copy of sistem */

sistem[5] = { p1, p2, p3, p4, p5}
product aux[5]; /* Auxliar array used in mergesort */

void mergesort_price(product a[], int left, int right) {
    int m = (right + left) / 2;
    if (right <= left)
        return;
    mergesort_price(a, left, m);
    mergesort_price(a, m + 1, right);
    merge_price(a, left, m, right);
}

void merge_price(product a[], int left, int m, int right) { 
    int i, j, k;
    for (i = m + 1; i > left; i--) 
        aux[i - 1] = a[i - 1];
    for (j = m; j < right; j++)
        aux[right + m - j] = a[j + 1];
    for (k = left; k <= right; k++)
        if (aux[j].price < aux[i].price || i > m)
            a[k] = aux[j--];
        else if ((aux[j].price == aux[i].price) || i > m) {
            if ((aux[j].ident < aux[i].ident) || i > m) {
                a[k] = aux[j--];
            }
        } else
            a[k] = aux[i++];
}

void print_array(product arr[]) {
    int i;
    for (i = 0; i < 5; i++) {
         printf("* %s %d %d %d\n", arr[i].desc, arr[i].price, arr[i].quant, arr[i].ident);
    }
}

void copy_el(product source[], product dest[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        dest[i] = source[i];
    }
}

int main() {   
    copy_el(sistem, sistem2, 5);
    printf("The products in the system are:\n");
    print_array(sistem);

    printf("\nSorted products by price in the system:\n");
    mergesort_price(sistem2, 5, 0);
    print_array(sistem2);

    return 0;
}

我知道我输入的内容在程序中没有编码，我只是以这种方式给出输入作为示例，以使其更易于理解。

- Martim Correia

---

aux是什么？另外，为什么你的代码重复了？ - Ackdari

你应该删除代码的第二份副本。你有在调试器中运行过吗？我发现使用更具描述性的变量名可以使代码更易于理解，并且可以比使用 i 或 j 更好地指出问题。 - Retired Ninja

在 merge_price 函数中，i、j 和 k 在它们各自的 for 循环中是 未初始化 的（例如）for (i; 并不会初始化 i。 - Craig Estey

我不明白你的意思，它们怎么没有初始化？ - Martim Correia

sistem[5] = {p1,p2,p3,p4,p5} 看起来并不能实现你所期望的功能。sistem[5] 超出了该数组的边界，而且你无法将 5 个项目塞入一个插槽中。 - Retired Ninja

Answer 1

如我在顶部评论中提到的，你的 for 循环没有初始化 i、j 或 k。

你的排序看起来有些复杂。

有两种方法可以进行合并：

(1) 先将数组复制到临时数组中，再将其合并回原始数组（这是你正在做的）。

(2) 从原始左/右数组合并到临时数组，然后将结果复制回原始数组（对我来说似乎更简单）。

无论如何，这是重构过的版本：

#include <stdio.h>

typedef struct product {
    int ident;                          /* idp of a product */
    char desc[64];                      /* string that describes a product eg.
                                            "bread" */
    int price;                          /* price of the product */
    int weight;                         /* weight of the product eg. 2kg */
    int quant;                          /* quantity of the product in stock */
    int state_prod;                     /* state of a product, if its 1 its in
                                            the system else is 0 and is not in
                                            the system */
} product;

#define AMAX    28
product a[AMAX];
product aux[AMAX];

void merge_price(product a[], int low, int mid, int high);

void
mergesort_price(product a[], int low, int high)
{
    int mid = (high + low) / 2;

    if (high <= low)
        return;
    mergesort_price(a, low, mid);
    mergesort_price(a, mid + 1, high);
    merge_price(a, low, mid, high);
}

void
merge_price(product a[], int low, int mid, int high)
{
    int right;
    int left;
    int k;
    int i;

    k = 0;
    left = low;
    right = mid + 1;

    for (;  (left <= mid) && (right <= high);  ++k) {
        if (a[left].price <= a[right].price)
            aux[k] = a[left++];
        else
            aux[k] = a[right++];
    }

    for (;  left <= mid;  ++left, ++k)
        aux[k] = a[left];

    for (;  right <= high;  ++right, ++k)
        aux[k] = a[right];

    k = low;
    i = 0;
    for (;  k <= high;  ++k, ++i)
        a[k] = aux[i];
}

void
show(void)
{
    for (int idx = 0;  idx < AMAX;  ++idx)
        printf(" %d",a[idx].price);
    printf("\n");
}

int
main(void)
{

    for (int idx = 0;  idx < AMAX;  ++idx)
        a[idx].price = AMAX - idx;
    show();

    mergesort_price(a,0,AMAX - 1);
    show();
}

---

更新：

好的，它起作用了，谢谢。但当我尝试对字符串做相同的事情时，它却没有起作用。我只是真正改变了 if 语句，可以解释一下为什么它没起作用吗？

好的，我创建了一个版本，生成随机产品描述，并按 price 排序。然后根据 desc [一个字符串排序] 进行重新排序。

我使用指向比较函数的指针作为传递给现有函数的额外参数来完成这个操作。这类似于 libc 的 qsort 函数的最后一个参数。

这可以扩展到“多关键字”排序（例如按 price 排序，然后按 然后 按 desc [或任何其他您希望的 struct 成员] 进行排序）。参见：cmpbyboth 和 cmpbyall。

请注意，乍一看，cmpbyall 应该比 cmpbyboth 更快，但是通过（例如）-O2 编译器可能选择内联 [简单] 函数，以便两个函数可能生成完全相同的可执行代码。

无论如何，这是代码：

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

#define STRMAX      64
#define GENSTR      7

typedef struct product {
    int ident;                          /* idp of a product */
    char desc[STRMAX];                  /* string that describes a product eg.
                                            "bread" */
    int price;                          /* price of the product */
    int weight;                         /* weight of the product eg. 2kg */
    int quant;                          /* quantity of the product in stock */
    int state_prod;                     /* state of a product, if its 1 its in
                                            the system else is 0 and is not in
                                            the system */
} product;

typedef int (*cmpfnc_p)(const product *,const product *);

#define AMAX    28
product a[AMAX];
product aux[AMAX];

void merge_price(product a[], int low, int mid, int high,cmpfnc_p cmpfnc);

void
mergesort_price(product a[], int low, int high, cmpfnc_p cmpfnc)
{
    int mid = (high + low) / 2;

    if (high <= low)
        return;
    mergesort_price(a, low, mid, cmpfnc);
    mergesort_price(a, mid + 1, high, cmpfnc);
    merge_price(a, low, mid, high, cmpfnc);
}

void
merge_price(product a[], int low, int mid, int high,cmpfnc_p cmpfnc)
{
    int cmpflg;
    int right;
    int left;
    int k;
    int i;

    k = 0;
    left = low;
    right = mid + 1;

    for (;  (left <= mid) && (right <= high);  ++k) {
        cmpflg = cmpfnc(&a[left],&a[right]);
        if (cmpflg <= 0)
            aux[k] = a[left++];
        else
            aux[k] = a[right++];
    }

    for (;  left <= mid;  ++left, ++k)
        aux[k] = a[left];

    for (;  right <= high;  ++right, ++k)
        aux[k] = a[right];

    k = low;
    i = 0;
    for (;  k <= high;  ++k, ++i)
        a[k] = aux[i];
}

void
show(const char *tag)
{

    printf("\n");
    printf("%s",tag);

    for (int idx = 0;  idx < AMAX;  ++idx)
        printf(" %s=%d",a[idx].desc,a[idx].price);

    printf("\n");
}

// genstr -- get random string
void
genstr(char *desc)
{
    int len;
    int idx;
    int chr;
    int carry;

    // get random string length
    len = (rand() % GENSTR) + 1;

    // fill in random string
    for (idx = 0;  idx < len;  ++idx) {
        chr = rand() % 26;
        chr += 'a';
        *desc++ = chr;
    }

    *desc = 0;
}

// cmpbyprice -- compare by price
int
cmpbyprice(const product *left,const product *right)
{
    int cmpflg;

    cmpflg = left->price - right->price;

    return cmpflg;
}

// cmpbydesc -- compare by description
int
cmpbydesc(const product *left,const product *right)
{
    int cmpflg;

    cmpflg = strcmp(left->desc,right->desc);

    return cmpflg;
}

// cmpbyboth -- compare by price description
int
cmpbyboth(const product *left,const product *right)
{
    int cmpflg;

    do {
        cmpflg = cmpbyprice(left,right);
        if (cmpflg)
            break;

        cmpflg = cmpbydesc(left,right);
        if (cmpflg)
            break;

        // add more if you like ...
    } while (0);

    return cmpflg;
}

// cmpbyall -- compare by price description [faster version]
int
cmpbyall(const product *left,const product *right)
{
    int cmpflg;

    do {
        cmpflg = left->price - right->price;
        if (cmpflg)
            break;

        cmpflg = strcmp(left->desc,right->desc);
        if (cmpflg)
            break;

        // add more if you like ...
    } while (0);

    return cmpflg;
}

int
main(int argc,char **argv)
{
    unsigned int seed;
    product *ptr;

    --argc;
    ++argv;

    if (argc > 0)
        seed = atoi(*argv);
    else
        seed = time(NULL);
    printf("SEED: %u\n",seed);
    srand(seed);

    for (int idx = 0;  idx < AMAX;  ++idx) {
        ptr = &a[idx];
        ptr->price = AMAX - idx;
        genstr(ptr->desc);
    }
    show("INITED");

    mergesort_price(a,0,AMAX - 1,cmpbyprice);
    show("BYPRICE");

    mergesort_price(a,0,AMAX - 1,cmpbydesc);
    show("BYDESC");

    mergesort_price(a,0,AMAX - 1,cmpbyboth);
    show("BYBOTH");

    mergesort_price(a,0,AMAX - 1,cmpbyall);
    show("BYALL");
}

- Craig Estey

---

好的，谢谢，它起作用了，但是当我尝试对字符串进行操作时，它没有起作用。我只是真的改变了if语句，你能解释一下为什么它没有起作用吗？ - Martim Correia