The Array as an ADT
- The Array as an ADT
(HSM Ch.2.2)
- An array object is a set of pairs, <index,value>, such that
each index is unique and each index that is defined has a value
associated with it (a mapping from indices to values).
- Operations include setting and retrieving a value for a given index.
- An array ADT
(HSM, Ch.2.2)
- Representation of Arrays
(HSM Ch.2.5)
- Space requirements
- Row and column major orders
- Row major changes column (in general, last index) fastest
- Column major changes row (in general, first index) fastest
- Address calculation
- Assume one address per element, scale later if necessary.
Assume base address
alpha.
- In 2D
- Array
A[NumberOfRows][NumberOfColumns]
- Offset for preceding rows is
Row * NumberOfColumns
- Offset in row is
Column
- Address is
alpha +
Row * NumberOfColumns +
Column
- In 3D
- Array
A[NumberOfSlices][NumberOfRows][NumberOfColumns]
- Offset for preceding slices is
Slice * NumberOfRows *
NumberOfColumns
- Offset for preceding rows is
Row * NumberOfColumns
- Offset in row is
Column
- Address is
alpha +
Slice * NumberOfRows *
NumberOfColumns +
Row * NumberOfColumns +
Column
- In ND
- Array
A[u1][u2]...[uN]
- Offset for dimensions preceding K is
iK * uK+1 * uK+2 * ... * uN
- Offset is (see HSM p.102)
Exercises
Lab Tasks
Exam Style Questions
- Define the array ADT.
- Explain what is meant by {row major order,column major order}.
- Give a generic formula for the space complexity of an N dimensional
array.
- What is the time complexity of accessing an element of an N dimensional
array?
- Given the following array declaration, what is the memory address of
[some element] if the base address is X and each element of the array
takes E memory locations?
- Give a generic formula for finding the memory location of an array
element, given the base address and array element size.