-3

我有一个 uni 分配，我必须在其中实现一个单链表，其中包含从称为 Shape 的通用抽象基类派生的不同对象。

我将链接到 GitHub 以获取类实现：shapes.h、shapes.cpp。到目前为止，它由Shape及其派生类组成Circle。也会有Rectangle，Point以后还会有Polygon。

我现在应该实现这些不同形状的单链表。到目前为止，我已经为List-class 和Node-class 提出了以下类原型：

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

应该能够以以下样式从 main 调用向 -objectvoid Append(Shape& inData)添加元素：ShapeList

ShapeList list1;

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

鉴于这些信息，我应该如何实施void Append(Shape& inData)？我尝试了几种不同的方法，但到目前为止还没有提出正确的解决方案。

参数 to 也完全有可能Append不是(Shape& inData).

编辑：

我已经实现Append(Shape& inData)了，但它只在某些时候有效：

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

但不与

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

到目前为止，我的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;
}

你们觉得这样好吗？

4

4 回答 4

1
  1. 你可能想Node嵌套在里面ShapeList所以它的全名将是ShapeList::Node，而不仅仅是::Node.
  2. 由于Node将远程拥有一些数据，因此您可能需要为其定义三巨头。
  3. 与此一致，当您将某些内容推送到列表时，列表将保存动态分配的副本，而不是原始对象。

编辑：Append应该采用 aShape const &而不是 a Shape &。对 const 的引用可以绑定到临时对象，但对非 const 的引用不能，因此list.Append(Circle(5,5,5))如果参数是对非 const 对象的引用，则使用创建临时对象（例如 ）的参数的调用将无法编译。

我还会更改Node::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());`

...并且 Node 的 ctor 会从那里处理事情。

另请注意，添加到链表的开头比添加到末尾更容易（它可以避免您遍历整个列表）。如果你真的想添加到最后，可能值得保存一个指向你添加的最后一个节点的指针，这样你就可以直接到最后，而不是每次都遍历整个列表。

于 2012-04-10T17:27:29.207 回答
1

由于这被标记为“作业”，我只会为您指出好的方向。这可能太基本了，或者可能足以满足您的需求......

在典型情况下，您只需使用已经编写好的容器，例如 std::list。

但是为了实现你自己的链表

当您从 ShapeList 的头成员开始时，您应该能够遍历整个列表并找到从未为其分配过 'nextNode' 的节点。

这是您要添加新节点的地方。

现在你有一些技巧可以让事情顺利进行：

1- 在 C++ 中，变量不会自动初始化。因此，您必须在创建新节点时初始化许多值，尤其是下一个节点指针。

2-我建议不要使用指向引用的指针，而是创建形状的副本，或者使用某种智能指针来避免复制。

3-不要忘记内存管理，当您销毁链表时，您将不得不单独销毁所有节点。

于 2012-04-10T17:27:48.130 回答
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 构造函数，它同时接受一个指向 Node 和一个 Shape 的指针，你应该能够在两行中执行 Append - 一行分配新 Node 并适当地调用构造函数，另一行修改指针以指向新的节点。

我会添加 - 根据您的编辑 - 您绝对需要在 Append 中进行分配和复制。

于 2012-04-10T17:46:56.923 回答
0

这是处理多态要求（std::shared_ptr）的一种方法，用 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));

以下是它对 Node 的影响：

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 回答