ОБЩИЕ СВЕДЕНИЯ
В предыдущих главах рассмотрена обработка данных, представленных в виде чисел различных систем счисления и форматов. На машинном уровне эти числа фиксируются как последовательности бит с примитивной организацией в виде байтов или многобайтных слов.
Однако с точки зрения пользователя такие числа представляют собой информационные объекты более высокого уровня абстракции. Например, числа с плавающей запятой определяются двумя взаимосвязанными элементами — мантиссой, порядком — и арифметическо-логическими операциями над ними. Если эти составляющие определены, то говорят о реализации числового типа данных в формате с плавающей запятой или типа действительных данных. Обработка информации в микропроцессорных системах (МП системах) не ограничивается числами, а использует различные типы данных и их совокупности —- структуры данных.Считается, что тип данных определен, если определены множества его элементов и отношений (операций) между элементами, причем эти отношения реализуются машинными средствами (аппаратурой или программами). Тип данных — это некоторая структура, с помощью которой осуществляется в машине иерархическое отображение информационных объектов: структуры нижнего уровня используются в качестве элементов структур более высокого уровня. Понятие структуры данных обобщает понятие типа данных для такой иерархии представлений. При выборе конкретных структур данных — структурировании данных — необходимо, с одной стороны, учитывать их проблемный аспект, т. е. пригодность для решения задач определенного класса, а с другой стороны,— ограничения на оперативность доступа к элементам структур и возможности их изменения (изменения числа элементов и отношений между ними), что определяет эффективность решения задач. Известны различные типы структур данных [40, 65].
Наиболее простой структурой является одномерный массив, представляющий конечное множество простых данных одного типа — множество однородных элементов.
Все элементы массива связаны отношением непосредственного следования, что позволяет их пронумеровать. Номер (индекс) позволяет однозначно идентифицировать любой элемент массива. Многомерные массивы можно рассматривать как одномерные, элементами которых являются не простые данные, а одномерные массивы.Если составить массив из данных различных типов, образуется структура другого вида — запись. Запись, как правило, содержит совокупность информации об одном объекте. Элементы записи называются полями. Доступ к элементу возможен либо по его номеру в записи, либо по значению поля. Совокупность записей, имеющих одинаковую организацию, образует таблицу. Таблицу можно рассматривать как массив, элементами которого являются записи. Обычно одно из полей каждой записи отводится для хранения уникального кода — ключа. Таблица является наиболее распространенной структурой данных в большинстве программных комплексов. Массивы, записи и таблицы сохраняют свою структуру постоянной в течение всего времени существования. В силу этого их называют статическими структурами. Достоинством этих структур является смежность элементов и как следствие непрерывность области памяти, отводимой под структуры, недостатком — постоянство отношений между элементами, которое задается при создании структуры и не подлежит изменению в процессе ее обработки.
Помимо статических, существуют динамические структуры, длины и отношения между элементами которых изменяются в процессе обработки. Одним из представителей динамических структур является связный список, элементы которого — это записи одного формата, содержащие указатели на другие элементы списка. Простейший связный список — односвязный. Поле указателя элемента односвязного списка содержит адрес следующего элемента (рис. 5.1), поле указателя последнего элемента — нулевой указатель, свидетельствующий об окончании списка. Удаление элементов из списка, вставка их в любое место списка сводятся лишь к изменению указателей. Организация списка не требует физической смежности элементов в памяти: они могут быть расположены различным образом относительно друг друга.
Вследствие этого в динамических структурах увели-
Рас. 5.1. Структура однонаправленного связного списка:
А — адресная ссылка на следующий элемент; К. — «ключ» — байт с уникальным для каждого элемента кодом; И — информационная основа элемента
чивается время доступа к элементам. Если в статических структурах по номеру элемента можно сразу определить его адрес в памяти, то в динамических структурах для доступа к искомому элементу необходимо прочесть поля указателей всех предыдущих элементов списка.
Кроме односвязных, существуют двухсвязные и много- связнЫе (сетевые) списки. В элементах двухсвязных списков присутствуют два поля указателей: один указывает на последующий элемент, второй — на предыдущий. В элементах многосвязных списков имеется несколько указателей.
Статические и динамические структуры обладают противоположными свойствами с точки зрения изменяемости и оперативности доступа к элементам. Компромиссное. решение представляют полустатические структуры, к которым относятся стеки, очереди и деки. Полу статическая структура — последовательный список, в котором элементы связаны между собой не указателями, а отношениями непосредственного следования. В отличие от статических структур в полустатических имеется возможность изменять количество элементов. На процедуры изменения в полустатических структурах накладываются определенные ограничения, которые и характеризуют разновидности таких структур. Стек представляет собой последовательный список переменной длины; элементы включаются в этот список и исключаются из него только с одной стороны: с начала или конца списка. Со стеком связан лишь один указатель, содержащий адрес первого (или последнего) элемента стека. Очередь отличается от стека тем, что позволяет включать элементы только с конца («хвоста») списка, а исключать только с его начала («головы»). В связи с этим для очереди требуются два указателя, один из которых содержит адрес «хвоста», а второй — адрес «головы» очереди.
Очередь специального вида, в которой элементы можно включать и исключать с любого конца, называется деком.В этой главе описываются простые операции над структурами данных: организация доступа (прямого и ассоциативного), исключение, добавление элементов и их модификация. Все приведенные далее программы обладают свойством реентерабельности: программа в процессе выполнения может быть в любой момент прервана, вызвана в прерывающей программе и выполнена вновь полностью, а затем после возврата из прерывания продолжена с прерванного места, причем оба процесса выполнения программы будут правильными по результатам (второй вызов программы не изменяет промежуточных данных первого ее вызова). Требование реентерабельности предъявляется к программам, используемым в системах реального времени. Реентерабельность можно обеспечить, если все рабочие переменные, с которыми работает программа, располагать в регистрах микропроцессора. В этом случае в прерывающей программе достаточно «сохранять регистры в стеке» перед началом ее работы и «восстанавливать регистры из стека» после завершения работы программы. Тем самым гарантируется сохранность промежуточных данных предыдущего процесса выполнения прерываемой программы.
Однако не всегда удается размещать все данные в регистрах: часть переменных приходится размещать в оперативной памяти. В этом случае для вложенных вызовов данной программы одни и те же рабочие переменные должны для каждого вызова размещаться в различных ячейках памяти, что выполнимо, если адрес рабочей области (области сохранения параметров) передавать в списке параметров вызываемой программы.
Другой, более эффективный прием — адресация рабочих переменных, а также части Параметров через общий стек. Такой прием экономит оперативную память, но затрудняет доступ к рабочим переменным. Использовать для реализации этого приема команды работы со стеком неудобно, так как они оперируют только с вершиной стека. Целесообразно оформлять процедуры доступа к данным, расположенным в общем стеке, в виде макрокоманд (см.
прил. 3).Рассмотрим ряд макрокоманд:
Макрокоманды RCHG и XCHR осуществляют обмен' содержимым соответственно регистров и регистровых пар. В макрокоманде RCHG в качестве промежуточного запоминающего регистра используется аккумулятор, а в макрокоманде XCHR — вершина стека. Макрокоманда RCHG изменяет содержимое аккумулятора. Макрокоманды XTRR, XTRN и LDSP предназначены для работы с содержимым стека. Макрокоманда XTRR является аналогом процессорной команды XTHL и позволяет производить обмен между вершиной стека и регистровыми парами (В, С) и (D, Е). Макрокоманда XTRN обеспечивает непосредственный доступ к указанному слову стека. Доступ к данным, содержащимся в стеке, осуществляется с помощью базовой косвенной адресации. В качестве базового адреса используется содержимое регистра указателя стека SP. В качестве операндов, определяющих имена регистров, нельзя указывать регистры (Н) и (L), так как они используются для адресации содержимого стека. Действия макрокоманды LDSP аналогичны действиям макрокоманды XTRN, за исключением того, что содержимое указанных регистров теряется, а не помещается в стек, как.
в XTRN. Следует отметить, что макрокоманды XTRN и LDSR изменяют содержимое аккумулятора, так как используют макрокоманду RCHG.
5.2.