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