Операции над структурами данных

Классификация структур данных

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

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

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

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

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

Интегрированными называются структуры данных, составными частями которых являются другие структуры данных – простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются с использованием средств интеграции данных, предоставляемых алгоритмическими языками.

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

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

По признаку изменчивости различают структуры статические, полустатические, динамические. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

Рис. 1.1. Классификация структур данных.

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

В языках программирования понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные характеризуются своими типами. Информация по каждому типу однозначно определяет:

– структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;

– множество допустимых значений, которые может иметь объект описываемого типа;

– множество допустимых операций, которые применимы к объекту описываемого типа.

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

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

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

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

Независимо от используемого языка, имеющиеся структуры данных не появляются «из ничего», а явно или неявно объявляются операторами создания структур. В результате всем экземплярам структур в программе выделяется память для их размещения.

Операция уничтожения структур данных противоположна по своему действию операции создания. Некоторые языки, такие как BASIC, FORTRAN не дают возможности уничтожать созданные структуры данных. В языках PL/1, C, PASCAL структуры данных, имеющиеся внутри блока, уничтожаются в процессе выполнения программы при выходе из этого блока (например, удаление локальных переменных подпрограмм). Операция уничтожения помогает эффективно использовать память.

Операция выбора используется для доступа к данным внутри структуры. Способ доступа зависит от типа структуры данных, к которой осуществляется обращение. Реализация метода доступа – один из наиболее важных свойств структур.

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

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

Дата добавления: 2014-01-07