В адресной части записываются отсылаемые адреса к элементам информации и  коды (или адреса) связи, объединяющие элементы в ассоциативные группы. В каждой ячейке памяти размещаются адрес отсылки А₀ и код связи К_св (рис.4). Адресная часть делится на участки А и Б, к которым обращаются соответственно с помощью кодов свертки и кодов связи. По кодам свертки выбираются отсылочные адреса начальных элементов ассоциативных групп, а по кодам связи - место записи адресов остальных элементов.

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

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

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

   2.1.3. Узловой способ организации массивов 

   Применяется для записи в память ЭВМ информационных сведений сложной структуры. Связи между элементами одного информационного массива фиксируются позиционно, т.е. путем совместного расположения кодов этих элементов или их адресов в одном узле. В узловом способе сочетаются свойства гнездового и цепного способов. На рис.5 приведен пример использования узлового способа массива сообщений, каждое из которых состоит из трех элементов: А - адресная часть, Б - массив сообщений. Для записи одного сообщения отводится 1 ячейка памяти. Ячейка делится на три участка. Каждый участок представляет один элемент сообщения, участки ячеек, обозначающие одинаковые элементы сообщения, соединяются между собой цепочками адресных отсылок - эти цепочки условно изображены линиями со стрелками. Адресные отсылки к участкам, являющиеся первыми элементами цепочек, указываются в части А, а отсылки к остальным элементам цепочек - в части Б.

   При этом отсылки элементов к элементам  ассоциативных цепочек с порядковым номером i записываются на участках, являющихся элементами этих цепочек с порядковым номером (i-1). Заштрихованные участки на рис.5 обозначают признак конца. В данном примере предполагается, что поиск в адресной части будет вестись цепным способом, а в качестве признаков для формирования ассоциативных цепочек будут служить свертки кодов элементов. К первым элементам ассоциативных цепочек будут обращаться по сверткам, а к остальным элементам - по кодам связи. Соответственно в ячейках адресной связи будут храниться тройки кодов К_эА₀<К_св. Поиск в адресной части считается законченным, если заданный код элемента совпадает с одним из кодов К_э и для чего выбирается соответствующий адрес А₀.

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

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

 

Рисунок 4- Цепной способ поиска

 

Рисунок 5 -Узловой способ поиска 

       2.2. Способ последовательного просмотра или способ перебора 

   Для заданного числа Х последовательно  проверяется выполнение неравенства:

   X>X₁, Х>Х₂,..., x>x_l   (1).

   Одновременно  ведется подсчет числа проверок. Этот процесс продолжается до тех  пор, пока одно из условий (1) окажется невыполнимым. Тогда проверяется равенство:

   Х=Х_K    (2),

К - порядковый номер сравниваемого числа списка.

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

   k=k₁+k-1 ,

K₁ - адрес первого числа.

   При выполнении (2) поиск прекращается. Способ последовательного просмотра самый  невыгодный в смысле затрат машинного времени. Если вероятность обращения к любому из L чисел списка одинакова и равна 1/L, то в среднем требуется просмотреть (L+1)/2 чисел, чтобы найти нужный адрес. 

         2.3. Способ последовательного деления на части. 

    Метод аналогичен предыдущему, но элементы множества  просматриваются не последовательно, а с заданным шагом L. В данном случае массив делится на К отдельных  частей.

    

К - целая  часть от деления количества элементов  в массиве на шаг l.

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

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

   

n - количество элементов в массиве X.

   Метод деления массива на части при  К=2 называют дихотомическим или двоичным поиском. Он является более эффективным  по сравнению с методом деления на части при K 2.

        2.4. Способ разделителей. 

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

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

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

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

   Правила образования кодов рассмотрим на примерах (таблица 1).

Таблица 1-Правила образования кодов

 
 

   Приближенно длина свертки может быть определена по формуле:

   

где  l - объем массива кодов, в котором производится поиск;

   n - среднее количество кодов в участке.

       2.5. Способ линейной интерполяции. 

   Дана  монотонно возрастающая функция

   k=f(x)     (4)

   Заменим ее линейной функцией

   k=Ax+B     (5)

с коэффициентами:

   

   Подставляя  в формулу (5) В и учитывая, что адрес k должен быть целым числом, получим для него следующее выражение:

      (6)

   Действительный  адрес числа х при х₁ х x_L заключен либо в интервале (k₁, k), либо в интервале (k, k_L.) в зависимости от того, выполняется или не выполняется условие х х_S, в котором х_S означает число X₁, имеющее адрес k.

   Поиск способом линейной интерполяции: сначала  по формуле (6) вычисляется адрес k. Затем  определяется величина и знак разности x-x_S. Если x-x_S=0, то поиск окончен. Если x-x_S>0, то дальнейший поиск ведется способом последовательного просмотра от меньших значений х к большим/ Если х-х_S<0, то последовательный просмотр ведется в обратном направлении.

 

        2.6. Серийный упорядоченный поиск (способ скользящего канала) 

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

   Среднее количество циклов поиска одного числа  определяется величиной:

   

l - объем списка чисел, находящихся в ОЗУ;

n - количество искомых чисел. 

       2.7 Прохождение бинарных деревьев 

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

   В результате обхода дерева получаем линейную расстановку всех вершин, т.е. фактически вводим отношение предшествования на множестве вершин дерева. На рис.6 изображен обход дерева. Мы обходим дерево вдоль пунктирной линии в направлении стрелок, начиная и заканчивая обход в корне. На каждое прохождение мы попадаем в вершину по меньшей мере один раз, а вообще говоря, три раза. Обходя дерево, мы можем систематически делать что-то с каждой вершиной, например, печатать номер вершины. Если мы будем печатать номер вершины только при первой встрече с ней, то получим последовательность 6, 4, 3, 5, 7. Если печатать номер при второй встрече, то получим 3, 4, 5, 6,7, а если при третьей - 3, 5, 4, 7, 6. Эти три способа обхода вершин называются соответственно обходом: сверху, слева направо, снизу.