Неупорядоченные таблицы

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

формулой

(2.7)

где i—порядковый номер записи, a p_i—вероятность того, что требуемая запись имеет номер i.

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

p_i =1/n

средняя длина поиска равна

(2.8)

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

Иногда в трансляторах в качестве временных таблиц применяют древовидные таблицы, организованные в виде двоичного дерева,которое в памяти машины отображается сетью. Каждая запись в такой таблице сопровождается двумя указателями: один указатель содержит адрес хранения записи с меньшим значением ключа, а другой — с большим. На рис. 2.13 левый указатель отвечает меньшему ключу, а правый — большему, причем предполагается, что запись занимает два машинных слова: первое занимает собственно запись, а второе — указатели. Нумерация машинных слов десятичная.

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

Древовидная таблица на рис. 2.13 заполнена для случая, когдазаписи имели следующие значения ключей (в порядке их поступления): 5, 3, 4, 7, 1 и 9. Поиск в древовидной таблице по заданному ключу происходит почти так же, как отыскание места, в которое записывается адрес хранения. Искомое значение ключа сравнивается со значением ключа первой записи. По результату сравнения с помощью указателей определяется направление дальнейшего пои-

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

Средняя длина поиска в древовидной таблице зависит от порядка поступления записей при заполнении таблицы. В худшем случае,когда записи поступали в порядке возрастания (или в порядке убывания) значений ключа, дерево будет иметь всего одну ветвь, и средняя длина поиска останется равной n/2, как в обычной неупорядоченной таблице. В лучшем случае, когда

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

D₂= entier (log₂n + 2). (2.9)

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