Корректировка данных последовательной структуры

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

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

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

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

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

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

При объединении основного массива с массивом изменений выполняются следующие операции (алгоритм слияния):

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

• когда все записи одного из массивов будут перезаписаны полностью, оставшиеся записи другого массива добавляются в результирующий массив, и алгоритм заканчивается.

Дата добавления: 2015-07-16