Язык программирования C

Скачать в pdf «Язык программирования C»


#define IN 1


Как только в тексте программы встречается такая директива, имя IN и его подстановка 1 записываются в таблицу. Позже, всякий раз, когда имя IN встретится в тексте, его следует заменить на 1, например: state = IN;


Всю работу с именами и текстами подстановки выполняют две функции. Первая, install (s, t), записывает имя s и текст подстановки t в таблицу; s и t — простые текстовые строки. Функция lookup (s) разыскивает строку s в таблице и возвращает указатель на место, в котором она ее нашла, или NULL, если не нашла.


Алгоритм основан на поиске в хэш-таблице: поступающее имя конвертируется в небольшое неотрицательное число, которое используется как индекс в массиве указателей. Каждый элемент массива указывает на начало связанного списка блоков, описывающих имена, которые соответствуют данному хэш-коду. Если какому-либо хэш-коду не соответствуют никакие имена, возвращается NULL.

Имя


Подстановка


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


struct nlist { /* запись таблицы: */


struct nlist *next; /* следующая запись в цепочке */


char *name;    /* имя в #define */


char *defn;    /* подставляемый текст */


};


Массив указателей объявляется просто:


#define HASHSIZE 101


static struct nlist *hashtab[HASHSIZE]; /* таблица указателей */ Хэш-функция, используемая функциями lookup и install, добавляет очередной символ из строки к замысловатой шифрованной комбинации предыдущих символов, после чего возвращает остаток от деления на размер массива. Это не самая лучшая хэш-функция из возможных, но зато она короткая и быстрая.

Скачать в pdf «Язык программирования C»