perl实例分析教程之十三

十、用关系数组创造数据构造 　　用关系数组不妨模仿在其它高档谈话中罕见的多种数据构造，本节报告怎样用之实行：链表、构造和树。 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 = ) { 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 ("$pointern"); 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 } 然而，这边波及的南针的观念在其它数据构造中很有意旨。