Структуры данных

1.

Структуры данных
Алгоритмы и структуры данных
Лекция

2.

Структуры данных
Данные, на которых базируется информационная модель,
представляют собой систему со всеми характерными
признаками – элементным составом, структурой,
назначением. Такие структурированные системы данных
называют структурами данных.

3.

Типы структур данных
Динамическое множество (в т.ч. стеки и очереди)
Графы
Деревья
Таблицы

4.

Динамическое множество

5.

Динамическое множество

6.

Стеки и очереди

7.

Стек

8.

Стек

9.

Очередь

10.

Очередь

11.

Связанные списки

12.

Поиск в связанном списке

13.

Вставка в связанный список

14.

Удаление в связанном списке

15.

Ограничители

16.

Ограничители

17.

Графы
Граф – это средство для наглядного представления
состава и структуры системы.
Граф состоит из ВЕРШИН, связанных ДУГАМИ (если
линия направленная) или РЕБРАМИ (если линия не
имеет направления). Две дуги, направленные в
противоположные стороны можно заменить ребром.
Граф, в котором все линии направленные, называется
ориентированным.
Две вершины, соединенные дугой или ребром,
называются смежными.

18.

Московский метрополитен
Структура метро
Через какие станции надо
проехать, чтобы добраться до
пункта назначения
Для сети характерна возможность
множества
различных
путей
перемещения по ребрам между
некоторыми парами вершин.
Также наличие замкнутых путей,
которые называются циклами.
Данный граф неориентированный
(симметричный)

19.

Группы крови человека
Связи несимметричны
Граф ориентированный
Петля, линия выходящая и входящая в одну и ту же вершину
I
II
III
IV

20.

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

21.

Административная структура РФ
Российская
Федерация
Корень дерева
Ветви
1 уровень
Центральный
округ
Приволжский
округ
Уральский
округ
Северозападный
округ
2 уровень
Башкирия
Татарстан
Свердловская
область
3 уровень
Казань
Набережные
Челны

22.

Двоичные (бинарные) деревья

23.

Двоичные (бинарные) деревья поиска

24.

Корневые деревья с произвольным
ветвлением

25.

Корневые деревья с произвольным
ветвлением

26.

Корневые деревья с произвольным
ветвлением

27.

Хеш-таблицы