Как создать код для вставки целого числа в связанный список отсортированным образом?

Question

Это часть моего задания.Я должен поместить номер в связанный список.Это должно быть в порядке, и это не может разрешить дубликаты.

Я пробовал следующий код, но я всегда заканчиваю ошибками сегментации.

int insertSortedLL(LinkedList *ll, int item)
{
    ListNode *current;
    int index=0;
    int res;

    if (ll == NULL || ll->head->item >= item) 
    {
        res=insertNode(ll,0,item);
        return 0;
    } 
    else
    { 
        /* Locate the node before the point of insertion */
        current = ll->head; 
        while (current->next!=NULL)
        { 
            if(current->next->item==item){
                return -1;
            }
            else if(current->next->item < item){
                current = current->next;
                index++;
            }
            else{
                break;
            }
        } 
        res=insertNode(ll,index,item);
        return index;
    } 
}

Я ожидал, что это возвратит значение, который является индексом числа, в котором он хранится, но он никогда не работал.Кроме того, int insertNode - это готовая функция для вставки числа в выбранный индекс, а ListNode - для определения узлов.

Answer 1

В вашем коде есть несколько ошибок.

1. Даже если связанный список, переданный в качестве аргумента, равен NULL, вы все равно вызовете insertNode(ll,0,item).Если связанный список имеет значение NULL, это приведет к ошибке сегментации в 100% случаев.

    if (ll == NULL || ll->head->item >= item) 
    {
        res=insertNode(ll,0,item);
        return 0;
    } 

Логика немного странная.Кажется, вы не хотите, чтобы элементы повторялись в вашем списке, как я вывел из этого оператора if (if(current->next->item==item)), но вы не проверяете это условие для первого элемента списка.

Использование функции insertNode делает ваш код менее эффективным.insertNode нужно будет снова перебрать список, чтобы поместить новый элемент в нужное место.

РЕДАКТИРОВАТЬ: Это грязное исправление (по сравнению с другой версией), чтобы не допуститьдубликаты в списке.

ListNode* make_node(int item){
    ListNode * new = malloc(sizeof(ListNode));
    new->item = item;
    new->next = NULL;
    return new;
}

int insertSortedLL(LinkedList *ll, int item){
    ListNode *current;
    ListNode *new;
    ListNode *tmp;
    int index=0;

    if(ll == NULL)
        return -1;

    //If the list is empty
    if(ll->head == NULL){
        ll->head = make_node(item);
    }

    if(ll->head->item == item)
        return -1;

    if(ll->head->item > item){
        new = make_node(item);
        new->next = ll->head;
        ll->head = new;
        return 0;
    }

    /* General case */
    current = ll->head; 
    while (current != NULL){
        if(current->next == NULL){
            current->next = make_node(item);
            return index;
        }else if (current->next->item == item){
            return -1;
        }else if (current->next->item < item){
            current = current->next;
            index++;
        }else{
            new = make_node(item);
            tmp = current->next;
            new->next = tmp;
            current->next = new;
            return index;
        }
    }
    return -1;
}

Редактировать: это версия, которая допускает дублирование.

#include <stdlib.h>

int insertSortedLL(LinkedList *ll, int item){
    ListNode *current;
    ListNode *new;
    ListNode *tmp;
    int index=0;

    if(ll == NULL)
        return -1;

    new = malloc(sizeof(ListNode));
    new->item = item;
    new->next = NULL;

    //If the list is empty or the first item of ll is greater
    if(ll->head == NULL || ll->head->item >= item){
        new->next = ll->head;
        ll->head = new;
        return 0;
    }

    /* General case */
    current = ll->head; 
    while (current != NULL){
        if(current->next == NULL){
            current->next = new;
            return index;
        }else if (current->next->item < item){
            current = current->next;
            index++;
        }else{
            tmp = current->next;
            new->next = tmp;
            current->next = new;
            return index;
        }
    }
    return -1;
}

Полезный инструмент для поиска того, какой фрагмент кода генерирует сообщение «Ошибка сегментации»: valgrind (и делает много других вещей, таких как поиск утечек памяти и т. д.).

Скомпилируйте свой код, используя -g -Wall -Wextra, не игнорируйте предупреждающие сообщения компилятора (даже если они кажутся безвредными) и запустите программу с valgrind.