High Level Language Programming

Data Structures

Compound collections of data items may be arranged to simulate a number of different organizations. The ARRAY is the most common, having the structure of a table or matrix. Others include:

Records Collections of data where the components can be referenced by name
Lists Data arranged in a manner so that access to any item is restricted to the nearest item only. Usually accessed sequentially, working from the head to the end of the tail - an "ordered list".
Trees Data organized in a graph-like organization: A directed acyclic graph; i.e. a graph wherein there is only one route between any pair of nodes, and there is a notion of "toward top of the tree" (i.e. the root node), and its opposite direction, toward the leaves.
Aggregates A data type composed of multiple elements. An aggregate can be homogeneous (all elements have the same type) e.g. an array, a list in a functional language, a string of characters, a file; or it can be heterogeneous (elements can have different types) e.g. a structure. In most languages aggregates can contain elements which are themselves aggregates. e.g. a list of lists.
Associative array An array where the indices are not just integers but may be arbitrary strings.



A collection of identically typed data items distinguished by their indices (or "subscripts"). The number of dimensions an array can have depends on the language but is usually unlimited.

A reference to an array element is written something like A[i,j,k] where A is the array name and i, j and k are the indices.

Elements of an array are usually stored contiguously. Languages differ as to whether the leftmost or rightmost index varies most rapidly, i.e. whether each row is stored contiguously or each column (for a 2D array). Arrays are appropriate for storing data which must be accessed in an unpredictable order, in contrast to lists which are best when accessed sequentially.


First we need a new kind of data type, arrays:

// program Pattern.C

{ functions will go here }

void main()
    char T[10000], P[10000];
    int n, m, position;

    cin >> n; cin >> m;
    read_string(T, n); read_string(P, m);
    position = 0;
    do   {
        if(occurs(P, m, T, position))
            cout << "Pattern found at position "
                 << position << "." << endl;
        position = position + 1;
       }  while (position < n - m);
} // end main

read_string and occurs are functions yet to be defined or described.



CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000