ПОИСК С ПЕРЕУПОРЯДОЧИВАНИЕМ СПИСКА

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

Если существует статистическая информация о частоте использования ключей различных записей (например, при построении таблицы операций компилятора), то построение таблицы можно выполнить один раз до осуществления операций поиска.

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

Метод перемещения в начало является эффективным только для таблицы, организованной как список. В этом методе при успешном поиске извлеченная запись удаляется из своей позиции в списке и помещается в голову списка (очевидно, что операции исключения и включения элементов выполнять не нужно, перемещение реализуется переключением связей между элементами списка). В приведенной на рис. 6.1 схеме Item_l — указатель элемента, предшествующего элементу с указателем Item (семантика обозначения — на 1 шаг назад от Item), в скобках указан порядок переключений связей.

Item:= Head;

ltem_1:= nil;

while (ltem^A.Next<>nil) and (ltem^A.Key<>x) do

begin

ltem_1 := Item;

ltem:= ltem^A.Next;

end;

if ltem^A.Key=x

then begin

if ltem_1<>nil

then begin //найденный элемент не первый

ltem_1^A.Next:= ltem^A.Next; ltem^A.Next:= Head;

Head:= Item; //перемещение

end;

Search:= Item;

end

else Search:= nil;

Г^- Item 1 Item П

Рис. 6.1. Перемещение элемента в начало списка

Метод транспозиции заключается в том, что извлеченная запись меняется местами с записью, которая ей предшествует, и может ис-

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

• для массива вводится переменная Temp типа элемента массива, через которую выполняется обмен элементами:

i:=1; while (ix) do lnc(i); if a[i].Key=x

then begin //элемент найден

if i>1

then begin //элемент не в первой позиции - обмен

Temp:= a[i]; a[i]:=a[i-1];a[i-1]:=Temp;

Dec(i);

end;

Search:=i;

end

else Search:=0;

• для списка (см. рис. 6.2) необходимо ввести указатель Item_2 элемента, предшествующего элементу с указателем Item_l (семантика обозначения Item_2 — на 2 шага назад от Item).

Item:= Head; ltem_2:= nil; ltem_1:= nil; while (ltem^A.Next<>nil) and (ltem^A.Key<>x) do begin ltem_2:= ltem_1; ltem_1 := Item; ltem:= ltem^A.Next; end;

if ltem^A.Key=x

then begin //перемещение найденного элемента

if ltem_1<>nil

then begin //найденный элемент не первый

ltem_1^A.Next:= ltem^A.Next; ltem^A.Next:= ltem_1; if ltem_2<>nil then ltem_2^A.Next:= Item

else Head:= Item; //элемент второй в списке

end;

Search:= Item;

end

else Search:= nil;

Item 2 pifFnrl---item^-)

----ХГ-Г-Г-Ж___J

Рис. 6.2. Транспозиция найденной и предшествующей

записей в списке

Такой способ перемещения элементов списка используется, если объем данных, помещенных в каждую запись, такой, что перемещение записей связано с большими затратами. Если содержательная часть элемента списка имеет несложную структуру, то вместо изменения взаимного расположения найденного и предшествующего ему элементов списка можно выполнить обмен их содержательных частей, как это показано на рис. 6.3. Для реализации такого обмена вводится переменная Temp типа содержательной части элемента списка. Во фрагменте программы, реализующей этот алгоритм, содержательная часть элемента списка идентифицируется полем Value, которое в свою очередь является записью с одним из полей — ключом Key.

Item:= Head; ltem_1:= nil;

while (ltem^A.Next<>nil) and (ltem^A.Value.Key<>x) do begin ltem_1 := Item; ltem:= ltem^A.Next;

end;

if ltem^A.Value.Key=x //элемент найден - перемещение

then begin if Itemjonil

then begin //найденный элемент не первый

Temp:= ltem^A.Value; ltem^A.Value:=ltem_1 ^A.Value; ltem_1 ^A.Value:=Temp;

end;

Search:= Item;

end

else Search:= nil;

Iteml Item Head *-f“*

Рис. 6.3. Обмен значениями найденной и предшествующей

записей в списке

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

Однако метод транспозиции требует большего времени для достижения максимальной эффективности. Кроме того, метод транспозиции одинаково эффективен и для массивов, и для списков.

ПОИСК В УПОРЯДОЧЕННОЙ ТАБЛИЦЕ

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

В приведенном ниже участке программы Left, Right — левая и правая границы поиска; Middle — середина области поиска.

Left:=1; Right:=n; while Left

if a[Right].Key=x then Search:=Right else Search:=0;

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

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

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

Индексно-последовательный поиск. В дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексом (см. рис. 6.4).

Каждый элемент индекса состоит из ключа Key и указателя Addr на запись в исходной таблице, соответствующую этому ключу. Индекс можно описать как массив Ind_v Ind₂, ..., Ind_m из т элементов. Элементы в индексе также отсортированы по ключу Key. Если индекс имеет размер, составляющий одну пятую, например, от размера таблицы, то каждая пятая запись представлена в индексе.

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

Индекс применяется для отсортированной таблицы, реализованной и в виде списка, и в виде массива. Использование списка приводит к накладным расходам по пространству для указателей, хотя вставки и удаления могут быть выполнены проще.

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

Индекс

Ключ

Таблица Другие данные

2

п

Ключ Указам ел ь (Key) (Addr)

2

т

54 961

Рис. 6.4. Индексно-последовательный поиск

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

Рассмотрим пример с таблицей в виде массива, где Ind, т — имя и размер индекса, а, п — имя и размер таблицы, Low и High — нижняя и верхняя границы поиска в таблице, Key — имя ключевого поля индекса и таблицы, Addr — имя поля-указателя в индексе.

i:=1;

while (i//поиск в индексе

// определение нижней границы поиска в таблице:

if i=1

then Low:=1

else Low:=lnd[i-1].Addr;

// определение верхней границы поиска в таблице:

if (i=m) and (lnd[i].Key<=x)

then begin //пространство поиска - конец таблицы

High:=n; Low:=lnd[i].Addr;

end

else High:=lnd[i].Addr-1;

i:=Low; // поиск в таблице от Low до High:

while (ix) do lnc(i);

if a[i].Key=x

then Search:=i

else Search:=0;

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

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

РАССТАНОВКА

В предыдущих методах организация таблицы была такой, что для поиска нужного ключа нужно было проверить некоторое количество ключей (от ^п/₂ в линейном поиске до log₂ п в бинарном поиске и поиске по дереву). Желательно иметь такую организацию таблицы, при которой положение записи внутри таблицы зависит только от данного ключа и не зависит от расположения других ключей. При этом исключаются ненужные сравнения.

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

Например, для применения прямой индексации с использованием пятизначного ключа потребовался бы массив из 100 тысяч элементов, причем большая часть записей вероятно была бы пустой.

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

Расстановка — процесс преобразования ключа в целое число внутри некоторого диапазона. Функция И, трансформирующая ключ в некоторый индекс в таблице, называется функцией расстановки. Если Key — некоторый ключ, то И(Кеу) — значение функции расстановки от ключа Key — индекс, по которому должна быть помещена в таблицу запись с ключом Key. Значения функции h должны покрывать все множество индексов таблицы.

Пусть существуют ключи Key 1 и Кеу2 такие, что И(Кеу ) = И(Кеу2). Запись с ключом Кеу помещается в позицию И(Кеу) таблицы. Ключ Кеу2 должен быть помещен на ту же позицию И(Кеу2). Такая ситуация называется конфликтом или столкновением.

Хорошая функция расстановки минимизирует конфликты и распределяет записи равномерно по всей таблице. Желательно иметь таблицу с размером большим, чем число реальных записей. Чем больше диапазон значений функции расстановки, тем меньше вероятность конфликтов. При этом возникает компромисс между временем и пространством.

Мерой использования памяти в таблицах с прямым доступом служит коэффициент заполнения: а = п/т (п — число записей; т — размер таблицы).

ФУНКЦИИ РАССТАНОВКИ

Метод деления — наиболее известная функция. Некоторый целый ключ делится на размер таблицы и остаток от деления берется в качестве значения функции: И(Кеу) = той(Кеу, т) +1 , диапазон индексов: ..т.

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

Метод середины квадрата. Ключ умножается сам на себя, и в качестве индекса используется несколько средних цифр результата, причем во всех ключах берутся одни и те же разряды. Если данный квадрат рассматривается как десятичное число, то размер таблицы должен быть степенью 10, если как двоичное — степенью 2.

Пример. Ключ 1 13586 дает в квадрате число 12901779396. В качестве четырехзначного индекса можно выбрать значение 1779. Причиной возведения в квадрат до извлечения средних цифр ключа является то, что все цифры первоначального числа дают свой вклад в значение средних цифр квадрата.

Метод свертки. Ключ разбивается на части, каждая из которых имеет длину, равную длине требуемого адреса (кроме, возможно, последней части). Части складываются без переноса в старшем разряде.

Если ключи представлены в двоичном виде, то может быть использовано сложение по модулю 2 (операция «исключающее ИЛИ»: 0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 0).

Примеры:

а) преобразование двоичного ключа 010111001010110₂ в пятиразрядный двоичный индекс приведено на рис. 6.5.

разбиение сложение 01011 11001

• 010111001010110 + юою + юно
• 11001 01111 — индекс

Рис. 6.5. Пример свертки двоичного ключа

б) преобразование десятичного ключа 187249653₁₀ в трехразрядный десятичный индекс приведено на рис. 6.6.

разбиение сложение 187 436

• 187249653 + 249 + 653
• 436 089 — индекс

Рис. 6.6. Пример свертки десятичного ключа

в) разновидность свертки — граничное свертывание (перед сло

жением инвертируются цифры в крайних частях ключа) для десятичного ключа 187249653₁₀ приведено на рис. 6.7.

781 030

+ 249 + 356

030 386 — индекс

Рис. 6.7. Граничное свертывание десятичного ключа

Свертывание удобно для сжатия многословных ключей и последующего перехода к другим функциям расстановки.

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

Ключ, представленный в системе счисления q (обычно q = 2 или 4 = 10), рассматривается как число в системе счисленияр, где p>q, причем р и q взаимно простые. Это число из системы счисления с основанием р переводится в систему счисления с основанием q, и адрес формируется путем выбора правых цифр или битов нового числа или методом деления.

Например, ключ 530476₁₀ , рассматриваемый как 530476,₁, переводится в десятичную систему счисления следующим образом:

530476,, = 5-11⁵ + 3-11⁴ +4 11² +7-11 + 6 = 849745,₀ .

В качестве трехзначного индекса (диапазон 0..999) выбирается значение 745, четырехзначного (диапазон 0.. 9999 ) — значение 9745.

Алгебраическое кодирование разделяет скопления ключей. Состоящий из г битов ключ (/:, к₂ ...к_г), где к₁ — цифры ключа, рассматривается как многочлен

К(х) = ^к₁х'~^х.

/=1

Если требуется сформировать адрес в интервале от 0 до т = 2' -1 (/‘-разрядный адрес), то многочлен К(х) делится на другой многочлен _/

Р(х) = х‘ + ^р₁х'~¹,

1=1

коэффициенты /?, которого выбираются произвольно. Получающийся при делении по модулю 2 остаток

тос^/Дх), /^>(х)) = ^/?_/х^;_|

/=1

дает адрес (/г, к₂... к,), где /г, — цифры адреса.

Пример. Преобразовать двоичный ключ 1010011₂ (г = 7 ) в четырехразрядный (ї = 4) двоичный адрес в диапазоне от 0 до 2⁴ -1 (или от 0 до 1111₂). Многочлен К(х) имеет вид:

К(х) = 1 • х° + 0 • х¹ +1 • х² + 0 • х³ + 0 • х⁴ +1 • х⁵ +1 • х⁶ = х⁶ + х⁵ + х² +1

Многочлен Р(х) = х⁴ + х² +1 выбирается произвольно (кроме одночлена х' =х⁴ ).

Деление многочленов по модулю 2 и вычисление адреса приведено на рис. 6.8.

X⁶ + Х⁵ + X² +

X⁶ + X⁴ + X²

х⁵+х⁴+ +

1

X⁴ + X² + 1 X² +Х+ 1

X⁵ + Х³+ X

X⁴ + X³ + X + 1 X⁴ + X² + 1

X³ +х² +х —?> Я(х) = 0 • х° + 1 -X^і + 1 -х²+ 1 -х³^

—> адрес = 0111₂.

Рис. 6.8. Вычисление адреса алгебраическим кодированием

Замечание. При делении по модулю 2 вычитание выполняется по правилам: 0-0 = 0; 1-0 = 1; 1 — 1 = 0; 0-1 = 1.

Мультипликативная функция. Для неотрицательного целого ключа Key и константы с такой, что 0<с< 1, функция определяется в виде h{Key) = m mod(c- Key, 1)] + 1, где mod(c- Key, 1) — дробная часть величины с Key, [х] — наибольшее целое, не превышающее х. Функция дает хорошие результаты при правильном выборе с, что можно сделать только исследованием различных вариантов.

МЕТОДЫ РАЗРЕШЕНИЯ КОНФЛИКТОВ ПРИ РАССТАНОВКЕ

Функция расстановки часто отображает разные ключи в один и тот же адрес. При этом записи переполнения должны запоминаться в других адресах таблицы, которые определяются с помощью методов устранения конфликтов. Существуют две группы таких методов: открытая адресация или повторная расстановка (линейное и случайное опробование, двойная расстановка) и метод цепочек (раздельное и внутреннее сцепление).

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

Пример. Ключи 3953, 4148, 52, 549, 748, 2350 преобразуются с помощью функции И(Кеу) = шос1(А^у, 100) +1 для получения индекса в диапазоне 1.. 100 .

Распределение ключей в таблице приведено на рис. 6.9.

Адрес

Ключ

• 748
• 2350

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

Пунктирная линия указывает на позицию, в которую должен помещаться ключ в соответствии со значением функции расстановки, сплошная линия — на позицию, в которую реально помещается ключ в случае конфликта.

Функция повторной расстановки rh воспринимает один индекс в массиве и выдает другой индекс. Если И(Кеу) занята, то определяется новое значение адреса ключа Key как / = rh(h(Key)). Если ячейка i опять занята, то преобразование выполняется еще раз, и проверяется ячейка с адресом rh(rh(h(Key))). Этот процесс повторяется, пока не будет найдена ячейка, содержащая заранее определенное значение «пусто». Для линейного опробования rh(i) = mod(/',/w) +1, т.е. повторное преобразование индекса дает следующую позицию в массиве, замкнутом в кольцо.

В приведенной ниже программе поиска и вставки: х — ключ; И(х) функция расстановки ключа х; rh(i) — функция повторной расстановки адреса /; а, т — имя и размер таблицы; i,j — позиции (адреса) записей в таблице. Отрицательное значение ключа является признаком «пусто».

j:=/7(x); i:=j;

// Повторная расстановка:

while (a[i].Key>=0) and (a[i].Key<>x) and (i<>j-1) do i:=r/7(i); if a[i].Key<0

then begin //позиция свободна - вставка

a[i].Key:=x; // запись в a[i] ключа

// запись в a[i] других полей

Searc/?:=i;

end

else begin //позиция занята

if a[i].Кеу=х

then Search:=i // ключ в таблице есть

else begin

//генерация исключительной ситуации “Переполнение таблицы”

end;

end;

Для оценки эффективности методов устранения конфликтов используется средняя длина поиска ALOS (Average Length Of Search). Предполагается, что каждый ключ отображается в каждый из m адресов таблицы с вероятностью /т , т.е. существует т^п вариантов отображения ключей в адреса. ALOS зависит от коэффициента заполнения таблицы ос = л/m (т — число адресов, л — число ключей) и представляет собой число попыток для размещения ключа. Для метода линейного опробования ALOS резко возрастает с ростом а:

ALOS -

• 2
• 1 +
• 1 +
• 1 ^
• 1-а,

при успешном поиске;

(1-а)²/

при неуспешном поиске.

Характеристики поиска с устранением конфликтов методом линейного опробования приведены в табл. 6.1.

Таблица 6.1

Средняя длина поиска для метода линейного опробования

Недостатки метода линейного опробования:

• 1) трудно выполнять удаление записей, необходимо вводить новый признак — «удаленная запись»; удаление большого числа записей приведет к неэффективному использованию таблицы;
• 2) возникновение эффекта «окучивания» — с возрастанием заполненности таблицы имеет место тенденция возникновения все более длинных последовательностей занятых подряд позиций (первичное окучивание).

Случайное опробование позволяет частично решить проблему первичных скучиваний. В этом методе при повторной расстановке функция г/?(/) генерирует не линейную последовательность позиций, а случайную, например, г/?(/) = тоб(/ + с,т) +1, где сит — взаимно простые числа (если т простое число, то с может быть любым). Диапазон адресов — ..т.

Рассмотрим предыдущий пример: ключи 3953, 4148, 52, 549, 748, 2350 преобразуются с помощью функции И(Кеу) = тос!(АГсу, 100) +1 для получения индекса в диапазоне 1..100. При занятом адресе / = 95 функция /*/?(/) = тос1(/, 100) +1 (линейное опробование) выдает последовательность 96, 97, 98, 99, 100, 1, 2,.., а функция, например, /*/?(/) = тос1(/ + 41,т) + 1 выдает последовательность 37, 79, 21, 63, 5, 47, ...

Недостаток случайного опробования — вторичное окучивание (возникновение одинаковых последовательностей адресов при преобразовании двух ключей в один и тот же адрес). Возможность устранения этого недостатка — использование еще одной функции расстановки для выбора с.

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

Двойная расстановка. Пусть первая функция дает одинаковые адреса для различных ключей: {Кеу) = И_{(Кеу2). Тогда, если есть вторая функция И₂ такая, что и И₂ являются независимыми и И₂(Кеу) Ф И₂(Кеу2), то любое из этих значений можно выбрать в качестве смещения с.

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

ЛЬ08 «

—1п(1-а) а при успешном поиске;

Л-а

при неуспешном поиске.

Значения средней длины поиска с устранением конфликтов методом двойной расстановки приведены в табл. 6.2.

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

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

Раздельное сцепление. Метод заключается в организации связанного списка из всех записей, чьи ключи преобразуются в один и тот же адрес. Пусть функция расстановки выдает значения в диапазоне от 1 до т. В этом случае говорят, что ключи распределяются по т классам эквивалентности. Каждый класс хранится в виде связанного списка. Указатели на списки содержатся в массиве длиной т. Запись, попавшая в один из классов эквивалентности, вставляется в начало (или конец) списка.

Пример. Обрабатываются ключи 75, 17, 12, 40, 35, 95, 87. Функция расстановки h(Key) = под(Кеу, 10). Таблица приведена на рис. 6.10.

Рис. 6.10. Распределение ключей в таблице методом

раздельного сцепления

Характеристики метода раздельного сцепления:

. ^а

ALOS

1 + — при успешном поиске; а + е^-апри неуспешном поиске.

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

Таблица 6.3

Средняя длина поиска для метода раздельного сцепления

Формулы АЮЗ справедливы и при а > 1, однако коэффициент заполнения желательно иметь небольшим. Метод эффективен, хорошо работает с меняющимися таблицами, но требует дополнительной памяти для т + п указателей.

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

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

Пример. Обрабатываются ключи 75, 17, 12, 40, 35, 95, 87. Функция расстановки И(Кеу) = то6(Кеу, 10). Таблица приведена на рис. 6.11.

Начало цепочки с индексом 5

Рис. 6.11. Распределение ключей в таблице методом

внутреннего сцепления

В конфликтной ситуации (если ячейка с нужным индексом занята) для поиска свободного места в таблице необходимо сначала дойти до конца цепочки с этим индексом (указатель равен nil), а затем с помощью любого алгоритма найти первую свободную ячейку. В нашем примере использован линейный поиск с конца таблицы.

Коэффициент заполнения а должен быть меньше 1. Средняя длина поиска несколько выше, чем при раздельном сцеплении, однако экономия памяти делает метод привлекательным.

К недостаткам метода относится возможное смешивание цепочек. Например, для поиска пришел ключ 29 (см. рис. 6.11). Его надо поместить в цепочку с индексом 9, а он будет помещен в конец цепочки с индексом 5 (75, 35, 95) — в ячейку с индексом 4 (первая свободная при поиске от ячейки 9 к ее началу).

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

• 1. Оцените минимальное и максимальное количество сравнений в алгоритме поиска с барьером. За счет чего достигается уменьшение числа операций по сравнению с линейным поиском?
• 2. В каких случаях целесообразно использовать для поиска методы с переупорядочиванием таблицы? Сравните по эффективности методы перемещения в начало и транспозиции.
• 3. Оцените минимальное и максимальное количество сравнений в алгоритме бинарного поиска.
• 4. Каково оптимальное соотношение между размерами таблицы и индекса в индексно-последовательном поиске.
• 5. Дана таблица расстановки !Г[0..12] (рис. 6.12) с функциями первичной расстановки i-k mod 13 и повторной расстановки / = (/ + 4)mod 13 , где / — адрес, к — ключ. Указать последовательность поступления ключей в таблицу. Построить дерево поиска из этих же ключей, поступающих в том же порядке?

Рис. 6.12. Таблица расстановки для задания 5

6. Даны две таблицы расстановки 74[0..12] и 7"2[0..12] (рис. 6.13) с функциями первичной расстановки / = к mod 13 и повторной расстановки / = (/ + 4) mod 13, где / — адрес, к — ключ. Дополнить таб-

лицу ключами из Т1, чтобы порядок записи ключей был таким

же, как и при заполнении Т1.

Рис. 6.13. Таблицы расстановки для задания 6

7. Даны две таблицы расстановки 7Т[0..10] и 7"2[0..10] (рис. 6.14) с функциями первичной расстановки i = к mod 11 и повторной расстановки / = (/ + 3) mod 11, где / — адрес, к — ключ. Дополнить таблицу Т2 ключами из Т1, чтобы порядок записи ключей был таким же, как и при заполнении Т1.

Рис. 6.14. Таблицы расстановки для задания 7

8. Дана таблица расстановки 7"[0..16] (рис. 6.15) с функциями первичной расстановки / = ?тоб17 и повторной расстановки / = (/ + 5) той 17 , где / — адрес, к — ключ. Как выглядела бы таблица, если бы эти же ключи заносились в нее в обратном порядке?

Рис. 6.15. Таблица расстановки для задания 8

9. Дана таблица расстановки 7"[0..12] (рис. 6.16) с функциями первичной расстановки / = /:modl3 и повторной расстановки / = (/ + 5)mod 13 , где / — адрес, к — ключ. Указать последовательность поступления ключей в таблицу. Построить дерево поиска из этих же ключей, поступающих в том же порядке?

Рис. 6.16. Таблица расстановки для задания 9

10. Определить, может ли таблица 7"[0..10] (рис. 6.17) быть таблицей расстановки при функциях первичной расстановки / = к mod 11 и повторной расстановки / = (/ + 2) mod 11 , где / — адрес, к — ключ. Если «да», то указать последовательность поступления ключей в таблицу. Если «нет», то доказать это.

Рис. 6.17. Таблица расстановки для задания 10

Лабораторная работа 6. ПОИСК И РАССТАНОВКА

Задание

Составить программу формирования заданным методом таблицы поиска и последующего поиска в этой таблице элементов из входной последовательности.

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

• • отладочный (10 элементов), демонстрирующий работу алгоритма поиска;
• • рабочий (50 элементов), в результате обработки которого выводятся значения параметров эффективности, определенных для заданного метода поиска.

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

В вариантах с нечетными номерами каждый элемент — строковая переменная.

В вариантах с четными номерами элемент состоит из двух полей: строковой переменной и числового ключа.

При расстановке строковые ключи необходимо предварительно свернуть каким-либо методом.

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

Варианты заданий приведены в табл. 6.4.

Варианты заданий к лабораторной работе 6

Рекомендации по выполнению работы

Для создания таблицы и последующего поиска в ней рекомендуется создать текстовый файл, содержащий порядка 100 элементов.

Сначала выполнить работу в отладочном (демонстрационном) режиме, для чего прочитать из этого файла первые 10 элементов и создать таблицу. Ввести в диалоговом режиме значение элемента, присутствующего в таблице, и выполнить его поиск, демонстрируя все шаги алгоритма (индексы и результаты сравнений). Затем ввести значение элемента, которого нет в таблице, и выполнить поиск с демонстрацией шагов алгоритма. Результаты поиска вывести в текстовый файл.

Затем выполнить работу в рабочем режиме. Для этого открыть тот же файл с исходными данными для чтения, прочитать из него первые 50 элементов и создать таблицу. Затем вновь открыть этот файл для чтения, последовательно прочитать из него и выполнить поиск всех 100 элементов, подсчитывая количество операций сравнения ключей

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

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

Чтобы правильно оценить эффективность поиска, необходимо, чтобы во второй половине текстового файла содержались элементы, отсутствующие в таблице.

Для методов разрешения конфликтов при расстановке необходимо отдельно оценивать эффективность успешного и неуспешного поиска.