單鏈表C++：頭指針不連接到下一個節點

對於我的任務，我必須創建一個單鏈表並插入3個項目。我嘗試使用面向對象的方法，而不是純粹的指針方法，我的老師和幾乎所有人都使用;頭部和尾部都是我的列表類的節點和屬性。我的代碼唯一的問題是頭節點的指針不會更新到下一個節點。任何人都可以幫我解決這個問題單鏈表C++：頭指針不連接到下一個節點

#include <iostream> 
using namespace std; 



class node 
{ 
public: 
    int element; 
    node* ptr; 
    friend class list; 
}; 



class list 
{ 
public: 
    //Including head and tail attributes and making them public so that 
they are easily accessible to anyone using the linked list construction 
    node head; 
    node tail; 

    list() 
    { 
     head.element = -1; //-1 is sentinel value 
     tail.element = -1; 
     head.ptr = NULL; 
     tail.ptr = NULL; 
     head = tail; 
    } 

    bool empty() 
    { 
     return((head.ptr == NULL) && (head.element == -1)); 
    } 

    void insert(int a) 
    { 
     if(empty()) 
     { 
      head.element = a; 
      tail.element = a; 
     } 

     else 
     { 
      //Making a new unnamed node, inserting the new value, and 
updating the tail attribute 
      node* v = new node; 
      tail.ptr = v; 
      v -> element = a; 
      v -> ptr = NULL; 
      tail.element = v-> element; 
      tail.ptr = v -> ptr; 
     } 
    } 

    void print() 
    { 
     int i = 0; 
     node *pointer = head.ptr; 
     while(pointer != NULL) 
     { 
      cout << "The " << i+1 << "th element is: " << pointer -> 
element; 
      pointer = pointer -> ptr; 
      i++; 
     } 
    } 

}; 



int main() 
{ 
    int values[3] = {1, 2, 3}; 
    list lst; 
    for(int i = 0; i < 3; i++) 
    { 
     lst.insert(values[i]); 
    } 

    cout << lst.head.element << endl; 
    cout << lst.tail.element; 
    lst.print(); 

};

來源

2017-10-06 arnavlohe15

「頭」和「尾」是指您構建它們的方式都完整列表。你只追尾，只能從頭上讀。 – PeterT

類和成員函數本身不會使您的程序面向對象;在C++中，OO通常具有* inheritance *和* virtual functions *。 –

另請注意，您的代碼包含無償的特殊情況。一個空列表沒有元素;引入一個帶有特殊「定點」值的需要更多的檢查，並且使得你的代碼更加複雜，更容易出錯，並且不那麼通用。你可能會得到一個降低的標記。 –

頭部和尾部節點應保持爲虛擬節點而不是列表的一部分。頭部和尾部節點的元素值不需要被初始化或檢查。非空列表的插入序列是

 // ... 
     v->ptr = head.ptr; 
     head.ptr = v; 
     // ...

查看是否可以修復其餘的代碼。

如果您創建一個附加功能，對於一個非空列表追加序列

 // ... 
     v->ptr = NULL; 
     tail.ptr->ptr = v; 
     // ..

來源

2017-10-06 22:19:57 rcgldr

謝謝你的幫助！我實際上想要製作頭尾節點，因爲它會使插入算法在O（1）時間內運行;如果尾部元素是已知的並且不斷更新，那麼每次我想添加元素時都不需要通過列表進行解析，這會花費O（n）個時間。但是你的評論確實幫助我思考如何更新指針。 – arnavlohe15

@ arnavlohe15 - 爲了清楚起見，「插入」意味着新節點位於列表的前面，或者它可能意味着新節點被插入到正確位置的排序列表中。「追加」意味着新節點在列表的末尾。這個替代術語是「push_front」，用於將新節點放在列表的開頭，「push_back」用於將新節點放在列表的末尾。 – rcgldr

哦，我看到了不同。該任務是添加新元素到列表的末尾，在這種情況下，我應該重新定義insert（）append（） – arnavlohe15

單鏈表C++：頭指針不連接到下一個節點

回答

相關問題