Chinaunix首页 | 论坛 | 博客
  • 博客访问: 54871
  • 博文数量: 23
  • 博客积分: 1598
  • 博客等级: 上尉
  • 技术积分: 210
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-27 10:26
文章分类

全部博文(23)

文章存档

2011年(2)

2010年(21)

我的朋友

分类: 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行后,输出次序为左子树、右子树、节点,则为“右序遍历”。 可以用同样的方法,即连接字符串构成下标,来创建其它的数据结构,如数据库等。

  1. %hash={a,”A”,”b”,”B”,”c”,”C”…}
  2. %hash{a}=“A”; 
    %hash{b}=“B”; 
    %hash{c}=“C”; 
  3. %hash={a⇒“A”,b⇒“B”,c⇒“C”…}

%hash{a}

%re_hash=reverse %hash; 
%re_hash{A}

  1. 测试%hash中是否存在某个关键字 exist $hash{c}
  2. 删除关键字 delete $hash{b}

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;

阅读(361) | 评论(0) | 转发(0) |
0

上一篇:Perl 语法小结5

下一篇:Perl 语法小结3

给主人留下些什么吧!~~