Arrays, and allocating memory

Declaring an array#

An array is a fixed number of values of one type, side by side in memory:

int scores[5];                        // five ints, values unknown
int primes[5] = {2, 3, 5, 7, 11};
int zeros[100] = {0};                 // all 100 set to 0
int auto_sized[] = {4, 8, 15};        // size worked out: 3

Positions run from 0 to size - 1:

primes[0]      // 2
primes[4]      // 11
primes[5]      // out of bounds: C does not check, and anything can happen

The length of an array#

Inside the function where it is declared, sizeof gives the length:

int n = sizeof primes / sizeof primes[0];    // 5

Passing an array to a function#

When you pass an array, the function receives only a pointer to its first element. The length is lost, so it must travel separately:

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

// called as: sum(primes, 5)

sizeof inside sum would give the size of a pointer, not the array, which is a common surprise. This is why the judge passes C solutions both nums and numsSize.

Because the function gets a pointer to the original, changes it makes to elements are seen by the caller. Arrays are never copied when passed.

Two-dimensional arrays#

int grid[3][4] = {0};       // 3 rows, 4 columns
grid[1][2] = 7;             // row 1, column 2

for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        printf("%d ", grid[r][c]);
    }
    printf("\n");
}

Arrays sized at run time: malloc#

A fixed array's size must be known when you write the program. When the size comes from input, ask for memory while the program runs:

#include <stdlib.h>

int n;
scanf("%d", &n);
int *nums = malloc(n * sizeof(int));
if (nums == NULL) {
    return 1;               // the system could not give you the memory
}

for (int i = 0; i < n; i++) {
    scanf("%d", &nums[i]);
}

/* ... use nums like an array ... */

free(nums);                 // give the memory back when finished

• malloc returns a pointer to enough bytes, or NULL if it cannot.
• calloc(n, sizeof(int)) does the same and sets everything to zero.
• Every malloc needs exactly one free once you are done. Forgetting it leaks memory; freeing twice, or using memory after freeing it, corrupts the program.

Returning an array from a function#

A local array disappears when its function returns, so returning it is a bug. Allocate with malloc instead, and tell the caller how many elements there are:

int *running_sum(const int *nums, int n, int *returnSize) {
    int *out = malloc(n * sizeof(int));
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += nums[i];
        out[i] = total;
    }
    *returnSize = n;
    return out;
}

That returnSize pattern is exactly how C solutions return arrays on CodexBash.

Sorting#

The standard library sorts any array with qsort, given a comparison function:

int ascending(const void *a, const void *b) {
    int x = *(const int *) a, y = *(const int *) b;
    return (x > y) - (x < y);
}

qsort(nums, n, sizeof(int), ascending);

Write the comparison as (x > y) - (x < y). The tempting x - y overflows for large values of opposite sign.

Key points#

• Arrays have a fixed size and positions 0 to size - 1, unchecked.
• Passed to a function, an array becomes a pointer: pass the length too.
• Use malloc for sizes known only at run time, check for NULL, and free once.
• Return arrays by allocating them and reporting the size through a pointer.

That completes the C basics. Try the practice problems below, then the Learn track to put them to work on real algorithms.