Глава 4 СТРУКТУРА ДАННЫХ ПРОГРАММ

Глава 4

СТРУКТУРА ДАННЫХ ПРОГРАММ

4.1. ПОНЯТИЕ СТРУКТУРЫ ДАННЫХ ПРОГРАММ

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

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

Н. Вирт определил понятие программы следующим образом:

Алгоритмы + структуры данных = программы

Простейшие структуры данных, реализуемые языком программирования, называют также стандартными типами данных. Многие языки программирования позволяют на основе стандартных типов строить типы данных, определенные программистом (пользователем).

Что же характеризует данные более содержательно, чем значения? В 1973 г. Н. Виртом была опубликована статья "Типы данных — это не значения". С его точки зрения тип данных — это множество значений. В статье говорилось также, что данные прежде всего характеризуются набором операций, которые можно выполнять над этими данными, множеством значений. Этот взгляд и дал миру впоследствии некоторые очень полезные идеи. Главная формула, которой стали придерживаться:

ТИП ДАННЫХ = МНОЖЕСТВО ЗНАЧЕНИЙ + НАБОР ОПЕРАЦИЙ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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