Предлагаемые этапы выполнения работы
1. Выбор наиболее подходящего стандартного контейнера данных (или группы контейнеров).
2. Выделение классов и функций, разрабатываемых в рамках программы.
3. Реализация классов и функций.
4. Отладка программы.
Теоретический материал, необходимый для выполнения лабораторной работы
Описание работы с классами в языке программирования C++
См. методические указания к лабораторной работе №2.
Основные контейнеры библиотеки STL
Контейнеры библиотеки STL подробно описаны в учебно-методическом пособии [1]. В STL воплощены все основные контейнеры – массив (std::vector), список (std::list), бинарное дерево поиска (std::set, std::multiset), словарь (std::map, std::multi_map), хэш-таблицы (std::hash_set, std::hash_multiset, std::hash_map , std::hash_multimap), двусторонняя очередь (std::deque), стеки и очереди (std::stack, std::queue), очереди с приоритетами (std::priority_queue)
Основные правила выбора контейнера для использования могут быть сформулированы следующим образом:
1. Если для задачи достаточно функциональности одного из контейнеров с жестко ограниченным набором операций (std::stack, std::queue, std::priority_queue) – используйте этот контейнер.
2. Если наиболее частая операция с контейнером – это поиск определенного значения (и выполнение тех или иных операций с ним) – целесообразно использование контейнеров, построенных на бинарном дереве (std::set, std::multiset, std::map, std::multi_map) или на хэш-таблице (std::hash_set, std::hash_multiset, std::hash_map , std::hash_multimap). Пожалуй, это наиболее частый случай.
3. Если Вы собираетесь выполнять операции, требующие доступа по индексу (сортировать массив по разным критериям, использовать индекс в массиве как идентификатор объекта, потому что в данной задаче он не меняется) – Вы можете использовать std::vector.
4. Если набор операций ограничивается добавлением элементов, и операциями над набором, реализуемыми стандартными механизмами STL (вызов функции для всех элементов, удаление всех соответствующих условию, …) – лучшим вариантом может быть std::list.
Лабораторная работа №4. Использование стандартных реализаций алгоритмов STL
Задачи работы
Задачами данной лабораторной работы являются:
1. Контроль освоения студентами теоретического материала (информации о стандартных алгоритмах STL).
2. Закрепление навыков использования механизмов стандартной библиотеки при разработке программного обеспечения.
3. Закрепление навыков решения прикладных задач разработки программного обеспечения.
Задание на лабораторную работу
Разработать программу, реализующую функциональность в соответствии с вариантом задания:
1. Реализовать программу хранения массива геометрических фигур в двумерном пространстве. Фигура – это окружность или N-угольник. Программа должна поддерживать поворот и растяжение/сжатие всех фигур относительно заданного пользователем центра. Необходима устойчивость программы к выбору контейнера данных.
2. Реализовать программу, хранящую в отсортированном массиве список пользователей операционной системы с информацией об имени и пароле. Пользователь вводит имя и пароль, программа сообщает, правильный ли пароль.
Указание: используйте функцию binary_search
Пожелание: Чтобы не хранить пароль в открытом виде, придумайте хэш-функцию, и храните имя и хэш-значение пароля. При проверке применяйте хэш-функцию к паролю и сравнивайте хэш-значения.
3. Разработайте программу, хранящую базу данных телефонной компании (фамилия, номер, остаток денег на счету) и по запросу пользователя выдающую количество пользователей с отрицательным остатком и их список.
Указание: можно использовать count_if, remove_copy_if, for_each…, equal_range
4. Реализуйте программу, заполняющую массив фиксированной длины прочитанными из файла значениями или случайными значениями (по выбору пользователя).
Указание: generate
Пожелание: используя стандартную библиотеку boost и функцию boost::bind, реализуйте чтение из файла в generate, не открывая файл каждый раз и не заводя глобальных переменных.
5. Реализуйте программу, считывающие из двух файлов два набора строчек и проверяющую их на совпадение.
Указание: generate, equal
Пожелание: используя стандартную библиотеку boost и функцию boost::bind, реализуйте чтение из файла в generate, не открывая файл каждый раз и не завождя глобальных переменных.
6. База данных телефонной компании реализована в форме отсортированного массива. Периодически приходит дополнение к базе – также отсортированный массив, который необходимо включить в главный.
Указание: используйте merge или inplace_merge.
7. В словаре – пары слово + объяснение. Напечатать список статей об отраслях науки, в которых слово заканчивается на «логия».
Указание: Например, remove_copy_if или for_each.
8. Прочитайте из файла последовательность чисел и выведите все возможные их перестановки в лексикографическом порядке (первая – по возрастанию, последняя – по убыванию).
Указание: sort, next_permutation
9. В текстовом файле – список сотрудников фирмы. Распечатайте списки сотрудников, принятых на работу до и после 01.01.2005.
Указание: partition
Достаточна разработка консольного приложения. Разработка Windows-приложения будет большим преимуществом выполнения работы, если студент достаточно подготовлен для создания Windows-приложений, иллюстрирующих работу системы.
Требования к отчетности по лабораторной работе
В качестве отчета по лабораторной работе студент предоставляет в электронном виде программу на языке C++, реализующую функциональность в соответствии с вариантом задания.