链表冒泡排序

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这个功能肯定可以，这里就不post了。我很确定 get_second 和 get_end_of_cart 也可以。所以我想我的错误要么在 swap 要么在 sort，但我看不出问题出在哪里。

Answer 1

改变你交换功能

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 %s\n", i->item_name);
    printf("j %s\n", j->item_name);
    swap(&i, &j);
    printf("i %s\n", i->item_name);
    printf("j %s\n", 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 %s\n", i->item_name);
    printf("j %s\n", j->item_name);
    swap(i, i->next);
    printf("i %s\n", i->item_name);
    printf("j %s\n", j->item_name);
}

多田！ :D

Answer 2

我认为您不必在交换功能中更改购物车的属性。您唯一需要的是指向要交换的项目之前的元素的指针。

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

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

如果您不必对预制列表进行排序，则应按排序顺序插入项目。

链表冒泡排序

Bubble sort on linked list

c

sorting

struct

linked-list

data-structures

编辑