📄 page250.html
字号:
<HTML><HEAD><TITLE>Projects</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="tex2html4074" HREF="page251.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4072" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4068" HREF="page249.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4076" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION008900000000000000000">Projects</A></H1><P><OL><LI> Complete the implementation of the <tt>ChainedHashTable</tt> class declared in Program <A HREF="page225.html#progchainedHashTablea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>-Program <A HREF="page228.html#progchainedHashTablec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by providing suitable definitions for the following operations: <tt>accept</tt>, <tt>_compareTo</tt>, <tt>__contains__</tt>, and <tt>__iter__</tt>. Write a test program and test your implementation.<LI> Complete the implementation of the <tt>ChainedScatterTable</tt> class declared in Program <A HREF="page232.html#progchainedScatterTablea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by providing suitable definitions for the following operations: <tt>accept</tt>, <tt>_compareTo</tt>, <tt>__contains__</tt>, <tt>getIsFull</tt>, <tt>getIsEmpty</tt>, and <tt>__iter__</tt>. Write a test program and test your implementation.<LI> Complete the implementation of the <tt>OpenScatterTable</tt> class declared in Program <A HREF="page242.html#progopenScatterTablea"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> by providing suitable definitions for the following methods: <tt>accept</tt>, <tt>_compareTo</tt>, <tt>__contains__</tt>, <tt>getIsFull</tt>, <tt>getIsEmpty</tt>, and <tt>__iter__</tt>. Write a test program and test your implementation.<LI> The <tt>withdraw</tt> method defined in Program <A HREF="page227.html#progchainedHashTableb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> has been written under the assumption that linear probing is used. Therefore, it does not call explicitly the collision resolution method <tt>c</tt>. Rewrite the <tt>withdraw</tt> method so that it works correctly regardless of the collision resolution strategy used.<LI> Consider an application that has the following profile: First, <I>n</I> symbols (character strings) are read in. As each symbol is read, it is assigned an ordinal number from 1 to <I>n</I>. Then, a large number of operations are performed. In each operation we are given either a symbol or a number and we need to determine its mate. Design, implement and test a data structure that provides both mappings in <I>O</I>(1) time.<LI> Spelling checkers are often implemented using hashing. However, the space required to store all the words in a complete dictionary is usually prohibitive. An alternative solution is to use a very large array of bits. The array is initialized as follows: First, all the bits are set to zero. Then for each word <I>w</I> in the dictionary, we set bit <I>h</I>(<I>w</I>) to one, where <IMG WIDTH=24 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58645" SRC="img261.gif" > is a suitable hash function.<P> To check the spelling in a given document, we hash the words in the document one-by-one and examine the corresponding bit of the array. If the bit is a zero, the word does not appear in the dictionary and we conclude that it is misspelled. Note if the bit is a one, the word may still be misspelled, but we cannot tell.<P> Design and implement a spelling checker. <b>Hint</b>: Use the <tt>SetAsBitVector</tt> class given in Chapter <A HREF="page386.html#chapsets"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.</OL><P><HR><A NAME="tex2html4074" HREF="page251.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4072" HREF="page205.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4068" HREF="page249.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4076" 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 + -