📄 page179.html
字号:
<HTML>
<HEAD>
<TITLE>Inserting and Accessing Items in a List</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html4129" HREF="page180.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page180.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4127" HREF="page177.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page177.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4121" HREF="page178.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page178.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4131" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4132" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION008122000000000000000">Inserting and Accessing Items in a List</A></H3>
<P>
Program <A HREF="page179.html#proglist7c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page179.html#proglist7c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> gives the implementation of the <tt>Insert</tt>
member function of the <tt>ListAsLinkedList</tt> class.
This function takes a reference to an <tt>Object</tt>
which is to be added to the ordered list.
As in the case of the <tt>ArrayAsLinkedList</tt> class,
the object is added at the end of the ordered list.
This is done simply by calling the <tt>Append</tt>
function from the <tt>LinkedList<T></tt> class.
<P>
<P><A NAME="10545"> </A><A NAME="proglist7c"> </A> <IMG WIDTH=575 HEIGHT=525 ALIGN=BOTTOM ALT="program10140" SRC="img802.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img802.gif" ><BR>
<STRONG>Program:</STRONG> <tt>ListAsLinkedList</tt> Class Constructor, <tt>Insert</tt> Member Function and Subscripting Operator Definitions<BR>
<P>
<P>
The running time of the <tt>Insert</tt> function is determined
by that of <tt>Append</tt>.
In Chapter <A HREF="page79.html#chapfds" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page79.html#chapfds"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> this was shown to be <I>O</I>(1).
The only other work done by the <tt>Insert</tt> function is to
add one to the <tt>count</tt> variable.
Consequently, the total running time for <tt>Insert</tt> is <I>O</I>(1).
<P>
Program <A HREF="page179.html#proglist7c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page179.html#proglist7c"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> also defines a subscripting operator,
<tt>operator[]</tt>,
which takes an argument of type <tt>unsigned int</tt>.
This operator is used to access elements of the ordered list
by their position in the list.
In this case, the position is specified by a non-negative,
integer-valued subscript expression.
Since there is no way to access directly the <IMG WIDTH=20 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61700" SRC="img803.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img803.gif" > element of linked list,
the implementation of this function comprises a loop
which traverses the list to find the <IMG WIDTH=20 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61700" SRC="img803.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img803.gif" > item.
The function returns a reference to the <IMG WIDTH=20 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline61700" SRC="img803.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img803.gif" > item,
provided <IMG WIDTH=70 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline61706" SRC="img804.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img804.gif" >.
Otherwise, <I>k</I> is not a valid subscript value
and the function throws an exception.
<P>
The running time of this <tt>operator[]</tt> depends
on the number of items in the list
and on the value of the subscript expression.
In the worst case,
the item sought is at the end of the ordered list.
Therefore, the worst-case running time of this algorithm,
assuming the subscript expression is valid,
is <I>O</I>(<I>n</I>), where <IMG WIDTH=72 HEIGHT=9 ALIGN=BOTTOM ALT="tex2html_wrap_inline61308" SRC="img709.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img709.gif" >.
<P>
<HR><A NAME="tex2html4129" HREF="page180.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page180.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html4127" HREF="page177.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page177.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html4121" HREF="page178.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page178.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html4131" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html4132" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -