<<
>>

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

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

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

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

Tk=logM+ML, где L - длина одной записи массива.

В формуле для Тк второе слагаемое по величине всегда значительно превыщает первое, поэтому можно считать:

Тк-М L.

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

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

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

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

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

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

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

Цепная (списковая) организация данных

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

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

В списке выделяется собственная информация (записи с содержательными сведениями) и ассоциативная информация, т. е, все адреса связи.

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

Определение адресов связи как начальных адресов записей:

type ref=Anode;

node=record

key: integer; {ключевой атрибут записи} other: string[30]; (остальные атрибуты} next: ref (адрес связи}

end; 2.

Определение адресов связи как номеров записей:

const М=12;

type

node=record

key: integer; {ключевой атрибут записи} other: string(30]; {остальные атрибуты} next: integer {адрес связи}

end;

var t:array[l..M] of node;

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

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

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

вдач

Указатель списка г

Записи

Рис. 3.3. Варианты списковой организации данных: а - совместное хранение записей и адресов связи;

б - раздельное хранение записей и адресов связи (0 - конец списка)

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

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

При формировании упорядоченного списка записей возможны два варианта: •

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

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

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

В итоге время формирования упорядоченного списка пропорционально T~MlogM.

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

Для поиска данных в однонаправленном списке используется единственный метод - последовательный поиск.

Ключевой атрибут первой записи (ее адрес извлекается из указателя списка) сравнивается с искомым значением q, затем такое же сравнение выполняется для ключа второй записи, которая извлекается по адресу связи первой записи, и т. д. Время поиска, естественно, пропорционально Т~М.

Неэффективность бинарного поиска для списковой организации данных объясняется тем обстоятельством, что для достижения середины интервала требуется последовательное движение в соответствии с адресами связи и суммарное количество переходов от записи к записи достаточно велико. Число переходов от записи к записи прн доступе к серединам интервалов представляется величиной М/2+М/4+М/8+..., что практически составляет М.

Для ускорения доступа к списку могут быть рекомендованы такие варианты использования адресов связи, как двунаправленный н кольцевой список (рис. 3.4):

Указатель

двунаправленный список образован двумя цепочками адресов связи - от первой записи к последней и от последней записи к первой;

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

Цепной каталог

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

Рассмотрим пример цепного каталога, в котором адреса связи представлены номерами соответствующих записей. Описание каталога на языке Паскаль имеет вид: const М=9; type

node=record

key: integer; {ключевой атрибут записи}

next: integer {адрес связи}

end;

vat t.array[l..M] of node;

Первоначальное состояние каталога показано на рис. 3.5,а.

Включение и исключение записей в цепном каталоге предполагает поиск местоположения включаемой (исключаемой) запнсн и замену значений адресов связи для установления новой последовательности записей основного списка н списка свободной памяти. NEXT US=6 SO 5 20 8 7 40 1 60 9 10 2 0 зо 4 70 0 До вставки записи KEY NEXT SO 5 2 20 8 3 7 4 40 1 б 60 9 6 10 2 7 0 8 ЗО 4 9 70 0 US=6 USP=3

До удаления записи

KEY NEXT 50 5 2 20 4 3 7 4 40 1 60 9 10 2 7 0 8 30 3 9 70 0 Ряс.

3.5. Операции корректировки в цепном каталоге: а - ставка записи с ключом 61; б - удаление залиси с ключом 30

Алгоритм вставки записи с ключом F в иепнон каталог. 1.

Найти в каталоге запись с ключом непосредственно меньше, чем F (предшествующая запись). 2.

Поместить запись с ключом F в первую позицию свободной памяти. 3.

Заменить указатель свободной памяти (УСП) на адрес связи новой записи, этот адрес - на адрес связи предшествующей записи, а последний - на первоначальное значение УСП.

На рнс. 3.5,а вставляется запись с ключом F=6I. Указатель дерева ГТТЛ ГШ

0~j І І 0 І 0 1 0 І і

. . . ,1

0~| j І 0 [ 0 [ 0 j

I g I g I g і гл

ГҐ 1 Ч Рис. З.б. Пример древовидной организации данных (а) и представление его в памяти ЭВМ (б)

Алгоритм удаления записи с ключом W из каталога. 1.

Найти в каталоге запись с ключом непосредственно меньше, чем W (предшествующая запись). 2.

Заменить УСП на адрес связи предшествующей записи, этот адрес - на адрес связи исключаемой записи, а последний - на первоначальное значение УСП.

На рис. 3.5,6 удаляется запись с ключом W=30.

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

<< | >>
Источник: Мишенин А. И.. Теория экономических информационных систем: Учебник. - 4-е изд., доп. и перераб. - М.: Финансы и статистика. - 240 с. 2002

Еще по теме Корректировка последовательного массива:

  1. 1.3 КЛАССИФИКАЦИЯ И ОСНОВНЫЕ СВОЙСТВА ЕДИНИЦ ИНФОРМАЦИИ
  2. 3.1 АНАЛИЗ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
  3. Критерии эффективности алгоритмов
  4. Корректировка последовательного массива
  5. Списки
  6. 3.3 ОРГАНИЗАЦИЯ ДАННЫХ ВО ВНЕШНЕЙ ПАМЯТИ ЭВМ
  7. Оптимальное вторичное индексирование
  8. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
  9. 2.3. СОВРЕМЕННОЕ СОСТОЯНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДРУГИХ ВИДОВ ЭКОНОМИЧЕСКОГО АНАЛИЗА
  10. 1.5. Задачи, решаемые в системах оперативно-календарного планирования современного производства