Общее понятие структуры данных

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

Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры важным является то обстоятельство, что в данной машинной архитектуре, в данной системе программирования мы всегда можем заранее сказать, каков будет размер данного простого типа и какова структура его размещения в памяти. С логической точки зрения простые данные являются неделимыми единицами. Интегрированными называются такие структуры данных, составными частями которых являются другие структуры данных - простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.

В зависимости от отсутствия или наличия явно заданных связей между элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).

Весьма важный признак структуры данных - ее изменчивость - изменение числа элементов и (или) связей между элементами структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

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

Важный признак структуры данных - характер упорядоченности ее элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ структуры.

В зависимости от характера взаимного расположения элементов в памяти линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти (односвязные, двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья, графы.

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

Информация по каждому типу однозначно определяет:

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

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

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

СТРУКТУРА ДАННЫХ - совокупность физически (типы данных) и логически (алгоритм, функции) взаимосвязанных переменных и их значений.

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

СТАТИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность фиксированного количества переменных постоянной размерности с неизменным характером связей между ними
И наоборот, если один из параметров структуры данных -количество переменных, их размерность или взаимосвязи между ними меняются во время работы программы, то такие структуры данных называются динамическими.

ДИНАМИЧЕСКАЯ СТРУКТУРА ДАННЫХ - совокупность переменных, количество, размерность или характер взаимосвязей между которыми меняется во время работы программ.

Динамические структуры данных базируются на двух элементах языка программирования:

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

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

Таким образом, близко к истине и такое определение: динамические структуры данных -это динамические переменные и массивы, связанные указателями.
Говоря о структурах данных, нельзя забывать, что обычные переменные размещаются в оперативной памяти (внутренней памяти компьютера). Поэтому обычно и структуры данных имеют отношение к памяти. Однако существует еще и внешняя память, которая в языке доступна опосредованно через операторы (Паскаль) или функции (Си), работающие с файлами. В режиме двоичного файла произвольного доступа любой файл представляет собой аналог неограниченной прямо адресуемой области памяти, то есть с точки зрения программы выглядит так же, как обычная память. Естественно, что программа может копировать переменные из памяти в произвольное место файла и обратно, а значит и организовывать в файле любые (в том числе и динамические) структуры данных.
Структура данных - это исполнитель, который организует работу с данными, включая их хранение, добавление и удаление, модификацию, поиск и т.д. Структура данных поддерживает определенный порядок доступа к ним. Структуру данных можно рассматривать как своего рода склад или библиотеку. При описании структуры данных нужно перечислить набор действий, которые возможны для нее, и четко описать результат каждого действия. Будем называть такие действия предписаниями. С программной точки зрения, системе предписаний структуры данных соответствует набор функций, которые работают над общими переменными.
Структуры данных удобнее всего реализовывать в объектно-ориентированных языках. В них структуре данных соответствует класс, сами данные хранятся в переменных-членах класса (или доступ к данным осуществляется через переменные-члены), системе предписаний соответствует набор методов класса. Как правило, в объектно-ориентированных языках структуры данных реализуются в виде библиотеки стандартных классов: это так называемые контейнерные классы языка C++, входящие в стандартную библиотеку классов STL, или классы, реализующие различные структуры данных из библиотеки Java Developer Kit языка Java.
Тем не менее, структуры данных столь же успешно можно реализовывать и в традиционных языках программирования, таких как Фортран или Си. При этом следует придерживаться объектно-ориентированного стиля программирования: четко выделить набор функций, которые осуществляют работу со структурой данных, и ограничить доступ к данным только этим набором функций. Сами данные реализуются как статические (не глобальные) переменные. При программировании на языке Си структуре данных соответствуют два файла с исходными текстами:
1. заголовочный, или h-файл, который описывает интерфейс структуры данных, т.е. набор прототипов функций, соответствующий системе предписаний структуры данных;
2. файл реализации, или Си-файл, в котором определяются статические переменные, осуществляющие хранение и доступ к данным, а также реализуются функции, соответствующие системе предписаний структуры данных
Структура данных обычно реализуется на основе более простой базовой структуры, ранее уже реализованной, или на основе массива и набора простых переменных. Следует четко различать описание структуры данных с логической точки зрения и описание ее реализации. Различных реализаций может быть много, с логической же точки зрения (т.е. с точки зрения внешнего пользователя) все они эквивалентны и различаются, возможно, лишь скоростью выполнения предписаний.

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