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

Ячейка памяти	Команда на машин­ном языке	Команда в симво­лической форме	Комментарий
. . . . . . . . .
1000	61	LRI 1	Загрузка регистров Н, L начальным
1001	20	20	адресом таблицы переходов
1002	62	LRI 2
1003	00	00
1004	F4	RSC	Сброс триггера С
1005	F2	RTR	Сдвиг младшего разряда аккумулятора в
			в триггер С
1006	78	JCN	Если С=1, то содержимое Н, L указы-
1007	10	10	вает на начальный адрес нужной ветви
1008	0Е	0Е	программы
1009	F5	IHL	Если С = 0, содержимое пары
100А	F5	IHL	регистров Н, L увеличивается дважды на 1 и
100В	7В	JMP	1 и указывает на
100С	10	10	следующий начальный адрес
100D	05	05
100Е	1F	MOV 0 from F	Замена в Н, L указателя на элемент таблицы переходов самим
100F	5F	IHL	адресом перехода
1010	F5	MOV 2 from F
1011	30	MOV 1 from 0
1012	F9	JHL	Переход на нужную ветвь программы
. . . . . . . . .
Таблица переходов:
2000	—	—	Начальный адрес ветви 1
2001	—	—
2002	—	—	Начальный адрес ветви 2
2003	—	—
. . . . . . . . .
200Е	—	—	Начальный адрес ветви 8
200F

В какой-то момент по команде перехода в ячейке 1006 микропро­цессор выйдет из цикла на команду в ячейке 100Е. В этот момент со­держимое пары регистров Н, L будет указывать на строку, содержа­щую начальный адрес нужной программной ветви. Четыре команды служат для загрузки этого начального адреса в регистры Н, L. По­скольку начальный адрес в строке таблицы замещает находившийся в Н, L указатель на саму строку, нужно особо позаботиться о том, чтобы не испортить указатель до того, как будет использована нахо­дящаяся в нем информация. Поэтому старшие разряды начального адреса ветви сначала переносятся в регистр 0, а не прямо в регистр Н. После этого указатель в Н, L увеличивается на 1, чтобы указывать на младшие разряды начального адреса, и эти разряды выбираются в регистр L, поскольку указатель больше не нужен. Затем в регистр Н переносятся старшие разряды начального адреса из регистра 0. На­конец, выполняется команда перехода по косвенному адресу, которая заносит содержимое регистров Н, L на программный счетчик, в ре­зультате чего начнется выполнение нужной программной ветви.

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

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