Chapter 08 of 24

8. Arrays

A row of values under one name

An array holds several values of the same type in a fixed-size sequence. If you have five quiz scores, one array is usually easier to work with than five unrelated variable names.

  1. Choose the element type and number of elements, for example int scores[5];.
  2. Remember that the first position is index 0, so five elements have indexes 0 through 4.
  3. Use a loop to visit each valid index, initialize the element, and perform the desired calculation.

An array does not automatically check that an index is in range. Before reading or writing an element, make sure the index is at least zero and smaller than the array length.

An array stores a fixed number of elements of one type in consecutive memory.

int main(void)
{
    int scores[4] = {82, 91, 77, 95};
    scores[0] = 85;
    return scores[0] == 85 ? 0 : 1;
}

Array indices start at zero. For an array of length n, valid indices are
0 through n - 1. C does not automatically check array bounds; an out-of-
bounds access is undefined behavior.

The array length is not automatically carried with the array when passed to a
function. Pass the length separately:

#include <stddef.h>

int sum(const int values[], size_t length)
{
    int total = 0;
    for (size_t i = 0; i < length; ++i) {
        total += values[i];
    }
    return total;
}

Include <stddef.h> when using size_t directly. const here says the
function will not modify the elements through values.

Multidimensional arrays, such as int grid[3][4], are arrays of arrays. Their
storage is contiguous in row-major order. Learn how dimensions affect function
parameters before passing them around.

Array initialization and traversal

An initializer can provide every element or only an initial prefix; any
remaining elements of an aggregate initializer are set to zero:

int counts[5] = {0};

The number of elements in an actual array can be computed in the same scope
where it is still an array:

#include <stddef.h>

int main(void)
{
    int scores[] = {82, 91, 77, 95};
    size_t length = sizeof scores / sizeof scores[0];
    return length == 4 ? 0 : 1;
}

This technique does not work after the array has been passed to a function:
there the parameter is adjusted to a pointer, so its sizeof is the pointer
size. Pass the length explicitly as shown earlier.

For a two-dimensional array, both row and column indices need valid bounds.
For example, int grid[2][3] has two rows and three columns, with valid
indices grid[0][0] through grid[1][2]. A function parameter can specify
the column count, such as int grid[][3]; the compiler needs that inner
dimension to calculate element addresses.

Arrays cannot be assigned to each other with = after declaration. Copy
elements in a loop or use an appropriate library operation when the element
types and sizes make that safe. Avoid using memcpy on overlapping ranges;
memmove is intended for overlap.

Checkpoint: For an array of length four, list every valid index. Explain
why an array function needs both a pointer-like parameter and a length.

Array algorithms

Most array algorithms are loops with a carefully maintained index or
invariant. A search can return the index of a match, or a sentinel such as
length to mean “not found”:

#include <stddef.h>

size_t find_int(const int values[], size_t length, int target)
{
    for (size_t i = 0; i < length; ++i) {
        if (values[i] == target) {
            return i;
        }
    }
    return length;
}

Because valid indices are strictly less than length, length is an
unambiguous “not found” result. The caller must still check it before using it
as an index. This function reads zero elements safely when length is zero,
provided the caller follows the contract and does not expect access to an
element.

To find a minimum, keep the index of the smallest value seen so far. For an
empty array, there is no minimum, so the interface must report failure:

#include <stdbool.h>
#include <stddef.h>

bool min_int(const int values[], size_t length, int *minimum)
{
    if (length == 0 || values == NULL || minimum == NULL) {
        return false;
    }

    int smallest = values[0];
    for (size_t i = 1; i < length; ++i) {
        if (values[i] < smallest) {
            smallest = values[i];
        }
    }

    *minimum = smallest;
    return true;
}

The loop starts at 1 because element zero initializes the current minimum.
This pattern—initialize from the first valid element, then process the
remaining elements—avoids inventing a sentinel that may not be valid for all
types.

Sorting and searching

Linear search checks values one at a time and works on unsorted data. Binary
search repeatedly halves a sorted range and takes logarithmic time, but only
when the array is sorted consistently with the search comparison. Insertion
sort is a useful first sorting algorithm: grow a sorted prefix by inserting
each new value at the right position. It is straightforward and works well
for small arrays, though its worst-case running time grows quadratically.
Later, study merge sort and quicksort, their trade-offs, and the behavior of
library sorting routines.

Before implementing an algorithm, specify whether it changes the input,
whether duplicate values are allowed, what happens for an empty array, and
how an invalid range is reported. Test lengths 0, 1, and 2 before testing a
large input.

Insertion sort in C:

#include <stddef.h>

void insertion_sort(int values[], size_t length)
{
    for (size_t i = 1; i < length; ++i) {
        int key = values[i];
        size_t position = i;

        while (position > 0 && values[position - 1] > key) {
            values[position] = values[position - 1];
            --position;
        }

        values[position] = key;
    }
}

At the start of each outer iteration, the prefix before i is sorted. The
inner loop shifts larger elements right until the saved key fits. The
algorithm is stable when equal elements are not shifted past one another;
the strict > comparison preserves their original order.

A lower-bound binary search finds the first position whose value is not less
than the target. Using a half-open range [low, high) avoids unsigned
underflow from a high = length - 1 initialization:

#include <stddef.h>

size_t lower_bound_int(const int values[], size_t length, int target)
{
    size_t low = 0;
    size_t high = length;

    while (low < high) {
        size_t middle = low + (high - low) / 2;
        if (values[middle] < target) {
            low = middle + 1;
        } else {
            high = middle;
        }
    }

    return low;
}

The result is an insertion position in the range from zero through length.
It is a match only when it is less than length and values[result] == target.
The array must already be sorted in ascending order.

Multidimensional arrays in functions

A two-dimensional array is not a pointer-to-pointer. For int matrix[2][3],
each row is an array of three integers, laid out consecutively. A parameter
such as int matrix[][3] is adjusted to a pointer to an array of three
integers. A int ** instead points to a pointer, which may refer to a
separately allocated row or another layout entirely. Do not interchange
these types.

#include <stddef.h>

int matrix_sum(size_t rows, const int matrix[][3])
{
    int total = 0;
    for (size_t row = 0; row < rows; ++row) {
        for (size_t column = 0; column < 3; ++column) {
            total += matrix[row][column];
        }
    }
    return total;
}

int main(void)
{
    const int values[2][3] = {{1, 2, 3}, {4, 5, 6}};
    return matrix_sum(2, values) == 21 ? 0 : 1;
}

The column count is part of the parameter type. This example assumes the
sum fits in int; production code must define a range or overflow policy.

For a runtime-selected row and column count, common choices include a
contiguous one-dimensional allocation with an explicit indexing formula, or
a pointer table whose rows are allocated separately. The contiguous form
often has simpler ownership and better locality; the pointer-table form can
support rows of different lengths but needs more allocations and cleanup.

Array traps to avoid 

#include <stddef.h>
#include <stdio.h>

int main(void)
{
    int values[] = {2, 4, 6};
    size_t length = sizeof values / sizeof values[0];

     // Each index is strictly less than length. 
    for (size_t i = 0; i < length; ++i) {
        printf("%d\n", values[i]);
    }
    return 0;
}

The loop condition is <, not <=.

Exercises: find the minimum and maximum in an array; reverse an array;
add two small matrices; implement linear search; sort a short array and test
empty, one-element, duplicate, and already-sorted inputs.

Suggested topics

0% read