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

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

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

Структуры данных, которые физически создаются, хранятся и обрабатываются в основной (оперативной) памяти ЭВМ, называются оперативными структурами. Представление структуры хранения во внешней памяти называют файловой структурой. Файл – это поименованная совокупность данных, расположенных на внешнем носителе, например, на диске. Элементами файловой структуры служат, в общем случае, записи. В процессе «зарождения» запись проходит фазу существования в оперативной памяти.

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

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

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

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

4. Основные операции над структурами данных

К основным операциям над структурами данных отно­сятся следующие операции:

• формирование;

• просмотр;

• вставка (включение);

• добавление (дополнение);

• извлечение;

• удаление (исключение);

• сдвиг;

• изменение содержимого элемента;

• сортировка.

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

Формирование  это создание в памяти компьютера структуры данных, соответствующей ее логическому пред­ставлению. При этом различают фазы:

1. первоначальное формирование (generation), когда создаются ячейки памяти для элементов структуры и отношений, и значения данных размещаются в порядке их поступления извне в этих ячейках, и

2. перегруппирования (regrouping), например, созда­ния древовидной структуры из записей, хранящихся в неко­торой таблице; на этапе перегруппирования может быть применена сортировка.

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

Вставка (insertion)  это ввод нового данного в струк­туру данных. При вставке указываются элементы, между которыми в логической структуре расположится новый элемент; эти элементы определяют точку вставки. Хотя на расположение точки вставки мо­гут быть наложены ограничения (например, включение в очередь возможно только со стороны «хвоста»), обыч­но, употребляя термин «вставка», подразумевают возмож­ность включения нового элемента в любое место исходной структуры. При вставке в массивах выполняется сдвиг некоторого количества элементов, чтобы ос­вободить место для вставляемого элемента. Вставка в ди­намические структуры такого сдвига не требует: просто изменяются адреса связей без физического перемещения данных в памяти.

Под добавлением (store) понимают вставку нового элемента в логический конец корректируемой структуры. В сущности, формирование структуры  это последова­тельность добавлений элементов данных.

Извлечение (extraction) выполняется с целью передачи содержимого элемента структуры для дальнейшего ис­пользования, например, для печати этого содержимого.

Удаление (deletion)  это исключение некоторого элемен­та из структуры данных. При удалении в массивах удаляе­мый элемент либо помечают как удаленный (такое удале­ние без физического уничтожения называется логическим удалением  logical deletion), либо осуществляют сдвиг некоторого количества элементов, при котором в ячейку с адресом удаляемого элемента заносится значение соседне­го сдвигаемого элемента. В динамических структурах про­сто изменяются адреса связей без физического перемеще­ния данных, а ячейка, в которой размещался удаляемый элемент, включается в список свободных ячеек, доступных для вставки.

Сдвиг (shift)  это перемещение некоторых элементов данных в одном из направлений: либо от логического нача­ла структуры к ее логическому концу, либо наоборот. При сдвиге сохраняется порядок следования сдвигаемых эле­ментов.

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

Сортировка (sorting)  это распределение элементов некоторого множества с целью их расположения в соответ­ствии с некоторыми правилами. Разновидностью сортиров­ки является упорядочение данных по возрастанию или убыванию значений некоторого признака или ключа сортировки. Часто сортировка выполняется как переупорядочение (reordering) ранее упорядоченной последовательности по другому признаку (полю). Сортировка массивов предпола­гает, что перестановки, приводящие элементы в порядок, должны выполняться «на том же месте». Сортировка ди­намической структуры предполагает изменение адресов связей.

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