Базовые структуры данных. STL Заикин Олег Сергеевич zaikin.all24.org zaikin.icc@gmail.com. - презентация

1 Базовые структуры данных. STL Заикин Олег Сергеевич zaikin.all24.org

2 Деревья Дерево - структура, эмулирующая древовидную структуру в виде набора связанных узлов. Каждый узел дерева имеет ноль или более узлов-потомков, которые располагаются ниже по дереву. Корневой узел самый верхний узел дерева. Лист узел, не имеющий дочерних элементов.

3 Деревья Внутренний узел любой узел дерева, имеющий потомков, и таким образом не являющийся листовым узлом. Узел, имеющий потомка, называется узлом-родителем относительно своего потомка. Высота узла это максимальная длина нисходящего пути от этого узла к самому нижнему листу. Высота корневого узла равна высоте всего дерева. С корневого узла начинается выполнение большинства операций над деревом (хотя некоторые алгоритмы начинают выполнение с «листов» и выполняются, пока не достигнут корня). Все прочие узлы могут быть достигнуты путём перехода от корневого узла по ссылкам.

4 Деревья Поддерево часть дерева, которая может быть представлена в виде отдельного дерева. Любой узел дерева T вместе со всеми его узлами-потомками является поддеревом дерева T. Для любого узла поддерева либо должен быть путь в корневой узел этого поддерева, либо сам узел должен являться корневым. Наиболее общий способ представления деревьев изображает узлы как записи, расположенные в динамически выделяемой памяти с указателями на своих потомков, предков (или и тех и других). Двоичное дерево – дерево, в котором каждый узел имеет не более двух потомков.

5 Пример задания с деревьями На вход программе дается файл с описанием двоичного дерева. Каждая строка – ветвь дерева, начиная с корневого узла. Например это дерево 1 / \ 3 2 / \ 5 4 С помощью fstream считать дерево из файла. Создать и использовать класс Tree, в котором кроме полей с данными должны быть конструктор, деструктор и другие методы класса в соответствии с заданием.

6 LIFO и стек LIFO (акроним Last In, First Out, «последним пришёл первым ушёл») способ организации и манипулирования данными относительно времени и приоритетов, в котором элементы могут добавляться и выбираться только с одного конца, называемого «вершиной списка». Структура LIFO может быть проиллюстрирована на примере стопки тарелок. Стек – структура данных, организованная по принципу LIFO.

7 FIFO и дэк FIFO (акроним First In, First Out «первым пришёл первым ушёл») способ организации и манипулирования данными по принципу: «первым пришёл первым обслужен». Дэк или двусвязная очередь (англ. deque double ended queue) структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO.

8 Очередь с приоритетом Очередь с приоритетом (англ. priority queue) структура данных, поддерживающая три операции: InsertWithPriority: добавить в очередь элемент с нaзначенным приоритетом GetNext: извлечь из очереди и вернуть элемент с минимальным приоритетом (другие названия «PopElement(Off)» или «GetMinimum») PeekAtNext (необязательная операция): просмотреть элемент с наивысшим приоритетом без извлечения

9 Standard Template Library (стандартная библиотека шаблонов) - набор алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.STL

10 Контейнер (англ. container) объект, который содержит другие объекты. Итератор (англ. iterator) объект-указатель на контейнер. Итератор циклически опрашивает содержимое контейнера. Алгоритм (англ. algorithm) вычислительная процедура для обработки контейнеров. Виды алгоритмов: инициализация, сортировка, поиск, преобразование содержимого контейнера. Основные компоненты STL

11 Последовательные контейнеры vector – динамический массив list – двусвязный список deque – дэк Ассоциативные контейнеры set – множество уникальных элементов multiset – множество необязательно уникальных элементов map – упорядоченный ассоциативный массив пар элементов (ключ/значение) multimap – как map, но можно хранить повторыКонтейнеры

12 Псевдоконтейнеры stack – стек, реализация LIFO. Добавление и удаление элементов осуществляется с одного конца. queue – очередь, реализация FIFO. С одного конца можно добавлять элементы, а с другого вынимать. priority_queue - очередь с приоритетом. Элемент с наивысшим проиоритетом всегда стоит на первом месте.Контейнеры

13 vector - динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. #include // подключение библиотеки vector имя_переменной; // объявление Контейнер vector

14 Основные функции в классе vector: begin() – итератор начального элемента end() – итератор последнего элемента clear() – удаление всех элементов вектора resize(новая_длина) // изменение размера вектора size() // получение текущего размера вектора push_back(T &val) // добавляет эл-нт в конец вектора insert(iterator i, T &val) // добавляет эл-нт внутрь вектора [] // обращение к элементу вектора Контейнер vector

15 Пример vector vec; for (unsigned i = 0; i < 5; i++) vec.push_back(i*i); for (unsigned i = 0; i < vec.size(); i++) cout

16 Вектор может быть многомерным. Пример: vector > vec_matrix; vec_matrix.resize(5); // у матрицы 5 строк for (unsigned i = 0; i < vec_matrix.size(); i++) vec_matrix[i].resize(6); // 6 столбцов Вектор может быть не только числовым. vector vec_string; // вектор строк Действуют операторы присваивания и сравнения. vec1 = vec2; If ( vec1 < vec2 ) … Контейнер vector

17 list – двусвязный список Поиск перебором медленнее, чем у вектора из-за большего времени доступа к элементу. Вставка и удаление производятся быстрее. #include // подключение библиотеки Некоторые функции как у vector. Но есть функции объединения (merge) двух списков и сортировки списка (sort). Пример: list lst; lst.resize(5); for (unsigned i = 0; i < 5; i++) lst.push_back(i*i); lst.sort(); Контейнер list

18 Объявление итератора тип_контейнера :: iterator имя_переменной; Пример list :: iterator lst_it; // итератор list lst; for (lst_it = lst.begin(); lst_it != lst.end(); lst_it++ ) cout :: iterator lst_it; // итератор for (lst_it = lst.begin(); lst_it != lst.end(); lst_it++ ) cout

19 Позволяет хранить пары вида «(ключ, значение)». Поддерживает операции добавления пары, а также поиска и удаления пары по ключу: INSERT(ключ, значение) FIND(ключ) REMOVE(ключ) Ключи должны быть уникальны. Порядок следования элементов определяется ключами. Контейнер map

20 #include // подключение библиотеки Пример. map m; char ch; for (int i = 0; i < 10; i++) m.insert(pair (A + i, i ) ); cout > ch; map :: Iterator p; p = m.find(ch); if ( p != m.end() ) cout

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

22 Не меняющие последовательность операции Операции с каждым элементом (For each) Найти (Find) Найти рядом (Аdjacent find) Подсчет (Count) Отличие (Mismatch) Сравнение на равенство (Equal) Поиск подпоследовательности (Search) Алгоритмы в STL

23 Меняющие последовательность операции Копировать (Copy) Обменять (Swap) Преобразовать (Transform) Заменить (Replace) Заполнить (Fill) Породить (Generate) Удалить (Remove) Убрать повторы (Unique) Расположить в обратном порядке (Reverse) Переместить по кругу (Rotate) Перетасовать (Random shuffle) Разделить (Partitions) Алгоритмы в STL

24 Операции сортировки и отношения Операции над множеством для сортированных структур … Алгоритмы в STL

25 sort() сортирует элементы в диапазоне [first, last). void sort(RandomAccessIterator first, RandomAccessIterator last); random_shuffle переставляет элементы в диапазоне [first, last) с равномерным распределением. void random_shuffle(RandomAccessIterator first, RandomAccessIterator last); Алгоритмы в STL

26 Пример #include … list lst; list :: iterator lst_it; for ( unsigned i=0; i < 10; i++ ) lst.push_back(i); random_shuffle(lst.begin(), lst.end()); for ( lst_it = lst.begin(); lst_it != lst.end(); lst_it++ ) cout