29

C++ でリストを作成するにはどうすればよいですか? リンクされたリストを作成するために必要です。どうすればそれを行うことができますか？私が従うことができる良いチュートリアルや例はありますか?

4

8 に答える 8

43

C++ には既にリンク リスト クラスがあることを知っていて、その方法を学びたいので、独自のリンク リスト クラスを実装したいと思っていると思います。

まず、なぜ他のデータ構造ではなく配列を使用するのかを読んでください。、基本的なデータ構造の良い答えが含まれています。次に、それらを C++ でモデル化する方法を考えます。

struct Node {
    int data;
    Node * next;
};

基本的に、リストを実装するために必要なのはそれだけです! （非常に単純なもの）。まだ抽象化されていないため、手ごとにアイテムをリンクする必要があります。

Node a={1}, b={20, &a}, c={35, &b} d={42, &c};

これで、すべてスタックに割り当てられたノードのリンク リストができました。

d -> c -> b -> a
42   35   20   1

次のステップは、開始ノードを指すラッパー クラスを記述し、List必要に応じてノードを追加できるようにし、リストの先頭を追跡することです (以下は非常に単純化されています)。

class List {
    struct Node {
        int data;
        Node * next;
    };

    Node * head;

public:
    List() {
        head = NULL;
    }

    ~List() {
        while(head != NULL) {
            Node * n = head->next;
            delete head;
            head = n;
        }
    }

    void add(int value) {
        Node * n = new Node;
        n->data = value;
        n->next = head;
        head = n;
    }

    // ...
};

次のステップは、(整数だけでなく) 他の値を詰め込むことができるように、リストをテンプレートにすることです。

スマート ポインターに精通している場合は、使用されている生のポインターをスマート ポインターに置き換えることができます。多くの場合、スターターにスマート ポインターを勧める人を見かけます。しかし、私の意見では、最初にスマート ポインターが必要な理由を理解してから使用する必要があります。ただし、そのためには、まず生のポインターを理解する必要があります。そうでなければ、なぜそれが必要なのかを知らずに、魔法のツールを使用します。

于 2008-12-29T15:51:56.180 に答える
22

標準の List クラスを実際に使用する必要があります。もちろん、これが宿題の質問であるか、またはリストが STL によってどのように実装されているかを知りたい場合を除きます。

こののように、Google を介して多くの簡単なチュートリアルを見つけることができます。リンクされたリストが「内部」でどのように機能するかを知りたい場合は、C++ ではなく C リストの例/チュートリアルを検索してみてください。

于 2008-12-29T15:23:41.010 に答える
15

を使用する場合はstd::list、型パラメーターを渡す必要があります。

list<int> intList;  
list<int>* intListPtr = new list<int>;

リストがどのように機能するかを知りたい場合は、その主題を理解するために、いくつかの C/C++ チュートリアルをグーグルで検索することをお勧めします。次のステップは、C++ を十分に学習してリスト クラスを作成し、最後にリスト テンプレート クラスを作成することです。

さらに質問がある場合は、ここに戻って質問してください。

于 2008-12-29T15:33:06.280 に答える
9

車輪を再発明する理由。STL リスト コンテナーを使用するだけです。

#include <list>

// in some function, you now do...
std::list<int> mylist; // integer list

詳しくは...

于 2008-12-29T15:23:56.753 に答える
0

ブースト ptr_list

http://www.boost.org/doc/libs/1_37_0/libs/ptr_container/doc/ptr_list.html

HTH

于 2008-12-29T17:00:09.087 に答える
0

これは宿題の質問だと思うので、おそらくここに行きたいと思うでしょう。リンクされたリストを説明するチュートリアルがあり、優れた擬似コードを提供し、ダウンロードできる C++ 実装もあります。

盲目的に実装を使用する前に、説明を読み、疑似コードを理解することをお勧めします。これは、CS を続けたいのであれば、深く理解しておくべきトピックです。

于 2008-12-29T15:38:12.713 に答える
-3

もう21世紀です！！既存のデータ構造を実装しようとしないでください。既存のデータ構造を使用してみてください。

STL または Boost ライブラリを使用する

于 2008-12-29T15:25:44.783 に答える