Устройство для поиска информации Советский патент 1987 года по МПК G06F17/30 

11

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

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

На чертеже приведена функциональная схема устройства.

Устройство содержит группу 1 элементов ИЛИ, группы 2-5 элементов И, элементы И 6-11, элементы ИЛИ 12-15, дешифраторы 16-19, элемент 20 сравнения, элемент 21 задержки, стековую память (стек) 22, содержащую первьй 23 и второй 24 разряды, регистры 25- 27, разряды 28 данных и 29 признака левого 30, правого 31 и обратного 32 указателей регистра 27, блок 33 памяти, распределитель 34 импульсов, содержащий с первого по шестой выходы 35-40, генератор 41 импульсов, группу 42 адресных входов устройства входы признака 43 и запуска 44 устройства, вход 45 признака конца работы устройства и информационные 46 выхо- ды устройства.Бинарное дерево представляет со- .бой связный неориентированный граф, в котором из каждого узла выходит

не более двух ребер.

Каждый узел дерева занимает одну ячейку блока 33 памяти и состоит из полей данных (либо указателя на данные), признака левого, правого и об- ратного указателей. Признак предназначен для идентификации данных, хранящихся в узле. Левый и правый указатели задают адреса узлов, следующих непосредственно за данным, а обратный указатель - адрес предшествующего данному узлу. Произвольный узел может иметь пустой либо левый, либо правый указателей. Пустой указатель задается кодом, расшифровывает- ся дешифраторами 16, 18 и 19 и обозначается 0. Узел, в который не входит ни одно ребро, имеет пустой обратный указатель, а узлы, из которых не выходит ни одного ребра, содержат пустые левые и правые указатели. Устройство реализует поиск требуемого узла методом полного перебора в глубину.

142

Устройство работает следующим образом,

В исходном состоянии генератор 41 остановлен, выходы распределителя 34 и стека 22 - нулевые. По группе 42 входов в регистр 26 записывается адрес узла, и который не входит ни одно ребро, а по входу 43 в регистр 25 - признак искомого узла. Устройство готово к работе.

Цикл работы устройства состоит из шести тактов.

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

По импульсу 35 код узла дерева, адрес которого находится в регистре 26, принимается в регистр 27. Признак этого узла сравнивается с признаком искомого узла, и в случае сравнения элемент 20 сравнения вьщает сигнал. Поля левого 30 и правого 31 указателей анализируются дешифраторами 18 и 19 «а 0, при обнаружении которого эти. дешифраторы выдают сигналы.

При появлении импульса 36, когда найден искомый узел, срабатывает элемент И 7, открьшается группа 2 элементов И и искомые данные проходят на выход 46 у генератор 41 останавливается, распределитель 34 и стек 22 обнуляются. После обновления содержимого регистров 25 и 26 устройство может быть использовано повторно. В случае несравнения признаков на этом такте никаких операций не вьшол- няется.

По импульсу 37, если на выходе дешифратора 1В логическая единица (ле- вьй указатель 0), разряд 23 стека

22устанавливается в единичное состояние. По импульсу 38, если на выходе дешифратора 19 логическая е,цинй- ца (правый указатель 0), разряд 24 стека 22 устанавливается в единичное состояние. Единицы в разрядах 23 и

24 запрещают выбор следующих за очередным узлов, если соответствующие указатели пустые.

Если разряды 23 и 24 или разряд

23находятся в нулевом состоянии, то появляется сигнал на первом выходе

313

дешифратора 17, подготавливая к открытию группу 3 элементов И. Если разряд 23 в нулевом состоянии, то сигналом с второго выхода дешифратора 17 -подготавливается к открытию группа 4 элементов И. Если разряды 23 и 24 в единичном состоянии, то сигналом с третьего выхода дешифратора 17 подготавливается к откры- тию группа 5 элементов И.

Импульсом 39 открывается одна из групп 3-5 элементов И, и код левого, правого или обратного указателей из регистра 25 записывается в регистр 26 и является адресом очередного узла в следующем цикле работы устройства. Если все указатели равны 0 (все дерево просмотрено), то на выходе дешифратора 16 появляется сигнал, устанавливающий на входе 45 признак конца работы устройства, свидетельствуя об отсутствии в дереве узла с заданным признаком.

По импульсу 40 срабатывает один из элементов И 6,8,9. На этом такте модифицируется вершина стека в соответствии с принятым решением по дальнейшему просмотру дерева. Если срабатывает элемент И 8 (на предыщуш,ем такте выбран левый указатель), то через элемент ИЛИ 14 разряд 23 устанавливается в единичное состояние, а содержимое стека 22 погружается на одну ячейку. При этом в вершине стека появляется свободная обнуленная ячейка. В ней отражаются результаты анализа указателей узла, который прочитывается из блока 33 памяти в следующем цикле. Если срабатывает элемент И 6 5 то происходят аналогичные операции, но в единичное состояние устанавливается разряд 24. Если срабатывает элемент И 9 (на предьщущем такте выбран обратный указатель), то содержимое стека 22 выталкивается на одну ячейку вверх. Вершина стека 22 отражает результаты анализа левого и правого указателей узла, а также результаты просмотра узлов, следующих за ним.

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

5 о Q g

5

5

;4

узел, либо не встретится nycToii левый указатапь.

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

Формула изобретения

Устройство для поиска информации, содержащее группу элементов ИЛИ, три группы элементов И, три регистра, блок памяти, элемент задержки, элемент сравнения, первый элемент И, первый дешифратор, первый элемент ИЛИ и генератор импульсов, вход которого является входом запуска устройства, группа адресных входов которого соединена с пер выми входами , элементов ИЛИ группы, выходы которых соединены с входами первого дешифратора и информационными входами первого регистра, выход которого соединен с адресным входом блока памяти, выход которого соединен с информационным входом второго регистра, выходы разрядов данных которого соединены с первыми входами элементов И первой группы, выходы которых являются информационными выходами устройства, вход признака которого соединен с информационным входом третьего регистра, выход которого соединен с первым входом элемента сравнения, второй вход которого соединен с выходом признака второго регистра, выходы разрядов левого и правого указателей которого соединены с первыми вxoдa ffl элементов И второй и третьей групп соответственно, выходы которых соединены с вторыми и третьими входами элементов ИЛИ группы соответ5 13

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

5 0 0 5

5

146

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

Редактор В.Петраш

Составитель Н.Матвеев Техред И.Попович

Заказ 3112/46

Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Корректор И.Муска

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