Przemierzanie trie, aby uzyskać wszystkie słowa - perl, struktury danych, traversal, trie

Napisałem kod Perla, aby stworzyć Trie datastructure otrzymała zestaw słów w tablicy. Teraz mam problemy z przechodzeniem i drukowaniem słów.

Wklejono również wyjście Dumper utworzonej struktury danych.

Ostatni zestaw słów po przejściu nie wydaje się być słuszny, ponieważ logika przejścia z pewnością czegoś brakuje. Ale tworzenie trie jest w porządku i działa szybko. Czy ktoś może mi tutaj pomóc?

Najwyższy poziom gry to skrót

1. Każdy element mieszania ma klucz, który jest litera i każdy skrót wskazuje na ref. tablicy

2. Ref. Tablicy ponownie zawiera a lista skrótów i każdy element skrótu jest tak samo jak 1

Jeśli zobaczysz pierwsze słowo na wyjściu. Pojawia się jak archtopriumwe.

Powinniśmy dostać łuk, łuk, szczyt, atrium, respekt

KOD

użyj danych ::Wywrotka; mój% mainhash;  ## Podprogram podszablon { mój $ type = shift; moje $ fc = shift; moje $ słowo = przesunięcie; return if ((niezdefiniowane $ słowo) lub (długość ($ słowo) == 0)); moje @letters = split (//, $ word); my $ len = skalar (@letters) - 1; my ($ arr_ref, $ pass_ref, $ flag, $ i, $ hashitem, $ newitem); $ pass_ref = $ hashitem = $ new_item = undef; $ arr_ref = $ type; $ setstop = 1 if (length ($ word) == 1); $ flag = 0; for ($ i = 0; $ i {$ letters [0]}) { $ flag = 1; $ pass_ref = $ hashitem -> {$ letters [0]}; ostatni, ubiegły, zeszły; } } if ($ flag == 0) { $ newitem -> {$ letters [0]} = []; push (@ $ arr_ref, $ newitem); $ pass_ref = $ newitem -> {$ letters [0]}; }  storeword ($ pass_ref, $ letters [0], join ("", @ letters [1 .. $ len])); }  ## Podprogram proces podrzędny { my ($ prefix, $ trie) = @_; dla mojego $ letter (sort keys% $ trie) { if (@ {$ trie -> {$ letter}}) { dla mojego $ branch (@ {$ trie -> {$ letter}}) { proces („$ prefix $ letter”, $ branch); } } inaczej { wypisz "$ prefix $ lettern"; } } }  ##Główny  ## lista słów mój @wd = qw (łuk na szczycie respektu blobu gotuje słoną wannę łuku atrium);  ## wstawianie każdego słowa do struktury danych foreach my $ w (@wd) { moje @letters = split (//, $ w); my $ len = skalar (@letters) - 1; jeśli (nie istnieje $ mainhash {$ letters [0]}) { $ mainhash {$ letters [0]} = []; } storeword ($ mainhash {$ letters [0]}, $ letters [0], join ("", @ letters [1 .. $ len])); } wydrukuj Dumper (% mainhash); ## Próbuję wydrukować każde słowo z trie. print ("n Lista słów"); proces („”,% mainhash);

Wydajność:

$ VAR1 = "a"; $ VAR2 = [ { „r” => [ { „c” =>[ { „h” => [] } ] } ] }, { „t” => [ { „o” => [ { „p” => [] } ] }, { „r” => [ { „i” => [ { „u” => [ { „m” => [] } ] } ] } ] } ] }, { „w” => [ { „e” => [] } ] } ]; $ VAR3 = "b"; $ VAR4 = [ { „l” => [ { „o” => [ { „b” => [] } ] } ] }, { „o” => [ { „i” => [ { „l” => [] } ] } ] } ]; $ VAR5 = "f"; $ VAR6 = [ { „a” => [ { „m” => [ { „e” => [] } ] } ] } ]; $ VAR7 = "t"; $ VAR8 = [ { „u” => [ { „b” => [] } ] } ];  Lista słów archtopriumwe bloboil sława wanna

Odpowiedzi:

Czy widzisz, że twój kod jest tylko drukowaniemkażda litera w strukturze danych raz, zamiast raz na słowo, w którym się znajduje? I drukujesz tylko jeden wiersz raz dla każdej litery najwyższego poziomu w drzewie, a nie dla każdego słowa?

Aby to naprawić, musisz przekazać więcej kontekstu do rekurencyjnego sub. Coś takiego:

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$lettern";
}
}
}

print("n List of wordsn");
process("", %mainhash);

To nie drukuje łuku, ponieważ podasz niesposób, aby powiedzieć w swojej strukturze danych, że łuk jest słowem, ale np. boi nie jest. Wartość dla każdej litery musi zawierać dwie rzeczy: wskaźnik logiczny, że jest to koniec słowa, oraz listę możliwych kolejnych liter i ich podrzędnych.