Брайан Керниган - Язык программирования Си. Издание 3-е, исправленное

#include ‹stdlib.h›

/* talloc: создает tnode */

struct tnode *talloc(void) {

return (struct tnode *) malloc(sizeof(struct tnode));

}

Функция strdup просто копирует строку, указанную в аргументе, в место, полученное с помощью malloc :

char *strdup(char *s) /* делает дубликат s */

{

char *p;

p = (char *) malloc(strlen(s)+1); /* +1 для '\0' */

if (p != NULL)

strcpy(p, s);

return p;

}

Функция malloc возвращает NULL, если свободного пространства нет; strdup возвращает это же значение, оставляя заботу о выходе из ошибочной ситуации вызывающей программе.

Память, полученную с помощью malloc , можно освободить для повторного использования, обратившись к функции free (см. главы 7 и 8).

Упражнение 6.2. Напишите программу, которая читает текст Си-программы и печатает в алфавитном порядке все группы имен переменных, в которых совпадают первые 6 символов, но последующие в чем-то различаются. Не обрабатывайте внутренности закавыченных строк и комментариев. Число 6 сделайте параметром, задаваемым в командной строке.

Упражнение 6.3. Напишите программу печати таблицы "перекрестных ссылок", которая будет печатать все слова документа и указывать для каждого из них номера строк, где оно встретилось. Программа должна игнорировать "шумовые" слова, такие как "и", "или" и пр.

Упражнение 6.4. Напишите программу, которая печатает весь набор различных слов, образующих входной поток, в порядке возрастания частоты их встречаемости. Перед каждым словом должно быть указано число вхождений.

В этом параграфе, чтобы проиллюстрировать новые аспекты применения структур, мы напишем ядро пакета программ, осуществляющих вставку элементов в таблицы и их поиск внутри таблиц. Этот пакет - типичный набор программ, с помощью которых работают с таблицами имен в любом макропроцессоре или компиляторе. Рассмотрим, например, инструкцию #define. Когда встречается строка вида

#define IN 1

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

state = IN;

это должно быть заменено на 1.

Существуют две программы, манипулирующие с именами и замещающими их текстами. Это install(s,t) , которая записывает имя s и замещающий его текст t в таблицу, где s и t - строки, и lookup(s) , осуществляющая поиск s в таблице и возвращающая указатель на место, где имя s было найдено, или NULL, если s в таблице не оказалось.

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

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

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

/* lookup: ищет s */

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) в таблицу */

struct nlist *install(char *name, char *defn)

{

struct nlist *np;

unsigned hashval;

if ((np = lookup(name)) == NULL) {/* не найден */

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 /* уже имеется */

free((void *) np-›defn); /* освобождаем прежний defn */

if ((np-›defn = strdup(defn)) == NULL)

return NULL;

return np;

}

Упражнение 6.5. Напишите функцию undef , удаляющую имя и определение из таблицы, организация которой поддерживается функциями lookup и install .

Упражнение 6.6. Реализуйте простую версию #define -npoцeccopa (без аргументов), которая использовала бы программы этого параграфа и годилась бы для Си-программ. Вам могут помочь программы getch и ungetch .

Язык Си предоставляет средство, называемое typedef, которое позволяет давать типам данных новые имена. Например, объявление

typedef int Length;

делает имя Length синонимом int . С этого момента тип Length можно применять в объявлениях, в операторе приведения и т. д. точно так же, как тип int :

Length len, maxlen;

Length *lengths[];

Аналогично объявление

typedef char *String;

делает String синонимом char * , т. e. указателем на char , и правомерным будет, например, следующее его использование: