分类: LINUX
2010-09-19 15:38:32
用关联数组可以模拟在其它高级语言中常见的多种数据结构,本节讲述如何用之实现:链表、结构和树。
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 = (/\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: ($word) = @_; 21: ($pointer); 22: 23: # if list is empty, add first item 24: if ($header eq "") { 25: $header = $word; 26: $wordlist{$word} = ""; 27: ; 28: } 29: # if word identical to first element in list, 30: # do nothing 31: 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: ; 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: if ($word eq $wordlist{$pointer}); 47: $wordlist{$word} = $wordlist{$pointer}; 48: $wordlist{$pointer} = $word; 49: } 50: 51: sub print_list { 52: ($pointer); 53: ("Words in this file:\n"); 54: $pointer = $header; 55: while ($pointer ne "") { 56: ("$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: ($nodename) = @_; 15: ($leftchildname, $rightchildname); 16: 17: $leftchildname = $nodename . "left"; 18: $rightchildname = $nodename . "right"; 19: if ($tree{$leftchildname} ne "") { 20: &print_tree($tree{$leftchildname}); 21: } 22: ("$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行后,输出次序为左子树、右子树、节点,则为“右序遍历”。 可以用同样的方法,即连接字符串构成下标,来创建其它的数据结构,如数据库等。
%hash{a}
%re_hash=reverse %hash;
%re_hash{A}
while(<>){ while(/(\w[\w-]*/g){ $words{$1}++; } }
与C语言类似的语法
if(/^aa/){ } else { }
sub subname { ($a,$b,$c)=@_; #或者使用$_[0],$_[1]来调用, #如果参数是两个及以上的数组或哈希结构,那么可能会丢失分组信息, #均已列表的形式传递给@_。 } &subname("a","b","c");#函数的定义可以在任何地方 subname("a","b","c");#函数的定义必须在调用之前
可使用return来返回值,可返回数组和哈希结构。
my可以在子例程中可缩小作用域于该例程中。
open(FH,"a.txt")||die "can not open to read"; close(FH); open(FH,">b.txt")||die "can not open to write"; close(FH);
(DH,"/usr/eda/mydir")||die "can not open the dir"; @file_and_dirs=; read_dir DH;