Упражнение 6-5
Напишите программу выдачи перекрестных ссылок, т.е. Программу, которая печатает
список всех слов документа и для каждого из этих слов печатает список номеров строк,
в кото- рые это слово входит.
Упражнение 6-6
Напишите программу, которая печатает слова из своего файла ввода, расположенные
в порядке убывания частоты их по- явления. Перед каждым словом напечатайте число
его появле- ний.
6.6. Поиск в таблице
Для иллюстрации дальнейших аспектов использования струк- тур в этом разделе мы
напишем программу, представляющую со- бой содержимое пакета поиска в таблице. Эта
программа явля- ется типичным представителем подпрограмм управления символь- ными
таблицами макропроцессора или компилятора. Рассмотрим, например, оператор #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.
6.7. Поля
Когда вопрос экономии памяти становится очень существен- ным, то может оказаться
необходимым помещать в одно машинное слово несколько различных объектов; одно из
особенно расп- росраненных употреблений - набор однобитовых признаков в применениях,
подобных символьным таблицам компилятора. внеш- не обусловленные форматы данных,
такие как интерфейсы аппа- ратных средств также зачастую предполагают возможность
полу- чения слова по частям.
Представьте себе фрагмент компилятора, который работает с символьной таблицей.
С каждым идентификатором программы связана определенная информация, например, является
он или нет ключевым словом, является ли он или нет внешним и/или статическим и т.д.
Самый компактный способ закодировать та- кую информацию - поместить набор однобитовых
признаков в от- дельную переменную типа CHAR или INT.
Обычный способ, которым это делается, состоит в опреде- лении набора "масок",
отвечающих соответствущим битовым по- зициям, как в
#DEFINE KEYWORD 01
#DEFINE EXTERNAL 02
#DEFINE STATIC 04
(числа должны быть степенями двойки). Тогда обработка битов сведется к "жонглированию
битами" с помощью операций сдвига, маскирования и дополнения, описанных нами в главе
2.
Некоторые часто встречающиеся идиомы:
FLAGS \!= EXTERNAL \! STATIC;
включает биты EXTERNAL и STATIC в FLAGS, в то время как
FLAGS &= \^(еXTERNAL \! STATIC);
их выключает, а
IF ((FLAGS & (EXTERNAL \! STATIC)) == 0) ...
истинно, если оба бита выключены.
Хотя этими идиомами легко овладеть, язык "C" в качестве альтернативы предлагает
возможность определения и обработки полей внутри слова непосредственно, а не посредством
побито- вых логических операций. Поле - это набор смежных битов внутри одной переменной
типа INT. Синтаксис определения и обработки полей основывается на структурах. Например,
сим- вольную таблицу конструкций #DEFINE, приведенную выше, можно бы было заменить
определением трех полей:
STRUCT \(
UNSIGNED IS_KEYWORD : 1;
UNSIGNED IS_EXTERN : 1;
UNSIGNED IS_STATIC : 1;
\) FLAGS;
Здесь определяется переменная с именем FLAGS, которая содер- жит три 1-битовых
поля. Следующее за двоеточием число задает ширину поля в битах. Поля описаны как
UNSIGNED, чтобы под- черкнуть, что они действительно будут величинами без знака.
На отдельные поля можно ссылаться, как FLAGS.IS_STATIE, FLAGS. IS_EXTERN, FLAGS.IS_KEYWORD
И т.д., то есть точно так же, как на другие члены структуры. Поля ведут себя подобно
небольшим целым без знака и могут участвовать в арифметичес- ких выражениях точно
так же, как и другие целые. Таким обра- зом, предыдущие примеры более естественно
переписать так:
FLAGS.IS_EXTERN = FLAGS.IS_STATIC = 1;
для включения битов;
FLAGS.IS_EXTERN = FLAGS.IS_STATIC = 0;
для выключения битов;
IF (FLAGS.IS_EXTERN == 0 &&FLAGS.IS_STATIC == 0)...
для их проверки.
Поле не может перекрывать границу INT; если указанная ширина такова, что это
должно случиться, то поле выравнива- ется по границе следующего INT. Полям можно
не присваивать имена; неименованные поля (только двоеточие и ширина) ис- пользуются
для заполнения свободного места. Чтобы вынудить выравнивание на границу следующего
INT, можно использовать специальную ширину 0.
При работе с полями имеется ряд моментов, на которые следует обратить внимание.
По-видимому наиболее существенным является то, что отражая природу различных аппаратных
сред- ств, распределение полей на некоторых машинах осуществляется слева направо,
а на некоторых справа налево. Это означает, что хотя поля очень полезны для работы
с внутренне опреде- ленными структурами данных, при разделении внешне определяе-
мых данных следует тщательно рассматривать вопрос о том, ка- кой конец поступает
первым.
Другие ограничения, которые следует иметь в виду: поля не имеют знака; они могут
храниться только в переменных типа INT (или, что эквивалентно, типа UNSIGNED); они
не являются массивами; они не имеют адресов, так что к ним не применима операция
&.
6.8. Объединения
Oбъединения - это переменная, которая в различные момен- ты времени может содержать
объекты разных типов и размеров, причем компилятор берет на себя отслеживание размера
и тре- бований выравнивания. Объединения представляют возможность работать с различными
видами данных в одной области памяти, не вводя в программу никакой машинно-зависимой
информации.
В качестве примера, снова из символьной таблицы компиля- тора, предположим, что
константы могут быть типа INT , FLOAT или быть указателями на символы. значение
каждой конкретной константы должно храниться в переменной соотвествующего ти- па,
но все же для управления таблицей самым удобным было бы, если это значение занимало
бы один и тот же объем памяти и хранилось в том же самом месте независимо от его
типа. это и является назначением объединения - выделить отдельную пере- менную,
в которой можно законно хранить любую одну из пере- менных нескольких типов. Как
и в случае полей, синтаксис ос- новывается на структурах.
UNION U_TAG \(
INT IVAL;
FLOAT FVAL;
CHAR *PVAL;
\) UVAL;
Переменная UVAL будет иметь достаточно большой размер,чтобы хранить наибольший
из трех типов, независимо от машины, на которой осуществляется компиляция, - программа
не будет за- висить от характеристик аппаратных средств. Любой из этих трех типов
может быть присвоен UVAR и затем использован в выражениях, пока такое использование
совместимо: извлекаемый тип должен совпадать с последним помещенным типом. Дело
программиста - следить за тем, какой тип хранится в объеди- нении в данный момент;
если что-либо хранится как один тип, а извлекается как другой, то результаты будут
зависеть от используемой машины.
Синтаксически доступ к членам объединения осуществляется следующим образом:
имя объединения.член
или
указатель объединения ->член
то есть точно так же, как и в случае структур. если для отс- леживания типа,
хранимого в данный момент в UVAL, использу- ется переменная UTYPE, то можно встретить
такой участок программы:
IF (UTYPE == INT)
PRINTF("%D\N", UVAL.IVAL);
ELSE IF (UTYPE == FLOAT)
PRINTF("%F\N", UVAL.FVAL);
ELSE IF (UTYPE == STRING)
PRINTF("%S\N", UVAL.PVAL);
ELSE
PRINTF("BAD TYPE %D IN UTYPE\N", UTYPE);
Объединения могут появляться внутри структур и массивов и наоборот. Запись для
обращения к члену объединения в структуре (или наоборот) совершенно идентична той,
которая используется во вложенных структурах. например, в массиве структур, определенным
следующим образом
STRUCT \(
CHAR *NAME;
INT FLAGS;
INT UTYPE;
UNION \(
INT IVAL;
FLOAT FVAL;
CHAR *PVAL;
\) UVAL;
\) SYMTAB[NSYM];
на переменную IVAL можно сослаться как
SYMTAB[I].UVAL.IVAL
а на первый символ строки PVAL как
*SYMTAB[I].UVAL.PVAL
В сущности объединение является структурой, в которой все члены имеют нулевое
смещение. Сама структура достаточно ве- лика, чтобы хранить "самый широкий" член,
и выравнивание пригодно для всех типов, входящих в объединение. Как и в случае структур,
единственными операциями, которые в настоя- щее время можно проводить с объединениями,
являются доступ к
члену и извлечение адреса; объединения не могут быть присво- ены, переданы функциям
или возвращены ими. указатели объеди- нений можно использовать в точно такой же
манере, как и ука- затели структур.
Программа распределения памяти, приводимая в главе 8 , показывает, как можно
использовать объединение, чтобы сде- лать некоторую переменную выровненной по определенному
виду границы памяти.
6.9. Определение типа
В языке "C" предусмотрена возможность, называемая TYPEDEF для введения новых
имен для типов данных. Например, описание
TYPEDEF INT LENGTH;
делает имя LENGTH синонимом для INT. "Тип" LENGTH может быть использован в описаниях,
переводов типов и т.д. Точно таким же образом, как и тип INT:
LENGTH LEN, MAXLEN;
LENGTH *LENGTHS[];
Аналогично описанию
TYPEDEF CHAR *STRING;
делает STRING синонимом для CHAR*, то есть для указателя на символы, что затем
можно использовать в описаниях вида
STRING P, LINEPTR[LINES], ALLOC();
Обратите внимание, что объявляемый в конструкции TYPEDEF тип появляется в позиции
имени переменной, а не сразу за словом TYPEDEF. Синтаксически конструкция TYPEDEF
подобна описаниям класса памяти EXTERN, STATIC и т. Д. мы также ис- пользовали прописные
буквы, чтобы яснее выделить имена.
В качестве более сложного примера мы используем конст- рукцию TYPEDEF для описания
узлов дерева, рассмотренных ра- нее в этой главе:
TYPEDEF STRUCT TNODE \( /* THE BASIC NODE */
CHAR *WORD; /* POINTS TO THE TEXT */
INT COUNT; /* NUMBER OF OCCURRENCES */
STRUCT TNODE *LEFT; /* LEFT CHILD */
