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

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

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

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

Байт  это минимально адресуемый элемент данных, состоящий из 8 двоичных цифр, представляющих собой единое целое, например, число. Положение любого байта характеризуется его адресом.

Бит  это минимальный информационный элемент, характеризующийся значением одной двоичной цифры. В большинстве МП невозможно адресоваться к каждому биту в отдельности. Положение бита характеризуется адресом байта, в котором он находится и его номером в данном байте.

Представление информации в виде совокупности битов соответствует упакованному формату данных. Упакованный формат используется только при вводе/выводе информации. Для обработки упакованная информация должна быть распакована, что реализуется программным путем. Как правило, распаковка осуществляется однократно, и значение каждого бита представляется флаговым байтом в памяти. Это повышает быстродействие программы, т. к. не требуется распаковки данных при каждом обращении к этому формату.

Слово  это элемент данных, состоящий из нескольких байтов, представляющих собой единое целое, например, число расширенного диапазона. Слово задается его адресом и типом, т. е. количеством входящих в него байтов. Стандартными типами слов являются простое слово (2 байта), двойное слово (4 байта), квадрослово (8 байтов) и тераслово (10 байтов).

Структура  это элемент данных, представляющий собой совокупность нескольких байтовых или словарных полей, объединенных под общим именем. Положение структуры в памяти характеризуется ее адресом, а поля в ней  смещением относительно начала структуры. Тип структуры указывает количество входящих в нее байтов.

Запись  это элемент данных, представляющий собой совокупность нескольких битовых полей, объединенных под общим именем. Запись характеризуется ее адресом и типом. Поля записи выделяются и обрабатываются программным путем.

Простейшие элементы данных могут образовывать простые блоки данных: массив, очередь и стек.

Массив  это совокупность элементов данных одинакового типа, расположенных в смежных ячейках памяти. Массив характеризуется его начальным адресом BASE и количеством элементов в нем. Положение элемента в массиве характеризуется его порядковым номером, называемым индексом IND. Адрес элемента вычисляется по формуле

ADDR = BASE + INDtype,

где type  размер элемента в байтах.

Произведение IND  type является смещением элемента относительно начала массива. Для увеличения быстродействия целесообразно выбирать размер type элементов массива кратным степени 2 (1, 2, 4, 8, 16, . . .). Тогда при вычислении смещения операцию умножения можно заменить соответствующим количеством сдвигов индекса IND влево (0, 1, 2, 3, 4, . . .).

Массивы данных могут быть одно-, двух-, трехмерными и т. д.

Положение каждого элемента одномерного массива A(I) полностью определяется его номером. Поэтому общий индекс в этом случае IND = I и адрес элемента одномерного массива вычисляется по формуле

ADDR(I) = BASE + I type.

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

A(0,0) A(0,1) . . . . A(0,M)

A(1,0) A(1,1) . . . . A(1,M)

. . . . . . . . . . . . . . . .

A(L,0) A(L,1) . . . . A(L,M)

размерностью (LM) приведены на рис. 3.16.

Для определения адреса некоторого элемента массива A(I, J) необходимо вычислить его общий индекс по формулам:

IND(I, J) = I M + J при хранении по строкам;

IND(I, J) = I + J L  при хранении по столбцам.

После этого адрес элемента A(I, J) двухмерного массива определяется обычным образом по формуле

ADDR(I, J) = BASE + IND(I, J) type.

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

Элементы массива могут выбираться в произвольной последовательности.

Очередь – это разновидность одномерного массива данных. Ее отличие от массива состоит в том, что выбор элемента из очереди возможен лишь с одного конца, называемого началом очереди, и сопровождается его исключением из нее. Включение элемента в очередь возможно только с другого конца, называемого концом очереди. Главная особенность очереди заключается в том, что ее элементы считываются из нее в той же последовательности, в которой включаются в нее. Часто очередь называют структурой данных типа FIFO (First Input, First Output – первый пришел, первый ушел). Количество элементов в очереди является ее длиной.

Рис. 3.16. Размещение двухмерного массива в памяти:

а) по строкам; б) по столбцам

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

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

Указатель начала очереди BegQ адресует элемент, подлежащий считыванию и исключению из очереди, а указатель конца очереди EndQ  последний элемент очереди или, что часто более удобно, следующую ячейку за последним элементом.

При выборке элемента из очереди он считывается по адресу указателя начала BegQ, а затем этот указатель инкрементируется (предполагается, что очередь растет вниз, в область больших адресов). При включении элемента в очередь он записывается по адресу указателя конца EndQ, а затем этот указатель инкрементируется.

Рис. 3.17. Организация очереди в памяти

Однако нельзя неограниченно увеличивать указатели начала и конца очереди, т. к. в противном случае она займет всю область памяти. Поэтому для очереди устанавливаются верхняя TQ и нижняя BQ границы и используется ее кольцевая организация. Это сводится к тому, что как только любой из указателей после инкрементирования принимает значение BQ + 1, ему присваивается значение TQ. Благодаря этому, ячейки TQ и BQ становятся смежными.

Наиболее часто в МПС очереди используются при вводе и выводе символьных данных. Для очереди выделяется некоторая область смежных ячеек памяти, размер которой определяется максимально возможной длиной очереди. При этом определяются ее границы TQ и BQ. Оба указателя BegQ и EndQ инициализируются на значение TQ. После этого данные могут включаться и исключаться из очереди.

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

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

В операциях со стеком могут возникнуть те же особые случаи, что и при использовании очереди. Попытка загрузить данные в ячейку с адресом, меньшим минимального адреса области стека, называется переполнением, а попытка извлечения данных из ячейки с адресом, большим максимального адреса области стека, называется антипереполнением. В МП ВМ86/ВМ88 нет никаких средств контроля за границами стека, и эта задача возлагается на программиста.

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

При разработке структур данных их целесообразно представлять в табличной форме.