- •Структуры данных и алгоритмы их обработки (Учебное пособие)
- •Москва 2007
- •1. Структуры данных и алгоритмы 6
- •1.2. Информация и ее представление
- •1.2.1. Природа информации
- •1.2.2. Хранение информации
- •1.2.3. Классификация структур данных
- •1.3. Операции над структурами данных
- •1.4. Порядок алгоритма
- •1.5. Структурность данных и технологии программирования
- •Контрольные вопросы
- •2. Простые структуры данных
- •2.1. Порядковые типы
- •2.2. Целочисленный тип
- •2.3. Символьный тип
- •2.4. Перечисляемый тип
- •2.5. Интервальный тип
- •2.6. Логический тип
- •2.7. Битовый тип
- •2.8. Вещественный тип
- •2.9. Указательный тип
- •Контрольные вопросы
- •3. Объектные типы данных
- •3.1. Объявление и реализация классов
- •Interface
- •Implementation
- •3.2. Директивы видимости
- •3.3. Свойства классов
- •3.4. Структурированная обработка ошибок
- •3.5. Применение объектов
- •Контрольные вопросы
- •4. Статические структуры данных
- •4.1. Векторы
- •4.2. Массивы
- •4.3. Множества
- •4.4. Записи
- •4.5. Таблицы
- •4.6. Операции над статическими структурами
- •4.6.1. Алгоритмы поиска
- •4.6.2. Алгоритмы сортировки
- •Самые медленные алгоритмы сортировки
- •Быстрые алгоритмы сортировки
- •Самые быстрые алгоритмы сортировки
- •Сортировка слиянием
- •Контрольные вопросы
- •5. Полустатические структуры данных
- •5.1. Стеки
- •5.1.1. Стеки в вычислительных системах
- •5.2. Очереди fifo
- •5.2.1. Очереди с приоритетами
- •5.2.2. Очереди в вычислительных системах
- •5.3. Деки
- •5.3.1. Деки в вычислительных системах
- •5.4. Строки
- •5.4.1. Операции над строками
- •5.4.2. Представление строк в памяти
- •3 A b d 8 p q r s t u V w
- •V w ptr nil
- •1 8 П р е д с т а в
- •2 7 ? Л е н и е ?
- •1 8 С т р о к и з
- •1 8 В е н ь я м и
- •1 8 С у п р а в л
- •1 8 Я е м о й д л
- •1 4 И н о й ? ? ? ? nil
- •6.2. Связные линейные списки
- •6.2.1. Машинное представление связных линейных списков
- •Inf next
- •Inf next
- •Inf nil
- •6.2.2. Реализация операций над связными линейными списками
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •Inf next
- •6.2.3. Применение линейных списков
- •6.3. Нелинейные разветвленные списки
- •6.3.1. Основные понятия
- •6.3.2. Представление списковых структур в памяти
- •6.3.3. Операции обработки списков
- •6.4. Язык программирования lisp
- •6.5. Управление динамически выделяемой памятью
- •Контрольные вопросы
- •7. Нелинейные структуры данных
- •7.1. Графы и деревья
- •(B) (a) (b) (a)
- •V0 v1 v2 v5 v6 v3 v4 v7 v8 v9 v10 (v0) (v1) (v7) (v8) (v9) (v10) (v3) (v2) (v4) (v5) (v6)
- •7.3. Бинарные деревья
- •7.3.1. Представление бинарных деревьев
- •7.3.2. Прохождение бинарных деревьев
- •7.4. Алгоритмы на деревьях
- •7.4.1. Сортировка с прохождением бинарного дерева
- •7.4.2. Сортировка методом турнира с выбыванием
- •7.4.3. Применение бинарных деревьев для сжатия информации
- •7.4.4. Представление выражений с помощью деревьев
- •7.5. Представление сильноветвящихся деревьев
- •Контрольные вопросы
- •8. Методы ускорения доступа к данным
- •8.1. Хеширование данных
- •8.1.1. Функции хеширования
- •8.1.2. Оценка качества хеш-функции
- •8.1.3. Методы разрешения коллизий
- •8.1.4. Переполнение таблицы и рехеширование
- •8.2. Организация данных для поиска по вторичным ключам
- •8.2.1. Инвертированные индексы
- •8.2.2. Битовые карты
- •Контрольные вопросы
- •Листинги рабочих примеров
- •1. Создание и управление списковыми объектами
- •Interface
- •Implementation
- •Interface
- •Implementation
- •3. Моделирование работы стека
- •Interface
- •Implementation
- •Interface
- •Implementation
- •4. Создание и редактирование бинарных деревьев
- •5. Создание и редактирование сильноветвящихся деревьев
- •Задания для самостоятельной работы
- •Литература
- •144Кафедра Вычислительной Техники и Программирования Московского Государственного Открытого Университета
4.5. Таблицы
В предыдущем разделе было отмечено, что полями записи могут быть интегрированные структуры – векторы, массивы, другие записи. Аналогично элементами векторов и массивов могут быть также интегрированные структуры. Одна из таких структур – таблица. С логической точки зрения таблица представляет вектор, элементами которого являются записи. Таблицы не имеют стандартного типа данных в языке Паскаль.
В таблицах доступ к элементам производится не по номеру (индексу), а по ключу – значению одного из свойств объекта, описываемого записью-элементом таблицы. Ключ идентифицирует данную запись во множестве однотипных. К ключу предъявляется требование уникальности в данной таблице. Ключ может включаться в состав записи и быть одним из ее полей, но может и не включаться, а вычисляться по положению записи. Таблица может иметь один или несколько ключей. Например, при интеграции в таблицу записей о студентах выборка может производиться как по личному номеру студента, так и по фамилии.
Основной операцией при работе с таблицами является операция доступа к записи по ключу. Она реализуется процедурой поиска. Поскольку поиск может быть значительно более эффективным в таблицах, упорядоченных по значениям ключей, довольно часто над таблицами необходимо выполнять операции сортировки. Такие операции рассматриваются в разделе 4.6.
Различают таблицы с фиксированной и переменной длиной записи. Очевидно, что таблицы, объединяющие записи идентичных типов, будут иметь фиксированные длины записей. Необходимость в переменной длине может возникнуть в задачах, подобных тем, которые рассматривались для записей с вариантами. Как правило, таблицы для таких задач и составляются из записей с вариантами, т.е. сводятся к фиксированной (максимальной) длине записи.
Значительно реже встречаются таблицы с действительно переменной длиной записи. Хотя в таких таблицах и экономится память, но возможности работы с такими таблицами ограничены, т.к. по номеру записи невозможно определить ее адрес. Таблицы с записями переменной длины обрабатываются только последовательно – в порядке возрастания номеров записей.
Доступ к элементу такой таблицы обычно осуществляется в два шага. На первом шаге выбирается постоянная часть записи, в которой содержится (в явном или неявном виде) длина записи. На втором шаге выбирается переменная часть записи в соответствии с ее длиной. Прибавив к адресу текущей записи ее длину, получают адрес следующей записи.
4.6. Операции над статическими структурами
4.6.1. Алгоритмы поиска
Алгоритмы поиска данных и сортировки, выполняемые на статических структурах данных, являются типичными операциями логического уровня. Однако те же операции и алгоритмы применимы и к данным, имеющим логическую структуру таблицы, но физически размещенным в динамической памяти и на внешней памяти, а также к логическим таблицам любого физического представления, обладающим изменчивостью.
Функция сравнения. Само действие поиска элемента в наборе данных требует возможности отличать элементы друг от друга. Очевидно, сравнение числовых типов не вызывает трудности. В случае сравнения строк процедура усложняется. Можно выполнять сравнение чувствительное или нечувствительное к регистру, сравнение по локальным таблицам символов, когда оно выполняется на основе алгоритмов, специфичных для определенной страны или языка и т.д. При работе с объектами вообще не существует заранее определенной схемы сравнения за исключением сравнения указателей на эти объекты.
В таком случае лучше всего рассматривать процедуру сравнения в виде «черного ящика» – функции с четко определенным интерфейсом, которая в качестве входных параметров принимает указатели на два элемента и возвращает результат сравнения – первый элемент больше, меньше или равен второму.
В последующем изложении все описания алгоритмов даны для работы с классом TList, а функции сравнения имеют следующий тип:
{ Объявление прототипа функции сравнения }
TCompareFunc=function(aData1,aData2:Pointer):Integer;
Тип входных параметров определяет сама функция, и решает, привести ли их к определенному классу или просто к типу, который не является указателем. Пример реализации функции сравнения для целых типа LongWord приведен ниже.
{ Функция сравнения двух целых чисел, заданных своими указателями }
function CompareLongWord(aData1, aData2: Pointer): Integer;
begin
{ Значение первого элемента меньше значения второго }
if LongWord(aData1^) < LongWord(aData2^) then
Result:=-1else
{ Значения элементов равны }
if LongWord(aData1^) = LongWord(aData2^) then
Result:=0 else
{ Значение первого элемента больше значения второго }
Result:=1;
end;
Линейный поиск. Единственно возможным методом поиска элемента по значению ключа, находящегося в неупорядоченном наборе данных, является последовательный (линейный) просмотр каждого элемента, который продолжается до тех пор, пока не будет найден искомый элемент. Если просмотрен весь набор, но элемент не найден, искомый ключ отсутствует. Для последовательного поиска в среднем требуется (n+1)/2 сравнений и порядок алгоритма линейный O(n).
Программная иллюстрация линейного поиска в неупорядоченном массиве приведена ниже, где aList – исходный массив, aItem – искомый ключ; функция возвращает индекс найденного элемента или -1, если элемент отсутствует.
{ Линейный поиск в неотсортированном массиве }
function LineNonSortedSearch(aList: TList;
aItem: Pointer; aCompare: TCompareFunc): Integer;
var i: Integer;
begin
Result:=-1;
for i:=0 to aList.Count-1 do
if aCompare(aList.List[i],aItem) = 0 then
begin
Result:=i;
Break;
end;
end;
Последовательный поиск для отсортированного массива ничем не отличается от приведенного и имеет порядок алгоритма O(n). Однако алгоритм можно несколько улучшить. Если искомого элемента нет в массиве, поиск можно выполнить быстрее, т.к. итерации должны выполняться только до тех пор, пока не будет найден элемент, больший или равный искомому. Все последующие элементы будут больше искомого и поиск можно прекратить.
{ Линейный поиск в отсортированном массиве }
function LineSortedSearch(aList: TList;
aItem: Pointer; aCompare: TCompareFunc): Integer;
var i, CompareResult: Integer;
begin
Result:=-1;
{ Искать первый элемент, больший или равный искомому }
for i:=0 to aList.Count-1 do
begin
CompareResult:=aCompare(aList.List[i], aItem);
if CompareResult >= 0 then
begin
if CompareResult = 0 then
Result:=i else
Result:=-1;
Exit;
end;
end;
end;
Обратите внимание, функция сравнения вызывается только один раз при каждой итерации, т.к. временные параметры ее выполнения заранее не известны, и поэтому вызывать ее желательно следует как можно реже.
Бинарный поиск. Другим методом доступа к элементу является бинарный (двоичный или дихотомичный) поиск, который выполняется в заведомо упорядоченной последовательности элементов. Элементы массива должны располагаться в лексикографическом (символьные ключи) или численно (числовые ключи) возрастающем порядке. Для достижения упорядоченности может быть использован один из методов сортировки.
В методе сначала приближенно определяется запись в середине массива и анализируется значение ее ключа. Если оно слишком велико, то анализируется значение ключа, соответствующего записи в середине первой половины массива, и указанная процедура повторяется в этой половине до тех пор, пока не будет найдена требуемая запись. Если значение ключа слишком мало, испытывается ключ, соответствующий записи в середине второй половины массива, и процедура повторяется в этой половине.
Процесс продолжается до тех пор, пока не найден требуемый ключ или не станет пустым интервал, в котором осуществляется поиск. Чтобы найти элемент, в худшем случае требуется log2(N) сравнений, что значительно лучше, чем при последовательном поиске. Программная иллюстрация бинарного поиска в упорядоченном массиве приведена ниже.
{ Двоичный поиск }
function BinarySearch(aList: TList;
aItem: Pointer; aCompare: TCompareFunc): Integer;
var L, R, M, CompareResult: Integer;
begin
{ Значения индексов первого и последнего элементов }
L:=0; R:=aList.Count-1;
while L <= R do
begin
{ Индекс среднего элемента }
M:=(L+R)div2;
{ Сравнить значение среднего элемента с искомым }
CompareResult:=aCompare(aList.List[M], aItem);
{ Если значение среднего элемента меньше искомого -
переместить левый индекс на позицию до среднего индекса }
if CompareResult < 0 then
L:=M+1 else
{ Если значение среднего элемента больше искомого -
переместить правый индекс на позицию после среднего индекса }
if CompareResult > 0 then
R:=M-1 else
begin
Result:=M;
Exit;
end;
end;
Result:=-1;
end;
Трассировка бинарного поиска ключа 275 в исходной последовательности: {75, 151, 203, 275, 318, 489, 524, 519, 647, 777} представлена в табл. 4.7.
Табл. 4.7. Трассировка бинарного поиска.
Итерация |
L |
R |
M |
a[M] |
1 |
1 |
10 |
5 |
318 |
2 |
1 |
4 |
2 |
151 |
3 |
3 |
4 |
3 |
203 |
4 |
4 |
4 |
4 |
275 |
Алгоритм бинарного поиска можно представить несколько иначе, используя рекурсивное описание. В этом случае граничные индексы интервала L и R являются параметрами алгоритма. Рекурсивная процедура бинарного поиска представлена ниже. Для выполнения поиска необходимо при вызове функции задать значения ее формальных параметров L и R – 1 и n соответственно.
{ Рекурсивный алгоритм двоичного поиска }
functionBinaryRecurSearch(aList:TList;
aItem: Pointer; L,R: Integer; aCompare: TCompareFunc): Integer;
var i, CompareResult: Integer;
begin
{ Проверка ширины интервала }
if L > R then
Result:=-1 else
begin
i:=(L + R) div 2;
CompareResult:=aCompare(aList.List[i], aItem);
{ Ключ найден, возврат индекса }
if CompareResult = 0 then
Result:=i else
if CompareResult = -1 then
{ Поиск в правом подинтервале }
Result:=BinaryRecurSearch(aList,aItem,i+1,R,aCompare) else
{ Поиск в левом подинтервале }
Result:=BinaryRecurSearch(aList,aItem,L,i-1,aCompare);
end;
end;