鏈接列表：分段錯誤

Question

我想嘗試此頁面上鍊接列表的示例：How to create Linked List using C++。
這是我到目前爲止的代碼：

#include <iostream> 
using namespace s-td; 

class node { 
public: 
    int value; 
    node *next; 
}; 

int main() { 
    node *head = nullptr; 

    node *temp1; 
    temp1 = new node(); 
    temp1->value = 1; 
    temp1 = head; 

    while(temp1->next!=nullptr) { 
     temp1 = temp1->next; 
    } 
    return 0; 
} 

但不幸的是，我得到一個Segmentation fault。 我覺得這部分是錯誤的：

while(temp1->next!=nullptr) { 
    temp1 = temp1->next; 
} 

Answer 1

兩件事情是你的代碼錯誤：

一）要指定temp1 = head，這是同義temp1 = nullptr你的情況

b）您沒有初始化->next是nullptr，使您的while-條件可能會或可能不會被滿足（未定義行爲）

Answer 2

node *head = nullptr; 

head是NULL

temp1 = head; 

temp1成爲NULL

while(temp1->next!=nullptr) { 

temp1是NULL，因此temp1->next正在引用NULL指針。

Answer 3

您的程序開始通過列表的空指針head迭代。如果您在調試器中查看它，head將仍然爲NULL，因爲您從未設置它。

node *temp1, *temp2, *temp3; 

temp1 = new node(); 
temp1->value = 1; 
temp1->next = nullptr; 
head= temp; // link to head 

temp2 = new node(); 
temp2->value = 2; 
temp2->next = nullptr; 
temp1->next= temp2; // link 1 -> 2 

temp3 = new node(); 
temp3->value = 3; 
temp3->next = nullptr; 
temp2->next= temp3; // link 2 -> 3 

// now we have head -> temp1 -> temp2 -> temp3 

// now use temp1 as iterator starting with head 
temp1 = head; 
while(temp1->next!=nullptr) { 
    printf("%d\n", temp1->value); 
    temp1 = temp1->next; 
} 

Answer 4

您分配：

node *head = 0; 
// ... 
temp1 = head; 

while(temp1->next!=nullptr) { // temp1 is null here 
    temp1 = temp1->next; 
} 

此外temp1->next不會是空無論是。你應該初始化：

#define NULL 0 

class node { 
public: 
    node(int value, node *next) { 
     this.value = value; 
     this.next = next; 
    } 
    int value; 
    node *next; 
}; 

// .. 
node *n3 = new node(1, NULL); 
node *n2 = new node(1, n3); 
node *n1 = new node(1, n2); 

Answer 5

那篇文章給出瞭如何創建在C鏈表一個合理的解釋，它使用C++註釋，但它是如何在C++鏈表一個可怕的解釋。

讓我從那裏引導你走出C語言心態，開始你走上封裝的道路。

通常，鏈接列表中的每個元素都稱爲「節點」，並且對於每個節點都有指向列表中的一個或多個其他節點的指針。在一個「單鏈表」中，它是到下一個節點，在一個「雙鏈表」中有一個指向前一個節點的指針和之後的節點，以允許我們向後以及向前。

一個重要的早期決定是如何封裝這個指向。您可以選擇擁有一個簡單的「Node」類，它是List類的私有類，它具有prev/next指針和一個指向實際數據本身的離散「void *」指針。這是一種非常類似於C的方法，因爲它拋棄了類型信息。啊 - 但你可以將類型存儲爲枚舉或其他東西？你可以，這是一個很棒的C解決方案。

但是C++是關於封裝的。作爲列表的節點是一個定義明確且相當離散的角色，具有一組簡單的屬性和屬性。它作爲一個簡單的基類是完美的封裝。

class ListNode 
{ 
    ListNode* m_next; 
    ListNode() : m_next(NULL) {} 

    ListNode* next() { return m_next; } 

    // return the last node in my current chain. 
    ListNode* tail() { 
     ListNode* node = this; 
     while (node->next() != nullptr) 
      node = node->next(); 
     return node; 
    } 

    // insert a new node at this point in the chain, 
    // think about what happens if newNode->next() is not null tho. 
    bool linkTo(ListNode* newNode); 
}; 

一個同樣重要的封裝問題，但是，是你是否不希望任何人能一起去，並調用ListNode成員，或者如果你想自己的知名度限制列表本身的存取。當然有一些模式可以幫助處理抽象的「ListNode *」，而不需要知道它們屬於哪個列表。但是單鏈表有一定的侷限性 - 例如，不知道列表本身，你永遠不能刪除一個條目（你怎麼知道誰指着你？）

但是，這可以讓我們做

class Product : public ListNode { 
    string m_name; 
    std::vector<float> m_priceHistory; 
public: 
    Product(const std::string& name_) 
     : ListNode() 
     , m_name(name_) 
     , m_priceHistory() 
     {} 
    void save(); 
}; 

class Book : public Product { ... }; 
class DVD : public Product { ... }; 

List productList; 

productList.add(new Book("hello world")); 
productList.add(new DVD("lose wait: lose a limb")); 
productList.add(new Insurance("dietary related gangrene")); 
... 
for(ListNode* node = productList.head(); node != nullptr; node = node->next()) { 
    node->save(); 
} 

另一種方法會讓我們回到第一個ListNode的想法，更像一個C;問題不在於它使用了指針，而是它丟棄​​了類型信息。當你想說「這個指針的類型不匹配」時，「void」主要用於這種情況。缺點是，「指針的類型消失」。我們可以通過模板解決這個問題。

template<typename T> // T will be an alias for whatever type we have to deal with. 
class List 
{ 
    struct Node* m_list; 

public: 
    struct Node 
    { 
     Node* m_next; 
     T* m_data; 
     Node() : m_next(nullptr), m_data(nullptr) {} 
     Node* next() const { return m_next; } 
     bool linkTo(Node* newPredecessor); 
     bool link(Node* newFollower); 
    }; 

public: 
    List() : m_list(nullptr) {} 

    Node* head() { return m_next; } 
    Node* tail() { 
     if (m_list == nullptr) 
      return nullptr; 
     for (Node* node = m_list; node->m_next != nullptr; node = node->m_next) 
      {} 
     return node; 
    } 
    void insert(T* data) { // add to head of the list 
     Node* node = new Node(data); 
     node->m_next = m_head; 
     m_head = node; 
    } 
    Node* append(T* data) { 
     if (head() == nullptr) 
      insert(data); 
     else { 
      Node* node = new Node(data); 
      Node* tail = this->tail(); // could get expensive. 
      tail->link(node); 
     } 
     return node; 
    } 
}; 

List<Product> productList; 
productList.append(new Book("Gone with the money")); 
productList.append(new DVD("that's no moon")); 
productList.append(new Pet("llama")); 

這種方法的一個優點是我們不必爲數據的定義添加額外的成員/混亂。缺點是我們使用更多的內存 - 每個節點需要兩個指針，並且節點沒有一個簡單的方法告訴您他們是否在列表中的哪個位置（您必須搜索所有節點並找到指向您的節點項目）。

在內存分配方面還有一個由使用決定的成本/收益。

這個最新的迭代還有一個主要的C-esque組件，Node類太明顯了。理想情況下，最終用戶應該完全私密。但是由於數據元素無法確定它們在列表中的位置，因此無法在列表中查找。

你想要的是隱藏節點定義，以便只有列表可以看到它（不，沒關係，你確實不需要改變'm_next'）並創建一個提供功能的輔助類我們需要不讓我們做我們不應該做的任何事情。

public: 
    class Iterator 
    { 
     Node* m_node; 
    public: 
     Iterator(Node* node_=nullptr) : m_node(node_) {} 

     bool advance() { 
      if (isValid()) 
       m_node = m_node->m_next; 
      return isValid(); 
     } 
     T* data() { 
      return isValid() ? m_node->m_data : nullptr; 
     } 
     bool isValid() const { return (m_node != nullptr); } 
     bool isTail() const { return isValid() && (m_node->m_next != nullptr); } 

     // if you feel the need to get seriously advanced, 
     // overload operator "++" to allow ++it; 
     // overload operator "*" to allow (*it) to get m_data 
     // overload operator "=" to allow Iterator* it = list->head(); 
    }; 

    // in class list: 
     Iterator head() { return Iterator(m_head); } 
     Iterator tail() { 
      Iterator it(m_head); 
      while (!it.isTail()) { 
       it.advance(); 
      } 
      return it; 
     } 
     Iterator find(const T& data_) { return find(&data_); } 
     Iterator find(const T* data_) { 
      for (Iterator it = head(); it.isValid(); it.advance()) { 
       if(it.data() == data_) 
        return it; 
      } 
     } 

希望這是足以讓你很多的想法:)