📄 ch05_16.htm
字号:
<HTML><HEAD><TITLE>Recipe 5.15. Representing Relationships Between Data (Perl Cookbook)</TITLE><METANAME="DC.title"CONTENT="Perl Cookbook"><METANAME="DC.creator"CONTENT="Tom Christiansen & Nathan Torkington"><METANAME="DC.publisher"CONTENT="O'Reilly & Associates, Inc."><METANAME="DC.date"CONTENT="1999-07-02T01:32:57Z"><METANAME="DC.type"CONTENT="Text.Monograph"><METANAME="DC.format"CONTENT="text/html"SCHEME="MIME"><METANAME="DC.source"CONTENT="1-56592-243-3"SCHEME="ISBN"><METANAME="DC.language"CONTENT="en-US"><METANAME="generator"CONTENT="Jade 1.1/O'Reilly DocBook 3.0 to HTML 4.0"><LINKREV="made"HREF="mailto:online-books@oreilly.com"TITLE="Online Books Comments"><LINKREL="up"HREF="ch05_01.htm"TITLE="5. Hashes"><LINKREL="prev"HREF="ch05_15.htm"TITLE="5.14. Finding the Most Common Anything"><LINKREL="next"HREF="ch05_17.htm"TITLE="5.16. Program: dutree"></HEAD><BODYBGCOLOR="#FFFFFF"><img alt="Book Home" border="0" src="gifs/smbanner.gif" usemap="#banner-map" /><map name="banner-map"><area shape="rect" coords="1,-2,616,66" href="index.htm" alt="Perl Cookbook"><area shape="rect" coords="629,-11,726,25" href="jobjects/fsearch.htm" alt="Search this book" /></map><div class="navbar"><p><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch05_15.htm"TITLE="5.14. Finding the Most Common Anything"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 5.14. Finding the Most Common Anything"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><B><FONTFACE="ARIEL,HELVETICA,HELV,SANSERIF"SIZE="-1"><ACLASS="chapter"REL="up"HREF="ch05_01.htm"TITLE="5. Hashes"></A></FONT></B></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch05_17.htm"TITLE="5.16. Program: dutree"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 5.16. Program: dutree"BORDER="0"></A></TD></TR></TABLE></DIV><DIVCLASS="sect1"><H2CLASS="sect1"><ACLASS="title"NAME="ch05-chap05_representing_0">5.15. Representing Relationships Between Data</A></H2><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch05-pgfId-1306">Problem<ACLASS="indexterm"NAME="ch05-idx-1000006531-0"></A><ACLASS="indexterm"NAME="ch05-idx-1000006531-1"></A><ACLASS="indexterm"NAME="ch05-idx-1000006531-2"></A></A></H3><PCLASS="para">You want to represent relationships between elements of data - for instance, the <EMCLASS="emphasis">mother of</EM> relationship in a family tree or<EMCLASS="emphasis"> parent process</EM> for a process table. This is closely related to representing tables in relational databases (tables represent relationships between information) and to representing computer science graph structures (edges represent relationships between nodes).</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch05-pgfId-1312">Solution</A></H3><PCLASS="para">Use a hash to represent the relationship.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch05-pgfId-1318">Discussion</A></H3><PCLASS="para">Here's part of the family tree from the Bible:</P><PRECLASS="programlisting">%father = ( 'Cain' => 'Adam', 'Abel' => 'Adam', 'Seth' => 'Adam', 'Enoch' => 'Cain', 'Irad' => 'Enoch', 'Mehujael' => 'Irad', 'Methusael' => 'Mehujael', 'Lamech' => 'Methusael', 'Jabal' => 'Lamech', 'Jubal' => 'Lamech', 'Tubalcain' => 'Lamech', 'Enos' => 'Seth' );</PRE><PCLASS="para">This lets us, for instance, easily trace a person's lineage:</P><PRECLASS="programlisting">while (<>) { chomp; do { print "$_ "; # print the current name $_ = $father{$_}; # set $_ to $_'s father } while defined; # until we run out of fathers print "\n";}</PRE><PCLASS="para">We can already ask questions like "Who begat Seth?" by checking the <CODECLASS="literal">%father</CODE> hash. By inverting this hash, we invert the relationship. This lets us use <ACLASS="xref"HREF="ch05_09.htm"TITLE="Inverting a Hash">Recipe 5.8</A> to answer questions like "Whom did Lamech beget?"</P><PRECLASS="programlisting">while ( ($k,$v) = each %father ) { push( @{ $children{$v} }, $k );}$" = ', '; # separate output with commaswhile (<>) { chomp; if ($children{$_}) { @children = @{$children{$_}}; } else { @children = "nobody"; } print "$_ begat @children.\n";}</PRE><PCLASS="para">Hashes can also represent relationships such as the C language <CODECLASS="literal">#include</CODE>s. A includes B if A contains <CODECLASS="literal">#include</CODE> <CODECLASS="literal">B</CODE>. This code builds the hash (it doesn't look for files in <CODECLASS="literal">/usr/include</CODE> as it should, but that is a minor change):</P><PRECLASS="programlisting">foreach $file (@files) { local *F; # just in case we want a local FH unless (open (F, "<$file")) { warn "Couldn't read $file: $!; skipping.\n"; next; } while (<F>) { next unless /^\s*#\s*include\s*<([^>]+)>/; push(@{$includes{$1}}, $file); } close F;}</PRE><PCLASS="para">This shows which files don't include any others:</P><PRECLASS="programlisting">@include_free = (); # list of files that don't include others@uniq{map { @$_ } values %includes} = undef;foreach $file (sort keys %uniq) { push( @include_free , $file ) unless $includes{$file};}</PRE><PCLASS="para">The values of <CODECLASS="literal">%includes</CODE> are anonymous arrays because a single file can (and often does) include more than one other file. We use <CODECLASS="literal">map</CODE> to build up a big list of all the included files and remove duplicates by using a hash.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch05-pgfId-1438">See Also <ACLASS="indexterm"NAME="ch05-idx-1000006533-0"></A><ACLASS="indexterm"NAME="ch05-idx-1000006533-1"></A></A></H3><PCLASS="para"><ACLASS="xref"HREF="ch04_07.htm"TITLE="Extracting Unique Elements from a List">Recipe 4.6</A>; the more complex data structures in <ACLASS="xref"HREF="ch11_10.htm"TITLE="Constructing Records">Recipe 11.9</A> through <ACLASS="xref"HREF="ch11_15.htm"TITLE="Transparently Persistent Data Structures">Recipe 11.14</A></P></DIV></DIV><DIVCLASS="htmlnav"><P></P><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch05_15.htm"TITLE="5.14. Finding the Most Common Anything"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 5.14. Finding the Most Common Anything"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="book"HREF="index.htm"TITLE="Perl Cookbook"><IMGSRC="../gifs/txthome.gif"ALT="Perl Cookbook"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch05_17.htm"TITLE="5.16. Program: dutree"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 5.16. Program: dutree"BORDER="0"></A></TD></TR><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228">5.14. Finding the Most Common Anything</TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="index"HREF="index/index.htm"TITLE="Book Index"><IMGSRC="../gifs/index.gif"ALT="Book Index"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228">5.16. Program: dutree</TD></TR></TABLE><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><FONTSIZE="-1"></DIV<!-- LIBRARY NAV BAR --> <img src="../gifs/smnavbar.gif" usemap="#library-map" border="0" alt="Library Navigation Links"><p> <a href="copyrght.htm">Copyright © 2002</a> O'Reilly & Associates. All rights reserved.</font> </p> <map name="library-map"> <area shape="rect" coords="1,0,85,94" href="../index.htm"><area shape="rect" coords="86,1,178,103" href="../lwp/index.htm"><area shape="rect" coords="180,0,265,103" href="../lperl/index.htm"><area shape="rect" coords="267,0,353,105" href="../perlnut/index.htm"><area shape="rect" coords="354,1,446,115" href="../prog/index.htm"><area shape="rect" coords="448,0,526,132" href="../tk/index.htm"><area shape="rect" coords="528,1,615,119" href="../cookbook/index.htm"><area shape="rect" coords="617,0,690,135" href="../pxml/index.htm"></map> </BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -