雙鏈表刪除後臺節點功能

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指針，那很好 - 但你必須通過節點指針，而不是節點對象。 mutator函數也必須返回一個指針 - 如果您在頭節點上調用delete_front，那麼您現在已經獲得了對已刪除節點的引用;你需要它的next或者你失去了對列表的任何引用。由於構造函數必須返回一個指針，因此不能使用真正的公共構造函數;你需要一個靜態工廠方法。等等。

您還必須對頭部前後是否存在「哨兵節點」（以及尾部後）是否一致。如果你在你的構造函數中創建了一個哨兵 - 就像你正在做的那樣 - 在最後插入的新節點需要指向哨兵 - 這是你沒​​有做的。

此外，您使用的整個head/tail概念對於節點API是錯誤的。 （另外，混搭不同風格的名字令人難以置信的混淆 - 你有add匹配delete_front和push_tail匹配​​3210 ...）要有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; 
} 

這將創建一個名爲data本地默認構造T變量，然後......什麼都不做吧。你可能想要設置data。你可能想爲此使用初始化器。在這種情況下，你不需要做任何事情，因爲這已經是默認了。

而且我不確定Inlist甚至應該做什麼。

至於remove_ele(T d)，想必您要刪除第一個元素，其data == d，對不對？如果你先寫一個find方法，那麼它是微不足道的：remove(find(d))。 （我假設find拋出異常;如果你想find返回null或定點或別的東西，而是和remove_ele返回true或false，很明顯，你需要一個多線檢查是否找到工作）

如果你不知道如何寫一個find方法...好，這是怎樣的一個鏈表的整點，有一個簡單的遞歸定義爲所有遍歷功能，包括find：

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

無論如何，我認爲，而不是試圖在你的代碼發揮作用之前砰的一聲，你的應該查看各種設計的現有實現，直到你瞭解其差異，然後選擇你想要的設計並嘗試實現它。