Лабораторная работа 8 для студентов курса 2 семестра кафедры ИУ5 МГТУ им Н.Э. Баумана.
MyStack, реализующий структуру данных «стек» на основе динамического связного списка.vector, list, map и алгоритмы сортировки, поиска, преобразования.Зайдите в свою локальную директорию с репозиторием для выполнения лабораторных работ. Заберите ветку с соответствующей лабораторной работой из общего репозитория:
git pull upstream
или
git pull upstream lab_8
Переключитесь на ветку с текущей лабораторной работой:
git checkout lab_8
Свяжите ветку локального репозитория с вашим удаленным репозиторием:
git push --set-upstream origin lab_8
Разработайте структуру ListNode, представляющую узел связного списка:
template <typename T>
struct ListNode {
T data;
ListNode<T>* next;
ListNode(const T& value) : data(value), next(nullptr) {}
};
Разработайте шаблонный класс MyStack, реализующий стек на основе односвязного списка.
private:
ListNode<T>* top; // указатель на вершину стека.
public:
MyStack(); // конструктор по умолчанию.
~MyStack(); // деструктор (освобождает память).
void push(const T& value); // добавляет элемент на вершину.
bool pop(T& value); // удаляет элемент с вершины, возвращает его значение.
bool peek(T& value) const; // возвращает значение верхнего элемента без удаления.
bool isEmpty() const; // проверка на пустоту.
int size() const; // возвращает количество элементов.
void clear(); // очищает стек.
void print() const; // выводит содержимое стека (от вершины ко дну).
Требования:
MyStack.h.Разработайте функцию:
void Multipliers(int n, MyStack<int>& stack);
Функция должна раскладывать число n на простые множители и помещать их в стек (в порядке нахождения, начиная с наименьшего делителя).
В main():
Multipliers().Пример вывода:
3960 = 11 * 5 * 3 * 3 * 2 * 2 * 2
3960 = 2 * 2 * 2 * 3 * 3 * 5 * 11
Примечание:
Стек является структурой
LIFO(Last In – First Out), поэтому порядок вывода элементов зависит от способа извлечения.
После выполнения задания 2 в стеке MyStack<int> содержатся множители числа 3960. Используйте этот стек как единственный источник данных для выполнения следующих подзаданий.
vector и использование алгоритмов3.1.1. Создайте std::vector<int> и перенесите в него все элементы из стека в порядке от дна к вершине (то есть в возрастающем порядке множителей: 2, 2, 2, 3, 3, 5, 11).
3.1.2. Используя алгоритмы STL и лямбда-выражения, выполните:
std::for_each и лямбды.3.1.3. Для сортировки по убыванию продемонстрируйте использование функтора (отдельный класс с перегруженным operator()).
list и использование алгоритмов3.2.1. Создайте std::list<int> и перенесите в него все элементы из исходного стека (также в возрастающем порядке).
3.2.2. Используя алгоритмы STL, выполните:
std::remove_if и лямбды.std::find. Выведите найденный элемент или сообщение об отсутствии.std::count_if и лямбды.map и использование алгоритмовКонтейнер std::map хранит элементы в отсортированном виде по ключу.
3.3.1. Создайте std::map<int, int>, где ключ — это множитель, а значение — количество его вхождений. Заполните отображение, анализируя данные из исходного стека.
3.3.2. Используя алгоритмы STL, выполните:
множитель -> количество.std::find_if (или метода find) и вывод результата.std::count_if и лямбды.3.4.1. Создайте два вектора: один с исходными множителями, второй — с их квадратами (из п. 3.1.2).
3.4.2. Используя алгоритм std::inner_product, вычислите скалярное произведение этих двух векторов.
3.4.3. Используя std::transform и лямбду, создайте третий вектор, содержащий суммы соответствующих элементов первых двух векторов.
Выполняется для получения повышенной оценки.
4.1 Реализуйте функтор для сравнения элементов при сортировке по убыванию (использовать в std::sort вместо лямбды).
4.2 Напишите шаблонную функцию void printContainer(const Container& cont), которая выводит содержимое любого контейнера STL (vector, list, map) с использованием итераторов и лямбды.
4.3 Используйте std::accumulate для вычисления произведения всех множителей (должно получиться исходное число 3960).
main() и все задания.========== ЗАДАНИЕ 2: Разложение на множители ==========
3960 = 11 * 5 * 3 * 3 * 2 * 2 * 2
3960 = 2 * 2 * 2 * 3 * 3 * 5 * 11
========== ЗАДАНИЕ 3.1: Работа с vector ==========
Исходный вектор (возрастающий): 2 2 2 3 3 5 11
Вектор после сортировки по убыванию: 11 5 3 3 2 2 2
Количество двоек: 3
Квадраты элементов: 4 4 4 9 9 25 121
Вывод через for_each: 11 5 3 3 2 2 2
========== ЗАДАНИЕ 3.2: Работа с list ==========
Исходный список: 2 2 2 3 3 5 11
Список после удаления двоек: 3 3 5 11
Поиск элемента 5: найден
Количество элементов > 3: 2
========== ЗАДАНИЕ 3.3: Работа с map ==========
Содержимое map (множитель -> количество):
2 -> 3
3 -> 2
5 -> 1
11 -> 1
Поиск ключа 3: найден, количество = 2
Количество множителей, встречающихся более 1 раза: 2
========== ЗАДАНИЕ 3.4: Работа с несколькими контейнерами ==========
Вектор множителей: 2 2 2 3 3 5 11
Вектор квадратов: 4 4 4 9 9 25 121
Скалярное произведение: 2*4 + 2*4 + ... = 4+4+4+9+9+25+121 = ...// вычисляется программно
Вектор сумм: 6 6 6 12 12 30 132
push и pop в вашей реализации стека?std::vector и std::list? Когда какой контейнер предпочтительнее?лямбда-выражение? Приведите синтаксис и пример использования.функтор? В чём его преимущество перед обычной функцией?std::remove_if? Почему он не удаляет элементы напрямую?std::map? Как реализован поиск по ключу?