Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Неупорядоченные таблицыСтр 1 из 4Следующая ⇒
В простейших неупорядоченных таблицах записи располагаются одна за другой без пропусков. Такие таблицы легко составлять. Новая запись просто добавляется к таблице. Для поиска применяется последовательный просмотр, при котором записи просматриваются подряд, начиная с первой. Средняя длина поиска при последовательном просмотре таблицы с n записями определяется формулой
(2.7) где i—порядковый номер записи, a pi—вероятность того, что требуемая запись имеет номер i.
Если искомая запись с равной вероятностью находится на любом месте таблицы, то pi =1/n средняя длина поиска равна
(2.8)
Неупорядоченные таблицы неэкономичны по времени поиска,поэтому в качестве постоянных таблиц транслятора их не используют. Однако на включение новой записи в таких таблицах расходуется минимальное время, поэтому неупорядоченные таблицы иногда применяют в трансляторах в качестве временных таблиц, заполняемых в ходе трансляции. Первые две позиции вектора, отображающего таблицу, часто используют для указания максимального допустимого номера записи и номера первой свободной строки таблицы.
Иногда в трансляторах в качестве временных таблиц применяют древовидные таблицы, организованные в виде двоичного дерева,которое в памяти машины отображается сетью. Каждая запись в такой таблице сопровождается двумя указателями: один указатель содержит адрес хранения записи с меньшим значением ключа, а другой — с большим. На рис. 2.13 левый указатель отвечает меньшему ключу, а правый — большему, причем предполагается, что запись занимает два машинных слова: первое занимает собственно запись, а второе — указатели. Нумерация машинных слов десятичная. Новые записи добавляются в таблицу подряд, как в простейших неупорядоченных таблицах. После добавления в таблицу новой записи значение ее ключа сравнивается со значением ключа первой табличной записи. По результату сравнения с помощью указателя определяется адрес хранения следующей записи, с ключом которой, нужно сравнивать значение ключа новой записи. Этот процесс продолжается до тех пор, пока не будет найдена запись с пустым указателем нужного направления просмотра. В этот указатель записывают адрес хранения новой записи. Древовидная таблица на рис. 2.13 заполнена для случая, когдазаписи имели следующие значения ключей (в порядке их поступления): 5, 3, 4, 7, 1 и 9. Поиск в древовидной таблице по заданному ключу происходит почти так же, как отыскание места, в которое записывается адрес хранения. Искомое значение ключа сравнивается со значением ключа первой записи. По результату сравнения с помощью указателей определяется направление дальнейшего пои- ска. Поиск прекращается либо при совпадении ключа очередной просматриваемой записи с искомым, либо при обнаружении пустого указателя. Последнее означает, что записи с требуемым значением ключа в таблице нет. Средняя длина поиска в древовидной таблице зависит от порядка поступления записей при заполнении таблицы. В худшем случае,когда записи поступали в порядке возрастания (или в порядке убывания) значений ключа, дерево будет иметь всего одну ветвь, и средняя длина поиска останется равной n/2, как в обычной неупорядоченной таблице. В лучшем случае, когда порядок поступления записей таков, что получается симметричное дерево, длина поиска уменьшится до
D2= entier (log2n + 2). (2.9) Недостатком древовидных таблиц является большой расход памяти, поскольку дополнительно приходится хранить указатели, и несколько более сложный алгоритм заполнения таблицы и поиска записей, чем в обычных неупорядоченных таблицах.
|