📄 ch09_01.htm
字号:
<html><head><title>Data Structures (Programming Perl)</title><!-- STYLESHEET --><link rel="stylesheet" type="text/css" href="../style/style1.css"><!-- METADATA --><!--Dublin Core Metadata--><meta name="DC.Creator" content=""><meta name="DC.Date" content=""><meta name="DC.Format" content="text/xml" scheme="MIME"><meta name="DC.Generator" content="XSLT stylesheet, xt by James Clark"><meta name="DC.Identifier" content=""><meta name="DC.Language" content="en-US"><meta name="DC.Publisher" content="O'Reilly & Associates, Inc."><meta name="DC.Source" content="" scheme="ISBN"><meta name="DC.Subject.Keyword" content=""><meta name="DC.Title" content="Data Structures"><meta name="DC.Type" content="Text.Monograph"></head><body><!-- START OF BODY --><!-- TOP BANNER --><img src="gifs/smbanner.gif" usemap="#banner-map" border="0" alt="Book Home"><map name="banner-map"><AREA SHAPE="RECT" COORDS="0,0,466,71" HREF="index.htm" ALT="Programming Perl"><AREA SHAPE="RECT" COORDS="467,0,514,18" HREF="jobjects/fsearch.htm" ALT="Search this book"></map><!-- TOP NAV BAR --><div class="navbar"><table width="515" border="0"><tr><td align="left" valign="top" width="172"><a href="ch08_05.htm"><img src="../gifs/txtpreva.gif" alt="Previous" border="0"></a></td><td align="center" valign="top" width="171"><a href="part2.htm">Part 2: The Gory Details</a></td><td align="right" valign="top" width="172"><a href="ch09_02.htm"><img src="../gifs/txtnexta.gif" alt="Next" border="0"></a></td></tr></table></div><hr width="515" align="left"><!-- SECTION BODY --><h1 class="chapter">Chapter 9. Data Structures</h1><div class="htmltoc"><h4 class="tochead">Contents:</h4><p><a href="ch09_01.htm">Arrays of Arrays</a><br><a href="ch09_02.htm">Hashes of Arrays</a><br><a href="ch09_03.htm">Arrays of Hashes</a><br><a href="ch09_04.htm">Hashes of Hashes</a><br><a href="ch09_05.htm">Hashes of Functions</a><br><a href="ch09_06.htm">More Elaborate Records</a><br><a href="ch09_07.htm">Saving Data Structures</a><br></p></div><a name="INDEX-2070"></a><p><a name="INDEX-2071"></a><a name="INDEX-2072"></a><a name="INDEX-2073"></a><a name="INDEX-2074"></a><a name="INDEX-2075"></a><a name="INDEX-2076"></a><a name="INDEX-2077"></a>Perl provides for free many of the data structures that you have tobuild yourself in other programming languages. The stacks and queuesthat budding computer scientists learn about are both just arrays inPerl. When you <tt class="literal">push</tt> and <tt class="literal">pop</tt> (or<tt class="literal">shift</tt> and <tt class="literal">unshift</tt>) an array,it's a stack; when you <tt class="literal">push</tt> and<tt class="literal">shift</tt> (or <tt class="literal">unshift</tt> and<tt class="literal">pop</tt>) an array, it's a queue. And many of the treestructures in the world are built only to provide fast, dynamic accessto a conceptually flat lookup table. Hashes, of course, are builtinto Perl, and provide fast, dynamic access to a conceptually flatlookup table, only without the mind-numbingly recursive datastructures that are claimed to be beautiful by people whose minds havebeen suitably numbed already.</p><p><a name="INDEX-2078"></a>But sometimes you want nested data structures because they mostnaturally model the problem you're trying to solve. So Perl lets youcombine and nest arrays and hashes to create arbitrarily complex datastructures. Properly applied, they can be used to create linkedlists, binary trees, heaps, B-trees, sets, graphs, and anything elseyou can devise. See <em class="citetitle">Mastering Algorithms withPerl</em> (O'Reilly, 1999), the <em class="citetitle">PerlCookbook</em> (O'Reilly, 1998), or CPAN, the central repositoryfor all such modules. But simple combinations of arrays and hashesmay be all you ever need, so they're what we'll talk about in thischapter.</p><h2 class="sect1">9.1. Arrays of Arrays</h2><p><a name="INDEX-2079"></a><a name="INDEX-2080"></a><a name="INDEX-2081"></a><a name="INDEX-2082"></a><a name="INDEX-2083"></a><a name="INDEX-2084"></a><a name="INDEX-2085"></a></p><p>There are many kinds of nested data structures. The simplest kind tobuild is an array of arrays, also called a two-dimensional array or amatrix. (The obvious generalization applies: an array of arrays ofarrays is a three-dimensional array, and so on for higher dimensions.)It's reasonably easy to understand, and nearly everything that applieshere will also be applicable to the fancier data structures that we'llexplore in subsequent sections.</p><h3 class="sect2">9.1.1. Creating and Accessing a Two-Dimensional Array</h3><p><a name="INDEX-2086"></a><a name="INDEX-2087"></a><a name="INDEX-2088"></a>Here's how to put together a two-dimensional array:<blockquote><pre class="programlisting"># Assign a list of array references to an array.@AoA = ( [ "fred", "barney" ], [ "george", "jane", "elroy" ], [ "homer", "marge", "bart" ],);print $AoA[2][1]; # prints "marge"</pre></blockquote>The overall list is enclosed by parentheses, not brackets, becauseyou're assigning a list and not a reference. If you wanted areference to an array instead, you'd use brackets:<blockquote><pre class="programlisting"># Create an reference to an array of array references.$ref_to_AoA = [ [ "fred", "barney", "pebbles", "bamm bamm", "dino", ], [ "homer", "bart", "marge", "maggie", ], [ "george", "jane", "elroy", "judy", ],];print $ref_to_AoA->[2][3]; # prints "judy"</pre></blockquote>Remember that there is an implied <tt class="literal">-></tt> between every pair ofadjacent braces or brackets. Therefore these two lines:<blockquote><pre class="programlisting">$AoA[2][3]$ref_to_AoA->[2][3]</pre></blockquote>are equivalent to these two lines:<blockquote><pre class="programlisting">$AoA[2]->[3]$ref_to_AoA->[2]->[3]</pre></blockquote>There is, however, no implied <tt class="literal">-></tt> before thefirst pair of brackets, which is why the dereference of<tt class="literal">$ref_to_AoA</tt> requires the initial<tt class="literal">-></tt>. Also remember that you can count backwardfrom the end of an array with a negative index, so:<blockquote><pre class="programlisting">$AoA[0][-2]</pre></blockquote>is the next-to-last element of the first row.</p><h3 class="sect2">9.1.2. Growing Your Own</h3><p><a name="INDEX-2089"></a>Those big list assignments are well and good for creating a fixed datastructure, but what if you want to calculate each element on the fly,or otherwise build the structure piecemeal?</p><p>Let's read in a data structure from a file. We'll assume that it's aplain text file, where each line is a row of the structure, and eachline consists of elements delimited by whitespace. Here's how toproceed:<a href="#FOOTNOTE-1">[1]</a><blockquote><pre class="programlisting">while (<>) { @tmp = split; # Split elements into an array. push @AoA, [ @tmp ]; # Add an anonymous array reference to @AoA.}</pre></blockquote>Of course, you don't need to name the temporary array, so you couldalso say:<blockquote><pre class="programlisting">while (<>) { push @AoA, [ split ];}</pre></blockquote>If you want a reference to an array of arrays, you can do this:<blockquote><pre class="programlisting">while (<>) { push @$ref_to_AoA, [ split ];}</pre></blockquote><a name="INDEX-2090"></a>Both of those examples add new rows to the array of arrays. What aboutadding new columns? If you're just dealing with two-dimensional arrays,it's often easiest to use simple assignment:<a href="#FOOTNOTE-2">[2]</a><blockquote><pre class="programlisting">for $x (0 .. 9) { # For each row... for $y (0 .. 9) { # For each column... $AoA[$x][$y] = func($x, $y); # ...set that cell }}for $x ( 0..9 ) { # For each row... $ref_to_AoA->[$x][3] = func2($x); # ...set the fourth column}</pre></blockquote><a name="INDEX-2091"></a>It doesn't matter in what order you assign the elements, nor does itmatter whether the subscripted elements of <tt class="literal">@AoA</tt> arealready there or not; Perl will gladly create them for you, settingintervening elements to the undefined value as need be. (Perl willeven create the original reference in <tt class="literal">$ref_to_AoA</tt>for you if it needs to.) If you just want to append to a row, youhave to do something a bit funnier:<blockquote><pre class="programlisting"># Append new columns to an existing row.push @{ $AoA[0] }, "wilma", "betty";</pre></blockquote>Notice that this wouldn't work:<blockquote><pre class="programlisting">push $AoA[0], "wilma", "betty"; # WRONG!</pre></blockquote>That won't even compile, because the argument to<tt class="literal">push</tt> must be a real array, not just a reference toan array. Therefore, the first argument absolutely must begin with an<tt class="literal">@</tt> character. What comes after the<tt class="literal">@</tt> is somewhat negotiable.</p><blockquote class="footnote"><a name="FOOTNOTE-1"></a><p>[1] Here as in other chapters, we omit (forclarity) the <tt class="literal">my</tt> declarations that you wouldordinarily put in. In this example, you'd normally write <tt class="literal">my@tmp = split</tt>.</p></blockquote><blockquote class="footnote"><a name="FOOTNOTE-2"></a><p>[2] As with the tempassignment earlier, we've simplified; the loops in this chapter wouldlikely be written <tt class="literal">for my $x</tt> in real code.</p></blockquote><h3 class="sect2">9.1.3. Access and Printing</h3><p><a name="INDEX-2092"></a><a name="INDEX-2093"></a>Now let's print the data structure. If you only want one element,this is sufficient:<blockquote><pre class="programlisting">print $AoA[3][2];</pre></blockquote>But if you want to print the whole thing, you can't just say:<blockquote><pre class="programlisting">print @AoA; # WRONG</pre></blockquote><a name="INDEX-2094"></a><a name="INDEX-2095"></a></p><p><a name="INDEX-2096"></a>It's wrong because you'll see stringified references instead of yourdata. Perl never automatically dereferences for you. Instead, youhave to roll yourself a loop or two. The following code prints thewhole structure, looping through the elements of <tt class="literal">@AoA</tt> anddereferencing each inside the <tt class="literal">print</tt> statement:<blockquote><pre class="programlisting">for $row ( @AoA ) { print "@$row\n";}</pre></blockquote>If you want to keep track of subscripts, you might do this:<blockquote><pre class="programlisting">for $i ( 0 .. $#AoA ) { print "row $i is: @{$AoA[$i]}\n";}</pre></blockquote>or maybe even this (notice the inner loop):<blockquote><pre class="programlisting">for $i ( 0 .. $#AoA ) { for $j ( 0 .. $#{$AoA[$i]} ) { print "element $i $j is $AoA[$i][$j]\n"; }}</pre></blockquote>As you can see, things are getting a bit complicated. That's whysometimes it's easier to use a temporary variable on your way through:<blockquote><pre class="programlisting">for $i ( 0 .. $#AoA ) {⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -