Таблица - символ
Cтраница 3
В этой программе таблица символов используется для поиска отдельных ключей в произвольно сгенерированной или считанной со стандартного ввода последовательности. Для каждого ключа операция search используется для проверки того, просматривался ли ключ раньше. Если ранее ключ не просматривался, функция вставляет элемент с этим ключом в таблицу символов. Типы ключей и элементов, а также абстрактные операции с ними определены в Item. [31]
В этой программе таблица символов используется для поиске отдельных кшочвй а произвольно а е мер и ре-санной или считанной со стандартного ввода послед оеатал ь-ности. Для каждого ключа операция кеягсП используется для проверки того, просматривался ли ключ раньше. Если ранее ключ не просматривался, функция вставляет элемент с этуц юючом в таблицу символов. [32]
После остановки программы таблица символов сбрасывается в файл листинга. [33]
В окне появляется таблица символов текущего шрифта. [34]
Реализация других функций таблиц символов с помощью списков пропусков не представляет сложности. [36]
В качестве реализации таблиц символов хеширование предпочтительней структур бинарных деревьев, рассмотренных в главах 12 и 13, поскольку оно несколько проще и может обеспечить оптимальное ( постоянное) время поиска, если ключи относятся к стандартному типу или достаточно просты, чтобы можно было быть уверенным в разработке хорошей хеш-функции для них. Когда эти факторы не имеют значения, безусловно следует выбирать хеширование, только с одной важной оговоркой: когда ключи представляют собой длинные строки, их можно встроить в структуры данных, которые могут обеспечить методы поиска, работающие еще быстрее хеширования. [37]
Чтобы разработать реализацию таблицы символов, в которой используются DST-деревья, мы изменили реализации операций search и insert в стандартном BST-де-реве ( см. программу 12.8), что должно быть заметно в этом примере операции search. Для принятия решения о том, следует ли выполнять перемещение влево или вправо, вместо сравнения полных ключей выполняется проверка единственного ( ведущего) разряда ключа. Рекурсивные вызовы функции имеют третий аргумент, позволяющий смещать вправо позицию проверяемого разряда при перемещении вниз по дереву. [38]
Определите интерфейс АТД таблицы символов, который ITO J во л нет клиентским программам улалятъ конкретные элементы с использованием л крип трон it изменять ключи ( см. радели А. [39]
Нас интересуют реализации таблиц символов, в которых используется небольшое количество зондирований. Мы будем избегать конкретных предположений касательно размеров страницы и отношения времени, требуемого для зондирования, ко времени, которое впоследствии потребуется для доступа к элементам внутри блока. Ожидается, что эти значения должны быть порядка 100 - 1000; большая точность не требуется, поскольку алгоритмы не особо чувствительны к этим значениям. [40]
В найденной позиции Таблицы Символов должен быть ряд связей ко всем относящимся к этому имени позициям в Таблице Данных. Далее, в каждой позиции Таблицы Данных нам потребуется связь с позицией для группового элемента, в который она входит. [41]
Инициализировать переменные в таблице символов. [42]
Реализуйте операцию remove для таблицы символов, основанной на применении В-дерева, при использовании простого метода, когда указанный элемент удаляется из внешней страницы ( возможно, допустив, чтобы количество элементов на странице становилось меньше М / 2), но чтобы изменение не распространялось вверх по дереву, за исключением, возможно, настройки значений ключей, если удаленный элемент оказался наименьшим на данной странице. [43]
Последняя операция с АТД таблиц символов, которую мы рассмотрим - операция join. В реализации с использованием BST-дерева это сводится к объединению двух деревьев. [44]
Одним из недостатков организации таблицы символов ХСОМ является то, что поиск символа в таблице представляет собой процесс порядка я. Другими словами, время ( или число сравнений), необходимое для нахождения символа, прямо пропорционально количеству символов в таблице, Когда ХСОМ осуществляет самокомпиляцию, в таблице символов насчитывается в среднем около 350 элементов и стоимость трансляции определяется временем, затраченным на обращение к таблице. [45]
Страницы: 1 2 3 4