The second aggregate data type in C that we consider is the struct. Structs are also commonly referred to as record. A struct has \(n\) fields of possibly distinct types \(T_1,\dots, T_n\text{.}\) A container for a struct is the combination of containers for the \(n\) fields. For an example, consider a struct that represents aspects of a person. We want to consider for each person a date of birth, a first name, and a last name.
A date consists of a day, a month, and a year:
struct date {
unsigned day, month, year;
};
We can use composition (“is part of”) or aggregation (“refers to”) to define our struct:
struct person {
struct date date_of_birth;
char name[16];
char surname[16];
};
Listing4.13.1.Composition
struct person {
struct date date_of_birth;
char const *name;
char const *surname;
};
Listing4.13.2.Aggregation
In both declarations, the date_of_birth field is added through composition. We could also implement the field via aggregation with a pointer to a date struct. However, the struct date is a small struct, therefore referencing it with a pointer saves little space in the person struct. Reusing struct date objects provides therefore little benefit for this case.
We can access the individual fields of a struct container with the . operator:
struct person p;
/* ... */
printf("%s %s\n", p.name, p.surname);
In contrast to arrays, structs can be passed to functions by value in C. With small structs, this can be sensible. In practice however, we usually pass structs via pointer as in the following example:
The expression A->B is an abbreviation for (*A).B.
Remark4.13.3.
In C, suffix operators have higher precedence than prefix operators. Therefore, *A.B is not the same as (*A).B: The former accesses a struct field and loads from the address contained there, the latter loads the field of a struct whose address is given. In practice, it is best to use parentheses to make non-obvious precedences explicit.
Subsection4.13.1typedef
Types in C can easily become long, like struct person, or complex, like int *(*)[10]. C provides the means to define shorter, more meaningful names for such types:
typedef struct {
/* see above */
} person_t;
/* ptr_table_t ist a pointer to an array
of 10 pointers to ints */
typedef int *(*ptr_table_t)[10];
Example4.13.4.Initialization.
It is a common pattern to define for each struct a function that properly initializes it. The following function initializes the version of struct person where name and surname are aggregated:
Such initialization functions, which are also called constructors, usually expect a pointer to an uninitialized struct container. This makes the constructor independent of how the struct is allocated: as a local variable, a global one, or dynamically:
It is important to not copy more characters than fit into the field. We realize this here with the snprintf function with the size sizeof(p->name). If we copied the string without ensuring that the field size is respected, we would encounter undefined behavior (see Section 4.15) when the function is called with too large strings. We can use sizeof here because the type of p->name here is char[16] and not char *. The value of sizeof(p->name) is therefore \(16\text{,}\) rather than the size of a pointer.
Example4.13.5.Polynomials.
The following struct represents a polynomial of degree n:
typedef struct {
unsigned degree;
int *coeffs;
} poly_t;
The coefficients are implemented through aggregation. This is necessary, since we do not want to assume a statically known fixed length for the polynomials. Therefore, an array for the coefficients need to be allocated separately (see Exercise 4.13.3.1).
Subsection4.13.2Incomplete Structs
We use a technique called encapsulation to separate large software systems into modules. By encapsulation, we hide the implementation details of a module from code that uses it. The benefit of this technique is that we can then change the module's implementation without affecting the code parts that use the module.
C supports encapsulation through incomplete structs. They allow to hide the specific structure of a struct from other code. We will discuss encapsulation in more detail in the Java part of this book.
Consider Example 4.13.5. Let us assume that we want to hide how polynomials are represented from using code parts. We achieve this with an incomplete struct that we declare in a header file (see poly.h in Figure 4.13.6). The values of the data type are then only accessible through a set of functions, a so-called Application Programming Interface (API). The API of such a data type only uses pointers to the incomplete type as the encapsulation ensures that its contents, and therefore the necessary container size, are not known to the outside.
#include <stdlib.h>
#include <stdio.h>
#include "poly.h"
int main(int argc, char *argv[])
{
if (argc < 3) {
fprintf(stderr, "syntax: %s x coeffs...",
argv[0]);
return 1;
}
poly_t *p = poly_alloc(argc - 3);
for (int i = 2; i < argc; i++) {
int coeff = atoi(argv[i]);
poly_set_coeff(p, i - 2, coeff);
}
int x = atoi(argv[1]);
int y = poly_eval(p, x);
poly_free(p);
printf("%d\n", y);
return 0;
}
(c)main.c
Figure4.13.6.Implementation of polynomials with encapsulation. The internal structure of the struct poly_t is only visible in the translation unit poly.c.
Exercises4.13.3Exercises
1.Polynomial.
We consider the API for polynomials defined in Figure 4.13.6. Complete the file poly.c: Implement the functions declared in the header file poly.h in.
Implement a function poly_alloc allocating the space for a polynomial on the heap.
Implement the function poly_free, that frees a polynomial that was constructed on the heap.
Implement the function poly_set_coeff that sets the coefficients of an polynomial.
Implement the evaluation of a polynomial using the Horner schema.
Implement the function poly_degree that returns the degree of a polynomial.
