Основные понятия и определения. Структура данных (СД) — общее свойство информационного объекта, с которым взаимодействует та или иная программа

Структура данных (СД) — общее свойство информационного объекта, с которым взаимодействует та или иная программа. Это общее свойство характеризуется:

1) множеством допустимых значений данной структуры;

2) набором допустимых операций;

3) характером организованности.

Различают следующие уровни описания СД:

1) абстрактный (математический) уровень;

2) логический уровень;

3) физический уровень.

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

Основные типы СД:

1. Множество (рис.1) — совокупность независимых элементов, отношения между которыми не заданы.

D1 D2 D3

Рис. 1. СД типа «множество»

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

D1 D2 D3

Рис. 2. СД типа «последовательность»

3. Дерево (рис.3) — множество элементов, над которыми определены отношения иерархического порядка, т.е. «один ко многим».

D1

D2 D3

D4 D5 D6

Рис.3. СД типа «дерево»

4. Граф (рис.4) — множество элементов, на которых определены отнощения бинарного порядка, т.е. “многие ко многим”.

D1 D2 D3

D4 D5

Рис.4. СД типа «граф»

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

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

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

Физический уровень — отображение на память ЭВМ информационного объекта в соответствии с логическим описанием. На этом уровне определяются область и объем памяти, необходимый для хранения экземпляра СД, форматы и интерпретация внутреннего представления. На физическом уровне, в памяти ЭВМ, СД могут иметь последовательную (прямоугольную) или связанную схему хранения, располагаться в статической или динамической памяти. При последовательной схеме хранения данные располагаются в соседних, последовательно расположенных ячейках памяти. Физический порядок следования данных полностью соответствует логическому. При связной схеме хранения каждый элемент СД имеет ссылку на другой (другие) элементы. Физический порядок следования данных может не соответствовать логическому.

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

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

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

Память (статическая или динамическая), используемая для хранения экземпляра СД, и схема хранения СД определяется реализацией СД и не является свойством СД.

Л а б о р а т о р н а я р а б о т а № 1