Arrays, Strings, and Multidimensional Data

Introduction

Arrays and strings are among the most important aggregate data structures in C. They allow a program to represent collections of values under one identifier, process data systematically, and model tables, matrices, records of measurements, text, and many forms of memory-resident data. Although arrays appear simple, their correct use requires an understanding of contiguous storage, indexing, pointer arithmetic, object lifetime, bounds, representation, and the distinction between storage capacity and meaningful data.

At postgraduate level, arrays should not be treated merely as syntax. They are an interface between C’s type system and its memory model. Their strengths—predictable layout, low overhead, and efficient access—also create risks, including out-of-bounds access, buffer overflow, unintended aliasing, and inefficient data movement. This chapter develops both the conceptual and engineering perspectives.

Learning Objectives

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

1. Explain array representation, indexing, initialization, and lifetime in C.
2. Analyze the relationship between arrays and pointers without confusing their types.
3. Design safe algorithms for searching, sorting, insertion, deletion, and aggregation.
4. Manipulate character arrays and null-terminated strings safely.
5. Represent and process multidimensional data using arrays and dynamic allocation.
6. Evaluate storage layout, cache behavior, complexity, portability, and security implications.
7. Apply these concepts to a realistic data-processing problem.

1. The Array Abstraction

An array is a contiguous sequence of objects of the same type. Its declaration specifies an element type and a number of elements:

int marks[5];

This declaration reserves storage for five int objects. The valid indices are 0 through 4. In general, for an array declared as T a[N], the valid index set is:

Here, T is the element type and N is the number of elements. C performs no automatic bounds checking. An expression such as a[N] is outside the array and evaluating it produces undefined behavior when it accesses an object that does not belong to the array.

The address of element i can be conceptualized as:

The formula describes byte-oriented address arithmetic; i must satisfy 0 ≤ i < N for a valid element access. The actual object representation and alignment are controlled by the implementation, but array elements themselves have no padding between consecutive elements beyond what is inherent in the element type’s size.

1.1 Initialization

Arrays can be initialized at definition:

int values[5] = {4, 8, 15, 16, 23};
int zeros[5] = {0};
int inferred[] = {2, 3, 5, 7};

The third declaration has four elements because the compiler infers the size from the initializer. If fewer initializers are supplied than the declared size, remaining elements are initialized to zero. An initializer cannot supply more elements than the declared size.

A variable-length array (VLA), supported in some versions and implementations of C, has a run-time determined bound:

void process(size_t n) {
    double data[n];
    /* use data only while n and data remain valid */
}

VLAs have automatic storage duration and can consume substantial stack space. Their use should be evaluated for portability, maximum input size, and failure behavior. In portable systems code, dynamic allocation is often preferable when the size is large or not known safely at compile time.

1.2 Storage Duration and Scope

An array may have automatic, static, or allocated storage duration.

• An automatic array is normally created when block execution begins and ceases to exist when the block ends.
• A static array exists for the entire program execution. A file-scope array is static in duration; the static keyword also controls linkage when used at file scope.
• An allocated array is obtained through functions such as malloc or calloc and remains until released with free.

Example:

int *make_vector(size_t n) {
    int *p = malloc(n * sizeof *p);
    if (p == NULL) return NULL;
    return p;
}

The caller owns the returned storage and must eventually call free(p). The expression n sizeof p is preferable to n * sizeof(int) because it remains correct if the pointed-to type changes. A robust implementation must also consider multiplication overflow before allocation, especially when n is derived from untrusted input.

2. Arrays and Pointers

In most expressions, an array name is converted to a pointer to its first element. Thus, if int a[4];, the expression a commonly behaves like &a[0]. However, an array is not itself a pointer. This distinction matters in sizeof, address-of operations, assignment, and function parameters.

int a[4] = {1, 2, 3, 4};
int *p = a;

sizeof a       /* size of all four elements */
sizeof p       /* size of a pointer */
&a             /* pointer to the whole array */
&a[0]          /* pointer to the first element */

Pointer arithmetic is scaled by the pointed-to type. If p points to a[0], then p + 2 points to a[2], provided that the resulting pointer remains within the same array object or one position beyond it. Dereferencing the one-past pointer is invalid.

The expression a[i] is defined in terms of pointer notation:

a[i]  /* equivalent to *(a + i) */

This equivalence explains why the index may be written on either side syntactically, although i[a] is poor style and should not be used.

2.1 Passing Arrays to Functions

A parameter declared as an array is adjusted to a pointer parameter:

void print_values(const int a[], size_t n);

is equivalent, for parameter purposes, to:

void print_values(const int *a, size_t n);

The function therefore does not know the array length from a; the length must be passed separately. const documents that the function will not modify the elements through that pointer.

void print_values(const int *a, size_t n) {
    for (size_t i = 0; i < n; ++i)
        printf("%d ", a[i]);
}

A pointer and a length form a common C “span” convention. The pair is efficient, but correctness depends on the caller supplying a valid pointer and a consistent length. Modern interface design should document whether the pointer may be null when n == 0, whether overlapping ranges are permitted, and whether the function modifies the data.

3. Core Array Algorithms

3.1 Traversal and Aggregation

A traversal visits each element once. For an array of n elements, its time complexity is Θ(n), and its auxiliary space is usually Θ(1), excluding the input array.

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

Using a wider accumulator can reduce overflow risk, but it does not guarantee safety if the sum itself exceeds the range of long. For high-assurance code, bounds analysis or checked arithmetic is required.

3.2 Linear and Binary Search

Linear search compares a target with each element and works on unsorted data. Its worst-case time is Θ(n).

Binary search repeatedly halves a sorted search interval. Its worst-case time is Θ(log n), and its auxiliary space is Θ(1) for an iterative implementation. The interval invariant must be stated carefully. For a half-open interval [low, high), the candidate elements are those satisfying low ≤ i < high.

size_t lower_bound(const int a[], size_t n, int target) {
    size_t low = 0, high = n;
    while (low < high) {
        size_t mid = low + (high - low) / 2;
        if (a[mid] < target)
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

This function returns the first index whose value is not less than target. If the returned index equals n, no such element exists. The expression for mid avoids the classical low + high overflow risk.

3.3 Insertion and Deletion

Inserting into or deleting from the middle of a contiguous array requires shifting elements. If n elements are shifted, the operation is Θ(n). The memmove function is appropriate when source and destination ranges overlap:

memmove(&a[pos + 1], &a[pos], (n - pos) * sizeof a[0]);
a[pos] = value;

The caller must verify that pos ≤ n and that the physical array has capacity for n + 1 elements. memcpy must not be used for overlapping regions; its behavior is undefined in that case.

3.4 Sorting and Stability

Sorting rearranges elements into an order determined by a comparison relation. Selection sort and insertion sort are simple but generally Θ(n²). Quicksort has average Θ(n log n) behavior but can have Θ(n²) worst-case behavior depending on pivot selection and implementation. Merge sort offers Θ(n log n) time and can be stable, but ordinarily needs auxiliary storage.

Stability means that records with equal keys retain their original relative order. Stability is important when sorting successively by multiple criteria. In professional applications, the choice of sorting algorithm should consider input size, key distribution, memory constraints, worst-case guarantees, and whether stability is required.

4. Strings as Character Arrays

C has no built-in string type. A C string is a contiguous sequence of characters terminated by a null character, written as \0, whose value is zero.

char name[] = "Ada";

The array contains four characters: 'A', 'd', 'a', and '\0'. Therefore, the storage requirement for a string containing L characters is at least L + 1 characters. strlen(name) returns L, not the allocated capacity.

A character array is not necessarily a string. For example:

char bytes[3] = {'A', 'B', 'C'};

contains no terminator and must not be passed to functions that expect a null-terminated string. This distinction is a frequent source of defects.

4.1 String Literals and Mutability

A string literal such as "hello" has static storage duration. It should not be modified. The correct declaration for a modifiable copy is:

char text[] = "hello";

A pointer declaration does not create writable storage for the literal:

const char *text = "hello";

The const qualification communicates the intended read-only use.

4.2 Standard String Functions

Important functions in <string.h> include:

The bounded functions are not automatically safe. For example, strncpy may produce a non-terminated character sequence. A safer interface often accepts an explicit destination capacity and guarantees termination:

int copy_text(char *dest, size_t capacity, const char *src) {
    if (capacity == 0) return 0;
    size_t i = 0;
    while (i + 1 < capacity && src[i] != '\0') {
        dest[i] = src[i];
        ++i;
    }
    dest[i] = '\0';
    return src[i] == '\0';  /* true if no truncation occurred */
}

The function assumes dest points to at least capacity writable characters and src points to a valid string. It returns zero if truncation occurs.

4.3 Input and Security

scanf("%s", buffer) is unsafe without a field width because input can exceed the buffer. fgets is generally preferable:

if (fgets(buffer, sizeof buffer, stdin) != NULL) {
    buffer[strcspn(buffer, "\n")] = '\0';
}

Even fgets requires careful handling of truncation and embedded input characters. String-processing defects can cause buffer overflows, information disclosure, denial of service, or control-flow attacks. Secure development therefore requires explicit capacity tracking, validation of external input, compiler diagnostics, testing with sanitizers, and code review.

5. Multidimensional Arrays

A two-dimensional array is an array whose elements are themselves arrays:

int matrix[3][4];

It contains three rows, each containing four integers. C stores the elements in row-major order: all elements of row 0, followed by row 1, and so on. For a declaration T a[R][C], the conceptual offset of a[i][j] from the first element is:

where 0 ≤ i < R and 0 ≤ j < C. The byte address is obtained by multiplying this element offset by sizeof(T). This formula assumes a conventional contiguous built-in array and zero-based indexing.

A useful visualization is:

matrix[0][0] matrix[0][1] ... matrix[0][C-1]
matrix[1][0] matrix[1][1] ... matrix[1][C-1]
...
matrix[R-1][0] ...       matrix[R-1][C-1]

5.1 Function Parameters for 2D Arrays

When passing a two-dimensional array, the compiler must know the size of the second and subsequent dimensions to calculate offsets:

void scale(size_t rows, size_t cols,
           double a[rows][cols], double factor) {
    for (size_t i = 0; i < rows; ++i)
        for (size_t j = 0; j < cols; ++j)
            a[i][j] *= factor;
}

This uses a variable-length array parameter. The cols value must be valid when indexing a. An alternative for compile-time dimensions is:

void print_matrix(size_t rows, int a[][4]);

The first dimension may be omitted because it is not needed to calculate the address of an element; the column dimension is required.

5.2 Dynamic 2D Data

There are several representations for dynamically sized matrices:

1. A single contiguous allocation containing rows × cols elements.
2. An array of row pointers, where each row is separately allocated.
3. A pointer to an array type, such as int (*a)[cols], when the column count is known at allocation time.

A contiguous representation improves locality and simplifies deallocation:

int *data = malloc(rows * cols * sizeof *data);
if (data != NULL) {
    #define AT(i, j) data[(i) * cols + (j)]
    AT(2, 3) = 10;
}
free(data);

The macro must be used cautiously because macro arguments can be evaluated more than once. An inline function cannot return an lvalue in standard C, so many designs instead use a documented indexing expression or a wrapper structure.

A row-pointer representation supports rows of different lengths but requires multiple allocations and can have poorer locality. It is not equivalent to a genuine rectangular array and should not be passed to a function expecting a contiguous matrix.

6. Performance, Locality, and Representation

Arrays provide constant-time indexed access under the random-access model: accessing a[i] takes Θ(1) time when the address calculation and element access are bounded operations. This does not mean all array algorithms are constant-time; traversing n elements remains Θ(n).

Modern processors transfer data between memory and cache in blocks. Iterating through a contiguous array in storage order usually improves spatial locality. For a row-major matrix, this loop generally has better locality:

for (size_t i = 0; i < rows; ++i)
    for (size_t j = 0; j < cols; ++j)
        total += a[i][j];

than the version with the loops reversed. The asymptotic complexity is the same, but execution time can differ significantly because of cache behavior. Optimization must preserve defined behavior; an out-of-bounds “optimization” is never valid.

The restrict qualifier can communicate a non-aliasing contract:

void add(size_t n, double *restrict out,
         const double *restrict x,
         const double *restrict y);

This declaration is appropriate only if the referenced objects do not overlap in a way that violates the restrict rules. Misuse can produce undefined behavior and incorrect optimized results. It is a semantic promise, not a request for optimization without conditions.

7. Worked Example: Temperature Analysis

Suppose a laboratory records temperatures for seven days, with three readings per day. The objective is to calculate each day’s mean and identify the day with the greatest mean.

#include <stddef.h>

size_t hottest_day(const double readings[][3], size_t days,
                   double *best_mean) {
    size_t best = 0;
    *best_mean = 0.0;

    if (days == 0) return 0;

    for (size_t d = 0; d < days; ++d) {
        double sum = 0.0;
        for (size_t r = 0; r < 3; ++r)
            sum += readings[d][r];
        double mean = sum / 3.0;
        if (d == 0 || mean > *best_mean) {
            *best_mean = mean;
            best = d;
        }
    }
    return best;
}

The mean for day d is:

where x_{d,r} is the reading for day d and reading position r. The function performs 3 × days additions and a constant amount of work per day, so its time complexity is Θ(days) because the number of readings per day is fixed. It uses Θ(1) auxiliary space.

A production version should specify units, missing-value policy, handling of sensor errors, floating-point tolerance, and behavior when days is zero. If readings are externally supplied, dimensions and allocation sizes must be validated before use.

8. Applied Case: A Small Log-Analysis Component

Background

Consider an illustrative software component that receives up to 10,000 textual log messages and must classify them by severity: INFO, WARN, and ERROR.

Problem

The component must store messages, count categories, search for a keyword, and produce a summary without overflowing fixed buffers or confusing capacity with length.

Analysis

A fixed two-dimensional character array such as char logs[10000][256] is simple and provides contiguous storage, but it reserves approximately 2.56 million character positions even when messages are short. It also imposes a maximum message length. A dynamically allocated array of pointers can reduce unused storage, but introduces allocation overhead and fragmentation. A contiguous character pool with offsets can improve locality and simplify serialization, but requires offset management.

Approach and Solution

A practical design may use an array of records:

struct LogEntry {
    char *message;
    unsigned severity;
};

Each message is allocated after validating its length. The record array stores ownership information, while a separate function releases every message and then the record array. Search functions receive explicit lengths or valid strings. Classification should use exact token comparison rather than unsafe prefix assumptions.

For high-throughput systems, a bounded ring buffer may be more suitable. It stores a fixed number of recent records and overwrites the oldest entry when full. Such a policy must be explicit because overwriting is a data-retention decision, not merely a memory optimization.

Outcome

The design can support efficient sequential reporting and clear ownership. Its correctness depends on checking allocation results, enforcing message limits, terminating strings, preventing data races in concurrent use, and defining what happens when capacity is exhausted.

Learning Points

1. Representation should follow access patterns and ownership requirements.
2. Every pointer should have a clear lifetime and owner.
3. Capacity, current length, and maximum permitted input are different concepts.
4. Security controls must be part of the data structure’s interface.
5. A faster representation is not better if its invariants are undocumented.

9. Limitations, Governance, and Best Practices

Arrays are efficient but inflexible. Their fixed size can cause waste or rejection of legitimate input; dynamic arrays require allocation failure handling; and raw character arrays provide no automatic encoding or bounds protection. C strings also represent byte sequences, not necessarily human-readable characters. Unicode text may require UTF-8 validation, code-point processing, or a specialized library.

Recommended practices include:

• Define and validate every array bound.
• Pass a pointer together with its valid length or capacity.
• Use size_t for object sizes and indices, while checking conversions from signed input.
• Check allocation multiplication for overflow.
• Prefer sizeof *pointer in allocation expressions.
• Use memmove for overlapping ranges and memcpy only for non-overlapping ranges.
• Treat external input as untrusted.
• Use compiler warnings, static analysis, fuzz testing, AddressSanitizer, and UndefinedBehaviorSanitizer where available.
• Document ownership, mutability, nullability, termination, and aliasing contracts.
• Avoid returning pointers to automatic arrays whose lifetime has ended.
• Consider cache locality and alignment only after correctness and profiling requirements are clear.

In regulated or safety-critical contexts, array access should be traceable to requirements, tested at boundary values, and reviewed against coding standards. Logging and telemetry data may contain personal or confidential information; storage and retention policies must therefore address privacy, access control, minimization, and secure deletion.

Chapter Summary

Arrays are contiguous collections of objects of one type, indexed from zero. Their layout supports efficient constant-time element access, but C does not perform bounds checking. Array names commonly decay to pointers, yet arrays and pointers remain different types with different behavior under sizeof, address-of operations, and assignment. Function interfaces should pass lengths explicitly and document ownership and mutability.

C strings are character arrays terminated by a null character. String capacity, current length, and termination are distinct properties. Standard library functions are useful only when their preconditions—valid strings, sufficient destination space, and appropriate overlap behavior—are satisfied. Multidimensional arrays are arrays of arrays stored in row-major order; dynamic representations must distinguish contiguous matrices from collections of independently allocated rows.

Algorithmic complexity, cache locality, aliasing, allocation strategy, and security all influence professional array design. Safe implementations validate dimensions, prevent arithmetic overflow, control lifetimes, handle truncation, and test boundary conditions. These principles apply to scientific data, text processing, embedded systems, operating systems, and high-performance computing.

Key Terms

Array: A contiguous sequence of objects of the same type.

Index: An integer position used to select an array element.

Bounds: The limits within which an array index is valid.

Pointer decay: Conversion of an array expression to a pointer to its first element in most expressions.

Contiguous storage: Adjacent placement of elements without unrelated gaps between them.

Storage duration: The period during which an object exists.

Dynamic allocation: Obtaining storage during execution, normally with malloc or related functions.

Capacity: The maximum number of elements or characters that storage can hold.

Length: The number of currently meaningful elements or characters.

C string: A character sequence terminated by \0.

Null character: The zero-valued character that terminates a C string.

Buffer overflow: Access beyond the storage allocated for an object.

Row-major order: Storage of a multidimensional array row by row.

Pointer arithmetic: Arithmetic whose scale is determined by the pointed-to type.

Aliasing: The condition in which multiple expressions can refer to the same object.

restrict: A qualifier expressing a programmer-supplied non-aliasing contract.

Stability: Preservation of the relative order of equal-key records during sorting.

Locality: The tendency of programs to reuse nearby or recently accessed memory.

Undefined behavior: Program execution for which the C standard imposes no requirements.

Review Questions

Short Answer Questions

1. Why are valid indices for an array of N elements from 0 through N − 1?
2. Explain why an array parameter in a function does not convey the array length.
3. What distinguishes a character array from a C string?
4. Why does a two-dimensional array parameter require the column dimension?
5. When should memmove be used instead of memcpy?

Long Answer Questions

1. Explain the relationship and differences between arrays and pointers, using sizeof, pointer arithmetic, and function parameters.
2. Discuss the representation, safety requirements, and limitations of C strings and standard string functions.
3. Compare contiguous dynamic matrices with row-pointer matrices in terms of layout, allocation, locality, and deallocation.
4. Analyze linear search, binary search, insertion, deletion, and sorting with respect to complexity and preconditions.
5. Develop a safe design for processing a collection of variable-length text records, including ownership and failure handling.

Analytical / Application Questions

1. A program receives a row-major matrix but traverses columns in the inner loop. Analyze the likely performance consequences and propose a revised traversal.
2. Design an interface that copies input text into a fixed-capacity destination and reports whether truncation occurred. State all preconditions and postconditions.
3. A matrix allocation computes rows cols sizeof(double) using unvalidated external values. Identify the risks and design a validation strategy before allocation.

Multiple Choice Questions with Answers

Question 1

For an array declared as int a[5], which index is valid?

A. -1

B. 0

C. 5

D. 6

Correct Answer: B. 0

Question 2

What does sizeof applied directly to an array generally produce?

A. The size of a pointer to its first element

B. The number of initialized elements only

C. The total size of the array in bytes

D. The size of the final element

Correct Answer: C. The total size of the array in bytes

Question 3

Which condition is required for standard binary search to operate correctly?

A. The array must contain strings

B. The array must be sorted according to the search ordering

C. The array must have an even number of elements

D. The array must be dynamically allocated

Correct Answer: B. The array must be sorted according to the search ordering

Question 4

What terminates a C string?

A. A newline character only

B. A space character

C. A null character with value zero

D. The last allocated byte automatically

Correct Answer: C. A null character with value zero

Question 5

Which function is appropriate for copying overlapping memory regions?

A. memcpy

B. memmove

C. strlen

D. strcmp

Correct Answer: B. memmove

Question 6

For int matrix[3][4], what is the conceptual element offset of matrix[2][1] in row-major order?

A. 3

B. 7

C. 9

D. 12

Correct Answer: C. 9

Question 7

Why must a string destination have room for one additional character beyond its visible text?

A. To store the array index

B. To store the terminating null character

C. To store the source pointer

D. To store the string length automatically

Correct Answer: B. To store the terminating null character

Question 8

What is the usual worst-case time complexity of linear search over n elements?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n² log n)

Correct Answer: C. Θ(n)

Question 9

Which statement about strncpy is correct?

A. It always guarantees null termination

B. It cannot copy character arrays

C. It may fail to append a null character when truncation occurs

D. It automatically allocates the destination

Correct Answer: C. It may fail to append a null character when truncation occurs

Question 10

Why is the second dimension required in a conventional two-dimensional array parameter?

A. To determine the element type

B. To calculate row offsets

C. To allocate the function stack frame only

D. To force column-major storage

Correct Answer: B. To calculate row offsets