欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

第九章 關(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ù)組來實現(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: }
    運行結(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)點后,查看該單詞是否曾出現(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)列表變得較大時,這是很耗費時間的。
    這些問題產(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ù)組改寫上面的程序,注意實現(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: }
    運行結(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");
        運行結(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,因為其元素位置是隨機(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)效率比較低,因為每返回一個下標(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é)講述如何用之實現(xiàn):鏈表、結(jié)構(gòu)和樹。
    1、(單)鏈表
        鏈表是一種比較簡單的數(shù)據(jù)結(jié)構(gòu),可以按一定的次序存貯值。每個元素含有兩個域,一個是值,一個是引用(或稱指針),指向鏈表中下一個元素。一個特殊的頭指針指向鏈表的第一個元素。
        在Perl中,鏈表很容易用關(guān)聯(lián)數(shù)組實現(xià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ù)未知或其隨程序運行而增長的情況下,鏈表十分有用。下例用鏈表按字母次序輸出一個文件中的單詞。
    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: }
        運行結(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)點符號,就去掉。第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é)點指向的元素多于一個。最簡單的樹是二叉樹,每個節(jié)點指向另外兩個元素,稱為左子節(jié)點和右子節(jié)點(或稱孩子),每個子節(jié)點又指向兩個孫子節(jié)點,依此類推。
        注:此處所說的樹像上述鏈表一樣是單向的,每個節(jié)點指向其子節(jié)點,但子節(jié)點并不指向父節(jié)點。
        樹的概念可以如下描述:
  • 因為每個子節(jié)點均為一個樹,所以左/右子節(jié)點也稱為左/右子樹。(有時稱左/右分支)
  • 第一個節(jié)點(不是任何節(jié)點的子節(jié)點的節(jié)點)稱為樹的根。
  • 沒有孩子(子節(jié)點)的節(jié)點稱為葉節(jié)點。
  •     有多種使用關(guān)聯(lián)數(shù)組實現(xiàn)樹結(jié)構(gòu)的方法,最好的一種應(yīng)該是:給子節(jié)點分別加上left和right以訪問之。例如,alphaleft和alpharight指向alpha的左右子節(jié)點。下面是用此方法創(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é)點、右子樹”來輸出各節(jié)點的名字,這種遍歷次序稱為“左序遍歷”。如果把第22行移到19行前,先輸出節(jié)點明,再輸出左子樹、右子樹,則為“中序遍歷”,如果把第22行移到25行后,輸出次序為左子樹、右子樹、節(jié)點,則為“右序遍歷”。
        可以用同樣的方法,即連接字符串構(gòu)成下標(biāo),來創(chuàng)建其它的數(shù)據(jù)結(jié)構(gòu),如數(shù)據(jù)庫等。

    上一章 下一章 目錄