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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

511 4 06 F 15/38

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЬТИЙ (21) 3792361/24-24 (22) 13,08.84 (46) 23.01.86. Бюл. Ф 3 (72) Б.С.Богумирский (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

М 666545, кл. G 06 F 15/38, 1977.

Авторское свидетельство СССР

У 780011, кл. G 06 F 15/38, 1978. па 1 1ао 1 2О (54) УСТРОЙСТВО ДЛЯ ПОСТРОЕНИЯ СПИСКА (57) Изобретение относится к вычислительной технике. Целью изобретения является расширение функциональных возможностей устройства путем введения новых элементов в начало списка. Устройство содержит счетчик, блок памяти, регистры, группу элементов И, элемент задержки, узел сравнения. 1 ил.

1206807 2

1О

:1.3

pl i l

"-.)I h

4, 1 ению списков.

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

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

На чертеже приведена схема усгройства.

Устройство содержит счетчик 1, блок 2 памяти, регистр 3, группу ч элементов И, элемент 5 задержки, узел 6 сравнения, регистр 7, регистр 8, разрешающий вход 9, установочный вход 10, вход ll адреса объекта, вход 12 адреса списка, вход

13 начального адреса, вход 14 конечного адреса, выход 15 признака, информационный выход 16 устройства.

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

Левый указатель определяет адрес

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

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

При включении питания в счетчик

1 с входа 13 по импульсу на входе

10 записывается адрес начала свободной области памяти, которая »о— жет использоваться для размещения элементов списков. Е регистр 3 заносится код, IIa единицу больший адреса последней ячейки свободной области. УстройстВо гОтово к построПри необходимости добавить новый элемент в начало списка в регистр

7 записывается адрес информационной области объекта, который должен быть представлен в списке, а в регистр 8 заносится адрес первого элемента модифицируемого списка, После этого подается импульс на вход 9, в результате чего новый, только что сформированный элемент списка записывается в блок 2 памяти но адресу, заданному на счетчике 1,. Кроме того, открывается группа 4 элементов

И и адрес первого элемента »одифициров анного спНсКВ из счетчика поступает на выход 16 устройства. 3ате» появляется импульс на выходс элемента 5 задержки вследствие чего содержимое счетчика 1 увеличивается на единицу. После этого аналогична »огут строиться цругие списки.

Если необходимо создать список из одного элемента, то в регистр 7 запись|в ется адрес информационной

Области соответствующего Объекта, а в регистр 8 — пустой указатель.

Содержимое счетчика 1 всегда определяет адрес начала свободной области. Гсли оно выйдет за ее верхнюк границу, то узел 6 сравнения выдает сигнал, который проходит на выход 15, .свидетельствуя об отсутствии свободной памяти в блоке 2, По этому сигналу должны включаться процедуры сборки кусков свободной памяти, после выполнения которых содержи»ое счетчика 1 и регистра 3 Обновляется и устройство сможет продолжить работу.

Фop:..óëàизобретения

Устройство для построения списка, содержащее два регистра, блок памяти,.; руппу элементов И, выходы которьгх являются информационны» выходом усгройства„ О . л и ч à Ip щ е

L. o,I Yà»,, что, с целью расширения ф--нкциональных возможностей путем введения новых эле»ентов в начало списка, в него введены третий регистр, элемент задержки, узел сравнения и с" ;;етчик вь1ходы разрядов IcoTopoi o iopicIIIp÷åíû к первы» входам элементов

И группы, к адресному входу блока

-nà Iÿ.-:.-: и к первому вхоцу узла сравнения, входы первого и второго регистров являются соответственно входом адреса объекта и входом адреса сг;иска устройства, выходы первого: и второго регистров подключены к первой и второй группам информационньгх входов блока памяти соответственно, вход разрешения заI писи которого, вторые входы элементов И группы и:;:õoä элемента =;ацержки сОецинены с разрешающим входом устройства, выход эл мента

Составитель А,Жеренов

Редактор П.Коссей Техред Т.Дубинчак Корректор А.Зимокосов

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

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 8715/51

Филиал ППП "Патент", r..Óæãîðoä, ул. Проектная, 4 задержки соединен со счетным входом счетчика, разрешающий вход которого соединен с установочным входом устройства, вход начального адреса которого соединен с информационным входом счетчика, вход конечного ад1206807 4 реса устройства соединен с входом третьего регистра, выход которого подключен к второму входу узла сравнения, выход которого соединен с

5 выходом признака отсутствия свободной памяти устройства.