1. INTRODUCTION TO HIGH LEVEL TYPES

2. ARRAYS AND THEIR DECLARATION

The most straight forward (and oldest) form of higher level data type is the array. An array is simply a series of data items, all of the same type, stored in a series of locations in memory such that a single value is held at each location.

Features of arrays

3. ASSIGNMENT OF VALUES TO ARRAY ELEMENTS

Given knowledge of the index for an array element we can assign a value to that element (or change its value) using an "assignment" operation. Ada and C example assignments:

LIST1(1):= 1;

list1[0] = 1;

Compound values

Some imperative languages support the concept of compound values which allow all the elements of an array to be assigned to simultaneously. Both C and Ada support compound values (in Ada they are called aggregates). Note that in C their usage is limited to initialisation, while in Ada array aggregates can be used in any assignment statement (not just initialisation).

Ada and C Examples statements:

MY_ARRAY : array (0..10) of integer
        := (9, 8, 7, 6, 5, 4, 3, 2, 1, 0);

int myArray[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

Ada also supports an alternative to the above:

MY_ARRAY:= (5, 4, 3, 2, 1, other => 0);

Ada array example programme

Declaring, initialising and outputting the contents of an array.

with CS_IO; use CS_IO;

procedure ARRAY_EXAMPLE is
        START : integer := 2;
        IA    : array (integer range START..START+4) of
                integer := (2,4,6,8,10);
begin
        put("Array comprises = ");
        put(IA(2)); put(", ");
        put(IA(3)); put(", ");
        put(IA(4)); put(", ");
        put(IA(5)); put(", ");
        put(IA(6)); new_line;
end ARRAY_EXAMPLE;

Note, in the above example, it would have been more succinct to use some kind of loop construct.

C array example programme

#include< stdio.h>

void main(void)
{
int ia[5] = {2,4,6,8,10};

printf("Size of array = %d (bytes)\n",sizeof(ia));
printf("Num elements = %d\n",sizeof(ia)/sizeof(ia[0]));
printf("Array comprises = %d, %d,%d, %d, %d\n",
        ia[0],ia[1],ia[2],ia[3],ia[4]);
printf("Address ia[0] = %d\n",&ia[0]);
printf("ia = %d\n",ia);
}

Note that if we output the name of the array (without an index) we produce the start address of the area in memory where the array is stored.

4. OPERATIONS ON COMPLETE ARRAYS

Some languages, such as PL/1 (but not Ada or C), allow operations on complete arrays. For example in PL/1 we can write:

IA = 0;

This will make all elements in the array IA equal to 0. The same effect can be achieved in Ada by writing:

IA:= (other => 0);

Alternatively, some imperative languages (Pascal) support assignment of one array to another:

ARRAY1 := ARRAY2 ;

Where ARRAY1 and ARRAY2 are two arrays of precisely the same type (such a capability supported by Ada and pascal, but not C).

Slices

A Slice is a sub-array of an array. The process of slicing returns a sub-array (supported by Ada but not C). Thus given:

IA: array (integer range START..START+4) of integer := (2,4,6,8,10);

or

IA: array (integer range START..START+4) of character := ('a', 'b', 'c', 'd', 'e');

The statements

IA_SUB := IA(START+1..START+3)

would assign the sub array (4,6,8) or ('b', 'c', 'd') to the variable IA_SUB.

"Slices" example:

with CS_IO; use CS_IO;

procedure EXAMPLE is
   START: constant := 2;
   type MY_ARRAY_T is array
      (integer range START..START+4)
      of integer;
   LIST1: MY_ARRAY_T := (2,4,6,8,10);
   LIST2, LIST3: MY_ARRAY_T;

   procedure OUTPUT_ARRAY (LIST: MY_ARRAY_T) is
   begin

   end OUTPUT_ARRAY;

begin
   OUTPUT_ARRAY(LIST1);
   LIST2 := LIST1;
   OUTPUT_ARRAY(LIST2);
   LIST3 := LIST1(2..4) & LIST2(2..3);
   OUTPUT_ARRAY(LIST3);
end EXAMPLE;

Conformant arrays parameters

5. ADA ARRAY ATTRIBUTES

Ada supports a number of attributes which can be used with respect to array:

• T'FIRST Gives first index for array type T.
• T'LAST Gives last index value for array type T.
• T'LENGTH Gives the number of components in array type T.

with CS_IO ; use CS_IO ;

procedure ARRAY_ATTRIBUTES is
        START  : integer:= 2;
        IA     : array (integer range START..START+4)
                 of character := ('a', 'b', 'b', 'd', 'e');
begin
        put("IA'first = ");
        put(IA'first);
        new_line;
        put("IA'last = ");
        put(IA'last);
        new_line;
        put("IA'length = ");
        put(IA'length);
        new_line;
end ARRAY_ATTRIBUTES ;

6. CONSTRAINED AND UNCONSTRAINED ARRAYS

A constrained array is an array where the index is specified (and hence the number of components is specified), we say that the bounds are static, hence constrained arrays are sometimes referred to as static arrays. Many imperative languages (including Ada) support the concept of unconstrained arrays. C and Pascal do not, however, C does provide facilities whereby such arrays can be simulated.

Ada makes use of the symbol <> to indicate an unconstrained array:

type TYPE_NAME is array (T1 range < >) of T2;

DATA_ITEM_NAME : TYPE_NAME(START..END);

where T1 and T2 are type identifiers (not necesseraily of the same type), and the data items START and END are of type T1.

Example declaration:

type LIST1 is array (INTEGER range < >) of FLOAT;
L1 : LIST1(START..END);

C dynamic arrays

Although C does not support the concept of unconstrained arrays it does provide facilities to delay the declaration of an upper bound of an array till run time, i.e. the upper bound is declared dynamically hence such an array is referred to as a dynamic array. To achieve this two library functions malloc and free are used. The maloc( < size > ) function obtains a block of memory (for the array in this case) according to the parameter < size > ). The type of this parameter is system dependent nut usually is an int or unsigned inr. The free function releases the memory when it is no longer required.

Example:

#include < stdlib.h>
#include < stdio.h>

void main(void)
{
int num, index = 0;
int *numPtr = NULL;

/* Get size of array and create space (Malloc returns NULL if no space
available). */

scanf("%d",&num);
numPtr = (int *) malloc(sizeof(int)*num);
if (numPtr == NULL) {
        printf("Not enough memory\n");
        exit(1);
        }

/* Initialise. */

while (index < = num) {
        numPtr[index] = index;
        index++;
        }

/* Output. */

index = 0;
while (index < = num) {
        printf("%d ",numPtr[index]);
        index++;
        }
printf("\n");

/* End. */

free(numPtr);
}

7. TYPES OF ARRAY

Other than the standard array forms described above we can identify a number of alternative "types" of array which are a feature of particular imperative languages. These include:

Flexible arrays

A powerful facility associated with some imperative languages is the ability to dynamically "resize" an array after it has been declared, i.e. during run-time. Such an array is referred to as a flexible array. Neither Ada or C support flexible arrays (Algol'68 does). However, a similar effect can be achieved in C using the built-in functions malloc and realloc. The latter dynamically extends or contracts the memory space available for a previously declared array.

C Example:

#include < stdlib.h>
#include < stdio.h>

int num = 4;

void main(void)
{
int *numPtr = NULL;

/* Allocate memory and initialise. */

numPtr = (int *) malloc(sizeof(int)*num);
numPtr[0] = 2; numPtr[1] = 4;
numPtr[2] = 6; numPtr[3] = 8;

/* Output. */

/* Reallocate memory and reinitialise. */

num = 3;
numPtr = (int *) realloc(numPtr,sizeof(int)*num);
numPtr[0] = 1; numPtr[1] = 3; numPtr[2] = 5;

/* Output. */

/* End */

free(numPtr);
}

Multi-dimensional arrays

Multi-dimensional arrays are arrays where the elements have more than one index. In the case of two-dimensional arrays these can be envisaged as tables comprising a number of rows and column such that the row number represents one index and the column number a second index:

Ada two-dimensional array example programme

with CS_IO ; use CS_IO ;

procedure TWO_DIM_ARRAY is
        type TWO_D_ARRAY_T is array (1..3, 1..2) of integer;
        IA: TWO_D_ARRAY_T:= ((1, 2), (3, 4), (5, 6));
begin
        put(IA(1,1));
        put(IA(1,2));new_line;
        put(IA(2,1));
        put(IA(2,2));new_line;
        put(IA(3,1));
        put(IA(3,2));new_line;
end TWO_DIM_ARRAY ;

Note that the "row" index is declared first and then the "column" index.

C two-dimensional array example programme

void main(void)
{
int twoDarray[3][2] = {{1, 2}, {3, 4}, {5, 6}};

printf("Size of array = %d (bytes)\n",sizeof(twoDarray));

printf("Num elements = %d\n",sizeof(twoDarray)/sizeof(twoDarray[0][0]));

printf("Array comprises = (%d, %d), (%d, %d), (%d, %d)\n",
        twoDarray[0][0],twoDarray[0][1],twoDarray[1][0],
        twoDarray[1][1],twoDarray[2][0],twoDarray[2][1]);
}

Three dimensional arrays can then be envisaged as comprising a book of tables such that the third index represents page number. Four dimensional arrays can then be envisaged as a set of books of tables and so on.

Some imperative languages (including Ada and C) support arrays of arrays:

with CS_IO ; use CS_IO ;

procedure ARRAY_OF_ARRAY is
        type ARRAY_T       is array (1..2) of integer;
        type TWO_D_ARRAY_T is array (1..3) of A;
        A1 : ARRAY_T       := (1, 2);
        A2 : ARRAY_T       := (3, 4);
        A3 : ARRAY_T       := (5, 6);
        IA : TWO_D_ARRAY_T := (A1, A2, A3);
begin
        put(IA(1)(1));
        put(IA(1)(2));new_line;
        put(IA(2)(1));
        put(IA(2)(2));new_line;
        put(IA(3)(1));
        put(IA(3)(2));new_line;
end ARRAY_OF_ARRAY ;

Note that in Ada the "sub-arrays" must all be of the same type (i.e. size and length), consequently the distinction between arrays of arrays and two-dimensional arrays can be blurred.

Lists

Lists (or sequences) can be considered to be special types of arrays but:

• with an unknown number of elements, and
• without the indexing capability.

Lists are popular in logic and functional languages but not in imperative languages.

SETS

A set is a group of (distinct) elements, all of the same type, which are all possible values of some other type referred to as the base type. The relationship is similar to that of an Ada sub-type to its "super-type". The distinction between an array and a set is that the elements are not ordered in anyway. Neither Ada or C feature sets, however Pascal and Modula-2 do. Pascal set declaration example:

program SET_EXAMPLE (output);
        type
                SOMEBASE_T = 0..10;
                SOMESET_T  = set of SOMEBASE_T;
        var
                SET1, SET2 : SOMESET_T;
begin
        SET1 := [1, 2, 5];
        SET2 := [6, 8, 9];

--- More code in here ---

end.

Here we have defined a base type SOMEBASE_T and defined a set SOMESET_T over this base. The number of elements in a set is referred to as its cardinality. The only operations that can be performed on sets are set operations, e.g. member, union, intersection etc.

BAGS

Bags (multisets) are similar to sets except that they can contain an element more than once and record how many times a value has been inserted. The primary operations on bags are "insert value" and "remove value" (as opposed to the set operations found in sets). Very few imperative languages feature bags

8. STRINGS

A further type of array is the string. A string is a sequence of characters usually enclosed in double (Ada, C) or single quotes (Pascal) - for this reason strings are sometimes referred to as a character arrays. As such we can use standard array operations on strings:

• We can access any character in a string using an index.
• Where supported (Ada) we can access slices of strings.

Note also that C strings are peculiar in that the last member of the sequence must always be the null terminator, written as '\0' (note single quotes).

String declarations

• In C a 15 character string is declared as follows:

  char name[15];
  

• Other languages provides a specific predefined data type for character arrays, e.g. string (Ada), or text (Pascal). Ada example:

  NAME: string(1 .. 15);
  

In both of the above examples note the similarity with array declarations.

Ada string example programme

with CS_IO ; use CS_IO ;

procedure ADA_STRING is
        NAME1: string(1..16);
        NAME2: string(1..16);
        LENGTH1, LENGTH2: integer;
begin
        get_line(NAME1,LENGTH1);
        get_line(NAME2,LENGTH2);
        put("String length NAME1 = ");
        put(LENGTH1);new_line;
        put("String length NAME2 = ");
        put(LENGTH2);new_line;
        put("Input = "); put(NAME1(1..LENGTH1));
        put(" and "); put(NAME2(1..LENGTH2));
        new_line;
        put("Initials = ");
        put(NAME1(1)); put(". and ");
        put(NAME2(1)); put(".");
        new_line;
end ADA_STRING ;

C string example programme

#include < stdio.h>

void main(void)
{
char name1[15], name2[15];

scanf("%s",name1);
scanf("%s",name2);

printf("Input = %s and %s\n",name1,name2);
printf("Initials = %c and %c\n",name1[0],name2[0]);
}

Operations on strings

Note that the C strcpy function does not require s1 and s2 to be of the same length (this is not the case when using the Ada := operator).