Сортировка связанного списка с использованием сортировки выбора в C ++

Question

Я сталкиваюсь с некоторой ошибкой во время выполнения при попытке проверить мой метод сортировки. В моей реализации я пытаюсь найти наименьший узел в связанном списке ... После этого я проверяю, является ли наименьший узел первым узлом, последним узлом или просто посередине. После тестирования этих случаев я пытаюсь добавить наименьшее значение в новый связанный список. Я делаю это во всех отсортированных значениях, затем указываю head (приватная переменная в моем классе) на вновь отсортированный список ... Если мне нужно включить мой заголовочный файл или что-нибудь еще, пожалуйста, дайте мне знать. Любая помощь приветствуется.

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

void Linkedlist::sort()
{
    Node * current = head;
    Node * smallest = head;
    Node * newHead = NULL;
    Node * newTail = NULL;

    while(head != NULL)
    {
        current = head;
        while(current != NULL)
        {
            if(current->elem < smallest->elem)
            {
                smallest = current;
            }
            current = current->next; 
        }

        //smallest is first node
        if(smallest->prev == NULL)
        {
            head = head->next;
            head->prev = NULL;
        }

        //smallest is last node
        else if(smallest->next == NULL)
        {
            tail = tail->prev;
            tail->next = NULL;
        }

        else
        {
            smallest->prev->next = smallest->next;
            smallest->next->prev = smallest->prev;
        }

        //adding smallest to a new linked list
        if(newHead == NULL)
        {
            smallest->prev = NULL;
            smallest->next = NULL;
            newHead = smallest;
        }
        else
        {
            smallest->prev = newTail;
            smallest->next = NULL;
            newTail->next = smallest;
            newTail = smallest;
        }
    }
    //point head to new linked list
    head = newHead;

}

Answer 1

после добавления

newTail = smallest

при помещении наименьшего элемента в первый узел и добавлении

smallest = head

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

tail = newTail

После этого моя функция все еще вызывала ошибку. Это ошибка произошла из-за того, что я пытался получить доступ к предыдущему члену NULL.

head = head->next //head is now NULL
head->prev = NULL //segfault

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

//smallest is first node
        if(smallest->prev == NULL)
        {
            //check if smallest is the ONLY node left
            //if it is only node left, head = head->next makes head NULL 
            //                         so then head->prev = NULL causes segfault
            if(smallest->next == NULL)
            {
                //break leaves while loops 
                //which is why you have to add the final node 
                //outside of the while loops
                break;
            }

            else
            {
                head = head->next;
                head->prev = NULL;

            }
        }

Когда остается один узел, он попадает в разрыв и выходит из обоих циклов while. Это означает, что последний узел никогда не был добавлен в отсортированный список. Чтобы исправить это, я просто использовал следующий код, прежде чем указывать головой и хвостом на их новый список.

smallest->prev = newTail;
smallest->next = NULL;
newTail->next = smallest;
newTail = smallest;

Answer 2

Вам необходимо установить newTail при добавлении первого элемента в новый связанный список.

В противном случае, когда newTail->next = smallest выполняется для второй новой записи, это будет нулевой указатель доступа.

Просто добавьте

newTail = smallest

после

newHead = smallest