在perl中创建链接列表中的NEXT的含义

所以我想用Perl学习链接列表。我正在阅读Jon Orwant的Mastering Algorithms with Perl。在书中他解释了如何创建链表。我明白其中的大部分内容，但我只是无法理解代码段第二行中的命令/索引/键NEXT。在perl中创建链接列表中的NEXT的含义

$list=undef; 
$tail=\$list; 

foreach (1..5){ 
    my $node = [undef, $_ * $_]; 
    $$tail = $node; 
    $tail = \${$node->[NEXT]}; # The NEXT on this line? 
}

他在那里试图做什么？

是$node一个标量，它存储了未命名数组的地址吗？此外，即使我们取消引用$node，我们是不是应该通过索引号（如（0,1））引用各个元素。如果我们使用NEXT作为关键字，那么是$node引用一个散列？我很困惑。

一些简单的英语将高度赞赏。

来源

2012-06-07 Amey

NEXT是一个常量，在脚本中早些时候声明。它包含一个整数值，表示当前节点的成员元素的索引，该元素指向下一个节点。

在这个方案下，每个节点都是一个小的匿名数组。这个匿名数组的一个元素包含有效载荷，另一个包含指向下一个节点的引用。

如果你看看一些在该章前面的例子中，你将看到以下声明：

use constant NEXT => 0; 
use constant VAL  => 1;

所以$node->[NEXT]是同义$node->[0]，其中包含链表链到下一个节点的引用而$node->[VAL]是$node->[1]的同义词;存储在当前节点中的值（或有效载荷）。

我的代码片断评论您提供：

foreach (1..5){ 
    my $node = [undef, $_ * $_]; # Create a new node as an anon array. 

    # Set the previous node's "next node reference" to point to this new node. 
    $$tail = $node;     

    # Remember a reference to the new node's "next node reference" element. 
    # So that it can be updated when another new element is added on next iteraton. 
    $tail = \${$node->[NEXT]}; # The NEXT on this line? 
}

优秀的书，顺便说一句。我有几本算法书籍，而且这些年来，这本书继续成为我的最爱。

更新：我确实同意这本书不是当前惯用Perl或目前的“最佳实践”Perl的模型，但确实感觉它是获取经典算法应用的理解资源与Perl。我仍然时常回顾它。

来源

2012-06-07 22:24:17 DavidO

感谢您的回复。 – Amey

NEXT是一个常量，在前面的页面上声明，包含一个数字。它被用来代替常规数字来访问数组，参考文献$node，因此读者知道该插槽是链接列表中下一个元素的存储位置。

这是一种使用数组引用来存储除列表之外的其他东西的技术。与使用散列引用相比，该技术旨在节省内存和CPU时间。实际上，它并没有带来太多的性能差异，而且使用起来也很尴尬。这本书在关于如何编写Perl代码的想法中已经过时了很多。改为使用散列引用。

my $list; 
my $tail = \$list; 
foreach my $num (1..5) { 
    my $node = { data => $num }; 
    $$tail = $node; 
    $tail = \$node->{next}; 
}

来源

2012-06-07 22:35:10 Schwern

感谢您的回复，我们是否应该有另一个键 - >值对来存储下一个节点地址。密钥的名称是“下一个”？ – Amey

@seleniumnewbie是的，这就是'$ node - > {next}'是的。 – Schwern

另外我改变了'$尾= = $ {$节点 - > {下一个}};'到'$尾= = $节点 - > {下};':)或它导致了整个lotta混乱 – Amey

在perl中创建链接列表中的NEXT的含义

回答

相关问题