Previous Next ua

Laboratory Training 1

Working with Enumerations and Structures

1 Training Tasks

1.1 An Enumeration for Presenting the Months of the Year

Create an enumeration to represent the months of the year. Implement and demonstrate overloaded operators ++ so -- that after December there is January and before January there is December.

1.2 3D-Points

Create a structure to describe a 3D-point. Write a program that calculates distance between two 3D-points. To calculate the distance, create a function with two parameters of structure type to represent the points.

1.3 Representation and Processing Students Data

Create a structure for presenting data concerned with student. The structure should contain the following data members:

student identity number (unsigned int);
surname (array of characters);
marks of the last session in the form of an array of integers from 0 to 100 (marks on subjects).

Implement a function that outputs student data to the console window. The first parameter of the function should be a structure that describes the student.

Implement functions that receive an array of pointers to student and the length of the array and execute

array sorting according to the criterion specified in the individual task;
searching for data about students that meet the condition given in the individual task;
displaying all items of the array in the console window.

When sorting an array of structures, swap the elements of the array of pointers instead of swapping two structures.

Create an array of students. Create an array of pointers to students, filling it with addresses of structures from the array of students. Demonstrate sorting and searching for students.

Individual tasks:

Index in the List of Students	Sorting Conditions	Data Selection Conditions
1	Alphabetically	With an average score in the interval "64" – "74"
2	Increasing the average score	With a surname length of more than 7 characters
3	Decreasing the length of surname	With an average score in the interval "90" – "100"
4	Descending numbers of student identity numbers	Surname starts with the letter "A"
5	Decreasing the average score	Surname ends with the letter "a"
6	Increasing the sum of scores	With the odd length of surname
7	Increasing the length of surname	With odd numbers of student identity numbers
8	Alphabetically	With even numbers of student identity numbers
9	Alphabetically reversed	More "A" grades than "D" grades
10	Increasing numbers of student identity numbers	Surname contains the letter "e"
11	Decreasing the product of scores	With the odd length of surname
12	Increasing the product of scores	With a surname length of less than 8 characters
13	Alphabetically	With an even sum of scores
14	Alphabetically reversed	With odd numbers of student identity numbers
15	Alphabetically	With an average score in the interval "75" – "81"
16	Increasing the average score	With a surname length of less than 7 characters
17	Increasing the length of surname	With an average score in the interval "82" – "89"
18	Increasing numbers of student identity numbers	Surname starts with the letter "A"
19	Increasing the average score	Surname ends with the letter "a"
20	Increasing the sum of scores	With the odd length of surname
21	Increasing the length of surname	With even numbers of student identity numbers
22	Alphabetically reversed	With even numbers of student identity numbers
23	Alphabetically	More "A" grades than "E" grades
24	Increasing numbers of student identity numbers	Surname contains the letter "o"
25	Decreasing the product of scores	With the even length of surname
26	Decreasing the product of scores	With a surname length of less than 9 characters
27	Alphabetically reversed	With an odd sum of scores
28	Alphabetically	With odd numbers of student identity numbers

1.4 Working with a Linked List

You should write a program that provides file input and output and implements an assignment of Laboratory training # 4 of the course "Programming Basics (Part 1)". You should implement following steps:

definition of a constant (n) which determines column count of two-dimensional array
opening file for reading (file should be prepared using some text editor)
reading integer values until the end of file and storing them in the linked list
creation of two-dimensional array in free store; row count should be calculated based on amount of integer values read from file and count of columns
filling of two-dimensional array row by row; missing elements of the last row should be set to zeroes;
removing elements of linked list from free store
implementation of the task of Laboratory training # 4 of the course "Programming Basics (Part 1)"
storing results in a new file
removing both arrays using delete operators.

2 Instructions

2.1 User Defined Types

The C++ language allows you to create your own types, which use may not be less convenient and should be more expressive than using existing standard types. The C++ language allows you to create your own types, the use of which can be no less convenient and more expressive than the use of existing standard types.

In most cases you should use classes for creation of custom types. But sometimes you can also use other language structures, such as enumerations, structures, and unions.

2.2 Enumerations

The enumeration type defines a set of integer constants. The enumeration can be defined using enum keyword followed by list of elements separated by commas. The list of elements must be enclosed in braces. By default, the first constant has a value of zero, the second is equal to one, and so on.

There are named and unnamed enumerations. An unnamed enumeration is essentially a list of constants. For example,

enum { red, green, blue };

Such definition can be used instead of a set of constant definitions:

const int red   = 0;
const int green = 1;
const int blue  = 2;

You can set necessary value explicitly. Each successive constant is one larger than the value of the previous one:

enum { one = 1, three = 3, four, nine = 9, ten }; 
// four == 4, ten == 10

Named enumeration defines a new data type. This new type can be used for definition of variables:

enum Colors { red, green, blue };
Colors c = blue;

Unlike typedef definition, user defined data types (including enumerations) are not aliases to existing types. For example, we cannot assign integer values to variables of Colors type, only the value of red, green, and blue are allowed. But contrary, assigning values of Colors type to integer variables are quite correct. Variables of such types can be used in expressions.

Colors c;
c = 1;     // Error!
c = green; // OK
int i = c; // OK
i = c + 1; // OK

You can overload some operations applied to enumerations, such as ++ and --.

Operator overloading is a powerful mechanism for defining behavior for objects of user defined types. Thanks to the operator overloading, you can work with objects using almost all operators of the C++ language. For example, if the object a has an overloaded operator of adding an integer value to it, the program can use the expression a + 1. This way, you can create types of objects, working with which is very close to working with primitive types. Almost all operations can be overloaded for classes, only some for enumerations.

In order for the operator to be considered overloaded, it is necessary to create a so-called operator function. The name of this function consists of the operator keyword, followed by the operator we want to overload. The arguments of the operator function are the operands of the operation. The syntax of operator functions will be discussed in detail when considering the syntax of classes. In example 3.1, operator overloading is implemented for the "Day of the week" enumeration.

Traditional enumerations add constants to the global scope, increasing the probability of name conflict. To avoid such conflicts, modern versions of C++ usually use a prefix (name of the enumeration type and scope resolution operation) to refer to individual list constants:

Colors c = Colors::green;

Starting with version C++11, it is possible to limit the visibility of enumeration items to the scope of the enumeration itself. You can create a special kind of enumeration, a scoped enum, adding the keyword class or struct after enum:

enum class Colors { red, green, blue };

You can now access list enumeration only through the enumeration name, because items are no longer global constants:

Colors c1 = Colors::green;
Colors c2 = green; // Error!

2.3 Structures

Structures are user-defined composite types. They are composed of data members that can have different types. Such group can be treated as a single entity. You can define a new structure data type and create variables of this type later. The struct keyword is used for creation of a new structure type:

struct Country
{
    char   name[20];
    double area;
    long   population;
};                     // semicolon is obligatory

Country France;        // France is a variable of Country type

Structures, like other user defined data types, are commonly defined in global scope. The C++ language syntax allows you to create variables of a new type directly after its definition:

struct Country
{
    char   name[20];
    double area;
    long   population;
} France;             // France is a variable of Country type

Such definition is not recommended. The better approach assumes separate definition of data types and variables.

When you create a variable of a structure type, can initialize it. The values of elements are initialized in the order of definition:

Country France = {"France", 551695, 64590000 };

Unlike arrays, assignment operator accomplishes elementwise copying of one structure to another:

Country someCountry;
someCountry = France; // elementwise copying

You can access particular data fields using dot operator (".").

cout << someCountry.area;

You can create pointers to structures. To access elements of structures, to which some pointer points, special operator -> is used. For example:

Country *pCountry;
pCountry->area = 551695;

Unlike arrays, structure type objects are transferred to functions by value. That means that function handles with copies of objects transferred to it. This also applies to array items that are located inside the structure. They are also copied when assigning one structure to another or when passing parameters. Consider the following example. The structure contains an array of fixed length n. A special auxiliary function print() outputs items of an array of integers:

const int n = 4;

struct Array
{
    int arr[n];
};

void print(int *arr_n)
{
    for (int* p = arr_n; p < arr_n + n; p++) {
        cout << *p << " ";
    }
    cout << endl;
}

The tryToModify() function gets the structure as a parameter, changes the values of the elements of the array, increasing them by one, and then displays the values of the elements on the screen:

void tryToModify(Array a)
{
    for (int i = 0; i < n; i++)
    {
        a.arr[i]++;
    }
    print(a.arr); // 2 3 4 5
}

The main() function initializes the structure, calls the function, and outputs the values of the array elements after the call:

int main()
{
    Array a = { { 1, 2, 3, 4 } }; // nested braces are required
    tryToModify(a);
    print(a.arr); // 1 2 3 4
}

The values of the items have not changed. If you want to modify structure objects within function's body, you should use reference type arguments:

void tryToModify(Array &a)
{
    for (int i = 0; i < n; i++)
    {
        a.arr[i]++;
    }
    print(a.arr); // 2 3 4 5
}

int main()
{
    Array a = { { 1, 2, 3, 4 } };
    tryToModify(a);
    print(a.arr); // 2 3 4 5
}

Even if you don't need to modify data within function, references to constant objects of struct type improve productivity of your program because of copying address instead of huge data block:

struct LargeData
{
    // Some large structure
};

void someFunc(const LargeData& data) 
{ 
    ...
};

If your structure contains a series of variables that can have only a very small number of possible values, you may save some room using bit fields, specifying the maximum field size in bits. The declaration of a bit field contains name of some integer type, followed by field name, followed by colon, followed by size of a bit field:

struct Flags 
{ 
    unsigned int logical : 1; // one bit 
    unsigned int tinyInt : 3; // tiny integer
};

By using bit fields, you can store several values in one byte. This takes no effect if bit fields are separated with non-bit fields. You can also use bit fields in class definitions.

In contrast to C programming language, structures in C++ can contain member functions and support other features of classes. In spite of this, structures are typically used for grouping data, but not instead of classes.

2.4 Unions

Union is a structure in which all data members are located at the same address. At any given time the only data member can be stored in the union. In the example below, the object of the union can save real or integer value, but not both simultaneously. An attempt to assign a value to the second element causes damage of the first element, because actually the memory allocated to only one of the values.

union FloatAndInt
{
    float f;
    int   i;
};

FloatAndInt fi;
fi.i = 2;
fi.f = 100;
cout << fi.i << endl; // 1120403456
fi.i = 3;
cout << fi.f << endl; // 4.2039e-45

Union can be used to create arrays of elements which have different types. In addition, you can use the union to encode information and to analyze internal data representation. In the above example the number 1120403456 if it is converted to a binary system shows the internal representation of the floating point value 100.0.

You can create anonymous unions:

union { int a; char* p; };
a = 1;
p = "name"; // a and p cannot be used simultaneously

Union can contain member functions.

Possibilities of unions are significantly limited. Using polymorphism provides a more correct way to store data in arrays of different types, so unions are rarely used now.

2.5 Sorting Arrays of Structures using Pointers

Structures that describe real-world objects can be quite large in size. Accordingly, copying the structure into a new variable can take a long time. If, for example, the program sorts an array of structures by a certain criterion, such copying can be performed very many times. Moreover, if you sequentially sort by different sorting criteria, this will increase the program execution time even more.

There is a way to improve the performance of programs that work with arrays of structures. The idea is as follows:

we create an auxiliary array of pointers, which we fill with the addresses of the elements of the array of structures;
in the sorting algorithm, or in another algorithm related to the exchange of places of elements of the structure array, the pointer array is modified;
structures are accessed through an array of pointers rather than directly.

This approach is demonstrated in example 3.3.

2.6 Use of Linked Lists

One of widespread problems solved by programmers is representation and processing of sequences of data. Most real world problems can be solved using arrays. But sometimes use of arrays is not sufficient because of the following disadvantages:

adding new elements to the end of an array cannot be allowed without extra reserved elements; if there are no such elements, we must allocate a new array and copy contents of an old array into new allocation
adding elements to the middle or removing of elements typically requires copying of numerous data elements.

Another approach to representation of sequences provides so called linked list, or chain. To implement linked list, you should create structure that contains data itself and pointer to another element of this type:

struct Link
{
    Data data;
    Link *next;
};

where Data is some known data type. To add a new element between existing ones, you must create this element in free store and then change values of pointers in neighbor elements.

For example, to store integer values, you should create the following structure (chain link):

struct Link
{
    int data;
    Link *next;
};

In order to create a linked list, you need to create a pointer to the beginning of the list (first link). For convenience, you can also save the last pointer separately. In addition, you will need a pointer to a specific current link. At first, these pointers do not point anything:

Link* first = 0;
Link* last = 0;
Link* link = 0;

You can now add the first item to the future list. Suppose you need to add the value of an integer variable k. Create a new link in free store and point to it:

int k = 1;
link = new Link();
link->data = k;
link->next = 0;
first = link;
last = link;

Then, if necessary, add the second and other elements to the end of the list:

k = 2;
link = new Link();
link->data = k;
link->next = 0;
last->next = link;
last = link;

You can show the values of list items using a loop:

link = first;
while (link != 0)
{
    std::cout << link->data << " ";
    link = link->next;
}
std::cout << std::endl;

If you need to add an item inside the list, you do not need to rewrite the existing items to a new location. Just change the pointers stored in the list items. For example, we want to add a new element with a value of 3 after the first:

Link* previous = first;
k = 3;

Create a new element and change pointers:

link = new Link();
link->data = k;
link->next = previous->next;
previous->next = link;

This is how you can add a link inside a list:

Similarly, you can remove an item after specified link. Do not forget to delete the item from free store:

link = previous->next;
previous->next = link->next;
delete link;

The removal of the link can be represented as follows:

The following cycle allows you to delete all existing items:

while (first)
{
    link = first;
    first = first->next;
    delete link;
}

Example 3.4 of this lesson shows how to work with linked lists.

There are also doubly linked lists – lists in which each element points not only to the next but also to the previous element. In addition, there are circular lists (singly linked and doubly linked).

Linked list is a kind of so called dynamic data structures. Other examples of such structures are queues, stacks and binary trees. Example of a binary tree:

3 Sample Programs

3.1 1 An Enumeration for Presenting the Days of Week

Suppose there is an enumeration type :

enum DayOfWeek {
    Sunday, 
    Monday, 
    Tuesday, 
    Wednesday,
    Thursday, 
    Friday, 
    Saturday
};

To overload the prefix ++ operator, in the same namespace where the type DayOfWeek is defined, the following function must be implemented::

// Overloading the prefix ++ operator
DayOfWeek operator++(DayOfWeek& day)
{
    if (day == Saturday) // special case
    {
        day = Sunday;
    }
    else
    {
        day = (DayOfWeek) (day + 1); // all other days
    }
    return day;
}

To overload the postfix ++ operator, we need to implement a function with two parameters:

// Overloading the postfix ++ operator
DayOfWeek operator++(DayOfWeek& day, int)
{
    DayOfWeek oldDay = day;// save the previous day
    operator++(day);       // call the previous function
    return oldDay;         // return the previous day
}

In the list of formal parameters int is a type of parameter that is not used, but its presence allows the compiler to distinguish a postfix operation from a prefix operation.

The entire code of the program will be as follows:

#include <iostream>

enum DayOfWeek {
    Sunday, 
    Monday, 
    Tuesday, 
    Wednesday,
    Thursday, 
    Friday, 
    Saturday
};

// Overloading the prefix ++ operator
DayOfWeek operator++(DayOfWeek& day)
{
    if (day == Saturday) // special case
    {
        day = Sunday;
    }
    else
    {
        day = (DayOfWeek) (day + 1); // all other days
    }
    return day;
}

// Overloading the postfix ++ operator
DayOfWeek operator++(DayOfWeek& day, int)
{
    DayOfWeek oldDay = day;// save the previous day
    operator++(day);       // call the previous function
    return oldDay;         // return the previous day
}

// Getting the names of the days of the week
const char* getName(DayOfWeek day)
{
    switch (day)
    {
        case Sunday: 
            return "Sunday";
        case Monday:
            return "Monday";
        case Tuesday:
            return "Tuesday";
        case Wednesday:
            return "Wednesday";
        case Thursday:
            return "Thursday";
        case Friday:
            return "Friday";
        default:
            return "Saturday";
    }
}

int main()
{
    // Sequentially output the days from Wednesday to the following Monday
    for (DayOfWeek d = Wednesday; d != Tuesday; d++)
    {
        std::cout << getName(d) << "\n";
    }
    return 0;
}

3.2 Distance Between Points

In the following example, we create structure which represents point on the screen. The program calculates distance between two points:

#include <iostream>
#include <cmath>

struct Point
{
    int x, y;
};

double sqr(double x)
{
    return x * x;
}

double distance(Point p1, Point p2)
{
    return std::sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}

int main()
{
    Point p1 = { 1, 2 };
    Point p2 = { 4, 6 };
    std::cout << distance(p1, p2);
    return 0;
}

3.3 Working with an Array of Structures

The program we will create describes the structure for representing the city. The city is described by its name, the name of the country in which it is located, the name of the region where the city is located and the number of inhabitants.

The program should create an array of several cities and implement the following functions:

sorting of cities by population;
search for cities that belong to a certain region (region);
display of information about cities.

For a better understanding of the code and to ensure the possibility of its multiple use, individual actions (sorting, searching, output) should be implemented as separate functions. To increase the efficiency of working with data, sorting is performed not for an array of cities, but for an array of pointers to cities.

The program code will be as follows:

#include <iostream>

// Structure for describing the city
struct City
{
    char name[30];
    char country[30];
    char region[30];
    int population;
};

// Sort by population
// Instead of modifying the array of cities, we modify the array of pointers
void sortByPopulation(City** arr, int size)
{
    bool mustSort; // repeat sorting
                   // if mustSort is true
    do
    {
        mustSort = false;
        for (int i = 0; i < size - 1; i++)
        {
            if (arr[i]->population > arr[i + 1]->population)
                // Swap items
            {
                City* temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                mustSort = true;
            }
        }
    } 
    while (mustSort);
}

// Display data about the city.
// To improve efficiency, we use reference
// to a constant object
void printCity(const City& city)
{
    std::printf("City: %s. Country: %s. Region: %s. Population: %d\n",
        city.name, city.country, city.region, city.population);
}

// Display data about all cities.
// We access cities through an array of pointers
void pintCities(City** arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        printCity(*arr[i]);
    }
    std::cout << "\n";
}

// Display data about cities,
// which are in a certain region
void printIf(City cities[], int size, const char* region)
{
    for (int i = 0; i < size; i++)
    {
        if (std::strcmp(cities[i].region, region) == 0) {
            printCity(cities[i]);
        }
    }
}

int main()
{
    const int n = 4;
    
    // Create and fill the array of cities:
    City cities[n] = { 
        { "Kharkiv", "Ukraine", "Kharkiv region", 1421125 },
        { "Poltava", "Ukraine", "Poltava region", 284942 },
        { "Lozova", "Ukraine", "Kharkiv region", 54618 },
        { "Sumy", "Ukraine", "Sumy region", 264753 }
    };
    
    // Create and fill an array of pointers:
    City* pointers[n];
    for (int i = 0; i < n; i++)
    {
        pointers[i] = &cities[i];
    }

    pintCities(pointers, n);
    sortByPopulation(pointers, n);
    pintCities(pointers, n);
    printIf(cities, n, "Kharkiv region");
    return 0;
}

As can be seen from the code, the elements of the array of pointers are swapped during sorting. Nothing changes in the structure array.

3.4 Reverse Order

The following program reads floating point numbers from a text file and puts these numbers into a new file in reverse order. Data are read until the end of file. During data loading, a temporary chain is used. A structure called Link is used for representation of particular links of a chain. Loaded data are copied into a new array, and then temporary chain should be destroyed.

#include<iostream>
#include <fstream>

using namespace std;

// A link:
struct Link
{
    double data;
    Link *next;
};

// The function reads numbers from the specified file
// and returns a pointer to the initial item of the array.
// The array is created inside the function, its items
// are located in the free store
// The parameter count after the function completes contains the length of the array
double *readFromFile(const char *fileName, int &count)
{
    // Prepare the linked list to work and create a file stream:
    Link *first = 0;
    Link *last = 0;
    Link *link;
    ifstream in(fileName);
    double d;
    count = 0;      // counter of numbers read from the file
    while (in >> d) // read to the end of the file
    {
        count++;
        // Create a new list item:
        link = new Link;
        link->data = d;
        link->next = 0;
        if (last == 0)
        {
            first = link;
        }
        else
        {
            last->next = link;
        }
        last = link;
    }
    // Create and fill an array of numbers:
    double *arr = new double[count];
    link = first;
    for (int i = 0; i < count; i++)
    {
        arr[i] = link->data;
        link = link->next;
    }
    // Deleting elements of the linked list from the free store:
    while (first)
    {
        link = first;
        first = first->next;
        delete link;
    }
    return arr;
}

// Writes the elements of the array arr of length count
// to the specified text file
void outToFile(const char *filename, double *arr, int count)
{
    ofstream out(filename);
    for (int i = count - 1; i >= 0; i--)
    {
        out << arr[i] << " ";
    }
}

int main()
{
    int count = 0;
    double *arr = readFromFile("data.txt", count);
    outToFile("results.txt", arr, count);
    delete [] arr;
    return 0;
}

4 Exercises

Define structure for representation of two integers, then create and test function that gets structure-type argument and calculates product of structure's element.

5 Quiz

What syntactic constructions C++ provides to create user defined types?
What is use of anonymous enumerations?
What is a scoped enum?
What are the features of unions and for what they are used?
What are structures?
What is the difference between structures and arrays?
Why do you need to place semicolons after brace that closes structure's body?
How to transfer structures to functions?
What are bit fields?
In what cases bit fields enhance the effectiveness of the program?
Why is it appropriate to use arrays of pointers when sorting arrays of structures?
What are dynamic data structures?
What are the advantages of lists compared to arrays?
What are the disadvantages of lists compared to arrays?

Previous Next

Programming Basics (Part 2)

Developed by Leo V. Ivanov

Laboratory Training 1 – Working with Enumerations and Structures