Значение мусора в pop_back, двусвязный список в C ++ - PullRequest
Новая
       60

Значение мусора в pop_back, двусвязный список в C ++

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

В следующем коде я реализовал двусвязный список. Я получаю вывод как 56 2 3 4 0 вместо 56 2 3 4. Однако, если я удаляю lt.erase(5); lt.push_back(46);, я получаю правильный вывод. Сначала я подумал, что в erase() есть некоторые ошибки, но при индивидуальном тестировании каждой функции они кажутся мне подходящими. Однако в этой комбинации я получаю дополнительные 0. 

#include <iostream>
using namespace std;

template <class T>
class LinkedList {
private:
    T data;
    LinkedList *prev, *next, *head, *tail;
public:
    LinkedList() : next(nullptr), head(nullptr), tail(nullptr), prev(nullptr){}
    LinkedList* get_node(T);
    void push_back(T);
    void insert(int, T);
    void pop_bak();
    void erase(int);
    void print();
};

template <typename T>
LinkedList<T>* LinkedList<T>:: get_node(T element) {
    auto* new_node = new LinkedList;
    new_node -> data = element;
    new_node -> prev = nullptr;
    new_node ->next = nullptr;
    return new_node;
}

template <typename T>
void LinkedList<T>:: push_back(T element) {
    static LinkedList *temp;
    if(head == nullptr) {
        head = get_node(element);
        tail = head;
        temp = head;
    } else {
        LinkedList *node = get_node(element);
        tail->next = node;
        tail = node;
        tail->prev = temp;
        temp = temp->next;
    }
}

template <typename T>
void LinkedList<T>:: insert(int position, T element) {
    LinkedList *node = get_node(element);
    if(position == 1){
        head->prev = node;
        node->next = head;
        head = node;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        node->next = start->next;
        node->prev = start;
        start->next = node;
    }
}

template <typename T>
void LinkedList<T>:: pop_bak() {
    LinkedList *temp;
    temp = tail;
    tail = tail->prev;
    tail->next = nullptr;
    delete temp;
}

template <typename T>
void LinkedList<T>:: erase(int position) {
    LinkedList *temp;
    if(position == 1){
        temp = head;
        head = head ->next;
        delete temp;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        if(start->next == tail) {
            temp = tail;
            tail = tail ->prev;
            tail->next = nullptr;
            delete temp;
        } else {
            temp = start -> next;
            start ->next = start ->next->next;
            delete temp;
        }
    }
}

template <typename T>
void LinkedList<T>:: print() {
    LinkedList *start = head;
    while(start != tail->next) {
        cout << start->data << " ";
        start = start->next;
    }
}

int main() {
    LinkedList<int> lt;
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    lt.insert(1, 56);
    lt.erase(5); // Remove this
    lt.push_back(46); // And this and it works perfectly. Where is the bug?
    lt.pop_bak();
    lt.print();
}

Ответы [ 2 ]

2 голосов
/ 27 марта 2020

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

Во-первых, просто глядя на ваш код, я почти уверен, что вы неправильно сохраняете двойные ссылки. Я вижу, как вы настраиваете следующие ссылки, но не прежние ссылки.

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

Решение

static LinkedList *temp; в push_back похоже на ленивый хак. Это не нужно, и ваш код становится еще короче без этого: 

template <typename T>
void LinkedList<T>::push_back(T element) {
    if (head == nullptr) {
        head = get_node(element);
        tail = head;
    }
    else {
        LinkedList* node = get_node(element);
        tail->next = node;
        node->prev = tail;
        tail = node;
    }
}

Но это только ошибка, которую я нашел для этой указанной c проблемы. Zan Lynx, вероятно, прав, может быть больше ошибок.

Объяснение

Вы получаете неопределенное поведение, потому что обращаетесь к удаленной памяти. Ошибка или ошибка проекта static LinkedList *temp; в push_back. Обратите внимание, что temp всегда будет указывать на последний нажатый элемент. Но в какой-то момент вы удаляете последний элемент! Итак, давайте рассмотрим шаг за шагом:

После lt.push_back(5); ваш список выглядит следующим образом: 

                         temp (from push_back)
                         |
56 <-> 2 <-> 3 <-> 4 <-> 5 -> nullptr
|                        |
head                     tail

Теперь сотрите delete s узел со значением 5. Но temp все еще указывает на память, которая была освобождена 1 , так что вы получите: 

                        temp (from push_back)
                        |
56 <-> 2 <-> 3 <-> 4    5 [freed]
|                  |
head               tail

После следующей строки lt.push_back(46); вещи go сумасшедшие. У вас есть следующий код (просто): 

void LinkedList<T>::push_back(T element) {
    static LinkedList* temp;
    if (head == nullptr) {...}
    else {
        LinkedList* node = get_node(element);
        tail->next = node;                   
        tail = node;                         
        tail->prev = temp; // prev->temp is now pointing to freed memory
        temp = temp->next; // dereferencing an invalid pointer -> undefined behaviour
    }
}

Это приводит к: 

                                          temp (from push_back)
         5 [deleted] <-                   |
56 <-> 2 <-> 3 <-> 4 -> 46  -> nullptr    ????  
|                       |
head                    tail

Тогда все идет в ад в корзине с lt.pop_bak();: 

void LinkedList<T>::pop_bak() {
    LinkedList* temp;
    temp = tail;
    tail = tail->prev;    // tail->prev is an invalid pointer, now tail is too
    tail->next = nullptr; // dereferencing invalid pointer (again)
    delete temp;
}

                        temp (from pop_bak)                 
                        |                                   
56 <-> 2 <-> 3 <-> 4 -> 46 [deleted] -> nullptr     5 [deleted] -> nullptr
|                                                   |
head                                                tail

Как вы видите, ваш список был полностью урезан, и вы получили два указателя, которые указывают на освобожденную память (например, память, которой вы не владеете, которая содержит данные для мусора). Просто потому, что вы сохранили указатель в static LinkedList *temp; в push_back.

1 Хотя в C ++ вы используете delete, а не C -функцию free Я имею в виду «освобожденную память», потому что, на мой взгляд, она более понятна. Память все еще там, она просто больше не принадлежит вашей программе
...