Читаем Технологии программирования полностью

Важно понять, что понятия данных и операций очень взаимосвязаны. Пусть есть некоторая структура данных, для которой существует операция Length, которая возвращает длину этой структуры в некоторых единицах. Возникает вопрос: есть ли где-то данные, называющиеся длиной, или нет. С содержательной точки зрения это совершенно неважно. Если эта операция применяется к строкам, признак конца которых ноль (null terminated string), то вычисление длины — это, действительно, операция, требующая вычислений. Если эта операция применяется к строкам, первый байт которых означает длину строки, а дальше идет сама строка (как в Turbo Pascal), то здесь происходит просто взятие данных из памяти, т. е. длина может быть операцией, а может быть данными, хотя это и неважно для программиста.

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

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

Языки программирования высокого уровня поддерживают системы формальных обозначений однозначного описания как абстрактных структур данных, так и алгоритмов программ. Использование мнемоники имен констант или переменных облегчает работу программисту. Для компьютера все типы данных сводятся в конечном счете к последовательности битов (байтов) и мнемоника имен ему безразлична. Компилятор связывает каждый идентификатор с определенным адресом памяти, при этом он учитывает информацию о типе каждой именованной величины с целью проверки совместимости типов. Человек обладает интуитивной способностью разбираться в типах данных и тех операциях, которые для каждого типа справедливы. Так, например, нельзя извлечь квадратный корень из слова или написать число со строчной буквы.

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

Программисту, который хочет, чтобы его программа имела реальное применение в некоторой прикладной области, не следует забывать о том, что программирование — это обработка данных. У реального программного изделия всегда есть Заказчик. У Заказчика есть входные данные, и он хочет, чтобы по ним были получены выходные данные, а какими средствами это обеспечивается — его обычно не интересует. Таким образом, задачей создания любого программного продукта является преобразование входных данных в выходные через последовательные состояния промежуточных данных.

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

Структура данных относится по существу к "пространственным" понятиям: ее можно свести к схеме организации информации в памяти компьютера. Алгоритм же является соответствующим процедурным элементом в структуре программы — он служит рецептом расчета.

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

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

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