在C++中创建单向链表的一些指针

Question

我有一个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; 
}; 

添加元素void Append(Shape& inData)为ShapeList -object应该能够从主在下面的风格被称为：

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)但它只能有时：

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

这对你们看起来好吗？

Answer 1

这里是处理多态的要求（的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)); 

这里是它会如何影响节点：

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. 与此相符的是，当您将某些东西推到列表上时，列表将包含动态分配的副本，而不是原始对象。

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

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

...和节点的构造函数会从那里处理事情。

另请注意，将链表添加到开始的比将其添加到结尾更容易（它可以帮助您避免走遍整个列表）。如果你真的希望添加到最后，那么将指针保存到你添加的最后一个节点可能是值得的，所以你可以直接到最后，而不是每次遍历整个列表。

Answer 3

由于这是在'家庭作业'标签下，我只会指出你的好方向。这可能太基本了，或者它可能足以满足您的需求...

在一个典型的情况下，您只需使用已经写入的容器，如std :: list。

但对于实现自己的链表

当您从ShapeList的头部件开始，你应该能够遍历整个列表，并找到其“nextNode”从未分配的节点。

这是您要添加新节点的位置。

现在你一个几招，可以使事情的工作：

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

2-我不建议使用指向引用的指针，而是要创建Shapes的副本，使用某种智能指针来避免复制。 3-不要忘记内存管理，当你销毁链表时，你将不得不单独销毁所有节点。

Answer 4

单链表的一个非常好的实现是作为一个圆形列表，其中“头”指针指向尾部。这样可以很容易地在前面或后面插入：在任何一种情况下，您都可以创建一个新节点，使其成为当前尾点，并使其指向当前头，然后在插入案例中使头指针指向新节点。

你看起来缺少的东西（除了已经指出的内容：分配，释放和复制节点）是一种知道你已经创建了列表的方法。因此，您需要添加某种输出 - 可以是运算符< <或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 - 一个分配新节点并适当地调用构造函数，另一个修改指向指向新节点。

我会添加 - 基于您的编辑 - 你绝对需要做Append中的分配和复制。