page107.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 67 行

HTML
67 行
字号 
<HTML><HEAD><TITLE>extract Method</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="tex2html2445" HREF="page108.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2443" HREF="page97.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2437" HREF="page106.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html2447" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0043100000000000000000"><tt>extract</tt> Method</A></H2><P>In this section we consider the <tt>extract</tt>method of the <tt>LinkedList</tt> class.The purpose of this method is to delete the specified elementfrom the linked list.<P><P><A NAME="4163">&#160;</A><A NAME="proglinkedListi">&#160;</A> <IMG WIDTH=575 HEIGHT=352 ALIGN=BOTTOM ALT="program3989" SRC="img636.gif"  ><BR><STRONG>Program:</STRONG> <tt>LinkedList</tt> class <tt>extract</tt> method.<BR><P><P>The <tt>extract</tt> method searches sequentially for the item to be deleted.In the absence of any <em>a priori</em> knowledge,we do not know in which list element the item to be deleted will be found.In fact, the specified item may not even appear in the list!<P>If we assume that the item to be deleted <em>is</em> in the list,and if we assume that there is an equal probability of finding it ineach of the possible positions,then on average we will need to search half way through the listbefore the item to be deleted is found.In the worst case, the item will be found at the tail--assumingit is in the list.<P>If the item to be deleted does not appear in the list,the algorithm shown in Program&nbsp;<A HREF="page107.html#proglinkedListi"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> raisesa <tt>KeyError</tt><A NAME=4003>&#160;</A>exception<A NAME=4004>&#160;</A>.A simpler alternative might be to do nothing--after all, if the item to be deleted is not in the list,then we are already done!However, attempting to delete an item which is not there,is more likely to indicate a logic error in the programming.It is for this reason that an exception is raised.<P>In order to determine the running time of the <tt>extract</tt> method,we first need to determine the time to find the element to be deleted.If the item to be deleted <em>is not</em> in the list,then the running time of Program&nbsp;<A HREF="page107.html#proglinkedListi"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>up to the point where it raises the exception (line&nbsp;10)is <I>T</I>(<I>n</I>)=<I>O</I>(<I>n</I>).<P>Now consider what happensif the item to be deleted <em>is</em> found in the list.In the worst-case the item to be deleted is at the tail.Thus, the running time to find the element is <I>O</I>(<I>n</I>).Actually deleting the element from the list once it has been foundis a short sequence of relatively straight-forward manipulations.These manipulations can be done in constant time.Therefore, the total running time is <I>T</I>(<I>n</I>)=<I>O</I>(<I>n</I>).<P><HR><A NAME="tex2html2445" HREF="page108.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html2443" HREF="page97.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html2437" HREF="page106.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html2447" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page107.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page107.html 源码文件，采用 HTML 编程语言编写，共 67 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?