Линейные структуры данных и стандартная библиотека шаблонов

1. Линейные структуры данных и стандартная библиотека шаблонов

Тенчурин Д.Р.
271ПИ

2. Линейные структуры данных

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

3. Линейные структуры данных

К линейным структурам данным можно
отнести:
◦ Массивы
Динамические массивы
◦
◦
◦
◦
◦
Связный список
Стек
Очередь
Дек
Хэш-таблица

4. Массивы

Массив – одна из простейших и наиболее широко
применяемых в компьютерных программах линейных
структур данных. В любом языке программирования
массивы имеют несколько общих свойств:
Содержимое массива хранится в непрерывной области
памяти.
Все элементы массива имеют одинаковый тип; поэтому
массивы называют однородными структурами данных.
Существует прямой доступ к элементам массива.
Типичные операции для массивов включают:
• Выделение элемента(Allocation)
• Доступ к элементу (Accessing)
• Изменение размеров массива (Redimensioning)

5. Строки

В языке C строки было принято
представлять в виде массива символов:
В языке C++ для представления строки
используется класс string
Обе структуры линейны, но вторую
принято считать более удобной,
безопасной и простой в использовании

6. Класс String

#include <string>
Поддерживает операции:
Удаления посл-ти символов (erase)
Поиска подстроки (find)
Возврата подстроки (substr)
Замены подстроки (replace)
Вставки подстроки (insert)

7. Стандартная библиотека шаблонов STL

Предоставляет обобщенные
компоненты для решения задач
Условно можно разделить на 3 части:
Контейнеры
Итераторы
Алгоритмы

8. Контейнеры STL

Контейнеры в STL – обобщенный
классы, моделирующие различные
структуры данных
Например:
◦ #include <hash_set>
◦ #include <hash_map>
◦ #include <slist>

9. Контейнеры STL

#include <string> // строки
#include <vector> // динамический массив
#include <list> // двусвязный список
#include <deque> // дек
#include <queue> // очередь
#include <stack> // стэк
#include <set> // множество
#include <map> // ассоциативный список

10. Итераторы

Итераторы – интерфейс между
контейнерами и алгоритмами.
Итератор - это универсальный способ
доступа к элементам контейнера.
Ведет себя как указатель.
Пример:
string A = "This is a string";
string::iterator it; // создание итератора
for (it = A.begin(); it != A.end(); ++it) {
cout << *it << endl;
}

11. Алгоритмы

Реализованы как свободные функции,
а не члены-функции
Использование - #include <algorithm>
Все алгоритмы работают с
итераторами на контейнерах
Для корректной работы –
использование пространства имен std

12. Использование Vector

Vector – динамически расширяемый
массив
Объявление – vector<type> v();
Доступ к элементам – так же как в
массиве, сложность O(1)
Добавление элемента – O(1) в конец,
O(n) в других случаях
Поиск O(n)

13. Дек

С точки зрения программиста –
использование схоже с Vector
Отличие в реализации – Vector – это
массив, когда как для удобство
добавления элемента Deque
реализован как множество массивов

14. Использование Дека

// Предикат
bool is_odd(int i) {
◦ return ((i % 2) == 1);
}
int main(int argc, char* argv[]) {
◦ deque<int> numbers;
◦ for (int i = 0; i < 20; i++) {
numbers.push_back(i);
◦ }
◦ cout << count(numbers.begin(), numbers.end(), 10) << endl;
◦ cout << count_if(numbers.begin(), numbers.end(), is_odd)
◦ << endl;
◦ return EXIT_SUCCESS;
}

15. Связные списки

Связный список - это разновидность линейных структур
данных, представляющая собой последовательность
элементов, обычно отсортированную в соответствии с
заданным правилом. Последовательность может
содержать любое количество элементов, поскольку при
создании
списка
используется
динамическое
распределение памяти.
Каждый элемент связного списка представляет собой
отдельный объект, содержащий поле для хранения
информации и указатель на следующий элемент списка
(а в случае двусвязного списка в объекте хранится также
указатель на предыдущий элемент).

16. Использование list

Объявление - list<int> l1;
Добавление элемента – O(n) в худшем случае
// Добавить элемент после 1ого
list<int> l(10);
list<int>::iterator it = l.begin();
it++;
l.insert(it, 5);
Удаление элемента – O(n) в худшем случае
// Удаление второго элемента
list<int> l(10);
list<int>::iterator second = l.begin();
second++;
l.erase(second);
Поиск – О(n)

17. Очередь

Очередь – линейная структура данных,
удовлетворяющая принципу FIFO
(первый пришел – первый ушел)
Поддерживает добавление элемента в
конец, доступ к первому и последнему,
удаление первого элемента
Не поддерживает итераторы

18. Очередь - Пример

queue<int> q;
// добавить и удалить
q.push(1);
q.pop();
// доступ к первому и последнему
q.push(1);
q.push(2);
cout << q.front() << endl;
cout << q.back() << endl;
// размер
cout << q.size() << endl;
cout << q.empty() << endl;

19. Стек

Очередь – линейная структура данных,
удовлетворяющая принципу
FILO(первый пришел – последний
ушел)
Поддерживает добавление элемента в
конец, доступ к первому и последнему,
удаление последнего элемента

20. Стек-Пример

stack<int> s;
// Добавление и удаление элемента из вершины стека
s.push(1);
s.pop();
// Доступ к вершине стека
s.push(10);
s.push(11);
cout << s.top() << endl;
// Размер
cout << s.size() << endl;
cout << s.empty() << endl;