在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的含義

回答

相關問題