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

Август 20, 2022

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

Содержание

2. Линейные структуры данных Линейные структуры — это упорядоченные структуры, в которых адрес элемента однозначно определяется его
3. Линейные структуры данных К линейным структурам данным можно отнести: Массивы Динамические массивы Связный список Стек Очередь
4. Массивы Массив – одна из простейших и наиболее широко применяемых в компьютерных программах линейных структур данных.
5. Строки В языке C строки было принято представлять в виде массива символов: В языке C++ для
6. Класс String #include Поддерживает операции: Удаления посл-ти символов (erase) Поиска подстроки (find) Возврата подстроки (substr) Замены
7. Стандартная библиотека шаблонов STL Предоставляет обобщенные компоненты для решения задач Условно можно разделить на 3 части:
8. Контейнеры STL Контейнеры в STL – обобщенный классы, моделирующие различные структуры данных Например: #include #include #include
9. Контейнеры STL #include // строки #include // динамический массив #include // двусвязный список #include // дек
10. Итераторы Итераторы – интерфейс между контейнерами и алгоритмами. Итератор - это универсальный способ доступа к элементам
11. Алгоритмы Реализованы как свободные функции, а не члены-функции Использование - #include Все алгоритмы работают с итераторами
12. Использование Vector Vector – динамически расширяемый массив Объявление – vector v(); Доступ к элементам – так
13. Дек С точки зрения программиста – использование схоже с Vector Отличие в реализации – Vector –
14. Использование Дека // Предикат bool is_odd(int i) { return ((i % 2) == 1); } int
15. Связные списки Связный список - это разновидность линейных структур данных, представляющая собой последовательность элементов, обычно отсортированную
16. Использование list Объявление - list l1; Добавление элемента – O(n) в худшем случае // Добавить элемент
17. Очередь Очередь – линейная структура данных, удовлетворяющая принципу FIFO (первый пришел – первый ушел) Поддерживает добавление
18. Очередь - Пример queue q; // добавить и удалить q.push(1); q.pop(); // доступ к первому и
19. Стек Очередь – линейная структура данных, удовлетворяющая принципу FILO(первый пришел – последний ушел) Поддерживает добавление элемента
21. Скачать презентацию

Слайд 2

Линейные структуры данных
Линейные структуры — это упорядоченные структуры, в которых адрес

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

Слайд 3

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

Слайд 4

Массивы
Массив – одна из простейших и наиболее широко применяемых в компьютерных

программах линейных структур данных. В любом языке программирования массивы имеют несколько общих свойств:
Содержимое массива хранится в непрерывной области памяти.
Все элементы массива имеют одинаковый тип; поэтому массивы называют однородными структурами данных.
Существует прямой доступ к элементам массива.

Типичные операции для массивов включают:
Выделение элемента(Allocation)
Доступ к элементу (Accessing)
Изменение размеров массива (Redimensioning)

Слайд 5

Строки
В языке C строки было принято представлять в виде массива символов:
В

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

Слайд 6

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

подстроки (replace)
Вставки подстроки (insert)

Слайд 7

Стандартная библиотека шаблонов STL
Предоставляет обобщенные компоненты для решения задач
Условно можно разделить

на 3 части:
Контейнеры
Итераторы
Алгоритмы

Слайд 8

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

#include
#include

Слайд 9

Контейнеры STL
#include // строки
#include // динамический массив
#include //

двусвязный список
#include // дек
#include // очередь
#include // стэк
#include // множество
#include // ассоциативный список

Слайд 10

Итераторы
Итераторы – интерфейс между контейнерами и алгоритмами.
Итератор - это универсальный способ

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

Слайд 11

Алгоритмы
Реализованы как свободные функции, а не члены-функции
Использование - #include
Все алгоритмы

работают с итераторами на контейнерах
Для корректной работы – использование пространства имен std

Слайд 12

Использование Vector
Vector – динамически расширяемый массив
Объявление – vector v();
Доступ к элементам

– так же как в массиве, сложность O(1)
Добавление элемента – O(1) в конец, O(n) в других случаях
Поиск O(n)

Слайд 13

Дек
С точки зрения программиста – использование схоже с Vector
Отличие в реализации

– Vector – это массив, когда как для удобство добавления элемента Deque реализован как множество массивов

Слайд 14

$Использование Дека // Предикат bool is_odd(int i) { return ((i %$

Использование Дека
// Предикат
bool is_odd(int i) {
return ((i % 2) == 1);
}
int

main(int argc, char* argv[]) {
deque 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 l1;
Добавление элемента – O(n) в худшем случае
//

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

Поиск – О(n)

Слайд 17

Очередь
Очередь – линейная структура данных, удовлетворяющая принципу FIFO (первый пришел –

первый ушел)
Поддерживает добавление элемента в конец, доступ к первому и последнему, удаление первого элемента
Не поддерживает итераторы

Слайд 18

Очередь - Пример
queue 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(первый пришел – последний

ушел)
Поддерживает добавление элемента в конец, доступ к первому и последнему, удаление последнего элемента

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

Содержание

Линейные структуры данныхЛинейные структуры — это упорядоченные структуры, в которых адрес

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

МассивыМассив – одна из простейших и наиболее широко применяемых в компьютерных

СтрокиВ языке C строки было принято представлять в виде массива символов:В

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

Стандартная библиотека шаблонов STLПредоставляет обобщенные компоненты для решения задачУсловно можно разделить

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

Контейнеры STL#include // строки#include // динамический массив#include //

ИтераторыИтераторы – интерфейс между контейнерами и алгоритмами.Итератор - это универсальный способ

АлгоритмыРеализованы как свободные функции, а не члены-функцииИспользование - #include Все алгоритмы

Использование VectorVector – динамически расширяемый массивОбъявление – vector v();Доступ к элементам

ДекС точки зрения программиста – использование схоже с VectorОтличие в реализации

Использование Дека// Предикатbool is_odd(int i) {return ((i % 2) == 1);}int

Связные спискиСвязный список - это разновидность линейных структур данных, представляющая собой

Использование listОбъявление - list l1;Добавление элемента – O(n) в худшем случае//

ОчередьОчередь – линейная структура данных, удовлетворяющая принципу FIFO (первый пришел –

Очередь - Примерqueue q;// добавить и удалитьq.push(1);q.pop();// доступ к первому и

СтекОчередь – линейная структура данных, удовлетворяющая принципу FILO(первый пришел – последний

Похожие презентации