Steven's Blog

A Dream Land of Peace!

Perl的链表

We will use linked list to output words in a file in alphabetical order. This example is in:

1

http://man.ddvip.com/web/perl/perl9.htm#10.1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

use utf8;

$header = "";
while ( $line = <STDIN> ) {
    chomp;
    @words = split( /\s+/, $line );
    foreach my $word (@words) {
        ##remove punctuation and transform from uppercase to lower case.

        $word =~ s/[,.:;-]//;
        $word =~ tr/A-Z/a-z/;
        &add_word_to_list($word);
    }
}

&print_list;

sub add_word_to_list {

    #these two are lists.
    my ($word) = @_;
    my ($pointer);

    # if list is empty, add first item;
    if ( $header eq "" ) {
        $header = $word;
        $wordlist{$word} = "";
        return;
    }

    # if word identical to first element in list, do nothing
    return if ( $header eq $word );

    # to see if word should be the new first word in the list.

    if ( $header gt $word ) {
        $wordlist{$word} = $header;
        $header = $word;
        return;
    }

    # find place where the word belongs
    $pointer = $header;
    while ( $wordlist{$pointer} ne "" && $wordlist{$pointer} lt $word ) {
        $pointer = $wordlist{$pointer};
    }

    # if the word seen already, do nothing
    return if ( $word eq $wordlist{$pointer} );
    $wordlist{$word}    = $wordlist{$pointer};
    $wordlist{$pointer} = $word;
}

sub print_list {
    local ($pointer);
    print("Words in the input are:\n");
    $pointer = $header;
    while ( $pointer ne "" ) {
        print("$pointer\n");
        $pointer = $wordlist{$pointer};
    }
}

and for a tree structure:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

use utf8;

my $rootname = "parent";

my %tree = (
    "parentleft", "child1",      "parentright", "child2",
    "child1left", "grandchild1", "child1right", "grandchild2",
    "child2left", "grandchild3", "child2right", "grandchild4"
);

# traverse tree, printing its elements
&print_tree($rootname);

sub print_tree {
    local ($nodename) = @_;
    local ( $leftchildname, $rightchildname );

    $leftchildname  = $nodename . "left";
    $rightchildname = $nodename . "right";

    # this is a left-order traversal.

    if ( $tree{$leftchildname} ne "" ) {
        &print_tree( $tree{$leftchildname} );
    }
    print("$nodename\n");

    if ( $tree{$rightchildname} ne "" ) {
        &print_tree( $tree{$rightchildname} );
    }
}