精华内容
下载资源
问答
  • 又称为哈希表(hash table),是一种很好用的数据结构。 在程序中。我们可能会遇到须要消重的问题,举一个最简单的模型: 有一份username列表。存储了 10000 个username,没有反复项; 另一份黑名单列表,...
    PHP有数据的一个非常重要的一类,就是关联数组。又称为哈希表(hash table),是一种很好用的数据结构。

    在程序中。我们可能会遇到须要消重的问题,举一个最简单的模型:

    有一份username列表。存储了 10000 个username,没有反复项;
    另一份黑名单列表,存储了 2000 个username,格式与username列表同样。
    如今须要从username列表中删除处在黑名单里的username,要求用尽量快的时间处理。

    这个问题是一个小规模的处理量,假设实际一点,2 个表都可能非常大,比方有 2 亿条记录。



    我最開始想到的方法,就是做一个嵌套的循环。设username表有 M 条记录,黑名单列表有 N 条记录,那么,循环的次数是 M * N 次。
    PHP 版代码:


    01 <?php  
    02 foreach($arrayM as $keyM => $nameM) {  
    03 foreach($arrayN as $nameN) {  
    04 if ($nameM == $nameN) {  
    05 // 本行运行了 M * N 次!  
    06 unset($arrayM[$keyM]);  
    07 }  
    08 }  
    09 }  
    10 return $arrayM;  
    11 ?

    >


    还有一种方式,利用数组索引。

    PHP 是一种弱类型的语言,不像 C 语言那样有严格的变量类型限制。C 语言的数组。每个元素的类型必须一致。并且索引都是从 0 開始。
    PHP 的数组,能够用字符串作为索引,也称为关联数组。
    数组索引,有一个天然的限制就是不会反复。并且訪问的时候不须要查找,能够直接定位。



    还是刚才的那个问题,我们採用还有一种办法。

    把黑名单列表的username组织到一个数组里,数组的索引就是username。

    然后,遍历用户列表的时候,仅仅需直接用 isset 查询那个username是否存在就可以。

    PHP 版代码:


    01 <?php  
    02 $arrayHash = array();  
    03 foreach($arrayN as $nameN) {  
    04 // 本行运行了 N 次。  
    05 $arrayHash[$nameN] = 1;  
    06 }  
    07  
    08 foreach($arrayM as $keyM => $nameM) {  
    09 if (isset($arrayHash[$nameM])) {  
    10 // 本行运行了 M 次!

      
    11 unset($arrayM[$keyM]);  
    12 }  
    13 }  
    14 return $arrayM;  
    15 ?

    >


    能够看到,优化过的代码,循环次数是 M + N 次。

    假如 M 和 N 都是 10000,优化前,循环了 1 亿次;优化后。仅仅循环了 20000 次。差了 5000 倍。
    假设第二个程序耗时 1 秒。则第一个程序须要将近一个半小时!



    =========================================================================
    hash一个貌似比較复杂的东西,实际上理解起来并不那么夸张。这里做个笔记。

    hash,中文翻译成杂乱的东西。有人也叫它杂凑,或者翻译成什么都不是的音译“哈希”。

    简单说来。hash就是为了把一个复杂的字串,通过一定的转换,得到一个简单的数字(一般是数字)。
    如"abcd" 用各个字符的值直接相加。再取对10的余数,既(a+b+c+d)。来得到一个数字。例如说结果为5,那么这个5就能在一定意义上代表这个字串 abcd了。或者说这个5也能够说是这个字串的一个标记性的东西,并且是简化了的标记,所以又有人叫这个5为字串的摘要,或指纹。
    这个5,有一个好的用处就是能够作为一个数组的下标来用,如我自己构造一个指针数组void* hash_array[10]。那么我就能够把5那个位置上填上一个指针,如指向abcd字串。
    这种话。我假设要去查询一个字串是否存在,就不须要对一个数组使用字符串循环对照这种慢操作,而直接先得到某个字串的hash值,再用这个hash值,在数组下标里直接找。这样速度要快上非常多,特别是数据比較多的时候。

    能够看到上面计算hash值时,出来的结果,可能并非从0開始的,如我们算出的就是5。也就是说,这个5是在数组中的某个不确定的位置,或者能够叫做是一个杂凑出来的位置。其它位置可能一直就空着在。这就是这个数组或表格叫hash表的原因了。



    但有个问题,上面的转换方法,直接相加,再取个余数,在字符串变为abdc时。结果得到的还是数字5。

    这个就是上面这个算法的一个问题了。即它不能保证一个唯一性。所以就出现了非常多hash算法的研究,如MD4,MD5,SHA-1等,来保证唯一性。


    但上面这个算法还是能够使用的,做法就是在abdc经过hash得到5后,去检查5是否被占用。假设占用了,那么就把数字加1。即为6,假设6没被占用,就填上值。假设后面某个字串算出一个值是6,但6已经被占用了,那么就再加1。再存。
    取数据的时候,能够先算出hash值后,再看里面的内容是不是你想要的,假设不是,就加1去看,最后得到一个。

    所以这里hash表的内容并非象一般的数组最開始就组织好了的,而是兴许慢慢往里添加的。


    hash表里存的内容一般能够是一个指针,这个指针能够指向一个大的结构也是能够的。这个结构里能够有key, value信息
    hash表也能够不是数组,你能够把它组织成一个链表,链表里的node的结构中能够有一个參数就是那个数字的hash_value。用来高速查找用。



    尽管在非常多时候hash被用在加密等场合,但在一般的应用程序代码中,也能够用它来存简单的数据存储,代码的这样的高效率将是非常。

    版权声明:本文博主原创文章,博客,未经同意不得转载。

    展开全文
  • perl关联数组/哈希表

    千次阅读 2012-08-31 17:45:05
    perl关联数组/哈希表 一、数组变量的限制 二、定义 三、访问关联数组的元素 四、增加元素 五、创建关联数组 六、从数组变量复制到关联数组 七、元素的增删 八、列出数组的索引值 九、用关联数组循环 ...

    perl关联数组/哈希表

    一、数组变量的限制
    二、定义
    三、访问关联数组的元素
    四、增加元素
    五、创建关联数组
    六、从数组变量复制到关联数组
    七、元素的增删
    八、列出数组的索引和值
    九、用关联数组循环
    十、用关联数组创建数据结构
    1、(单)链表
    2、结构
    3、树

    一、数组变量的限制
         在前面讲的数组变量中,可以通过下标访问其中的元素。例如,下列语句访问数组@array的第三个元素:
         $scalar = $array[2];
         虽然数组很有用,但它们有一个显著缺陷,即很难记住哪个元素存贮的什么内容。假如我们来写一个程序计算某文件中首字母大写的单词出现的次数,用数组来实现就比较困难,程序代码如下:
    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: }
         运行结果如下:
    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
         这个程序每次从标准输入文件读一行文字,第四行起的循环匹配每行中首字母大写的单词,每找到一个循环一次,赋给简单变量$word。在第六行中去掉标点后,查看该单词是否曾出现过,7~15行中在@wordlist中挨个元素做此检查,如果某个元素与$word相等,@wordcount中相应的元素就增加一个数。如果没有出现过,即@wordlist中没有元素与$word相等,16~20行给@wordlist和@wordcount增加一个新元素。
    二、定义
         正如你所看到的,使用数组元素产生了一些问题。首先,@wordlist中哪个元素对应着哪个单词并不明显;更糟的是,每读进一个新单词,程序必须检查整个列表才能知道该单词是否曾经出现过,当列表变得较大时,这是很耗费时间的。
         这些问题产生的原因是数组元素通过数字下标访问,为了解决这类问题,Perl定义了另一种数组,可以用任意简单变量值来访问其元素,这种数组叫做关联数组,也叫哈希表。
         为了区分关联数组变量与普通的数组变量,Perl使用%作为其首字符,而数组变量以@打头。与其它变量名一样,%后的第一个字符必须为字母,后续字符可以为字母、数字或下划线。
    三、访问关联数组的元素
         关联数组的下标可以为任何简单/标量值,访问单个元素时以$符号打头,下标用大括号围起来。例如:
    $fruit{"bananas"}
    $number{3.14159}
    $integer{-7}
         简单变量也可作为下标,如:
         $fruit{$my_fruit}
    四、增加元素
         创建一个关联数组元素最简单的方法是赋值,如语句$fruit{"bananas"} = 1; 把1赋给关联数组%fruit下标为bananas的元素,如果该元素不存在,则被创建,如果数组%fruit从未使用过,也被创建。
         这一特性使得关联数组很容易用于计数。下面我们用关联数组改写上面的程序,注意实现同样的功能此程序简化了许多。
    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: }
         运行结果如下:
    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
         你可以看到,这次程序简单多了,读取输入并存贮各单词数目从20行减少到了7行。
         本程序用关联数组%wordlist跟踪首字母大写的单词,下标就用单词本身,元素值为该单词出现的次数。第11行使用了内嵌函数keys()。这个函数返回关联数组的下标列表,foreach语句就用此列表循环。
         注:关联数组总是随机存贮的,因此当你用keys()访问其所有元素时,不保证元素以任何顺序出现,特别值得一提的是,它们不会以被创建的顺序出现。
         要想控制关联数组元素出现的次序,可以用sort()函数对keys()返回值进行排列,如:
    foreach $capword (sort keys(%wordlist)) {
    print ("$capword: $wordlist{$capword}\n");
    }
    五、创建关联数组
         可以用单个赋值语句创建关联数组,如:
         %fruit = ("apples",17,"bananas",9,"oranges","none");
         此语句创建的关联数组含有下面三个元素:
    下标为apples的元素,值为17下标为bananas的元素,值为9下标为oranges的元素,值为none
         注:用列表给关联数组赋值时,Perl5允许使用"=>"或","来分隔下标与值,用"=>"可读性更好些,上面语句等效于:
         %fruit = ("apples"=>17,"bananas"=>9,"oranges"=>"none");
    六、从数组变量复制到关联数组
         与列表一样,也可以通过数组变量创建关联数组,当然,其元素数目应该为偶数,如:
         @fruit = ("apples",17,"bananas",9,"oranges","none");
         %fruit = @fruit;
         反之,可以把关联数组赋给数组变量,如:
         %fruit = ("grapes",11,"lemons",27);
         @fruit = %fruit;
         注意,此语句中元素次序未定义,那么数组变量@fruit可能为("grapes",11,"lemons",27)或("lemons",27,"grapes",11)。
         关联数组变量之间可以直接赋值,如:%fruit2 = %fruit1; 还可以把数组变量同时赋给一些简单变量和一个关联数组变量,如:
         ($var1, $var2, %myarray) = @list;
         此语句把@list的第一个元素赋给$var1,第二个赋给$var2,其余的赋给%myarray。
         最后,关联数组可以通过返回值为列表的内嵌函数或用户定义的子程序来创建,下例中把split()函数的返回值--一个列表--赋给一个关联数组变量。
    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");
         运行结果如下:
    oranges 5 apples 7 bananas 11 cherries 6
    Number of bananas: 11
    七、元素的增删
         增加元素已经讲过,可以通过给一个未出现过的元素赋值来向关联数组中增加新元素,如$fruit{"lime"} = 1;创建下标为lime、值为1的新元素。
         删除元素的方法是用内嵌函数delete,如欲删除上述元素,则:
         delete ($fruit{"lime"});
    注意:
    1、一定要使用delete函数来删除关联数组的元素,这是唯一的方法。
    2、一定不要对关联数组使用内嵌函数push、pop、shift及splice,因为其元素位置是随机的。
    八、列出数组的索引和值
         上面已经提到,keys()函数返回关联数组下标的列表,如:
    %fruit = ("apples", 9, "bananas", 23, "cherries", 11);@fruitsubs = keys(%fruits);
         这里,@fruitsubs被赋给apples、bananas、cherries构成的列表,再次提请注意,此列表没有次序,若想按字母顺序排列,可使用sort()函数。
         @fruitindexes = sort keys(%fruits);
         这样结果为("apples","bananas","cherries")。类似的,内嵌函数values()返回关联数组值的列表,如:
    %fruit = ("apples", 9, "bananas", 23, "cherries", 11);@fruitvalues = values(%fruits);
         这里,@fruitvalues可能的结果为(9,23.11),次序可能不同。
    九、用关联数组循环
         前面已经出现过利用keys()函数的foreach循环语句,这种循环效率比较低,因为每返回一个下标,还得再去寻找其值,如:
    foreach $holder (keys(%records)){
    $record = $records{$holder};
    }
         Perl提供一种更有效的循环方式,使用内嵌函数each(),如:
    %records = ("Maris", 61, "Aaron", 755, "Young", 511);
    while (($holder, $record) = each(%records)) {
    # stuff goes here
    }
         each()函数每次返回一个双元素的列表,其第一个元素为下标,第二个元素为相应的值,最后返回一个空列表。
         注意:千万不要在each()循环中添加或删除元素,否则会产生不可预料的后果。
    十、用关联数组创建数据结构
         用关联数组可以模拟在其它高级语言中常见的多种数据结构,本节讲述如何用之实现:链表、结构和树。
    1、(单)链表
         链表是一种比较简单的数据结构,可以按一定的次序存贮值。每个元素含有两个域,一个是值,一个是引用(或称指针),指向链表中下一个元素。一个特殊的头指针指向链表的第一个元素。
         在Perl中,链表很容易用关联数组实现,因为一个元素的值可以作为下一个元素的索引。下例为按字母顺序排列的单词链表:
    %words = ("abel", "baker", "baker", "charlie", "charlie", "delta", "delta", "");$header = "abel";
         上例中,简单变量$header含有链表中第一个单词,它同时也是关联数组第一个元素的下标,其值baker又是下一个元素的下标,依此类推。
         下标为delta的最后一个元素的值为空串,表示链表的结束。
         在将要处理的数据个数未知或其随程序运行而增长的情况下,链表十分有用。下例用链表按字母次序输出一个文件中的单词。
    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: }
         运行结果如下:
    Here are some words.
    Here are more words.
    Here are still more words.
    ^D
    Words in this file:
    are
    here
    more
    some
    still
    words
         此程序分为三个部分:
    主程序:读取输入并转换到相应的格式。子程序:add_word_to_list,建立排序单词链表。子程序:print_list,输出单词链表
         第3~17行为主程序,第4行初始化链表,将表头变量$header设为空串,第5行起的循环每次读取一行输入,第7行去掉头、尾的空格,第8行将句子分割成单词。9~15行的内循环每次处理一个单词,如果该单词的最后一个字符是标点符号,就去掉。第13行把单词转换成全小写形式,第14行传递给子程序add_word_to_list。
         子程序add_word_to_list先在第24行处检查链表是否为空。如果是,第25行将单词赋给$header,26行创建链表第一个元素,存贮在关联数组%wordlist中。如果链表非空,37行检查第一个元素是否与该单词相同,如果相同,就立刻返回。下一步检查这一新单词是否应该为链表第一个元素,即其按字母顺序先于$header。如果是这样,则:
         1、创建一个新元素,下标为该新单词,其值为原第一个单词。
         2、该新单词赋给$header。
         如果该新单词不该为第一个元素,则40~44行利用局域变量$pointer寻找其合适的有效位置,41~44行循环到$wordlist{$pointer}大于或等于$word为止。接下来46行查看该单词是否已在链表中,如果在就返回,否则47~48行将其添加到链表中。首先47行创建新元素$wordlist{$word},其值为$wordlist{$pointer},这时$wordlist{$word}和$wordlist{$pointer}指向同一个单词。然后,48行将$wordlist{$pointer}的值赋为$word,即将$wordlist{$pointer}指向刚创建的新元素$wordlist{$word}。
         最后当处理完毕后,子程序print_list()依次输出链表,局域变量$pointer含有正在输出的值,$wordlist{$pointer}为下一个要输出的值。
         注:一般不需要用链表来做这些工作,用sort()和keys()在关联数组中循环就足够了,如:
    foreach $word (sort keys(%wordlist)) {
    # print the sorted list, or whatever }
         但是,这里涉及的指针的概念在其它数据结构中很有意义。
    2、结构
         许多编程语言可以定义结构(structure),即一组数据的集合。结构中的每个元素有其自己的名字,并通过该名字来访问。
         Perl不直接提供结构这种数据结构,但可以用关联数组来模拟。例如模拟C语言中如下的结构:
    struce{
    int field1;
    int field2;
    int field3; }mystructvar;
         我们要做的是定义一个含有三个元素的关联数组,下标分别为field1、field2、field3,如:
    %mystructvar = ("field1" , "" ,
    "field2" , "" ,
    "field3" , "" ,);
         像上面C语言的定义一样,这个关联数组%mystrctvar有三个元素,下标分别为field1、field2、field3,各元素初始值均为空串。对各元素的访问和赋值通过指定下标来进行,如:
         $mystructvar{"field1"} = 17;
    3、树
         另一个经常使用的数据结构是树。树与链表类似,但每个节点指向的元素多于一个。最简单的树是二叉树,每个节点指向另外两个元素,称为左子节点和右子节点(或称孩子),每个子节点又指向两个孙子节点,依此类推。
         注:此处所说的树像上述链表一样是单向的,每个节点指向其子节点,但子节点并不指向父节点。
         树的概念可以如下描述:
    因为每个子节点均为一个树,所以左/右子节点也称为左/右子树。(有时称左/右分支)第一个节点(不是任何节点的子节点的节点)称为树的根。没有孩子(子节点)的节点称为叶节点。
         有多种使用关联数组实现树结构的方法,最好的一种应该是:给子节点分别加上left和right以访问之。例如,alphaleft和alpharight指向alpha的左右子节点。下面是用此方法创建二叉树并遍历的例程:
    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: }
         结果输出如下:
    grandchild1
    child1
    grandchild2
    parent
    grandchild3
    child2
    grandchild4
         该程序创建的二叉树如下图:

         注意函数print_tree()以次序“左子树、节点、右子树”来输出各节点的名字,这种遍历次序称为“左序遍历”。如果把第22行移到19行前,先输出节点明,再输出左子树、右子树,则为“中序遍历”,如果把第22行移到25行后,输出次序为左子树、右子树、节点,则为“右序遍历”。
         可以用同样的方法,即连接字符串构成下标,来创建其它的数据结构,如数据库等。
    展开全文
  • 第九章 关联数组/哈希表 by flamephoenix 一、数组变量的限制二、定义三、访问关联数组的元素四、增加元素五、创建关联数组六、从数组变量复制到关联数组七、元素的增删八、列出数组的索引值九、用关联数组...


    第九章 关联数组/哈希表

    by flamephoenix

    一、数组变量的限制
    二、定义
    三、访问关联数组的元素
    四、增加元素
    五、创建关联数组
    六、从数组变量复制到关联数组
    七、元素的增删
    八、列出数组的索引和值
    九、用关联数组循环
    十、用关联数组创建数据结构
      1、(单)链表
      2、结构
      3、树

    一、数组变量的限制
        在前面讲的数组变量中,可以通过下标访问其中的元素。例如,下列语句访问数组@array的第三个元素:
        $scalar = $array[2];
        虽然数组很有用,但它们有一个显著缺陷,即很难记住哪个元素存贮的什么内容。假如我们来写一个程序计算某文件中首字母大写的单词出现的次数,用数组来实现就比较困难,程序代码如下:

    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: }

        运行结果如下:

    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

        这个程序每次从标准输入文件读一行文字,第四行起的循环匹配每行中首字母大写的单词,每找到一个循环一次,赋给简单变量$word。在第六行中去掉标点后,查看该单词是否曾出现过,7~15行中在@wordlist中挨个元素做此检查,如果某个元素与$word相等,@wordcount中相应的元素就增加一个数。如果没有出现过,即@wordlist中没有元素与$word相等,16~20行给@wordlist和@wordcount增加一个新元素。
    二、定义
        正如你所看到的,使用数组元素产生了一些问题。首先,@wordlist中哪个元素对应着哪个单词并不明显;更糟的是,每读进一个新单词,程序必须检查整个列表才能知道该单词是否曾经出现过,当列表变得较大时,这是很耗费时间的。
        这些问题产生的原因是数组元素通过数字下标访问,为了解决这类问题,Perl定义了另一种数组,可以用任意简单变量值来访问其元素,这种数组叫做关联数组,也叫哈希表。
        为了区分关联数组变量与普通的数组变量,Perl使用%作为其首字符,而数组变量以@打头。与其它变量名一样,%后的第一个字符必须为字母,后续字符可以为字母、数字或下划线。
    三、访问关联数组的元素
        关联数组的下标可以为任何简单/标量值,访问单个元素时以$符号打头,下标用大括号围起来。例如:

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

        简单变量也可作为下标,如:
        $fruit{$my_fruit}
    四、增加元素
        创建一个关联数组元素最简单的方法是赋值,如语句$fruit{"bananas"} = 1; 把1赋给关联数组%fruit下标为bananas的元素,如果该元素不存在,则被创建,如果数组%fruit从未使用过,也被创建。
        这一特性使得关联数组很容易用于计数。下面我们用关联数组改写上面的程序,注意实现同样的功能此程序简化了许多。

    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: }

        运行结果如下:

    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

        你可以看到,这次程序简单多了,读取输入并存贮各单词数目从20行减少到了7行。
        本程序用关联数组%wordlist跟踪首字母大写的单词,下标就用单词本身,元素值为该单词出现的次数。第11行使用了内嵌函数keys()。这个函数返回关联数组的下标列表,foreach语句就用此列表循环。
        注:关联数组总是随机存贮的,因此当你用keys()访问其所有元素时,不保证元素以任何顺序出现,特别值得一提的是,它们不会以被创建的顺序出现。
        要想控制关联数组元素出现的次序,可以用sort()函数对keys()返回值进行排列,如:

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

    五、创建关联数组
        可以用单个赋值语句创建关联数组,如:
        %fruit = ("apples",17,"bananas",9,"oranges","none");
        此语句创建的关联数组含有下面三个元素:

    • 下标为apples的元素,值为17
    • 下标为bananas的元素,值为9
    • 下标为oranges的元素,值为none

        注:用列表给关联数组赋值时,Perl5允许使用"=>"或","来分隔下标与值,用"=>"可读性更好些,上面语句等效于:
        %fruit = ("apples"=>17,"bananas"=>9,"oranges"=>"none");
    六、从数组变量复制到关联数组
        与列表一样,也可以通过数组变量创建关联数组,当然,其元素数目应该为偶数,如:
        @fruit = ("apples",17,"bananas",9,"oranges","none");
        %fruit = @fruit;
        反之,可以把关联数组赋给数组变量,如:
        %fruit = ("grapes",11,"lemons",27);
        @fruit = %fruit;
        注意,此语句中元素次序未定义,那么数组变量@fruit可能为("grapes",11,"lemons",27)或("lemons",27,"grapes",11)。
        关联数组变量之间可以直接赋值,如:%fruit2 = %fruit1; 还可以把数组变量同时赋给一些简单变量和一个关联数组变量,如:
        ($var1, $var2, %myarray) = @list;
        此语句把@list的第一个元素赋给$var1,第二个赋给$var2,其余的赋给%myarray。
        最后,关联数组可以通过返回值为列表的内嵌函数或用户定义的子程序来创建,下例中把split()函数的返回值--一个列表--赋给一个关联数组变量。

    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");

        运行结果如下:

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

    七、元素的增删
        增加元素已经讲过,可以通过给一个未出现过的元素赋值来向关联数组中增加新元素,如$fruit{"lime"} = 1;创建下标为lime、值为1的新元素。
        删除元素的方法是用内嵌函数delete,如欲删除上述元素,则:
        delete ($fruit{"lime"});
    注意:

    1、一定要使用delete函数来删除关联数组的元素,这是唯一的方法。
    2、一定不要对关联数组使用内嵌函数push、pop、shift及splice,因为其元素位置是随机的。

    八、列出数组的索引和值
        上面已经提到,keys()函数返回关联数组下标的列表,如:

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

        这里,@fruitsubs被赋给apples、bananas、cherries构成的列表,再次提请注意,此列表没有次序,若想按字母顺序排列,可使用sort()函数。
        @fruitindexes = sort keys(%fruits);
        这样结果为("apples","bananas","cherries")。类似的,内嵌函数values()返回关联数组值的列表,如:

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

        这里,@fruitvalues可能的结果为(9,23.11),次序可能不同。
    九、用关联数组循环
        前面已经出现过利用keys()函数的foreach循环语句,这种循环效率比较低,因为每返回一个下标,还得再去寻找其值,如:

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

        Perl提供一种更有效的循环方式,使用内嵌函数each(),如:

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

        each()函数每次返回一个双元素的列表,其第一个元素为下标,第二个元素为相应的值,最后返回一个空列表。
        注意:千万不要在each()循环中添加或删除元素,否则会产生不可预料的后果。
    十、用关联数组创建数据结构
        用关联数组可以模拟在其它高级语言中常见的多种数据结构,本节讲述如何用之实现:链表、结构和树。
    1、(单)链表
        链表是一种比较简单的数据结构,可以按一定的次序存贮值。每个元素含有两个域,一个是值,一个是引用(或称指针),指向链表中下一个元素。一个特殊的头指针指向链表的第一个元素。
        在Perl中,链表很容易用关联数组实现,因为一个元素的值可以作为下一个元素的索引。下例为按字母顺序排列的单词链表:

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

        上例中,简单变量$header含有链表中第一个单词,它同时也是关联数组第一个元素的下标,其值baker又是下一个元素的下标,依此类推。
        下标为delta的最后一个元素的值为空串,表示链表的结束。
        在将要处理的数据个数未知或其随程序运行而增长的情况下,链表十分有用。下例用链表按字母次序输出一个文件中的单词。

    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: }

        运行结果如下:

    Here are some words.
    Here are more words.
    Here are still more words.
    ^D
    Words in this file:
    are
    here
    more
    some
    still
    words

        此程序分为三个部分:

    • 主程序:读取输入并转换到相应的格式。
    • 子程序:add_word_to_list,建立排序单词链表。
    • 子程序:print_list,输出单词链表

        第3~17行为主程序,第4行初始化链表,将表头变量$header设为空串,第5行起的循环每次读取一行输入,第7行去掉头、尾的空格,第8行将句子分割成单词。9~15行的内循环每次处理一个单词,如果该单词的最后一个字符是标点符号,就去掉。第13行把单词转换成全小写形式,第14行传递给子程序add_word_to_list。
        子程序add_word_to_list先在第24行处检查链表是否为空。如果是,第25行将单词赋给$header,26行创建链表第一个元素,存贮在关联数组%wordlist中。如果链表非空,37行检查第一个元素是否与该单词相同,如果相同,就立刻返回。下一步检查这一新单词是否应该为链表第一个元素,即其按字母顺序先于$header。如果是这样,则:
        1、创建一个新元素,下标为该新单词,其值为原第一个单词。
        2、该新单词赋给$header。
        如果该新单词不该为第一个元素,则40~44行利用局域变量$pointer寻找其合适的有效位置,41~44行循环到$wordlist{$pointer}大于或等于$word为止。接下来46行查看该单词是否已在链表中,如果在就返回,否则47~48行将其添加到链表中。首先47行创建新元素$wordlist{$word},其值为$wordlist{$pointer},这时$wordlist{$word}和$wordlist{$pointer}指向同一个单词。然后,48行将$wordlist{$pointer}的值赋为$word,即将$wordlist{$pointer}指向刚创建的新元素$wordlist{$word}。
        最后当处理完毕后,子程序print_list()依次输出链表,局域变量$pointer含有正在输出的值,$wordlist{$pointer}为下一个要输出的值。
        注:一般不需要用链表来做这些工作,用sort()和keys()在关联数组中循环就足够了,如:

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

        但是,这里涉及的指针的概念在其它数据结构中很有意义。
    2、结构
        许多编程语言可以定义结构(structure),即一组数据的集合。结构中的每个元素有其自己的名字,并通过该名字来访问。
        Perl不直接提供结构这种数据结构,但可以用关联数组来模拟。例如模拟C语言中如下的结构:

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

        我们要做的是定义一个含有三个元素的关联数组,下标分别为field1、field2、field3,如:

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

        像上面C语言的定义一样,这个关联数组%mystrctvar有三个元素,下标分别为field1、field2、field3,各元素初始值均为空串。对各元素的访问和赋值通过指定下标来进行,如:
        $mystructvar{"field1"} = 17;
    3、树
        另一个经常使用的数据结构是树。树与链表类似,但每个节点指向的元素多于一个。最简单的树是二叉树,每个节点指向另外两个元素,称为左子节点和右子节点(或称孩子),每个子节点又指向两个孙子节点,依此类推。
        注:此处所说的树像上述链表一样是单向的,每个节点指向其子节点,但子节点并不指向父节点。
        树的概念可以如下描述:

    • 因为每个子节点均为一个树,所以左/右子节点也称为左/右子树。(有时称左/右分支)
    • 第一个节点(不是任何节点的子节点的节点)称为树的根。
    • 没有孩子(子节点)的节点称为叶节点。

        有多种使用关联数组实现树结构的方法,最好的一种应该是:给子节点分别加上left和right以访问之。例如,alphaleft和alpharight指向alpha的左右子节点。下面是用此方法创建二叉树并遍历的例程:

    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: }

        结果输出如下:

    grandchild1
    child1
    grandchild2
    parent
    grandchild3
    child2
    grandchild4

        该程序创建的二叉树如下图:

        注意函数print_tree()以次序“左子树、节点、右子树”来输出各节点的名字,这种遍历次序称为“左序遍历”。如果把第22行移到19行前,先输出节点明,再输出左子树、右子树,则为“中序遍历”,如果把第22行移到25行后,输出次序为左子树、右子树、节点,则为“右序遍历”。
        可以用同样的方法,即连接字符串构成下标,来创建其它的数据结构,如数据库等。

    上一章 下一章 目录

     

    展开全文
  • 第九章 关联数组/哈希表by flamephoenix一、数组变量的限制二、定义三、访问关联数组的元素四、增加元素五、创建关联数组六、从数组变量复制到关联数组七、元素的增删八、列出数组的索引值九、用关联数组循环十、...

    第九章 关联数组/哈希表

    by flamephoenix

    一、数组变量的限制
    二、定义
    三、访问关联数组的元素
    四、增加元素
    五、创建关联数组
    六、从数组变量复制到关联数组
    七、元素的增删
    八、列出数组的索引和值
    九、用关联数组循环
    十、用关联数组创建数据结构
      1、(单)链表
      2、结构
      3、树

    一、数组变量的限制
        在前面讲的数组变量中,可以通过下标访问其中的元素。例如,下列语句访问数组@array的第三个元素:
        $scalar = $array[2];
        虽然数组很有用,但它们有一个显著缺陷,即很难记住哪个元素存贮的什么内容。假如我们来写一个程序计算某文件中首字母大写的单词出现的次数,用数组来实现就比较困难,程序代码如下:
    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: }
        运行结果如下:
    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
        这个程序每次从标准输入文件读一行文字,第四行起的循环匹配每行中首字母大写的单词,每找到一个循环一次,赋给简单变量$word。在第六行中去掉标点后,查看该单词是否曾出现过,7~15行中在@wordlist中挨个元素做此检查,如果某个元素与$word相等,@wordcount中相应的元素就增加一个数。如果没有出现过,即@wordlist中没有元素与$word相等,16~20行给@wordlist和@wordcount增加一个新元素。
    二、定义
        正如你所看到的,使用数组元素产生了一些问题。首先,@wordlist中哪个元素对应着哪个单词并不明显;更糟的是,每读进一个新单词,程序必须检查整个列表才能知道该单词是否曾经出现过,当列表变得较大时,这是很耗费时间的。
        这些问题产生的原因是数组元素通过数字下标访问,为了解决这类问题,Perl定义了另一种数组,可以用任意简单变量值来访问其元素,这种数组叫做关联数组,也叫哈希表。
        为了区分关联数组变量与普通的数组变量,Perl使用%作为其首字符,而数组变量以@打头。与其它变量名一样,%后的第一个字符必须为字母,后续字符可以为字母、数字或下划线。
    三、访问关联数组的元素
        关联数组的下标可以为任何简单/标量值,访问单个元素时以$符号打头,下标用大括号围起来。例如:
    $fruit{"bananas"}
    $number{3.14159}
    $integer{-7}
        简单变量也可作为下标,如:
        $fruit{$my_fruit}
    四、增加元素
        创建一个关联数组元素最简单的方法是赋值,如语句$fruit{"bananas"} = 1; 把1赋给关联数组%fruit下标为bananas的元素,如果该元素不存在,则被创建,如果数组%fruit从未使用过,也被创建。
        这一特性使得关联数组很容易用于计数。下面我们用关联数组改写上面的程序,注意实现同样的功能此程序简化了许多。
    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: }
        运行结果如下:
    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
        你可以看到,这次程序简单多了,读取输入并存贮各单词数目从20行减少到了7行。
        本程序用关联数组%wordlist跟踪首字母大写的单词,下标就用单词本身,元素值为该单词出现的次数。第11行使用了内嵌函数keys()。这个函数返回关联数组的下标列表,foreach语句就用此列表循环。
        注:关联数组总是随机存贮的,因此当你用keys()访问其所有元素时,不保证元素以任何顺序出现,特别值得一提的是,它们不会以被创建的顺序出现。
        要想控制关联数组元素出现的次序,可以用sort()函数对keys()返回值进行排列,如:
    foreach $capword (sort keys(%wordlist)) {
      print ("$capword: $wordlist{$capword}/n");
    }
    五、创建关联数组
        可以用单个赋值语句创建关联数组,如:
        %fruit = ("apples",17,"bananas",9,"oranges","none");
        此语句创建的关联数组含有下面三个元素:
    下标为apples的元素,值为17 下标为bananas的元素,值为9 下标为oranges的元素,值为none
        注:用列表给关联数组赋值时,Perl5允许使用"=>"或","来分隔下标与值,用"=>"可读性更好些,上面语句等效于:
        %fruit = ("apples"=>17,"bananas"=>9,"oranges"=>"none");
    六、从数组变量复制到关联数组
        与列表一样,也可以通过数组变量创建关联数组,当然,其元素数目应该为偶数,如:
        @fruit = ("apples",17,"bananas",9,"oranges","none");
        %fruit = @fruit;
        反之,可以把关联数组赋给数组变量,如:
        %fruit = ("grapes",11,"lemons",27);
        @fruit = %fruit;
        注意,此语句中元素次序未定义,那么数组变量@fruit可能为("grapes",11,"lemons",27)或("lemons",27,"grapes",11)。
        关联数组变量之间可以直接赋值,如:%fruit2 = %fruit1; 还可以把数组变量同时赋给一些简单变量和一个关联数组变量,如:
        ($var1, $var2, %myarray) = @list;
        此语句把@list的第一个元素赋给$var1,第二个赋给$var2,其余的赋给%myarray。
        最后,关联数组可以通过返回值为列表的内嵌函数或用户定义的子程序来创建,下例中把split()函数的返回值--一个列表--赋给一个关联数组变量。
    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");
        运行结果如下:
    oranges 5 apples 7 bananas 11 cherries 6
    Number of bananas: 11
    七、元素的增删
        增加元素已经讲过,可以通过给一个未出现过的元素赋值来向关联数组中增加新元素,如$fruit{"lime"} = 1;创建下标为lime、值为1的新元素。
        删除元素的方法是用内嵌函数delete,如欲删除上述元素,则:
        delete ($fruit{"lime"});
    注意:
    1、一定要使用delete函数来删除关联数组的元素,这是唯一的方法。
    2、一定不要对关联数组使用内嵌函数push、pop、shift及splice,因为其元素位置是随机的。
    八、列出数组的索引和值
        上面已经提到,keys()函数返回关联数组下标的列表,如:
    %fruit = ("apples", 9,
              "bananas", 23,
              "cherries", 11);
    @fruitsubs = keys(%fruits);
    
        这里,@fruitsubs被赋给apples、bananas、cherries构成的列表,再次提请注意,此列表没有次序,若想按字母顺序排列,可使用sort()函数。
        @fruitindexes = sort keys(%fruits);
        这样结果为("apples","bananas","cherries")。类似的,内嵌函数values()返回关联数组值的列表,如:
    %fruit = ("apples", 9,
               "bananas", 23,
               "cherries", 11);
    @fruitvalues = values(%fruits);
    
        这里,@fruitvalues可能的结果为(9,23.11),次序可能不同。
    九、用关联数组循环
        前面已经出现过利用keys()函数的foreach循环语句,这种循环效率比较低,因为每返回一个下标,还得再去寻找其值,如:
    foreach $holder (keys(%records)){
      $record = $records{$holder};
    }
        Perl提供一种更有效的循环方式,使用内嵌函数each(),如:
    %records = ("Maris", 61, "Aaron", 755, "Young", 511);
    while (($holder, $record) = each(%records)) {
      # stuff goes here
    }
        each()函数每次返回一个双元素的列表,其第一个元素为下标,第二个元素为相应的值,最后返回一个空列表。
        注意:千万不要在each()循环中添加或删除元素,否则会产生不可预料的后果。
    十、用关联数组创建数据结构
        用关联数组可以模拟在其它高级语言中常见的多种数据结构,本节讲述如何用之实现:链表、结构和树。
    1、(单)链表
        链表是一种比较简单的数据结构,可以按一定的次序存贮值。每个元素含有两个域,一个是值,一个是引用(或称指针),指向链表中下一个元素。一个特殊的头指针指向链表的第一个元素。
        在Perl中,链表很容易用关联数组实现,因为一个元素的值可以作为下一个元素的索引。下例为按字母顺序排列的单词链表:
    %words = ("abel", "baker", 
              "baker", "charlie",
              "charlie", "delta",
              "delta", "");
    $header = "abel";
    
        上例中,简单变量$header含有链表中第一个单词,它同时也是关联数组第一个元素的下标,其值baker又是下一个元素的下标,依此类推。
        下标为delta的最后一个元素的值为空串,表示链表的结束。
        在将要处理的数据个数未知或其随程序运行而增长的情况下,链表十分有用。下例用链表按字母次序输出一个文件中的单词。
    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: }
        运行结果如下:
    Here are some words.
    Here are more words.
    Here are still more words.
    ^D
    Words in this file:
    are
    here
    more
    some
    still
    words
        此程序分为三个部分:
    主程序:读取输入并转换到相应的格式。 子程序:add_word_to_list,建立排序单词链表。 子程序:print_list,输出单词链表
        第3~17行为主程序,第4行初始化链表,将表头变量$header设为空串,第5行起的循环每次读取一行输入,第7行去掉头、尾的空格,第8行将句子分割成单词。9~15行的内循环每次处理一个单词,如果该单词的最后一个字符是标点符号,就去掉。第13行把单词转换成全小写形式,第14行传递给子程序add_word_to_list。
        子程序add_word_to_list先在第24行处检查链表是否为空。如果是,第25行将单词赋给$header,26行创建链表第一个元素,存贮在关联数组%wordlist中。如果链表非空,37行检查第一个元素是否与该单词相同,如果相同,就立刻返回。下一步检查这一新单词是否应该为链表第一个元素,即其按字母顺序先于$header。如果是这样,则:
        1、创建一个新元素,下标为该新单词,其值为原第一个单词。
        2、该新单词赋给$header。
        如果该新单词不该为第一个元素,则40~44行利用局域变量$pointer寻找其合适的有效位置,41~44行循环到$wordlist{$pointer}大于或等于$word为止。接下来46行查看该单词是否已在链表中,如果在就返回,否则47~48行将其添加到链表中。首先47行创建新元素$wordlist{$word},其值为$wordlist{$pointer},这时$wordlist{$word}和$wordlist{$pointer}指向同一个单词。然后,48行将$wordlist{$pointer}的值赋为$word,即将$wordlist{$pointer}指向刚创建的新元素$wordlist{$word}。
        最后当处理完毕后,子程序print_list()依次输出链表,局域变量$pointer含有正在输出的值,$wordlist{$pointer}为下一个要输出的值。
        注:一般不需要用链表来做这些工作,用sort()和keys()在关联数组中循环就足够了,如:
    foreach $word (sort keys(%wordlist)) {
      # print the sorted list, or whatever }
        但是,这里涉及的指针的概念在其它数据结构中很有意义。
    2、结构
        许多编程语言可以定义结构(structure),即一组数据的集合。结构中的每个元素有其自己的名字,并通过该名字来访问。
        Perl不直接提供结构这种数据结构,但可以用关联数组来模拟。例如模拟C语言中如下的结构:
    struce{
      int field1;
      int field2;
      int field3; }mystructvar;
        我们要做的是定义一个含有三个元素的关联数组,下标分别为field1、field2、field3,如:
    %mystructvar = ("field1" , "" ,
          "field2" , "" ,
          "field3" , "" ,);
        像上面C语言的定义一样,这个关联数组%mystrctvar有三个元素,下标分别为field1、field2、field3,各元素初始值均为空串。对各元素的访问和赋值通过指定下标来进行,如:
        $mystructvar{"field1"} = 17;
    3、树
        另一个经常使用的数据结构是树。树与链表类似,但每个节点指向的元素多于一个。最简单的树是二叉树,每个节点指向另外两个元素,称为左子节点和右子节点(或称孩子),每个子节点又指向两个孙子节点,依此类推。
        注:此处所说的树像上述链表一样是单向的,每个节点指向其子节点,但子节点并不指向父节点。
        树的概念可以如下描述:
    因为每个子节点均为一个树,所以左/右子节点也称为左/右子树。(有时称左/右分支) 第一个节点(不是任何节点的子节点的节点)称为树的根。 没有孩子(子节点)的节点称为叶节点。
        有多种使用关联数组实现树结构的方法,最好的一种应该是:给子节点分别加上left和right以访问之。例如,alphaleft和alpharight指向alpha的左右子节点。下面是用此方法创建二叉树并遍历的例程:
    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: }
        结果输出如下:
    grandchild1
    child1
    grandchild2
    parent
    grandchild3
    child2
    grandchild4
        该程序创建的二叉树如下图:

        注意函数print_tree()以次序“左子树、节点、右子树”来输出各节点的名字,这种遍历次序称为“左序遍历”。如果把第22行移到19行前,先输出节点明,再输出左子树、右子树,则为“中序遍历”,如果把第22行移到25行后,输出次序为左子树、右子树、节点,则为“右序遍历”。
        可以用同样的方法,即连接字符串构成下标,来创建其它的数据结构,如数据库等。

    上一章 下一章 目录


     
    展开全文
  • 字典:一一对应(映射) 键(key)-->值(value) 字典是另一种可变容器模型,且...字典由多个键对应值成对组成。字典使用大括号(标志) 索引方式用中括号 ,但不是用索引值,而是使用字典中的键,可以是整形变量
  • 通过学习官方APIcookbook,我总结了如下原因: 1.从API中我们了解到,ArrayObject都是动态类,也就是我们可以给他们动态添加属性。 var obj:Object = new Object(); obj.prop1 = "value1"; obj....
  • 其中数字索引数组和C语言中的数组一样,下标是为0,1,2…而关联数组下标可能是任意类型,与其它语言中的hash,map等结构相似。 下面介绍PHP中遍历关联数组的三种方法:方法1:foreach view source ...
  • 关联数组(associative array )是一种常用的抽象数据类型。它有很多别名,例如associative container , map , mapping , dictionary ...它的特点是由一个关键字其他...而用于描述关联数组最常用的是哈希表 (has...
  • 算法有高效的,也有拙劣的,好的算法能够达到四两拨千斤的效果,但差的算法会消耗大量的内存运行时间。效果相差甚远。 算法可以应用在以下场景: 1、运算 2、查找 3、排序 4、最优决策 二、数据结构 数据结构是...
  • 哈希表

    2019-09-19 19:49:56
    一、哈希表别称:关联数组、映射、特征表字典 哈希表作为一种抽象数据类型,包括数据成员增删改查操作、哈希、冲突及解决方案(open address) 在Python中是一种字典的存在,那么,可以作为Key的数据类型是int...
  • 轻松学习C#的哈希表

    2021-01-20 06:39:48
    在C#语言中,还有一种用于快速搜索而组织的键/值组合的数组,这种数组叫做关联数组,也叫做哈希表(Hashtable)。  哈希表也在System.Collection命名空间下,用于处理表现类似key/value的键值对,其中key通常用来...
  • C#拾遗之哈希表

    千次阅读 2015-04-05 14:20:09
    在C#语言中,还有一种用于快速搜索而组织的键/值组合的数组,这种数组叫做关联数组,也叫做哈希表(Hashtable)。  哈希表也在System.Collection命名空间下,用于处理表现类似key/value的键值对,其中key通常用来...
  • 本文大家重点讨论一下Perl引用数组的概念,Perl5中的两种Perl引用类型为硬引用...Perl学习笔记一、Perl引用简介Perl引用就是指针,可以指向变量、数组、哈希表(也叫关联数组)甚至子程序。Pascal或C程序员应该对...
  • perl 基本命令[hash]

    2012-07-28 12:29:21
    1. perl hash表的简介: http://www.cnblogs.com/nwf5d/archive/2011/11/10/2244866.html 2. perl 关联数组 http://developer.51cto.com/art/201007/212308.htm ...关联数组和哈希表是同一个东西
  • 数据结构之哈希表HashTable实例讲解

    千次阅读 2018-06-06 14:56:25
    哈希表 是一种以关联方式存储数据的数据结构,在哈希表中,数据以数组格式存储,其中每个数据值都有自己唯一的索引。如果我们知道所需数据的索引,那么数据的访问就会变得非常快。 所以关键是 找到索引, 而检索 ...
  • Hash Table 哈希表介绍

    2012-10-09 13:55:34
    Hash Table是一种数组,可以用任意简单变量值来访问其元素,这种数组叫做关联数组,也叫哈希表。键/值对的集合。 二.优点: 哈希表最大的优点就是把数据的存储查找消耗的时间大大降低,几乎可以看成是常数时间...
  • PHP数组 特点:可以存储任意类型的数据,可以不连续,可以是索引的也可以是关联的 ...就是我们的哈希表集合,在定义的时候,必须给它一个key,一个values,这两个是关联的,通过key对应的values值是关联的。...
  • 本文从数据结构角度认识哈希表,更多关于Java编程中HashMap的用法见:对HashMap的简单认识 1. 什么是哈希表 ...而哈希表的设计采用了函数映射的思想,将记录的存储位置与记录的关键字关联起来。这样的设计方
  • 哈希表的设计采用了函数映射的思想,将记录的存储位置与记录的关键字关联起来 这样的设计方式,能够快速定位到想要查找的记录 而且不需要与表中存在的记录的关键字比较后再来进行查找 数组使用过数据的索引来取出...
  • 哈希表可以认为是一种特殊的数组,一个重要的特性是“数据项的关键字与数组下标有关联”。(数据项的关键字经过简单计算便可得到数组下标,从而实现快速存取) 优点与缺点 优点 提供快速的插入操作查找操作,...
  • 在PHP里面使用最多的数据结构恐怕就是数组了,不过PHP的数组和我们传统意义上的数组区别很大,PHP的数组功能上相当于其它语言里面array...PHP的数组底层是使用HashTable实现,说到哈希表估计很多人都了解过,PHP数组...
  • 哈希函数 哈希表 碰撞

    千次阅读 2010-06-13 13:46:00
    哈希表:一种将键关联在一起的数据结构。其主要操作是可以高效的通过键来定位其值,该过程是通过哈希函数来计算键的哈希值,然后通过哈希值直接定位所需要的值。 碰撞:若不同的键所计算的哈希值相同...
  • 哈希表是比数组更复杂的数据结构,在某些语言里被称作关联数组或者字典等等。简单说,哈希表用于存放指定键(key)对应的值(value),键值的关系,就像字典中单词释义的对应关系,通过单词可以快速找到释义,而...
  • 关于数据的处理,不同的数据结构各有千秋。 线性表中的栈队列对增删有严格要求,它们会更...哈希表的设计采用了函数映射的思想,将记录的存储位置与记录的关键字关联起来。这样的设计方式,能够快速定位到想要查找
  • 在计算机中,散列表 是 一种实现了关联数组 抽象数据类型的数据结构,这种数据结构可以映射 键(key) 值(value). 补充: 关联数组:在计算机科学中,一个关联数组(associative array),映射(map),符号...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 360
精华内容 144
关键字:

关联数组和哈希表