Arrays, Pointers, and Structures

Arrays are multielement variables with a uniform type, which are stored in sequential memory locations. An array variable refers to the address of the first array element called its 'base address'. Other elements are accessed by indexing from from the first element using the bracket operators '[expression]'. Since all array elements are of the same type, and are therefore the same size, array offsets can be calculated as follows:

element_address = base_address + sizeof(array_type) * index

There is no range checking of an array index in C. Thus, there is no need to know the size of an array when computing offsets.

Multidimensional arrays are specified by fixing the outer-most 'stride' sizes. For example one can specifiy a 4 by 3 array with 12 elements as follows:

int a[][3] = {
    {  1,  2,  3 },
    {  4,  5,  6 },
    {  7,  8,  9 },
    { 10, 11, 12}};

In terms of style, it might be preferable to declare int a[4][3] = { ..., and C accepts such declarations. However, the innermost stride of 4 is unnecessary if the array is initialized when declared as shown above. All strides of unitinialized arrays must be specified, and the array will be zero-filled.

The elements of multidimensional arrays are referenced using multiple indices. Just like a one-dimensional array, the array variable refers to the base address of the first array element. Array offsets into a two-dimensional array of the form a[j][i] are calculated as follows:

element_address = base_address + sizeof(array_type) * (j * i_stride + i)

While array offsets into a three-dimensional array of the form a[k][j][i] are calculated as follows:

element_address = base_address + sizeof(array_type) * ((k * j_stride + j) * i_stride + i)

Notice that in multidimensional arrays all 'outer strides' must be known in order to compute the array element's address, but the inner-most stride is never used to compute an element's address.

Pointer variables are a powerful and much maligned feature of the C programming language. The use of pointers is often critized since it is impossible to identify to what a pointer references without tracing code back to where it was last assigned. Moreover, pointers can reference invalid or deallocated variables.

Rather than restricting or obfuscating pointer variables as other languages do, C often makes them the method of choice. In particular, pointers are commonly used to process multielement data types; in particular, arrays and structures.

Pointer variables are declared with a "*" (star) prefix, and they contain addresses. As previously mentioned, array variables are also addresses. Thus, it is possible to assign the base address of an array to a pointer variable. For example:

References to memory using p can be made either with or without offset. Note that the variable p does not inherit with any strides associated with a's declaration. C also provides the "&" operator that gives the address of an aribtrary variable.

int *p = &a[1][1];
a[0][0] = *p;
a[0][1] = *(p+3);

When the star operator is used as a prefix in an expression, as in the second statement above, it refers to the contents of the memory address of the pointer variable to its right.This can be combined with offsets as shown in the third statement.

Structs are another multielement variable type provided in C. The elements of a C struct are named and need not all be of the same type. Stucts are a convenent way of aggregating groups of variables. Structs are defined as follows:

struct {
    char *name;
    int value;
} thing1, thing2;

Similar to arrays the variable "thing" is the address of the structure, and elements of the structure are referenced using the "." operator as follows:

thing1.name = "Lee Hart";
thing1.value = 42;
thing2.name = "Bud LeVile";
thing2.value = 666;

One can also define struct pointers and arrays of structs. For example

struct coord2 {
    float x;
    float y;
} point[10];

struct coord2 *pt;

Whose elements can be set as follows:

point[7].x = 20.0;
point[7].y = 30.0;
pt = point;
(*(pt+3)).x = 10.0;
(*(pt+3)).y = 40.0;

As you can see, accessing the elements of a structure using a struct pointer is syntactically cumbersome. To deal with this C provides another operator "->" that has higher precedence than the "*". This allows struct pointers to access struct elements using the following syntax:

(pt+3)->x = 10.0;
(pt+3)->y = 40.0;

Consider the following program:

#include <stdio.h>

int a[] = {30, 40, 50, 10, 20};
int *p[] = {a+4, a+3, a+2, a+1, a};

int min(int array[], int size) {
    int i;
    int minIndex = 0;
    int minValue = array[0];
    for (i = 1; i < size; i++)
        if (array[i] < minValue) {
            minValue = array[i];
            minIndex = i;
        }
    return minIndex;
}

void selectionSort(int array[], int N) {
    int i, j, t;
    int *p = array;
    for (i = 0; i < N-1; i++) {
        j = min(p,N-i);
        t = array[i];
        array[i] = array[i+j];
        array[i+j] = t;
        p++;
    }
}

int main( ) {
    int i;
    
    for (i = 0; i < 5; i++)
        printf("%d: %d, %d, %d, %d\n", i, a[i], p[i] - a, (int) p[i] - (int) a, *p[i]);
}

In C one can create arrays of any type. In this example, p is an array of pointers. In other words, every element in p is a address. When the star operator is used as a prefix in an expression, as in the last argument of the printf() statement, it refers to the contents of the memory address of the pointer variable to its right. Thus, the statement *p[i], refers to the contents of the address of the i^th element of the array p.

Notice that fourth argument of the printf() makes use of another feature of C called typecasting. The syntax of prefixing a variable with a parentheses enclosed data type has the effect of coverting it from it's original type to the one specified. For example, int pi = (int) 3.1415; converts the specified floating point constant to an integer, which is then loaded into the variable pi.

Enter, compile, and execute the given program.

Checkoff #1. Modify the functions min() and selectionSort() so that when called as follows:

The pointers in array p will be reordered such that the first points to the smallest entry in a, and the second points to the next smallest, and so on. For testing purposes you might want to make a second copy of the given for-loop placed after youc call to selectionSort(). Write down your modified versions of selectionSort() and min().  Feel free to change function prototypes if needed.

The following program illustrates how C structs can be used for creating lists.

#include <stdio.h> 

struct item {
    char *name;
    int value;
    struct item *next;
};

int main( ) {
    struct item list[] = {
        {"Lee Hart", 42, list+2},
        {"Bud Levile", 666, (struct item *) 0},
        {"Loch Narration", 32, list+3},
        {"Ali Acorn", 64, list+1}
    };
    struct item extra = {"Mute Conic Creeps", 128, (struct item *) 0};
    struct item *current;
    struct item *first = list;
    
    for (current = first; current != 0; current = current->next)
        printf("%s: %d\n", current->name, current->value);
}

The initial list is defined using an array of "item" structs. The for loop illustrates how the lists are traversed in C.

Checkoff #2. Add a function append(struct item *oldList, struct item *newItem), which appends the item "newItem" to the end of "oldList". Then call it with append(first, &extra). Verify that your code works, and then write down the code for the function you added.