草庐IT

关于 c : 擦除链表的正确方法

codeneng 2023-03-28 原文

Correct way of erasing a linked list

假设，我有一个单链表，它的基本组成部分是，

struct Node {
  Data d;
  Node *pNext;
  // methods
  ~Node();
};

链表的头部存储为，

Node *m_Head; // member of some class

当我完成列表时，我将通过删除每个节点来清理它，

void Erase()
{
  Node *pIter, *pTemp = m_Head;
  while((pIter = pTemp) != 0)
  {
    pTemp = pIter->pNext;
    delete pIter;
    pIter = pTemp;
  }
}

我想，如果我能简化一下。所以我想出了一个主意，我可以用一条指令清理整个链表！

delete m_Head;

和析构函数看起来像：

Node::~Node() { delete this->pNext; }

我担心的是，它会导致递归(隐含地由于delete)吗？如果是，那么对于更大的链表来说绝对是一个问题。编译器能以任何方式帮助优化吗？

[注意：不使用任何库工具，如 std::list 或其他。]

  • 注意，如果你选择了后面的【使用删除】，在删除前【修改列表时，不要销毁】必须设置node->pNext = NULL;，否则会丢失这个子列表的尾部。

我想你要问的问题是，列表中的每个 Node 是否都拥有它的 pNext Node？如果不是，那么它就没有必要在其析构函数中删除其 pNext 节点。

在大多数链表实现中，所有节点都归链表所有，一个节点并不拥有链表中它之后的所有节点。将节点保持为哑(POD 结构)并让所有逻辑驻留在列表中更有意义。

您的节点具有析构函数但没有复制构造函数或复制赋值运算符，这绝对是一种设计"气味"。我认为当您编写实现插入、拼接和擦除单个元素功能的代码时，这种方法会导致更多复杂性，因为在任何情况下您都必须手动管理 pNext 指针，以避免无意破坏列表的整个尾部。

  • 在 cons 列表中，一个节点拥有它之后的那些似乎很自然，因为定义是 List a = Empty | Cons a List。我同意它需要小心操作。

当然：仅出于学习目的或确定自己的 List 确实更适合您的用例时才这样做

这取决于。您的编译器可能会检测到尾递归并发出在概念上等同于使用循环的代码。

如果不是，那么是的，它将递归。通常，如果堆栈压力很小(如您的情况)，商品盒上应该可以进行数千次递归。但是，不能保证，事实上，对于非常大的列表，这可能是一个问题。

另外，我认为递归确实不完全适合兄弟节点的概念。一个节点层次结构，就像四叉树一样，需要递归，但是当列表概念与兄弟节点有关时，我在递归(形成调用层次结构)方面的思考不是很好。

您也可以将手动循环视为对递归的一种易于实现的优化，它可以保证您的代码更加健壮。

顺便说一句，您也可以将删除的节点删除到持有者类中：

class List {
public:
    ~List() {
        for-each-node
            delete-node
    }

private:
    class Node {
        Node *node_;
        ...
    };
    ...
};

这基本上是标准库的列表通常是如何实现的。它使整个实现更容易实现并且在概念上更正确(节点在逻辑上不拥有它们的兄弟)

  • AFAIK，Data 成员(和 Node 的基类)的破坏发生在 Node 析构函数调用的末尾，这使得它根本不是尾递归的(除非所有这些都是空操作并优化了)。

大多数编译器在默认设置中进行尾调用消除。一些更聪明的可以将非尾调用转换为尾调用。

所以，只要你开启了一些优化，这个方法就可以了。

原始指针？手动调用 delete ?

为什么不呢，简单地说：

struct Node {
  Data d;
  std::unique_ptr<Node> next;
};

那你根本不用担心内存管理，它是自动的！

  • 实际上，这会产生递归，但这会阻止stackoverflow吗？这是问题的主要关注点。
  • @stefaanv：开放主题。这取决于编译器和标准库的实现，我希望是这样，但这是猜测。我不知道标准是否Promise最小递归深度，如果它不关心这一点，我不会感到惊讶。

关于擦除spanclasssectionc++linked-listmemory-managementrecursion

有关关于 c : 擦除链表的正确方法的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  4. ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2

    我正在尝试设置一个puppet节点，但ruby​​gems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter，它工作正常，但如果我通过由ruby​​gems(/usr/bin/facter)安装的二进制文件，它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby

  5. Ruby 方法() 方法 - 2

    我想了解Ruby方法methods()是如何工作的。我尝试使用“ruby方法”在Google上搜索，但这不是我需要的。我也看过ruby​​-doc.org，但我没有找到这种方法。你能详细解释一下它是如何工作的或者给我一个链接吗？更新我用methods()方法做了实验，得到了这样的结果:'labrat'代码classFirstdeffirst_instance_mymethodenddefself.first_class_mymethodendendclassSecond使用类#returnsavailablemethodslistforclassandancestorsputsSeco

  6. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

    我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

  7. ruby - Highline 询问方法不会使用同一行 - 2

    设置:狂欢ruby1.9.2高线(1.6.13)描述:我已经相当习惯在其他一些项目中使用highline，但已经有几个月没有使用它了。现在，在Ruby1.9.2上全新安装时，它似乎不允许在同一行回答提示。所以以前我会看到类似的东西:require"highline/import"ask"Whatisyourfavoritecolor?"并得到:Whatisyourfavoritecolor?|现在我看到类似的东西:Whatisyourfavoritecolor?|竖线(|)符号是我的终端光标。知道为什么会发生这种变化吗？ 最佳答案

  8. ruby-on-rails - 如何使用 instance_variable_set 正确设置实例变量？ - 2

    我正在查看instance_variable_set的文档并看到给出的示例代码是这样做的:obj.instance_variable_set(:@instnc_var,"valuefortheinstancevariable")然后允许您在类的任何实例方法中以@instnc_var的形式访问该变量。我想知道为什么在@instnc_var之前需要一个冒号:。冒号有什么作用？ 最佳答案 我的第一直觉是告诉你不要使用instance_variable_set除非你真的知道你用它做什么。它本质上是一种元编程工具或绕过实例变量可见性的黑客攻击

  9. ruby - 主要 :Object when running build from sublime 的未定义方法 `require_relative' - 2

    我已经从我的命令行中获得了一切，所以我可以运行rubymyfile并且它可以正常工作。但是当我尝试从sublime中运行它时，我得到了undefinedmethod`require_relative'formain:Object有人知道我的sublime设置中缺少什么吗？我正在使用OSX并安装了rvm。 最佳答案 或者，您可以只使用“require”，它应该可以正常工作。我认为“require_relative”仅适用于ruby​​1.9+ 关于ruby-主要:Objectwhenrun

  10. ruby - 多个属性的 update_column 方法 - 2

    我有一个具有一些属性的模型:attr1、attr2和attr3。我需要在不执行回调和验证的情况下更新此属性。我找到了update_column方法，但我想同时更新三个属性。我需要这样的东西:update_columns({attr1:val1,attr2:val2,attr3:val3})代替update_column(attr1,val1)update_column(attr2,val2)update_column(attr3,val3) 最佳答案 您可以使用update_columns(attr1:val1,attr2:val2

随机推荐