Сортировка вставок для односвязного списка C ++ - PullRequest
Новая
       35

Сортировка вставок для односвязного списка C ++

0 голосов
/ 01 марта 2020

Мне дан заголовочный файл, который определяет, как должны создаваться узлы связанного списка. 

#ifndef _LISTNODE
#include <cstddef>
#define _LISTNODE

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
#endif

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

Функция определена как 

ListNode *insertionSortList(ListNode *head)

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

Затем у меня есть другой итератор go по списку, пока он не найдет место, где он go сделает заказ, а затем разместит узел, который хранится с временным указателем и имеет следующий указатель в этом узле, указывает на узел, который, как обнаружил новый итератор, меньше его.

Извините, если это объяснение немного грязно, но, кажется, имеет смысл, когда я рисую диаграмму, и я не вижу, где мой код может разбить эту логику c, но когда я запускаю ее с некоторыми тестами, она либо не сортируется, либо иногда он не сортирует и не печатает все значения. 

#include <iostream>
#include "ListNode.h"
using namespace std;

ListNode *insertionSortList(ListNode *head)
{
    ListNode *temp;
    for (ListNode *iterator = head; iterator->next != NULL; iterator = iterator->next) //first iterator to find node that breaks the pattern
    {
        if (iterator->val >= iterator->next->val) // if it doesn't break the pattern
        {
            break;
        }

        else //if it does break the pattern
        {
            temp = iterator->next; //store pattern breaking node
            iterator->next = iterator->next->next; //have linked list skip over this pattern breaking node 
            for (ListNode *replacementit = head; replacementit->next != NULL; replacementit = replacementit->next) // find place for patteern breaking node
            {
                if (replacementit->val < temp->val) //if found the right place
                {
                    temp->next = replacementit; //put node into place
                    break;
                }
            }
        }
    }

    return head;
}

int main() //test cases
{
    ListNode A(5);
    ListNode B(6);
    ListNode C(10);
    ListNode D(21);
    ListNode E(25);

    ListNode* head = &A;
    A.next = &B;
    B.next = &C;
    C.next = &D;
    D.next = &E;

    insertionSortList(head);

    for (ListNode *print = head; print->next != NULL; print = print->next) //print out sorted Linked List
    {
        cout << print->val << " ";
    }
}

OUTPUT 

5 10 %

1 Ответ

1 голос
/ 01 марта 2020

Ваша реализация неверна в первой строке внутри первой функции for l oop в insertionSortList.

Например - если первый элемент связанного списка больше или равен второму элементу связанного списка, ваш код не будет выполнять больше строк в для l oop, он будет «разбиваться» , Вы можете проверить с помощью списка 2 -> 1 -> 3.

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

...