c++ - C++中的简单链表实现

Question

我是第一门 C++ 类(class)的编程学生，最近我们学习了链表，我们被分配了一项任务来实现一个简单的链表。除了我的 pop_back() 函数，我已经编写了所有代码，该函数应该返回指向需要在 Main() 中删除的 Node 的指针>。实际函数中不需要删除Node。所以我的问题是:

您愿意为我的 pop_back() 功能指明正确的方向吗？另外，如果您发现我做错了什么，请告诉我。

另外，这个链表只是用来处理字符串的。在本例中，一个杂货 list ，一个字符串表示商品数量 (1,2)，一个字符串表示商品类型。 (牛奶、鸡蛋等)

下面我包含了我的 List 和 Node 类实现，因此您可以了解我到目前为止所做的事情。

Node.cpp

Node::Node(void)
{
    descrip = " ";
    quantity = " ";
    previous = NULL;
    next = NULL;
}
Node::Node(string q, string d)
{
    descrip = d;
    quantity = q;
    previous = NULL;
    next = NULL;
}
Node* Node::GetNext()
{
    return next;
}
Node* Node::GetPrevious()
{
    return previous;
}
void Node::SetNext(Node * setter)
{
    next = setter;
}
void Node::SetPrevious(Node * setter)
{
    previous = setter;
}

---

列表.cpp

List::List(void)
{
   first = NULL;
   last = NULL;
   numNodes = 0;
}
Node* List::GetFirst()
{
    return first;
}
Node* List::GetLast()
{
    return last;
}
void List::SetFirst(Node* setter)
{
    first = setter;
}
void List::SetLast(Node* setter)
{
    last = setter;
}
int List::GetNumNodes()
{
    return numNodes;
}
void List::push_front(Node* item)
{
   if (first == NULL)
   {
       first = item;
       last = item;
   }
   else 
   {
       Node* pFirst = first;
       item->SetNext(pFirst);
       first = item;
       numNodes++;
   }
}
void List::push_back(Node * item)
{
    if (last == NULL)
    {
       first = item;
       last = item;
    }
    else 
    {
        last->SetNext(item);
        last = item;
        numNodes++;
    }
}
Node* List::pop_front()
{
    Node* temp = first;
    first = first->GetNext();
    if (first == NULL)
    {
        temp = first->GetNext();
        first = p;
    }
    if (first == NULL)
    {
        last = NULL;
    }
    if (numNodes > 0)
    {
        numNodes--;
    }
    return temp;
}
Node* List::pop_back() // this whole function may be wrong, this is just my attempt at it
{
    Node* temp;
    temp = first;

    while((temp->GetNext()) != NULL)
        // im stuck here

}

Answer 1

一些提示:

0x1243bfa3
0x45afc56e
0xdeadbeef

一些提示:

1. 您应该更喜欢在初始化列表中初始化您的类成员，而不是在构造函数的主体中。

2. 在 C++ 中，与 C89 不同，我们声明和定义一个没有参数的函数为 void f();。 , 不是 void f(void); .

3. 在 C++ 中，我们通常使用 0 重置指针, 不是 NULL .

   请参阅下文了解我在代码中的意思。

4. 好的 C++ 代码会尝试利用 RAII .这意味着在很大程度上避免使用原始指针。在这种情况下，普通旧 std::auto_ptr<>可以完全替代原始 Node*指针。但是，我确实认为这里的部分练习是指针算术，所以我将其作为旁注。

5. 如果您附上类声明，这对我们会很有用。我假设所有这些访问器和修改器，GetFirst()和 SetFirst()等等，因为它们是公开的。这是个坏主意。首先，它们公开了私有(private)指针，这破坏了整个访问点。其次，他们没有做任何特别的事情，所以他们只是额外的代码——这意味着额外的错误空间。这让我想到了下一点。

6. 您的修改器不正确。您盲目地为私有(private)成员指针分配一个新值，而没有删除之前的值。那是内存泄漏。

7. 曾经尝试过pop_front()当列表为空时？

8. 最后，8 是一个整数，是时候让我们开始讨论手头的问题了。 pop_back() .我要问你的问题是，如果你如此小心翼翼地维护指向列表最后一个节点的指针，为什么要一直遍历列表到最后？事实上，如果您不愿意维护指向列表末尾的指针，那么您必须一直遍历到最后一个节点才能弹出它。为此，您的方向是正确的。除了……

9. 当您通过指针访问成员时，如 first->GetNext() ，总是确保first不是空指针——或者在函数的文档注释中说明您假定指针不为空。

这些应该可以帮助您入门。

代码中的第 1、2 和 3 点:

Node::Node()
: descrip(" "), quantity(" "), previous(0), next(0)
{
}