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

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

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

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

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

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

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

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

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

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 извлечения данных из стека и передача их в аккумулятор реализуются следующими программами.

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

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