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

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

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

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

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

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

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

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

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

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

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

- просмотр;

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

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

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

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

- сдвиг;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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