- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Многомерные статические массивы
Как было отмечено выше, вектор это одномерный массив. Во всех языках программирования можно объявлять и многомерные массивы, т. е. массивы, элементами которых являются массивы. Например, двумерный массив можно объявить следующим образом:
Type TarrMatr = Array [0..5] Of Array [0..3] Of Word;
Var X: TarrMatr;
То же самое можно объявить более компактно:
Type TarrMatr = Array [0..5, 0..3] Of Word;
Var X: TarrMatr;
Доступ к значениям элементов многомерного массива обеспечивается с помощью имени переменной типа «массив» и индексов, перечисляемых через запятую, например, X[3, 0]. Количество указываемых индексов должно быть равно размерности массива: для доступа к элементу М-мерного массива необходимо указать М индексов.
Все элементы массива имеют один и тот же тип. В отличие от вектора для массива общего вида преобразование логической структуры в физическую имеет более сложный вид. Это преобразование выполняется путем линеаризации, в ходе которой М-мерная логическая структура массива преобразуется в одномерную физическую структуру, представляющую собой линейно упорядоченную последовательность слотов. Такое преобразование реализуется с помощью подходящей функции упорядочения, аргументом которой является упорядоченный набор индексов элемента, а значением адрес соответствующего слота. Например, если последовательность однотипных элементов трактуется как двумерный массив, и нижние границы индексов i и j равны 0, то адрес (i, j)-элемента матрицы вычисляется с помощью следующей функции упорядочения:
Адрес(i, j) = база + Nrow SizeOf(Element) i + j,
где база адрес начального элемента массива,
Nrow количество элементов в строке,
SizeOf(Element) размер слота элемента в байтах,
Хотя физическая структура М-мерного массива при линейном упорядочении его элементов в памяти совпадает с физической структурой вектора, дескриптор массива отличается от дескриптора вектора. В частности, в полях дескриптора массива может содержаться следующая информация:
поле типа структуры;
поле имени массива, например, Matr;
поле, содержащее размерность массива;
адрес массива в памяти (база);
поля, содержащие пары граничных значений индексов, число этих полей равно размерности массива;
поля, содержащие специальные индексные множители (их число равно размерности массива), необходимые для использования в функции упорядочения;
поле базового типа массива;
поле, содержащее размер слота для элемента.
Для массивов в Delphi определена операция присваивания. Если два массива A и B типа TarrVect определены, с помощью нотаций, приведенных в п. 5.2.1, то в результате выполнения оператора
A:= B;
значения элементов массива В скопируются в элементы массива А.
Но если объявить массивы как
Var A: Array [-2..10] Of Integer;
B: Array [-2..10] Of Integer;
то при попытке присваивания A:= B компилятор Delphi выдаст сообщение об ошибке несовместимости типов. Дело в том, что компилятор считает, что переменные имеют один и тот же тип только в случае, если они объявлены в одном и том же списке или они явно определены через некоторый поименованный тип. Это еще один аргумент в пользу использования имен типов в описаниях структурированных переменных.