第九章 關(guān)聯(lián)數(shù)組/哈希表

by flamephoenix

?

一、數(shù)組變量的限制
二、定義
三、訪問關(guān)聯(lián)數(shù)組的元素
四、增加元素
五、創(chuàng)建關(guān)聯(lián)數(shù)組
六、從數(shù)組變量復(fù)制到關(guān)聯(lián)數(shù)組
七、元素的增刪
八、列出數(shù)組的索引和值
九、用關(guān)聯(lián)數(shù)組循環(huán)
十、用關(guān)聯(lián)數(shù)組創(chuàng)建數(shù)據(jù)結(jié)構(gòu)
? 1、(單)鏈表
? 2、結(jié)構(gòu)
? 3、樹

一、數(shù)組變量的限制
????在前面講的數(shù)組變量中，可以通過下標(biāo)訪問其中的元素。例如，下列語句訪問數(shù)組@array的第三個元素：
????$scalar = $array[2];
????雖然數(shù)組很有用，但它們有一個顯著缺陷，即很難記住哪個元素存貯的什么內(nèi)容。假如我們來寫一個程序計算某文件中首字母大寫的單詞出現(xiàn)的次數(shù)，用數(shù)組來實(shí)現(xiàn)就比較困難，程序代碼如下：

1 : #!/usr/local/bin/perl
2 :
3 : while ($inputline = <STDIN>) {
4 : ? while ($inputline =~ /\b[A-Z]\S+/g) {
5 : ? ? $word = $&;
6 : ? ? $word =~ s/[;.,:-]$//; # remove punctuation
7 : ? ? for ($count = 1; $count <= @wordlist;
8 : ? ? ? ? $count++) {
9 : ? ? ? $found = 0;
10: ? ? ? if ($wordlist[$count-1] eq $word) {
11: ? ? ? ? $found = 1;
12: ? ? ? ? $wordcount[$count-1] += 1;
13: ? ? ? ? last;
14: ? ? ? }
15: ? ? }
16: ? ? if ($found == 0) {
17: ? ? ? $oldlength = @wordlist;
18: ? ? ? $wordlist[$oldlength] = $word;
19: ? ? ? $wordcount[$oldlength] = 1;
20: ? ? }
21: ? }
22: }
23: print ("Capitalized words and number of occurrences:\n");
24: for ($count = 1; $count <= @wordlist; $count++) {
25: ? print ("$wordlist[$count-1]: $wordcount[$count-1]\n");
26: }

????運(yùn)行結(jié)果如下：

Here is a line of Input.
This Input contains some Capitalized words.
^D
Capitalized words and number of occurrences:
Here: 1
Input: 2
This: 1
Capitalized: 1

????這個程序每次從標(biāo)準(zhǔn)輸入文件讀一行文字，第四行起的循環(huán)匹配每行中首字母大寫的單詞，每找到一個循環(huán)一次，賦給簡單變量$word。在第六行中去掉標(biāo)點(diǎn)后，查看該單詞是否曾出現(xiàn)過，7~15行中在@wordlist中挨個元素做此檢查，如果某個元素與$word相等，@wordcount中相應(yīng)的元素就增加一個數(shù)。如果沒有出現(xiàn)過，即@wordlist中沒有元素與$word相等，16~20行給@wordlist和@wordcount增加一個新元素。
二、定義
????正如你所看到的，使用數(shù)組元素產(chǎn)生了一些問題。首先，@wordlist中哪個元素對應(yīng)著哪個單詞并不明顯；更糟的是，每讀進(jìn)一個新單詞，程序必須檢查整個列表才能知道該單詞是否曾經(jīng)出現(xiàn)過，當(dāng)列表變得較大時，這是很耗費(fèi)時間的。
????這些問題產(chǎn)生的原因是數(shù)組元素通過數(shù)字下標(biāo)訪問，為了解決這類問題，Perl定義了另一種數(shù)組，可以用任意簡單變量值來訪問其元素，這種數(shù)組叫做關(guān)聯(lián)數(shù)組，也叫哈希表。
????為了區(qū)分關(guān)聯(lián)數(shù)組變量與普通的數(shù)組變量，Perl使用%作為其首字符，而數(shù)組變量以@打頭。與其它變量名一樣，%后的第一個字符必須為字母，后續(xù)字符可以為字母、數(shù)字或下劃線。
三、訪問關(guān)聯(lián)數(shù)組的元素
????關(guān)聯(lián)數(shù)組的下標(biāo)可以為任何簡單/標(biāo)量值，訪問單個元素時以$符號打頭，下標(biāo)用大括號圍起來。例如：

$fruit{"bananas"}
$number{3.14159}
$integer{-7}

????簡單變量也可作為下標(biāo)，如：
????$fruit{$my_fruit}
四、增加元素
????創(chuàng)建一個關(guān)聯(lián)數(shù)組元素最簡單的方法是賦值，如語句$fruit{"bananas"} = 1； 把1賦給關(guān)聯(lián)數(shù)組%fruit下標(biāo)為bananas的元素，如果該元素不存在，則被創(chuàng)建，如果數(shù)組%fruit從未使用過，也被創(chuàng)建。
????這一特性使得關(guān)聯(lián)數(shù)組很容易用于計數(shù)。下面我們用關(guān)聯(lián)數(shù)組改寫上面的程序，注意實(shí)現(xiàn)同樣的功能此程序簡化了許多。

1 : #!/usr/local/bin/perl
2 :
3 : while ($inputline = ) {
4 : ? while ($inputline =~ /\b[A-Z]\S+/g) {
5 : ? ? $word = $&;
6 : ? ? $word =~ s/[;.,:-]$//; # remove punctuation
7 : ? ? $wordlist{$word} += 1;
8 : ? }
9 : }
10: print ("Capitalized words and number of occurrences:\n");
11: foreach $capword (keys(%wordlist)) {
12: ? print ("$capword: $wordlist{$capword}\n");
13: }

????運(yùn)行結(jié)果如下：

Here is a line of Input.
This Input contains some Capitalized words.
^D
Capitalized words and number of occurrences:
This: 1
Input: 2
Here: 1
Capitalized: 1

????你可以看到，這次程序簡單多了，讀取輸入并存貯各單詞數(shù)目從20行減少到了7行。
????本程序用關(guān)聯(lián)數(shù)組%wordlist跟蹤首字母大寫的單詞，下標(biāo)就用單詞本身，元素值為該單詞出現(xiàn)的次數(shù)。第11行使用了內(nèi)嵌函數(shù)keys()。這個函數(shù)返回關(guān)聯(lián)數(shù)組的下標(biāo)列表，foreach語句就用此列表循環(huán)。
????注：關(guān)聯(lián)數(shù)組總是隨機(jī)存貯的，因此當(dāng)你用keys()訪問其所有元素時，不保證元素以任何順序出現(xiàn)，特別值得一提的是，它們不會以被創(chuàng)建的順序出現(xiàn)。
????要想控制關(guān)聯(lián)數(shù)組元素出現(xiàn)的次序，可以用sort()函數(shù)對keys()返回值進(jìn)行排列，如：

foreach $capword (sort keys(%wordlist)) {
? print ("$capword: $wordlist{$capword}\n");
}

五、創(chuàng)建關(guān)聯(lián)數(shù)組
????可以用單個賦值語句創(chuàng)建關(guān)聯(lián)數(shù)組，如：
????%fruit = ("apples",17,"bananas",9,"oranges","none");
????此語句創(chuàng)建的關(guān)聯(lián)數(shù)組含有下面三個元素：

• 下標(biāo)為apples的元素，值為17
• 下標(biāo)為bananas的元素，值為9
• 下標(biāo)為oranges的元素，值為none

????注：用列表給關(guān)聯(lián)數(shù)組賦值時，Perl5允許使用"=>"或","來分隔下標(biāo)與值，用"=>"可讀性更好些，上面語句等效于：
????%fruit=("apples"=>17,"bananas"=>9,"oranges"=>"none");
六、從數(shù)組變量復(fù)制到關(guān)聯(lián)數(shù)組
????與列表一樣，也可以通過數(shù)組變量創(chuàng)建關(guān)聯(lián)數(shù)組，當(dāng)然，其元素數(shù)目應(yīng)該為偶數(shù)，如：
????@fruit = ("apples",17,"bananas",9,"oranges","none");
????%fruit = @fruit;
????反之，可以把關(guān)聯(lián)數(shù)組賦給數(shù)組變量，如：
????%fruit = ("grapes",11,"lemons",27);
????@fruit = %fruit;
????注意，此語句中元素次序未定義，那么數(shù)組變量@fruit可能為("grapes",11,"lemons",27)或("lemons",27,"grapes",11)。
????關(guān)聯(lián)數(shù)組變量之間可以直接賦值，如：%fruit2 = %fruit1; 還可以把數(shù)組變量同時賦給一些簡單變量和一個關(guān)聯(lián)數(shù)組變量，如：
????($var1, $var2, %myarray) = @list;
????此語句把@list的第一個元素賦給$var1，第二個賦給$var2，其余的賦給%myarray。
????最后，關(guān)聯(lián)數(shù)組可以通過返回值為列表的內(nèi)嵌函數(shù)或用戶定義的子程序來創(chuàng)建，下例中把split()函數(shù)的返回值--一個列表--賦給一個關(guān)聯(lián)數(shù)組變量。

1: #!/usr/local/bin/perl
2:
3: $inputline = <STDIN>;
4: $inputline =~ s/^\s+|\s+\n$//g;
5: %fruit = split(/\s+/, $inputline);
6: print ("Number of bananas: $fruit{\"bananas\"}\n");

????運(yùn)行結(jié)果如下：

oranges 5 apples 7 bananas 11 cherries 6
Number of bananas: 11

七、元素的增刪
????增加元素已經(jīng)講過，可以通過給一個未出現(xiàn)過的元素賦值來向關(guān)聯(lián)數(shù)組中增加新元素，如$fruit{"lime"} = 1;創(chuàng)建下標(biāo)為lime、值為1的新元素。
????刪除元素的方法是用內(nèi)嵌函數(shù)delete，如欲刪除上述元素，則：
????delete ($fruit{"lime"});
注意：

1、一定要使用delete函數(shù)來刪除關(guān)聯(lián)數(shù)組的元素，這是唯一的方法。
2、一定不要對關(guān)聯(lián)數(shù)組使用內(nèi)嵌函數(shù)push、pop、shift及splice，因?yàn)槠湓匚恢檬请S機(jī)的。

八、列出數(shù)組的索引和值
????上面已經(jīng)提到，keys()函數(shù)返回關(guān)聯(lián)數(shù)組下標(biāo)的列表，如：

%fruit = ("apples", 9,
          "bananas", 23,
          "cherries", 11);
@fruitsubs = keys(%fruits);

????這里，@fruitsubs被賦給apples、bananas、cherries構(gòu)成的列表，再次提請注意，此列表沒有次序，若想按字母順序排列，可使用sort()函數(shù)。
????@fruitindexes = sort keys(%fruits);
????這樣結(jié)果為("apples","bananas","cherries")。類似的，內(nèi)嵌函數(shù)values()返回關(guān)聯(lián)數(shù)組值的列表，如：

%fruit = ("apples", 9,
           "bananas", 23,
           "cherries", 11);
@fruitvalues = values(%fruits);

????這里，@fruitvalues可能的結(jié)果為(9,23.11)，次序可能不同。
九、用關(guān)聯(lián)數(shù)組循環(huán)
????前面已經(jīng)出現(xiàn)過利用keys()函數(shù)的foreach循環(huán)語句，這種循環(huán)效率比較低，因?yàn)槊糠祷匾粋€下標(biāo)，還得再去尋找其值，如：

foreach $holder (keys(%records)){
? $record = $records{$holder};
}

????Perl提供一種更有效的循環(huán)方式，使用內(nèi)嵌函數(shù)each()，如：

%records = ("Maris", 61, "Aaron", 755, "Young", 511);
while (($holder, $record) = each(%records)) {
? # stuff goes here
}

????each()函數(shù)每次返回一個雙元素的列表，其第一個元素為下標(biāo)，第二個元素為相應(yīng)的值，最后返回一個空列表。
????注意：千萬不要在each()循環(huán)中添加或刪除元素，否則會產(chǎn)生不可預(yù)料的后果。
十、用關(guān)聯(lián)數(shù)組創(chuàng)建數(shù)據(jù)結(jié)構(gòu)
????用關(guān)聯(lián)數(shù)組可以模擬在其它高級語言中常見的多種數(shù)據(jù)結(jié)構(gòu)，本節(jié)講述如何用之實(shí)現(xiàn)：鏈表、結(jié)構(gòu)和樹。
1、(單)鏈表
????鏈表是一種比較簡單的數(shù)據(jù)結(jié)構(gòu)，可以按一定的次序存貯值。每個元素含有兩個域，一個是值，一個是引用（或稱指針），指向鏈表中下一個元素。一個特殊的頭指針指向鏈表的第一個元素。
????在Perl中，鏈表很容易用關(guān)聯(lián)數(shù)組實(shí)現(xiàn)，因?yàn)橐粋€元素的值可以作為下一個元素的索引。下例為按字母順序排列的單詞鏈表：

%words = ("abel", "baker", 
          "baker", "charlie",
          "charlie", "delta",
          "delta", "");
$header = "abel";

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

1 : #!/usr/local/bin/perl
2 :
3 : # initialize list to empty
4 : $header = "";
5 : while ($line = <STDIN>) {
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: }

????運(yùn)行結(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)換到相應(yīng)的格式。
• 子程序：add_word_to_list，建立排序單詞鏈表。
• 子程序：print_list，輸出單詞鏈表

????第3~17行為主程序，第4行初始化鏈表，將表頭變量$header設(shè)為空串，第5行起的循環(huán)每次讀取一行輸入，第7行去掉頭、尾的空格，第8行將句子分割成單詞。9~15行的內(nèi)循環(huán)每次處理一個單詞，如果該單詞的最后一個字符是標(biāo)點(diǎn)符號，就去掉。第13行把單詞轉(zhuǎn)換成全小寫形式，第14行傳遞給子程序add_word_to_list。
????子程序add_word_to_list先在第24行處檢查鏈表是否為空。如果是，第25行將單詞賦給$header，26行創(chuàng)建鏈表第一個元素，存貯在關(guān)聯(lián)數(shù)組%wordlist中。如果鏈表非空，37行檢查第一個元素是否與該單詞相同，如果相同，就立刻返回。下一步檢查這一新單詞是否應(yīng)該為鏈表第一個元素，即其按字母順序先于$header。如果是這樣，則：
????1、創(chuàng)建一個新元素，下標(biāo)為該新單詞，其值為原第一個單詞。
????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}。
????最后當(dāng)處理完畢后，子程序print_list()依次輸出鏈表，局域變量$pointer含有正在輸出的值，$wordlist{$pointer}為下一個要輸出的值。
????注：一般不需要用鏈表來做這些工作，用sort()和keys()在關(guān)聯(lián)數(shù)組中循環(huán)就足夠了，如：

foreach $word (sort keys(%wordlist)) {
? # print the sorted list, or whatever }

????但是，這里涉及的指針的概念在其它數(shù)據(jù)結(jié)構(gòu)中很有意義。
2、結(jié)構(gòu)
????許多編程語言可以定義結(jié)構(gòu)(structure)，即一組數(shù)據(jù)的集合。結(jié)構(gòu)中的每個元素有其自己的名字，并通過該名字來訪問。
????Perl不直接提供結(jié)構(gòu)這種數(shù)據(jù)結(jié)構(gòu)，但可以用關(guān)聯(lián)數(shù)組來模擬。例如模擬C語言中如下的結(jié)構(gòu)：

struce{
? int field1;
? int field2;
? int field3; }mystructvar;

????我們要做的是定義一個含有三個元素的關(guān)聯(lián)數(shù)組，下標(biāo)分別為field1、field2、field3，如：

%mystructvar = ("field1" , "" ,
? ? ? "field2" , "" ,
? ? ? "field3" , "" ,);

????像上面C語言的定義一樣，這個關(guān)聯(lián)數(shù)組%mystrctvar有三個元素，下標(biāo)分別為field1、field2、field3，各元素初始值均為空串。對各元素的訪問和賦值通過指定下標(biāo)來進(jìn)行，如：
????$mystructvar{"field1"} = 17;
3、樹
????另一個經(jīng)常使用的數(shù)據(jù)結(jié)構(gòu)是樹。樹與鏈表類似，但每個節(jié)點(diǎn)指向的元素多于一個。最簡單的樹是二叉樹，每個節(jié)點(diǎn)指向另外兩個元素，稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)（或稱孩子），每個子節(jié)點(diǎn)又指向兩個孫子節(jié)點(diǎn)，依此類推。
????注：此處所說的樹像上述鏈表一樣是單向的，每個節(jié)點(diǎn)指向其子節(jié)點(diǎn)，但子節(jié)點(diǎn)并不指向父節(jié)點(diǎn)。
????樹的概念可以如下描述：

• 因?yàn)槊總€子節(jié)點(diǎn)均為一個樹，所以左/右子節(jié)點(diǎn)也稱為左/右子樹。（有時稱左/右分支）
• 第一個節(jié)點(diǎn)（不是任何節(jié)點(diǎn)的子節(jié)點(diǎn)的節(jié)點(diǎn)）稱為樹的根。
• 沒有孩子（子節(jié)點(diǎn)）的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。

????有多種使用關(guān)聯(lián)數(shù)組實(shí)現(xiàn)樹結(jié)構(gòu)的方法，最好的一種應(yīng)該是：給子節(jié)點(diǎn)分別加上left和right以訪問之。例如，alphaleft和alpharight指向alpha的左右子節(jié)點(diǎn)。下面是用此方法創(chuàng)建二叉樹并遍歷的例程：

1 : #!/usr/local/bin/perl
2 :
3 : $rootname = "parent";
4 : %tree = ("parentleft", "child1",
5 :? ? ? ? ? "parentright", "child2",
6 :? ? ? ? ? "child1left", "grandchild1",
7 :? ? ? ? ? "child1right", "grandchild2",
8 :? ? ? ? ? "child2left", "grandchild3",
9 :? ? ? ? ? "child2right", "grandchild4");
10: # traverse tree, printing its elements
11: &print_tree($rootname);
12:
13: sub print_tree {
14: ? local ($nodename) = @_;
15: ? local ($leftchildname, $rightchildname);
16:
17: ? $leftchildname = $nodename . "left";
18: ? $rightchildname = $nodename . "right";
19: ? if ($tree{$leftchildname} ne "") {
20: ? ? &print_tree($tree{$leftchildname});
21: ? }
22: ? print ("$nodename\n");
23: ? if ($tree{$rightchildname} ne "") {
24: ? ? &print_tree($tree{$rightchildname});
25: ? }
26: }

????結(jié)果輸出如下：

grandchild1
child1
grandchild2
parent
grandchild3
child2
grandchild4

????該程序創(chuàng)建的二叉樹如下圖：

????注意函數(shù)print_tree()以次序“左子樹、節(jié)點(diǎn)、右子樹”來輸出各節(jié)點(diǎn)的名字，這種遍歷次序稱為“左序遍歷”。如果把第22行移到19行前，先輸出節(jié)點(diǎn)明，再輸出左子樹、右子樹，則為“中序遍歷”，如果把第22行移到25行后，輸出次序?yàn)樽笞訕?、右子樹、?jié)點(diǎn)，則為“右序遍歷”。
????可以用同樣的方法，即連接字符串構(gòu)成下標(biāo)，來創(chuàng)建其它的數(shù)據(jù)結(jié)構(gòu)，如數(shù)據(jù)庫等。