3

我编写了 Perl 代码来实际创建一个Trie数据结构，给定数组中的一组单词。现在我在遍历和打印单词时遇到问题。

还粘贴了创建的数据结构的 Dumper 输出。

遍历后的最后一组单词似乎不正确，因为遍历逻辑肯定遗漏了一些东西。但是 trie 的创建很好并且运行速度很快。有人可以在这里帮助我吗？

trie的顶层是哈希

  1. 每个散列项都有一个键，它是一个字母，每个散列指向一个数组 ref。

  2. 数组 ref 再次包含一个哈希列表，每个哈希项与 1 相同

如果您在输出中看到第一个单词。它以archtopriumwe的形式出现。

我们应该得到弧，拱，顶，中庭，敬畏

代码

使用 Data::Dumper；
我的 %mainhash;

## 子程序
子商店字{
    我的 $type = 班次；
    我的 $fc = 班次；
    我的 $word = 班次；
    return if ((not defined $word) or (length($word) == 0));    
    我的@letters = split (//,$word);
    我的 $len = 标量(@letters) - 1;
    我的 ($arr_ref,$pass_ref,$flag ,$i,$hashitem,$newitem);
    $pass_ref = $hashitem = $new_item = undef;
    $arr_ref = $类型；
    $setstop = 1 if (长度($word) == 1);   
    $标志=0；
    for($i = 0;$i {$letters[0]}) {
            $标志=1；
            $pass_ref = $hashitem->{$letters[0]};
            最后的;
        }
    }
    如果 ($flag == 0) {
        $newitem->{$letters[0]} = [];   
        推（@$arr_ref，$newitem）；
        $pass_ref = $newitem->{$letters[0]};
    }

    storeword($pass_ref,$letters[0],join ('',@letters[ 1..$len]));
}

## 子程序
子进程{
    我的 ($prefix,$trie) = @_;
    对于我的 $letter（排序键 %$trie）{
        if (@{ $trie->{$letter} } ) {
            对于我的 $branch (@{ $trie->{$letter} }) {
                进程（“$前缀$字母”，$分支）；
            }
        }
        别的 {
            打印“$前缀$字母\n”；
        }
    }
}

＃＃主要的

##单词列表
我的@wd = qw（在 awe blob 沸腾成名浴缸拱形中庭上的弧形）；

##将每个单词插入数据结构
foreach 我的 $w (@wd) {
    我的@letters = split (//,$w);
    我的 $len = 标量(@letters) - 1;
    if (不存在 $mainhash{$letters[0]}) {
        $mainhash{$letters[0]} = [];
    }
    storeword($mainhash{$letters[0]},$letters[0],join ('',@letters[ 1..$len]));
}
    打印转储器（%mainhash）；
        ## 尝试打印 trie 中的每个单词。
    print("\n 单词列表\n");    
    进程('',\%mainhash);

输出：

$VAR1 = 'a';
$VAR2 = [
          {
            'r' => [
                     {
                       'c' => [
                                {
                                  'h' => []
                                }
                              ]
                     }
                   ]
          },
          {
            't' => [
                     {
                       'o' => [
                                {
                                  'p' => []
                                }
                              ]
                     },
                     {
                       'r' => [
                                {
                                  '我' => [
                                           {
                                             '你' => [
                                                      {
                                                        'm' => []
                                                      }
                                                    ]
                                           }
                                         ]
                                }
                              ]
                     }
                   ]
          },
          {
            'w' => [
                     {
                       'e' => []
                     }
                   ]
          }
        ];
$VAR3 = 'b';
$VAR4 = [
          {
            'l' => [
                     {
                       'o' => [
                                {
                                  'b' => []
                                }
                              ]
                     }
                   ]
          },
          {
            'o' => [
                     {
                       '我' => [
                                {
                                  'l' => []
                                }
                              ]
                     }
                   ]
          }
        ];
$VAR5 = 'f';
$VAR6 = [
          {
            '一个' => [
                     {
                       'm' => [
                                {
                                  'e' => []
                                }
                              ]
                     }
                   ]
          }
        ];
$VAR7 = 't';
$VAR8 = [
          {
            '你' => [
                     {
                       'b' => []
                     }
                   ]
          }
        ];

单词列表
Archtopriumwe
水滴
名声
浴缸
4

1 回答 1

3

您是否看到您的代码仅将数据结构中的每个字母打印一次，而不是每个单词打印一次？并且只为树中的每个顶级字母打印一个换行符，而不是每个单词一个？

要解决此问题，您需要将更多上下文传递到您的递归子程序中。像这样的东西：

sub process {
    my ($prefix, $trie) = @_;
    for my $letter (sort keys %$trie) {
        if ( @{ $trie->{$letter} } ) {
            for my $branch (@{ $trie->{$letter} }) {
                process("$prefix$letter", $branch);
            }
        }
        else {
            print "$prefix$letter\n";
        }
    }
}

print("\n List of words\n");
process('', \%mainhash);

这不会打印 arc，因为您无法在数据结构中告诉您 arc 是一个单词，但例如 boi 不是。每个字母的值需要提供两件事：一个表示这是单词结尾的布尔指示符，以及可能的后续字母及其子树的列表。

于 2011-05-18T07:58:06.443 回答