У цьому розділі, ми напишемо осердя програми пошуку за таблицею, щоб проілюструвати додаткові риси структур. Цей код типовий для того, що можна знайти у функціях по обробці таблиці символів макро-процесору або компілятора. Наприклад, розглянемо твердження#define. Коли ми зустріли рядок на кшталт
#define IN 1
назва IN і її текст заміни 1 буде збережено в таблиці. Пізніше, коли IN з'явиться у виразі на зразок
state = IN;
її замістить 1.
Ми побачимо дві функції, по обробці назв і текстів заміни. install(s,t) реєструє в таблиці назву s і текст заміни t; s із t, це просто символьні ланцюжки. lookup(s) шукає s у таблиці, і повертає покажчик на місце, де його знайдено, або NULL, як такого ланцюжка там немає.
Використовується алгоритм гешованого пошуку — новоприбуле ім'я перетворено на невелике додатнє ціле, яке пізніше використовується як індекс масиву покажчиків. Елемент масиву вказує на початок суцільного списку блоків з описами назв, що відповідають цьому хеш-значенню.NULL означає, що жодне ім'я не відповідає вказаному значенню.
+-----+ +-----+ +-----+
| *--|---->| *--|----->| 0 |
+-----+ | *--|--> | *--|---> назва
| 0 | | *--|--> | *--|---> визначення
+-----+ +-----+ +-----+
| 0 |
+-----+ +-----+
| *--|---->| 0 |
+-----+ | *--|---> назва
| 0 | | *--|---> визначення
+-----+ +-----+
Блок являється списком всередині структури з покажчиками на назву, текст заміни та наступний блок у списку. Наступний нульовий покажчик позначає кінець списку.
struct nlist { /* запис таблиці: */
struct nlist *next; /* наступний запис в ланцюжку */
char *name; /* визначене ім'я */
char *defn; /* текст заміни */
};
Масив покажчиків, це просто
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* таблиця покажчиків */
Функція гешування, використовувана обома, lookup та install, додає кожне значення символу ланцюжка до зашифрованої комбінації попередніх, і повертає остаток поділу на розмір гешу. Це не найкраща з можливих функцій гешування, але вона коротка й ефективна.
/* hash: утворює геш-значення для ланцюжка s */
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
Беззнакова арифметика забезпечує додатнє геш-значення.
Процес гешування видасть початковий індекс для масиву hashtab; якщо ланцюжок існує, його можна буде знайти у списку блоків, які там беруть свій початок. Пошук здійснюється функцієюlookup. Якщо lookup знайде відповідний запис, вона поверне покажчик на нього; якщо ні —NULL.
/* lookup: шукає s у hashtab */
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np; /* знайдено */
return NULL; /* не знайдено */
}
Цикл for функції lookup є стандартною ідіомою проходження вздовж зв'язного списку:
for (ptr = head; ptr != NULL; ptr = ptr->next)
...
функція install використовує lookup, щоб визначити, чи назва, яка додається вже присутня; якщо так, то нове визначення витіснить старе. У протилежному випадку, буде створено новий запис. install поверне NULL, якщо з якоїсь причини не залишилося місця для нового запису.
struct nlist *lookup(char *);
char *strdup(char *);
/* install: додає (name, defn) до hashtab */
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) { /* not found */
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* already there */
free((void *) np->defn); /*free previous defn */
if ((np->defn = strdup(defn)) == NULL)
return NULL;
return np;
}
Вправа 6-5. Напишіть функцію undef, яка би видаляла назву та визначення з таблиці, утворюваної функціями lookup та install.
Вправа 6-6. Втільте просту версію (без аргументів) оброблювача визначень #define (який можна би було використовувати із C-програмами), основуючись на функціях із цього розділу. Вам можливо доведеться згадати функції getch і ungetch.
