Сортировка связанного списка

115

26 января 2022, 21:20

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

template <class T>
class LinkedList {
    struct Node  {
        T data;
        Node* link;
    };
    Node* head = nullptr;
    public:
    void pushNode(T value) {
        Node* tail = new Node;
        tail->data = value;
        tail->link = head;
        head = tail;
    };
    vector<T> getList() {
        vector<T> list;
        while(head != NULL) {
            list.push_back(head->data);
            head = head->link;
        }
        return list;
    };
    void sort() {
        if(head == NULL) return;
        bool isNotSorted = 1;
        Node* last=NULL;
        do {
            isNotSorted = 0;
            while(head->link != last) {
                if(head->data>head->link->data) {
                    T temp = head->data;
                    head->data =head->link->data;
                    head->link->data = temp;
                    isNotSorted = 1;
}
                }
            last = head;
        } while(isNotSorted);
    };
};
int main() {
    LinkedList<int> ll;
    ll.pushNode(2019);
    ll.pushNode(2007);
    ll.pushNode(2020);
    ll.pushNode(1999);
    vector<int> vectLL = ll.getList();
    for(size_t i=0; i<vectLL.size(); i++) {
        cout<<"Node "<<i+1<<": ";
        cout<<vectLL[i];
        if(i != vectLL.size()-1) cout<<" --> ";
    }
    ll.sort();
    vectLL = ll.getList();
    for(size_t i=0; i<vectLL.size(); i++) {
        cout<<"Node "<<i+1<<": ";
        cout<<vectLL[i];
        if(i != vectLL.size()-1) cout<<" --> ";
    }
    return 0;
}

Сортировка осуществляется методом пузырька. Как я понимаю, она не выполняется из-за того, что head указывает на элемент за списком, так как сначала был выведен несортированный его вариант. Как исправить эту ошибку?

Answer 1

Если вы внимательно посмотрите на то, как реализовали функцию_член getList, то вы поймете, что после вызова этой функции член_указатель head становится нулевым, а в функции сортировки вы говорите: if(head == NULL) return; Вот и получается, что функция сортировки ничего не выполняет. Правильно будет, если вы вообше нигде не будете трогать указатель head, и он будет всегда указывать на один из концов списка(в вашей реализации pushNode он будет указывать на последный введенный элемент), чтобы класс мог контралировать список и освобождать память

Answer 2

В дополнение к ответу выше, Ваша функция сортировки делает что-то странное. Она не перемещает указатель, а строка last = head; непонятно что делает. Вот (не идеальная) реализация алгоритма сортировки пузырьком:

void sort()
{
    if (!head)
        return;
    Node* temp = head;
    Node* mainTemp = head;
    while (mainTemp)
    {
        while (temp->link)
        {
            if (temp->data > temp->link->data)
            {
                T tempVal = temp->data;
                temp->data = temp->link->data;
                temp->link->data = tempVal;
            }
            temp = temp->link;
        }
        temp = head;
        mainTemp = mainTemp->link;
    }
}