Язык С




Поиск в таблице - часть 2


FOR (HASHVAL = 0; *S != '\0'; ) HASHVAL += *S++; RETURN(HASHVAL % HASHSIZE); \)

В результате процесса хеширования выдается начальный ин- декс в массиве HASHTAB ; если данная строка может быть где-то найдена, то именно в цепи блоков, начало которой ука- зано там. Поиск осуществляется функцией LOOKUP. Если функция LOOKUP находит, что данный элемент уже присутствует, то она возвращает указатель на него; если нет, то она возвращает NULL.

STRUCT NLIST *LOOKUP(S) /* LOOK FOR S IN HASHTAB */ CHAR *S; \( STRUCT NLIST *NP;

FOR (NP = HASHTAB[HASH(S)]; NP != NULL;NP=NP->NEXT) IF (STRCMP(S, NP->NAME) == 0) RETURN(NP); /* FOUND IT */ RETURN(NULL); /* NOT FOUND */

Функция INSTALL использует функцию LOOKUP для определе- ния, не присутствует ли уже вводимое в данный момент имя; если это так, то новое определение должно вытеснить старое. В противном случае создается совершенно новый элемент. Если по какой-либо причине для нового элемента больше нет места, то функция INSTALL возвращает NULL.

STRUCT NLIST *INSTALL(NAME, DEF) /* PUT (NAME, DEF) */ CHAR *NAME, *DEF; \( STRUCT NLIST *NP, *LOOKUP(); CHAR *STRSAVE(), *ALLOC(); INT HASHVAL;

IF((NP = LOOKUP(NAME)) == NULL) \( /* NOT FOUND */ NP = (STRUCT NLIST *) ALLOC(SIZEOF(*NP)); IF (NP == NULL) RETURN(NULL); IF ((NP->NAME = STRSAVE(NAME)) == NULL) RETURN(NULL); HASHVAL = HASH(NP->NAME); NP->NEXT = HASHTAB[HASHVAL]; HASHTAB[HASHVAL] = NP; \) ELSE /* ALREADY THERE */ FREE((NP->DEF);/* FREE PREVIOUS DEFINITION */ IF ((NP->DEF = STRSAVE(DEF)) == NULL) RETURN (NULL); RETURN(NP); \)

Функция STRSAVE просто копирует строку, указанную в ка- честве аргумента, в место хранения, полученное в результате обращения к функции ALLOC. Мы уже привели эту функцию в гла- ве 5. Так как обращение к функции ALLOC и FREE могут проис- ходить в любом порядке и в связи с проблемой выравнивания, простой вариант функции ALLOC из главы 5 нам больше не под- ходит; смотрите главы 7 и 8.

Упражнение 6-7

--------------- Напишите процедуру, которая будет удалять имя и опреде- ление из таблицы, управляемой функциями LOOKUP и INSTALL.

Упражнение 6-8

--------------- Разработайте простую, основанную на функциях этого раз- дела, версию процессора для обработки конструкций #DEFINE , пригодную для использования с "C"-программами. Вам могут также оказаться полезными функции GETCHAR и UNGETCH.




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