Язык С




Поиск в таблице


Для иллюстрации дальнейших аспектов использования струк- тур в этом разделе мы напишем программу, представляющую со- бой содержимое пакета поиска в таблице. Эта программа явля- ется типичным представителем подпрограмм управления символь- ными таблицами макропроцессора или компилятора. Рассмотрим, например, оператор #DEFINE языка "C". Когда встречается строка вида

#DEFINE YES 1

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

INWORD = YES;

Oно должно быть замещено на 1. Имеются две основные процедуры, которые управляют имена- ми и заменяющими их текстами. Функция INSTALL(S,T) записыва- ет имя S и заменяющий текст T в таблицу; здесь S и T просто символьные строки. Функция LOOKUP(S) ищет имя S в таблице и возвращает либо указатель того места, где это имя найдено, либо NULL, если этого имени в таблице не оказалось. При этом используется поиск по алгоритму хеширования - поступающее имя преобразуется в маленькое положительное чис- ло, которое затем используется для индексации массива указа- телей. Элемент массива указывает на начало цепочных блоков, описывающих имена, которые имеют это значение хеширования. Если никакие имена при хешировании не получают этого значе- ния, то элементом массива будет NULL. Блоком цепи является структура, содержащая указатели на соответствующее имя, на заменяющий текст и на следующий блок в цепи. Нулевой указатель следующего блока служит признаком конца данной цепи.

STRUCT NLIST \( /* BASIC TABLE ENTRY */ CHAR *NAME; CHAR *DEF; STRUCT NLIST *NEXT; /* NEXT ENTRY IN CHAIN */ \);

Массив указателей это просто

DEFINE HASHSIZE 100 TATIC STRUCT NLIST *HASHTAB[HASHSIZE] /* POINTER TABLE */

Значение функции хеширования, используемой обеими функ- циями LOOKUP и INSTALL , получается просто как остаток от деления суммы символьных значений строки на размер массива. (Это не самый лучший возможный алгоритм, но его достоинство состоит в исключительной простоте).

HASH(S) /* FORM HASH VALUE FOR STRING */ CHAR *S; \( INT HASHVAL;




Содержание  Назад  Вперед