1

所以我正在尝试使用 Perl 学习链接列表。我正在阅读Jon Orwant 的用 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对哈希的引用吗？我很迷茫。

用简单的英语表达的东西将不胜感激。

4

2 回答 2

6

NEXT是一个常量，在脚本前面声明过。它包含一个整数值，表示当前节点的成员元素的索引，该成员元素引用下一个节点。

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

如果您查看该章中的一些较早的示例，您将看到以下声明：

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

So$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-07T22:24:17.903 回答
2

NEXT是一个常量，在前一页声明，包含一个数字。它被用于访问数组 ref 而不仅仅是常规数字，$node因此读者知道该 slot 是存储链表中下一个元素的位置。

这是一种使用数组引用来存储列表以外的东西的技术。与使用哈希引用相比，该技术旨在节省内存和 CPU 时间。实际上，它并没有太大的性能差异，而且使用起来很尴尬。这本书关于如何编写 Perl 代码的想法有点过时了。请改用哈希引用。

my $list;
my $tail = \$list;
foreach my $num (1..5) {
    my $node = { data => $num };
    $$tail = $node;
    $tail = \$node->{next};
}
于 2012-06-07T22:35:10.787 回答