CS201: Elementary Data Structures

Pointers

In declarations the asterisk modifier (*) specifies a pointer type. For example, where the specifier int would refer to the integer type, the specifier int* refers to the type "pointer to integer". Pointer values associate two pieces of information: a memory address and a data type. The following line of code declares a pointer-to-integer variable called ptr:

int *ptr;

Referencing

When a non-static pointer is declared, it has an unspecified value associated with it. The address associated with such a pointer must be changed by assignment prior to using it. In the following example, ptr is set so that it points to the data associated with the variable a:

int *ptr;
int a;

ptr = &a;

In order to accomplish this, the "address-of" operator (unary &) is used. It produces the memory location of the data object that follows.

Dereferencing

The pointed-to data can be accessed through a pointer value. In the following example, the integer variable b is set to the value of integer variable a, which is 10:

int *p;
int a, b;

a = 10;
p = &a;
b = *p;

In order to accomplish that task, the unary dereference operator, denoted by an asterisk (*), is used. It returns the data to which its operand (which must be of pointer type) points. Thus, the expression *p denotes the same value as a. Dereferencing a null pointer is illegal.

Arrays

Array definition

Arrays are used in C to represent structures of consecutive elements of the same type. The definition of a (fixed-size) array has the following syntax:

int array[100];

which defines an array named array to hold 100 values of the primitive type int. If declared within a function, the array dimension may also be a non-constant expression, in which case memory for the specified number of elements will be allocated. In most contexts in later use, a mention of the variable array is converted to a pointer to the first item in the array. The sizeof operator is an exception: sizeof array yields the size of the entire array (that is, 100 times the size of an int, and 

sizeof(array) / sizeof(int)

 will return 100). Another exception is the & (address-of) operator, which yields a pointer to the entire array, for example

int (*ptr_to_array)[100] = &array;

Accessing elements

The primary facility for accessing the values of the elements of an array is the array subscript operator. To access the i-indexed element of array, the syntax would be array[i], which refers to the value stored in that array element.

Array subscript numbering begins at 0 (see Zero-based indexing). The largest allowed array subscript is therefore equal to the number of elements in the array minus 1. To illustrate this, consider an array a declared as having 10 elements; the first element would be a[0] and the last element would be a[9].

C provides no facility for automatic bounds checking for array usage. Though logically the last subscript in an array of 10 elements would be 9, subscripts 10, 11, and so forth could accidentally be specified, with undefined results.

Due to arrays and pointers being interchangeable, the addresses of each of the array elements can be expressed in equivalent pointer arithmetic. The following table illustrates both methods for the existing array:

Since the expression a[i] is semantically equivalent to *(a+i), which in turn is equivalent to *(i+a), the expression can also be written as i[a], although this form is rarely used.

Variable-length arrays

C99 standardised variable-length arrays (VLAs) within block scope. Such array variables are allocated based on the value of an integer value at runtime upon entry to a block, and are deallocated at the end of the block. As of C11 this feature is no longer required to be implemented by the compiler.

int n = ...;
int a[n];
a[3] = 10;

This syntax produces an array whose size is fixed until the end of the block.

Dynamic arrays

Arrays that can be resized dynamically can be produced with the help of the C standard library. The malloc function provides a simple method for allocating memory. It takes one parameter: the amount of memory to allocate in bytes. Upon successful allocation, malloc returns a generic (void) pointer value, pointing to the beginning of the allocated space. The pointer value returned is converted to an appropriate type implicitly by assignment. If the allocation could not be completed, malloc returns a null pointer. The following segment is therefore similar in function to the above desired declaration:

#include <stdlib.h> /* declares malloc */
...
int *a;
a = malloc(n * sizeof(int));
a[3] = 10;

The result is a "pointer to int" variable (a) that points to the first of n contiguous int objects; due to array–pointer equivalence this can be used in place of an actual array name, as shown in the last line. The advantage in using this dynamic allocation is that the amount of memory that is allocated to it can be limited to what is actually needed at run time, and this can be changed as needed (using the standard library function realloc).

When the dynamically-allocated memory is no longer needed, it should be released back to the run-time system. This is done with a call to the free function. It takes a single parameter: a pointer to previously allocated memory. This is the value that was returned by a previous call to malloc.

As a security measure, some programmers then set the pointer variable to NULL:

free(a);
a = NULL;

This ensures that further attempts to dereference the pointer will crash the program. If this is not done, the variable becomes a dangling pointer which can lead to a use-after-free bug. However, if the pointer is a local variable, setting it to  NULL does not prevent the program from using other copies of the pointer. Local use-after-free bugs are usually easy for static analyzers to recognize. Therefore, this approach is less useful for local pointers and it is more often used with pointers stored in long-living structs.

Multidimensional arrays

In addition, C supports arrays of multiple dimensions, which are stored in row-major order. Technically, C multidimensional arrays are just one-dimensional arrays whose elements are arrays. The syntax for declaring multidimensional arrays is as follows:

int array2d[ROWS][COLUMNS];

where ROWS and COLUMNS are constants. This defines a two-dimensional array. Reading the subscripts from left to right, array2d is an array of length ROWS, each element of which is an array of COLUMNS integers.

To access an integer element in this multidimensional array, one would use

array2d[4][3]

Again, reading from left to right, this accesses the 5th row, and the 4th element in that row. The expression array2d[4] is an array, which we are then subscripting with [3] to access the fourth integer.

Higher-dimensional arrays can be declared in a similar manner.

A multidimensional array should not be confused with an array of references to arrays (also known as an Iliffe vectors or sometimes an array of arrays). The former is always rectangular (all subarrays must be the same size), and occupies a contiguous region of memory. The latter is a one-dimensional array of pointers, each of which may point to the first element of a subarray in a different place in memory, and the sub-arrays do not have to be the same size. The latter can be created by multiple uses of malloc.

Source: Wikipedia, https://en.wikipedia.org/wiki/C_syntax#Pointers
 This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 License.