最後在雙向鏈表中追加或插入

Question

我試圖在雙向鏈表的末尾插入一個值，我成功地插入了頭或第一個節點的值，但第二個值沒有被插入

這裏的問題是，在進入第二個值

class d_list 
{ 
private: 

    struct node 
    { 
     double data; 
     node *next; 
     node *previous; 
    }; 

    node *first; 
    node *last ; 
public: 
    d_list(void) 
    { 
     first = nullptr; 
     last = nullptr; 
    }; 
    void append(double); 

}; 

void d_list::append(double num) 
{ 
    node *ptr; 
    node *toinsert; 
    if(!first) 
    { 
     first = new node; 
     first->previous= nullptr; 
     first->data = num; 
     last= new node; 
     first->next= last->previous; 
     last->previous = first->next; 
     last->next= nullptr; 

    } 
    else 
    { 
     if(last->next == nullptr) 
     { 
      ptr = new node; 
      ptr->next =last->previous; 
      ptr->data=num; 
      last->previous = ptr->next ; 
     } 


     last->next= nullptr; 
    } 

} 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    d_list aa; 
    cout<<"going to append first"<<endl; 
    aa.append(44); 
    cout<<"going to append second"<<endl; 
    aa.append(50.5); 

    return 0; 
} 

Answer 1

你有許多問題在你的代碼：

• 你node下一個和以前的成員從來沒有在任何地方初始化並使用時，結果是不確定的。可以將一個構造函數添加到node或確保它們在分配後進行初始化。
• 將節點添加到空列表是不正確的。 first->next未定義，爲什麼要創建兩個節點，包括第一個和最後一個？在包含一個元素的列表中，然後first == last。第一個/最後一個下一個/上一個的設置也沒有任何意義。
• 在格式良好的雙鏈表中，那麼last->next應該始終爲空，應該爲first->previous。
• 將節點添加到非空列表中也是不正確的。
• 雖然在示例中沒有顯示它，但最終需要一個析構函數以及一個複製操作符和複製構造函數（三條規則）。目前，你正在泄漏內存，如果你試圖刪除節點，你可能會導致一個雙重的和崩潰的。

我建議從代碼中稍微退出一點，以確保您正確理解雙鏈表背後的概念。使用next/prev箭頭在紙上繪製一個列表，看看在將節點添加到空/非空列表時如何更改它們以及如何刪除和移動節點。一旦確定應該如何設置next/prev，那麼將其轉換爲代碼應該是相對直截了當的。

編輯回答評論： 要添加技術上可以將其添加任何地方一個新的節點，但它通常是在年底加入（至少從我所看到的）。查看其他答案，獲取完整和正確的代碼，以便在空列表和非空列表中添加新節點。

Answer 2

... 
if(last->next == nullptr) 
{ 
    ptr = new node; 
    ptr->next =last->previous; // <- is not correct 
    ptr->data=num; 
    last->previous = ptr->next ; // <- does not do anything useful 
    ... 

不要將您的新節點添加到列表中。

... 
if(!last->next) 
{ 
    ptr = new node; 
    ptr->previous=last->previous; 
    ptr->next =last; 
    ptr->data=num; 
    last->previous = ptr ; 
    ... 

應該會更好。順便說一下：在析構函數中刪除已分配的內存！

Answer 3

我會寫在下面的代碼的雙向鏈表：

#include <iostream> 
    using namespace std; 
    class d_list 
    { 
    private: 

     struct node 
     { 
      double data; 
      node *next; 
      node *previous; 
     }; 

     node *first; 
     // node *last ; no need for bidirectional list 
    public: 
     d_list(void) 
     { 
      first = nullptr; 
      //last = nullptr; 
     }; 
     void append(double); 

    }; 

    void d_list::append(double num) 
    { 
     node *ptr = new node; 
     ptr->data = num; 
     node *toinsert; 
     if(!first) 
     { 
      first = ptr; 
      first->previous=first->next=first; 
     } 
     else 
     { 
      if(first->next == first) 
      { 
       ptr->next = ptr->previous = first; 
       first->next = first->previous = ptr; 
      } 
      else{ 
       node *last = first->previous; 
       ptr->next = first; 
       ptr->previous = last; 
       last->next = ptr; 
       first->previous = ptr; 
      } 
     } 
    } 


    int _tmain(int argc, _TCHAR* argv[]) 
    { 
     d_list aa; 
     cout<<"going to append first"<<endl; 
     aa.append(44); 
     cout<<"going to append second"<<endl; 
     aa.append(50.5); 

     return 0; 
    } 

Answer 4

你爲什麼要插入的聲明node *ptr;和node *toinsert;，如果你不使用它們？另外它應該很明顯，如果你在最後插入單個節點，那麼應該只創建一個新元素（如果第一個元素爲空，你可以調用new兩次）。

Answer 5

試試這個代碼...

class d_list 
{ 


private: 
     struct node 
     { 
     double data; 
     node *next; 
     node *previous; 
    }; 
     node *first; 
    node *last ; 

public: 
    d_list(void) 
    { 
     first = nullptr; 
     last = nullptr; 
    }; 

    void append(double); 
    }; 

void d_list::append(double num) 
{ 
    node *ptr; 
    node *toinsert; 
    if(!first) 
    { 
     first = last = new node; 
     first->previous= nullptr; 
     first->next = nullptr; 
     first->data = num; 
    } 
    else 
    { 
      ptr = new node; 
      ptr->next =last->previous; 
      ptr->data=num; 
      last->previous = ptr->next ; 
    } 
    } 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    d_list aa; 
    cout<<"going to append first"<<endl; 
    aa.append(44); 
    cout<<"going to append second"<<endl; 
    aa.append(50.5); 
     return 0; 
}