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

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

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

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

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

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

4.2. ОПЕРАЦИИ НАД СТРУКТУРАМИ ДАННЫХ

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

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

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

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

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

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

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

4.3. ОБЩАЯ КЛАССИФИКАЦИЯ ЛОГИЧЕСКИХ СТРУКТУР ДАННЫХ

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

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

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

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