Двойной связанный список удалять функцию узла назад

Question

/* Что-то не так с функцией delete_back(); Я думаю, что что-то не так с функцией удаления 3 части. Также remove_ele() Я не знаю, как это сделать, спасибо. почему я использую тот же метод, чтобы удалить элемент не работает */

#include <iostream> 

using namespace std; 


template<class T> 
class doulinked 
{ 
private: 
    doulinked *head; 
    doulinked *tail; 
    doulinked *prev; 
    doulinked *next; 

    T data; 
public: 
    doulinked() 
    { 
     head=tail=prev=next=NULL; 
     T data; 
    } 
    void Inlist (doulinked *head); 
    void add(T d); 
    void insert_node(); 
    void remove(doulinked* v); 
    void push_tail(T d); 
    void delete_front(); 
    void delete_back(); 
    void remove_ele (T d); 
    template <class U> 
    friend ostream & operator<<(ostream & os, const doulinked<U> & dll); 
}; 
template<class U> 
ostream & operator<<(ostream & os,const doulinked<U> & dll) 
{ 
    doulinked<U> * tmp = dll.head; 
    while (tmp) 
    { 
     os << tmp->data << " "; 
     tmp = tmp->next; 
    } 

    return os; 
} 
template<class T> 
void doulinked<T>::add(T d) 
{ 
    doulinked *n = new doulinked; 
    n->data=d; 
     if(head == NULL) 
     { 
      head = n; 
      tail = n; 
     } 
     else 
     { 
      head->prev = n; 
      n->next = head; 
      head = n; 
     } 
} 
template<class T> 
void doulinked<T>::push_tail(T d) 
{ 
    doulinked *n = new doulinked; 
    n->data=d; 
     if(tail == NULL) 
     { 
      head = n; 
      tail = n; 
     } 
     else 
     { 
      tail->next = n; 
      n->prev = tail; 
      tail = n; 
     } 

} 
template <class T> 
void doulinked<T>::delete_front() 
{ 
    remove(head); 
} 
template <class T> 
void doulinked<T>::delete_back() 
{ 
    remove(tail); 
} 
template <class T> 
void doulinked<T>::remove(doulinked* v) 
{ 
    if(v->prev!=NULL && v->next!=NULL) 
    { 
     doulinked* p = v->prev; 
     doulinked* n = v->next;    
     p->next = n;     
     n->prev = p; 
     delete v; 
    } 
    else if(v->prev==NULL && v->next!=NULL) 
    { 
     doulinked* n =v->next;    
     head->next = n;     
     n->prev = head; 
     delete head; 
     head=n; 
    } 
    else if(v->prev!=NULL && v->next==NULL) // have some wrong with this loop; 
    { 
     doulinked* p=v->prev; 
     p->next=tail; 
     tail->prev=p; 
     delete tail; 
     tail=p; 
    } 

} 
template <class T> 
void doulinked<T>::remove_ele(T d) // have some wrong with this loop 
{ 

    if(head->data==d) 
    { 
     remove(head); 
     head=head->next; 
    } 
    else 
     head=head->next; 
} 

int main() 
{ 
    doulinked<int> dll; 
    dll.add(5123); 
    dll.add(1227); 
    dll.add(127); 
    dll.push_tail(1235); 
    dll.push_tail(834); 
    dll.push_tail(1595); 
    dll.delete_front(); 
    //dll.delete_back(); 
    //dll.remove_ele(834); 
    cout<<dll<<endl; 
    system("pause"); 
} 

Answer 1

Ваша конструкция немного запутался.

Традиционный C++ способа создать связанный список (например, std::list) имеет отдельные node и list классов, вместо одного класса, который действует как:

template <typename T> struct node { 
    node *prev, *next; 
}; 
template <typename T> struct list { 
    node *head, *tail; 
}; 

Если вы хотите просто пройти вокруг node указателей , это нормально, но тогда вам нужно пройти вокруг узла указателей, а не узла объектов. И функции-мутаторы должны возвращать указатель, если вы назовете delete_front на головном узле, теперь у вас есть ссылка на удаленный узел; вам понадобится его next или вы потеряли ссылку на список. Поскольку конструктор должен возвращать указатель, вы не можете использовать реальный публичный конструктор; вместо этого вы хотите использовать статический заводский метод. И так далее.

Вы также должны быть последовательны в отношении того, есть ли «дозорный узел» перед головой (и после хвоста) или нет. Если вы создаете контролер в своем конструкторе - как вы делаете - новые узлы, вставленные в конце (-ях), должны указывать на дозор (-ы), которые вы не делаете.

Кроме того, все, что вы используете, неверно для API-интерфейса узла. (Кроме того, невероятно сложно смешивать и сопоставлять имена из разных стилей - у вас есть add, соответствующие delete_front и push_tail, соответствующие delete_back ...) Чтобы иметь метод push_tail, вам либо нужно пройти весь список (что делает его O (N)), , или вам нужно, чтобы каждый узел удерживал указатель tail (делая любое изменение списка O (N)), или вам нужно сделать удержание указателя tail, а хвост - указателем head.

Последний работает (он тратит несколько указателей на каждый узел, когда каждому требуется только один узел, но это редко имеет значение). Но смущает думать.

Это на самом деле намного проще просто создать циклический список, где prev точки головы в на хвосте (или сторожевого) вместо 0, и next точки хвоста в в голове (или сторожевого) вместо 0. Это становится вы все преимущества отдельного класса list, не нуждаясь в этом классе, если у вас есть указатель на голову, это все, что вам нужно, чтобы ссылаться на весь список (потому что node - это голова, а node->prev - это хвост или, или аналогично, если у вас есть страж).

Кроме того, ваш конструктор не имеет особого смысла:

doulinked() 
{ 
    head=tail=prev=next=NULL; 
    T data; 
} 

Это создает локальный по-умолчанию, T переменную с именем data, а потом ... ничего не делает с ним. Вероятно, вам нужно было установить data. И вы, вероятно, хотели использовать для этого инициализаторы. И в этом случае вам не нужно ничего делать, потому что это уже значение по умолчанию.

И я не уверен, что делать Inlist.

Что касается remove_ele(T d), предположительно вы хотите удалить первый элемент, у которого data == d, справа? Если вы сначала напишите метод find, тогда это тривиально: remove(find(d)). (Я предполагаю, что find бросает исключение;., Если вы хотите find вернуть нуль или сторожевого или что-то еще вместо этого, и remove_ele вернуть true или false, очевидно, нужно еще одну строку, чтобы проверить, является ли поиск работал)

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

node *node::find(T d) { 
    if (data == d) { return this; } 
    if (next) { return next->find(d); } 
    return 0; 
} 

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