Связанный список: Ошибка сегментации

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 в вашем случае

б) Вы не инициализирующий ->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. Если вы посмотрите на него в отладчике, голова будет по-прежнему 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-мышления и начать вас по пути к инкапсуляции.

Обычно каждый элемент в связанном списке называется «узлом», а для каждого узла есть указатель на один или несколько других узлов в списке. В «односвязном списке» он находится на следующем узле, в «двусвязном списке» есть указатель на узел до и после узла, чтобы мы могли вернуться назад, а также вперед.

Важным ранним решением является то, как вы хотите инкапсулировать это указание. Вы можете выбрать либо простой класс «Узла», либо личный класс List, который имеет предыдущие/следующие указатели и дискретный указатель «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; 
      } 
     } 

Надеется, что это достаточно, чтобы дать вам много идей :)