- •Понятие о структуре данного. Уровни представления структур данных.
- •Классификация сд в программах пользователя и в памяти эвм
- •Сд в оперативной памяти
- •Сд типа массив.
- •Сд типа запись (прямое декартово произведение).
- •Сд типа таблица.
- •Операции над таблицей:
- •Временная сложность алгоритмов.
- •Сд типа хеш-таблица.
- •Операция включения элемента в таблицу.
- •Операция исключения элемента из таблицы:
- •Сортировки. Улучшенные методы сортировок.
- •Классификация задач по временной сложности.
- •Сд типа стек.
- •Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):
- •Сд типа очередь.
- •Связное распределение памяти.
- •Сд типа линейный односвязный список.
- •Сд типа указатель.
- •Статические и динамические переменные.
- •Сд типа циклический линейный список.
- •Сд типа двусвязный линейный список.
- •Сд типа дек.
- •Многосвязные списки.
- •Средства объектно-ориентированного программирования.
- •Объекты и свойства инкапсуляции.
- •Наследование и переопределение.
- •Полиморфизм. Виртуальные методы.
- •Динамические объекты. Деструкторы.
- •Обработка ошибок при работе с динамическими объектами.
- •Модули, экспортирующие объекты.
- •Нелинейные структуры данных.
- •Сд типа дерево.
- •Представление деревьев в связной памяти эвм.
- •Алгоритмы прохождения деревьев в глубину и в ширину.
- •Представление деревьев в виде бинарных.
- •Представление бинарных деревьев в связной памяти. Прошитые деревья
- •Формирование бинарного дерева.
- •Применение бинарных деревьев в алгоритмах поиска.
- •Операция включения в сд типа бинарное дерево.
- •Операция исключения из бинарного дерева.
- •Представление бинарного дерева в прямоугольной памяти.
- •Применение бинарных деревьев.
- •Сд типа граф.
- •Представление графа в памяти эвм.
- •Алгоритмы прохождения графа.
- •Топологическая сортировка.
- •Организация данных во внешней памяти. Типы и характеристики устройств внешней памяти.
- •Сд типа последовательный файл.
- •Сд типа файл прямого доступа.
- •Сд типа индексно-последовательный файл.
- •Сд типа хеш-файл.
- •Внешняя сортировка.
- •Алгоритм прямого слияния.
- •Многофазная сортировка.
- •Сущность базы данных. Системы управления базами данных.
- •Общая структура субд.
- •Реляционная модель субд.
- •Язык реляционной алгебры.
Сд типа запись (прямое декартово произведение).
Запись – последовательность элементов, которые в общем случае могут быть одного типа. На логическом уровне СД типа запись можно записать следующим образом:
type Т = Record
S1: T1;
S2: T2;
……..
Sn: Tn;
End;
Здесь: Ti изменяется при i = 1, 2, …, n; S1, …, Sn – идентификаторы полей; Т1, …, Tn – типы данных. Если Ti также является в свою очередь записью, то Si – иерархическая запись.
Если DT1 – множество значений элементов типа Т1, DТ2 – множество значений элементов типа Т2, … , DТn – множество значений элементов типа Тn, то DT – множество значений элементов типа Т будет определяться с помощью прямого декартова произведения: DT = DT1 DT2 … DТn. Другими словами, множество допустимых значений СД типа запись:
Допустимые операции для СД типа запись аналогичны операциям для СД типа массив.
Дескриптор СД типа запись включает в себя: условное обозначение, название структуры, количество полей, указатель на первый элемент (в случае прямоугольной СД), характеристики каждого элемента, условные обозначения типа каждого элемента, размер слота, а также смещение, необходимое для вычисления адреса.
Вообще, смещение – это адрес компоненты (поля) ri относительно начального адреса записи r. Смещение вычисляется следующим образом:
ki = S1 + S2 + … + Si-1, i=1,2, …,n
где Si – размер слота каждого элемента записи.
Дескриптор СД типа запись, в отличие от дескриптора СД типа массив, зависит от количества элементов записи.
Сд типа таблица.
Таблица –последовательность записей, которые имеют одну и ту же организацию. Такая отдельная запись называется элементом таблицы. Чаще всего используется простая запись. Таким образом, таблица – это агрегация элементов. Если последовательность записей упорядочена относительно какого-либо признака, то такая таблица называется упорядоченной, иначе – таблица неупорядоченная.
Классификация СД типа таблица:
СД типа таблица |
||
|
||
неупорядоченная таблица |
упорядоченная таблица |
хеш-таблица |
|
||
как отображение на массив |
как отображение на список |
|
кортеж
атрибут
Если один элемент d i , то кортеж – это <d 1, d 2, …, d n>, причем D Ti d i. Множество значений элементов типа Т (множество допустимых значений СД типа таблица) будет определяться с помощью прямого декартова произведения:
DT = DT1 DT2 … DТn, причем D Ti <d 1, d 2, …, d n>.
Сам же элемент таблицы можно представить в виде двойки <K, V>, где К – ключ, а V – тело элемента. В качестве ключа может быть разное число полей, которые определяют этот элемент. Ключ используется для операции доступа к элементу, так как каждый из ключей уникален для данного элемента. Таким образом, таблица является совокупностью двоек <K, V>.
На логическом уровне элемент СД типа таблица описывается следующим образом:
Type Element = record
Key: integer;
{описание остальных полей}
end;
При реализации таблицы как отображения на массив ее описание выглядит так:
Tabl = array [0 .. N] of Element
Во время выполнения программы количество элементов может меняться. Структура, в которой изменяется количество элементов во время выполнения программы, называется динамической. Если рассматривать динамическую структуру как отображение на массив, то такая структура называется полустатической.
Перед тем как определить операции, которые можно выполнять над таблицей рассмотрим классификацию операций:
Конструкторы – операции, которые создают объекты рассматриваемой структуры.
Деструкторы – операции, которые разрушают объекты рассматриваемой структуры. Признаком этой операции является освобождение памяти.
Модификаторы – операции, которые модифицируют соответствующие структуры объектов. К ним относятся динамические и полустатические модификаторы.
Наблюдатели – операции, у которых в качестве элемента (входного параметра) используются объекты соответствующей структуры, а возвращают эти операции результаты другого типа. Таким образом, операции-наблюдатели не изменяют структуру, а лишь дают информацию о ней.
Итераторы – операторы доступа к содержимому объекта по частям в определенном порядке.