C语言 链表上的冒泡排序

Question

我正试图编写一个冒泡排序的实现来排序链表，但目前它导致我的程序崩溃。

结构是这样定义的:

typedef struct shopping_cart cart;
struct shopping_cart{
    char *item_name;
    int quantity;
    cart *next;
};

下面是我的代码:

void sort(cart *head){
    cart *i, *j;
    cart *second = get_second(head);
    cart *last = get_end_of_cart(head);
    for(i = second; i != NULL; i = i->next){
        for(j = head; j != last; j = j->next){
            if ((compare(j, j->next) > 0)){
                swap(j, j->next);
            }
        }
    }
}
void swap(cart *ptr1, cart *ptr2){
    cart *temp;
    temp = ptr1;
    ptr1 = ptr2;
    ptr2 = temp;
}
cart *get_end_of_cart(cart *head){
    cart *_next = head;
    while (_next->next != NULL){
        _next = _next->next;
    }
    return _next;
}

cart *get_second(cart *head){
    cart *first_item = head;
    cart *second_item = first_item->next;
    return second_item;
}

compare函数绝对有效，所以我不会在这里发布。我很确定get_second和get_end_of_cart也可以。所以我想我的错误是在swap或sort，但我看不到问题在哪里。

Answer 1

更改swap函数

void swap(cart **ptr1, cart **ptr2){
    cart *temp = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = temp;
}

你所做的是传递一个指针，并在局部改变它的值。你需要传递指针的地址(指针指向指针)。

确保在使用swap函数时，参数是cart指针的地址。

下面是一个片段:

int main(int argc, char **argv) {
    cart *i = (cart *)malloc(sizeof(cart));
    cart *j = (cart *)malloc(sizeof(cart));
    i->item_name = "hello";
    j->item_name =" bla";
    i->next = j;
    printf("i %sn", i->item_name);
    printf("j %sn", j->item_name);
    swap(&i, &j);
    printf("i %sn", i->item_name);
    printf("j %sn", j->item_name);
}

输出应该是:

i hello
j  bla
i  bla
j hello

编辑

然而，在你的情况下，这将不起作用，因为地址被改变了，这可能会在最坏的情况下导致分段错误。解决这个问题的另一种方法是交换属性。

void swap(cart *ptr1, cart *ptr2){
    char *tmp_name;
    int tmp_quantity;
    tmp_name = ptr1->item_name;
    tmp_quantity = ptr1->quantity;
    ptr1->item_name = ptr2->item_name;
    ptr1->quantity = ptr2->quantity;
    ptr2->item_name = tmp_name;
    ptr2->quantity = tmp_quantity;
}

现在，我们不必处理next，并希望最好的。我们只是在i和j的属性(item_name和quantity)之间交换。

所以代码片段应该是这样的:

int main(int argc, char **argv) {
    cart *i = (cart *)malloc(sizeof(cart));
    cart *j = (cart *)malloc(sizeof(cart));
    i->item_name = "hello";
    j->item_name =" bla";
    i->next = j;
    printf("i %sn", i->item_name);
    printf("j %sn", j->item_name);
    swap(i, i->next);
    printf("i %sn", i->item_name);
    printf("j %sn", j->item_name);
}

大作。: D

Answer 2

我认为您不必在swap函数中更改购物车的属性。惟一需要的是指向要交换的元素前的元素指针。

void swap(cart **first, cart **ptr1, cart **ptr2){
    (*first)->next = *ptr2;
    (*ptr1)->next = (*ptr2)->next;
    (*ptr2)->next = *ptr1;
}

我认为它是有效的，但是应该检查一下。如果以这种方式进行交换，请注意列表的开头部分。

如果您不需要对预先制作的列表进行排序，那么您应该按顺序插入项目。