Структуры данных

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

Выбор структуры данных начинается с выбора абстрактной структуры данных, которая предназначена для удобного хранения и доступа к информации. Абстрактные структуры данных делятся на 2 части – это интерфейс, то есть набор операций над объектами, и реализация.

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

Перед решением любой задачи необходимо ответить на ряд вопросов:

- Как логически организовать структуру данных,

- Как ее реализовать,

- Как осуществить поиск информации в этой структуре,

- Как упорядочить данные,

- Как выполнять корректировку данных в этой структуре.

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

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

1. несвязанные структуры данных (множества),

2. структуры данных с неявными связями (массивы, записи, строки, хэш-таблицы, просмотровые таблицы, таблицы двоичного поиска и т.д.),

3. структуры данных с явными связями (стек, очереди, дек, бинарные и n-связные деревья, сети, графы).

Структуры данных также можно разделить на статические и динамические.

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

Достоинства статичной структуры:

- постоянство времени для доступа к любому элементу,

- оперативная память расходуется только на данные.

Недостатки:

- структура является неизменной.

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

Каждый элемент динамической структуры состоит из двух частей:

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

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

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

Достоинства динамической структуры:

- размер структуры ограничивается только доступным объемом оперативной памяти,

- при изменении порядка следования данных требуется не перемещать данные, а только корректировать ссылки,

- большая гибкость структуры.

Недостатки:

- нельзя заранее определить время, которое потребуется для доступа к произвольному элементу,

- требуется дополнительная память для хранения ссылок.

Некоторые абстрактные структуры данных:

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

1. на первом уровне расположена только одна запись (корень дерева).

2. к любой записи i-го уровня ведет адрес связи только одной записи i-1 уровня.

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

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