Тема 5

Класс для работы со структурами типа "Связный список"

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

Элемент однонаправленного связного списка содержит значение некоторого типа, которое он сохраняет, и адрес следующего элемента списка (указатель next). Значение указателя next, который содержится в последнем элементе списка, устанавливается равным значению NULL .

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

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

- динамическое присваивание для переменных типа List, символ "=" ;

- конкатенация (объединение двух связных списков в один), символ "+" ;

- проверка двух связных списков на совпадение, символ "==";

- ввод списка из файла, символ "<<";

- вывод списка в файл, символ ">>".

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

5. int List::size() - количество элементов списка;

6. elem& List::front() - возвращает ссылку на первый элемент;

elem& List::back() - возвращает ссылку на последний элемент;

5. void List::push_back(const elem&) - добавить новый элемент в конец списка;

6. elem List::pop_back() - извлечь последний элемент;

7. void List::push_front(const elem&) - добавить новый элемент в начало списка;

8. elem List::pop_front() - извлечь первый элемент;

bool List::find(const elem&) - проверить, есть ли заданный элемент в списке;

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

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

Тема 6

Класс для работы со структурами типа "Двухсвязный список"

Тема 7

Класс "Очередь" на основе одномерного массива

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

Очередь является структурой данных типа "Первый пришел - первый вышел" (FIFO - first-in, first-out). Действие очереди напомина-ет работу эскалатора в метро. Класс Queue построить на основе одно-мерного массива. Размер массива определяет максимальное количест-во элементов, помещаемых в очередь. Размер массива должен опреде-ляться при создании объекта типа 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&) - добавить новый элемент в конец очереди;

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

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