C foundations for data structures

Learning outcomes

Write a small C function, distinguish an array from a structure, and state the contract of a data-structure operation.

1.1 From a problem to a representation

A student-record application stores roll numbers, marks and names. A program must decide both what a value means and how many values are organised. A data type specifies a set of values and permitted operations. A data structure organises values so that operations such as search, insertion and deletion can be performed.

An abstract data type (ADT) describes behaviour without prescribing storage. A stack ADT promises last-in, first-out access. An array and a linked list are two possible implementations. The choice affects capacity, memory use and operation costs, but not the stack's ordering rule.

C has arithmetic types, pointers, arrays, structures, unions, enumerations and function types. These language categories should not be confused with the ADT category. C has no built-in class or C++ reference type. In C11, include <stdbool.h> to use bool.

1.2 Control flow and functions

A sequence executes statements in order. Selection chooses a branch with if or switch. Iteration repeats work using for, while or do…while. Choose a loop whose termination condition you can explain.

#include <stddef.h>

/* Contract: a points to n valid int values, or n is zero. */
size_t count_positive(const int a[], size_t n)
{
    size_t count = 0;
    for (size_t i = 0; i < n; ++i) {
        if (a[i] > 0) {
            ++count;
        }
    }
    return count;
}

The counter records how many values satisfy a condition. An accumulator instead combines values, for example a running total. An accumulator's type must have enough range; signed integer overflow is not a valid way to wrap a total in C.

C passes arguments by value. To change a caller's object, pass its address and operate through a pointer. An array parameter such as int a[] is adjusted to a pointer parameter; the function does not receive the array's length automatically.

1.3 Arrays, structures and input

struct Student {
    int roll;
    double mark;
};

struct Student group[3] = {{101, 72.5}, {102, 81.0}, {103, 65.0}};

group[1].mark is the second student's mark. Each structure holds related fields, and the array groups three objects of the same type. Padding may exist between fields, so do not calculate a structure's size by adding field sizes manually.

printf formats output; its conversion specifiers must match the argument types. %d prints an int, %zu prints a size_t, and %f prints a promoted floating-point argument. For input, check the return value of functions such as scanf. For line-oriented input, fgets reads into a bounded buffer; converting and validating the resulting text is a separate step.

1.4 Write the contract before the code

For insertion into an array, a useful contract is: the position is within the logical sequence, spare capacity exists, and success increases the length by one. On failure, the sequence remains unchanged. This prevents a common mistake: writing the happy path without defining full, empty or invalid-input behaviour.

Trace: for {4, -2, 0, 9}, the positive counter after each value is 1, 1, 1, 2. The loop visits four values and uses a fixed amount of extra storage: Θ(n) time and Θ(1) auxiliary space.

Common mistakes

• Treating array length as information a function can infer from a pointer.
• Using an uninitialised variable as a counter or pointer.
• Treating an ADT as inherently static or dynamic. A stack can use either representation.
• Ignoring an input-conversion failure and using an old or uninitialised value.

Practice

1. Explain why a queue is an ADT rather than a C language type.
2. Trace count_positive for {-1, 2, 3, -4, 5}.
3. Write a function contract for finding the largest element. What should happen for an empty array?
4. Design a struct Book with a numeric identifier, a bounded title and a price. Explain one validation rule for each field.