在C语言中使用指针进行结构体的冒泡排序

Question

我希望使用C语言的冒泡排序算法和指针对结构体数组进行排序。 我有一个cars结构体：

typedef struct{
    char model[30];
    int hp;
    int price;
}cars;

我为12个项目分配内存：

cars *pointer = (cars*)malloc(12*sizeof(cars));

并从文件中读取数据：

for (i = 0; i <number ; i++) {
    fscanf(file, "%s %i %i\n", (pointer+i)->model, &(pointer+i)->hp, &(pointer+i)->price);
}

我把指针ptr传递给了bubbleSort函数：

bubbleSort(pointer, number);

这是我的bubbleSort函数：

void bubbleSort(cars *x, int size) {
    int i, j;
    for (i=0;i<size-1;i++) {
    int swapped = 0;
    for (j = 0; j < size - 1 - i; j++) {
        if ( (x+i)->hp > (x+j+1)->hp ) {
            cars *temp = (x+j+1);
            x[j+1] = x[j];
            x[j] = *temp;
            swapped = 1;
        }
    }
        if (!swapped) {
        //return;
        }
    }
}

问题在于我不知道如何使用指针交换项目。

- yerassyl

---

尝试将 cars *temp = (x+j+1); 更改为 cars temp = x[j+1];..x[j] = temp;。 - BLUEPIXY

也就是说 if ( (x+i)->hp > (x+j+1)->hp ) { --> if ( (x+j)->hp > (x+j+1)->hp ) { - BLUEPIXY

不需要对malloc的返回值进行类型转换。这是C++的事情。只需使用cars *pointer = malloc(12*sizeof(cars));即可。 - Deanie

Answer 1

考虑以下用于排序函数的解决方案：

void bubbleSort(cars *x, int size) 
{
    int i, j;
    for (i = 0; i < size-1; i++) 
    {
        for (j = 0; j < size-1-i; j++) 
        {
            if ( x[j].hp > x[j+1].hp ) 
            {
               cars temp = x[j+1];
               x[j+1] = x[j];
               x[j] = temp;
            }
        }
    }
}

问题出在数据交换部分。

- VolAnd

---

现在，在你指出我的错误之后，我的解决方案也是正确的，只是有点不同！ - Sir Jo Black

如果你不只是简单地复制示例，那么你的解决方案会有所不同。当然，对于同一个问题，存在无数种不同的解决方案。祝你好运！ - VolAnd

@VolAnd，这可能被视为标准编码！我认为Dogbert并没有说什么要被发现，如果你提到我，请看回复时的时间，并注意我在Dogbert之前写了回复，但有一些错误，我已经纠正了！ - Sir Jo Black

Answer 2

void bubbleSort(cars *x, int size)
{
        int i, j;
        cars temp;

        for (i=0;i<size-1;i++) {
            for (j = i+1; j < size; j++) {
                if ( (x+i)->hp > (x+j)->hp ) {
                    temp = x[j];
                    x[j] = x[i];
                    x[i] = temp;
                }
            }
        }
}

这是对代码下评论的回复；它展示了我建议的排序方法交换更少的次数... :) 这里是代码：

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

typedef struct {
    int x;
    int hp;
} cars;

int swaps;

void bubbleSortB(cars *x, int size)
{
        int i, j;
        cars temp;

        for (i=0;i<size-1;i++) {
            for (j = i+1; j < size; j++) {
                if ( (x+i)->hp > (x+j)->hp ) {
                    temp = x[j];
                    x[j] = x[i];
                    x[i] = temp;
                    swaps++;
                }
            }
        }
}

void bubbleSortA(cars *x, int size)
{
    int i, j;
    for (i = 0; i < size-1; i++)
    {
        for (j = 0; j < size-1-i; j++)
        {
            if ( x[j].hp > x[j+1].hp )
            {
               cars temp = x[j+1];
               x[j+1] = x[j];
               x[j] = temp;
               swaps++;
            }
        }
    }
}

int main(void)
{
    int i;

    cars x[10]={ {1,4},{1,8},{1,12},{1,6},{1,5},{1,4},{1,8},{1,12},{1,6},{1,5} };
    cars y[10]={ {1,4},{1,8},{1,12},{1,6},{1,5},{1,4},{1,8},{1,12},{1,6},{1,5} };

    swaps=0;
    bubbleSortA(x,10);
    for(i=0;i<10;i++)
        printf("%d ",x[i].hp);
    printf("- swaps %d\n",swaps);

    swaps=0;
    bubbleSortB(y,10);  //My sort
    for(i=0;i<10;i++)
        printf("%d ",y[i].hp);
    printf("- swaps %d\n",swaps);

}

- Sir Jo Black

---

你没有对(x+j)进行解引用，并且将指向结构体的指针赋值给了一个结构体。 - Cloud

今天我喝醉了... :) 现在一切都应该正确！ - Sir Jo Black

这不是通常的冒泡排序算法，它操作的是“相邻项对”。它更类似于选择排序，但有很多无用的交换。 - undur_gongor

@undur_gongor，我对两种排序方法（我的和DogBert的）进行了一次小测试！结果是相同的，但我的交换次数更少！... :) 我将测试添加到了上面的代码中，因为它无法放在注释中。 - Sir Jo Black

也许吧。但这还不是冒泡排序。如果性能很重要，那么冒泡排序和选择排序都不行。 - undur_gongor

我总是使用库中的qsort！但我的排序算法是冒泡排序的优化版本！ - Sir Jo Black

Answer 3

使用类似以下的交换函数：

#define TYPE <your type>
void swap(TYPE *a, TYPE *b){
        TYPE *temp = (TYPE*)malloc(sizeof(TYPE));
        *temp = *a;
        *a = *b;
        *b = *temp;
        free(temp);
}

或者这个，不使用malloc：

void swap(TYPE *a, TYPE *b){
        TYPE temp;
        temp = *a;
        *a = *b;
        *b = temp;
}

- 1.618

---

需要交换的值不是整数，而是一个结构体！ :) - Sir Jo Black

@Dogbert 在排序中，如果值相同为什么要进行交换？这似乎是教条主义，但我无论如何会编辑这个答案... - 1.618

此解决方案仅适用于整数类型，如char、int、long，但不适用于结构体！！！ - Sir Jo Black

@undur_gongor 嗯...我猜这样会更好，因为只有一个临时变量。我会添加该函数的另一个版本。 - 1.618

也许是这样，但使用单独的函数会使代码更易读！虽然这只是我的个人偏好！ - 1.618