Data at Scale

This chapter moved the course from values to collections: one name for many elements, grids behind one declaration, and the first real algorithms. It also sharpened the course's central safety theme, because arrays are where undefined behaviour stops being a curiosity and becomes the daily hazard. The recap.

One Dimension

int a[N] declares N elements indexed 0 to N-1; ANSI C sizes come from #define constants, never variables, and never const variables. Brace lists initialize in order and zero the remainder, giving the = {0} idiom; a bare automatic array holds indeterminate values. Too many initializers is the opposite case and gets no such kindness: it is a diagnosed constraint violation, a hard error under this course's settings, and the only array mistake here that cannot survive to run time. Elements sit contiguously, so indexing is arithmetic, sizeof(a) is the whole object, and sizeof(a) / sizeof(a[0]) counts elements.

The bounds rule with everything hanging on it: any index outside 0 to N-1 is undefined behaviour, unchecked by the language. The loop discipline i < n mirrors the declaration; the input discipline validates a count against capacity before the read loop, because an oversized count makes the reading itself the overflow. And when the index is computed from data rather than counted by a loop, as in the frequency-table idiom group[mark / 10]++, validating the value is the bounds check: the data is choosing where the write lands.

Two Dimensions

int t[ROWS][COLS] is rows of columns, stored row-major: row 0 complete, then row 1, one contiguous run, making t[r][c] arithmetic too. Nested braces mirror rows and {{0}} zeroes the grid; only the first dimension may be omitted (int t[][3]), because the column count is what turns two subscripts into an offset, and the flat brace-less list that old papers print is equivalent and legal but warns. Two bracket pairs always, t[1, 2] is the comma operator naming the wrong thing, and bounds apply per dimension, with swapped indexes the 2D-specific bug.

Row sums, addition, and transpose are one three-pass nested-loop skeleton with different inner statements, per-row accumulators resetting inside the outer loop. Multiplication is the exception and the reason it is examined: element [r][c] of the product comes from row r of one matrix and column c of the other, so it needs a third index, product[r][c] accumulating a[r][k] * b[k][c] over k, with the reset inside the c loop but outside the k loop, and the first matrix's column count equal to the second's row count.

Dimensions do not stop at two. Multiply the sizes for the element count (int survey[3][5][12] is 180 ints), the rightmost subscript varies fastest, and a three-dimensional array is a stack of two-dimensional tables: one bracket pair, one loop, and one brace level per dimension.

The Algorithms

Linear search walks with a result index started at -1 and breaks on match: up to n comparisons, any array. Binary search demands sorted input, halves a [lo, hi] window with mid + 1/mid - 1 updates, and finds anything in about log n comparisons; keeping mid in the window loops forever on a miss. Bubble sort sweeps neighbor swaps, each pass settling the largest remaining element, inner bound n - 1 - i doing double duty for bounds and progress; the three-assignment temp swap is permanent equipment; cost n squared, the nested-loop multiplication made concrete.

One Program, Whole Chapter

A sort, a last-element read that is only correct because of the sort, and a bounds-respecting print walk. Predict both lines, run it, take the quiz.

Looking Ahead

Chapter 8 takes the array in one special direction: character arrays, where a zero-code terminator turns a run of chars into a string, and where the bounds discipline of this chapter becomes the difference between correct programs and the security bugs that made C famous.