32. Операторы преобразования типов (конверторы).

Конвертер – функция-член класса, которая преобразует тип объекта класса в некоторый другой тип. Конвертер имеет следующий прототип:

operator тип ();

Параметр тип задаёт тип данных, к которому приводится объект. Этот тип может быть как встроенным типом данных, так и типом данных, определённым пользователем.

Конвертер может вызываться как явно, так и неявно при преобразованиях типов данных. Запишем оператор преобразования типов для дробей:

В rational.h:

operator double () const;

В rlib.cpp:

ratio:: operator double () const

{return (double) n/ (double) d;}

В rtest.cpp:

ratio dr4 (3, 5);

double d = 1.1 + dr4;

32. Структура данных – стек.

В информатике и математике для решения задач разработан и используется ряд специальных структур данных. К таким структурам относятся матрицы, множества, стеки, очереди, деревья и т.д. в языках программирования реализация части структур данных осуществляется на встроенном уровне. Например, в языке Delphi (Pascal) реализованы такие структуры, как матрицы, массивы, множества. В языке С/С++ реализация структуры данных множества отсутствует, но присутствуют массивы и матрицы.

Однако имеется ряд структур, которые не реализованы в языках программирования. Это стек, очередь, деревья и т.д. Поэтому для того, чтобы использовать эти структуры при решении задач, их моделируют с помощью средств языка программирования. Чаще всего для моделирования используют массивы одномерные и многомерные или же динамические структуры, память под которые выделяется в процессе работы программы.

Структура данных стек представляет собой упорядоченное множество элементов, добавление и удаление которых из этой структуры происходит по следующему правилу: первым всегда удаляется элемент, который последним был добавлен в эту структуру. Все элементы должны быть однотипны. Количество элементов конечно. По сути, структура данных стек напоминает собой колодец, в который поочерёдно помещаются и из которого достаются элементы. Элемент, который был добавлен последним, всегда лежит на вершине стека. Примером задачи, в которой используется стек, является проверка баланса скобок в выражении. Встречая открывающую скобку, мы кладём её в стек. Затем, встречая закрывающую скобку, мы достаём из стека открывающую скобку. Если стек пуст после завершения процедуры, то баланс скобок соблюдён.

Ещё один пример. На железнодорожном перегоне стоят белые и чёрные вагоны вперемешку. Используя тупик, поставить вагоны в порядке белый – черный – белый … Ставим вагоны. Первый просто оставляем, а дальше проверяем, совпадает ли цвет следующего вагона с предыдущим. Если нет, то помещаем его к предыдущему вагону, а если да, то помешаем его в стек, и проверяем дальше.

Структура данных стек реализуется в языке С с помощью статических массивов, динамических массивов и динамических переменных.

Рассмотрим реализацию задачи проверки баланса скобок с помощью смоделированной на статическом массиве структуры данных стек. Для работы со структурой данных необходимо написать несколько функций:

1. создание стека;

2. помещение элемента в стек;

3. извлечение элемента из стека;

4. проверка стека на пустоту;

5. проверка, заполнен стек полностью или нет.

Замечание: последняя функция реализуется только при моделировании стека через массив.