perl5中文教程--第九章 关联数组/哈希表

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