Сутью искусства программирования обычно
считается умение составлять операции.
Но не менее важно умение составлять данные.
Н. Вирт
Основные понятия
Процесс разработки программы на ассемблере традиционно осложняется
тем, что в этом языке ограничены средства описания данных, привычные
для языков программирования высокого уровня. В уроке 12 «Сложные
структуры данных» учебника были рассмотрены средства, которые
поддерживает ассемблер для работы с данными. Но это деление весьма
условно и не дает представления о том, как реализуется общая концепция
понятий «данное», «тип данных» и «структура данных» в контексте
программирования на языке ассемблера. Это обстоятельство существенно
влияет на эффективность изучения и использования языка ассемблера.
Учитывая сложность и практическую важность данного вопроса, есть смысл
изложить его более систематично.
Проблема представления и организации эффективной работы с данными
возникла одновременно с идеей разработки первой вычислительной машины.
Вычислительная машина функционирует согласно некоторому алгоритму. А
если есть алгоритм, то должны быть и данные, с которыми он работает.
Аналогично извечной дилемме о курице или яйце возникает вопрос о
первичности алгоритма и данных. Схожий вопрос неявно заложен в название
небезызвестной книги Никлауса Вирта — «Алгоритмы + структуры данных =
программы», два издания которой были выпущены издательством «Мир» в 1985
и 1989 годах.
Что же представляют собой понятия «данное», «тип данного», «структура
данных»? Попытаемся привести некую классификационную характеристику этих
понятий.
Данное — набор байт, рассматриваемый безотносительно к заложенному в
них смыслу. Понятие «обработка данных» характерно для процессора как
исполнительного устройства. При этом «данное» рассматривается как
совокупность двоичных разрядов, которыми манипулирует определенная
машинная команда. Для человека подобную интерпретацию вряд ли можно
считать удобной. Для него более естественной является логическая
интерпретация данных, которая базируется на понятии «типа данных».
Тип данных можно определить множеством значений данного и
набором операций над этими значениями. В учебнике с точки зрения типа
данные были разделены на две группы — простые и сложные. Данными
простого типа считаются элементарные, неструктурированные данные,
которые могут быть описаны с помощью одной из директив резервирования и
инициализации памяти. Примером таких данных являются целые и
вещественные числа различной размерности. В языках высокого уровня в
качестве простых данных используются еще и данные символьного,
логического, указательного типов. Данные простого типа называют
упорядоченными (или скалярными), так как теоретически можно перечислить
все значения, которые они могут принять.
Отличительная особенность данных простого типа — их
неструктурированность. В контексте конкретной задачи исходя из смысла и
логики обработки между некоторыми простыми данными могут существовать
определенные отношения И связи, что позволяет рассматривать их как
определенным образом организованные совокупности. Обобщенное название
таких совокупностей — структуры данных. В общем случае отдельная
структура данных может содержать не только простые данные, но и другие
структуры данных.
С известной долей условности можно сказать, что тип данного и
структура данных — понятия, не зависимые от компьютерной платформы.
Вполне можно абстрагироваться от представления в программе данных
простого или сложного типа и проводить теоретические рассуждения
относительно действий с целыми и вещественными числами, массивами,
списками, деревьями и т. д. Поэтому такие структуры данных называют
структурами данных уровня представления, абстрактными, или логическими,
структурами. Для машинной обработки абстрактные типы и структуры данных
необходимо некоторым способом представить в оперативной памяти, то есть в
виде физической структуры данных {структуры хранения), которая, в свою
очередь, отражает способ физического представления абстрактных данных на
конкретной программно-аппаратной платформе. В качестве примера можно
привести двумерный массив. Для программиста, пишущего программу для
обработки этого массива, он видится в виде матрицы, содержащей
определенное количество строк и столбцов. В оперативной памяти данный
массив представляется в виде линейной последовательности ячеек. В данном
случае логическая структура данных — двумерный массив, а
соответствующая ему физическая структура — вектор (см. ниже). Таким
образом, в большинстве случаев существует различие между логическими и
соответствующими им физическими структурами данных. Задачей программиста
фактически является написание кода, осуществляющего отображение
логической структуры на физическую и наоборот. Этот код реализует
различные операции логического уровня над структурой данных. Так, на
логическом уровне доступ к элементу двумерного массива осуществляется
указанием номеров столбца и строки в матрице, в которой расположен
данный элемент. На физическом уровне эта операция выглядит по-другому.
Для доступа^ к определенному элементу массива программный код по
известному номеру строки и столбца вычисляет смещение от начального
адреса массива в памяти. Исходя из вышеприведенных рассуждений
конкретную структуру данных можно характеризовать ее логическим
(абстрактным) и физическим (конкретным) представлениями, а также
совокупностью операций на этих уровнях.
Язык ассемблера — язык уровня архитектуры конкретного компьютера.
Память компьютеров с архитектурой Intel представляет собой упорядоченный
набор непосредственно адресуемых машинных ячеек (байтов). Исходя из
этого номенклатура структур хранения данных архитектурно ограничена
следующим набором: скаляр, вектор, список, сеть.
- Скаляр — поле, содержащее одиночное двоичное значение, размерностью один или несколько байтов. Количество байтов, составляющих скаляр, определяется допустимыми размерами операндов системы команд конкретного процессора.
- Вектор — конечное упорядоченное множество расположенных рядом скаляров одного типа, называемых элементами вектора. По сути дела вектор — это одномерный массив. Что у них общего? Геометрически вектор представляет собой состоящий из точек объект в пространстве, имеющий начальную точку, из которой он выходит, и конечную точку, в которую он приходит. Точки, лежащие в пространстве между начальной и конечной точками (элементы вектора), находятся между собой в единственно возможном отношении — отношении непосредственного следования. Такая строгая упорядоченность элементов вектора позволяет произвести их последовательную нумерацию. Аналогично и одномерный массив имеет началом и концом скаляры, расположенные по определенным адресам памяти. Между этими адресами последовательно расположены скаляры, составляющие элементы массива. Определенность с начальным и конечным адресами массива, а также с размерностью его элементов дает возможность однозначно идентифицировать любой его элемент.
- Список — набор элементов, каждый из которых состоит из двух полей. Одно поле содержит элемент данных или указатель на элемент данных, другое -указатель на следующий элемент списка, который, в свою очередь, тоже может быть начальным или промежуточным элементом другого списка. Наличие явного указания на упорядоченность элементов списка позволяет достаточно легко манипулировать содержимым списка, включая новые и исключая старые элементы списка без их фактического перемещения в памяти. Это свойство позволяет размещать в памяти динамически изменяющиеся структуры данных.
- Сеть — набор элементов, каждый из которых помимо информационного поля содержит несколько полей-указателей на другие элементы сети. С помощью сети удобно представлять такие структуры данных уровня представления, как деревья, ориентированные графы и т. п.
Как мы увидим ниже, эти четыре структуры хранения дают возможность представить в памяти машины практически все известные структуры уровня представления: массивы, записи, таблицы, стеки, Точереди, деки, списки различной степени связности, деревья, ориентированные и неориентированные графы. Эти структуры можно классифицировать по следующим признакам.
- Связность, то есть отсутствие или наличие явно заданных связей между элементами структуры. К несвязным структурам уровня представления относятся массивы, символьные строки, стеки, очереди. К связным структурам уровня представления относятся связные списки.
- Изменчивость, то есть изменение числа элементов и (или) связей между элементами структуры. По этому признаку структуры делятся на статические (массивы, таблицы), полу статические (стеки, очереди, деки) и динамические (одно-, двух- и многосвязные списки).
- Упорядоченность — линейные (массивы, символьные строки, стеки, очереди, одно- и двусвязные списки) и нелинейные (многосвязные списки, древовидные и графовые структуры).
Отображение структур представления в структуры хранения производится в соответствии с требованиями конкретной задачи и в зависимости от требований последней может производиться разными способами. В ходе дальнейшего изложения мы выясним возможности, которыми обладает язык ассемблера для представления и программной обработки наиболее полезных и часто используемых на практике структур представления (абстрактных типов данных).