Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Структуры данных






Одной из важных предпосылок успешного проектирования МП-систем является четкое представление характера данных, которыми оперирует прикладная программа. Создатель языка ПАСКАЛЬ Н. Вирт в своей книге «Алгоритмы + структуры данных = программы» (Prentice Hall, 1976) писал: «...все интуитивно чувствуют, что данные предшествуют алгоритмам: необходимо иметь некоторые объекты, прежде чем оперировать ими».

Под структурами данных понимают наборы некоторым образом организованных данных. Характер организации может быть простым, например, когда элемент в массиве определяется своим номером (индексом), или сложным, например, когда элемент двусвязного списка вместе с собственно данными должен содержать указатели преемника и предшественника. Программисту необходимо знать наиболее распространенные структуры данных, способы хранения их в памяти МП-систем и эффективного использования в прикладных программах. Правильный выбор структуры данных позволяет уменьшить объем памяти и увеличить производительность МП-системы. Пока в МП-системах применяются простые структуры данных, но расширение возможностей микропроцессоров позволяет использовать все более сложные структуры данных. В данном подразделе кратко рассматриваются основные структуры данных и приводятся программы некоторых операций с ними.

Массивы. Наиболее простой и распространенной структурой данных является одномерный массив. Он представляет собой набор элементов данных (записей) одинаковой длины, который размещается в области смежных ячеек памяти с начальным (базовым) адресом BASE. Число элементов в массиве называется его длиной. Положение любого элемента в массиве характеризуется его порядковым номером, называемым индексом или смещением. Адрес элемента равен сумме базового адреса BASE и индекса IND, умноженного на длину элемента в байтах. На практике целесообразно применять массивы, длина элементов которых равна степени двух. Тогда при вычислении адреса элемента операция умножения заменяется сдвигами. В наиболее простых массивах длина элементов составляет 1 байт. Формирование и обработка массивов осуществляются циклическими программами, состоящими из трех частей: инициализации, обращения к текущему элементу, перехода к следующему элементу и проверки условия окончания цикла. В программах используются два важных регистра:

регистр, хранящий адрес текущего элемента и называемый указателем POINTER (сокращенно PTR);

регистр-счетчик, фиксирующий окончание цикла после обработки последнего элемента массива.

В микропроцессоре I8080 для операций с массивам удобно применять косвенную адресацию, где функции указателя выполняют регистры (Н, L). Приведем простую программу поиска максимального числа в массиве
8-битных целых чисел. Длина массива хранится в ячейке с адресом LENGT, а в качестве счетчика используется регистр В.

 

Метка Код Операнд Комментарий
  LDA LENGT ; Инициализация счетчика
  MOV В, А  
  LXI H, BASE ; Инициализация указателя
NEWMX: MOV А, М  
NEXT: DCR В ; Проверка окончания цикла
  JZ DONE  
  INX Н ; Переход к следующему элементу
  CMP М ; Сравнение его с максимумом
  JC NEWMX ; Новый максимум
  JMP NEXT   ; Следующий элемент меньше
DONE: ***   ; Максимум в аккумуляторе

 

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

Когда длина элементов больше одного байта, необходимо считывать из массива соответствующее число байт и правильно модифицировать указатель. Следующая программа вычисляет в регистрах (D, Е) сумму 16-битных элементов массива, представляющих собой целые без знака.

 

Метка Код Операнд Комментарий
  LDA LENGT ; Инициализация счетчика
  MOV В, А  
  LXI D, 0 ; Начальное значение суммы
ADDW: MOV А, М ; Суммирование
  ADD Е ; младшего
  MOV Е, А ; байта
  INX Н ; Указатель на старший байт
  MOV A, M ; Суммирование
  ADC D ; старшего байта
  MOV D, A ; (с учетом переноса)
  INX H ; Следующий элемент
  DCR В ; Проверка окончания цикла
  JNZ ADDW  
DONE: ***   ; Сумма в регистрах (D, Е)

Cтек

 

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

В микропроцессоре I8080 имеется аппаратный указатель стека и все команды, связанные с загрузкой данных в стек и извлечением их из стека, сопровождаются автоматической модификацией SP. До использования стека необходимо инициализировать SP командой LXI SP на максимальный адрес области оперативной памяти, выделенной для стека.

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

При программировании иногда удобно использовать то обстоятельство, что извлечение данных из стека является неразрушающим. Пусть, например, командой POP H произведены извлечение данных из стека и передача их в регистры (Н, L). Если произвести декремент SP двумя командами DCX SP, то те же самые данные можно затем передать в любую регистровую пару командой POP rp.

Доступ к SP производится через регистры (Н, L).Когда требуется запомнить содержимое SP в двух ячейках памяти, адрес первой из которых есть STPTR, выполняется следующая последовательность команд: LXI Н, 0; DAD SP; SHLD STPTR. Загрузка SP из указанных ячеек осуществляется двумя командами LHLD STPTR; SPHL.

При необходимости несложно реализовать программный стек со своим указателем. Если, например, адрес верхушки стека хранится в двух ячейках памяти, адрес первой из которых есть STACK, то операция PSHST загрузки в стек содержимого аккумулятора и операция POPST извлечения данных из стека и передача их в аккумулятор реализуются следующими программами.

 

Запись в стек содержимого аккумулятора

 

Метка Код Операнд Комментарий
PSHST: LHLD STACK ; Загрузка указателя стека в (Н, L)
  DCX Н ; Декремент указателя
  MOV М, А ; Загрузка в стек аккумулятора
  SHLD STACK ; Запоминание указателя стека в (H, L)

 

Копирование содержимого стека в аккумулятор

 

Метка Код Операнд   Комментарий
POPST: LHLD STACK ; Загрузка указателя в (H, L)
  MOV A, M ; Извлечение из стека
  INX H ; Инкремент указателя стека
  SHLD STACK ; Запоминание указателя стека в ОП

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.