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



         

Поиск в таблице - часть 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.




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