Поиск в таблице
Для иллюстрации дальнейших аспектов использования структур в этом разделе мы напишем программу, представляющую собой содержимое пакета поиска в таблице. Эта программа является типичным представителем подпрограмм управления символьными таблицами макропроцессора или компилятора. Рассмотрим, например, оператор #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;
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.
