4

我现在正在使用链表作为练习。

我在《Cracking The Coding Interview》一书中看到的示例没有 LinkedList（管理器）类，只有 Nodes，并且您在 main 函数中使用头 Node。

我查找了 C++ 实现，但大多数似乎比 C++ 更具 C 风格，即不是面向对象的。它们使用结构，没有类，并且有一个用于删除列表的静态方法，您需要明确记住调用该方法。我想用合理的析构函数编写一个合理的 RAII（资源获取即初始化）风格的 C++ 类来处理内存释放，并且我只想使用一个 Node 类（没有 LinkedList 类）。

我看到完成这项工作的唯一方法是让 Node 的析构函数删除下一个 Node（如果有的话），但我读过这种递归删除是一个坏主意，因为你最终会创建一个与链表。

所以总结一下我的问题：

  • 如果在 C++ 中编写一个面向对象的类来处理链表，是否必须有一个 LinkedList（管理器）类来处理其析构函数中列表节点的删除？
  • 如果不是，您将如何处理节点的破坏？

谢谢！

4

1 回答 1

6

如果在 C++ 中编写一个面向对象的类来处理链表，是否必须有一个 LinkedList（管理器）类来处理其析构函数中列表节点的删除？

不，结构是由节点之间的链接定义的，因此不需要单独的管理器对象。有时拥有一个会更方便，特别是如果您正在设计一个类似 STL 的库并希望所有容器都具有类似的接口，但您当然可以只使用一个节点类型来实现一个链表。

如果不是，您将如何处理节点的破坏？

避免递归的一种方法是在删除之前从列表中删除每个节点，例如：

~node() {
    while (node * victim = next) {
        next = victim->next;
        victim->next = nullptr;
        delete victim;
    }
}
于 2012-08-03T11:54:03.573 回答