Chapter 4

Foundational Data Structures

In the remaining lectures of this course, we will study several abstract data types: stacks, queues, deques, ordered lists, sorted lists, hash tables, etc. These can all be implemented using arrays or using linked lists.

Dynamic Arrays

1. Why make an array class?

  • Although C++ provides built-in arrays, they are not true data types.
  • Arrays can not be values in expressions.
  • Arrays can not be the actual value parameter of a function.
  • Arrays can not be the return value of function.
  • You can not assign one array to another.
  • Array subscripts range from 0 to n-1, where n is the number of elements in the array.
  • There is no bounds checking of array subscript expressions.
  • The size of the array is static and fixed at compile time.

So we can define a generic Array object which overcomes these limitations.

We use two structures. The first has:

data – pointer to the array data

base – starting array index

length – number of array cells.

The second structure is a dynamically allocated contiguous set of memory locations which hold the array data.

[See the implementations of the Dynamic Array from the power point version of “Chapter 4”.]

Example to use and test the Array:

#include <iostream.h>

#include “array.h”

main()

{

Array <int> a(3);

a[0] = 0;

a[1] = 1;

a[2] = 1;

cout < a.Base( ) < endl;

a.setBase(10);

cout < a[10] < endl;

a.setLength(4);

a[13] = 2;

for (int i=10; i <=13; i++)

{

cout < a[i];

}

cout < endl;

}

This example shows how to resizing an Array and change the base.

Multidimensional Arrays

  • n-dimensional array (or simply nD array) is a collection of items accessed via n subscript expressions.
  • For example, the (i, j)th element of the 2D array X is accessed by writing X[i][j].
  • C++ has built-in support for multidimensional arrays. But nD arrays in C++ have the same problems as 1D arrays, namely

- not true data types

- no array valued expressions

- no arrays as function parameters

- no arrays as return values of functions

- no assignment operator

- subscripts start at 0

- no bounds checking

- size of array is fixed at compile time

So just same as with 1D arrays, it is useful to implement a class for nD arrays.

Array Subscript Calculations:

  • Memory of a computer is essentially a one dimensional array, the memory address is the array subscript.
  • So it is natural to implement multidimensional arrays by storing the element in a 1D array.
  • To do this, we need to be able to determine the 1D subscript which corresponds to the nD subscripts.

For example,T a[2][3];

T b[20];

Which b[k] = a[i][j] ?

K = f(i, j) is the mapping function

  • The mapping function determines how elements are stored in memory.
  • The most common way is row-major order. (see Figure 4.5)
  • The elements are stored starting at address a
  • The first element of the first row is at address: a+0*Size of (T) = a (NB: array name is a constant pointer)
  • So a [i][j] is at address : a + i * number of columns + j
  • For an nD array T a[s1][s2]…[sn]

The address of a[i1][i2]…[in] is:

a + Size of (T) *

where = /1if j=n

\if 1<= j < n

For example, for T a[2][3][4] the address of a[1][2][3] is:

a+ Size of (T) *

= = 3*4 = 12

== 4

= 1

so the address is: a + Size of (T) * (12+4*2+3)

= a + Size of (T) * (23)

NB: in C++, whenever an integer is added to a pointer, the result is always scaled by the size of the object pointed to. Hence a[1][2][3] = *(a+23) = a[23]

Two-dimensional Array Implementations: see the text book for the coding part.