Структура данных. 
Информатика и математика

Работа с данными упрощается, когда данные упорядочены, т. е. имеют структуру.

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

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

Хорошо спроектированное хранилище данных оптимизирует использование ресурсов, требуемых для выполнения операций. Если данные хранятся в организованной структуре, то каждый элемент данных приобретает новый параметр — свой адрес в этой структуре. Работать с упорядоченными данными удобнее, но за это приходится платить увеличением их количества, поскольку адреса элементов — это дополнительные данные, которые тоже надо хранить и обрабатывать.

Рассмотрим некоторые структуры данных.

Массивы и связные списки

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

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

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

Достоинства:

— легкость вычисления адреса элемента массива по его индексам (поскольку элементы массива располагаются один за другим);

• — одинаковое время доступа ко всем элементам;
• — хранить нужно только сами данные, никакие дополнительные ссылки не требуются.

Недостатки:

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

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

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

Пример 11.4.

1. Односвязный список (однонаправленный связный список). Более темным цветом обозначена ссылка (поле указателя) на следующий элемент списка.

В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента из данного списка невозможно.

2. Двусвязный список (двунаправленный связный список). Более темным цветом обозначена ссылка на следующий/предыдущий элемент списка.

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

Достоинства:

• — легкость добавления и удаления элементов;
• — размер списка ограничен только объемом памяти компьютера и разрядностью указателей (ссылок);
• — динамическое добавление и удаление элементов.

Недостатки:

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