C++で単一リンクリストを作成するためのいくつかのポインタ

Question

Shapeという共通の抽象基底クラスから派生した異なるオブジェクトを含む単一リンクリストを実装する必要があるuni割り当てがあります。

クラスの実装では、GitHubにリンクします：shapes.h、shapes.cppです。これまではShapeとその派生クラスCircleで構成されています。また、Rectangle,Point、Polygonとなります。

これらの異なる種類のシェイプの1つのリンクリストを実装する必要があります。これまでのところ私はList級とNode -classのための以下のクラスのプロトタイプを作ってみた：

要素を追加する void Append(Shape& inData) -objectは、次のスタイルで、メインから呼ばれることができるはず ShapeListに

class Node 
{ 
public: 
    Node() {} 

    friend class ShapeList; 

    private: 
    Shape* data; 
    Node* nextNode; 
}; 

class ShapeList 
{ 
public: 
    ShapeList(){head = NULL;} 
    void Append(Shape& inData); 

private: 
    Node* head; 
}; 

：

ShapeList list1; 

list1.Append(Circle(5,5,5)); 
list1.Append(Rectangle(4, 10, 2, 4)); 

void Append(Shape& inData)を実装するにはどうすればよいですか？私はいくつかの異なるアプローチを試しましたが、これまでのところ正しい解決策を思い付いていません。

Appendへのパラメータは、(Shape& inData)以外の値にすることも完全に可能です。

編集：

私はAppend(Shape& inData)を実装しましたが、それは時々しか動作します：

ShapeList list1; 
list1.Append (Circle(5,5,5)) 

と

Circle circle1; 
ShapeList list1; 
list1.Append(circle1); 

ではなく、次のようにこれまでのところ、私のAppend() -Implementationが見えます：

void ShapeList::Append(Shape& inData) 
{ 
    //Create a new node 
    Node* newNode = new Node(); 
    newNode->data=&inData; 
    newNode->nextNode=NULL; 

    //Create a temp pointer 
    Node *tmp = head; 

    if (tmp != NULL) 
    { 
     //Nodes already present in the list 
     //Traverse to the end of the list 
     while(tmp->nextNode != NULL) 
      tmp = tmp->nextNode; 

     tmp->nextNode=newNode; 
    } 

    else 
     head=newNode; 
} 

それはあなたに大丈夫ですか？ここで

Answer 1

はSTL単独リンクリストに示された多型の要件（のstd :: shared_ptrの）を、処理するための一つの方法です...ここで

typedef forward_list<shared_ptr<Shape>> ShapeList; 

ShapeList list1; 

list1.push_back(make_shared<Circle>(5,5,5)); 

list1.push_back(make_shared<Rectangle>(4, 10, 2, 4)); 

は、それがノードに影響を与えるだろうかです：

class Node 
{ 
public: 
    Node() {} 

    friend class ShapeList; 

    private: 
    shared_ptr<Shape> data; 
    Node* nextNode; 
}; 

とShapeList ...

class ShapeList 
{ 
public: 
    ShapeList(){head = NULL;} 
    void Append(const shared_ptr<Shape>& inData); 

private: 
    Node* head; 
}; 

Answer 2

1. あなたPR NodeをShapeListの内部にネストする必要があります。したがって、そのフルネームはShapeList::Nodeで、::Nodeではありません。
2. Nodeはリモートでデータを所有するため、おそらく大きな3つを定義する必要があります。
3. これに沿って、リストに何かを押すと、リストには元のオブジェクトではなく動的に割り当てられたコピーが保持されます。

編集：Appendは、Shape &ではなくShape const &となります。 constへの参照は一時オブジェクトにバインドできますが、非constへの参照はできません。したがって、一時オブジェクトを作成するパラメータを使用する呼び出し（たとえばlist.Append(Circle(5,5,5))）は、パラメータが非constオブジェクトへの参照であればコンパイルされません。

Node::Nodeにもパラメータを渡す必要があります。つまり、あなたのリンクリストコードは、私が望む以上にノードの内部を扱っています。代わりに、APPENDで次に

Node::Node(Shape const *d, Node *n=NULL) : data(d), nextNode(n) {} 

：

Node* newNode = new Node(); 
newNode->data=&inData; 
newNode->nextNode=NULL; 

あなたが好きなものを使用したい：私のようなものに変更したい

Node *newNode = new Node(&inData); // or, probably, `... = new Node(inData.clone());` 

を...とノードのctorのそこから物事を処理するだろう。

にリンクリストの末尾よりを追加する方が簡単です（リスト全体を歩くことができなくなります）。最後に追加したいのであれば、追加した最後のノードへのポインタを保存する価値があるので、毎回リスト全体を歩くのではなく、最後に直接行くことができます。

Answer 3

「宿題」でタグ付けされているので、私はあなたに良い方向を指摘します。これはあまりにも基本的なものかもしれませんが、おそらくそれで十分です。

標準的な状況では、std :: listのようにすでに書かれているコンテナを使用するだけです。

しかし、あなたはShapeListのヘッド部材から開始すると、あなた自身のリンクリスト

を実現するために、あなたは「NEXTNODEは」割り当てされていないいるノードをリスト全体を横断し、見つけることができるはずです。

新しいノードを追加する場所です。

今、あなたの事を動作させることにするいくつかのトリック：C++で

の1-は、変数は自動的に初期化されません。したがって、新しいノード、特に次のノードポインタを作成するときに、多くの値を初期化する必要があります。

2リファレンスへのポインタを持つ代わりに、コピーを避けるためにスマートポインタを使用するか、Shapesのコピーを作成することをお勧めします。

3メモリ管理について忘れないでください。リンクされたリストを破棄すると、以後、すべてのノードを個別に破棄する必要があります。

Answer 4

単独リンクされたリストの非常に優れた実装の1つは、 "head"ポインタがテールを​​指している循環リストです。これにより、正面に挿入したり、最後に追加したりすることが容易になります。どちらの場合も、新しいノードを作成し、現在の尾をポイントにして、現在のヘッドをポイントするようにします。 headポインタが新しいノードを指すようにします。

あなたが実際にリストを作成したことを知っている方法が分かっています（既に指摘されていること以外は、ノードの割り当て、割り当て解除、コピーを行っています）。したがって、オペレータ< <やprint（）ルーチンのような出力を追加して、リストを歩き回り、グラフィカルオブジェクトの印刷メカニズムを順番に呼び出すことができます。

Appendの引数がShape &dataではない可能性があります。指定された呼び出し規約の要件を考慮すると、次のようになります。

Append(const Shape &data) // provided shapes have copy constructors 
    { 
    Node *newNode = new Node(data); // requires a constructor of Node that copies data to a freshly allocated location and sticks a pointer to that location in its data field - then Node's destructor needs to release that pointer. 
    ... (and the code to manipulate the existing list and newNode's next pointer) 
    } 

これは、管理の責任を明確かつ単純にします。

ノードとシェイプの両方のポインタを取得するNodeコンストラクタを使用している場合、新しいノードを割り当てて適切にコンストラクタを呼び出す方法と、ポインタを変更する方法の2つの行でAppendを実行できます。新しいノードをポイントします。

私はあなたの編集に基づいて追加します - あなたは絶対に割り当てをして、Appendの中にコピーする必要があります。