- •Понятие о структуре данного. Уровни представления структур данных.
- •Классификация сд в программах пользователя и в памяти эвм
- •Сд в оперативной памяти
- •Сд типа массив.
- •Сд типа запись (прямое декартово произведение).
- •Сд типа таблица.
- •Операции над таблицей:
- •Временная сложность алгоритмов.
- •Сд типа хеш-таблица.
- •Операция включения элемента в таблицу.
- •Операция исключения элемента из таблицы:
- •Сортировки. Улучшенные методы сортировок.
- •Классификация задач по временной сложности.
- •Сд типа стек.
- •Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):
- •Сд типа очередь.
- •Связное распределение памяти.
- •Сд типа линейный односвязный список.
- •Сд типа указатель.
- •Статические и динамические переменные.
- •Сд типа циклический линейный список.
- •Сд типа двусвязный линейный список.
- •Сд типа дек.
- •Многосвязные списки.
- •Средства объектно-ориентированного программирования.
- •Объекты и свойства инкапсуляции.
- •Наследование и переопределение.
- •Полиморфизм. Виртуальные методы.
- •Динамические объекты. Деструкторы.
- •Обработка ошибок при работе с динамическими объектами.
- •Модули, экспортирующие объекты.
- •Нелинейные структуры данных.
- •Сд типа дерево.
- •Представление деревьев в связной памяти эвм.
- •Алгоритмы прохождения деревьев в глубину и в ширину.
- •Представление деревьев в виде бинарных.
- •Представление бинарных деревьев в связной памяти. Прошитые деревья
- •Формирование бинарного дерева.
- •Применение бинарных деревьев в алгоритмах поиска.
- •Операция включения в сд типа бинарное дерево.
- •Операция исключения из бинарного дерева.
- •Представление бинарного дерева в прямоугольной памяти.
- •Применение бинарных деревьев.
- •Сд типа граф.
- •Представление графа в памяти эвм.
- •Алгоритмы прохождения графа.
- •Топологическая сортировка.
- •Организация данных во внешней памяти. Типы и характеристики устройств внешней памяти.
- •Сд типа последовательный файл.
- •Сд типа файл прямого доступа.
- •Сд типа индексно-последовательный файл.
- •Сд типа хеш-файл.
- •Внешняя сортировка.
- •Алгоритм прямого слияния.
- •Многофазная сортировка.
- •Сущность базы данных. Системы управления базами данных.
- •Общая структура субд.
- •Реляционная модель субд.
- •Язык реляционной алгебры.
Сд в оперативной памяти
полуслово
схемы хранения
слово
двойное слово
прямоугольные
связные
Оперативная память представляет собой массив.
Слово – минимальное количество бит, которое может обрабатываться одновременно.
СД во внешней
памяти
схемы хранения
физический блок
СД последовательного
доступа
СД
индексно-последовательного доступа
СД прямого доступа
Сд типа массив.
Массив – последовательность элементов одного типа, называемого базовым. На математическом языке массив – это функция с ограниченной областью определения. Структура массивов однородна. Для выделения отдельной компоненты массива используется индекс. Индекс – это значение специального типа, определенного как тип индекса данного массива. Поэтому на логическом уровне СД типа массив можно записать следующим образом:
type A = array [T1] of T2,
где Т1 – базовый тип массива, Т2 – тип индекса.
Если DT1 – множество значений элементов типа Т1, DТ2 – множество значений элементов типа Т2, то А: DT1 DТ2 (отображение).
Кардинальное число Car(T) структуры типа Т – это множество значений, которое может принимать данная структура типа Т. Кардинальное число характеризует объем памяти, необходимый данной структуре. Для массива A: Car(A) = [Car(T2)] Car(T1).
Набор допустимых операций для СД типа массив:
Операция доступа (доступ к элементам массива – прямой; от размера структуры операция не зависит).
Операция присваивания.
Операция инициализации (определение начальных условий).
На физическом уровне СД типа массив представляет собой непрерывный участок памяти элементов одинакового объема. Участок памяти, необходимый для одного элемента называется слотом.
Var B: A {определяем переменную В как переменную типа массив А}
p i g, где p – индекс первого элемента массива, g – индекс последнего элемента массива, i – индекс рассматриваемого элемента.
Учитывая введенные обозначения, формула для вычисления размера слота одномерного массива выглядит следующим образом:
Adr(B[i]) = Adr(B[p]) + (i-p)S = Adr(B[p]) – p S + i S,
где S – количество слов, которое необходимо для одного элемента (зависит от типа элемента), Adr(B[p]) – p S является константой, а i S – переменная.
Нередко физической структуре ставится в соответствие дескриптор (заголовок), который содержит общие сведения о данной физической структуре. Дескриптор хранится также как и структура в памяти. Вообще дескриптор представляет собой структуру типа запись.
Применительно к СД типа массив, дескриптор содержит следующие компоненты: имя массива, условное обозначение данной структуры, адрес первого элемента массива, индексы нижней и верхней границ массива, тип элемента массива, размер слота. Например, для следующего описания массива:
Var A: array [-5 .. 4] of Char
дескриптор будет выглядеть таким образом:
-
V
A
Adr (A[-5])
-5
4
Char
Для СД типа массив размер дескриптора не зависит от размерности массива. При каждой операции доступа используется вся информация дескриптора. Например, поля границы изменения индекса используются при обработке исключительных операций.