Керниган и Ритчи - Язык программирования Си (793773), страница 35
Текст из файла (страница 35)
Каждый элемент этого массиваявляется указателем на начало связанного списка блоков, описывающих имена с данным хэш-кодом. Еслиэлемент массива равен NULL, это значит, что имен с соответствующим хэш-кодом нет.Блок в списке — это структура, содержащая указатели на имя, на замещающий текст и на следующий блок всписке; значение NULL в указателе на следующий блок означает конец списка.struct nlist { /* элемент таблицы */struct nlist *next; /* указатель на следующий элемент */char *name; /* определенное имя */char *defn; /* замещающий текст */};А вот как записывается определение массива указателей:#define HASHSIZE 101static 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-процессора (без аргументов), которая использовалабы программы этого параграфа и годилась бы для Си-программ. Вам могут помочь программы getch иungetch.6.7. Средство typedefЯзык Си предоставляет средство, называемое typedef, которое позволяет давать типам данных новыеимена. Например, объявлениеtypedef int Length;делает имя Length синонимом int. С этого момента тип Length можно применять в объявлениях, воператоре приведения и т. д.
точно так же, как тип int:Length len, maxlen;Length *lengths[];Аналогично объявлениеtypedef char *String;делает String синонимом char*, т. е. указателем на char, и правомерным будет, например, следующееего использование:String р, lineptr[MAXLINES], alloc(int);int strcmp(String, String);p = (String) malloc(100);Заметим, что объявляемый в typedef тип стоит на месте имени переменной в обычном объявлении, а несразу за словом typedef. С точки зрения синтаксиса слово typedef напоминает класс памяти — extern,static и т.
д. Имена типов записаны с заглавных букв для того, чтобы они выделялись.Для демонстрации более сложных примеров применения typedef воспользуемся этим средством призадании узлов деревьев, с которыми мы уже встречались в данной главе.typedef struct tnode *Treeptr;typedef struct tnode { /* узел дерева: */char *word; /* указатель на текст */int count; /* число вхождений */Treeptr left; /* левый сын */Treeptr right; /* правый сын */} Treenode;В результате создаются два новых названия типов: Treenode (структура) и Treeptr (указатель наструктуру).
Теперь программу talloc можно записать в следующем виде:Treeptr talloc(void){return (Treeptr) malloc(sizeof (Treenode));}Следует подчеркнуть, что объявление typedef не создает объявления нового типа, оно лишь сообщаетновое имя уже существующему типу. Никакого нового смысла эти новые имена не несут, они объявляютпеременные в точности с теми же свойствами, как если бы те были объявлены напрямую безпереименования типа. Фактически typedef аналогичен #define с тем лишь отличием, что приинтерпретации компилятором он может справиться с такой текстовой подстановкой, которая не может бытьобработана препроцессором. Напримерtypedef int (*PFI)(char *, char *);создает тип PFI — "указатель на функцию (двух аргументов типа char *), возвращающую int", который,например, в программе сортировки, описанной в главе 5, можно использовать в таком контексте:PFI strcmp, numcmp;Помимо просто эстетических соображений, для применения typedef существуют две важные причины.Первая — параметризация программы, связанная с проблемой переносимости.
Если с помощью typedefобъявить типы данных, которые, возможно, являются машинно-зависимыми, то при переносе программы надругую машину потребуется внести изменения только в определения typedef. Одна из распространенныхситуаций —использование typedef-имен для варьирования целыми величинами. Для каждой конкретноймашины это предполагает соответствующие установки short, int или long, которые делаются аналогичноустановкам стандартных типов, например size_t и ptrdiff_t.Вторая причина, побуждающая к применению typedef, — желание сделать более ясным текст программы.Тип, названный Treeptr (от английских слов tree — дерево и pointer — указатель), более понятен, чем тотже тип, записанный как указатель на некоторую сложную структуру.6.8.
ОбъединенияОбъединение — это переменная, которая может содержать (в разные моменты времени) объекты различныхтипов и размеров. Все требования относительно размеров и выравнивания выполняет компилятор.Объединения позволяют хранить разнородные данные в одной и той же области памяти без включения впрограмму машинно-зависимой информации. Эти средства аналогичны вариантным записям в Паскале.Примером использования объединений мог бы послужить сам компилятор, заведующий таблицей символов,если предположить, что константа может иметь тип int, float или являться указателем на символ и иметьтип char *.
Значение каждой конкретной константы должно храниться в переменной соответствующегоэтой константе типа. Работать с таблицей символов всегда удобнее, если значения занимают одинаковую пообъему память и запоминаются в одном и том же месте независимо от своего типа. Цель введения впрограмму объединения — иметь переменную, которая бы на законных основаниях хранила в себе значениянескольких типов.
Синтаксис объединений аналогичен синтаксису структур. Приведем пример объединения.union u_tag {int ival;float fval;char *sval;} u;Переменная u будет достаточно большой, чтобы в ней поместилась любая переменная из указанных трехтипов; точный ее размер зависит от реализации. Значение одного из этих трех типов может быть присвоенопеременной и и далее использовано в выражениях, если это правомерно, т. е. если тип взятого ею значениясовпадает с типом последнего присвоенного ей значения. Выполнение этого требования в каждый текущиймомент — целиком на совести программиста. В том случае, если нечто запомнено как значение одного типа,а извлекается как значение другого типа, результат зависит от реализации.Синтаксис доступа к элементам объединения следующий:имя-объединения.элементилиуказатель-на-объединение->элементт. е.
в точности такой, как в структурах. Если для хранения типа текущего значения и использовать, скажем,переменную utype, то можно написать такой фрагмент программы:if (utype == INT)printf("%d\n", u.ival);else if (utype == FLOAT)printf("%f\n", u.fval);else if (utype == STRING)printf("%s\n", u.sval);elseprintf ("неверный тип %d в utype\n", utype);Объединения могут входить в структуры и массивы, и наоборот. Запись доступа к элементу объединения,находящегося в структуре (как и структуры, находящейся в объединении), такая же, как и для вложенныхструктур.
Например, в массиве структурstruct {char *name;int flags;int utype;union {int ival;float fval;char *sval;} u;} symtab[NSYM];к ival обращаются следующим образом:symtab[i].u.ivalа к первому символу строки sval можно обратиться любым из следующих двух способов:*symtab[i].u.svalsymtab[i].u.sval[0]Фактически объединение — это структура, все элементы которой имеют нулевое смещение относительно еебазового адреса и размер которой позволяет поместиться в ней самому большому ее элементу, авыравнивание этой структуры удовлетворяет всем типам объединения.
Операции, применимые к структурам,годятся и для объединений, т. е. законны присваивание объединения и копирование его как единого целого,взятие адреса от объединения и доступ к отдельным его элементам.Инициализировать объединение можно только значением, имеющим тип его первого элемента; такимобразом, упомянутую выше переменную u можно инициализировать лишь значением типа int.В главе 8 (на примере программы, заведующей выделением памяти) мы покажем, как, применяяобъединение, можно добиться, чтобы расположение переменной было выровнено по соответствующейгранице в памяти.6.9. Битовые поляПри дефиците памяти может возникнуть необходимость запаковать несколько объектов в одно словомашины.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
