- •Понятие о структуре данного. Уровни представления структур данных.
- •Классификация сд в программах пользователя и в памяти эвм
- •Сд в оперативной памяти
- •Сд типа массив.
- •Сд типа запись (прямое декартово произведение).
- •Сд типа таблица.
- •Операции над таблицей:
- •Временная сложность алгоритмов.
- •Сд типа хеш-таблица.
- •Операция включения элемента в таблицу.
- •Операция исключения элемента из таблицы:
- •Сортировки. Улучшенные методы сортировок.
- •Классификация задач по временной сложности.
- •Сд типа стек.
- •Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):
- •Сд типа очередь.
- •Связное распределение памяти.
- •Сд типа линейный односвязный список.
- •Сд типа указатель.
- •Статические и динамические переменные.
- •Сд типа циклический линейный список.
- •Сд типа двусвязный линейный список.
- •Сд типа дек.
- •Многосвязные списки.
- •Средства объектно-ориентированного программирования.
- •Объекты и свойства инкапсуляции.
- •Наследование и переопределение.
- •Полиморфизм. Виртуальные методы.
- •Динамические объекты. Деструкторы.
- •Обработка ошибок при работе с динамическими объектами.
- •Модули, экспортирующие объекты.
- •Нелинейные структуры данных.
- •Сд типа дерево.
- •Представление деревьев в связной памяти эвм.
- •Алгоритмы прохождения деревьев в глубину и в ширину.
- •Представление деревьев в виде бинарных.
- •Представление бинарных деревьев в связной памяти. Прошитые деревья
- •Формирование бинарного дерева.
- •Применение бинарных деревьев в алгоритмах поиска.
- •Операция включения в сд типа бинарное дерево.
- •Операция исключения из бинарного дерева.
- •Представление бинарного дерева в прямоугольной памяти.
- •Применение бинарных деревьев.
- •Сд типа граф.
- •Представление графа в памяти эвм.
- •Алгоритмы прохождения графа.
- •Топологическая сортировка.
- •Организация данных во внешней памяти. Типы и характеристики устройств внешней памяти.
- •Сд типа последовательный файл.
- •Сд типа файл прямого доступа.
- •Сд типа индексно-последовательный файл.
- •Сд типа хеш-файл.
- •Внешняя сортировка.
- •Алгоритм прямого слияния.
- •Многофазная сортировка.
- •Сущность базы данных. Системы управления базами данных.
- •Общая структура субд.
- •Реляционная модель субд.
- •Язык реляционной алгебры.
Алгоритмы прохождения деревьев в глубину и в ширину.
При прохождении
в глубину представленного дерева,
список его вершин, записанных в порядке
их посещения, будет выглядеть следующим
образом: A,
B, C, F, G, H, D, E, I, J, K.
Алгоритм прохождения дерева в глубину:
<пустой стек S>;
<пройти корень и включить его в стек S>;
while <стек S не пуст> do
begin {пусть P – узел, находящийся в вершине стека S}
if <не все сыновья узла Р пройдены>
then <пройти старшего сына и включить его в стек S>
else begin
<исключить из вершины стека узел Р>;
if <не все братья вершины Р пройдены>
then <пройти старшего брата и включить его в стек S>
end;
end;
При прохождении представленного дерева в ширину (по уровням), список его вершин, записанных в порядке их посещения, будет выглядеть следующим образом:
A , B, C, D, E, F, G, H, I, J, K.
Алгоритм прохождения дерева в ширину:
<взять две очереди О1 и О2>;
<поместить корень в очередь О1>;
while <О1 или О2 не пуста> do
if <О1 не пуста> then {Р – узел, находящийся в голове очереди О1}
begin
<исключить узел из очереди О1 и пройти его>;
<поместить все узлы, относящиеся к братьям этого узла Р в очередь О2>;
end
else <O1=O2; O2=> и повторяем цикл.
Представление деревьев в виде бинарных.
Между деревьями общего вида (узел дерева может иметь более двух сыновей) и бинарными деревьями существует взаимно однозначное соответствие, поэтому бинарные деревья часто используют для представления деревьев общего вида. Для такого представления используют следующий алгоритм:
изображаем корень дерева;
по вертикали изображаем старшего сына этого корня;
по горизонтали вправо от этого узла представляем всех его братьев;
пп. 1, 2, 3 повторяем для всех его узлов.
Таким образом,
получаем, что вертикальные ребра
изображают левые поддеревья, а
горизонтальные – правые. Данный
алгоритм можно распространить и для
леса.
a c
d e b
j f
g h i
k
Теорема. Число бинарных деревьев с n вершинами можно выразить формулой: . Например, для n=3 имеем
Проиллюстрируем этот пример графически:
Представление бинарных деревьев в связной памяти. Прошитые деревья
При представлении бинарных деревьев в связной памяти, различают также три основных способа представления: стандартный, инверсный, смешанный. Узлы дерева при каждом таком представлении выглядят следующим образом:
Data L_Son R_Son
F Data
F Data L_Son R_Son
стандартный
инверсный смешанный
Е
LP RP Data L_Son R_Son
О
Симметричным
прохождением бинарного дерева
является такое прохождение, когда мы
проходим сначала левое поддерево, затем
посещаем корень и последним посещаем
правое поддерево: A R
B.
A
B
П
В памяти это дерево
будет выглядеть так:
a b
e c
d f g
фиктивный элемент
1 1 a
1 1
1 0 b
1 1 e
При его симметричном
прохождении получаем следующий список
вершин: c, b,
a, d, g,
e, f.
0 0 c
0 0 f
0 1 d
0 0 g
Использование “прошивок” существенно убыстряет прохождение дерева, позволяет не использовать стек, но при этом усложняются алгоритмы включения / исключения узла, т.к. в прошитом дереве необходимо управлять не только структурными связями, но и “нитями”.