📄 page348.html
字号:
<HTML><HEAD><TITLE>Applications</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5196" HREF="page349.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5194" HREF="page298.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5188" HREF="page347.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5198" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0010800000000000000000">Applications</A></H1><P>There are many applications for search trees.The principal characteristic of such applicationsis that a database of keyed information needs to be frequently accessedand the access pattern is either unknown or known to be random.For example, <em>dictionaries</em> are often implemented using search trees. A dictionary is essentially a container that contains ordered key/value pairs.The keys are words is a source language and,depending on the application,the values may be the definitions of the words orthe translation of the word in a target language.<P>This section presents a simple application of search trees.Suppose we are required to translate the words in an input fileone-by-one from some source language to another target language.In this example, the translation is done one word at a time.That is, no natural language syntactic or semantic processing is done.<P>In order to implement the translator we assume that there exists a text file,which contains pairs of words.The first element of the pair is a word in the source languageand the second element is a word in the target language.To translate a text, we first read the words and the associated translationsand build a search tree.The translation is created one word at a timeby looking up each word in the text.<P>Program <A HREF="page348.html#progalgorithmsl"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives an implementation of the translator.The <tt>translate</tt> method uses a search tree to hold the pairs of words.In this case, an AVL tree is used.However, this implementation works with all the search tree typesdescribed in this chapter(e.g., <tt>BinarySearchTree</tt>, <tt>AVLTree</tt>,<tt>MWayTree</tt>, and <tt>BTree</tt>).<P><P><A NAME="23035"> </A><A NAME="progalgorithmsl"> </A> <IMG WIDTH=575 HEIGHT=334 ALIGN=BOTTOM ALT="program23032" SRC="img1365.gif" ><BR><STRONG>Program:</STRONG> Application of search trees--word translation.<BR><P><P>The <tt>translate</tt> method reads pairs of stringsfrom the input stream (lines 5-8).The <tt>Association</tt> class defined in Section <A HREF="page127.html#secadtsassociations"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is used to contain the key/value pairs.A new instance is created for each key/value pairwhich is then inserted into the search tree (line 9).The process of building the search tree terminates when the end-of-file is encountered.<P>During the translation phase,the <tt>translate</tt> method reads words one at a time from the input streamand writes the translation of each word on the output stream.Each word is looked up as it is read (lines 10-12).If no key matches the given word,the word is printed followed by a question mark (lines 13-14).Otherwise, the value associated with the matching keyis printed (line 16).<P><HR><A NAME="tex2html5196" HREF="page349.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5194" HREF="page298.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5188" HREF="page347.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5198" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -