Доставка цветов в Севастополе: SevCvety.ru
Главная -> Появление первого микропроцессора

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116

о о о о

Рис. 5.1. Структура однонаправленного связного списка:

А - адресная ссылка на следующий элемент; К - «ключ» - байт с уникальным для каждого элемеЕ1та кодом; И - информационная основа элемента

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

Кроме односвязных, существуют двухсвязные и много-связнЫе (сетевые) списки. В элементах двухсвязных списков присутствуют два поля указателей: один указывает на последующий элемент, второй - на предыдущий. В элементах многосвязных списков имеется несколько указателей.

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



определенные ограничения, которые и характеризуют разновидности таких структур. Стек представляет собой последовательный список переменной длины; элементы включаются в этот список и исключаются из него только с одной стороны: с начала или конца списка. Со стеком связан лишь один указатель, содержащий адрес первого (или последнего) элемента стека. Очередь отличается от стека тем, что позволяет включать элементы только с конца («хвоста») списка, а исключать только с его начала («головы»). В связи с этим для очереди требуются два указателя, один из которых содержит адрес «хвоста», а второй - адрес «головы» очереди. Очередь специального вида, в которой элементы можно включать и исключать с любого конца, называется деком.

В этой главе описываются простые операции над структурами данных: организация доступа (прямого и ассоциативного), исключение, добавление элементов и их модификация. Все приведенные далее программы обладают свойством реентерабельности: программа в процессе выполнения может быть в любой момент прервана, вызвана в прерывающей программе и выполнена вновь полностью, а затем после возврата из прерывания продолжена с прерванного места, причем оба процесса выполнения программы будут правильными по результатам (второй вызов программы не изменяет промежуточных данных первого ее вызова). Требование реентерабельности предъявляется к программам, используемым в системах реального времени. Реентерабельность можно обеспечить, если все рабочие переменные, с которыми работает программа, располагать в регистрах микропроцессора. В этом случае в прерывающей программе достаточно «сохранять регистры в стеке» перед началом ее работы и «восстанавливать регистры из стека» после завершения работы программы. Тем самым гарантируется сохранность промежуточных данных предыдущего процесса вьшолнения прерываемой программы.

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



Другой, более эффективный прием - адресация рабочих переменных, а также части Ьараметров через общий стек. Такой прием экономит оперативную память, но затрудняет доступ к рабочим переменным. Использовать для реализации этого приема команды работы со стеком неудобно, так как они оперируют только с вершиной стека. Целесообразно оформлять процедуры доступа к данным, расположенным в общем стеке, в виде макрокоманд (см. прил. 3).

Рассмотрим ряд макрокоманд:

i НАКРОКОМЙИДА ОБМЕНА СОДЕРЛИМЫН РЕГИСТРОВ.

i ПАРАМЕТРЫ! R1,R2-ИМЕНА РЕГИСТРОВ.

} ОЦЕНКА! ВРЕМЯ-15 ТАКТОВ; ДЛИНА-3 БАЙТА.

, . RCHG MACRO R1,R2 MOV A,R1 MOV R1,R2 MOV R2,A ENBM

; МАКРОКОМАНДА ОБМЕНА СОДЕРЖИМЫМ РЕГИСТРОВЫХ ПАР.

5 ПАРАМЕТРЫ: XI,Х2 - ИМЕНА РЕГИСТРОВЫХ ПАР.

! ОЦЕНКА!ВРЕНЯ - 44 ТАКТА!ЯЛИНА-4 БАЙТА; ГЛУБИНА СТЕКА-4

; БАЙТА.

;к«к«кк«к»кк»х«»««««ккккз1«)(««)с««»««)с»»«»)С)С)С)1К)н(к«к«)(«)Н(« XCHR MACRO XI,Х2

PUSH XI

PUSH Х2

POP XI

POP Х2

ENBM

{КККККККХКККХККККККММКККХХКККККККХККХХХКККХХККККХККККХКК

; МАКРОКОМАНДА ОБМЕНА СОДЕРЖИМЫМ РЕГИСТРОВОЙ ПАРЫ И ЕЕР-

i ШИНЫ СТЕКА.

; ПАРАМЕТРЫ: Х1-ИМЯ РЕГИСТРОВОЙ ПАРЫ (D ИЛИ Б ).

; ОЦЕНКА: ВРЕМЯ - 77 ТАКТОВ; ДЛИНА - 13 БАЙТ; ГЛУБИНА

; СТЕКА - 2 БАЙТА.

XTRR MACRO XI

XCHR Н,Х1 XTHL

XCHR HrXl ENDM

;i«K«»K««»K»K»»«»»»«KK«»»««»K»i«KKK«K««»«»»«KK»K«)C)CK)c«)c« ; МАКРОКОМАНДА ОБМЕНА СОДЕРЖИМЫМ РЕГИСТРОВОЙ ПАРЫ И ; N-M СЛОВОМ В СТЕКЕ.

; ПАРАМЕТРЫ: Rl-ИМЯ СТАРШЕГО РЕГИСТРА РЕГИСТРОВОЙ ПАРЫ ; ( КРОМЕ Н ), R2-HH3 МЛАДШЕГО РЕГИСТРА РЕГИСТРОВОЙ ПАРЫ ; ( КРОМЕ L ), N-HOMEP СЛОВА В СТЕКЕ ОТНОСИТЕЛЬНО ТЕКУ-; «ЕГО ЗНАЧЕНИЯ SP.

5 ОЦЕНКА:БРЕМЯ-61 ТАКТ;ДЛИНА-? ЕАЙТ;ГЛУБИНА СТЕКА-2 БАЙТА.

XTRN MACRO R1»R2,H PUSH Н



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 [70] 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116



0.0099
Яндекс.Метрика