-3

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

クラスの実装については、GitHub にリンクします: shape.h、shapes.cpp。これまでのところ、Shapeとその派生クラスで構成されていCircleます。Rectangle、以降もありPointますPolygon。

ここで、これらのさまざまな種類の形状の単一リンク リストを実装する必要があります。これまでのところ、List-class と -classの次のクラス プロトタイプを作成しましたNode。

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;
};

void Append(Shape& inData)-objectへの要素の追加ShapeListは、次のスタイルで main から呼び出すことができる必要があります。

ShapeList list1;

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

この情報が与えられた場合、どのように実装すればよいvoid Append(Shape& inData)ですか? 私はいくつかの異なるアプローチを試みましたが、これまでのところ正しい解決策を思いつきませんでした.

パラメータ toAppendが 以外のものであることも完全に可能です(Shape& inData)。

編集：

私は実装しましAppend(Shape& inData)たが、時々しか機能しません:

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

しかし、一緒ではありません

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

これまでのところ、私のAppend()実装は次のようになります。

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;
}

それは大丈夫ですか？

4

4 に答える 4

1
  1. Nodeの中に入れ子にしたいShapeListので、フルネームShapeList::Nodeは だけではなく になり::Nodeます。
  2. は一部のデータをリモートで所有するためNode、おそらくビッグ 3 を定義する必要があります。
  3. それに沿って、リストに何かをプッシュすると、リストは元のオブジェクトではなく、動的に割り当てられたコピーを保持します。

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

Node::Nodeまた、パラメーターを 1 つまたは 2 つ渡す必要があるように変更します。現状では、あなたの連結リスト コードは、私が望む以上に Node の内部を扱っています。私はそれを次のように変更します：

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 がそこから物事を処理します。

また、リンクされたリストの最後に追加するよりも最初に追加する方が簡単であることに注意してください(リスト全体をたどる必要がありません)。最後に追加したい場合は、最後に追加したノードへのポインターを保存することをお勧めします。これにより、毎回リスト全体を確認するのではなく、直接最後に移動できます。

于 2012-04-10T17:27:29.207 に答える
1

これは「宿題」でタグ付けされているので、良い方向だけを示します。これは基本的すぎるかもしれませんし、あなたのニーズには十分かもしれません...

典型的な状況では、std::list などの既に作成されているコンテナーを使用するだけです。

ただし、独自のリンクリストを実装する場合

ShapeList の head メンバーから開始すると、リスト全体をトラバースして、「nextNode」が割り当てられたことのないノードを見つけることができるはずです。

これは、新しいノードを追加する場所です。

次に、物事を機能させるためのいくつかのトリックを示します。

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

2- 参照へのポインターを使用する代わりに、シェイプのコピーを作成するか、ある種のスマート ポインターを使用してコピーを回避することをお勧めします。

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

于 2012-04-10T17:27:48.130 に答える
1

単一リンク リストの非常に優れた実装の 1 つは、「先頭」ポインタが末尾を指す循環リストです。これにより、先頭への挿入または末尾への追加が簡単になります。どちらの場合でも、新しいノードを作成し、現在の末尾をそのノードに向け、現在の先頭を指すようにします。ヘッド ポインタは新しいノードを指します。

不足しているように見えるもの (既に指摘されているもの以外: ノードの割り当て、割り当て解除、およびコピー) は、実際にリストを作成したことを知る方法です。そのため、何らかの出力を追加する必要があります。演算子 << または 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 と Shape の両方へのポインターを受け取る Node コンストラクターがある場合、Append を 2 行で実行できるはずです。ノード。

あなたの編集に基づいて、追加内で割り当てとコピーを行う必要があることを追加します。

于 2012-04-10T17:46:56.923 に答える
0

これは、多態性要件 (std::shared_ptr) を処理する 1 つの方法であり、STL 単一リンク リストで示されています...

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;
};

そしてシェイプリスト...

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

private:
    Node* head;
};
于 2012-04-10T17:23:23.983 に答える