3

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

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 указывает на элемент за списком, так как сначала был выведен несортированный его вариант. Как исправить эту ошибку?

2 ответа 2

3

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

1

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.