Array Navigation

Arrays can be navigated in sequence or by random index addressing. Sequential navigation is achieved though repetitive control structures such as "for" or "while".

Example of Sequential Addressing:

for ( int i=0; i<5; i++ )
{
  cout << iarray[i] << endl;
}

Example of Traversing a Double Dimension Array:

      COL
      1 2 3 4
Row A x x x x
Row B x x x x
Row C x x x x

const int ROW = 3;
const int COL = 4;
int darray[ROW][COL] = {'x'};

for ( i=0; i<ROW; i++ )
{
  for ( j=0; j<COL; j++ )
  {
    cout << darray[i][j] << endl;
  }
}

Example of Random Addressing:

int index = rand() % 5;
cout << iarray[ index ];

Declaring and Initializing Arrays

Arrays can be declared with any data type. Arrays should always be initialized to ensure a known state of the object within the array. Arrays declared to contain class based object are initialized through the eyes of the class’s constructor. Arrays of native data types can be initialized using the assignment (=) operator . Arrays of structures can be initialized using the memset function. The size of an array must be declared as a constant.

Example of Declaring and Initializing Arrays

Native Data Types:

const int SIZE = 100;

int iarray[SIZE] = {0};

char carray[SIZE] = {‘A’};

float farray[SIZE] = {9.9};

double darray[5] = { 2.2, 3.3, 4.4, 5.5, 6.6 };

long larray[] = { 2, 3, 4, 5, 6 };

char string[] = { "Hello World" };

static char pstring[] = { "static improves"
                          " performance" };

Double Dimension Array: darray.cpp

int idarray[SIZE][SIZE] = { {0}, {1} };
memset ( idarray, 0, SIZE*SIZE );

Triple Dimension Array:

float fdarray[SIZE][SIZE][SIZE] = { (0.0}, {1.1},
                                    {4.4} };

Class Data Types:

class Vertex;

Vertex varray[SIZE]; // Fires SIZE constructors

Structure Data Types:

typedef struct
{
  float x,y,z;
} VertexType;

VertexType varray[SIZE];

memset ( varray, 0, sizeof(VertexType)*SIZE );

Passing Arrays to Functions

Arrays are passed to functions by using the name of the array, not the brackets. The name of the array is the pointer to the begining of the memory segment. As such an array can be specified by int[] or int *. Passing an array to a function is always performed by a pass by reference or the four bytes for the pointer to the beginning of the array memory segment.

Sorting and Searching Arrays

The section covers sorting and searching arrays.  The two basic methods for searching are linear and binary.  Linear searching starts at the head of the array and searches the whole array inorder until the desired data is found.    At worst case the performance of the search is of order "n", O(n), where n is the number of elements in the array.  Binary searching is of Order Log₂(n) and is much faster than linear searching but one must know the size of the space to search.  The search algorithm divides the search space in two and search one half.   If the desired value is not found then the remaining search space is divided into two and the process is repeated until the desired item is found.

This chapter gives and example of Bubble Sort.  This sorting alogrithm is at worst case when the array is reverse order O(n²) and at best case when the array is already in order O(n Log(n)).

04/12/00 03:51 PM