📄 page170.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="tex2html4015" HREF="page171.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page171.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="tex2html4013" HREF="page168.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page168.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="tex2html4007" HREF="page169.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page169.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="tex2html4017" 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="tex2html4018" 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="SECTION008112000000000000000">Inserting and Accessing Items in a List</A></H3>
<P>
Program <A HREF="page170.html#proglist1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page170.html#proglist1c"><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 definitions of the
constructor and <tt>Insert</tt> member functions
of the <tt>ListAsArray</tt> class.
The constructor takes a single argument which specifies
the length of array to use in the representation of the ordered list.
Thus if we use an array-based implementation,
we need to know when a list is declared
what will be the maximum number of items in that list.
The constructor initializes the <tt>array</tt> variable as
an array with the specified length.
The running time of the constructor is clearly <I>O</I>(1).
<P>
<P><A NAME="9602"> </A><A NAME="proglist1c"> </A> <IMG WIDTH=575 HEIGHT=353 ALIGN=BOTTOM ALT="program9419" SRC="img787.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img787.gif" ><BR>
<STRONG>Program:</STRONG> <tt>ListAsArray</tt> Class Constructor, <tt>Insert</tt> Member Function and Subscripting Operator Definitions<BR>
<P>
<P>
The <tt>Insert</tt> member function is part of the interface of
all searchable containers.
I.e., it is a pure virtual function declared
in the <tt>SearchableContainer</tt> class.
Its purpose is to put an object into the container.
The obvious question which arises is,
where should the inserted item be placed in the ordered list?
The simple answer is, at the end.
<P>
In Program <A HREF="page170.html#proglist1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page170.html#proglist1c"><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> we see that the <tt>Insert</tt>
function simply adds the new item to the end of the list,
provided there is still room in the array.
Normally, the array will not be full,
so the running time of this function is <I>O</I>(1).
<P>
Program <A HREF="page170.html#proglist1c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page170.html#proglist1c"><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 gives the definition
of the subscripting operator, <tt>operator[]</tt>,
which take a subscript of type <tt>unsigned int</tt>.
This function simply returns a reference to the object
in the ordered list at the specified position.
In this case, because the type <tt>unsigned int</tt> is used,
the position is specified using a non-negative,
integer-valued subscript expression.
The implementation of this function is trivial--it simply makes use of the subscript operator provided
by the <tt>Array<T></tt> class.
Assuming the specified position is valid,
the running time of this function is <I>O</I>(1).
<P>
<HR><A NAME="tex2html4015" HREF="page171.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page171.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="tex2html4013" HREF="page168.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page168.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="tex2html4007" HREF="page169.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page169.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="tex2html4017" 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="tex2html4018" 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 + -