Устройство для редактирования списка Советский патент 1986 года по МПК G06F17/24 

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

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

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

Схема содержит регистр 1 адреса следующего элемента, блок 2 памяти, регистр 3 указателя, регистр 4 указателя, дешифратор 5, группа 6 элементов ИЛИ, группы 7-1 элементов И, регистр 12 адреса, регист 13 адреса предыдущего элемента, узел 14 сравнения, вход 15 запуска устройства, элемент ИЛИ 16, триггер 17, распределитель 18 импульсов, генератор 19 тактовых импульсов, адресный вход 20, адресный .вход 21 устройства.

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

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

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

При включении питания регистр 3 и триггер 17 обнуляются,а генератор

19устанавливается в запертое состояние (.не показаноJ. С входа 21 через группу 6 элементов ИЛИ в регистр 1 заносится . первого элемента списка, из которого требуется удалить некоторые элементы. С входа

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

Удаление элементов из списка инициируется импульсом по входу 15,

0

5

0

5

0

5

5

0

5

который запускает генератор 19. Удаление элементов из списка происходит за число циклов работы устройства, равное количеству элементов в списке , Каждый цикл реализуется по одному импульсу с выхода генератора 19 и состоит из ряда тактов, зада- . Баемых импульсами с выходов распределителя 18. Импульсы на его выходах появляются последовательно во времени, начиная с первого выхода. Распределитель 18 должен быть выполнен на элементах задержки.

При несовпадении содержимого регистров 3 и 12 узел 14 выдает сигнал, открывающий группу 9 элементов И.

По импульсу с первого выхода распределителя 18 фиктивный элемент списка из блока 2 памяти считывается на регистррл 3 и 4, причем в регистр 3 помещается левый указатель, а в регистр 4 правый. Сигнал с выхода узла 14 не снимается, поэтому триггер 17 остается в нулевом состоянии, в результате чего группа 10 элементов И закрыта. Вследствие этого импульсы со второго, третьего и четвертого выходов распределителя 18 через группу 10 элементов И не проходят. По импульсу с пятого выхода распределителя 8 содержимое регистра 1 переписывается в регистр 13, а по импульсу на шестом выходе содержимое регистра 4 заносится в регистр 1, т.е. в регистре 1 формируется- адрес следующего элемента списка.

В дальнейшем устройство работает аналогично до тех пор, пока по импульсу с первого выхода распределителя 18 на регистр 3 не будет считан код, совпадающий с coдep) регистра 12. Совпадение означает, что удаляемый элемент найден. При этом сигнал с выхода узла 14 снимается, группа 9 элементов И закрывается, триггер 17 устанавливается в единичное состояние, в результате чего открывается группа 10 элементов И. Поэтому по импульсу со второго выхода распределителя 18 содержимое регистра 13 (т.е. адрес предыдущего элемента списка) через открытую группу 8 элементов И и группу 6 элементов ШШ переписывается в регистр 1. По импульсу с третьего выхода распределителя

18 указатель предыдущего элемента списка считывается на регистр ,3. Содержимое регистра 4 не изменяетс (так как группа 9 элементов И закрыта). Оно представляет собой адрес следующего элемента списка. Затем группа 9 элементов И открывается. Таким образом, на регистрах 3 и 4 сформирован элемент списка, который позволяет обойти удаляемый элемент. По импульсу с четвертого выхода распределителя 18 триггер 17 возвращается в нулевое состояние, в результате чего группа 10 элементов И закрывается. По этому же импульсу содержимое регистров 3 и 4 записывается в ячейку,,где хранился предьщущий элемент списка Затем содержимое регистра I переписывается в регистр 13 (хотя это и не является необходимым)), а содержимое регистра 4 заносится в регистр 1 .

В дальнейшем устройство работает аналогично описанному. Из списка удаляются все элементы, определенные содержимым регистра 12 1,с одинаковыми левыми указателями). Наступает такой момент, когда на регистр 4 будет считан нулевой код В этом случае генератор 19 переводится в запертое состояние, однако последний цикл завершается нормальным образом.

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

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

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

068064

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

введены третья, четвертая и пятая группы элементов И, регистр адре- ,,са, регистр адреса предыдущего элемента, узел сравнения, элемент ИЛИ,

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

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

50

55

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

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