Вставка в двусвязный список

Я пытаюсь создать контейнер с двусвязным списком для проекта. Я не могу использовать стандартные контейнеры. Двусвязный список необходимо отсортировать. Вот мой код:

#include <iostream>
using namespace std;

template <typename T>
class dll {
private:
    struct Node {
        Node* prev;
        Node* next;
        T data;
    };

    Node* head;
    Node* tail;

public:
    dll();
    ~dll();

    void insert(T value);

    bool empty() const { return head == tail; };
};

template <typename T> dll<T>::dll() {
    head = nullptr;
    tail = head;
}

template <typename T> dll<T>::~dll() {
    delete[] head;
}

template <typename T> void dll<T>::insert(T value) {
    Node *node = new Node;
    node->data = value;
    // Case 1: There are no nodes yet
    if (head == nullptr) {
        node->prev = nullptr;
        node->next = nullptr;
        head = node;
        tail = head;
    }
    else {
        // Case 2: There is more than one node
        Node *curr = head;
        if (curr->next != nullptr)
        {
            while (curr->next) {
                // If the value is less than the current value
                if (value < curr->data) {
                    Node *temp = new Node;
                    temp->data = curr->data;
                    temp->next = curr->next;
                    temp->prev = curr->prev;
                    node->next = temp;
                    node->prev = temp->prev;
                    curr->prev = node;
                }
                curr = curr->next;
            }
        }
        // Case 3: There is only one node
        else {
            node->prev = head;
            node->next = nullptr;
            tail = node;
        }
    }
}

int main() {
    dll<int> list;
    list.insert(10);
    list.insert(20);
    list.insert(15);
}

Проблема, с которой я столкнулся, заключается в моей функции вставки. Я использую отладчик и вхожу в код в строке: list.insert (10) ;.

Он правильно переходит в первый случай, когда head == nullptr и создает Node. Когда я перехожу к следующей строке кода (list.insert (20)), он создает узел с этой строкой: Node * node = new Node; Но он создает узел с адресом памяти, на который указывает голова.

Я обратил внимание на переменную head, переменную узла и адреса памяти были одинаковыми. По сути, он создает тот же узел, что и при последней вставке.

Я не знаю, как получить строку: Node * code = new Node; создать что-то новое. Я неправильно использую ключевое слово new?


c++ new-operator doubly-linked-list
person DHines    schedule 08.08.2014    source источник
comment
dll, вероятно, не лучшее имя для двусвязного списка. В Windows это означает нечто совершенно иное. :)   -  person selbie    schedule 09.08.2014
comment
В чем смысл temp? Почему бы не использовать curr? И тогда зачем устанавливать node->next как временный? Вы фактически проделываете дыру в своем списке. Кроме того, вы забыли обновить узел за node.   -  person scohe001    schedule 09.08.2014
comment
удалить [] голову; использование удаления неверно   -  person Matt    schedule 09.08.2014
comment
Вы можете упростить свой список, используя дозорный узел.   -  person eerorika    schedule 09.08.2014
comment
Хотя в вашем коде есть несколько ошибок, о которых уже упоминалось, проблема с созданием объектов по одному и тому же адресу со мной не возникает: ideone.com/RX5NyR   -  person eerorika    schedule 09.08.2014
comment
@ user2226319 Смотрите мой обновленный пост.   -  person Vlad from Moscow    schedule 09.08.2014

Ответы (2)


arrow_upward
1
arrow_downward

Чтобы упростить инициализацию Node, давайте добавим разумный конструктор, который инициализирует элементы prev и next значением null. Это упрощает работу с последующим кодом.

struct Node {
    Node* prev;
    Node* next;
    T data;
    Node() : prev(nullptr), next(nullptr)
    {

    }
};

В проблеме связанного списка всегда есть четыре случая, о которых следует помнить. Некоторые из них у вас есть. Вставка в пустой список. Вставка в начале списка, вставка в конце списка и в середине.

template <typename T> void dll<T>::insert(T value) {
    Node *node = new Node;
    node->data = value;

    // Case 1: There are no nodes yet
    if (head == nullptr) {
        head = node;
        tail = head;
        return;
    }


    // case 2 - inserting at the head of the list
    if (node->data < head->data)
    {
        node->next = head;
        head = node;
        return;
    }

    // case 3 - inserting at the end of the list
    if (node->data >= tail->data)
    {
        node->prev = tail;
        tail->next = node;
        tail = node;
        return;
    }

    // general case - inserting into the middle
    Node* probe = head;
    while (probe && (node->data >= probe->data))
    {
        probe = probe->next;
    }
    if (probe)
    {
        node->next = probe;
        node->prev = probe->prev;
        probe->prev->next = node;
        probe->prev = node;
        return;
    }

    // error - we shouldnt' reach this point. If we did, it meant the list was out of order to begin with.
    return;
}
person selbie    schedule 08.08.2014
comment
Спасибо, селби! Это очень помогло. - person DHines; 09.08.2014
comment
Видя, как мне не хватает ровно на 5 очков, чтобы достичь рубежа в 20 тысяч, почему бы тебе не помочь мне ... :) - person selbie; 09.08.2014
comment
@selbie xD вот и 10 из моих за это - person AVI; 11.05.2017

arrow_upward
0
arrow_downward

Во-первых, деструктор недействителен. Это утверждение

delete[] head;

означает, что голова - это массив. Однако голова - это не массив. Это указатель на отдельный объект типа Node. Вы должны удалить все узлы списка в деструкторе. Деструктор может выглядеть следующим образом

template <typename T> 
dll<T>::~dll() 
{
    while ( head )
    {
        Node *tmp = head;
        head = head->next;
        delete tmp;
    }
}

Что касается вставки метода, то это может выглядеть очень просто. Например

template <typename T> 
void dll<T>::insert( const T &value ) 
{
    Node *current  = head;
    Node *previous = nullptr;

    while ( current && !( value < current->data ) )
    {
        previous = current;
        current  = current->next;
    }

    Node *node = new Node { previous, current, value };

    if ( previous == nullptr ) head = node;
    else previous->next = node;

    if ( current  == nullptr ) tail = node;
    else current->prev = node;
}

И нет необходимости и смысла добавлять конструктор в структуру Node. Лучше, когда это будет агрегат.

Вот тестовая программа

#include <iostream>

template <typename T>
class dll 
{
private:
    struct Node 
    {
        Node *prev;
        Node *next;
        T data;
    };

    Node *head;
    Node *tail;

public:
    dll();
    ~dll();

    void insert( const T &value);

    bool empty() const { return head == tail; };

    void print() const;
};

template <typename T> 
dll<T>::dll() 
{
    head = tail = nullptr;
}

template <typename T> 
dll<T>::~dll() 
{
    while ( head )
    {
        Node *tmp = head;
        head = head->next;
        delete tmp;
    }
}

template <typename T> 
void dll<T>::insert( const T &value ) 
{
    Node *current  = head;
    Node *previous = nullptr;

    while ( current && !( value < current->data ) )
    {
        previous = current;
        current  = current->next;
    }

    Node *node = new Node { previous, current, value };

    if ( previous == nullptr ) head = node;
    else previous->next = node;

    if ( current  == nullptr ) tail = node;
    else current->prev = node;
}

template <typename T> 
void dll<T>::print() const
{
    for ( Node *current = head; current; current = current->next )
    {
        std::cout << current->data << ' ';
    }
}

int main() 
{
    dll<int> list;

    list.insert( 10 );
    list.insert( 20 );
    list.insert( 15 );

    list.print();
    std::cout << std::endl;

    return 0;
}

На выходе

10 15 20
person Vlad from Moscow    schedule 08.08.2014