📄 perl9.htm
字号:
# stuff goes here<br>
}
</blockquote>
each()函数每次返回一个双元素的列表，其第一个元素为下标，第二个元素为相应的值，最后返回一个空列表。<br>
注意：千万不要在each()循环中添加或删除元素，否则会产生不可预料的后果。<br>
<a name="10">十、用关联数组创建数据结构</a><br>
用关联数组可以模拟在其它高级语言中常见的多种数据结构，本节讲述如何用之实现：链表、结构和树。<br>
<a name="10.1">1、(单)链表<br>
链表是一种比较简单的数据结构，可以按一定的次序存贮值。每个元素含有两个域，一个是值，一个是引用（或称指针），指向链表中下一个元素。一个特殊的头指针指向链表的第一个元素。<br>
在Perl中，链表很容易用关联数组实现，因为一个元素的值可以作为下一个元素的索引。下例为按字母顺序排列的单词链表：<br>
<blockquote><pre>
%words = ("abel", "baker",
"baker", "charlie",
"charlie", "delta",
"delta", "");
$header = "abel";
</pre></blockquote>
上例中，简单变量$header含有链表中第一个单词，它同时也是关联数组第一个元素的下标，其值baker又是下一个元素的下标，依此类推。<br>
下标为delta的最后一个元素的值为空串，表示链表的结束。<br>
在将要处理的数据个数未知或其随程序运行而增长的情况下，链表十分有用。下例用链表按字母次序输出一个文件中的单词。<br>
<blockquote>
1 : #!/usr/local/bin/perl<br>
2 :<br>
3 : # initialize list to empty<br>
4 : $header = "";<br>
5 : while ($line = <STDIN>) {<br>
6 : # remove leading and trailing spaces<br>
7 : $line =~ s/^\s+|\s+$//g;<br>
8 : @words = split(/\s+/, $line);<br>
9 : foreach $word (@words) {<br>
10: # remove closing punctuation, if any<br>
11: $word =~ s/[.,;:-]$//;<br>
12: # convert all words to lower case<br>
13: $word =~ tr/A-Z/a-z/;<br>
14: &add_word_to_list($word);<br>
15: }<br>
16: }<br>
17: &print_list;<br>
18:<br>
19: sub add_word_to_list {<br>
20: local($word) = @_;<br>
21: local($pointer);<br>
22:<br>
23: # if list is empty, add first item<br>
24: if ($header eq "") {<br>
25: $header = $word;<br>
26: $wordlist{$word} = "";<br>
27: return;<br>
28: }<br>
29: # if word identical to first element in list,<br>
30: # do nothing<br>
31: return if ($header eq $word);<br>
32: # see whether word should be the new<br>
33: # first word in the list<br>
34: if ($header gt $word) {<br>
35: $wordlist{$word} = $header;<br>
36: $header = $word;<br>
37: return;<br>
38: }<br>
39: # find place where word belongs<br>
40: $pointer = $header;<br>
41: while ($wordlist{$pointer} ne "" &&<br>
42: $wordlist{$pointer} lt $word) {<br>
43: $pointer = $wordlist{$pointer};<br>
44: }<br>
45: # if word already seen, do nothing<br>
46: return if ($word eq $wordlist{$pointer});<br>
47: $wordlist{$word} = $wordlist{$pointer};<br>
48: $wordlist{$pointer} = $word;<br>
49: }<br>
50:<br>
51: sub print_list {<br>
52: local ($pointer);<br>
53: print ("Words in this file:\n");<br>
54: $pointer = $header;<br>
55: while ($pointer ne "") {<br>
56: print ("$pointer\n");<br>
57: $pointer = $wordlist{$pointer};<br>
58: }<br>
59: }
</blockquote>
运行结果如下：<br>
<blockquote>
Here are some words.<br>
Here are more words.<br>
Here are still more words.<br>
^D<br>
Words in this file:<br>
are<br>
here<br>
more<br>
some<br>
still<br>
words
</blockquote>
此程序分为三个部分：<br>
<blockquote>
<li>主程序：读取输入并转换到相应的格式。</li>
<li>子程序：add_word_to_list，建立排序单词链表。</li>
<li>子程序：print_list，输出单词链表</li>
</blockquote>
第3~17行为主程序，第4行初始化链表，将表头变量$header设为空串，第5行起的循环每次读取一行输入，第7行去掉头、尾的空格，第8行将句子分割成单词。9~15行的内循环每次处理一个单词，如果该单词的最后一个字符是标点符号，就去掉。第13行把单词转换成全小写形式，第14行传递给子程序add_word_to_list。<br>
子程序add_word_to_list先在第24行处检查链表是否为空。如果是，第25行将单词赋给$header，26行创建链表第一个元素，存贮在关联数组%wordlist中。如果链表非空，37行检查第一个元素是否与该单词相同，如果相同，就立刻返回。下一步检查这一新单词是否应该为链表第一个元素，即其按字母顺序先于$header。如果是这样，则：<br>
1、创建一个新元素，下标为该新单词，其值为原第一个单词。<br>
2、该新单词赋给$header。<br>
如果该新单词不该为第一个元素，则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}。<br>
最后当处理完毕后，子程序print_list()依次输出链表，局域变量$pointer含有正在输出的值，$wordlist{$pointer}为下一个要输出的值。<br>
注：一般不需要用链表来做这些工作，用sort()和keys()在关联数组中循环就足够了，如：<br>
<blockquote>
foreach $word (sort keys(%wordlist)) {<br>
# print the sorted list, or whatever
}
</blockquote>
但是，这里涉及的指针的概念在其它数据结构中很有意义。<br>
<a name="10.2">2、结构</a><br>
许多编程语言可以定义结构(structure)，即一组数据的集合。结构中的每个元素有其自己的名字，并通过该名字来访问。<br>
Perl不直接提供结构这种数据结构，但可以用关联数组来模拟。例如模拟C语言中如下的结构：<br>
<blockquote>
struce{<br>
int field1;<br>
int field2;<br>
int field3;
}mystructvar;
</blockquote>
我们要做的是定义一个含有三个元素的关联数组，下标分别为field1、field2、field3，如：<br>
<blockquote>
%mystructvar = ("field1" , "" ,<br>
"field2" , "" ,<br>
"field3" , "" ,);
</blockquote>
像上面C语言的定义一样，这个关联数组%mystrctvar有三个元素，下标分别为field1、field2、field3，各元素初始值均为空串。对各元素的访问和赋值通过指定下标来进行，如：<br>
$mystructvar{"field1"} = 17;<br>
<a name="10.3">3、树</a><br>
另一个经常使用的数据结构是树。树与链表类似，但每个节点指向的元素多于一个。最简单的树是二叉树，每个节点指向另外两个元素，称为左子节点和右子节点（或称孩子），每个子节点又指向两个孙子节点，依此类推。<br>
注：此处所说的树像上述链表一样是单向的，每个节点指向其子节点，但子节点并不指向父节点。<br>
树的概念可以如下描述：<br>
<blockquote>
<li>因为每个子节点均为一个树，所以左/右子节点也称为左/右子树。（有时称左/右分支）</li>
<li>第一个节点（不是任何节点的子节点的节点）称为树的根。</li>
<li>没有孩子（子节点）的节点称为叶节点。</li>
</blockquote>
有多种使用关联数组实现树结构的方法，最好的一种应该是：给子节点分别加上left和right以访问之。例如，alphaleft和alpharight指向alpha的左右子节点。下面是用此方法创建二叉树并遍历的例程：<br>
<blockquote>
1 : #!/usr/local/bin/perl<br>
2 :<br>
3 : $rootname = "parent";<br>
4 : %tree = ("parentleft", "child1",<br>
5 : "parentright", "child2",<br>
6 : "child1left", "grandchild1",<br>
7 : "child1right", "grandchild2",<br>
8 : "child2left", "grandchild3",<br>
9 : "child2right", "grandchild4");<br>
10: # traverse tree, printing its elements<br>
11: &print_tree($rootname);<br>
12:<br>
13: sub print_tree {<br>
14: local ($nodename) = @_;<br>
15: local ($leftchildname, $rightchildname);<br>
16:<br>
17: $leftchildname = $nodename . "left";<br>
18: $rightchildname = $nodename . "right";<br>
19: if ($tree{$leftchildname} ne "") {<br>
20: &print_tree($tree{$leftchildname});<br>
21: }<br>
22: print ("$nodename\n");<br>
23: if ($tree{$rightchildname} ne "") {<br>
24: &print_tree($tree{$rightchildname});<br>
25: }<br>
26: }
</blockquote>
结果输出如下：<br>
<blockquote>
grandchild1<br>
child1<br>
grandchild2<br>
parent<br>
grandchild3<br>
child2<br>
grandchild4
</blockquote>
该程序创建的二叉树如下图：<br>
<p align="center"><img src="tree.gif"></p>
注意函数print_tree()以次序“左子树、节点、右子树”来输出各节点的名字，这种遍历次序称为“左序遍历”。如果把第22行移到19行前，先输出节点明，再输出左子树、右子树，则为“中序遍历”，如果把第22行移到25行后，输出次序为左子树、右子树、节点，则为“右序遍历”。<br>
可以用同样的方法，即连接字符串构成下标，来创建其它的数据结构，如数据库等。<br>
<p align="center"><a href="perl8.htm">上一章</a> <a href="perl10.htm">下一章</a> <a href="index.htm">目录</a></p>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -