page101.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 89 行
HTML
89 行
<HTML>
<HEAD>
<TITLE>Array Subscript Calculations</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="tex2html3156" HREF="page102.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page102.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="tex2html3154" HREF="page100.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page100.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="tex2html3148" HREF="page100.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page100.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="tex2html3158" 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="tex2html3159" 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>
<H2><A NAME="SECTION005310000000000000000">Array Subscript Calculations</A></H2>
<P>
The memory of a computer is essentially a one-dimensional array--the memory address is the array subscript.
Therefore, the most natural way to implement a multi-dimensional
array is to store its elements in a one-dimensional array.
In order to do this,
we need a mapping from the <I>n</I> subscript expressions
used to access an element of the multi-dimensional array
to the one subscript expression used to access the one-dimensional array.
E.g., suppose we have a two-dimensional array
of elements of type <tt>T</tt>, <tt>T a[2][3]</tt>,
the elements of which are to be stored in a one-dimensional array,
<tt>T b[20]</tt>.
Then we need to determine which element of <tt>b</tt>, say <tt>b[k]</tt>,
will be accessed given a reference of the form <tt>a[i][j]</tt>.
I.e., we need the mapping <I>f</I> such that <IMG WIDTH=74 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61103" SRC="img640.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img640.gif" >.
<P>
The mapping function determines the way in which the elements
of the array are stored in memory.
The most common way to represent an array is in
<em>row-major order</em><A NAME=3769> </A>,
also known as <em>lexicographic order</em><A NAME=3771> </A>.
E.g., consider the 2D array <tt>T a[2][3]</tt>.
The row-major layout of this array is shown in Figure <A HREF="page101.html#figrowmajor" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page101.html#figrowmajor"><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>.
<P>
<P><A NAME="4023"> </A><A NAME="figrowmajor"> </A> <IMG WIDTH=575 HEIGHT=212 ALIGN=BOTTOM ALT="figure3774" SRC="img641.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img641.gif" ><BR>
<STRONG>Figure:</STRONG> Row-Major Order Layout of a 2D Array<BR>
<P>
<P>
In row-major layout, it is the right-most subscript expression
(the column index) that increases the fastest.
As a result, the elements of the rows of the matrix
end up stored in contiguous memory locations.
In Figure <A HREF="page101.html#figrowmajor" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page101.html#figrowmajor"><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>,
the array is stored starting from address <I>a</I>.
The first element of the first row is a address <IMG WIDTH=155 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61119" SRC="img642.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img642.gif" >.
The first element of the second row is at address <IMG WIDTH=125 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline61121" SRC="img643.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img643.gif" >,
since there are 3 elements in each row.
<P>
We can now generalize this to an arbitrary <I>n</I>-dimensional array.
Suppose we have an <I>n</I>-D array declared as
<tt>T a[ <IMG WIDTH=12 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline61127" SRC="img644.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img644.gif" >][ <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline61129" SRC="img645.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img645.gif" >][ <IMG WIDTH=17 HEIGHT=2 ALIGN=BOTTOM ALT="tex2html_wrap_inline61131" SRC="img646.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img646.gif" >][ <IMG WIDTH=13 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline61133" SRC="img647.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img647.gif" >]</tt>.
Furthermore, let <I>a</I> be the starting address of the array.
Then, the address of the element
<tt>a[ <IMG WIDTH=11 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline61137" SRC="img648.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img648.gif" >][ <IMG WIDTH=12 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline61139" SRC="img649.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img649.gif" >][ <IMG WIDTH=17 HEIGHT=2 ALIGN=BOTTOM ALT="tex2html_wrap_inline61131" SRC="img646.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img646.gif" >][ <IMG WIDTH=11 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline61143" SRC="img650.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img650.gif" >]</tt> is given by
<P><A NAME="eqnfdsaddress"> </A> <IMG WIDTH=500 HEIGHT=46 ALIGN=BOTTOM ALT="equation4031" SRC="img651.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img651.gif" ><P>
where
<P> <IMG WIDTH=353 HEIGHT=48 ALIGN=BOTTOM ALT="displaymath61097" SRC="img652.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img652.gif" ><P>
<P>
The running time required to calculate the address appears to be <IMG WIDTH=40 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline59179" SRC="img261.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img261.gif" >
since the address is the sum of <I>n</I> terms and for each term
we need to compute <IMG WIDTH=12 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61149" SRC="img653.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img653.gif" >, which requires <I>O</I>(<I>n</I>) multiplications
in the worst case.
However, the address calculation can in fact be done in <I>O</I>(<I>n</I>) time
using the following algorithm:
<P>
<PRE>unsigned int product = 1;
T* address = <IMG WIDTH=8 HEIGHT=7 ALIGN=BOTTOM ALT="tex2html_wrap61091" SRC="img654.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img654.gif" >;
for (int j = n; j >= 1; -j)
<P>
address += product * <IMG WIDTH=10 HEIGHT=17 ALIGN=BOTTOM ALT="tex2html_wrap61092" SRC="img655.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img655.gif" >;
product *= <IMG WIDTH=10 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap61093" SRC="img656.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img656.gif" >;
<P>
</PRE>
<P>
This algorithm makes subtle use of the way that
address arithmetic<A NAME=4044> </A> is done in C++.
Since the variable <tt>address</tt> is of type <tt>T*</tt>,
it is not necessary to scale the computation by <tt>sizeof(T)</tt>.
In C++ whenever an integer value is added to a pointer variable,
it is automatically scaled by the compiler before the addition.
<P>
<HR><A NAME="tex2html3156" HREF="page102.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page102.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="tex2html3154" HREF="page100.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page100.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="tex2html3148" HREF="page100.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page100.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="tex2html3158" 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="tex2html3159" 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 + =
减小字号Ctrl + -
显示快捷键?