LABORATORY 11

User-Defined Data Types

Duration: 2 hours Language: C / C++ Previous: Laboratory 10 PDF handout RO versiunea română

Predefined types are not enough when data is complex and must be structured according to your own criteria. C/C++ lets the programmer define new types, tailored exactly to the application's needs.

1Lab objectives

struct S { char a; int b; char c; }; on a machine with a 4-byte intapaddingbcpadding01234567891011byte indices inside the structuresizeof(S) = 12, not 6the compiler inserts padding so each field starts at an aligned address
Fig. - Alignment of fields in a structure. Padding bytes hold no data, but they count toward sizeof - which is why the declaration order of the fields changes the structure's size.
  • Renaming types with typedef for more readable code
  • Defining and using enumerations
  • Building structures and accessing members
  • Understanding memory alignment and padding bytes
  • Using bit fields and unions

2Overview

MechanismWhat it doesWhen it is used
typedefrenames an existing typesimplifying complicated declarations
enumdefines a set of named integer constantsstates, options, error codes
structgroups data of different types under one namerecords: student, product, point
bit fieldsmembers allocated at bit levelhardware registers, compact flags
unionseveral members that share the same zonememory savings, reinterpreting data

In addition to C, the C++ language offers the definition of classes - types that follow the principles of object-oriented programming (covered in Laboratory 13).

3The typedef declaration

examples
typedef unsigned char  byte;        // byte becomes a synonym for unsigned char
typedef unsigned int   uint;
typedef int            Vector[10];  // Vector is "an array of 10 integers"
typedef int          (*Operation)(int, int);   // pointer to a function

byte      mask = 0xF0;
uint      counter = 0;
Vector    v;                        // equivalent to int v[10];
Operation op;                       // equivalent to int (*op)(int,int);
The real usefulnessThe declaration int (*table[5])(int, int); is hard to read. With typedef it becomes Operation table[5]; - the same meaning, but understandable at a glance.

4Enumeration

syntax
enum <enum_type_id> { elem_id <= const>, ... } <var_id_list>;

enum Color { RED, GREEN, BLUE };               // 0, 1, 2 by default
enum Code  { OK = 0, ERROR = -1, WARNING = 10, SEVERE };  // SEVERE becomes 11

enum boolean { false, true };                  // false=0, true=1
typedef enum { false, true } boolean;          // equivalent declaration
RuleDetail
Default valuethe first element is 0, each next one increases by 1
Explicit valuescan be assigned; the following elements continue from that value
Name uniquenessidentifiers must be distinct within their scope
Underlying typecompatible with int
Why they are usefulCompare if (state == 2) with if (state == CONNECTED). The second form explains itself, and if the numeric values change, the code stays correct with no change at all.

5Structures

declaring and using
struct Student {
    char   name[50];
    int    age;
    float  average;
};                                  // note: semicolon is mandatory

struct Student s1;                  // in C the word struct must be repeated
Student s2;                         // in C++ it is not needed

typedef struct {                    // typedef variant, common in C
    char  name[50];
    int   age;
    float average;
} Student_t;

Student_t s3 = {"John Smith", 20, 9.15};    // initialization at declaration

s3.age = 21;                        // access through the dot
Student_t *p = &s3;
p->average = 9.40;                  // access through the arrow, when we have a pointer
OperationSyntaxNotes
Member accesss.memberfor ordinary variables
Access through a pointerp->memberequivalent to (*p).member
Assignments2 = s1;allowed - all members are copied
Comparisons1 == s2forbidden - must be compared member by member
Structures cannot be compared directlyThe == operator is not defined for structures, precisely because of the padding bytes, whose contents are undefined. Two structures with the same values can have different binary representations.

6Simulator: memory alignment

The compiler inserts padding bytes so that each member starts at a suitable address. Compare the two structures below: they contain exactly the same members, but in a different order - and they take up different amounts of space.

struct { char c; int x; char d; } - unfavorable order
struct { int x; char c; char d; } - optimized order
The practical ruleDeclare members in decreasing order of size (double, then int, then short, then char). In an array of a million structures, the savings become significant.

7Bit fields

A structure's members can be allocated at bit level rather than byte level. The number of bits is specified after the member's name:

example - describing a register
struct ControlRegister {
    unsigned int enabled  : 1;      // 1 bit  -> values 0 or 1
    unsigned int mode     : 3;      // 3 bits -> values 0..7
    unsigned int priority : 4;      // 4 bits -> values 0..15
    unsigned int reserved : 8;      // 8 unused bits
};                                  // total 16 bits, that is, 2 bytes

struct ControlRegister reg = {1, 5, 12, 0};
AdvantageDisadvantage
Considerable memory savingsaccess is slower (requires shifts and masks)
Direct correspondence with hardware registersbit order depends on the compiler
More readable code than manual masksthe address of a field cannot be taken with &

8Unions

A union looks like a structure, but all members share the same memory zone. The union's size is that of its largest member, and only one member is valid at any given time.

struct vs. union
struct S { int a; float b; char c; };   // sizeof = 12 (4 + 4 + 1 + padding)
union  U { int a; float b; char c; };   // sizeof = 4  (the largest member)

union U u;
u.a = 65;                    // written as an integer
printf("%c\n", u.c);         // read as a character: 'A'
                             // ...because it is the SAME memory zone
Only one member is valid at a timeWriting to one member destroys the value of the others. The union does not keep track of which member was written last - that is the programmer's responsibility, usually through an additional enum-typed field.
Typical useA union combined with a type indicator forms a "variant": a value that can be an integer, a real number, or a string, but not at the same time.

9Source code

students.c - structures and arrays of structures
#include <stdio.h>
#include <string.h>

typedef struct {
    char  name[50];
    int   age;
    float average;
} Student;

void print(const Student *s)         // we receive the address, not a copy
{
    printf("%-20s %3d years   average %.2f\n", s->name, s->age, s->average);
}

int main(void)
{
    Student group[3] = {
        {"John Smith",    20, 9.15f},
        {"Mary Johnson",  21, 8.70f},
        {"Radu Georgescu",20, 9.60f}
    };

    printf("Group list:\n");
    for (int i = 0; i < 3; i++) print(&group[i]);

    // computing the overall average
    float sum = 0;
    for (int i = 0; i < 3; i++) sum += group[i].average;
    printf("\nOverall average: %.3f\n", sum / 3);

    // finding the student with the highest average
    int pos = 0;
    for (int i = 1; i < 3; i++)
        if (group[i].average > group[pos].average) pos = i;
    printf("Highest average: %s\n", group[pos].name);

    printf("\nsizeof(Student) = %d bytes\n", (int)sizeof(Student));
    return 0;
}
state_enum.c - a state machine with an enumeration
#include <stdio.h>

typedef enum {
    STOPPED,        // 0
    STARTING,       // 1
    RUNNING,        // 2
    ERROR = 99
} State;

const char* stateName(State s)
{
    switch (s) {
        case STOPPED:  return "STOPPED";
        case STARTING: return "STARTING";
        case RUNNING:  return "RUNNING";
        case ERROR:    return "ERROR";
        default:       return "UNKNOWN";
    }
}

int main(void)
{
    State s = STOPPED;

    printf("Initial state: %s (%d)\n", stateName(s), s);

    s = STARTING;  printf("-> %s (%d)\n", stateName(s), s);
    s = RUNNING;   printf("-> %s (%d)\n", stateName(s), s);
    s = ERROR;     printf("-> %s (%d)\n", stateName(s), s);

    return 0;
}
alignment.c - experimentally checking the padding
#include <stdio.h>
#include <stddef.h>

struct Unfavorable { char c; int x; char d; };
struct Optimized    { int x; char c; char d; };

int main(void)
{
    printf("Unfavorable: sizeof = %d\n", (int)sizeof(struct Unfavorable));
    printf("  offset c = %d\n", (int)offsetof(struct Unfavorable, c));
    printf("  offset x = %d\n", (int)offsetof(struct Unfavorable, x));
    printf("  offset d = %d\n", (int)offsetof(struct Unfavorable, d));

    printf("\nOptimized:    sizeof = %d\n", (int)sizeof(struct Optimized));
    printf("  offset x = %d\n", (int)offsetof(struct Optimized, x));
    printf("  offset c = %d\n", (int)offsetof(struct Optimized, c));
    printf("  offset d = %d\n", (int)offsetof(struct Optimized, d));

    printf("\nSame members, different space!\n");
    return 0;
}
union.c - reinterpreting the same zone
#include <stdio.h>

union Converter {
    unsigned int  value;
    unsigned char bytes[4];
};

int main(void)
{
    union Converter c;
    c.value = 0x12345678;

    printf("Value: 0x%X\n", c.value);
    printf("Bytes in memory: ");
    for (int i = 0; i < 4; i++) printf("%02X ", c.bytes[i]);
    printf("\n");

    // on Intel/AMD processors (little-endian), 78 56 34 12 is printed
    if (c.bytes[0] == 0x78) printf("Little-endian system\n");
    else                    printf("Big-endian system\n");

    printf("\nsizeof(union) = %d bytes\n", (int)sizeof(union Converter));
    return 0;
}

10Code workshop

Structures group data of different types under a single name. In the panel on the right, a structure appears with all of its fields, and the address shows where it begins in memory.

An array of structures
#include <stdio.h>
#include <string.h>

typedef struct {
    char   name[20];
    int    age;
    double average;
} Student;

int main(void)
{
    Student group[3];
    int i;
    double sumAverages = 0;

    strcpy(group[0].name, "Popescu");  group[0].age = 19; group[0].average = 9.15;
    strcpy(group[1].name, "Ionescu");  group[1].age = 20; group[1].average = 7.40;
    strcpy(group[2].name, "Vasilescu"); group[2].age = 19; group[2].average = 8.80;

    printf("%-12s %6s %7s\n", "NAME", "AGE", "AVERAGE");
    for (i = 0; i < 3; i++) {
        printf("%-12s %6d %7.2f\n", group[i].name, group[i].age, group[i].average);
        sumAverages += group[i].average;
    }
    printf("\nGroup average: %.2f\n", sumAverages / 3);
    printf("sizeof(Student) = %d bytes\n", (int)sizeof(Student));
    return 0;
}
Exercise - enum and structures
#include <stdio.h>

typedef enum { OFF, ON, ERROR } State;

typedef struct {
    int   id;
    State state;
} Device;

const char* stateName(State s)
{
    /* Complete this: return "off", "on", or "error",
       depending on the value received. Use switch. */
    return "?";
}

int main(void)
{
    Device d[3] = { {1, ON}, {2, OFF}, {3, ERROR} };
    int i;

    for (i = 0; i < 3; i++)
        printf("device %d: %s\n", d[i].id, stateName(d[i].state));
    return 0;
}

11Exercises with automatic checking

This is where you write the code. The ✓ Check button runs your program on several data sets and shows you right away where the result differs. At the end you submit the track you chose, and the instructor grades it automatically.

Every exercise has the program already started, and the comments tell you what is left to add. Write the code, press ✓ Check and read what each failed test says. If you get stuck, open the hints one at a time. You may also print messages for the user (such as Enter n:); the test looks at what you print at the end.

P1

The Point structure

Complete the structure Point with two real fields, x and y. The program reads two points and prints the distance between them with two decimals.

input0 0 3 4
output5.00
#include <stdio.h>
#include <math.h>

struct Point {
    /* declare the fields here: double x, y; */
};

int main(void)
{
    struct Point a, b;
    scanf("%lf %lf", &a.x, &a.y);
    scanf("%lf %lf", &b.x, &b.y);

    /* Distance: sqrt((b.x - a.x)^2 + (b.y - a.y)^2).
       Print it with %.2f. */

    return 0;
}
P2

The value of the stock

Read n products, one per line: code name price stock. Compute the total value of the stock (the sum of price · stock) and print it with two decimals.

input2 1 mere 2.5 10 2 pere 3 4
output37.00
#include <stdio.h>

typedef struct {
    int code;
    char name[30];
    double price;
    int stock;
} Product;

int main(void)
{
    Product p[100];
    int n, i;
    double total = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d %29s %lf %d", &p[i].code, p[i].name, &p[i].price, &p[i].stock);

    /* Go through the array of structures and add p[i].price * p[i].stock
       to total. Print the total with %.2f. */

    return 0;
}
P3

Search by code

As in the previous exercise, read n products (code name price stock), then a code to search for. Print the name and price (with two decimals) of the product with that code, or not found.

input3 10 mere 2.5 1 20 pere 3 2 30 prune 4.75 3 20
outputpere 3.00
#include <stdio.h>

typedef struct {
    int code;
    char name[30];
    double price;
    int stock;
} Product;

int main(void)
{
    Product p[100];
    int n, i, c;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d %29s %lf %d", &p[i].code, p[i].name, &p[i].price, &p[i].stock);
    scanf("%d", &c);

    /* Look for the element with p[i].code == c. If you find it, print
       printf("%s %.2f\n", p[i].name, p[i].price); and stop searching.
       If it does not exist, print "not found". */

    return 0;
}
P4

Days of the week with enum

Read a number from 1 to 7 and print the name of the matching day (monday … sunday). For any other number print invalid. Use the enumeration from the skeleton in a switch.

input1
outputmonday
#include <stdio.h>

enum Day { MONDAY = 1, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };

int main(void)
{
    int n;
    scanf("%d", &n);

    switch (n) {
        case MONDAY: printf("monday\n"); break;
        /* Continue with TUESDAY ... SUNDAY (they automatically get 2 ... 7)
           and a default for "invalid". */
    }
    return 0;
}
P5

Adding two fractions

Read two fractions a/b and c/d as four positive integers a b c d. Print their sum as an irreducible fraction, in the form p/q.

input1 2 1 3
output5/6
#include <stdio.h>

struct Fraction { int num, den; };

int gcd(int a, int b) { while (b) { int r = a % b; a = b; b = r; } return a; }

int main(void)
{
    struct Fraction f, g, s;
    scanf("%d %d %d %d", &f.num, &f.den, &g.num, &g.den);

    /* s.num = f.num * g.den + g.num * f.den;
       s.den = f.den * g.den;
       then divide both fields by their gcd and print "%d/%d". */

    return 0;
}

Problems start from an empty main. The output format must be followed exactly (spaces and newlines do not matter unless the statement says otherwise), so do not print prompts. The visible tests cover only the simple cases; grading also runs hidden tests chosen to catch the edge cases.

A1

Products sorted by price

Read n (1 ≤ n ≤ 100) products code name price. Print them sorted by price ascending, and on equal price by code ascending, one per line: code name price (the price with two decimals). Use an array of structures and write the sort yourself.

input3 3 lapte 6.5 1 paine 3 2 oua 6.5
output1 paine 3.00 2 oua 6.50 3 lapte 6.50
#include <stdio.h>

int main(void)
{
    /* write your solution here */

    return 0;
}
A2

Student ranking

Read n (1 ≤ n ≤ 50) students: name grade1 grade2 grade3 (the name is one word). Print the students in descending order of their average, and on equal averages alphabetically by name, in the form name average (the average with two decimals). At the end print how many have an average of at least 5.

input3 Ion 5 6 7 Ana 9 9 10 Dan 4 4 5
outputAna 9.33 Ion 6.00 Dan 4.33 2
#include <stdio.h>

int main(void)
{
    /* write your solution here */

    return 0;
}
A3

Union: the bytes of an integer

Using a union between an unsigned int and an array of 4 unsigned char, read an unsigned integer and print its 4 bytes in the order they sit in memory, in hexadecimal with two digits each (lower case). The lab computers are little-endian.

input1
output01 00 00 00
#include <stdio.h>

int main(void)
{
    /* write your solution here */

    return 0;
}
A4

Complex numbers

Define a structure for complex numbers and functions for the sum, the product and the modulus. Read two complex numbers a b c d (that is, a + bi and c + di) and print, one per line, with two decimals: the sum and the product in the form x y, then the modulus of the product.

input1 2 3 4
output4.00 6.00 -5.00 10.00 11.18
#include <stdio.h>

int main(void)
{
    /* write your solution here */

    return 0;
}

12Work tasks

  • Define a Product structure (code, name, price, stock) and an array of products.
  • Write functions to print the list, compute the total stock value, and search by code.
  • Sort the array of structures by price, using an exchange sort.
  • Use sizeof and offsetof to check where padding bytes appear.
  • Reorder the structure's members and measure the space savings obtained.
  • Define an enumeration for the days of the week and print the day's name from a number.
  • Build a structure with bit fields describing an 8-bit control register.
  • Use a union to determine whether the system is little-endian or big-endian.

13Extended application

ExtensionImplement a small student database, with dynamically allocated structures: adding, removing, searching by name, sorting by average, and saving the list to a file. Add an enum-typed member for the student's status (funded, fee-paying, expelled) and a bit field that stores the results of eight exams. Compare the size of the structure before and after optimizing the order of its members.

14Review questions

15Resources