Data Structures and Algorithms with C · Lecture Notes

Chapter 2: Arrays and Structures

The array is the oldest and most widely used data structure in programming. Its elements are reached by index in constant time. This speed comes from the array sitting contiguously in memory and from the address of every element being computed with a simple formula. The chapter first defines the array as an abstract data type and then descends to its implementation in C. The relationship between arrays and pointers follows, then arrays that grow with malloc, realloc, and free, and the amortized cost of doubling. How multidimensional arrays are laid out in one-dimensional memory, and how the address of an element is computed, is treated in detail. The same idea is used to hold lower triangular and band matrices by storing only the necessary elements. The last sections cover the struct and union types, which bring together fields of different types, C strings, and the analysis of matrix multiplication.

Learning outcomes

See the array abstractly and concretely
Define the array ADT and explain the contiguous layout of a C array in memory and the relationship between an array name and a pointer.
Compute addresses
Find the address of an element of two-, three-, and n-dimensional arrays in row-major and column-major layout; reduce the number of multiplications with Horner's method.
Save memory
Store triangular and band matrices in a one-dimensional array and write functions that reach every element in O(1) time.
Dynamic memory
Build growing arrays and two-dimensional arrays with malloc, realloc, and free; justify the amortized cost of doubling.
Record types
Use struct, union, and strings terminated by '\0' correctly and safely; explain the effect of alignment on structure size.
Matrix operations
Derive the step counts of matrix addition and multiplication and show that multiplication is O(n3).

2.1The array abstract data type

A data structure can be thought of at two levels. At the abstract level one speaks only of what the structure does, that is, which values it holds and which operations it offers. At the concrete level one deals with the layout in memory and the code with which those operations are carried out. The first level is called the abstract data type (ADT), the second the implementation. The array is a structure in which the two levels are often confused: say "array" and one immediately thinks of cells sitting side by side in memory. Yet sitting side by side is not the definition of the array but its most common implementation.

2.1.1An array is a mapping

Viewed abstractly, an array is a relationship established between indices and values. Each valid index corresponds to exactly one value. The grades of the students in a class by their sequence number, the temperatures by the days of a year, or the pieces by the squares of a chessboard are relationships of this kind. The index set may be a range of numbers or, as on a chessboard, may consist of pairs of numbers.

Definition 2.1

An array is a set of ⟨index, value⟩ pairs. For every defined index, the set contains exactly one pair that starts with that index. This relationship is called a mapping: an array is a mapping from the index set to the value set.

An ADT is defined not only by its values but also by its operations. The textbook by Horowitz, Sahni, and Anderson-Freed gives three operations for the array ADT. Create builds an empty array, Retrieve reads the value at an index, and Store writes a value at an index. The meaning of these operations is shown in Table 2.1.

Table 2.1: The operations of the array ADT.
OperationMeaning
Create(j, list)Returns an empty array of dimension j whose index set is list.
Retrieve(A, i)Returns the value A[i] if i is a valid index, and an error otherwise.
Store(A, i, x)If i is valid, pairs i with x in A and returns the new array; otherwise returns an error.

Two details of the definition are important. First, Retrieve and Store give an error at an invalid index. At the ADT level, index checking is part of the operation. Second, Store returns "the new array". At the abstract level a write does not destroy the old array but produces a new mapping. In a language such as C, however, a write changes the contents of the existing cell. These two differences show why the implementation must be thought of separately from the ADT. A C array does not check the index at all and changes the place it writes to in place. These two properties give speed, and in return give up safety.

2.1.2The source and the price of speed

The most common implementation of an array is to place the elements in consecutive cells of memory. Since every element has the same type, each occupies the same number of bytes. If this number is called s and the address of the first element α, the address of the element with index i is computed directly:

address(A[i]) = α + i · s

This computation consists of one multiplication and one addition. Whatever the length of the array, the number of operations does not change. That is why access by index takes O(1) time. Reaching the 999th element of an array of a thousand elements takes as little time as reaching the first. In structures such as the linked list, one must start at the beginning and move element by element to reach the same element. This is the distinguishing strength of the array.

Contiguous placement has two costs. First, the size of the array is fixed in advance. The block allocated in memory does not grow by itself afterwards; if a bigger array is needed, a new block is allocated and the old elements are moved there. Second, insertion and deletion in the middle are expensive. To insert a new element at the front of an array of n elements, all the elements must be shifted one cell to the right. In deletion, too, the following elements are shifted left to close the gap. Since the number of shifted elements is n in the worst case, insertion and deletion in the middle take O(n) time. Appending at the end of the array requires no shifting; the cost of that operation is examined separately under dynamic arrays.

2.2One-dimensional arrays in C

C implements the array ADT directly within the language. When an array is declared, the compiler allocates a contiguous block of memory and remembers the address of the first element. This section covers the declaration, the address computation, the sizeof operator, and the close relationship between the array name and the pointer. To follow the topic, it is enough to know two pointer operators: &x gives the address of the object x; *p reaches the object that the pointer p points to.

2.2.1Declaration, address, and sizeof

The following declaration defines two arrays. list holds five integers, and plist holds five pointers to integers.

int list[5], *plist[5];
/* list : 5 integers          */
/* plist: 5 pointers to int   */

list[i]  /* address: α + i * sizeof(int) */
sizeof list   /* 5 * sizeof(int) bytes */

The compiler allocates a contiguous block of five ints for list and keeps the address of list[0], that is, α. When the program writes list[i], the address of the element is computed at run time as α + i · sizeof(int). sizeof is an operator that gives the size of a type or object in bytes. Its value is known at compile time. For a local array, sizeof list gives the size of the whole array: if int is 4 bytes, 5 · 4 = 20 bytes. plist holds five pointers, and on a 64-bit system each pointer is 8 bytes, so sizeof plist is 40. These values were measured in the driver program written for these notes; the sizes of int and of pointers may vary with the compiler and the system.

[0]10[1]20[2]30[3]40αα+4α+8α+12
Figure 2.1: An array of four integers in memory. Assuming sizeof(int) = 4, the elements sit at the addresses α, α + 4, α + 8, and α + 12.

Figure 2.1 shows this layout. Each box is an element; the index is written above the box and the address below it. The addresses grow by four bytes, because every int occupies four bytes. Indices start from 0: the valid indices of an array of n elements are 0, 1, …, n − 1. The reason for starting at zero is the address formula. The address of the first element becomes α + 0 · s = α, and the formula needs no extra correction term.

C does not check whether an index is valid. While Retrieve and Store in the ADT give an error at an invalid index, C computes the address α + 5 · 4 for the expression list[5] as well and accesses it. No part of the array is at this address; it may be another variable, a return address, or a region that was never allocated. The C standard regards this case as undefined behavior. The program may crash, produce a wrong result, or seem to work correctly. The last is the most dangerous, because the error shows up only on another machine or with another input.

Common mistake

Writing the loop in an array of n elements as for (i = 0; i <= n; i++). In the last round a[n] is accessed and one cell beyond the array is read or overwritten. The compiler does not catch this error. The correct condition is i < n; the rule "n elements, last index n − 1" must be kept in mind in every loop.

2.2.2Array name and pointer

A pointer is a variable that holds the memory address of an object. In C, an array name turns into the address of the first element in most expressions. For example, when list is written, the compiler treats it as &list[0], that is, as an address of type int *. This rule brings arrays and pointers very close together. Table 2.2 lists equivalent expressions.

Table 2.2: Equivalents of array and pointer expressions (int list[5]; int *p;).
ExpressionEquivalent
list&list[0]
list + i&list[i] (i · sizeof(int) bytes forward)
*(list + i)list[i]
p = list; then p[i]the same cell as list[i]

The second row of the table contains the basic rule of pointer arithmetic. When an integer is added to a pointer, the unit is not a byte but one element of the type pointed to. If p is an int *, p + 1 points to the next int; the address grows not by 1 but by 4 bytes. For double * the increase is 8 bytes, for char * 1 byte. The compiler does the multiplication itself. In this way the notation *(list + i) becomes the direct counterpart in C of the address formula α + i · s. In fact, the notation list[i] is defined in the standard as *(list + i); the square brackets are a short way of writing this addition and dereference.

An array name and a pointer variable are still not the same thing. Two differences matter:

  • An array name cannot be assigned to. list = p; does not compile. An array name is not a variable but a constant address known to the compiler. p = list; is valid, because p is a variable and can hold another address.
  • sizeof gives a different result. For a local array, sizeof list gives the size of the whole array (20 bytes). For a pointer, sizeof p is only the size of the pointer itself (8 bytes on a 64-bit system).

The second difference often leads to mistakes in function parameters. In C, when an array is passed to a function, the array is not copied; only the address of its first element is passed. So the declarations void f(int a[]) and void f(int *a) are exactly the same. Even if the parameter is written as int a[10], a is a pointer inside the function and sizeof a gives 8. In the driver written for these notes, the compiler issued the warning -Wsizeof-array-argument for this usage. The length of the array is sent to the function as a separate parameter. This is why functions of the standard library such as qsort, memcpy, and fwrite all take a length parameter.

Common mistake

Computing the array length inside a function with sizeof a / sizeof a[0]. This pattern works correctly only where the array is declared. Since a, arriving as a parameter, is a pointer, the result is 8 / 4 = 2 on a 64-bit system and has nothing to do with the real length of the array.

2.2.3Code trace: print_array()

The following program passes an array of four elements to the function print_array. The function prints the address and value of each element using pointer arithmetic.

void print_array(int *p, int n) {
  int i;
  for (i = 0; i < n; i++)
    printf("%p %d\n", (void *)(p + i), *(p + i));
}

int main(void) {
  int arr[] = {10, 20, 30, 40};
  print_array(arr, 4);
  return 0;
}

The program works as follows, line by line:

  • main allocates arr on the stack as four consecutive ints. The size is derived from the number of initial values. Let us call the address of the first element α.
  • In the call print_array(arr, 4) the array is not copied. The name arr turns into &arr[0], and this address, that is α, is copied into the parameter p. The length arrives as a separate parameter (n = 4).
  • In each round of the loop, p + i computes the address α + i · 4. *(p + i) reads the value at this address; it is the same as writing p[i].
  • The %p format expects a void *. That is why the address is converted with (void *). If the conversion is not written, the behavior is undefined according to the standard.
Table 2.3: Trace of the call print_array(arr, 4) (sizeof(int) = 4).
ii < np + i*(p + i)Line printed
00 < 4, trueα + 010α 10
11 < 4, trueα + 420α + 4 20
22 < 4, trueα + 830α + 8 30
33 < 4, trueα + 1240α + 12 40
44 < 4, false——the loop ends, print_array returns

In the real output a hexadecimal address appears in place of α. In one run made for these notes the addresses came out …F910, …F914, …F918, and …F91C. The last two hexadecimal digits grow by four, as 10, 14, 18, 1C. The address itself may change on every run; what does not change is the 4-byte difference between two consecutive elements. The function visits each element of the array once and does constant work in each round. Its time is Θ(n) and its extra memory O(1).

2.3Dynamic arrays

In a declaration such as int list[5]; the size is known at compile time. In many programs, however, the size is learned only at run time: the number of students the user enters, the number of lines in a file, or the number of packets arriving from a network connection. In this case memory is requested at run time. This is called dynamic memory allocation. In C it is done with the functions malloc, calloc, realloc, and free in the header <stdlib.h>.

2.3.1An array with malloc

The following fragment first reads the size of the array, then allocates a block of that many ints, uses the block like an array, and finally gives it back.

int n, i, *a;
scanf("%d", &n);
a = malloc(n * sizeof *a);   /* n ints */
if (a == NULL) {
  fprintf(stderr, "Out of memory\n");
  exit(EXIT_FAILURE);
}
for (i = 0; i < n; i++)
  a[i] = i * i;              /* like an array */
free(a);                     /* give it back */
a = NULL;          /* no dangling pointer */

The code works as follows, line by line:

  • malloc(n * sizeof *a) asks for the number of bytes sufficient for n integers and returns the starting address of the block. The return type is void *; C assigns this address to a, of type int *, without a cast.
  • If memory is insufficient, malloc returns NULL. A null pointer points to no object. If a[i] is written without checking this case, the program crashes. If the check fails, a message is written and the program terminates with exit(EXIT_FAILURE).
  • The loop fills the block with a[i] = i * i. Although a is a pointer, the notation a[i] works as with an array, because a[i] already means *(a + i).
  • free(a) gives the block back to the system. Then a = NULL is written. After free, a still holds the old address, but the memory at that address no longer belongs to the program. Such a pointer is called a dangling pointer. Assigning NULL turns a possible misuse into an immediately noticeable error instead of an unclear corruption.

A local array and a malloc block have different lifetimes. An array declared inside a function sits in the stack frame of the call and disappears when the function returns. A block obtained with malloc, on the other hand, sits in heap memory and lives until it is freed. A function can therefore safely return the address of a block it allocated inside, but cannot return the address of a local array. The address of a local array becomes a dangling pointer the moment the function returns.

The pattern sizeof *a in the size expression is a deliberate choice. sizeof *a gives the size of the type that a points to. Even if the type of a is later changed to double *, the expression computes the correct size by itself. Writing sizeof(int) is correct too, but one may forget to update it when the type changes. A more dangerous mistake is to confuse sizeof(int *) with sizeof(int): on a 64-bit system the first is 8 and the second 4 bytes. If the wrong one is smaller, the end of the block is overrun; if it is larger, memory is wasted.

The library has two more functions. calloc(n, s) reserves room for n elements of s bytes each and zeroes all bytes of the block. malloc does not zero the block; the initial contents are indeterminate. realloc(p, new_size) enlarges or shrinks a previously allocated block. If the block cannot grow in place, realloc allocates a new block, copies the old contents there, and frees the old block. If p is NULL, realloc behaves exactly like malloc. This last property is useful in growing arrays that start empty.

Common mistake

Not checking the return of malloc, or continuing to use the pointer after free. In the first case, when memory is insufficient, the program tries to write to address NULL. In the second, the block that was given back may have been allocated again for another request, and a write lands on top of other data. Checking for NULL after every malloc, and assigning NULL to the pointer after every free, should become a habit.

2.3.2A growing array: append()

If it is not known at all how many elements will come, the array must be able to grow. A dynamic array is an array that is enlarged with realloc when it fills up. Defining a dynamic array takes three pieces of information: the address of the block in which the elements sit, how many elements are currently in the array, and the maximum number of elements the block can hold. The last value is called the capacity. In the following code these three pieces of information sit in the fields data, size, and cap of the structure DynArray.

typedef struct { int *data; int size, cap; } DynArray;

int append(DynArray *d, int x) {
  if (d->size == d->cap) {              /* full */
    int ncap = d->cap ? 2 * d->cap : 1;
    int *t = realloc(d->data, ncap * sizeof *t);
    if (t == NULL) return 0;    /* old block intact */
    d->data = t;
    d->cap = ncap;
  }
  d->data[d->size++] = x;
  return 1;
}

The code works as follows, line by line:

  • d is a DynArray *. A pointer is taken so that the structure itself is not copied and the function can change size and cap permanently. The notation d->size is short for (*d).size.
  • If d->size == d->cap, the array is full and must first be enlarged. The new capacity is twice the old one. If the capacity is 0, its double would also be 0, so ncap is taken as 1. The conditional operator ?: separates these two cases in one line.
  • The result of realloc is first taken into a temporary variable t. On failure realloc returns NULL but does not touch the old block. Had the result been written directly into d->data, the address of the old block would have been lost: the elements would be neither reachable nor freeable. This is a memory leak. In the code, in case of failure 0 is returned and the array stays intact in its old state.
  • If the enlargement succeeds, d->data and d->cap are updated.
  • The line d->data[d->size++] = x; writes the element into the first empty cell. size++ is the postfix form: in the expression the old value is used first, and then the value is incremented by one. So x is written to data[size] and then size grows by one.
Example 2.1

Let 7, 3, 9, 4, and 6 be appended in turn to an empty dynamic array ({NULL, 0, 0}). At each append it is checked whether the array is full; if it is, the capacity is doubled and the old elements are copied to the new block. Table 2.4 gives all the steps.

Table 2.4: Trace of append while 7, 3, 9, 4, 6 are appended to an empty array. "Copies" is the number of elements moved to the new block when growing.
xsize == capncapCopies (total)capsizedata
70 == 0, full10 (0)11[7]
31 == 1, full21 (1)22[7, 3]
92 == 2, full42 (3)43[7, 3, 9, _]
43 == 4, room left—0 (3)44[7, 3, 9, 4]
64 == 4, full84 (7)85[7, 3, 9, 4, 6, _, _, _]

At the first append data is NULL and realloc(NULL, …) behaves like a malloc; there are no elements to copy. At the later enlargements 1, 2, and 4 elements are copied in turn. For five appends only 7 copies are made in total. At the fourth append (4) there is room in the array and the element is written directly. In the driver program written for these notes, the number of realloc calls and the total of copies came out exactly the same as in this table. Here "copies" is the number of elements realloc moves in the worst case. If the block can grow in place, realloc does not copy at all; the analysis therefore gives an upper bound.

data07size = 1 cap = 1 data0713293size = 3 cap = 4 data0713293446567size = 5 cap = 8
Figure 2.2: Three moments of the dynamic array. (a) First append: capacity 1, element 7. (b) Third append: the capacity has doubled to 4, 9 was written; one cell is empty. (c) Fifth append: capacity 8, five elements full, three cells empty.

2.3.3Amortized cost

The cost of a single append call varies greatly. If there is room in the array, the call consists of one write and takes O(1) time. If the array is full, realloc may copy all the elements; that call takes O(n) time. Looking only at the worst case gives a pessimistic result such as O(n2) for n appends. Yet the expensive calls are rare: because the capacity doubles each time, enlargement is needed only after 1, 2, 4, 8, … elements. Finding the cost per operation by dividing the total cost of a long sequence of operations by the number of operations is called amortized analysis.

Theorem 2.1 (Cost of doubling)

If n ≥ 1 elements are appended to an empty dynamic array with the capacity doubling, the total number of copies is less than 2n. Counting the writes as well, the total work is less than 3n. Hence the amortized cost per append is O(1).

Enlargements happen when 1, 2, 4, …, 2k elements fill the array, where 2k is the largest power of two less than n. At each enlargement the elements then in the array are copied. The total number of copies is a geometric series: 1 + 2 + 4 + … + 2k = 2k+1 − 1. Since 2k < n, this total is less than 2n − 1. Each element is also written once; that makes n units of work. The total is less than 3n, and divided by n a constant per append remains. ∎

Increasing the capacity by one cell each time, instead of doubling it, looks more economical at first glance. But in that case an enlargement is needed at every append. At the ith append i − 1 elements are copied, and the total number of copies is 0 + 1 + … + (n − 1) = n(n − 1)/2. This is O(n2). Growing by a fixed c does not fix the situation either: the number of enlargements is n/c, and the total number of copies is still proportional to n2. What matters is that the increase is proportional to the current capacity, not fixed. Table 2.5 compares the two strategies for a few values of n.

Table 2.5: Total number of copies when n appends are made to an empty array. The values were produced with a counting program.
n appendsDoubling: copiesCopies / nGrow by +1: copiesCopies / n
870.88283.5
64630.982,01631.5
1,0241,0231.00523,776511.5

With doubling, the number of copies per append stays below 1; when n is a power of two, the number of copies is exactly n − 1. With growth by one, the number of copies per append is (n − 1)/2 and grows with n. At a thousand elements the difference is more than five hundredfold.

The amortized result does not mean that every single append is fast. The append that coincides with an enlargement still takes O(n). Amortized analysis guarantees the average over a long sequence of operations; it does not rely on probability and holds for the worst sequence of operations as well. In a real-time system, where the time of a single operation matters, this distinction must be taken into account.

Doubling also has a memory cost. Right after an enlargement about half the capacity is empty. The capacity never exceeds twice the size; that is, in the worst case half the cells are unused. Some libraries use a smaller factor such as 1.5 to reduce this margin. As long as the factor stays above 1, the total number of copies is still O(n); only the constant changes.

Common mistake

Writing a = realloc(a, new_size * sizeof *a);. If realloc fails, it returns NULL and this value is written into a. The old block is still allocated, but its address is no longer in any variable: the block leaks and the data in it is lost. The result must first be taken into a temporary variable and, if it is not NULL, assigned to the real pointer.

In an experiment made for these notes, malloc and realloc were replaced with a wrapper that keeps counters, and the third realloc was made to fail on purpose. append returned 0, the array stayed intact with its two elements (0, 1), and after free no allocated block was left.

2.3.4A two-dimensional dynamic array: array2d()

For a matrix whose number of rows and columns is known only at run time, the most common method is to build an array of pointers. First an array holding one pointer for each row is allocated, then each row is allocated as a separate block and its address is written into this array. The address of the matrix is the address of the pointer array. The type of this address is int **, that is, a pointer to pointer.

int **array2d(int rows, int cols) {
  int i, **x = malloc(rows * sizeof *x);
  if (x == NULL) return NULL;
  for (i = 0; i < rows; i++) {
    x[i] = malloc(cols * sizeof **x);
    if (x[i] == NULL) {                /* roll back */
      while (--i >= 0) free(x[i]);
      free(x); return NULL;
    }
  }
  return x;
}

The code works as follows, line by line:

  • malloc(rows * sizeof *x) allocates a block of rows pointers. Since x is an int **, *x is an int * and sizeof *x gives the size of a pointer. If this block cannot be allocated, the function immediately returns NULL.
  • The loop allocates cols ints for each row. Since **x is an int, sizeof **x is the size of an integer. The two sizeof expressions are different and must not be confused.
  • If a row cannot be allocated, everything allocated so far is given back. while (--i >= 0) first decrements i and then checks; thus the failed row i is skipped and rows i − 1, …, 0 are released. Last, the pointer array is given back and NULL is returned. If this step is not written, the rows already allocated leak on failure.
  • If all rows were allocated, x is returned. The caller can use the notation x[i][j] as in an ordinary two-dimensional array.
Table 2.6: Trace of the call array2d(3, 4).
StepOperationResult
1x = malloc(3 * sizeof(int *))pointer array of 3 cells; contents indeterminate
2x == NULL?no, continue
3i = 0: x[0] = malloc(4 * sizeof(int))x[0] points to a block of 4 ints
4i = 1: x[1] = malloc(…)x[1] points to the second block
5i = 2: x[2] = malloc(…)x[2] points to the third block
6i = 3, 3 < 3 falsethe loop ends, x is returned
xx[0]0?1?2?3?x[1]????x[2]????rows = 3cols = 4
Figure 2.3: The structure built by array2d(3, 4). x points to an array of three pointers; each pointer points to a separate row block of four ints. The contents of the rows are still indeterminate (?).

Figure 2.3 gives the structure as it appears in memory. The expression x[i][j] is resolved in two steps: x[i], that is *(x + i), fetches the address of row i; [j] advances j elements from this address. Written out in full it is *(*(x + i) + j). In the driver program, the values x[2][3] = 23 and *(*(x + 1) + 2) = 12 were read as expected after 10i + j was written into the rows.

There is an important difference between this structure and a real two-dimensional array such as int a[3][4];. In a real array all twelve elements sit in a single contiguous block. In the pointer array, each row is allocated by a separate malloc call, so rows need not be contiguous in memory. Two consequences follow. First, rows can have different lengths; for a lower triangular matrix it is possible to allocate only i + 1 cells for row i. Second, the structure involves one more step of indirection, and it is not possible to copy the whole matrix with a single memcpy.

The order matters when such a matrix is given back. First every row x[i] and then the pointer array x is freed. If the order is reversed, x[i] is read after x has been released; that is an access to memory that has been given back. If only free(x) is written, the addresses of the rows are lost and all of them leak.

Common mistake

Releasing a two-dimensional dynamic array with only free(x). In a matrix of three rows this leaks three blocks. The correct order: for (i = 0; i < rows; i++) free(x[i]); free(x);. In the experiment with counters written for these notes, the cases in which array2d fails at each allocation were tried one by one; in every case the function returned NULL and no allocated block was left behind.

In terms of cost, array2d makes rows + 1 calls to malloc. If the time of each call is taken as constant, the function takes O(rows) time. The memory allocated is the sum of rows · cols integers and rows pointers. Access to the elements is O(1), even though it involves two indirect steps.

2.4Multidimensional arrays and address computation

A table, a picture, or a game board is expressed naturally with two indices; a volume or a video with three. An array whose elements are reached with more than one index is called a multidimensional array. Memory, however, is one-dimensional: every byte has a single address. This section examines how a multidimensional array is laid out in one-dimensional memory and how the address of an element is computed.

2.4.1Memory is one-dimensional

An n-dimensional array declared as A[u0][u1]…[un−1] has u0 · u1 · … · un−1 elements. For example A[10][10][10] holds a thousand elements. The compiler must put these elements into memory in some order. There are two basic orders.

Definition 2.2

In row-major order, all elements of row 0 are placed first, then the elements of row 1; the rightmost index varies fastest. In column-major order, all elements of column 0 are placed first, then the elements of column 1; the leftmost index varies fastest.

C, C++, and the NumPy library in Python use row-major order by default. Fortran, MATLAB, and R are column-major. In a program that passes matrices between two languages, overlooking this difference results in the matrix being transposed without anyone noticing.

Whichever order is chosen, the address computation rests on the same question: how many elements are there in memory before the element A[i][j]? If this number is called k, the address of the element is α + k · s. Here α is the starting address of the array and s is the size of one element in bytes. In a one-dimensional array k = i; in a multidimensional array k is the sum of several terms.

In C, the declaration int x[3][4]; is really an array of arrays: three elements, each an array of four ints. The expression x[1] points to the start of row 1, that is, of an array of four elements. In the driver program the difference x[1] - x[0] came out as 4 elements: there is exactly one row between two row starts. This structure is the row-major order showing up directly in the type system of the language.

2.4.2Row-major and column-major formulas

Let us take the array int x[3][4]; the number of rows is u0 = 3 and the row length is u1 = 4. In row-major order there are i full rows before x[i][j]. Since each row has u1 elements, these rows come to i · u1 elements. In the element's own row there are j elements to its left. The total:

row-major: &x[i][j] = α + (i · u1 + j) · s

In column-major order, j full columns come first. Each column has u0 elements; these come to j · u0 elements. Within its column, the element has i elements above it:

column-major: &x[i][j] = α + (j · u0 + i) · s
00x0001x0112x0223x0331x104x115x126x1372x208x219x2210x23110x001x012x023x034x105x116x127x138x209x2110x2211x23αα + 11·srow-major: row by row 00x0001x0132x0263x0391x101x114x127x13102x202x215x228x23110x001x102x203x014x115x216x027x128x229x0310x1311x23αα + 11·scolumn-major: column by column
Figure 2.4: The two layouts of the array int x[3][4]. The small numbers in the corners of the matrix cells are the position of the element in the linear array. At the top, row-major order: the four elements of row 0 come first. At the bottom, column-major order: the three elements of column 0 come first.

Figure 2.4 shows that the same element falls at different positions in the two orders. x12 is at position 1 · 4 + 2 = 6 in row-major order and at position 2 · 3 + 1 = 7 in column-major order. The two formulas follow the same logic; only which index is "outer" and which is "inner" changes.

The expression in parentheses in the formula is in units of elements. To get to a byte address, it is multiplied by the element size s. Since pointer arithmetic in C does this multiplication itself, &x[0][0] + 6 is already 6 · s bytes ahead. When computing a byte address by hand, however, s must not be forgotten.

Common mistake

Using the number of rows (u0) in the row-major formula. The space taken by i full rows depends on the row length (u1, that is, the number of columns). The number of rows does not appear in the formula at all. In square matrices the two values are equal, so the mistake stays hidden; in a non-square matrix such as 3 × 4 it immediately gives a wrong address.

2.4.3Code trace: address()

The row-major formula can be written as a small function. The function takes the starting address, the two indices, the row length, and the element size, and returns the byte address.

/* int x[3][4]: row-major byte address */
long address(long alpha, int i, int j,
             int dim1, int s) {
  long k = (long)i * dim1 + j;   /* elements before */
  return alpha + k * s;
}

int main(void) {
  printf("%ld\n", address(100, 1, 2, 4, 4));
  printf("%ld\n", address(100, 2, 3, 4, 4));
  return 0;
}

k is the number of elements before the element. The cast (long)i makes the multiplication happen in type long; for very large arrays an int product could overflow. The function returns alpha + k * s. main asks for the addresses of two elements: x[1][2] and x[2][3]; the array starts at address 100, u1 = 4, and s = 4.

Table 2.7: The two calls of the function address (α = 100, u1 = 4, s = 4).
Callk = i · dim1 + jReturn alpha + k · sOutput
address(100, 1, 2, 4, 4)1 · 4 + 2 = 6100 + 6 · 4 = 124124
address(100, 2, 3, 4, 4)2 · 4 + 3 = 11100 + 11 · 4 = 144144
000010120230311011121322021222300010120230341051161271382092110221123100104108112116120124128132136140144address▲ k = 6
Figure 2.5: The address of x[1][2]. Before the element there is one full row (4 elements) and 2 elements in its own row; k = 6, address 100 + 6 · 4 = 124.

x[2][3] in the second call is the last element of the array. k = 11, that is, the last position in an array of twelve elements. When the program is compiled and run, it prints 124 and 144. Had column-major order been used, k = 2 · 3 + 1 = 7 for x[1][2] and the address would have been 128. In the driver program, in a real int x[3][4] array the difference &x[1][2] - &x[0][0] also came out as 6 elements; thus one sees directly that C is row-major. The function contains no loop that depends on the input; its time is O(1).

2.4.4Three-dimensional arrays

A three-dimensional array is an array of two-dimensional arrays. The array G[2][2][3] has two slices; each slice is a matrix of 2 rows and 3 columns. In row-major order the six elements of slice 0 come first, then the six elements of slice 1. The inside of a slice is also laid out row by row.

slice 0[0][0][0]+0[0][0][1]+1[0][0][2]+2[0][1][0]+3[0][1][1]+4[0][1][2]+5slice 1[1][0][0]+6[1][0][1]+7[1][0][2]+8[1][1][0]+9[1][1][1]+10[1][1][2]+11
Figure 2.6: The two slices of the array G[2][2][3]. In each cell the indices of the element are written, and below them its linear position (+0 … +11).

The elements before G[i][j][k] are again counted layer by layer. First there are i full slices; each slice comes to u1 · u2 elements. Then within its own slice there are j full rows, each of u2 elements. Finally in its own row there are k elements. Table 2.8 shows step by step how these terms are added; the addresses are in units of elements.

Table 2.8: How the address of an element in a three-dimensional array is built up (in element units).
ElementAddress
[0][0][0]α
[i][0][0]α + i · u1 · u2
[i][j][0]α + i · u1 · u2 + j · u2
[i][j][k]α + i · u1 · u2 + j · u2 + k

The expression in the last row has three multiplications and three additions. Since multiplication is a more expensive operation than addition, the compiler rewrites the expression by factoring out the common factor:

α + (i · u1 + j) · u2 + k

In this form two multiplications and three additions remain. For G[1][0][2] the computation gives (1 · 2 + 0) · 3 + 2 = 8. Comparing with Figure 2.6, one sees that under the cell [1][0][2] indeed +8 is written. In the driver program, in a real int G[2][2][3] array the difference &G[1][0][2] - &G[0][0][0] also came out as 8.

2.4.5The n-dimensional generalization

The same idea extends to any number of dimensions. In the array A[u0][u1]…[un−1], before A[i0][i1]…[in−1] there are, for the outermost index, i0 full "slices", each of u1 u2 … un−1 elements. For the next index inward there are i1 blocks of u2 … un−1 elements. The innermost index adds only in−1 elements.

Table 2.9: Address terms in an n-dimensional array (in element units).
ElementAddress
A[0][0]…[0]α
A[i0][0]…[0]α + i0 · u1 u2 … un−1
A[i0][i1]…[0]previous row + i1 · u2 … un−1
A[i0]…[in−1]previous row + in−1

The terms can be written as a sum. The coefficient of the jth index is the product of all the dimensions that come after it:

&A[i0]…[in−1] = α + Σj=0n−1 ij · aj,   aj = uj+1 · uj+2 · … · un−1 (0 ≤ j < n − 1),   an−1 = 1

The coefficients aj depend only on the dimensions, not on the indices. The compiler computes them once, at compile time. A notable consequence of the formula is that u0 appears in no coefficient. The length of the outermost dimension does not enter the address computation. This is why a function parameter in C can be written int a[][4] but cannot be written int a[3][]. The first dimension is unnecessary for the address, while the following ones are mandatory.

Computing each term separately takes many multiplications. Horner's method is a method that evaluates a polynomial with nested products, and it is useful here as well. The address term can be rewritten as follows:

(…((i0 · u1 + i1) · u2 + i2) · u3 + … ) · un−1 + in−1

The computation starts with t = i0 and for each dimension t = t · uj + ij is performed. The loop runs n − 1 times, with one multiplication and one addition per round. In total n − 1 multiplications suffice. The "factoring out" in the three-dimensional array is the special case of this method for n = 3.

2.4.6Code trace: offset()

Horner's method is written as a general function that takes the array of indices and the array of dimensions. The function returns the relative position in element units; the byte address is found with alpha + t * s.

/* idx: indices, dim: dimensions, n: number of dimensions */
int offset(const int idx[], const int dim[], int n) {
  int j, t = idx[0];
  for (j = 1; j < n; j++)
    t = t * dim[j] + idx[j];            /* Horner */
  return t;               /* address = alpha + t*s */
}

The const in the parameters documents that the function will not modify the arrays. t starts with the outermost index. Since the loop starts at j = 1, dim[0] is never read. Thus the fact that the outermost dimension does not enter the address computation is visible in the code as well.

Table 2.10: Position of G[1][0][2] in the array G[2][2][3] with offset (idx = {1, 0, 2}, dim = {2, 2, 3}, n = 3).
StepjOperationtMeaning
start—t = idx[0]1slice number 1
11t = 1 · 2 + 02the "global row" number counted across slices (slice 1, row 0)
22t = 2 · 3 + 28there are 8 elements before the element
end33 < 3 false8the loop ends, 8 is returned
slice 0000001002010011012slice 110010110211011111200001001200230104011501261007101810291101011111112
Figure 2.7: The result of offset. G[1][0][2] (orange) is cell number 8 of the linear array.

The meaning of the intermediate value t = 2 is interesting. If the rows of the two slices are counted one after the other (rows 0 and 1 of slice 0, rows 2 and 3 of slice 1), the sought element is in row number 2. In the last step, multiplying this row number by the row length (3) and adding the column index gives the position of the element. The computation uses two multiplications in all, that is, n − 1. The direct formula gives the same result: 1 · 2 · 3 + 0 · 3 + 2 = 8. In the driver program the relative position of [2][3][4] was also tried for an array A[4][5][6], and the result of the function (82) came out the same as the difference in the real array. The time of offset is linear in the number of dimensions, Θ(n). Since the number of dimensions is fixed for an array, access is O(1) in terms of the number of elements.

2.5Triangular matrices

The address formula is useful not only to the compiler. The programmer can also arrange memory and find the place of elements with a formula. The simplest application of this idea is to store matrices that are half empty by keeping only their filled halves.

2.5.1The lower triangular matrix

A square matrix is divided into two by its main diagonal. In some applications one of the halves suffices. In a table of distances between cities, the distance from i to j is the same as the distance from j to i; half the table is a repeat of the other half. In solving systems of linear equations, too, matrices that are zero above the diagonal occur often.

Definition 2.3

A lower triangular matrix is a square matrix all of whose elements above the main diagonal are zero: if i < j then aij = 0.

There is no need to store the zeros. The rest of the matrix is kept row by row in a one-dimensional array LOW. The user, however, is offered an interface as if working with a two-dimensional matrix: when aij is requested, the function computes its position in LOW.

00a001020301a10a11002a20a21a2203a30a31a32a330a001a102a113a204a215a226a307a318a329a33Array LOW (n(n+1)/2 = 10 elements)
Figure 2.8: A 4 × 4 lower triangular matrix and the 10-element array LOW that holds it row by row. The six zeros above the diagonal are not stored.

To find the formula, the same question is asked again: how many elements are there in LOW before aij? In row i, i + 1 elements are stored (from column 0 to i). The previous rows come to 1 + 2 + … + i = i(i + 1)/2 elements. In its own row the element has j elements to its left:

k = i(i + 1)/2 + j   (j ≤ i)

In an n × n lower triangular matrix, 1 + 2 + … + n = n(n + 1)/2 elements are stored in all. A full matrix needs n2 cells. The saving is n(n − 1)/2 cells, which for large n means about half the memory. The formula can be tried on Figure 2.8: for a21 one finds k = 2 · 3/2 + 1 = 4, and LOW[4] is indeed a21.

2.5.2Code trace: lower_read()

The following function reads the stored elements of an n × n lower triangular matrix row by row from standard input and places them in the array low.

#define MAX_SIZE 100
void lower_read(int low[], int n) {
  int i, j, k;
  if (n * (n + 1) / 2 > MAX_SIZE) {
    printf("Array too small!\n"); exit(1);
  }
  for (i = 0; i < n; i++) {
    k = (i + 1) * i / 2;      /* elements before */
    for (j = 0; j <= i; j++)  /* j <= i */
      scanf("%d", &low[k + j]);
  }
}

The code works as follows, line by line:

  • First the number of elements to be stored, n(n + 1)/2, is compared with the capacity of the array, MAX_SIZE. If it does not fit, a message is printed and the program ends. Without this check a large n would overrun the end of the array.
  • The outer loop walks over the rows. k = (i + 1) * i / 2 is the number of elements already placed before row i; that is, the start of the row in low. The division is done after the multiplication; since i(i + 1) is always even, the division is exact.
  • The inner loop runs only for j <= i; the zeros above the diagonal are not read. Each value is written to low[k + j].
Example 2.2

Let the input for n = 4 be 3 1 4 1 5 9 2 6 5 3. First the check 4 · 5/2 = 10 ≤ 100 passes. Table 2.11 shows where each value is written.

Table 2.11: Trace of the call lower_read(low, 4).
ikjPosition k + jValue readMatrix element
01 · 0/2 = 0003a00
12 · 1/2 = 1011a10
11124a11
23 · 2/2 = 3031a20
23145a21
23259a22
34 · 3/2 = 6062a30
36176a31
36285a32
36393a33
00310203011400215903265303112431455962768593Array LOW (n(n+1)/2 = 10 elements)
Figure 2.9: The matrix and the array LOW when reading is finished. Ten values were read; the six zeros in the upper triangle were never stored.

The body of the function performs one scanf for each stored element. The total number of rounds of the inner loop is 1 + 2 + … + n = n(n + 1)/2. The time is proportional to the number of stored elements, Θ(n2). Reading a full matrix would take n2 rounds; the triangular representation halves the constant factor but does not change the growth rate. In the driver program the array low was printed after reading as 3 1 4 1 5 9 2 6 5 3 and the table was verified.

2.5.3Access and error codes: lower_get()

To access the matrix after reading, a function is needed that converts the pair (i, j) into a position inside LOW. The function must tell apart two exceptions: the indices may be outside the matrix, or the requested element may be in the upper triangle, that is, in the zero region that is not stored.

int lower_get(int i, int j, int n) {
  if (i < 0 || i >= n || j < 0 || j >= n) {
    printf("Invalid index\n");
    return -2;
  } else if (i < j) return -1;    /* upper triangle: 0 */
  else return (i + 1) * i / 2 + j;   /* valid */
}
/* main: */
printf("%d\n", lower_get(2, 1, 4));
printf("%d\n", lower_get(1, 3, 4));
printf("%d\n", lower_get(4, 0, 4));

The function first checks the bounds. If one of the indices is outside the range [0, n − 1], it prints a message and returns −2. Then it looks at whether i < j. If so, the element is in the upper triangle; its value is zero but it has no place in LOW, and the function returns −1. In the remaining case the element is in the lower triangle and the position is computed with the formula.

Table 2.12: The three calls of the function lower_get (n = 4).
CallBounds checki < j?ReturnOutput
lower_get(2, 1, 4), a21valid2 < 1, no3 · 2/2 + 1 = 44
lower_get(1, 3, 4), a13valid1 < 3, yes−1 (upper triangle)-1
lower_get(4, 0, 4), a40i = 4 ≥ n, invalid—−2Invalid index, -2

The output of the driver program consists of the lines 4, -1, Invalid index, and -2. The choice of return values is deliberate. Valid positions are nonnegative numbers such as 0, 1, 2, …. The error codes {−1, −2} do not intersect this set. The caller can therefore always tell the situation apart by looking at the return value: a negative value is an exception, and zero or a positive value is a real position. Had 0 been chosen as an error code, for example, it would be confused with the position of a00.

The function contains no loop that depends on the input: it makes a few comparisons and one formula evaluation. Its time is O(1). It is as fast as the access a[i][j] in a full matrix, yet works with half the memory.

Common mistake

Writing the position formula as i * i / 2 + j or (i + 1) * (i + 2) / 2 + j instead of i * (i + 1) / 2 + j. The first gives the row start too small (2 instead of 3 at i = 2), the second gives the start of the next row. The formula is easily tested on a small matrix with the corner elements: a00 → 0, a10 → 1, an−1,n−1 → n(n + 1)/2 − 1.

2.5.4Other triangles and the symmetric matrix

The stored half can take four forms, depending on which side of the diagonal it lies. In each, the position formula is derived by the same method: the elements in the previous rows are added up, then the order within the row is added. Table 2.13 gives the result for the four cases.

Table 2.13: Row-major position formula for the four kinds of triangles (n × n matrix).
Stored regionElements in row iPosition k
j ≤ i (lower left)i + 1i(i + 1)/2 + j
j ≥ i (upper right)n − ii · n − i(i − 1)/2 + (j − i)
i + j ≤ n − 1 (upper left)n − ii · n − i(i − 1)/2 + j
i + j ≥ n − 1 (lower right)i + 1i(i + 1)/2 + j − (n − 1 − i)

In the upper right triangle there are n − r elements in row r. The total before row i is n + (n − 1) + … + (n − i + 1) = i · n − i(i − 1)/2. The first stored element of the row is on the diagonal (j = i), so the order within the row is j − i. In the upper left triangle the row lengths are the same but the row starts at column 0; the order is directly j. In the lower right triangle row i holds i + 1 elements and starts at column j = n − 1 − i; the order is j − (n − 1 − i). A loop written for these notes tried the four formulas on every matrix from n = 1 to 8. The positions given by the formulas always came out the same as the positions counted row by row.

In a real symmetric matrix (aij = aji) the upper triangle is not zero but the mirror image of the lower triangle. In this case lower_get, instead of returning −1 for the upper triangle, swaps the indices: if i < j then k = j(j + 1)/2 + i. A distance table or the undirected adjacency matrix of a graph can be stored this way. The memory again halves and no information is lost.

2.6Band matrices

In the triangular matrix the stored region was one side of the diagonal. In many numerical problems, however, the nonzero elements gather in a narrow strip on both sides of the diagonal. In the numerical solution of physics problems such as heat conduction or vibration, each unknown is related only to its neighbors; the elements of the resulting matrix far from the diagonal are zero. Storing such a matrix in full means spending most of the memory on zeros.

2.6.1Definition and element count

Definition 2.4

A band matrix is a square matrix whose meaningful elements gather in a strip around the main diagonal. The elements outside the strip are unused or all have the same constant value c (most often c = 0). The matrix is described by three numbers: the side length n, the number a of lower diagonals including the main diagonal, and the number b of upper diagonals including the main diagonal.

00d001d012c3c1d10d11d12c2d20d21d22d233cd31d32d330d201d312d103d214d325d006d117d228d339d0110d1211d23band[]diagonal -2diagonal -1diagonal 0diagonal 1-20-120519start[](index = diagonal no + a − 1)
Figure 2.10: A band matrix with n = 4, a = 3, b = 2. On the left the matrix (elements outside the band are c); on the right the array band, which holds the elements diagonal by diagonal, and the array start, which holds the start of each diagonal.

In the matrix of Figure 2.10, the main diagonal and the two diagonals below it (a = 3) and one diagonal above the main diagonal (b = 2, main diagonal included) are stored. d02, d03, d13, and d30 fall outside the band.

To find the number of stored elements, the diagonals are counted one by one. The main diagonal has n elements. The diagonal one step away (below or above) has n − 1, and the one two steps away has n − 2 elements. In general a diagonal at distance t from the main diagonal has n − |t| elements. In all a + b − 1 diagonals are stored, because the main diagonal has been counted both in a and in b. If every diagonal had n elements, the total would be n(a + b − 1). The shortfalls in the lower diagonals are 1 + 2 + … + (a − 1) = a(a − 1)/2, and in the upper diagonals b(b − 1)/2:

number of elements = n(a + b − 1) − a(a − 1)/2 − b(b − 1)/2

In the example 4 · 4 − 3 − 1 = 12 elements are stored; a full matrix would need 16 cells. The saving looks small, because the matrix is small. In a matrix with n = 1000 and a = b = 3, however, the full matrix needs a million cells while the band representation makes do with 1000 · 5 − 3 − 3 = 4994 cells.

The storage problem is thus solved. The real question is whether the stored elements can still be reached quickly. When the elements are compressed, the position computation becomes more complicated too. The value of the band matrix representation depends on access still being possible in constant time.

2.6.2Diagonal number and the START array

The key to access is to tell from its indices at once which diagonal an element lies in. For elements in the same diagonal the difference j − i is constant. For example d20 and d31 are in the same diagonal: 0 − 2 = 1 − 3 = −2. This difference is called the diagonal number. The number of the main diagonal is 0; negative numbers denote the lower diagonals and positive numbers the upper ones.

The valid diagonal numbers lie in the closed interval [1 − a, b − 1]. In the example this interval is [−2, 1]. Elements whose number falls outside this interval are in the constant region and are not stored. Thus whether an element is inside or outside the band is found out with a single subtraction and two comparisons.

The elements are stored in the array band diagonal by diagonal, starting from the lowest diagonal. The position of an element has two parts: the start of its diagonal inside band and the order of the element within the diagonal.

  • Start of the diagonal. The start of each diagonal is kept in the array start (START). The array has a + b − 1 elements, that is, one per diagonal. Since an array index in C cannot be negative, the diagonal number is used shifted by a − 1: the start of diagonal number t is at start[t + a - 1]. In the example start = {0, 2, 5, 9}; diagonal −2 starts at 0, diagonal −1 at 2, the main diagonal at 5, and diagonal +1 at 9.
  • Order within the diagonal. The first element of a lower diagonal is in column 0; along the diagonal the column increases by one at each step. So in a lower diagonal the order is j. The first element of an upper diagonal is in row 0; the order is i. On the main diagonal i = j, so both give the same result.

The thought behind the design is this: examine everything as if it were constrained, and derive the access mechanism from those constraints. That the diagonal number is constant, that the diagonal lengths are n − |t|, and that the place of the first element is known are three constraints. Together they reduce an apparently complicated compression to a few arithmetic operations.

2.6.3Code trace: band_build()

The following function reads the elements of the band matrix from standard input. The input comes diagonal by diagonal, starting from the lowest diagonal. The function writes the start of each diagonal into start and places the elements in band. The function abs is in the header <stdlib.h>.

void band_build(int band[], int start[],
                int n, int a, int b) {
  int i, k, total = 0;   /* previous diagonals */
  if (n*(a+b-1) - a*(a-1)/2 - b*(b-1)/2 > MAX_SIZE) {
    printf("Out of memory!\n"); exit(-1);
  }
  for (i = 1 - a; i <= b - 1; i++) {  /* diagonal by diagonal */
    start[i + a - 1] = total;       /* diagonal start */
    for (k = 0; k <= n - abs(i) - 1; k++)
      scanf("%d", &band[start[i + a - 1] + k]);
    total += n - abs(i);
  }
}

The code works as follows, line by line:

  • total is the number of elements placed so far; that is, the start of the next diagonal.
  • First the number of elements to be stored is compared with MAX_SIZE. The formula is the element count obtained from the sum of the diagonal lengths.
  • The outer loop walks the diagonal number i from 1 − a to b − 1. Here i is not a row index but a diagonal number.
  • start[i + a - 1] = total records the start of the diagonal.
  • The inner loop reads the n − |i| elements of the diagonal: k goes from 0 to n − |i| − 1. Each value is written to band[start[i + a - 1] + k].
  • When the diagonal ends, total grows by the length of the diagonal.
Example 2.3

For n = 4, a = 3, b = 2, let the values of the matrix be d00 = 1, d01 = 2, d10 = 3, d11 = 4, d12 = 5, d20 = 6, d21 = 7, d22 = 8, d23 = 9, d31 = 10, d32 = 11, d33 = 12. The input given diagonal by diagonal is 6 10 · 3 7 11 · 1 4 8 12 · 2 5 9. The check passes with 4 · 4 − 3 − 1 = 12 ≤ MAX_SIZE. Table 2.14 gives the processing of each diagonal.

Table 2.14: Trace of the call band_build(band, start, 4, 3, 2).
Diagonal iLength n − |i|start[i + a − 1]Positions written ← value (element)total after
−2 (lower)2start[0] = 00 ← 6 (d20), 1 ← 10 (d31)2
−1 (lower)3start[1] = 22 ← 3 (d10), 3 ← 7 (d21), 4 ← 11 (d32)5
0 (main)4start[2] = 55 ← 1 (d00), 6 ← 4 (d11), 7 ← 8 (d22), 8 ← 12 (d33)9
1 (upper)3start[3] = 99 ← 2 (d01), 10 ← 5 (d12), 11 ← 9 (d23)12
0012c3c1c263c1006110234567891011band[]diagonal -2diagonal -1diagonal 0diagonal 1-20-101start[](index = diagonal no + a − 1) 001122c3c1345c267893c10111206110233741151647881292105119band[]diagonal -2diagonal -1diagonal 0diagonal 1-20-120519start[](index = diagonal no + a − 1)
Figure 2.11: Two moments of the construction. (a) The first diagonal (−2) has been placed: band[0] = 6, band[1] = 10, start[0] = 0. (b) All diagonals have been placed: band = {6, 10, 3, 7, 11, 1, 4, 8, 12, 2, 5, 9}, start = {0, 2, 5, 9}.

In the end total reaches 12; this is the value given by the element count formula. The arrays start and band printed by the driver program are the same as in the table. The function performs one scanf for each stored element, and the outer loop runs a + b − 1 times. The time is O(a + b + number of stored elements); since the number of diagonals cannot exceed the number of elements, this is O(number of stored elements). The extra memory is the a + b − 1 cells of the array start.

2.6.4Code trace: band_get()

The access function converts the pair (i, j) into a position inside band. For elements outside the band it returns two separate error codes, so that the upper and lower constant regions can be told apart.

int band_get(int i, int j, int n, int a,
              int b, int start[]) {
  if (i < 0 || j < 0 || i >= n || j >= n) {
    printf("Index overflow\n"); return -3;
  } else if (j - i >= 1) {         /* upper triangle */
    if (j - i < b)               /* valid diagonal */
      return start[j - i + a - 1] + i;
    else return -1;              /* upper constant region */
  } else if (i - j < a)          /* main / lower */
    return start[j - i + a - 1] + j;
  else
    return -2;                   /* lower constant region */
}

The logic of the function divides into four cases:

  • If one of the indices is outside the matrix, a message is printed and −3 is returned.
  • If j − i ≥ 1, the element is above the diagonal. If the diagonal number is less than b, the element is in a valid upper diagonal and the position is start[j - i + a - 1] + i. Otherwise the element is in the upper constant region; −1 is returned.
  • Otherwise the element is on the main diagonal or below it. If i − j < a, it is in a valid lower diagonal (main diagonal included) and the position is start[j - i + a - 1] + j.
  • If none of these holds, the element is in the lower constant region; −2 is returned.
Table 2.15: Four queries with band_get (n = 4, a = 3, b = 2, start = {0, 2, 5, 9}).
ElementDiagonal no. j − iDecisionReturnValue
d31−2i − j = 2 < 3: lower diagonalstart[0] + j = 0 + 1 = 1band[1] = 10
d1211 ≥ 1: upper; 1 < b = 2: validstart[3] + i = 9 + 1 = 10band[10] = 5
d0333 ≥ 1: upper; 3 ≥ b: outside the band−1c
d30−3i − j = 3 < 3 false: outside the band−2c
001122c3c1345c267893c10111206110233741151647881292105119band[]diagonal -2diagonal -1diagonal 0diagonal 1-20-120519start[](index = diagonal no + a − 1)
Figure 2.12: The query for d31. The element is the second element of diagonal −2; its position is start[0] + 1 = 1 and its value is 10.

In the driver program the four queries gave the same results. In addition, the access function was called for all pairs (i, j) and the matrix was rebuilt, with 0 written for elements outside the band. The resulting matrix is the same as the values in the example. In every case the function performs a constant number of comparisons and arithmetic operations; it has no loop that depends on the input. Its time is O(1).

Common mistake

Computing the position in an upper diagonal as start[…] + j. The first element of an upper diagonal is in row 0 but not in column 0; the upper diagonal number t starts at column t. The order must be counted from the row, not from the column. For d12 the faulty formula gives 9 + 2 = 11 and returns the value of d23 (9).

2.6.5The START array or a formula?

band_get runs in constant time because the diagonal starts were written beforehand into the array start. Without this array, every access would need a loop that adds up the lengths of the previous diagonals, and access would rise to O(a + b). start prevents this but has a price: it uses extra memory, and if the parameters of the matrix change it must be rebuilt. That also takes the program away from being dynamic.

A general design principle can be seen here. If it really improves performance, there is no harm in using a reasonable amount of extra memory. start is only a + b − 1 cells; next to the stored elements it is very small. Still, the same result can be had without any extra memory: the start of a diagonal can also be computed with a closed formula.

/* t: diagonal no (1-a..b-1); same as start[t+a-1] */
int diag_start(int t, int n, int a) {
  if (t <= 0)                     /* lower diagonals */
    return (t + a - 1) * n
           - (a * (a - 1) + t * (1 - t)) / 2;
  return (a - 1) * n - a * (a - 1) / 2  /* start at t=0 */
         + t * n - t * (t - 1) / 2;
}

The formula is derived in two cases.

  • Lower diagonals and the main diagonal (t ≤ 0). Before t there are the t + a − 1 diagonals numbered 1 − a, …, t − 1. Had all of them n elements, the total would be (t + a − 1) · n. The shortfalls are the absolute values of the numbers of these diagonals: (−t + 1) + … + (a − 1) = a(a − 1)/2 − t(t − 1)/2. In the code this expression is written as (a * (a - 1) + t * (1 - t)) / 2; the two forms are the same.
  • Upper diagonals (t > 0). The start of the main diagonal is found by putting t = 0 in the formula above: (a − 1) · n − a(a − 1)/2. To it are added the main diagonal and the lengths of the diagonals numbered 1, …, t − 1: n + (n − 1) + … + (n − t + 1) = t · n − t(t − 1)/2.

For n = 4 and a = 3, the values t = −2, −1, 0, 1 give 0, 2, 5, and 9 in turn; the same as start. A loop written for these notes counted 4,356 diagonal starts one by one for n ≤ 11 and all a, b ≤ n. No difference with the formula appeared. Access with the formula becomes diag_start(j - i, n, a) + (j > i ? i : j). This is also O(1); a few extra multiplications are made but no array is needed. Which to choose depends on whether memory or running time is more valuable.

2.6.6Evaluation order of the && operator

The conditions in the access functions are compound expressions such as i < 0 || i >= n || …. There is a common belief about such expressions. According to it, one cannot know whether the compiler scans the expression from left to right or from right to left. Therefore the second of the two forms below is safer.

/* 1 */ if (i < n && a[i] != 0) ...

/* 2 */ if (i < n)
          if (a[i] != 0) ...

This belief is wrong. The C standard guarantees left-to-right evaluation and short-circuit evaluation for the operators && and || (C99 §6.5.13–14). If the left side of && is false, the result is already false and the right side is never evaluated. In ||, if the left side is true, the right side is not evaluated. In the first form, if i < n is false, a[i] is never read. The two forms are equally safe; the first is a common and correct pattern in C. In the driver program the first form was tried on an array of three elements with i = n = 3; the condition came out false without a[3] being read.

The real traps are elsewhere. & (bitwise AND) and | do not short-circuit; if i < n & a[i] != 0 is written, both sides are evaluated and a[n] is read. Moreover, in an ordinary expression such as f(x) + g(x), the order in which the operands are evaluated is not specified by the standard. If f and g modify the same global variable, the result may differ from compiler to compiler. The order of evaluation is guaranteed only for &&, ||, ?:, and the comma operator.

2.7Structures and unions

All elements of an array have the same type. Records in the real world, however, consist of parts of different types: a student's number is an integer, the name is a character array, and the grade point average is a floating-point number. C defines such records with struct. A union, on the other hand, is a special kind of record in which several fields share the same memory. This section covers the two constructs, their appearance in memory, and the effect of alignment on size.

2.7.1struct

Definition 2.5

A struct (structure) is a C type that gathers fields of different types into a single record. The fields are laid out in memory in the order of declaration. A field is accessed as variable.field, and through a pointer to a structure as pointer->field.

typedef struct {
  char name[10];
  int age;
  float salary;
} person;

person p1, p2;
strcpy(p1.name, "Ali");
p1.age = 21;
p1.salary = 3500.0f;
p2 = p1;          /* copied field by field */
/* if (p1 == p2) -> DOES NOT COMPILE */

The code works as follows, line by line:

  • typedef struct { … } person; defines an anonymous structure and gives it the name person. typedef is a declaration that gives a new name to an existing type. This way one does not need to write struct every time a variable is declared: person p1, p2; suffices.
  • p1.name is a char array. Since arrays cannot be assigned to, the name is copied with strcpy. p1.age and p1.salary are assigned like ordinary variables. The f at the end of 3500.0f says that the constant is a float.
  • p2 = p1; copies the whole structure field by field. What is interesting is this: the name array inside the structure is copied as well. An array alone cannot be assigned to, but if the array is a field of a structure, the structure assignment carries it along.
  • p1 == p2 does not compile. C defines no equality operator for structures. The reason is alignment: there may be meaningless padding bytes between fields, and a byte-by-byte comparison could give a wrong result. To compare two structures, a function that compares field by field is written; char array fields are compared with strcmp.

Structures are often passed to functions by pointer. If a structure is passed by value, all its fields are copied; for large structures this is expensive. Passing by pointer copies only an address. After the definition person *p = &p2;, p->age and (*p).age give the same field. The parentheses are necessary because the operator . has higher precedence than *: *p.age means "what p.age points to" and does not compile. The arrow operator exists to shorten this notation.

In the driver program sizeof(person) came out as 20. The sum of the fields is 10 + 4 + 4 = 18 bytes. The 2 bytes in between come from alignment: the field age must start at an address that is a multiple of 4, and since name ends at byte 10, two padding bytes are added.

2.7.2Nested and self-referential structures

A field of a structure can be another structure. A structure can also carry a pointer field that points to an object of its own type.

typedef struct {
  int day, month, year;
} date;

typedef struct {
  char name[10];
  date birth;           /* nested structure */
} member;
/* m.birth.year = 2004; */

typedef struct list {
  char data;
  struct list *link;    /* self-reference */
} list;

The field birth of the structure member is a date structure. Nested fields are reached by applying the dot operator repeatedly: m.birth.year = 2004;. In the driver program sizeof(member) came out as 24: the 10-byte name, 2 padding bytes, and the 12-byte date.

The structure list is different. The type of the field link is struct list *, that is, a pointer to the structure's own type. Such structures are called self-referential structures. It is mandatory to give the structure a tag name (struct list) in the definition. The name list given with typedef is not yet defined until the declaration ends; the type of the field can only be written with the tag.

abcNULLdatalink
Figure 2.13: A linked list of three nodes built from self-referential structures. In the data field of each node sits a character, and in the link field the address of the next node; the link of the last node is NULL.

Figure 2.13 shows how three such structures are linked together. Each node holds the address of the next; the end of the chain is marked with NULL. In the driver program three nodes were built with the values a, b, c and printed in order with the loop for (q = &a1; q != NULL; q = q->link). This structure is the basis of linked lists, trees, and graphs. Unlike an array, the nodes do not have to be contiguous in memory; insertion in the middle is done by changing only a few links.

A structure cannot contain a field of its own type. In a definition such as struct list { char data; struct list next; }; the size of the structure would have to include its own size; that means an infinite size and it does not compile. A pointer to its own type, on the other hand, causes no problem, because the size of a pointer is independent of the size of the type pointed to (8 bytes on a 64-bit system). In the driver sizeof(list) came out as 16: the 1-byte character, 7 padding bytes, and the 8-byte pointer.

2.7.3union and alignment

Definition 2.6

A union is a C type all of whose fields share the same region of memory. The size of a union is that of its largest field (it may grow a little for alignment). Only one field at a time holds a valid value.

A union saves memory when a record needs to carry different information depending on its kind. In the example in the textbook, two different pieces of information are kept depending on a person's gender. Since the two fields are never needed at the same time, they can share the same memory.

typedef struct {
  enum { FEMALE, MALE } kind;   /* tag */
  union {
    int children;              /* if FEMALE */
    int beard;                 /* if MALE */
  } u;
} gender;

gender c;
c.kind = MALE;
c.u.beard = 0;   /* read only the field that matches the tag */

The type of the field kind is an enumeration type (enum): FEMALE and MALE are named constants taking the values 0 and 1. This field is a tag that shows which field of the union is valid. Such a structure is called a tagged union. The code sets the tag to MALE and then uses only the field that matches it, beard.

Keeping the tag correct is entirely the programmer's job. C does not track which field of the union was written last. If c.u.children is read after c.u.beard = 0; was written, the same four bytes are interpreted with another meaning. Here both fields are int, so the result is 0, but had the fields been of different types, a meaningless value would be read. The correct pattern is to look at the tag before every access to the union: if (c.kind == MALE) … c.u.beard …. In the driver program sizeof c.u came out as 4 and sizeof c as 8 bytes: the 4-byte tag and the 4-byte union. Had two separate fields been used, the structure would be 12 bytes.

The real factor that determines structure size is alignment. Processors read most types fastest from addresses that are multiples of their own size; some processors do not allow unaligned reads at all. The compiler therefore places each field at a suitable address multiple and, if necessary, inserts padding bytes in between. The total size of the structure is also rounded up to a multiple of the largest alignment requirement; this way every element in arrays of structures starts at the correct alignment.

{char c; int x; char d;} → 12cxxxxd{int x; char c; char d;} → 8xxxxcdempty box = padding byte
Figure 2.14: The effect of field order on structure size (4-byte int, a typical 32/64-bit compiler). At the top {char c; int x; char d;} takes 12 bytes, at the bottom {int x; char c; char d;} takes 8 bytes. The empty boxes are padding bytes.

Figure 2.14 compares two different orders of the same three fields. In the first order c sits at byte 0; because x must start at a multiple of 4, bytes 1, 2, 3 become padding and x occupies bytes 4–7. d sits at byte 8. The size of the structure must be a multiple of 4, so three padding bytes are added at the end: 12 in total. In the second order x occupies bytes 0–3, c byte 4, and d byte 5; two padding bytes are added at the end and the total is 8. The same data is held with one third less memory. In the driver program the sizes of these two structures came out as 12 and 8, and the position of x measured with offsetof came out as 4 in the first.

The practical rule is to order the fields from largest to smallest. The alignment rules depend on the compiler and the processor; the values given here are typical for common 32- and 64-bit systems. For structures written to a file or to the network as raw bytes, padding bytes cause portability problems. That is why in such cases the fields are written one by one.

2.7.4Code trace: class_avg()

Structures can be collected in arrays. The following function takes an array holding the student records of a class and returns the average of the grade point averages. Visiting all the elements of a data structure once each in a certain order is called traversal.

typedef struct {
  int id;
  char name[16];
  double avg;
} Student;

double class_avg(const Student s[], int n) {
  double sum = 0.0;
  int i;
  for (i = 0; i < n; i++)
    sum += s[i].avg;               /* . for a field */
  return n > 0 ? sum / n : 0.0;    /* empty class */
}

The code works as follows, line by line:

  • The parameter const Student s[] is a pointer; the array is not copied. const documents that the function will not modify the records and makes the compiler report an error if a field is written by mistake.
  • s[i].avg first finds record i (the address α + i · sizeof(Student)), then reads its avg field. In an array of structures the address formula applies as is; only the element size is the size of the structure.
  • n > 0 ? sum / n : 0.0 prevents division by zero in an empty class. With floating-point numbers, division by zero does not stop the program but produces infinity or NaN; this value silently spreads to later computations.
s[0]101"Ada"3.2idnameavgs[1]102"Can"2.6idnameavgs[2]103"Ece"3.5idnameavg
Figure 2.15: An array of structures made of three student records. The records sit one after another in memory; each record is sizeof(Student) bytes.
Table 2.16: Trace of the call class_avg(s, 3) with the three records of Figure 2.15.
ii < ns[i].avgsum after
00 < 3, true3.23.2
11 < 3, true2.65.8
22 < 3, true3.59.3
33 < 3, false—the loop ends; n > 0, return 9.3 / 3 = 3.10

The function visits each record once; its time is Θ(n) and its extra memory O(1). In the driver program the result was printed as 3.10 with the format %.2f. The exact values of the intermediate sums are 3.2000000000000002, 5.8000000000000007, and 9.3000000000000007. Decimal numbers such as 3.2 cannot be represented exactly in binary, and small rounding errors accumulate. That is why floating-point results are not compared with ==; they are either printed with a given number of digits or compared within a small tolerance.

The structure Student also shows the effect of alignment. The 4-byte id and the 16-byte name come to 20 bytes. A double must start at a multiple of 8; so 4 padding bytes are added and avg starts at byte 24. The total size is 32 bytes. In the driver program offsetof(Student, avg) came out as 24 and sizeof(Student) as 32.

2.8Strings

Text is one of the kinds of data that programs process most. Many languages offer a separate type for text. In C, text is an ordinary char array that obeys a special rule. This simplicity gives speed, but when used carelessly it is also the source of the most common security holes.

2.8.1A char array terminated by '\0'

Definition 2.7

In C a string is a char array terminated by the character '\0', whose value is zero. This character is called the null character. The length of the string is the number of characters before the first '\0'.

char s[] = "dog";      /* 4 bytes: d o g \0 */
char t[10];
char *p = "dog";       /* read-only constant */

strlen(s)   /* 3 : up to the \0 */
sizeof s    /* 4 : size of the array */

strcpy(t, s);                 /* is t big enough? */
snprintf(t, sizeof t, "%s!", s);   /* safe */
if (strcmp(s, "dog") == 0) ...     /* not == ! */
0'd'1'o'2'g'3'\0's
Figure 2.16: The declaration char s[] = "dog"; in memory: three characters and the terminating '\0', 4 bytes in all.

The code works as follows, line by line:

  • char s[] = "dog"; allocates an array of four bytes. The compiler copies the string and adds '\0' at the end; its size is therefore 4, not 3 (Figure 2.16).
  • char t[10]; is an empty area of ten characters; its contents are as yet indeterminate.
  • char *p = "dog"; does not allocate an array. p points to a string constant in the read-only region of the program. Writing p[0] = 'D'; is undefined behavior and on most systems crashes the program. That is why such pointers should be declared const char *p; then the compiler catches an attempt to write.
  • strlen(s) gives 3 and sizeof s gives 4. strlen counts characters up to the '\0'; sizeof is the memory the array occupies.
  • strcpy(t, s) copies s to t together with its terminator. strcpy does not know the size of the destination; if t is not big enough, it overruns the end. Here 10 bytes are enough for a string of 4 bytes.
  • snprintf(t, sizeof t, "%s!", s) takes the size of the destination as its second parameter, writes at most sizeof t - 1 characters, and always puts a '\0' at the end. Overflow is impossible. In the driver the new value of t was dog!.
  • strcmp(s, "dog") == 0 compares the contents of two strings character by character. Had s == "dog" been written, addresses and not contents would be compared and the result would most likely be wrong.

The header <string.h> offers a set of functions for strings. Table 2.17 summarizes the most used ones. All these functions recognize the end of a string by the '\0'. If an array without a terminator is given to these functions, they keep reading until they find an accidental zero further on in memory.

Table 2.17: Frequently used <string.h> functions.
FunctionJobTime (n: string length)
strlenlength (excluding '\0')O(n)
strcpy / strncpycopyO(n)
strcatappendO(n + m); the end of the destination is searched for first
strcmpcompare in dictionary order; 0 if equal, negative if the first is smaller, positive if largerO(n)
strchr / strstrsearch for a character / substring; NULL if not foundO(n) / O(n · m) in a simple implementation

strncpy has a trap. If the source is longer than the given limit, strncpy does not put a '\0' in the destination; the result is not a string. For a safe copy, therefore, snprintf is preferred, or strncpy with the limit kept one smaller and a '\0' written by hand afterwards.

Common mistake

Not reserving room for the terminator in a string. char name[3] = "Ali"; compiles in C (it does not in C++), but the array holds only three characters and the '\0' is left outside. strlen(name) or printf("%s", name) keeps reading past the end of the array. A string of n characters always needs n + 1 bytes. The same holds for dynamic allocation: malloc(strlen(s) + 1).

2.8.2Code trace: length()

The following function writes out explicitly what strlen does. It advances a pointer until it reaches the '\0' and returns how far it has moved from the start.

size_t length(const char *s) {
  const char *p = s;
  while (*p != '\0')     /* up to the terminator */
    p++;
  return (size_t)(p - s);  /* pointer difference */
}

/* length("data") */

p initially points to the same place as s. In each round the loop compares *p with the terminator; if different, it advances p by one character (1 byte). When the loop ends, p points to the terminator. The difference of the two pointers, p - s, is the number of elements between them; that is the length of the string. The difference is of type ptrdiff_t and is returned converted to size_t.

Table 2.18: Trace of the call length("data").
Roundp - s*p*p != '\0'Action
10'd'truep++
21'a'truep++
32't'truep++
43'a'truep++
54'\0'falsethe loop ends; return 4
0'd'1'a'2't'3'a'4'\0's▲ pp − s = 4
Figure 2.17: When the loop ends, p points to the terminator; p − s = 4.

To find the length the string is scanned from beginning to end: the time is Θ(n). Unlike structures such as arrays, whose length is kept separately, the length of a C string is recomputed every time. This leads to a commonly seen inefficiency:

for (i = 0; i < strlen(s); i++)   /* strlen on every round! */
    ...

The loop condition is recomputed in every round, and each computation scans n characters. For n rounds a total of n · n characters are read; the loop becomes O(n2). In a text of a million characters this means a trillion reads instead of a million. The right way is to compute the length once before the loop: size_t len = strlen(s); for (i = 0; i < len; i++). If the loop body does not modify the string, good compilers may do this transformation themselves, but one should not rely on it.

2.9Matrix operations

Two-dimensional arrays are used most in matrix computations. This section examines matrix addition and multiplication; in particular it derives the exact step count of multiplication. In the examples N is a constant defined at compile time, and matrices are passed in the form int a[][N]. Writing the second dimension is mandatory, because the address computation needs the row length.

2.9.1Matrix addition

In the sum of two matrices of the same size, each cell is the sum of the cells at the same position in the two matrices. For m × N matrices the code consists of two nested loops.

void add(int a[][N], int b[][N], int c[][N], int m) {
    int i, j;
    for (i = 0; i < m; i++)
        for (j = 0; j < N; j++)
            c[i][j] = a[i][j] + b[i][j];
}

The body of the inner loop runs once for each cell, m · N times in all. The loop tests are also proportional to this number. The time is Θ(mN); for n × n square matrices, Θ(n2). No extra memory is needed apart from the result matrix. Since each cell is read once and written once, there is no faster addition algorithm: every cell of the input must be looked at at least once. In the driver the sum of two 2 × 3 matrices was tried and the expected result was obtained.

2.9.2Code trace: mult()

Let A and B be two n × n matrices. Each cell of the product C = AB is the inner product of a row of A with a column of B:

cij = Σk=0n−1 aik · bkj
#define N 2
void mult(int a[][N], int b[][N], int c[][N]) {
  int i, j, k;
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++) {
      c[i][j] = 0;
      for (k = 0; k < N; k++)
        c[i][j] += a[i][k] * b[k][j];
    }
}

The outer two loops walk over the cells of the result matrix. Each cell is first zeroed, then the innermost loop adds up n products. For A = [[1, 2], [3, 4]] and B = [[5, 6], [7, 8]] the trace is given in Table 2.19.

Table 2.19: Trace of the function mult for N = 2.
ijkOperationc[i][j] after
0000 + a[0][0] · b[0][0] = 1 · 55
0015 + a[0][1] · b[1][0] = 5 + 2 · 719
0100 + a[0][0] · b[0][1] = 1 · 66
0116 + a[0][1] · b[1][1] = 6 + 2 · 822
1000 + a[1][0] · b[0][0] = 3 · 515
10115 + a[1][1] · b[1][0] = 15 + 4 · 743
1100 + a[1][0] · b[0][1] = 3 · 618
11118 + a[1][1] · b[1][1] = 18 + 4 · 850
a1234×b5678=c19224350
Figure 2.18: The product of 2 × 2 matrices: C = [[19, 22], [43, 50]]. The innermost line ran N3 = 8 times.

The driver program printed the result as [[19, 22], [43, 50]]. The innermost assignment ran eight times, that is, N3 times. As n grows, this number grows as a cube; when the matrix size doubles, the work grows eightfold.

2.9.3Step count, rectangular matrices, and the transpose

The exact step count of the multiplication is found by counting how many times each line runs. The condition of a for loop is tested one more time than the body runs: the last test comes out false and the loop ends. Table 2.20 gives the count line by line.

Table 2.20: Step count of mult on n × n matrices.
LineTimes executed
for (i …) conditionn + 1
for (j …) conditionn(n + 1)
c[i][j] = 0n2
for (k …) conditionn2(n + 1)
c[i][j] += …n3
Total2n3 + 3n2 + 2n + 1

The total is found by adding the terms (n + 1) + (n2 + n) + n2 + (n3 + n2) + n3. The dominant term is 2n3; the time is Θ(n3). The number of multiplications performed is exactly n3. In a version with a counter written for these notes, the steps were counted for n = 1 to 9 and came out the same as the formula (for example 33 at n = 2 and 88 at n = 3).

Matrices need not be square. The product of an m × n matrix and an n × p matrix has size m × p; that is, it has m · p cells. Each cell is the sum of n products. The total number of multiplications and the time are Θ(m · n · p). This result also explains why the order of multiplication matters in a chain of matrices. (AB)C and A(BC) give the same result but may need very different numbers of multiplications.

The transpose of a matrix is the matrix with its rows and columns exchanged: aij and aji are swapped. For a square matrix this can be done without an extra array, in place.

void transpose(int a[][N], int n) {
    int i, j, t;
    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++) { /* upper triangle only */
            t = a[i][j];
            a[i][j] = a[j][i];
            a[j][i] = t;
        }
}

The inner loop starts at j = i + 1; only the cells above the diagonal are visited. Each swap exchanges an upper triangle cell with its counterpart in the lower triangle. Had the loop started at j = 0, every pair would be swapped twice: the first swap takes the transpose and the second reverses it, and the matrix would end up unchanged. The diagonal cells stay in place. The number of swaps is (n − 1) + (n − 2) + … + 0 = n(n − 1)/2; the time is Θ(n2) and the extra memory is a single temporary variable. In the driver a 3 × 3 matrix was transposed with three swaps. Transposing a non-square matrix in place is much harder, because the row length changes and the elements move around the array in cycles.

2.10Complexity summary

Table 2.21 gives the time and extra memory costs of the operations in the chapter together. The times are for the worst case; amortized ones are noted separately.

Table 2.21: Complexity of the operations in the chapter.
OperationTimeExtra memory
Access A[i]; n-dimensional address (n − 1 multiplications)O(1)O(1)
Append to a dynamic array (doubling)amortized O(1), worst case O(n)capacity ≤ 2 · size
Insertion / deletion in the middleO(n)O(1)
Access to a lower triangular / band matrixO(1)n(n + 1)/2 / band elements
band_build, lower_readO(stored elements)START: a + b − 1
strlen / lengthO(n)O(1)
Matrix addition (m × n)O(mn)O(1)
Matrix multiplication (n × n)O(n3)O(1)

The table has a common lesson: when the layout in memory is known, access reduces to a formula and is done in constant time. In one-dimensional arrays, multidimensional arrays, and triangular and band matrices alike, the same question has been asked: "how many elements are there before the sought element?" The operations that raise the cost are those that move elements: insertion in the middle, growing, and scanning.

2.11Common mistakes

Most of the mistakes in this chapter arise from a deliberate choice of C: the language does not check indices, the result of memory allocation, or the end of a string. In the list below each mistake is given together with its correct pattern.

  1. Writing outside the array bounds. Accessing a[n] is undefined behavior and C does not check it. The last index of an array of n elements is n − 1; the loop condition is written i < n.
  2. Writing a = realloc(a, …). On failure the address of the old block is lost and the block leaks. The result is first taken into a temporary variable and, if it is not NULL, assigned to the real pointer.
  3. Confusing sizeof(int *) with sizeof(int); using sizeof a on a parameter. The first allocates memory of the wrong size. In the second, since the parameter is a pointer, the size of the pointer comes out, not that of the array. The pattern malloc(n * sizeof *a) and passing the length as a separate parameter prevent these two mistakes.
  4. Releasing only the pointer array of a two-dimensional dynamic array without freeing the rows. All the rows leak. First every x[i] and then x is released.
  5. Confusing the row-major and column-major formulas; forgetting the element size (s). The row-major formula uses the row length (u1); for a byte address the element count is multiplied by s.
  6. Using == on strings or not reserving room for '\0'. == compares addresses; use strcmp for contents. A string of n characters needs n + 1 bytes.
  7. Not taking alignment into account. The size of a structure can be larger than the sum of its fields. The size is always obtained with sizeof, never added up by hand.

2.12Summary

  • At the abstract level an array is a mapping made of ⟨index, value⟩ pairs; its operations are Create, Retrieve, and Store. In the C implementation the elements sit contiguously and the address of A[i] is computed as α + i · s in O(1). Insertion and deletion in the middle need shifting and are therefore O(n).
  • C does not check indices; accessing a[n] is undefined behavior. An array name turns into the address of the first element in most expressions: list[i] ≡ *(list + i). Pointer arithmetic counts elements, not bytes. An array name cannot be assigned to; an array passed to a function turns into a pointer, and its length is sent separately.
  • malloc allocates a block from heap memory; its return is checked for NULL, the block is freed when the work is done, and NULL is assigned to the pointer. The pattern sizeof *a gives the right size even when the type changes.
  • A dynamic array doubles its capacity when it is full. In n appends the total number of copies is less than 2n; the amortized cost per append is O(1). Growing by a fixed increment means O(n2) copies. The result of realloc is first taken into a temporary variable.
  • A two-dimensional dynamic array consists of an array of pointers and separate row blocks (int **). The rows need not be contiguous; when releasing, first the rows and then the pointer array are freed.
  • C uses row-major order: &x[i][j] = α + (i · u1 + j) · s. In column-major order it is α + (j · u0 + i) · s. In an n-dimensional array the address is α + Σ ij aj; Horner's method computes it with n − 1 multiplications. The outermost dimension does not enter the address computation.
  • A lower triangular matrix is stored with n(n + 1)/2 elements; the position of aij is i(i + 1)/2 + j. The access function returns error codes (−1, −2) that do not intersect the valid positions.
  • In a band matrix the difference j − i of elements on the same diagonal is constant. The number of elements is n(a + b − 1) − a(a − 1)/2 − b(b − 1)/2. The diagonal starts are kept in the START array or computed with a closed formula; with either route access is O(1).
  • && and || are evaluated left to right and with short-circuiting; i < n && a[i] != 0 is safe. & and | do not short-circuit.
  • struct gathers fields of different types; it can be assigned but cannot be compared with ==. A self-referential structure is the basis of linked structures. The fields of a union share the same memory; the valid field is tracked with a tag. Alignment adds padding bytes; a structure can be made smaller by ordering the fields from largest to smallest.
  • A C string is a char array terminated by '\0'; n characters need n + 1 bytes. strlen is O(n); if it is called in a loop condition, the loop becomes O(n2). Contents are compared with strcmp; snprintf is used against overflow.
  • Matrix addition is Θ(mn), multiplication of square matrices is Θ(n3) with 2n3 + 3n2 + 2n + 1 steps, and multiplication of rectangular matrices is Θ(mnp). The in-place transpose of a square matrix takes n(n − 1)/2 swaps.

2.13Key terms

  • abstract data type (ADT)
  • implementation
  • array
  • mapping
  • index
  • pointer
  • pointer arithmetic
  • pointer to pointer
  • null pointer (NULL)
  • dangling pointer
  • sizeof
  • dynamic memory allocation
  • heap memory
  • malloc / calloc / realloc / free
  • memory leak
  • dynamic array
  • capacity
  • doubling
  • amortized analysis
  • multidimensional array
  • row-major order
  • column-major order
  • Horner's method
  • lower triangular matrix
  • band matrix
  • short-circuit evaluation
  • struct
  • typedef
  • arrow operator (->)
  • self-referential struct
  • union (C)
  • tagged union
  • enumeration (enum)
  • alignment
  • traversal
  • string
  • null character ('\0')
  • transpose
  • in place

2.14Test Yourself

  1. The array int a[6]; starts at address 1000 and sizeof(int) = 4. What address do &a[4] and a + 4 give? Which element is *(a + 4)?

    Answer

    Both give the address 1000 + 4 · 4 = 1016. Since pointer arithmetic counts elements, a + 4 is 4 elements ahead, that is 16 bytes, not 4 bytes. *(a + 4) is a[4] itself.

  2. The array short s[4][7]; starts at address 500 and sizeof(short) = 2. What is &s[2][5] in row-major order? What would it be if the array were stored column-major?

    Answer

    Row-major: before the element there are 2 full rows (2 · 7 = 14 elements) and 5 elements in its row; 500 + 19 · 2 = 538. Column-major: first 5 full columns (5 · 4 = 20 elements) and 2 elements in its column; 500 + 22 · 2 = 544. The row-major formula uses the row length (7), and the column-major formula the column length (4).

  3. In the array int A[3][4][5];, what is the relative position of A[2][1][3] found with Horner's method? How many multiplications are made in the computation?

    Answer

    t = 2; t = 2 · 4 + 1 = 9; t = 9 · 5 + 3 = 48. Two multiplications are made (n − 1, n = 3). The first dimension, 3, does not enter the computation at all. In a real C array &A[2][1][3] - &A[0][0][0] is also 48.

  4. A 6 × 6 lower triangular matrix is stored in an array LOW. How many elements does the array have? At which position is a52? What does lower_get(2, 5, 6) return?

    Answer

    6 · 7/2 = 21 elements. a52: 5 · 6/2 + 2 = 17. lower_get(2, 5, 6) asks for a25 in the upper triangle; since 2 < 5, −1 is returned (the value is 0 and is not stored).

  5. How many elements does a band matrix with n = 5, a = 2, b = 2 (a tridiagonal matrix) hold? What is the START array? At which positions of the array band are d34 and d43?

    Answer

    5 · 3 − 1 − 1 = 13 elements. The diagonals are −1, 0, 1 with lengths 4, 5, 4; START = [0, 4, 9]. d34: diagonal 4 − 3 = 1, an upper diagonal; position start[1 + 1] + i = 9 + 3 = 12. d43: diagonal −1, a lower diagonal; position start[0] + j = 0 + 3 = 3.

  6. If 20 elements are appended to a dynamic array that starts empty and doubles its capacity, how many copies are made in total and what is the final capacity? What would the number of copies be if the capacity were increased by 1 each time?

    Answer

    Enlargements happen when 1, 2, 4, 8, and 16 elements fill the array: 1 + 2 + 4 + 8 + 16 = 31 copies, final capacity 32. This is less than 2 · 20 = 40. With growth by 1, 0 + 1 + … + 19 = 190 copies are made.

  7. How many bytes does struct { char a; int b; char c; double d; } take on a typical 64-bit system? To what size can it be reduced by reordering the fields?

    Answer

    a at byte 0, 3 padding, b at 4–7, c at byte 8, 7 padding, d at 16–23: 24 bytes in total. In the order { double d; int b; char a, c; } the 8 + 4 + 1 + 1 = 14 bytes get 2 bytes of padding and the size becomes 16. Both values were measured in the driver program.

  8. About how many characters does the loop for (i = 0; i < strlen(s); i++) if (s[i] == ' ') count++; read on a string of 10,000 characters? How is the loop fixed?

    Answer

    The condition is recomputed in every round and each strlen scans 10,000 characters. In 10,001 tests about 108 characters are read; the loop is O(n2). The length is computed once before the loop (size_t len = strlen(s);), or the loop is written with the condition s[i] != '\0'; both are O(n).

  9. A 2 × 3 matrix is multiplied by a 3 × 4 matrix. How many cells does the result have and how many multiplications are made?

    Answer

    The result is 2 × 4, that is, it has 8 cells. Each cell is the sum of 3 products: 2 · 3 · 4 = 24 multiplications.

  10. What does the function size_t f(int a[10]) { return sizeof a; } return on a 64-bit system? Why?

    Answer

    It returns 8. Even though the parameter is written as int a[10], the compiler treats it as int *a; sizeof a is the size of the pointer, not 40. The length of the array must be sent to the function as a separate parameter. Compilers issue a warning for this usage.

2.15Further reading

  • E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Chapter 2: the array ADT, structures, polynomial and sparse matrix representations, address computation for multidimensional arrays, and strings; this is the textbook these notes follow.
  • B. W. Kernighan and D. M. Ritchie, The C Programming Language (2nd ed.), Chapters 5–6: the relationship between pointers and arrays, arrays of pointers, multidimensional arrays, and structures, in the words of the designers of the language.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed.), Section 17.4: analyzes the expansion and contraction of dynamic tables in an amortized way with the aggregate, accounting, and potential methods.

2.16References

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009.
  2. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Silicon Press, 2008.
  3. B. W. Kernighan, D. M. Ritchie, The C Programming Language, 2nd ed., Prentice Hall, 1988.

Related pages: Chapter 2 slides · © Sercan Külcü. All rights reserved.