Arrays, Pointers, and Structures

September 25, 2015

Prelab (complete before lab)

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 specify 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 uninitialized 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 criticized 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:

int *p = a;

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 arbitrary 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 convenient 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;

Part 1: C Arrays

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], (int) (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 the third and fourth arguments of the printf() make use of another feature of C called typecasting. The syntax of prefixing an expression with a parentheses enclosed data type has the effect of converting 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. Paste the results after running the program below

Checkoff #2. Insert the following line of code before the for loop in main:

selectionSort(a, 5);

Recompile and execute the code, and paste the result below:

Checkoff #3. Modify the functions min() and selectionSort() and replace the call to selectionSort() from Checkoff #2 as follows:

selectionSort(p, 5);

In your modified version, the pointers in array p should be reordered such that the first points to the smallest entry in a, and the second points to the next smallest, and so on, but no entries in array a should be moved. Enter and test your modified versions of selectionSort() and min(). Feel free to change any function prototypes if needed.

Part 2: C Structures

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 #4. Compile and execute the given code fragment, and paste the results below:

Checkoff #5. 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 enter the code for the function you added.

Arrays, Pointers, and Structures

September 25, 2015

Prelab (complete before lab)

Part 1: C Arrays

Part 2: C Structures

Press Submit to turn in Lab 5.