在構造函數中分配雙向鏈表指針

Question

我正在嘗試爲雙向鏈表創建幾個節點並將它們打印出來。所以我創建我dnode類：

template <typename T> 
class dnode 
{ 
    public: 
     T nodeValue; 
     dnode<T> *prev; 
     dnode<T> *next; 

     dnode() : prev(this), next(this) {} 

     dnode(const T& item, dnode<T> *prevNode = NULL, dnode<T> *nextNode = NULL) : 
      nodeValue(item), prev(prevNode), next(nextNode) {} 

}; 

然後我有我寫列表功能：

template <typename T> 
void writeDLinkedList(dnode<T>* header, const string& seperator = " ") 
{ 
    dnode<T> *p = header->next; 

    while (p != header) 
    { 
     cout << p->nodeValue << seperator; 
     p = p->next; 
    } 

    cout << endl << endl; 
} 

在主，我創建了一個頭指針和兩個節點，使用constuctor分配一個和下一個節點在通知列表中：

dnode<int> *header, *one, *two; 

header = new dnode<int>(0, two, one); 
one = new dnode<int> (10, header, two); 
two = new dnode<int> (25, one, header); 

writeDLinkedList(header); 

當我調用writeDLinkedList時，出現分段錯誤。我很困惑，所以我最終嘗試單獨輸出每個節點值，看看指針是否正常工作。事實證明，他們不是。相反，我必須這樣做，以獲得打印功能正常工作：

header = new dnode<int>; 

one = new dnode<int> (10); 
two = new dnode<int> (25); 
header->next = one; 
one->next = two; 
two->next = header; 

writeDLinkedList(header); 

我想知道爲什麼我的構造函數不工作應該的方式。它是初始化列表嗎？

Answer 1

您的構造函數正在工作。問題在於你在賦值之前使用變量。

dnode<int> *header, *one, *two; 
// one and two have undefined values at this point 

header = new dnode<int>(0, two, one); 
// so undefined values get put into header->next and header->prev 

在一個雙向鏈表，你有指針週期，節點A指向指向回節點A.根據定義指針週期不能只在構造函數來創建節點B.因爲節點A或節點B必須首先創建。由於該另一個節點尚不存在，因此無法創建指向另一個節點的先前創建的節點。

雙鏈表比你想象的要複雜一點。

Answer 2

您沒有正確管理節點。試試這個：

template <typename T> 
class dnode 
{ 
    public: 
     T nodeValue; 
     dnode<T> *prev; 
     dnode<T> *next; 

     dnode() : prev(NULL), next(NULL) {} 

     dnode(const T& item, dnode<T> *prevNode = NULL) : 
      nodeValue(item), prev(prevNode), next(NULL) 
     { 
      if (prev) 
      { 
       if (prev->next) 
        prev->next->prev = this; 
       prev->next = this; 
      } 
     } 

     ~dnode() 
     { 
      if (prev) 
       prev->next = next; 

      if (next) 
       next->prev = prev; 
     } 
}; 

。

template <typename T> 
void writeDLinkedList(dnode<T>* header, const string& seperator = " ") 
{ 
    dnode<T> *p = header; 

    while (p != NULL) 
    { 
     cout << p->nodeValue << seperator; 
     p = p->next; 
    } 

    cout << endl << endl; 
} 

。

dnode<int> *header, *one, *two; 

header = new dnode<int>(0); 
one = new dnode<int> (10, header); 
two = new dnode<int> (25, one); 

writeDLinkedList(header); 

Answer 3

我想你正在嘗試創建雙向循環列表。您可以先創建單個節點然後連接它們。在連接兩個節點後，在雙向循環列表中，必須將最後一個節點連接到第一個節點以關閉循環。 你可能想嘗試類似的東西。我已經完成了int，但它可以很容易地放入模板中。

#include<iostream> 

class dnode 
{ 

public: 

    dnode(int a):prev(this), next(this), nodeValue(a) 
    {} 
    void connectNode(dnode *newNode) 
    { 
     if(newNode != NULL) 
     { 
      dnode*head = this->next; 
      this->next = newNode; 
      newNode->prev = this; 
      newNode->next = head; 
      head->prev = newNode; 
     } 
    } 

    void writeDNode() 
    { 
    dnode *p = this->next; 
     while(p != this) 
     { 
      std::cout<<"Element "<<p->nodeValue<<std::endl; 
      p = p->next; 
     } 
    } 
private: 
    int nodeValue; 
    dnode *prev; 
    dnode *next; 

}; 


int main(int argc, char*argv[]) 
{ 
    dnode* header = new dnode(-1); 
    dnode *one = new dnode(23); 
    dnode *two = new dnode(45); 
    dnode *three = new dnode(67); 
    header->connectNode(one); 
    one->connectNode(two); 
    two->connectNode(three); 
    header->writeDNode(); 
    std::getchar(); 



}