3 Курс Лабораторная работа № 1 Реализация программы с использованием контейнерного класса stack stl

Цель работы: научиться использовать контейнерные классы стандартной библиотеки шаблонов в C++.

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

Инструкции к выполнению:

Инициализацию лабиринта производить в коде программы.

Теоретическая справка

Стек (stack) представляет собой структуру данных, которая допускает только две операции, изменяющие ее размер: push (для добавления элемен­та в конце) и pop (для удаления элемента в конце). Иными словами, стек работает по принципу «последний пришел - первый ушел» (также назы­ваемому LIFO от английского Last In - First Out). Кроме push и pop для стека определены также функции-члены empty и size, имеющие обычное значение, и top для доступа к последнему элементу.

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

Лабораторная работа № 2 Ассоциативные контейнеры stl

Цель работы: закрепить навыки работы с ассоциативными контейнерными классами стандартной библиотеки шаблонов в C++.

Задание: Реализовать программу-словарь, предполагающую загрузку пар слов-синонимов на двух языках из файла и выводящую по введенному пользователем слову его перевод. Для хранения пар слов использовать ассоциативный контейнер map, а для отдельных слов объекты типа string.

Теоретическая справка

Последовательный контейнер содержит упорядоченный набор элементов одного типа. Можно выделить два основных типа контейнеров – вектор (vector) и список (list). Третий последовательный контейнер – двусторонняя очередь (deque) – обеспечивает ту же функциональность, что и vector, но особенно эффективно реализует операции вставки и удаления первого элемента. deque следует применять, например, при реализации очереди, из которой извлекается только первый элемент.

Ассоциативный контейнер эффективно реализует операции проверки существования и извлечения элемента. Два основных ассоциативных контейнера – это отображение (map) и множество (set). map состоит из пар ключ/значение, причем ключ используется для поиска элемента, а значение содержит хранимую информацию. Телефонный справочник хорошо иллюстрирует понятие отображения: ключом является фамилия и имя абонента, а значением – его телефонный номер.

Элемент контейнера set содержит только ключ, поэтому set эффективно реализует операцию проверки его существования. Этот контейнер можно применить, например, при реализации системы текстового поиска для хранения списка так называемых стоп-слов – слов, не используемых при поиске, таких, как и, или, не, так и тому подобных. Программа обработки текста считывает каждое слово и проверяет, есть ли оно в указанном списке. Если нет, то слово добавляется в базу данных.

В контейнерах map и set не может быть дубликатов – повторяющихся ключей. Для поддержки дубликатов существуют контейнеры multimap и multiset. Например, multimap можно использовать при реализации такого телефонного справочника, в котором содержится несколько номеров одного абонента.