4. Arrays, Strings, Matrices, and Sparse Structures

Introduction and Context

Arrays are among the most important representations in algorithm design. They provide direct access to elements through numeric indices, support compact storage, and form the basis of strings, tables, matrices, heaps, hash-table buckets, image buffers, and many scientific data structures. In C, arrays are especially significant because the language exposes their memory layout directly. This makes arrays efficient, but also places responsibility on the programmer to manage bounds, allocation, representation, and lifetime correctly.

This chapter develops array-based structures from one-dimensional sequences to multidimensional and sparse representations. It also examines dynamic arrays, character strings, polynomial storage, compact matrices, and locality-aware layouts. The central design question is not merely how data can be stored, but how representation influences access time, memory consumption, cache behavior, update cost, and algorithmic complexity.

An array normally occupies a contiguous region of memory. If the base address is B, the size of each element is w bytes, and indexing begins at zero, the address of element A[i] is:

Address(A[i]) = B + i × w.

This constant-time address calculation explains why indexed access is O(1). It also explains why insertion near the beginning is expensive: many subsequent elements may need to be shifted.

Learning Objectives

After completing this chapter, the learner should be able to:

• explain the memory model and operational characteristics of arrays in C;
• distinguish fixed-size arrays from dynamically allocated arrays;
• design safe operations for insertion, deletion, searching, and resizing;
• represent and manipulate strings, matrices, polynomials, and sparse structures;
• select row-major, column-major, packed, or blocked layouts for a problem;
• evaluate time, space, locality, and update trade-offs;
• identify implementation errors involving bounds, pointers, allocation, and aliasing;
• apply array-based representations to realistic computing scenarios.

Array Representation and Its Computational Consequences

A declaration such as `int a[10];` reserves storage for ten integers with indices 0 through 9. The array name generally denotes the address of its first element when used in an expression, although an array is not itself a modifiable pointer. The expressions `a[i]` and `*(a+i)` are equivalent, provided that i is within the valid range.

The fixed size of a built-in array is determined at declaration or allocation time. Its major strengths are predictable layout, low access overhead, and good spatial locality. Its limitations are equally important: the capacity cannot normally be expanded, and an incorrect index can cause undefined behavior. C does not automatically perform bounds checking.

Typical operations have the following costs:

• reading or writing an element by index: O(1);
• traversing all n elements: O(n);
• linear search in an unsorted array: O(n);
• binary search in a sorted array: O(log n), assuming random access;
• insertion or deletion at an arbitrary position: O(n) in the worst case;
• sorting: dependent on the selected algorithm, commonly O(n log n) for comparison-based methods.

The distinction between logical size and physical capacity becomes important in reusable array structures. Logical size is the number of valid elements; capacity is the number of allocated positions. A dynamic array may have size 37 and capacity 64. Confusing these values leads either to out-of-bounds access or to unnecessary reallocation.

Static, Automatic, and Dynamic Storage

An array may have static storage duration, automatic storage duration, or dynamically allocated storage. A global or `static` array exists for the lifetime of the program. A local array normally belongs to the current function activation and is commonly placed on the stack. An array created with `malloc` or `calloc` resides in dynamically managed storage until released with `free`.

Dynamic allocation is useful when the required size is known only at run time:

```c

int a = malloc(n sizeof *a);

if (a == NULL) {

/ allocation failure /

}

```

The expression `sizeof a` is preferable to repeating the type because it remains correct if the pointer type changes. For n elements of type T, robust allocation should also consider whether `n sizeof(T)` can overflow the size type. After use, `free(a)` must be called. A pointer should not be dereferenced after it has been freed, and retaining such a pointer creates a dangling pointer.

`calloc(n, sizeof *a)` allocates space for n elements and initializes all bytes to zero. This is useful for numeric arrays, but zeroed bytes should not be confused with a universal valid representation for every C type.

Dynamic Arrays and Amortized Growth

A dynamic array stores a pointer, a logical size, and a capacity. When the array becomes full, a larger block is allocated, existing elements are copied, and the old block is released. If capacity is multiplied by a constant such as two, an append operation is usually O(1) amortized, even though an individual resize costs O(n). Across a long sequence of append operations, each element is copied only a limited number of times at each growth scale.

A conceptual append operation is:

```c

bool append(int *data, size_t size, size_t *capacity, int value) {

if (size == capacity) {

size_t new_capacity = (capacity == 0) ? 1 : 2 (*capacity);

int p = realloc(data, new_capacity sizeof *data);

if (p == NULL) return false;

*data = p;

*capacity = new_capacity;

}

(data)[(size)++] = value;

return true;

}

```

In production code, multiplication overflow, maximum object sizes, and failure semantics should be handled explicitly. `realloc` must be assigned to a temporary pointer; assigning directly to the original pointer can lose the original allocation if reallocation fails.

Growth factors represent a trade-off. Larger factors reduce the frequency of copying but may reserve more unused memory. Smaller factors reduce slack but cause more frequent reallocations. If insertions and deletions occur throughout the sequence, a dynamic array may be inferior to a linked or tree-based structure; if traversal and indexing dominate, its locality often makes it preferable.

Strings: Arrays with a Contract

A C string is a sequence of characters terminated by the null character `\0`. The terminating byte is part of the storage requirement but not part of the logical text length. Thus, a string containing five visible characters requires at least six character positions.

```c

char word[6] = "array";

```

The library function `strlen` counts characters until the first null character and therefore costs O(n). Functions such as `strcpy`, `strcat`, and `sprintf` can be unsafe when destination capacity is not controlled. Safer design tracks buffer capacity explicitly and uses bounded operations or carefully written routines. `fgets` is generally preferable to unbounded input functions because it accepts a maximum length, although its retained newline may need removal.

String comparison is lexicographic and commonly costs O(min(m,n)) for strings of lengths m and n. Searching can use a straightforward scan, or algorithms such as Knuth–Morris–Pratt when repeated pattern matching is important. For large-scale text processing, compressed indexes, tries, suffix structures, and finite automata may be more suitable than repeated library calls.

A string is not necessarily the same as an arbitrary character array. A character buffer may contain binary data, embedded null bytes, or uninitialized positions. Treating such a buffer as a string is a representation error. International text also requires care: a byte-oriented C string may encode a multibyte character sequence, so character count, display width, and byte count need not be equal.

Multidimensional Arrays and Matrix Storage

A two-dimensional array in C, such as `double m[rows][cols]`, is stored in row-major order. Complete row 0 is followed by complete row 1, and so forth. The address of `m[i][j]` is conceptually:

B + (i × cols + j) × sizeof(double).

The number of columns is therefore part of the type information needed for pointer arithmetic. A function receiving a conventional two-dimensional array must know that dimension:

```c

void scale(size_t r, size_t c, double a[r][c], double k) {

for (size_t i = 0; i < r; ++i)

for (size_t j = 0; j < c; ++j)

a[i][j] *= k;

}

```

A dynamically allocated matrix can be represented as one contiguous block, as an array of row pointers, or as separately allocated rows. A single block generally offers better locality and simpler deallocation. Row pointers provide convenient syntax and permit unequal row lengths, but may require multiple allocations and do not guarantee one contiguous matrix.

For a matrix with r rows and c columns stored in one-dimensional array `x`, the row-major index is `ic+j`. In column-major order it is `jr+i`. Row-major traversal is usually faster on a C implementation when the inner loop advances across columns because adjacent accesses are more likely to share cache lines. The best order, however, depends on the actual layout and operation.

Locality-Aware Storage

Contiguity affects more than memory usage. Modern processors transfer data between memory and cache in blocks called cache lines. Accessing neighboring elements can exploit spatial locality; repeatedly using recently accessed elements exploits temporal locality. Consequently, two algorithms with the same asymptotic complexity may have different practical performance.

A matrix multiplication loop that accesses a matrix column through a row-major representation may generate large strides and poor locality. Loop interchange, transposition, tiling, and blocking can improve reuse. In blocked multiplication, matrices are processed in submatrices that fit more effectively in cache. The asymptotic bound may remain cubic, but the constant factor can change substantially.

Alignment, padding, false sharing in parallel programs, and the layout of structures containing arrays also influence performance. Locality should be measured rather than assumed; profiling and hardware-performance counters are valuable for critical systems.

Compact and Special Matrix Representations

Many matrices contain predictable values. Storing every entry wastes memory and may cause unnecessary computation. A diagonal matrix stores only its main diagonal, requiring n values rather than n². A triangular matrix stores either the upper or lower triangle, requiring n(n+1)/2 values. A symmetric matrix can store one triangle and reconstruct the other through `A[i][j] = A[j][i]`.

For zero-based indices, a lower-triangular matrix may be packed row by row. In row i, entries 0 through i are stored. The position of `A[i][j]`, where j ≤ i, is:

index(i,j) = i(i+1)/2 + j.

For an upper-triangular matrix packed row by row, a corresponding formula can be derived from the number of entries in preceding rows. Such formulas reduce space but make access less transparent and updates more dependent on correct index arithmetic.

A band matrix has nonzero values concentrated near the main diagonal. If the lower and upper bandwidths are small, a banded representation stores only those diagonals. This is common in numerical methods for differential equations and sparse linear systems. Compact representations should be selected only when the structural property is guaranteed; otherwise, the index complexity may outweigh the memory benefit.

Sparse Matrices: Representing Absence Efficiently

A sparse matrix contains relatively few nonzero entries. A dense n×n representation requires O(n²) storage even when only a small fraction of entries matter. Sparse representations store values together with their coordinates.

The simple triplet representation uses three arrays or records: row index, column index, and value. A header may store the matrix dimensions and number of nonzero terms. For example, the nonzero entries (0,2,5), (1,0,7), and (3,3,4) can be stored as three records. Triplets are easy to construct and useful for input, output, and some transformations.

Compressed Sparse Row (CSR) uses three arrays:

• `values`, containing nonzero values;
• `column_index`, containing the column of each value;
• `row_ptr`, where `row_ptr[i]` and `row_ptr[i+1]` delimit row i.

For a matrix with four rows, `row_ptr` has five entries. The number of nonzeros in row i is `row_ptr[i+1] - row_ptr[i]`. CSR provides efficient row traversal and matrix-vector multiplication, while random access to an arbitrary element may require searching within a row. Compressed Sparse Column (CSC) reverses the organization and is preferable for column-oriented operations.

Sparse formats involve trade-offs. Coordinate lists are flexible during construction; CSR and CSC are efficient for stable computation; diagonal or band formats can be superior when structure is known. Insertions into CSR may be costly because arrays must be shifted. A practical workflow often builds data in a flexible format, sorts and combines duplicate coordinates, and then converts to a compressed format.

Sparse matrix-vector multiplication in CSR visits each stored nonzero once and has time complexity O(nnz), where nnz denotes the number of nonzero entries. It is therefore proportional to actual stored information rather than the dimensions alone.

Polynomial Representation

A polynomial can be represented by an array of coefficients. For

P(x) = 4x⁵ − 2x² + 7,

a dense coefficient array may store `[7, 0, -2, 0, 0, 4]`, where position i contains the coefficient of xⁱ. Dense representation offers direct coefficient access and is efficient when most degrees occur, but it wastes space for high-degree polynomials with few nonzero terms.

A sparse polynomial stores pairs `(coefficient, exponent)`, such as `(4,5), (-2,2), (7,0)`. Terms are commonly ordered by decreasing exponent. Addition then resembles a merge of two sorted lists, while multiplication combines exponents and accumulates like terms. Hash-based accumulation may be useful when products produce terms in irregular order, followed by sorting if canonical output is required.

Horner’s rule evaluates a dense polynomial using n multiplications and n additions for degree n:

P(x) = (...((aₙx + aₙ₋₁)x + aₙ₋₂)...)x + a₀.

Compared with computing each power independently, Horner’s rule reduces operations and usually improves numerical behavior. The choice between dense and sparse representation depends on degree, number of nonzero terms, access patterns, and whether arithmetic or structural operations dominate.

An Illustrative Applied Case: Scientific Sensor Grid

Background

Consider an environmental-monitoring system that receives measurements from a 4,000 × 4,000 spatial grid. Most locations are inactive because sensors are installed only along roads, rivers, and industrial sites. The system must support periodic matrix-vector calculations, export data, and occasional sensor insertion.

Situation and Analysis

A dense double matrix would require 16 million values, approximately 128 megabytes before additional metadata. Although this may be feasible on a workstation, repeated scans would process millions of zero values. The active locations are estimated to be below one percent, so a sparse representation is more appropriate. Row-oriented calculations suggest CSR. However, frequent insertion during field deployment makes direct insertion into CSR inefficient.

Approach

New readings are first collected as coordinate triples `(row, column, value)` in a dynamic array. The system validates coordinates, combines duplicate readings, removes explicit zeros, sorts records by row and column, and converts the result to CSR. Matrix-vector multiplication then iterates from `row_ptr[i]` to `row_ptr[i+1]` for each row. If later workloads become predominantly column-oriented, a CSC version is generated rather than forcing every algorithm to use one layout.

The implementation uses `size_t` for dimensions and checks allocation multiplication for overflow. Input values are validated before indexing. A separate logical timestamp prevents confusion between a missing reading and a genuine zero reading.

Outcome

The design reduces storage and avoids computation over inactive locations. Conversion is performed in batches, so the cost of maintaining a compressed structure does not burden every incoming record. Performance is evaluated using both asymptotic measures and actual traces, because sparsity distribution and cache behavior affect results.

Learning Points

Representation must follow workload, not merely data type. Construction and computation may require different formats. Missing data must not automatically be encoded as numerical zero. Finally, safe memory and input handling are part of algorithm design, not optional implementation details.

Common Errors, Risks, and Professional Considerations

Array programs fail frequently because of off-by-one errors, incorrect capacity calculations, uninitialized elements, signed and unsigned comparisons, and invalid pointer lifetimes. A loop using `i <= n` accesses one position beyond an n-element array. Copying overlapping regions with `memcpy` rather than `memmove` can produce undefined behavior. Releasing the same allocation twice, losing a pointer after failed `realloc`, and returning the address of a local array are serious defects.

Security concerns are especially significant for strings and externally supplied dimensions. Buffer overflows may corrupt data or enable code execution. Integer overflow in allocation expressions may allocate less memory than expected and cause a subsequent overwrite. Robust code validates input ranges, checks allocation results, uses explicit capacities, and keeps ownership rules clear.

In numerical systems, floating-point equality, overflow, underflow, and propagation of missing values require domain-specific policies. In shared or regulated data systems, provenance, access control, retention, and auditability may apply to array contents just as they apply to database records. AI and analytics pipelines commonly use dense tensors, sparse tensors, and memory-mapped arrays; their performance depends on layout, precision, batching, and accelerator-specific access patterns. Automated tools can detect some bounds and lifetime errors, but testing, code review, sanitizers, and profiling remain necessary.

Design Guidance and Emerging Directions

A sound design begins by specifying operations: random access, sequential traversal, insertion, deletion, aggregation, matrix-vector multiplication, or numerical factorization. It then estimates dimensions, density, update frequency, precision, and locality. The representation should be selected against these requirements.

Useful practices include:

• keep logical size separate from capacity;
• encapsulate allocation and ownership in clear interfaces;
• use contiguous storage when traversal and locality dominate;
• choose CSR or CSC according to the dominant orientation of computation;
• build sparse structures flexibly and compress them for stable workloads;
• document index formulas for packed matrices;
• test empty, singleton, maximum-size, and boundary cases;
• use sanitizers, assertions, profiling, and property-based tests;
• avoid premature compression when it makes correctness difficult.

Emerging systems increasingly combine ordinary arrays with compressed sparse tensors, memory mapping, vectorized instructions, and accelerators. Columnar data layouts support analytical scans, while structure-of-arrays layouts can improve SIMD processing compared with array-of-structures layouts. These developments reinforce the central principle of the chapter: storage layout is an algorithmic decision with consequences for speed, memory, scalability, and correctness.

Chapter Summary

Arrays provide contiguous, indexed storage with O(1) element access and strong locality. Their fixed capacity makes insertion costly and motivates dynamic arrays, whose geometric growth gives amortized constant-time append. C strings are null-terminated character arrays and require explicit capacity and careful input handling. Multidimensional arrays use layout-dependent index formulas; in C, ordinary two-dimensional arrays are row-major. Compact diagonal, triangular, symmetric, and band representations exploit known structure. Sparse matrices store only nonzero values, commonly through triplets, CSR, or CSC, and achieve computation proportional to the number of stored entries. Polynomial representation may be dense or sparse, and Horner’s rule provides efficient evaluation. Across all these structures, the correct representation depends on workload, density, locality, update patterns, and safety requirements.

Key Terms

Array: A fixed-index sequence of elements stored in an organized memory region.

Contiguous storage: Placement of elements in adjacent memory locations.

Logical size: Number of positions currently containing valid data.

Capacity: Number of elements that an allocated structure can hold.

Dynamic array: A resizable array managed through dynamic memory allocation.

Amortized analysis: Analysis of average cost over a sequence of operations.

Spatial locality: Tendency to access memory locations near recently accessed locations.

Row-major order: Storage in which complete rows are placed consecutively.

Column-major order: Storage in which complete columns are placed consecutively.

Packed matrix: A matrix stored using fewer positions by exploiting structural properties.

Sparse matrix: A matrix in which most entries are zero or absent.

Triplet representation: Sparse storage using row, column, and value records.

CSR: Compressed Sparse Row representation using values, columns, and row offsets.

CSC: Compressed Sparse Column representation organized by columns.

Polynomial: An expression represented by coefficients associated with exponents.

Horner’s rule: Nested polynomial evaluation using one multiplication per degree.

Null character: The `\0` byte that terminates a C string.

Dangling pointer: A pointer referring to storage that is no longer valid.

Cache locality: Performance benefit obtained when memory access reuses nearby or recent data.

Structure of arrays: Layout that stores each field of many records in a separate array.

Review Questions

Short Answer Questions

1. Why does indexed access to a conventional array have O(1) complexity?

2. Distinguish logical size from capacity in a dynamic array.

3. What is the role of the null character in a C string?

4. State two differences between CSR and triplet sparse representations.

5. Why can row-major traversal be faster than column traversal in a C matrix?

Long Answer Questions

1. Explain dynamic-array growth, including reallocation, ownership, and amortized complexity.

2. Describe the representation and access formulas for a row-major two-dimensional array.

3. Compare dense, triplet, CSR, and CSC representations of a sparse matrix.

4. Discuss packed representations for triangular, diagonal, symmetric, and band matrices.

5. Explain dense and sparse polynomial representations and evaluate the role of Horner’s rule.

Analytical / Application Questions

1. A matrix has one million rows and ten million nonzero entries distributed unevenly among rows. Which representation would you choose for repeated matrix-vector multiplication, and what information must its row-offset array contain?

2. A program appends 100,000 integers and occasionally accesses arbitrary positions. Design a capacity-growth policy and justify it using time, memory, and locality considerations.

3. A C program receives matrix dimensions from users and allocates `rows columns sizeof(double)` bytes. Identify the risks and propose a safe allocation and validation strategy.

22. Multiple Choice Questions with Answers

Question 1

Which property most directly gives a conventional array constant-time indexed access?

A. Elements are stored contiguously and the address is computed arithmetically

B. Elements are always sorted

C. Insertion shifts elements automatically

D. Every element stores a pointer to the next element

Correct Answer: A. Elements are stored contiguously and the address is computed arithmetically

Question 2

A dynamic array doubles its capacity whenever it becomes full. What is the amortized complexity of appending n elements?

A. O(n²)

B. O(log n) per append

C. O(1) per append amortized

D. O(n) per append amortized

Correct Answer: C. O(1) per append amortized

Question 3

For a C string containing seven visible characters, the minimum character-array capacity is:

A. 6

B. 7

C. 8

D. 14

Correct Answer: C. 8

Question 4

In a row-major matrix with c columns, the one-dimensional index of element (i,j), using zero-based indexing, is:

A. i + j

B. i*c + j

C. j*c + i

D. i*j + c

Correct Answer: B. i*c + j

Question 5

Which sparse representation is organized around row offsets and is especially suitable for row traversal?

A. CSR

B. CSC

C. A dense array

D. A null-terminated string

Correct Answer: A. CSR

Question 6

A sparse matrix contains 500 nonzero entries in a 10,000 × 10,000 grid. Which is the strongest reason to avoid dense storage?

A. Dense storage cannot represent zero

B. Dense storage uses space proportional to all grid positions

C. Sparse storage prevents arithmetic

D. Dense storage cannot be indexed

Correct Answer: B. Dense storage uses space proportional to all grid positions

Question 7

For a lower-triangular matrix stored row by row, which formula gives the packed index of A[i][j] when j ≤ i and indices start at zero?

A. i + j

B. i(i+1)/2 + j

C. j(j+1)/2 + i

D. i² + j²

Correct Answer: B. i(i+1)/2 + j

Question 8

Why should realloc generally be assigned to a temporary pointer first?

A. It always returns a pointer to a different type

B. It initializes all elements to zero

C. Failure may return NULL while the original allocation remains valid

D. It automatically releases the old pointer before allocation

Correct Answer: C. Failure may return NULL while the original allocation remains valid

Question 9

Which method evaluates a degree-n polynomial using a nested sequence of multiplications and additions?

A. Binary search

B. Horner’s rule

C. Row blocking

D. Coordinate compression

Correct Answer: B. Horner’s rule

Question 10

A workload performs repeated column-oriented operations on a sparse matrix. Which representation is generally the most natural choice?

A. CSC

B. CSR

C. A row-packed triangular format

D. A null-terminated character array

Correct Answer: A. CSC