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

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

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

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;

}

c++ doubly-linked-list selection-sort
person ColdMold    schedule 06.11.2018    source источник
comment
Что именно идет не так? Есть ли сообщение об ошибке, которое вы могли бы скопировать в свой вопрос?   -  person Matt    schedule 07.11.2018
comment
@Matt, программа просто завершается, когда я пытаюсь вызвать свою функцию сортировки. Нет реального сообщения об ошибке, вот почему я здесь в тупике.   -  person ColdMold    schedule 07.11.2018
comment
Вы прошли через это с отладчиком?   -  person Mark Ransom    schedule 07.11.2018
comment
@Mark Я пытался использовать строки cout во всей функции сортировки, но мне так и не удалось увидеть что-либо на выходе, когда программа завершается. То, что я пытался сделать, похоже на шаг? Если нет, я посмотрю, как это сделать.   -  person ColdMold    schedule 07.11.2018
comment
Значит, у вас нет интегрированной среды разработки вроде Visual Studio со встроенным отладчиком?   -  person drescherjm    schedule 07.11.2018
comment
@drescherjm Я использую netbeans, но я не использую его давно, поэтому я не слишком хорошо знаком со всем, что такие IDE могут сделать, чтобы помочь мне. Я проведу небольшое исследование.   -  person ColdMold    schedule 07.11.2018

Ответы (2)


arrow_upward
0
arrow_downward

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

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

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

newTail = smallest

после

newHead = smallest
person The Dark    schedule 07.11.2018
comment
только что попробовал добавить newTail = наименьший в конце этого оператора if, и теперь фактической ошибки нет, и он компилируется, но создает бесконечный цикл. - person ColdMold; 07.11.2018
comment
Определенно подумайте об использовании отладчика, гораздо проще найти эти типы проблем, когда вы можете пройти через программу. - person The Dark; 07.11.2018
comment
Я думаю, что бесконечный цикл возникает из-за того, что вы ничего не устанавливаете для smallest в случае, когда в старом списке ссылок осталась только одна запись. Это означает, что наименьший будет оставлен в качестве последней удаленной записи. Добавьте smallest = head вверху петли while head != null). - person The Dark; 07.11.2018
comment
Также, пожалуйста, не редактируйте свой код в вопросе, чтобы исправить проблему - это означает, что мой ответ больше не будет иметь смысла ни для кого другого. - person The Dark; 07.11.2018
comment
Да, извините за это. Я только что вернулся к своей последней редакции поста. Я добавил small = head в начало цикла while, и теперь программа вылетает, а не просто бесконечно зацикливается. Сейчас я собираюсь изучить, как использовать отладчик netbeans. - person ColdMold; 07.11.2018

arrow_upward
0
arrow_downward

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

newTail = smallest

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

smallest = head

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

tail = newTail

После этого моя функция все еще вызывала segfault. Этот segfault произошел из-за того, что я пытался получить доступ к предыдущему элементу 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;

            }
        }

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

smallest->prev = newTail;
smallest->next = NULL;
newTail->next = smallest;
newTail = smallest;
person ColdMold    schedule 07.11.2018