Реферат: Экономические информационные системы

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

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

Преимущества упорядоченных последовательных структур данных, в частности, хорошо видны на примере с операцией пересечения двух массивов, определяемой как выбор записей с ключевым признаком, значение которого есть и в первом и во втором массиве. Если исходные массивы длиною М записей каждый н е отсортированы по указанному признаку, то пересечение массивов потребует выполнения С=К М² сравнений пар признаков, где 0,5£К £1. Когда массивы отсортированы, С »2М .

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

Время сортировки данных, которые можно в известной мере считать и трудоемкостью формирования упорядоченной последовательной структуры, пропорционально числу сравнений пар признаков различных записей (С), в свою очередь зависящему от количества записей в массиве (М). Лучший по времени метод сортировки — метод слияния — характеризуется числом сравнений

С = М log₂ М

и временем сортировки

T = t ´ C = tM log₂ M,

где t— константа с размернос тью времени.

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

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

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

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

B	E	A	C	D
0100	0100	0140	0140	0220
0220	0140	0220	0240
0240

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

Затем основной массив просматривается второй раз от записи к записи. Во всех его записях проверяется наличие ключей, значения которых зафиксированы ранее в инвертированном массиве, и на этой основе заполняются адреса в группах. Именно поэтому в таблице группы не упорядочены по ключу. Последняя операция—сортировка групп по значениям ключа и уплотнение инвертированного массива.