СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

 

СТАТИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

структур, которые, фактически, представляют собой структурирован- ное множество примитивных, базовых, структур. Например, вектор может быть представлен упорядоченным множеством чисел. Поскольку

Векторы

данных с фиксированным числом элементов одного и того же типа ти- па. Каждый элемент вектора имеет уникальный в рамках заданного вектора номер. Обращение к элементу вектора выполняется по имени

Массивы

Логическая структура

- фиксированным набором элементов одного и того же типа; - каждый элемент имеет уникальный набор значений индексов; - количество индексов определяют мерность массива, например, два

Физическая структура

памяти ЭВМ. Для случая двумерного массива, состоящего из (k1-n1+1) строк и (k2-n2+1) столбцов физическая структура предс- тавлена на рис. 3.3.

Операции

Важнейшая операция физического уровня над массивом - доступ

к заданному элементу. Как только реализован доступ к элементу,

над ним может быть выполнена любая операция, имеющая смысл для

того типа данных, которому соответствует элемент. Преобразование

логической структуры в физическую называется процессом линеариза-

ции, в ходе которого многомерная логическая структура массива

преобразуется в одномерную физическую структуру.

В соответствии с формулами (3.3), (3.4) и по аналогии с век-

тором (3.1), (3.2) для двумерного массива c границами изменения

индексов: [B(1)..E(1)][B(2)..E(2)], размещенного в памяти по

строкам, адрес элемента с индексами [I(1),I(2)] может быть вычис-

лен как: Addr[I(1),I(2)] = Addr[B(1),B(2)] +

{ [I(1)-B(1)] * [E(2)-B(2)+1] + [I(2)-B(2)] }*SizeOf(Тип) (3.5)

Обобщая (3.5) для массива произвольной размерности:

Mas[B(1)..E(2)][B(2)..E(2)]...[B(n)..E(n)]

получим:

Addr[I(1),I(2),...,I(n)] = Addr[B(1),B(2),...B(n)] -

n n (3.6)

- Sizeof(Тип)*СУММА[B(m)*D(m)] + Sizeof(Тип)*СУММА[I(m)*D(m)]

m=1 m=1

где Dm зависит от способа размещения массива. При размещении по

строкам:

D(m)=[E(m+1)-B(m+1)+1]*D(m+1), где m = n-1,...,1 и D(n)=1

при размещении по столбцам:

D(m)=[E(m-1)-B(m-1)+1]*D(m-1), где m = 2,...,n и D(1)=1

При вычислении адреса элемента наиболее сложным является вы-

числение третьей составляющей формулы (3.6), т.к. первые две не

зависят от индексов и могут быть вычислены заранее. Для ускорения

вычислений множители D(m) также могут быть вычислены заранее и

сохраняться в дескрипторе массива. Дескриптор массива, таким об-

разом, содержит:

- начальный адрес массива - Addr[I(1),I(2),...,I(n)];

- число измерений в массиве - n;

- постоянную составляющую формулы линеаризации (первые две сос-

тавляющие формулы (3.6);

- для каждого из n измерений массива:

- значения граничных индексов - B(i), E(i);

- множитель формулы линеаризации - D(i).

Одно из определений массива гласит, что это вектор, каждый

элемент которого - вектор. Некоторые языки программирования поз-

воляют выделить из многомерного массива одно или несколько изме-

рений и рассматривать их как массив меньшей мерности.

Например, если в PL/1-программе объявлен двумерный массив:

DECLARE A(10,10) BINARY FIXED;

то выражение: A[*,I] - будет обращаться к одномерному массиву,

состоящему из элементов: A(1,I), A(2,I),...,A(10,I).

Символ-джокер "*" означает, что выбираются все элементы мас-

сива по тому измерению, которому соответствует заданный джокером

индекс. Использование джокера позволяет также задавать групповые

операции над всеми элементами массива или над выбранным его изме-

рением, например: A(*,I) = A(*,I) + 1

К операциям логического уровня над массивами необходимо от-

нести такие как сортировка массива, поиск элемента по ключу. Наи-

более распространенные алгоритмы поиска и сортировок будут расс-

мотрены в данной главе ниже.

Адресация элементов с помощью векторов Айлиффа

мента многомерного массива может потребовать много времени, пос- кольку при этом должны выполняться операции сложения и умножения, число которых пропорционально размерности массива. Операцию умно-

Специальные массивы

причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К

МАССИВЫ С МАТЕМАТИЧЕСКИМ ОПИСАНИЕМ МЕСТОПОЛОЖЕНИЯ НЕФОНОВЫХ

местоположения элементов со значениями отличными от фонового, мо- гут быть математически описаны, т. е. в их расположении есть ка- кая-либо закономерность.

ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ ПОСЛЕДОВАТЕЛЬНОГО

ных матриц заключается в запоминании ненулевых элементов в одно- мерном массиве и идентификации каждого элемента массива индексами строки и столбца, как это показано на рис. 3.5 а).

ПРЕДСТАВЛЕНИЕ РАЗРЕЖЕННЫХ МАТРИЦ МЕТОДОМ СВЯЗАННЫХ СТРУКТУР.

матриц обычно позволяют быстрее выполнять операции над матрицами и более эффективно использовать память, чем методы со связанными структурами. Однако последовательное представление матриц имеет

Множества

представляет собой набор неповторяющихся данных одного и того же типа. Множество может принимать все значения базового типа. Базо- вый тип не должен превышать 256 возможных значений. Поэтому базо-

Числовые множества

формирования множества - тип byte. Множество хранится в памяти как показано в таблице 3.3. Таблица 3.3

Символьные множества

Символьные множества хранятся в памяти также как и числовые

множества. Разница лишь в том, что хранятся не числа, а коды

ASCII символов.

Например, S : set of char; S:=['A','C'];

В этом случае представление множества S в памяти выглядит

следующим образом :

@S+0 - 00000000 . . . . . .

. . . . . . @S+31 - 00000000

@S+8 - 00001010

Множество из элементов перечислимого типа

хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит от ко- личества элементов в перечислимом типе.

Множество от интервального типа

хранится также, как множество, базовым типом которого является тип byte. Однако, в памяти занимает место, которое зависит от ко- личества элементов, входящих в объявленный интервал.

Операции над множествами

Пусть S1, S2, S3 : set of byte , Над этими множествами опре-

делены следующие специфические операции.

1) Объединение множеств: S2+S3. Результатом является множество,

содержащее элементы обоих исходных множеств.

2) Пересечение множеств: S2*S3. Результатом является множество,

содержащее общие элементы обоих исходных множеств.

3) Проверка на вхождение элемента в множество: a in S1. Результа-

том этой операции является значение логического типа - true, если

элемент a входит в множество S1, false - в противном случае.

Записи

Логическое и машинное представление записей

зующихся различным типом данных. Записи являются чрезвычайно удобным средством для представления программных моделей реальных объектов предметной области, ибо, как правило, каждый такой объ-

Операции над записями

Важнейшей операцией для записи является операция доступа к

выбранному полю записи - операция квалификации. Практически во

всех языках программирования обозначение этой операции имеет вид:

<имя переменной-записи>.<имя поля>

Так, для записи, описанной в начале п.3.5.1, конструкции:

stud1.num и stud1.math будут обеспечивать обращения к полям num и

math соответственно.

Над выбранным полем записи возможны любые операции, допусти-

мые для типа этого поля.

Большинство языков программирования поддерживает некоторые

операции, работающие с записью, как с единым целым, а не с от-

дельными ее полями. Это операции присваивания одной записи значе-

ния другой однотипной записи и сравнения двух однотипных записей

на равенство/неравенство. В тех же случаях, когда такие операции

не поддерживаются языком явно (язык C), они могут выполняться над

отдельными полями записей или же записи могут копироваться и

сравниваться как неструктурированные области памяти.

Записи с вариантами

В ряде прикладных задач программист может столкнуться с

группами объектов, чьи наборы свойств перекрываются лишь частич-

но. Обработка таких объектов производится по одним и тем же алго-

ритмам, если обрабатываются общие свойства объектов, или по раз-

ным - если обрабатываются специфические свойства. Можно описать

все группы единообразно, включив в описание все наборы свойств

для всех групп, но такое описание будет неэкономичным с точки

зрения расходуемой памяти и неудобным с логической точки зрения.

Если же описать каждую группу собственной структурой, теряется

возможность обрабатывать общие свойства по единым алгоритмам.

Для задач подобного рода развитые языки программирования (C,

PASCAL) предоставляют в распоряжение программиста записи с вари-

антами. Запись с вариантами состоит из двух частей. В первой час-

ти описываются поля, общие для всех групп объектов, моделируемых

записью. Среди этих полей обычно бывает поле, значение которого

позволяет идентифицировать группу, к которой данный объект при-

надлежит и, следовательно, какой из вариантов второй части записи

должен быть использован при обработке. Вторая часть записи содер-

жит описания непересекающихся свойств - для каждого подмножества

таких свойств - отдельное описание. Язык программирования может

требовать, чтобы имена полей-свойств не повторялись в разных ва-

риантах (PASCAL), или же требовать именования каждого варианта

(C). В первом случае идентификация поля, находящегося в вариант-

ной части записи при обращении к нему ничем не отличается от слу-

чая простой записи:

<имя переменной-записи>.<имя поля>

Во втором случае идентификация немного усложняется:

<имя переменной-записи>.<имя варианта>.<имя поля>

Рассмотрим использование записей с вариантами на примере.

Пусть требуется размещать на экране видеотерминала простые гео-

метрические фигуры - круги, прямоугольники, треугольники. Для

"базы данных", которая будет описывать состояние экрана, удобно

представлять все фигуры однотипными записями. Для любой фигуры

описание ее должно включать в себя координаты некоторой опорной

точки (центра, правого верхнего угла, одной из вершин) и код цве-

та. Другие же параметры построения будут разными для разных фи-

гур. Так для круга - радиус; для прямоугольника - длины непарал-

лельных сторон; для треугольника - координаты двух других вершин.

Запись с вариантами для такой задачи в языке PASCAL выгля-

дит, как:

type figure = record

fig_type : char; { тип фигуры }

x0, y0 : word; { координаты опорной точки }

color : byte; { цвет }

case fig_t : char of

'C': ( radius : word); { радиус окружности }

'R': (len1, len2 : word); { длины сторон прямоугольника }

'T': (x1,y1,x2,y2 : word); { координаты двух вершин }

end;

а в языке C, как:

typedef struct

{ char fig_type; /* тип фигуры */

unsigned int x0, y0; /* координаты опорной точки */

unsigned char color; /* цвет */

union

{ struct

{ unsigned int radius; /* радиус окружности */

} cyrcle;

struct

{ unsigned int len1, len2; /* длины сторон прямоугольника */

} rectangle;

struct

{ unsigned int x1,y1,x2,y2; /* координаты двух вершин */

} triangle;

} fig_t;

} figure;

И если в программе определена переменная fig1 типа figure, в

которой хранится описание окружности, то обращение к радиусу этой

окружности в языке PASCAL будет иметь вид: fig1.radius,

а в C: fig1.circle.radius

Поле с именем fig_type введено для представления идентифика-

тора вида фигуры, который, например, может кодироваться символа-

ми: "C"- окружность или "R"- прямоугольник, или "T"- треугольник.

Выделение памяти для записи с вариантами показано на рис.

3.12.

 

 

окружность прямоугольник треугольник

┌──────────┐ ┌──────────┐ ┌──────────┐

│ fig_type │1байт │ fig_type │1байт │ fig_type │1байт

├──────────┤ ├──────────┤ ├──────────┤

│ x0 │2байт │ x0 │2байт │ x0 │2байт

├──────────┤ ├──────────┤ ├──────────┤

│ y0 │2байт │ y0 │2байт │ y0 │2байт

├──────────┤ ├──────────┤ ├──────────┤

│ color │1байт │ color │1байт │ color │1байт

├──────────┤ ├──────────┤ ├──────────┤

│ radius │2байт │ len1 │2байт │ x1 │2байт

├──────────┤ ├──────────┤ ├──────────┤

│ не │6байт │ len2 │2байт │ y1 │2байт

│ исполь- │ ├──────────┤ ├──────────┤

│ зуется │ │ не │4байт │ x2 │2байт

│ │ │ исполь- │ ├──────────┤

│ │ │ зуется │ │ y2 │2байт

└──────────┘ └──────────┘ └──────────┘

Рис.3.12. Выделение памяти для записи с вариантами

Как видно из рисунка, под запись с вариантами выделяется в

любом случае объем памяти, достаточный для размещения самого

большого варианта. Если же выделенная память используется для

меньшего варианта, часть ее остается неиспользуемой. Общая для

всех вариантов часть записи размещается так, чтобы смещения всех

полей относительно начала записи были одинаковыми для всех вари-

антов. Очевидно, что наиболее просто это достигается размещением

общих полей в начале записи, но это не строго обязательно. Вари-

антная часть может и "вклиниваться" между полями общей части.

Поскольку в любом случае вариантная часть имеет фиксированный

(максимальный) размер, смещения полей общей части также останутся

фиксированными.

Таблицы

могут быть интегрированные структуры данных - векторы, массивы, другие записи. Аналогично и элементами векторов и массивов могут быть также интегрированные структуры. Одна из таких сложных

Операции логического уровня над статическими

Структурами. Поиск

ка данных и сортировок, выполняемых на статических структурах данных, так как это характерные операции логического уровня для таких структур. Однако, те же операции и те же алгоритмы примени-

Последовательный или линейный поиск

доченном наборе данных, по значению его ключа является последова- тельный просмотр каждого элемента набора, который продолжается до тех пор, пока не будет найден желаемый элемент. Если просмотрен

Бинарный поиск

ется метод бинарного (дихотомического, двоичного) поиска, который выполняется в заведомо упорядоченной последовательности элемен- тов. Записи в таблицу заносятся в лексикографическом (символьные

Операции логического уровня над статическими

Структурами. Сортировка

ким образом: имеется некоторое неупорядоченное входное множество ключей и должны получить выходное множество тех же ключей, упоря- доченных по возрастанию или убыванию в численном или лексикогра-

Сортировки выборкой

чески "дословно" сформулированную выше стратегию выборки. Порядок алгоритма простой выборки - O(N^2). Количество пересылок - N. Алгоритм сортировки простой выборкой иллюстрируется прог-

Еще одна модификация пузырьковой сортировки носит название

мотров чередуются: за просмотром от начала к концу следует прос- мотр от конца к началу входного множества. При просмотре в прямом направлении запись с самым большим ключом ставится на свое место

Сортировки включением

лизации стратегии включения. Порядок алгоритма сортировки просты- ми вставками - O(N^2), если учитывать только операции сравнения. Но сортировка требует еще и в среднем N^2/4 перемещений, что де-

Сортировки распределением.

ления ключей сортируемой последовательности в виде чисел в неко- торой системе счисления P. Число проходов сортировка равно макси- мальному числу значащих цифр в числе - D. В каждом проходе анали-

Прямой доступ и хеширование

В рассмотренных выше методах поиска число проб при поиске в

лучшем случае было пропорционально log2(N). Естественно, возника-

ет желание найти такой метод поиска, при котором число проб не

зависело бы от размера таблицы, а в идеальном случае поиск сво-

дился бы к одной пробе.

Таблицы прямого доступа

быстрый поиск, вляется таблица прямого доступа. В такой таблице ключ является адресом записи в таблице или может быть преобразо- ван в адрес, причем таким образом, что никакие два разных ключа

Таблицы со справочниками

справочников. Основная таблица содержит записи в произвольном по- рядке. В дополнение к основной строится справочная или индексная таблица, записи которой состоят всего из двух полей: ключа и ад-

Хешированные таблицы и функции хеширования

множество ключей является лишь небольшим подмножеством множества всех теоретически возможных ключей. Поскольку память является од- ним из самых дорогостоящих ресурсов вычислительной системы, из

Проблема коллизий в хешированных таблицах

Удачно подобранная функция хеширования может минимизировать

число коллизий, но не может гарантировать их полного отсутствия.

Ниже мы рассмотрим методы разрешения проблемы коллизий в хеширо-

ванных таблицах.

ПОВТОРНОЕ ХЕШИРОВАНИЕ. Повторное хеширование, известное так-

же под названием открытой таблицы, предусматривает следующее: ес-

ли при попытке записи в таблицу оказывается, что требуемое место

в таблице уже занято, то значение записывается в ту же таблицу на

какое-то другое место. Другое место определяется при помощи вто-

ричной функции хеширования H2, аргументом которой в общем случае

может быть и исходное значение ключа и результат предыдущего хе-

ширования: r = H2(k,r`), где r` - адрес, полученный при предыду-

щем применении функции хеширования. Если полученный в результате

применения функции H2 адрес также оказывается занятым, функция H2

применяется повторно - до тех пор, пока не будет найдено свобод-

ное место. Простейшей функцией вторичного хеширования является

функция: r = r` + 1. Эту функцию иногда называют функцией линей-

ного опробования. Фактически при применении линейного опробова-

ния, если "законное" место записи (т.е. слот, расположенный по

адресу, получаемому из первичной функции хеширования) уже занято,

то запись занимает первое свободное место за "законным" (таблица

при этом рассматривается как кольцо). Выборка элемента по ключу

производится аналогичным образом: адрес записи вычисляется по

первичной функции хеширования и ключ записи, расположенной по

этому адресу, сравнивается с искомым. Если запись непуста, и клю-

чи не совпадают, то продолжается поиск с применением вторичной

функции хеширования. Поиск заканчивается, когда найдена запись с

искомым ключом (успешное завершение) или перебрана вся таблица

(неуспешное завершение).

Приведенный ниже программный пример иллюстрирует применение

метода линейного опробования для разрешения коллизий. В составля-

ющем этот пример модуле определены процедуры/функции инициализа-

ции таблицы, вставки элемента в таблицу и поиска элемента в

таблице. Процедура инициализации является обязательной для хеши-

рованных таблиц, так как перед началом работы с таблицей для нее

должна быть выделена память и заполнена "пустыми" (свободными)

записями. В качестве признака пустой записи значение ключа ис-

пользована константа EMPTY, которая при отладке была определена

как -1. Функция первичного хеширования - Hash - выполняет деление

по модулю.

{==== Программный пример 3.19 ====}

{ Хешированная таблица с повторным перемешиванием }

Unit HashTbl;

Interface

Procedure Init;

Function Insert(key : integer) : boolean;

Function Fetch(key : integer) : integer;

Implementation

const N=...; { число записей в таблице }

type Seq = array[1..N] of integer; { тип таблицы }

var tabl : Seq; { таблица }

{ Хеширование - деление по модулю }

Function Hash(key : integer) : integer;

begin Hash:= key mod N+1; end;

{ Инициализация таблицы - заполнение пустыми записями }

Procedure Init;

var i : integer;

begin for i:=1 to N do tabl[i]:=EMPTY; end;

{ Добавление элемента в таблицу }

Function Insert(key : integer) : boolean;

Var addr, a1 : integer;

begin addr:=Hash(key); { вычисление адреса }

if tabl[addr]<>EMPTY then { если адрес занят }

begin a1:=addr;

repeat { поиск свободного места }

addr:=addr mod N+1;

until (addr=a1) or (tabl[addr]=EMPTY);

if tabl[addr]<>EMPTY then { нет свободного места }

begin Insert:=false; Exit; end;

end; tabl[addr]:=key; { запись в таблицу }

Insert:=true; end;

{ Выборка из таблицы - возвращает адрес найденного ключа

или EMPTY - если ключ не найден }

Function Fetch(key : integer) : integer;

Var addr, a1 : integer;

begin addr:=Hash(key);

if tabl[addr]=EMPTY then

Fetch:=EMPTY { место свободно - ключа нет в таблице }

else if tabl[addr]=key then

Fetch:=addr { ключ найден на своем месте }

else begin { место занято другим ключом }

a1:=(addr+1) mod N;

{ Поиск, пока не найден ключ или не сделан полный оборот }

while (tabl[a1]<>key) and (a1<>addr) do addr:=(a1+1) mod N;

if tabl[a1]<>key then Fetch:=EMPTY else Fetch:=a1;

end;

end.

Повторное хеширование обладает существенным недостатком:

число коллизий зависит от порядка заполнения таблицы. Ниже приве-

ден пример работы программы примера 3.19 для двух случаев. В обо-

их случаях размер таблицы задавался равным 15. В первом случае в

таблицу заносилась следующая последовательность из 14 чисел-клю-

чей: 58 0 19 96 38 52 62 77 4 15 79 75 81 66

Результирующая таблица имела такой вид:

0 15* 62 77 19 4* 96 52 38 79* 75* 81* 66* 58 E

Буквой "E" обозначено свободное место в таблице. Значком "*" по-

мечены элементы, стоящие не на своих "законных" местах. Во втором

случае те же ключи заносились в таблицу в иной последовательнос-

ти, а именно:

0 75 15 62 77 19 4 79 96 81 66 52 38 58

Результирующая таблица имела вид:

0 75* 15* 62* 77* 19* 4* 79* 96* 81* 66* 52* 38* 58 E

Большее число коллизий во втором случае объясняется тем, что если

ключ не может быть записан по тому адресу, который вычислен для

него первичной функцией хеширования, он записывается на свободное

место, а это пока свободное место принадлежит (по первичной функ-

ции хеширования другому ключу, который впоследствии тоже может

поступить на вход таблицы.

ПАКЕТИРОВАНИЕ. Сущность метода пакетирования состоит в том,

что записи таблицы объединяются в пакеты фиксированного, относи-

тельно небольшого размера. Функция хеширования дает на выходе не

адрес записи, а адрес пакета. После нахождения пакета, в пакете

выполняется линейный поиск по ключу. Пакетирование позволяет

сгладить нарушения равномерности распределения ключей по прост-

ранству пакетов и, следовательно, уменьшить число коллизий, но не

может гарантированно их предотвратить. Пакеты также могут пере-

полняться. Поэтому пакетирование применяется как дополнение к бо-

лее радикальным методам - к методу повторного хеширования или к

методам, описанным ниже. В программном примере 3.20, применен ме-

тод пакетирования без комбинации с другими методами. При общем

размере таблицы - 15 и размере пакета - 3 уже ранее опробованная

последовательность:

58 0 75 19 96 38 81 52 66 62 77 4 15 79

записалась в результирующую таблицу без коллизий (значком "|"

обозначены границы пакетов):

0 75 15| 96 81 66| 52 62 77| 58 38 E| 19 4 79

{==== Программный пример 3.20 ====}

{ Хешированная таблица с пакетами }

Unit HashTbl;

Interface

Procedure Init;

Function Insert(key : integer) : boolean;

Function Fetch(key : integer) : integer;

Implementation

const N=...; { число записей в таблице }

const NB=...; { размер пакета }

type Seq = array[1..N] of integer; { тип таблицы }

var tabl : Seq; { таблица }

{ Инициализация таблицы - заполнение пустыми записями }

Procedure Init;

var i : integer;

begin for i:=1 to N do tabl[i]:=EMPTY; end;

{ Хеширование - деление по модулю на число пакетов }

Function Hash(key : integer) : integer;

begin Hash:= key mod (N div NB); end;

{ Добавление элемента в таблицу }

Function Insert(key : integer) : boolean;

Var addr, a1, pa : integer;

begin pa:=Hash(key); { вычисление номера пакета }

addr:=pa*NB+1; { номер 1-го эл-та в пакете }

Insert:=true;

a1:=addr; { поиск свободного места в пакете }

while (a1<addr+NB) and (tabl[a1]<>EMPTY) do a1:=a1+1;

if a1<addr+NB then { своб.место найдено } tabl[a1]:=key

else { своб.место не найдено } Insert:=false;

end;

{ Выборка из таблицы }

Function Fetch(key : integer) : integer;

Var addr, a1 : integer;

begin

addr:=Hash(key)*NB+1; { номер 1-го эл-та в пакете }

a1:=addr; { поиск в пакете }

while (a1<addr+NB) and (tabl[a1]<>key) do a1:=a1+1;

if a1<addr+NB then Fetch:=a1 else Fetch:=EMPTY;

end;

END.

ОБЩАЯ ОБЛАСТЬ ПЕРЕПОЛНЕНИЙ. Для таблицы выделяются две об-

ласти памяти: основная область и область переполнений. Функция

хеширования на выходе дает адрес записи или пакета в основной об-

ласти. При вставке записи, если ее "законное" место в основной

области уже занято, запись заносится на первое свободное место в

области переполнения. При поиске, если "законное" место в основ-

ной занято записью с другим ключом, выполняется линейный поиск в

области переполнения. Программная иллюстрация приведена в примере

3.21.

При размере таблицы N=15 и размере области переполнения NPP=

6 запись последовательности чисел:

58 0 75 82 96 38 88 52 66 62 78 4 15 79

дает такой вид таблицы (значком "|" показана граница между основ-

ной областью и областью переполнения):

0 -1 62 78 4 -1 96 82 38 -1 -1 -1 -1 58 -1 | 75 88 52 66 15 79

{==== Программный пример 3.21 ====}

{ Хешированная таблица с областью переполнения }

Unit HashTbl;

Interface

Procedure Init;

Function Insert(key : integer) : boolean;

Function Fetch(key : integer) : integer;

Implementation

const N=...; { число записей в таблице }

const NPP=...; { размер области переполнения }

type Seq = array[1..N+NPP] of integer; { тип таблицы - массив,

в котором первые N эл. составляют основную область, а следующие

NPP эл.тов - область переполнения }

var tabl : Seq; { таблица }

Procedure Init;{Инициализация таблицы-заполнение пустыми записями}

var i : integer;

begin for i:=1 to N+NPP do tabl[i]:=EMPTY; end;

{ Хеширование - деление по модулю }

Function Hash(key : integer) : integer;

begin Hash:= key mod N+1; end;

{ Добавление элемента в таблицу }

Function Insert(key : integer) : boolean;

Var addr : integer;

begin

addr:=Hash(key); { вычисление адреса }

Insert:=true;

if tabl[addr]=EMPTY then

{ если место в основной табл.свободно - пишем на него }

tabl[addr]:=key

else begin { если место в основной таблице занято }

{ поиск свободного места в таблице переполнения }

addr:=N+1; { нач.адрес табл.переполнения }

while (tabl[addr]<>EMPTY) and (addr<N+NPP) do addr:=addr+1;

if tabl[addr]<>EMPTY then Insert:=false { нет места }

else tabl[addr]:=key; { запись в обл.переполнения }

end;

end;

Function Fetch(key : integer) : integer; { Выборка из таблицы }

Var addr : integer;

begin

addr:=Hash(key);

if tabl[addr]=key then { найден в основной таблице }

Fetch:=addr

else if tabl[addr]=EMPTY then { отсутствует в таблице }

Fetch:=EMPTY

else { линейный поиск в таблице переполнения }

begin addr:=N+1; { начало табл.переполнения }

while (addr<=N+NPP) and (tabl[addr]<>key) do addr:=addr+1;

if tabl[addr]<>key then {отсутствует в таблице} Fetch:=EMPTY

else { найден в таблице переполнения } Fetch:=addr;

end;

end;

END.

Общая область переполнений требует больше памяти, чем откры-

тые таблицы: если размер открытой таблицы может не превышать раз-

мера фактического множества записей, то здесь еще требуется до-

полнительная память для переполнений. Однако, эффективность

доступа к таблице с областью переполнения выше, чем к таблице с

повторным хешированием. Если в таблице с повторным хешированием

при неудачной первой пробе приходится продолжать поиск во всей

таблице, то в таблице с областью переполнения продолжение поиска

ограничивается только областью переполнения, размер которой зна-

чительно меньше размера основной таблицы.

РАЗДЕЛЬНЫЕ ЦЕПОЧКИ ПЕРЕПОЛНЕНИЙ. Естественным представляется

желание ограничить продолжение поиска лишь множеством тех значе-

ний ключей, которые претендуют на данное место в основной табли-

це. Эта идея реализуется в таблицах с цепочками переполнения. В

структуру каждой записи добавляется еще одно поле - указатель на

следующую запись. Через эти указатели записи с ключами-синонимами

связываются в линейный список, начало которого находится в основ-

ной таблице, а продолжение - вне ее. При вставке записи в таблицу

по функции хеширования вычисляется адрес записи (или пакета) в

основной таблице. Если это место в основной таблице свободно, то

запись заносится в основную таблицу. Если же место в основной

таблице занято, то запись располагается вне ее. Память для такой

записи с ключом-синонимом может выделяться либо динамически для

каждой новой записи, либо для синонима назначается элемент из за-

ранее выделенной области переполнения. После размещения запи-

си-синонима поле указателя из записи основной таблицы переносится

в поле указателя синонима, а на его место в записи основной таб-

лицы записывается указатель на только что размещенный синоним.

Хотя в таблицах с цепочками переполнений и увеличивается

размер каждой записи и несколько усложняется обработка за счет

обработки указателей, сужение области поиска дает весьма значи-

тельный выигрыш в эффективности.

В программной иллюстрации примера 3.21 используется стати-

ческая область переполнения, элементы которой динамически распре-

деляются по цепочкам. Роль указателя играют индексы в области

переполнения. Специальное значение индекса EMPTY представляет

пустой указатель.

При объеме основной области - 15 и области переполнения - 6

включение в таблицу следующей последовательности чисел:

58 0 75 82 96 38 88 52 66 62 78 4 15 79

привело к такому содержимому основной таблицы и области перепол-

нения (каждый элемент представлен парой <число>:<указатель>,Е-

пустое значение):

0:20 E:E 62:E 78:E 4:21 E:E 96:19 82:18 38:E E:E E:E

E:E E:E 58:17 E:E 75:E 88:E 52:E 66:E 15:16 79:E

Это содержимое таблицы с цепочками переполнения наглядно предс-

тавлено на рис. 3.18.

┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐

│ 0│ │62│78│ 4│ │96│82│38│ │ │ │ │58│ │

├──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┤

└─┼┴──┴──┴──┴─┼┴──┴─┼┴─┼┴──┴──┴──┴──┴──┴──┴──┘

└>┌──┐ └>┌──┐│ └>┌──┐

│15│ │79││ │52│

├──┤ ├──┤│ ├──┤

└─┼┘ └──┘│ └──┘

└>┌──┐ └>┌──┐

│75│ │66│

├──┤ ├──┤

└──┘ └──┘

Рис. 3.18. Цепочки переполнения

{==== Программный пример 3.21 ====}

{ Хешированная таблица с цепочками переполнений }

Unit HashTbl;

Interface

Procedure Init;

Function Insert(key : integer) : boolean;

Function Fetch(key : integer) : integer;

Implementation

const N=...; { число записей в таблице }

const NPP=...; { размер области переполнения }

type rec = record { запись таблицы }

key : integer; { ключ }

next : integer; { указатель на синоним }

end;

type Seq = array[1..N+NPP] of rec; { тип таблицы -

основная область и область переполнения }

var tabl : Seq; { таблица }

{ Хеширование - деление по модулю }

Function Hash(key : integer) : integer;

begin

Hash:= key mod N+1; end;

{ Инициализация таблицы - заполнение пустыми записями }

Procedure Init;

var i : integer;

begin

for i:=1 to N+NPP do

begin

tabl[i].key:=EMPTY; tabl[i].next:=EMPTY;

end;

end;

{ Добавление элемента в таблицу }

Function Insert(key : integer) : boolean;

Var addr1, addr2 : integer; {адреса- основной, переполнение}

begin

addr1:=Hash(key); { вычисление адреса }

Insert:=true;

if tabl[addr1].key=EMPTY then

{ эл-т в основной области свободен - запись в него }

tabl[addr1].key:=key

else { эл-т в основной области занят }

{ поиск свободного места в таблице переполнения }

begin addr2:=N+1;

while (tabl[addr2].key<>EMPTY) and (addr2<N+NPP) do

addr2:=addr2+1;

if tabl[addr2].key<>EMPTY then Insert:=false { нет места }

else { запись в область переполнения и

коррекция указателей в цепочке }

begin tabl[addr2].key:=key;

tabl[addr2].next:=tabl[addr1].next;

tabl[addr1].next:=addr2;

end;

end;

end;

Function Fetch(key : integer) : integer; { Выборка из таблицы }

Var addr : integer;

begin

addr:=Hash(key);

if tabl[addr].key=key then { найден на своем месте }

Fetch:=addr

else if tabl[addr].key=EMPTY then { нет в таблице }

Fetch:=EMPTY

else { поиск в таблице переполнения }

begin addr:=tabl[addr].next;

while (addr<>EMPTY) and (tabl[addr].key<>key) do

addr:=tabl[addr].next;

Fetch:=addr; { адрес в обл.переполнения или EMPTY }

end; end;

END.

При любом методе построения хешированных таблиц возникает

проблема удаления элемента из основной области. Хотя эта глава и

посвящена у нас статическим структурам данных, но в реальных за-

дачах абсолютно неизменные структуры встречаются крайне редко.

При удалении удаляемая запись должна прежде всего быть найдена в

таблице. Если запись найдена вторичным хешированием (открытая

таблица) или в области переполнения (таблица с общей областью пе-

реполнения), то удаляемую запись достаточно пометить как пустую.

Если запись найдена в цепочке (таблица с цепочками переполнений),

то необходимо также скорректировать указатель предыдущего элемен-

та в цепочке. Если же удаляемая запись находится на своем "закон-

ном" месте, то, пометив ее как пустую, мы тем самым сделаем не-

возможным поиск ее синонимом, возможно, имеющихся в таблице.

Одним из способов решения этой проблемы может быть пометка записи

специальным признаком "удаленная". Этот способ часто применяется

в таблицах с повторным хешированием и с общей областью переполне-

ний, но он не обеспечивает ни освобождения памяти, ни ускорения

поиска при уменьшении числа элементов в таблице. Другой способ -

найти любой синоним удаляемой записи и перенести его на "закон-

ное" место. Этот способ легко реализуется в таблицах с цепочками,

но требует значительных затрат в таблицах с другой структурой,

так как требует поиска во всей открытой таблицы или во всей облас-

ти переполнения с вычислением функции хеширования для каждого

проверяемого элемента.