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

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

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

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

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

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

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

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

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

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

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

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

Простейшим условием поиска является поиск по совпадению, т. е. равенство значения ключевого атрибута i-й записи p(i) и некоторого заранее заданного значения q. Алгоритмы всех разновидностей поиска можно получить из алгоритмов поиска по совпадению.

Базовым методом доступа к массиву является ступенчатый поиск. Этот метод предполагает упорядоченность обрабатываемых записей, причем безразлично, по возрастанию или по убыванию. Для определенности будем считать, что массив отсортирован по возрастанию значений ключевого атрибута p(i).

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

Рассмотрим двухступенчатый поиск в массиве, состоящем из М записей. Для заданного М выбирается константа H, называемая шагом поиска. Если необходимо отыскать запись со значением ключевого атрибута, равным q, производятся сле­дующие действия.

Значение q последовательно сравнивается с рядом величин р(1), p(l + H), p(l + 2∙H), ..., p(l + k∙H) до тех пор, пока будет впервые достигнуто неравенство p(l + m∙H) ≥ q. Здесь заканчивается первая ступень поиска. На второй ступени q после­довательно сравнивается со всеми ключами, которые имеют номер l + m∙H и больше, до тех пор, пока в процессе сравнений будет достигнут ключ, больший, чем q. Извлеченные при этом записи с ключом q образуют результат поиска.

Эффективность поиска измеряется количеством произведенных сравнений. Ступенчатый поиск имеет важный частный вариант – бинарный поиск. Для бинарного поиска вводятся левая граница интервала поиска А и правая граница В. Первоначально интервал охватывает весь массив, т. е. А = 0, В = М + 1. Вычисляется середина интервала i по формуле i = (A + B)/2 с округлением в меньшую сторону. Ключ i-й записи p(i) сравнивается с искомым значением q. Если p(i) = q, то поиск заканчивается. В случае p(i) > q записи с номерами i+1, i+2,..., М заведомо не содержат ключа q, и надо сократить интервал поиска, приняв B = i. Аналогично при p(i) < q надо взять A = i. Далее середина интервала вычисляется заново, и все действия повторяются. Если будет до­стигнут нулевой интервал, то требуемой записи в массиве нет.

Достаточно легко оценить максимальное число сравнений при поиске данных бинарным методом. Сокращение ин­тервала поиска на каждом шаге в худшем случае приведет к интервалу нулевой длины, что соответствует отсутствию в массиве искомого значения ключевого атрибута. После первого сравнения интервал поиска составит М/2 записей, после второго – М/4 и т. д. Когда интервал поиска впервые станет меньше 1, применяемая схема округления результата деления даст нулевой интервал и поиск закончится. Среднее число сравнений при бинарном поиске приблизительно составляет C = log(M) - 1. Можно утверждать, что при достаточно большом числе за­писей М бинарный метод поиска выполняется быстрее двух остальных.