从结构数组中交换两个结构（冒泡排序）

Question

我有一个包含 3 个整数的结构，每个整数都类似于三角形一侧的大小：

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

我首先需要读取三角形的数量（n）。然后读取n个三角形的3条边，按三角形面积从小到大排序

现在我的想法是将区域相互比较，如果前一个区域大于后一个区域，我交换相应的结构。最后，structs（边）的值将作为输出从小到大打印出来。

我坚持交换结构。到目前为止我已经这样做了：

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) 循环中。

Answer 1

代码的问题是辅助数组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[ );

Answer 2

swap的方法很好。不过您的方法存在逻辑错误。

您比较存储（面积），如果比较正确，则交换三角形，但不交换面积。因此，i-th 三角形不再必然对应于 i-th 存储。

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

（我使用 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

Debug-Tip：正如@alk 提到的，当您不确定特定方法的正确性时，编写一个简洁的程序来测试该方法（一个最小的完整验证示例（MCVE），因为我们倾向于在 Stack Overflow 中说）。

从结构数组中交换两个结构（冒泡排序）

Swapping two structs from an array of structs (bubblesort)

c

swap

struct

pointers

bubble-sort