Линейные структуры данных и стандартная библиотека шаблонов
Линейные структуры данных
Линейные структуры данных
Массивы
Строки
Класс String
Стандартная библиотека шаблонов STL
Контейнеры STL
Контейнеры STL
Итераторы
Алгоритмы
Использование Vector
Дек
Использование Дека
Связные списки
Использование list
Очередь
Очередь - Пример
Стек
Стек-Пример
709.50K
Category: programmingprogramming

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

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;
English     Русский Rules