明輝手游網(wǎng)中心:是一個免費提供流行視頻軟件教程、在線學習分享的學習平臺!

Perl教學 第9篇 關聯(lián)數(shù)組之3

[摘要]上例中,簡單變量$header含有鏈表中第一個單詞,它同時也是關聯(lián)數(shù)組第一個元素的下標,其值baker又是下一個元素的下標,依此類推。下標為delta的最后一個元素的值為空串,表示鏈表的結(jié)束。在將要處理的數(shù)據(jù)個數(shù)未知或其隨程序運行而增長的情況下,鏈表十分有用。下例用鏈表按字母次序輸出一個文件中的單...
上例中,簡單變量$header含有鏈表中第一個單詞,它同時也是關聯(lián)數(shù)組第一個元素的下標,其值baker又是下一個元素的下標,依此類推。
下標為delta的最后一個元素的值為空串,表示鏈表的結(jié)束。
在將要處理的數(shù)據(jù)個數(shù)未知或其隨程序運行而增長的情況下,鏈表十分有用。下例用鏈表按字母次序輸出一個文件中的單詞。

1 : #!/usr/local/bin/perl
2 :
3 : # initialize list to empty
4 : $header = "";
5 : while ($line = ) {
6 : # remove leading and trailing spaces
7 : $line =~ s/^\s+ \s+$//g;
8 : @words = split(/\s+/, $line);
9 : foreach $word (@words) {
10: # remove closing punctuation, if any
11: $word =~ s/[.,;:-]$//;
12: # convert all words to lower case
13: $word =~ tr/A-Z/a-z/;
14: &add_word_to_list($word);
15: }
16: }
17: &print_list;
18:
19: sub add_word_to_list {
20: local($word) = @_;
21: local($pointer);
22:
23: # if list is empty, add first item
24: if ($header eq "") {
25: $header = $word;
26: $wordlist{$word} = "";
27: return;
28: }
29: # if word identical to first element in list,
30: # do nothing
31: return if ($header eq $word);
32: # see whether word should be the new
33: # first word in the list
34: if ($header gt $word) {
35: $wordlist{$word} = $header;
36: $header = $word;
37: return;
38: }
39: # find place where word belongs
40: $pointer = $header;
41: while ($wordlist{$pointer} ne "" &&
42: $wordlist{$pointer} lt $word) {
43: $pointer = $wordlist{$pointer};
44: }
45: # if word already seen, do nothing
46: return if ($word eq $wordlist{$pointer});
47: $wordlist{$word} = $wordlist{$pointer};
48: $wordlist{$pointer} = $word;
49: }
50:
51: sub print_list {
52: local ($pointer);
53: print ("Words in this file:\n");
54: $pointer = $header;
55: while ($pointer ne "") {
56: print ("$pointer\n");
57: $pointer = $wordlist{$pointer};
58: }
59: }
運行結(jié)果如下:

Here are some words.
Here are more words.
Here are still more words.
^D
Words in this file:
are
here
more
some
still
words
此程序分為三個部分:


·主程序:讀取輸入并轉(zhuǎn)換到相應的格式。
·子程序:add_word_to_list,建立排序單詞鏈表。
·子程序:print_list,輸出單詞鏈表
第3~17行為主程序,第4行初始化鏈表,將表頭變量$header設為空串,第5行起的循環(huán)每次讀取一行輸入,第7行去掉頭、尾的空格,第8行將句子分割成單詞。9~15行的內(nèi)循環(huán)每次處理一個單詞,如果該單詞的最后一個字符是標點符號,就去掉。第13行把單詞轉(zhuǎn)換成全小寫形式,第14行傳遞給子程序add_word_to_list。
子程序add_word_to_list先在第24行處檢查鏈表是否為空。如果是,第25行將單詞賦給$header,26行創(chuàng)建鏈表第一個元素,存貯在關聯(lián)數(shù)組%wordlist中。如果鏈表非空,37行檢查第一個元素是否與該單詞相同,如果相同,就立刻返回。下一步檢查這一新單詞是否應該為鏈表第一個元素,即其按字母順序先于$header。如果是這樣,則:
1、創(chuàng)建一個新元素,下標為該新單詞,其值為原第一個單詞。
2、該新單詞賦給$header。
如果該新單詞不該為第一個元素,則40~44行利用局域變量$pointer尋找其合適的有效位置,41~44行循環(huán)到$wordlist{$pointer}大于或等于$word為止。接下來46行查看該單詞是否已在鏈表中,如果在就返回,否則47~48行將其添加到鏈表中。首先47行創(chuàng)建新元素$wordlist{$word},其值為$wordlist{$pointer},這時$wordlist{$word}和$wordlist{$pointer}指向同一個單詞。然后,48行將$wordlist{$pointer}的值賦為$word,即將$wordlist{$pointer}指向剛創(chuàng)建的新元素$wordlist{$word}。
最后當處理完畢后,子程序print_list()依次輸出鏈表,局域變量$pointer含有正在輸出的值,$wordlist{$pointer}為下一個要輸出的值。
注:一般不需要用鏈表來做這些工作,用sort()和keys()在關聯(lián)數(shù)組中循環(huán)就足夠了,如:

foreach $word (sort keys(%wordlist)) {
# print the sorted list, or whatever }
但是,這里涉及的指針的概念在其它數(shù)據(jù)結(jié)構中很有意義。