- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Многомерные динамические массивы
Многомерный динамический массив размерности М определяется как динамический вектор динамических массивов размерности М1, динамический массив размерности М1 является вектором динамических массивов размерности М2 и т. д. Например, нотации
Type TdinMatr = Array Of Array Of Integer;
Var arrMatr: TdinMatr;
описывают двумерный динамический массив (динамическую матрицу).
Один из способов отвести память под такой массив использовать процедуру SetLength. Если требуется зафиксировать диапазоны изменения всех индексов, то в функцию SetLength следует передавать столько размеров, сколько раз повторяется слово Array в объявлении типа создаваемого многомерного динамического массива. Например, оператор
SetLength(arrMatr, 3, 5);
отводит память под прямоугольную матрицу arrMatr, состоящую из трех строк и пяти столбцов.
Индексы существующего динамического массива отсчитываются от нуля.
Можно изменять диапазоны некоторых индексов в зависимости от значений других индексов. Например, можно создать матрицу, у которой в зависимости от номера строки варьируется длина строки. В этом случае сначала процедурой SetLength фиксируется диапазон первого индекса. Если диапазон изменения первого индекса нужно установить [0, 2], то следует записать вызов SetLength в виде:
SetLength(arrMatr, 3);
При выполнении этого вызова в памяти отводится место для трех переменных arrMatr[0], arrMatr[1] и arrMatr[2]. Затем можно задать размер, например, второго из этих массивов, т. е. фактически количество элементов второй строки динамического двумерного массива (строки с индексом 1). Следующий оператор устанавливает этому размеру значение 5:
SetLength(arrMatr[1], 5);
Программный фрагмент, приведенный ниже, уменьшает размер строки с ростом ее индекса:
Var arrMatr: TdinMatr;
N, i, j, m: Integer;
Begin
N:= 3; m:= 1;
SetLength(arrMatr, N);
For i:= 0 To N-1 Do Begin
SetLength(arrMatr[i], N-i);
For j:= 0 To N-i-1 Do Begin
arrMatr[i, j]:= m;
Inc(m);
End;
End;
End;
В результате выполнения этого фрагмента формируется логическая структура, показанная на рисунке 5.2
Рисунок 5.2 Логическая структура динамической матрицы arrMatr, содержащей строки различных размеров
Физическая структура массива приводится на рисунке 5.3. Как показывает этот рисунок, для всего массива в сегменте статических данных для массива выделяется 4-хбайтовая ячейка, в которую помещается указатель (адрес) на вектор (arrMatr[0], arrMatr[1], arrMatr[2]), элементы которого располагаются в куче, занимая последовательные 4-хбайтовые ячейки. В этих ячейках содержатся ссылки на слоты соответствующих строк, а сами слоты размещаются в куче в непредсказуемом «порядке». Элементы каждой строки располагаются в слотах строки последовательно друг за другом. В ячейки элементов заносятся из значения.
Рисунок 5.3 Физическая структура динамической матрицы arrMatr, содержащей строки различных размеров
Массивы типа Variant
Переменной типа Variant, как указывалось в п. 3.3.10 , нельзя присвоить значение обычного статического массива. Это можно сделать только с помощью специальных функций VarArrayCreate и VarArrayOf.
Функция VarArrayCreate определена следующим образом:
Function VarArrayCreate(Const Bounds: Array Of Integer; VarType: Integer);
Здесь параметр Bounds является массивом, содержащим четное количество целых чисел, каждая пара которых определяет диапазон индекса, соответствующего паре. Параметр VarType определяет тип элементов массива. Он может принимать такие значения, как, например, varInteger, varDouble или varString соответствие таких значений и определяемых ими типов приводится в пособиях по Object Pascal. Например, для создания вектора V1 из девяти элементов целого типа и матрицы V2 типа Double (размерности 46), можно воспользоваться следующими операторами:
Var V1, V2: Variant;
. . .
V1:= VarArrayCreate([2, 10], varInteger);
V2:= VarArrayCreate([0,3, 0,5], varDouble);
Пример создания и использования массива типа Variant дают следующие строки:
Var A: Variant;
. . .
A:= VarArrayCreate([0, 2], varVariant);
A[0]:= 12e-6;
A[1]:= 20;
A[2]:= 'Количество = ' + IntToStr(A[1]);
ShowMessage(A[1]); ShowMessage(A[2]);
Label1.Caption:= A[2];
Функция VarArrayOf возвращает одномерный массив элементов, задаваемый параметром Values, и имеет следующий интерфейс:
Function VarArrayOf(Const Values: Array Of Variant): Variant;
Например, можно «превратить» элемент A[2] из вышеприведенного примера в вектор с помощью операторов:
A[2]:= VarArrayOf([-1.5, ’Параметр = ’, 20]);
ShowMessage(A[2][1] + IntToStr(A[2][2]));