Применение очереди

Очередь используется при передаче данных из оперативной во вторичную память (при этом происходит процедура буферизации: накапливается блок и передается во вторичную память). Наличие буфера обеспечивает независимость взаимодействия процессов между производителем и потребителем (ранжирование задач пользователя). Задачи разделяются по приоритетам: 1) задачи, решаемые в режиме реального времени (высший приоритет) (очередь 1); 2) задачи, решаемые в режиме разделения времени (очередь 2); задачи, решаемые в пакетном режиме (фоновые задачи) (очередь 3). Очереди выполняются последовательно.

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

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

Классификация СД типа таблица:

СД типа таблица
неупорядоченная таблица	упорядоченная таблица	хеш-таблица
как отображение на массив	как отображение на список

Если один элемент d _i , то кортеж – это <d ₁, d ₂, …, d _n>, причем D _Ti Î d _i. Множество значений элементов типа Т (множество допустимых значений СД типа таблица) будет определяться с помощью прямого декартова произведения:

D_T = D_T1 ´ D_T2 ´ … ´ D_Тn, причем D _Ti Î <d ₁, d ₂, …, d _n>.

Сам же элемент таблицы можно представить в виде двойки <K, V>, где К – ключ, а V – тело элемента. В качестве ключа может быть разное число полей, которые определяют этот элемент. Ключ используется для операции доступа к элементу, так как каждый из ключей уникален для данного элемента. Таким образом, таблица является совокупностью двоек <K, V>.

На логическом уровне элемент СД типа таблица описывается следующим образом:

Type Element = record

Key: integer;

{описание остальных полей}

end;

При реализации таблицы как отображения на массив ее описание выглядит так:

Tabl = array [0 .. N] of Element

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

Перед тем как определить операции, которые можно выполнять над таблицей рассмотрим классификацию операций:

1. Конструкторы – операции, которые создают объекты рассматриваемой структуры.

2. Деструкторы – операции, которые разрушают объекты рассматриваемой структуры. Признаком этой операции является освобождение памяти.

3. Модификаторы – операции, которые модифицируют соответствующие структуры объектов. К ним относятся динамические и полустатические модификаторы.

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

5. Итераторы – операторы доступа к содержимому объекта по частям в определенном порядке.

Операции над таблицей:

4. Операция инициализации (конструктор).

5. Операция включения элемента в таблицу (модификатор).

6. Операция исключения элемента из таблицы (модификатор).

7. Операции-предикаты:

A. таблица пуста / таблица не пуста (наблюдатель)

B. таблица переполнена / таблица не переполнена (наблюдатель).

8. Чтение элемента по ключу (наблюдатель).

СД типа хеш-таблица.

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