perl实例分析教程之十三-Perl-idc中文资讯站-客观公证的IDC产业权威媒体,关注域名、虚拟主机、服务器、网络、开源技术资讯，整合运营商资源，客观评价各地机房带宽线路质量、IDC企业名录等信息

perl实例分析教程之十三

来源：linux宝库作者：linux宝库发布时间:2007-09-30 00:00:00

　　十、用关联数组创建数据结构

　　用关联数组能够模拟在其他高级语言中常见的多种数据结构，本节讲述怎样用之实现：链表、结构和树。

　　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 }

　　但是，这里涉及的指针的概念在其他数据结构中很有意义。

喜欢本文，那就收藏到：

下一篇: perl实例分析教程之十二

相关推荐

相关资讯