ВВЕДЕНИЕ

ТЕРМИНОЛОГИЯ

Основной сферой применения ЭВМ являются обработка больших массивов информации, организация их хранения, поиск в них нужных сведений. От правильной организации данных существенно зависит эффективность работы с этими данными. Данные могут быть организованы многими различными способами; логическая или математическая модель организации данных называется структурой данных [ 1 ].

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

Структуры данных, реализованные в конкретном языке программирования, называются типами данных этого языка.

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

Отношения между элементами данных могут быть различными. Например, в массиве элементы данных имеют один и тот же тип и строго упорядочены.

Физическая структура — это способ представления логической структуры данных в машинной памяти.

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

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

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

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

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

КЛАССИФИКАЦИЯ СТРУКТУР ДАННЫХ

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

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

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

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

Заметим, что в программировании термины «статические» и «динамические» по отношению к данным перегружены, — употребляются в двух смыслах: 1) по признаку изменчивости, — как указано выше; 2) по месту физического размещения — в сегментах данных или в свободно распределяемой памяти (Heap в DOS и Free storage в Windows).

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

• 1. Операция «создать» создает соответствующую структуру данных. Например, процедура New может использоваться для создания структур данных в динамически распределяемой памяти компьютера.
• 2. Операция «уничтожить» приводит к уничтожению созданной структуры данных. Например, процедура Dispose может использоваться для удаления созданных ранее структур данных.

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

3. Операция «выбрать» осуществляет доступ к данным структуры для чтения (Read only).

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

4. Операция «изменить» осуществляет доступ к данным структуры для записи (Read-Write) и приводит к изменению данных в структуре.

Авторы: Белов В.В., Чистякова В.И.