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

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

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

- просмотр;

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

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

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

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

- сдвиг;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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