Обнаружил время сортировки связанного списка

Question

Я пытаюсь отсортировать связанный список с узлами, содержащими имена животных и их вес в возрастающем алфавитном порядке. Я реализовал функцию, чтобы сделать это, но я получаю неожиданный вывод. Я действительно пытался отладить его довольно долго, но я изо всех сил пытаюсь найти проблему. Я был бы очень признателен за любой вклад. Мой код выглядит следующим образом:

typedef struct Animal_Info{
    char animal_name[1000];
    float animal_weight;
}AnimalInfo;

typedef struct my_node{
    AnimalInfo info;
    struct my_node *next;
}Animal_Node;

Animal_Node *sortAnimalList(Animal_Node *head)
{
    Animal_Node *a = NULL;
    Animal_Node *b = NULL;
    a = head;
    b = head->next;
    char name_copy[MAX_STR_LEN];
    float weight_copy;
    while (a != NULL){
        while (b != NULL){
            if (strcmp(a->info.animal_name, b->info.animal_name) > 0){
                strcpy(name_copy, b->info.animal_name);
                weight_copy = b->info.animal_weight;
                deleteNode(b->info.animal_name, b->info.animal_weight, head); // finds and deletes the node
                insertNode(name_copy, weight_copy, head); // insert at head of linked list
            }
            else if (strcmp(a->info.animal_name, b->info.animal_name) == 0){
                weight_copy = 1.0; /* "do nothing" statement */
            }
            b = b->next;
        }
        a = a->next;
    }
}

Answer 1

В вашем коде есть несколько вещей, которые выглядят странно.

Сначала эта часть:

        else if (strcmp(a->info.animal_name, b->info.animal_name) == 0){
            weight_copy = 1.0; /* "do nothing" statement */
        }

Когда он ничего не делает, просто удалите его!

Теперь посмотрите на это и мои встроенные комментарии:

Animal_Node *sortAnimalList(Animal_Node *head)
{
    Animal_Node *a = NULL;
    Animal_Node *b = NULL;
    a = head;
    b = head->next;
    char name_copy[MAX_STR_LEN];
    float weight_copy;
    while (a != NULL){
        while (b != NULL){
            if (strcmp(a->info.animal_name, b->info.animal_name) > 0){
                strcpy(name_copy, b->info.animal_name);
                weight_copy = b->info.animal_weight;

                // Here you delete node b
                deleteNode(b->info.animal_name, b->info.animal_weight, head);
                insertNode(name_copy, weight_copy, head);
            }

            // Here you use node b
            b = b->next;
        }
        a = a->next;
    }
}

Когда вы попадаете в код, который удаляет узел b, вы не можете использовать узел в выражении b = b->next; Просто потому, что b больше не указывает к действительному узлу.

Когда b становится NULL, вы делаете a = a->next;, но не меняете b, так что inner-l oop не будет выполняться.

Я предполагаю, что вам нужно что-то вроде:

    while (a != NULL){

        // Assign new value to b whenever a has changed
        b = a->next;

        while (b != NULL){
            if (strcmp(a->info.animal_name, b->info.animal_name) > 0){
                strcpy(name_copy, b->info.animal_name);
                weight_copy = b->info.animal_weight;

                // Here you delete node b
                deleteNode(b->info.animal_name, b->info.animal_weight, head);
                insertNode(name_copy, weight_copy, head);
            }

            // Here you use node b
            b = b->next;
        }
        a = a->next;
    }

Наконец, я думаю, что ваш алгоритм неверен. Когда вы меняете связанный список, вы всегда помещаете элемент перед списком. Это не сработает. Рассмотрим:

 "c" -> "a" -> "b"

Таким образом, шаги будут такими:

compare "c" and "a"
delete "a" and insert "a" in front, i.e. you have "a" -> "c" -> "b"

compare "c" and "b"
delete "b" and insert "b" in front, i.e. you have "b"->"a" -> "c"

Итак, итоговый список будет "b"->"a" -> "c", который не отсортирован.

Вам необходимо пересмотреть ваш алгоритм.

Вместо «удаления и вставки впереди» вы можете поменять местами узлы. Может быть, это может помочь Обмен узлов в связанном списке