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

Поисковым признаком может служить:

n номер записи;

n значения ключевого поля ( найти все записи для некоторых p_i=q, где p_i - ключ i - той записи, а q - значение поискового признака ).

Если задано только одно значение признака поиска, то такой поиск называется единичным, если задано несколько значений признака поиска, то это - групповой поиск.

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

Метод последовательного просмотра (сканирование)

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

При реализации данного метода необходимо различать дополнительные условия:

n массив не упорядочен и не известно число элементов, удовлетворяющих искомому признаку;

n массив не упорядочен, но известно число элементов, удовлетворяющих искомому признаку;

n массив упорядочен.

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

Если же массив упорядочен, то после того, как найдена нужная запись, поиск прекращается как только p > q.

Среднее число сравнений для реализации этого метода

С_ср =

где n - число записей  в массиве

Максимальное число сравнений С_мах = n

Метод дихотомического поиска

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

Пусть массив, длина которого известна, упорядочен по возрастанию и требуется найти элемент с минимальным номером, удовлетворяющий условию a_i =p.

Принципиальная блок-схема алгоритма реализации функции int select (float *a, int n, float p) приведена на рисунке.

Рис.

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

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

Корректировка данных обеспечивает их достоверность в требуемый момент времени и представляет собой процедуру внесения изменений в структуру данных. Различают следующую корректировку списка:

n вставка записей;

n удаление (исключение) записей;

n замена значений отдельных полей записей.

Список который, подвергается корректировке называется основным. Чтобы изменить значение всей записи необходимо задать её признак и определить её место местоположение.

Рассмотрим особенности коррекции списка, когда его структура хранения представит собой массив записей.

Как правило, основной массив упорядочен по какому-либо ключевому признаку, поэтому для реализации вставки требуется наличие свободных участков памяти определенной величины между записями массива для размещения вставленных записей. Это приводит к избыточности необходимого счета памяти и поскольку заранее не известны места (адреса) и величины свободных участков памяти, то реализация вставки невозможна без реорганизации массива. Для вставки новой записи в массив требуется сдвиг всех последующих записей. Если вставка записей производится случайно по отношению к их расположению в массиве, то в среднем на каждую вставку приходится сдвиг половины записей массива.

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

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

Организация корректировки списков может проводится различными способами в зависимости от требований систем обработки данных.

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

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

Основной массив

Исходное состояние                                                       Корректура

Р 1	Р 2	Р 3	Р 4			пр.	Р 1	Р 2	Р 3	Р 4
АА	0230	257	560			D	АА
АБ	0240	290	370			D	БА
БА	0280	420	500			V	ВА	0320	200	310
ДА	0340	500	370			Z	ДА	0345	456	505
ДА	0345	256	374

Результат

Р 1	Р2	Р3	Р4
АБ	0240	290	370
ВА	0320	200	310
ДА	0340	560	370
ДА	0346	456	505