Тема 8

Класс "Очередь" на основе связного списка

1. Создать класс Queue для работы со структурами типа "Очередь". Тип элемента очереди должен быть представлен шаблоном.

Очередь является структурой данных типа "Первый пришел - первый вышел" (FIFO - first-in, first-out). Действие очереди напомина-ет работу эскалатора в метро. Класс Queue построить на основе связ-ного списка.

2. Для создания объектов и правильного их удаления предусмо-треть соответствующие конструкторы и деструкто­р. Предусмотреть в классе конструктор копирования.

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

- динамическое присваивание, символ "=" ;

- ввод очереди из файла, символ "<<";

- вывод очереди в файл, символ ">>".

4. Предусмотреть следующие функции - члены класса:

5. int Queue::num() - количество элементов, которые находятся в очереди в данный момент;

6. int Queue::max() - количество мест в очереди (максималь-но возможное количество элементов, помещаемых в очередь);

7. bool Queue::empty() - проверка, является ли очередь пустой;

8. elem& Queue::pop() - извлечь первый элемент очереди;

9. void Queue::push(elem&) - добавить новый элемент в конец очереди;

elem* Queue::find(elem&) - найти заданный элемент в очереди и вернуть его адрес, при отсутствии элемента - вернуть значение NULL;

5. Разработать демонстрационно-тестирующую программу. Вы-полнить тестирование созданных программных средств.

Литература: [17]

Тема 9

Класс "Множество" на основе динамического массива

1. Для программирования операций с объектами типа "Множество" создать класс Set. Тип элемента множества представить шаблоном. Множество представляет собой набор элементов, каждый из которых является уникальным, повторение элементов не допускает-ся. В качестве базовой структуры для создания класса "Множество" использовать одномерный динамический массив.

2. Для создания объектов типа "Множество", их инициализации и правильного их удаления предусмотреть следующие функции класса:

2.1. Конструктор без параметров.

2.2. Конструктор копирования.

2.3. Конструктор для инициализации создаваемого объекта с помощью внешнего массива.

2.4. Деструктор.

3. Для программирования операций над объектами типа "Множество" выполнить перегрузку символов операций, указанных ниже.

3.1. Динамическое присваивание, символ "=". При выполне-нии операции вида A = B, где A и B имеют тип "Множество", объект A должен стать идентичным объекту B. Значение, возвращаемое операцией - ссылка на левый операнд.

3.2. Проверка, являются ли два множества одинаковыми, символ "==". Операция вида A == B, где A и B имеют тип "Множество", должна возвращать значение true, если множества A и B идентичны, и значение false в противном случае.

3.2. Объединение множеств, символ "+". Операция вида A + B, где A и B имеют тип "Множество", должна возвращать множество, которое является объединением множеств A и B.

3.3. Пересечение множеств, символ "*". Операция вида A * B, где A и B имеют тип "Множество", должна возвращать множество, которое является пересечением множеств A и B.

3.4. Вычитание множеств, символ "-". Операция вида A - B, где A и B имеют тип "Множество", должна возвращать множество, которое является разностью множеств A и B.

3.5. Отношение включения, символ "<=". Операция вида A <= B, где A и B имеют тип "Множество", должна возвращать значение true, если множество A является подмножеством B, и значение false в противном случае.

3.6. Ввод множества из файла, символ ">>". Операция вида f >> A, где f - переменная типа ifstream, а A - переменная типа "Множество", должна приводить к считываию значения A из потока f. Операция должна возвращать ссылку на левый операнд (поток f).

3.7. Вывод множества в файл, символ "<<". Операция вида f << A, где f - переменная типа ofstream, а A - переменная типа "Множество", должна приводить к записи значения A в поток f. Операция должна возвращать ссылку на левый операнд (поток f).

4. Предусмотреть следующие функции - члены класса:

5. void Set::include(type x) - добавить новый элемент к множеству;

6. void Set::exclude(type x) - удалить значение x из множества;

bool Set::find(type x) - проверить, содержит ли множество заданный элемент.

5. Разработать демонстрационно-тестирующую программу. Выполнить тестирование созданного класса.