从结构体数组中交换两个结构体 (冒泡排序)

Question

我有一个结构体，其中包含3个整数，分别表示三角形的三条边的长度：

struct triangle{
    int a; int b; int c;
};
typedef struct triangle tri;

首先，我需要读取要处理的三角形数量（n）；然后，我会读取n个三角形的三条边，并按照从小到大的顺序排序。

接下来，我的想法是比较这些三角形的面积，如果前面的面积比后面的面积大，则交换相应的结构。最后，结构体（即三角形的三条边）的值将按照从小到大的顺序打印出来。

我卡在了如何交换这些结构上。目前为止，我已经完成了以下步骤：

void swap(tri *a, tri *b)
{
    tri t;
    t = *a;
    *a = *b;
    *b = t;
}

void sort_by_area(tri *tr, int n)
{
    int sorted, storage[n];

    for(int i = 0; i <= n-1; i++)
    {
        storage[i] = give_area(&tr[i]);
    }

    do
    {
        sorted = 1;
        for(int i = 0; i < n-1; i++)
        {
            if(storage[i] > storage[i+1])
            {
                /*swap(tr[i].a, tr[i+1].a);
                swap(tr[i]->b, tr[i+1]->b);  
                swap(tr[i]->c, tr[i+1]->c);*/
              /*the commented section was my another attempt in which I would change the swap inputs to swap(int a, int b) or swap(int *a, int *b)*/

                swap(&tr[i], &tr[i+1]);
                sorted = 0;

            }
        }
    }while(!sorted);
}

我确定把结构体放在这里是完全错误的。

如果需要更多信息，这是我的主函数：

int main()
{
    int n;
    scanf("%d\n", &n);
    tri *tr = malloc(n*(sizeof(tri)));

    for(int i = 0; i < n; i++){
        scanf("%d %d %d", &tr[i].a, &tr[i].b, &tr[i].c);
    }
    sort_by_area(tr, n);

    for(int i = 0; i < n; i++){
        printf("\n%d %d %d", tr[i].a, tr[i].b, tr[i].c);
    }
    free(tr);
return 0;
}

经过我的调查，代码运行正确，我认为主要问题可能在于交换函数或者嵌套的for/if循环中运行的交换函数。

- DemoVision

---

如果不确定，请编写一个简单的测试程序，仅使用定义的输入执行单个交换并打印结果。 - alk

我同意@alk的观点，此外根据这个链接，交换函数看起来没问题。在你交换结构体之后，storage会发生什么？ - gsamaras

@xing今天会去做，谢谢你的提示！ - DemoVision

感谢大家的询问。 - DemoVision

@DemoVision 欢迎您，但别忘了检查已发布的答案，并接受其中一个，如果您觉得它有用！ - gsamaras

Answer 1

交换方法是正确的。但你的方法存在逻辑错误。

你比较了存储（区域），如果比较结果为真，则交换三角形，但没有交换区域。结果是，第 i 个三角形不一定对应于第 i 个存储。

当它们各自的三角形被交换时，你需要同时交换区域，像这样：

（我使用double来存储区域，但你仍然可以使用int，只是精度会降低）

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

struct triangle{
    int a; int b; int c;
};
typedef struct triangle tri;

void swap(tri *a, tri *b)
{
    tri t;
    t = *a;
    *a = *b;
    *b = t;
}

void swap_double(double *a, double *b)
{
    double tmp = *a;
    *a = *b;
    *b = tmp;
}

// Heron's formula
double give_area(struct triangle *tr)
{
  double t = (tr->a + tr->b + tr->c)/2.0; /* Compute half of the perimeter */
  return sqrt(t * (t - tr->a) * (t - tr->b) * (t - tr->c)); /* Return area */
}

void sort_by_area(tri *tr, int n)
{
    int sorted;
    double storage[n];

    for(int i = 0; i <= n-1; i++)
    {
        storage[i] = give_area(&tr[i]);
    }

    do
    {
        sorted = 1;
        for(int i = 0; i < n-1; i++)
        {
            if(storage[i] > storage[i+1])
            {
                swap(&tr[i], &tr[i+1]);
                // Swap the areas too!!!
                swap_double(&storage[i], &storage[i + 1]);
                sorted = 0;

            }
        }
    }while(!sorted);
}

int main(void)
{
    int n;
    scanf("%d\n", &n);
    tri *tr = malloc(n*(sizeof(tri)));

    for(int i = 0; i < n; i++){
        scanf("%d %d %d", &tr[i].a, &tr[i].b, &tr[i].c);
    }
    sort_by_area(tr, n);

    for(int i = 0; i < n; i++){
        printf("\n%d %d %d", tr[i].a, tr[i].b, tr[i].c);
    }
    free(tr);
    return 0;
}

编译方式如下：

gcc main.c -Wall -Wextra -lm
./a.out

输入：

2
7 8 9
4 5 6

输出：

4 5 6
7 8 9

---

调试提示：正如@alk所提到的，当你对某个方法的正确性不确定时，编写一个简洁的程序来测试该方法（我们在Stack Overflow中习惯称之为最小完整验证示例(MCVE)）。

---

- gsamaras

Answer 2

代码的问题在于，当结构元素交换时，辅助数组storage保持不变。

实际上，没有必要使用这个辅助数组。如果没有它，你可以直接写

if( give_area(&tr[i] ) > give_area( &tr[i+1] ) )

否则，您需要添加一个额外的交换函数，如下所示：

void swap_storage(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

并与已定义的函数swap一起使用

swap(&tr[i], &tr[i+1]);
swap_storage( &storage[i[, ^storage[i+1[ );

- Vlad from Moscow

---

很好的回答Vlad，+1，干得好！我冒昧做了一个小修改，使它更加一致，希望没关系.. :) PS：give_area()方法可以通过海伦公式实现，就像我在我的答案中所做的那样.. - gsamaras

@gsamaras Heron公式正是我所使用的方法:D就像我说的，我唯一遇到的问题就是交换，而你们所有人通过指出我所犯的逻辑错误，已经帮了我很多！ - DemoVision