1

このページのリンクされたリストの例を試してみたかった: 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;
}
4

5 に答える 5

0

あなたが割り当てているもの:

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

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

さらにtemp1->next、null にもなりません。初期化する必要があります。

#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);
于 2013-06-02T16:12:17.710 に答える
0

その記事では、C でリンク リストを作成する方法について合理的な説明があり、C++ のコメントが使用されていますが、C++ でリンク リストを作成する方法についてのひどい説明です。

そこにあるCの考え方からあなたを遠ざけ、カプセル化への道を歩み始めさせてください.

通常、リンクされたリストの各要素は「ノード」と呼ばれ、各ノードには、リスト内の 1 つ以上の他のノードへのポインターがあります。「片方向リスト」では次のノードへ、「二重方向リスト」では前のノードと後のノードへのポインターがあり、前後に移動できるようになっています。

初期の重要な決定事項は、このポイントをどのようにカプセル化するかです。前/次のポインターと、実際のデータ自体への個別の「void*」ポインターを持つ、List クラスに対してプライベートな単純な「Node」クラスを持つかどうかを選択できます。これは、型情報を破棄するため、非常に 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();
}

もう 1 つのアプローチは、最初の 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"));

このアプローチの利点は、データの定義に追加のメンバー/混乱を追加する必要がないことです。欠点は、より多くのメモリを使用することです。各ノードには2つのポインターが必要であり、ノードがリスト内にあるかどうか/どこにあるかを簡単に伝える方法がありません(すべてのノードを検索し、あなたを指すものを見つける必要があります)アイテム）。

また、メモリ割り当てに関しては、使用量によって決まるコスト/メリットもあります。

この最新のイテレーションにはまだ主要な C 風のコンポーネントがあり、Node クラスはあまりにも目立ちすぎています。理想的には、エンド ユーザーに対して完全に非公開にする必要があります。しかし、データ要素はリスト内のどこにあるかを知る方法がないため、リストをたどることは不可能です。

あなたが望むのは、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;
            }
        }

これがあなたにたくさんのアイデアを与えるのに十分であることを願っています:)

于 2013-06-02T20:29:01.340 に答える