Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
2. Структуры данных
Структура данных – это совокупность правил и ограничений, которые отражают связи, существующие между отдельными частями (элементами) данных. В вычислительной технике структура данных – это способ хранения данных в компьютере.
Выбор структуры данных начинается с выбора абстрактной структуры данных, которая предназначена для удобного хранения и доступа к информации. Абстрактные структуры данных делятся на 2 части – это интерфейс, то есть набор операций над объектами, и реализация.
Исходными данными для решения задачи являются описание набора и типов хранимых данных, а также перечень операций, выполняемых над ними.
Перед решением любой задачи необходимо ответить на ряд вопросов:
- Как логически организовать структуру данных,
- Как ее реализовать,
- Как осуществить поиск информации в этой структуре,
- Как упорядочить данные,
- Как выполнять корректировку данных в этой структуре.
При проектировании программного продукта разработчик обычно создает модель представления данных, которая не зависит от реализации, при этом используются абстрактные структуры данных.
Классификация абстрактных структур данных:
1. несвязанные структуры данных (множества),
2. структуры данных с неявными связями (массивы, записи, строки, хэш-таблицы, просмотровые таблицы, таблицы двоичного поиска и т.д.),
3. структуры данных с явными связями (стек, очереди, дек, бинарные и n-связные деревья, сети, графы).
Структуры данных также можно разделить на статические и динамические.
По определению, статичная структура отличается от динамической отсутствием изменчивости. Память для них выделяется один раз, и ее объем остается неизменным вплоть до уничтожения структуры. Реализация в виде непрерывной области памяти.
Достоинства статичной структуры:
- постоянство времени для доступа к любому элементу,
- оперативная память расходуется только на данные.
Недостатки:
- структура является неизменной.
Динамические структуры по определению характеризуются отсутствием смежности элементов структуры в памяти, также для них характерны непостоянство и непредсказуемость размера (числа элементов) структуры во время ее обработки. Поскольку элементы динамической структуры данных расположены по заранее неизвестным адресам, то адрес произвольного элемента не может быть вычислен. Поэтому для установки связи между элементами используются ссылки (указатели), через которые устанавливаются явные связи между элементами.
Каждый элемент динамической структуры состоит из двух частей:
1. информационные поля данных, в которых содержатся данные, ради которых и создается структура. Информационные поля в свою очередь могут также являться структурами данных.
2. служебные поля, содержащие одну или несколько ссылок, связывающих элементы между собой.
При использовании данных структур в прикладных задачах, конечному пользователю делаются видимыми только информационные поля, а служебные используются только программистом.
Достоинства динамической структуры:
- размер структуры ограничивается только доступным объемом оперативной памяти,
- при изменении порядка следования данных требуется не перемещать данные, а только корректировать ссылки,
- большая гибкость структуры.
Недостатки:
- нельзя заранее определить время, которое потребуется для доступа к произвольному элементу,
- требуется дополнительная память для хранения ссылок.
Некоторые абстрактные структуры данных:
Записи i-го уровня, адресованные из записи i-1-го уровня, образуют группу этой записи. Максимальное число записей в группе называется порядком или степенью дерева. Каждое дерево имеет один корень. От произвольного элемента до вершины (до корня) существует ровно один путь. Деревья реализуются на n-связных и двусвязных списках, в редких случаях в виде матриц связности.
PAGE 3