В Камаев - Технологии программирования

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

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

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

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

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

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

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

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

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

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

Над всеми структурами данных могут выполняться пять операций: создание, уничтожение, выбор (доступ), обновление, копирование.

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

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

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

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

Операция копирования создает копию данных в новом месте памяти.

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

Упорядоченность элементов структуры данныхявляется важным ее признаком.

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

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

Пример широко известных структур данных с разной упорядоченностью приведен на рис. 4.1.

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

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