Arrays and address calculation

Learning outcomes

Distinguish logical length from capacity, trace insertion and deletion, and calculate one- and two-dimensional array addresses.

3.1 Contiguous elements and valid indices

An array is a contiguous sequence of elements of one type. In int a[5], valid indices are 0 through 4. The declaration reserves storage for five integers; it does not imply that an application's sequence currently contains five meaningful records.

Keep capacity and logical length separate. If capacity is 8 and length is 5, operations act on indices 0 through 4 while three slots remain available for insertion. C does not automatically check either boundary.

int a[5] = {23, 12, 7};

Here all five elements exist; the last two are initialised to zero. sizeof a measures the complete local array in bytes. It is 5 * sizeof(int), not necessarily 10 or 20 bytes. An uninitialised automatic array does not receive these zero values.

3.2 Insert without overwriting unread values

Insert 18 at position 2 in {23, 12, 7, 45} with capacity 6.

Shift right to left so that a source value is not destroyed before it is copied. A valid insertion position satisfies 0 ≤ pos ≤ n. The position n appends. Reject the operation if n == capacity.

if pos < 0 or pos > n or n == capacity: report failure
for i = n down to pos + 1:
    a[i] = a[i − 1]
a[pos] = value
n = n + 1

Deletion requires pos < n. Save the removed value if needed, shift later elements one place to the left, and decrease n. The old final slot may still contain a value, but it is outside the logical sequence. Deleting an element does not shrink the allocated C array.

3.3 Operation costs

A growable array adds an allocation policy. Occasional reallocation is expensive; amortised constant-time append requires a suitable growth strategy and is not a property of a fixed C array.

3.4 Address calculation

For lower bound L, element size w and base address B, the conceptual address is B + (i − L)w. C arrays have lower bound zero. If B = 1000 and w = 4, index 3 has address 1012. These addresses are illustrative, not a promise about an actual program.

For a rectangular array with R rows and C columns in row-major order:

address(A[i][j]) = B + ((i − Lr) × C + (j − Lc)) × w

For int a[3][4], the element a[2][1] is 9 elements from the base. If w = 4 and B = 1000, its illustrative address is 1036. C uses row-major storage for true multidimensional arrays. An array of pointers need not form one contiguous rectangle.

Column-major order instead uses B + ((j − Lc)R + (i − Lr))w. Do not apply the column-major formula to a C rectangular array.

Practice

1. Delete position 1 from {23, 12, 18, 7, 45}. Show every shift.
2. Explain the difference between int a[8] = {0}; and a logical sequence of length zero.
3. For a row-major 4 × 5 array, B = 2000 and w = 8, find the address of element [2][3].
4. Test array insertion at the beginning, at the end, into an empty sequence and into a full sequence.

/* C11. teaching example. Logical length is separate from capacity. */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

static bool insert(int a[], size_t *n, size_t cap, size_t pos, int value)
{
    if (*n > cap || *n == cap || pos > *n) return false;
    for (size_t i = *n; i > pos; --i) a[i] = a[i - 1];
    a[pos] = value;
    ++*n;
    return true;
}
static bool erase(int a[], size_t *n, size_t pos, int *removed)
{
    if (pos >= *n) return false;
    *removed = a[pos];
    for (size_t i = pos; i + 1 < *n; ++i) a[i] = a[i + 1];
    --*n;
    return true;
}
/* Return n if the value is absent. */
static size_t linear_search(const int a[], size_t n, int key)
{
    for (size_t i = 0; i < n; ++i) if (a[i] == key) return i;
    return n;
}
/* Precondition: a[0..n) is in nondecreasing order. Returns first match. */
static size_t binary_search(const int a[], size_t n, int key)
{
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (a[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return lo < n && a[lo] == key ? lo : n;
}
int main(void)
{
    int a[5] = {10, 30, 40}, removed = 0;
    size_t n = 3;
    assert(insert(a, &n, 5, 1, 20));
    assert(insert(a, &n, 5, 4, 50));
    assert(!insert(a, &n, 5, 5, 60));
    assert(!insert(a, &n, 5, 6, 60));
    assert(binary_search(a, n, 30) == 2);
    assert(binary_search(a, n, 99) == n);
    assert(linear_search(a, n, 50) == 4);
    assert(erase(a, &n, 2, &removed) && removed == 30);
    assert(!erase(a, &n, 4, &removed));
    printf("After deletion:");
    for (size_t i = 0; i < n; ++i) printf(" %d", a[i]);
    putchar('\n');
    int duplicate[] = {1, 2, 2, 2, 3};
    assert(binary_search(duplicate, 5, 2) == 1);
    assert(binary_search(a, 0, 10) == 0);
    assert(linear_search(a, 0, 10) == 0);
    n = 0;
    assert(!erase(a, &n, 0, &removed));
    assert(insert(a, &n, 5, 0, -1) && a[0] == -1);
    puts("arrays/search tests passed");
    return 0;
}