нкции сравнениЯ и перестановки,
мы можем организовать сортировку по различным критериЯм.
€менно такой подход используетсЯ в нашей новой программе
сортировки.
    Љак и прежде, лексикографическое сравнение двух строк
осуществлЯетсЯ функцией STRCMP, а перестановка функцией
SWAP; нам нужна еще функциЯ NUMCMP, сравнивающаЯ две строки
на основе численного значениЯ и возвращающаЯ условное указа-
ние того же вида, что и STRCMP. ќти три функции описываютсЯ
в MAIN и указатели на них передаютсЯ в SORT. ‚ свою очередь
функциЯ SORT обращаетсЯ к этим функциЯм через их указатели.
мы урезали обработку ошибок в аргументах с тем, чтобы сосре-
доточитьсЯ на главных вопросах.


 #DEFINE LINES 100 /* MAX NUMBER OF LINES
        TO BE SORTED */

 MAIN(ARGC, ARGV) /* SORT INPUT LINES */
 INT ARGC;
 CHAR *ARGV[];
 \(
  CHAR *LINEPTR[LINES]; /* POINTERS TO TEXT LINES */
  INT NLINES; /* NUMBER OF INPUT LINES READ */
  INT STRCMP(), NUMCMP(); /* COMPARSION FUNCTIONS */
  INT SWAP(); /* EXCHANGE FUNCTION */
  INT NUMERIC = 0; /* 1 IF NUMERIC SORT */

  IF(ARGC>1 && ARGV[1][0] == '-' && ARGV[1][1]=='N')
     NUMERIC = 1;
  IF(NLINES = READLINES(LINEPTR, LINES)) >= 0) \(
     IF (NUMERIC)
           SORT(LINEPTR, NLINES, NUMCMP, SWAP);
     ELSE
           SORT(LINEPTR, NLINES, STRCMP, SWAP);
     WRITELINES(LINEPTR, NLINES);
  \) ELSE
     PRINTF("INPUT TOO BIG TO SORT\N");
 \)


‡десь STRCMP, NIMCMP и SWAP - адреса функций; так как извес-
тно, что это функции, операциЯ & здесь не нужна совершенно
аналогично тому, как она не нужна и перед именем массива.
Џередача адресов функций организуетсЯ компилЯтором.
    ‚торой шаг состоит в модификации SORT:

 SORT(V, N, COMP, EXCH) /* SORT STRINGS V[0] ... V[N-1] */
 CHAR *V[];           /* INTO INCREASING ORDER */
 INT N;
 INT (*COMP)(), (*EXCH)();
 \(
  INT GAP, I, J;

  FOR(GAP = N/2; GAP > 0; GAP /= 2)
      FOR(I = GAP; I &lt; N; I++)
     FOR(J = I-GAP; J >= 0; J -= GAP) \(
         IF((*COMP)(V[J], V[J+GAP]) &lt;= 0)
             BREAK;
         (*EXCH)(&V[J], &V[J+GAP]);
     \)
 \)


    ‡десь следует обратить определенное внимание на описа-
ниЯ. Ћписание

 INT (*COMP)()

говорит, что COMP ЯвлЯетсЯ указателем на функцию, котораЯ
возвращает значение типа INT. Џервые круглые скобки здесь
необходимы; без них описание

 INT *COMP()

говорило бы, что COMP ЯвлЯетсЯ функцией, возвращающей указа-
тель на целые, что, конечно, совершенно другаЯ вещь.
    €спользование COMP в строке

 IF (*COMP)(V[J], V[J+GAP]) &lt;= 0)

полностью согласуетсЯ с описанием: COMP - указатель на функ-
цию, *COMP - сама функциЯ, а

  (*COMP)(V[J], V[J+GAP])

- обращение к ней. Љруглые скобки необходимы длЯ правильного
объединениЯ компонентов.
    Њы уже приводили функцию STRCMP, сравнивающую две строки
по первому численному значению:

NUMCMP(S1, S2) /* COMPARE S1 AND S2 NUMERICALLY */
CHAR *S1, *S2;
\(
 DOUBLE ATOF(), V1, V2;

 V1 = ATOF(S1);
 V2 = ATOF(S2);
 IF(V1 &lt; V2)
    RETURN(-1);
 ELSE IF(V1 > V2)
    RETURN(1);
 ELSE
    RETURN (0);
\)


    ‡аключительный шаг состоит в добавлении функции SWAP,
переставлЯющей два указателЯ. ќто легко сделать, непосредст-
венно используЯ то, что мы изложили ранее в этой главе.


SWAP(PX, PY) /* INTERCHANGE *PX AND *PY */
CHAR *PX[], *PY[];
\(
 CHAR *TEMP;

 TEMP = *PX;
 *PX = *PY;
 *PY = TEMP;
\)
    €меетсЯ множество других необЯзЯтельных аргументов, ко-
торые могут быть включены в программу сортировки: некоторые
из них составлЯют интересные упражнениЯ.

    “пражнение 5-11
    ---------------
    Њодифицируйте SORT таким образом, чтобы она работала с
меткой -R, указывающей на сортировку в обратном (убывающем)
порЯдке. Љонечно, -R должна работать с -N.

    “пражнение 5-12
    ---------------
    „обавьте необЯзательный аргумент -F, объединЯющий вместе
прописные и строчные буквы, так чтобы различие регистров не
учитывалось во времЯ сортировки: данные из верхнего и нижне-
го регистров сортируютсЯ вместе, так что буква 'а' прописное
и 'а' строчное оказываютсЯ соседними , а не разделенными це-
лым алфавитом.

    “пражнение 5-13
    ---------------
    „обавьте необЯзательный аргумент -D ("словарное упорЯдо-
чивание"), при наличии которого сравниваютсЯ только буквы,
числа и пробелы. Џозаботьтесь о том, чтобы эта функциЯ рабо-
тала и вместе с -F.

    “пражнение 5-14
    ---------------
    „обавьте возможность обработки полей, так чтобы можно
было сортировать полЯ внутри строк. Љаждое поле должно сор-
тироватьсЯ в соответствии с независимым набором необЯзатель-
ных аргументов. (предметный указатель этой книги сортировал-
сЯ с помощью аргументов -DF длЯ категории указателЯ и с -N
длЯ номеров страниц).


         * 6. ‘труктуры * 


    ‘труктура - это набор из одной или более переменных,
возможно различных типов, сгруппированных под одним именем
длЯ удобства обработки. (‚ некоторых Языках, самый известный
из которых паскаль, структуры называютсЯ "записЯми").
    ’радиционным примером структуры ЯвлЯетсЯ учетнаЯ карточ-
ка работающего: "служащий" описываетсЯ набором атрибутов та-
ких, как фамилиЯ, имЯ, отчество (ф.и.о.), адрес, код соци-
ального обеспечениЯ, зарплата и т.д. Ќекоторые из этих атри-
бутов сами могут оказатьсЯ структурами: ф.и.о. €меет нес-
колько компонент, как и адрес, и даже зарплата.
    ‘труктуры оказываютсЯ полезными при организации сложных
данных особенно в больших программах, поскольку во многих
ситуациЯх они позволЯют сгруппировать свЯзанные данные таким
образом, что с ними можно обращатьсЯ, как с одним целым, а
не как с отдельными объектами. ‚ этой главе мы постараемсЯ
продемонстрировать то, как используютсЯ структуры. Џрограм-
мы, которые мы длЯ этого будем использовать, больше, чем
многие другие в этой книге, но все же достаточно умеренных
размеров.


        6.1. Ћсновные сведениЯ

    „авайте снова обратимсЯ к процедурам преобразованиЯ даты
из главы 5. „ата состоит из нескольких частей таких, как
день, месЯц, и год, и, возможно, день года и имЯ месЯца. ќти
пЯть переменных можно объеденить в одну структуру вида:

 STRUCT DATE \(
 INT  DAY;
 INT  MONTH;
 INT  YEAR;
 INT  YEARDAY;
 CHAR MON_NAME[4];
 \);

    Ћписание структуры, состоЯщее из заключенного в фигурные
скобки списка описаний, начинаетсЯ с ключевого слова STRUCT.
‡а словом STRUCT может следовать необЯзательное имЯ, называ-
емое Ярлыком структуры (здесь это DATе). ’акой Ярлык именует
структуры этого вида и может использоватьсЯ в дальнейшем как
сокращеннаЯ запись подробного описаниЯ.
    ќлементы или переменные, упомЯнутые в структуре, называ-
ютсЯ членами. џрлыки и члены структур могут иметь такие же
имена, что и обычные переменные (т.е. Ќе ЯвлЯющиесЯ членами
структур), поскольку их имена всегда можно различить по кон-
тексту. Љонечно, обычно одинаковые имена присваивают только
тесно свЯзанным объектам.


    ’очно так же, как в случае любого другого базисного ти-
па, за правой фигурной скобкой, закрывающей список членов,
может следовать список переменных.
Ћператор

   STRUCT   \( ...\) X,Y,Z;

синтаксически аналогичен

   INT X,Y,Z;

в том смысле, что каждый из операторов описывает X , Y и Z в
качестве переменных соотвествующих типов и приводит к выде-
лению длЯ них памЯти.
    Ћписание структуры, за которым не следует списка пере-
менных, не приводит к выделению какой-либо памЯти; оно толь-
ко определЯет шаблон или форму структуры. Ћднако, если такое
описание снабжено Ярлыком, то этот Ярлык может быть исполь-
зован позднее при определении фактических экземплЯров струк-
тур. Ќапример, если дано приведенное выше описание DATE, то

   STRUCT  DATE D;

определЯет переменную D в качестве структуры типа DATE.
‚нешнюю или статическую структуру можно инициализировать,
поместив вслед за ее определением список инициализаторов длЯ
ее компонент:

 STRUCT DATE D=\( 4, 7, 1776, 186, "JUL"\);

    —лен определенной структуры может быть указан в выраже-
нии с помощью конструкции вида

  имЯ структуры . —лен
  --------------------
ЋперациЯ указаниЯ члена структуры "." свЯзывает имЯ структу-
ры и имЯ члена. ‚ качестве примера определим LEAP (признак
високосности года) на основе даты, находЯщейсЯ в структуре
D,

LEAP = D.YEAR % 4 == 0 && D.YEAR % 100 != 0
   \!\! D.YEAR % 400 == 0;

или проверим имЯ месЯца

 IF (STRCMP(D.MON_NAME, "AUG") == 0) ...

€ли преобразуем первый символ имени месЯца так, чтобы оно
начиналось со строчной буквы

 D.MON_NAME[0] = LOWER(D.MON_NAME[0]);


    ‘труктуры могут быть вложенными; учетнаЯ карточка служа-
щего может фактически выглЯдеть так:

 STRUCT  PERSON  \(
    CHAR NAME[NAMESIZE];
    CHAR ADDRESS[ADRSIZE];
    LONG ZIPCODE;   /* почтовый индекс */
    LONG SS_NUMBER; /* код соц. ЋбеспечениЯ */
    DOUBLE SALARY;  /* зарплата */
    STRUCT DATE BIRTHDATE; /* дата рождениЯ */
    STRUCT DATE HIREDATE; /* дата поступлениЯ
     на работу */
 \);


‘труктура PERSON содержит две структуры типа DATE . …сли мы
определим EMP как

 STRUCT PERSON EMP;

то

 EMP.BIRTHDATE.MONTH

будет ссылатьсЯ на месЯц рождениЯ. ЋперациЯ указаниЯ члена
структуры "." ассоциируетсЯ слева направо.


        6.2. ‘труктуры и функции

    ‚ Языке "C" существует рЯд ограничений на использование
структур. ЋбЯзательные правила заключаютсЯ в том, что единс-
твенные операции, которые вы можете проводить со структура-
ми, состоЯт в определении ее адреса с помощью операции & и
доступе к одному из ее членов. ќто влечет за собой то, что
структуры нельзЯ присваивать или копировать как целое, и что
они не могут быть переданы функциЯм или возвращены ими. (‚
последующих версиЯх эти ограничениЯ будут снЯты). Ќа указа-
тели структур эти ограничениЯ однако не накладываютсЯ, так
что структуры и функции все же могут с удобством работать
совместно. € наконец, автоматические структуры, как и авто-
матические массивы, не могут быть инициализированы; инициа-
лизациЯ возможна только в случае внешних или статических
структур.
    „авайте разберем некоторые из этих вопросов, переписав с
этой целью функции перобразованиЯ даты из предыдущей главы
так, чтобы они использовали структуры. ’ак как правила зап-
рещают непосредственную передачу структуры функции, то мы
должны либо передавать отдельно компоненты, либо передать
указатель всей структуры. ЏерваЯ возможность демонстрируетсЯ
на примере функции DAY_OF_YEAR, как мы ее написали в главе
5:

 D.YEARDAY = DAY_OF_YEAR(D.YEAR, D.MONTH, D.DAY);


другой способ состоит в передаче указателЯ. если мы опишем
HIREDATE как

 STRUCT  DATE HIREDATE;

и перепишем DAY_OF_YEAR нужным образом, мы сможем тогда на-
писать

 HIREDATE YEARDAY = DAY_OF_YEAR(&HIREDATE);

передаваЯ указатель на HIREDATE функции DAY_OF_YEAR . ”унк-
циЯ должна быть модифицирована, потому что ее аргумент те-
перь ЯвлЯетсЯ указателем, а не списком переменных.

   DAY_OF_YEAR(PD) /* SET DAY OF YEAR FROM MONTH, DAY */
   STRUCT DATE *PD;
   \(
INT I, DAY, LEAP;

DAY = PD->DAY;
LEAP = PD->YEAR % 4 == 0 && PD->YEAR % 100 != 0
   \!\! PD->YEAR % 400 == 0;
FOR (I =1;  I &lt; PD->MONTH; I++)
   DAY += DAY_TAB[LEAP][I];
RETURN(DAY);
    \)


Ћписание

STRUCT DATE *PD;

говорит, что PD ЯвлЯетсЯ указателем структуры типа DATE.
‡апись, показаннаЯ на примере

PD->YEAR

ЯвлЯетсЯ новой. …сли P - указатель на структуру, то
               P-> член структуры
               ------------------
обращаетсЯ к конкретному члену. (ЋперациЯ -> - это знак ми-
нус, за которым следует знак ">".)
    ’ак как PD указывает на структуру, то к члену YEAR можно
обратитьсЯ и следующим образом

 (*PD).YEAR

но указатели структур используютсЯ настолько часто, что за-
пись -> оказываетсЯ удобным сокращением. Љруглые скобки в
(*PD).YEAR необходимы, потому что операциЯ указаниЯ члена


стуктуры старше , чем * . Ћбе операции, "->" и ".", ассоции-
руютсЯ слева направо, так что конструкции слева и справа
зквивалентны

 P->Q->MEMB    (P->Q)->MEMB
 EMP.BIRTHDATE.MONTH    (EMP.BIRTHDATE).MONTH

„лЯ полноты ниже приводитсЯ другаЯ функциЯ, MONTH_DAY, пере-
писаннаЯ с использованием структур.

   MONTH_DAY(PD) /* SET MONTH AND DAY FROM DAY OF YEAR */
   STRUCT DATE *PD;
   \(
 INT I, LEAP;

 LEAP = PD->YEAR % 4 == 0 && PD->YEAR % 100 != 0
    \!\! PD->YEAR % 400 == 0;
 PD->DAY = PD->YEARDAY;
 FOR (I = 1; PD->DAY > DAY_TAB[LEAP][I]; I++)
    PD->DAY -= DAY_TAB[LEAP][I];
 PD->MONTH = I;
    \)

    Ћперации работы со структурами "->" и "." нарЯду со ()
длЯ списка аргументов и [] длЯ индексов находЯтсЯ на самом
верху иерархии страшинства операций и, следовательно, свЯзы-
ваютсЯ очень крепко. …сли, например, имеетсЯ описание

 STRUCT \(
    INT X;
    INT *Y;
 \) *P;

то выражение

 ++P->X

увеличивает х, а не р, так как оно эквивалентно выражению
++(P->х). „лЯ изменениЯ порЯдка выполнениЯ операций можно
использовать круглые скобки: (++P)->х увеличивает P до дос-
тупа к х, а (P++)->X увеличивает P после. (круглые скобки в
последнем случае необЯзательны. Џочему ?)
    ‘овершенно аналогично *P->Y извлекает то, на что указы-
вает Y; *P->Y++ увеличивает Y после обработки того, на что
он указывает (точно так же, как и *S++); (*P->Y)++ увеличи-
вает то, на что указывает Y; *P++->Y увеличивает P после вы-
борки того, на что указывает Y.


        6.3. Њассивы сруктур

    ‘труктуры особенно подходЯт длЯ управлениЯ массивами
свЯзанных переменных. ђассмотрим, например, программу подс-
чета числа вхождений каждого ключевого слова Языка "C". Ќам
нужен массив символьных строк длЯ хранениЯ имен и массив це-
лых длЯ подсчета. одна из возможностей состоит в использова-
нии двух параллельных массивов KEYWORD и KEYCOUNT:

CHAR *KEYWORD [NKEYS];
INT  KEYCOUNT [NKEYS];

Ќо сам факт, что массивы параллельны, указывает на возмож-
ность другой организации. Љаждое ключевое слово здесь по су-
ществу ЯвлЯетсЯ парой:

CHAR *KEYWORD;
INT  KEYCOUNT;

и, следовательно, имеетсЯ массив пар. Ћписание структуры

STRUCT KEY  \(
   CHAR *KEYWORD;
   INT  KEYCOUNT;
\) KEYTAB [NKEYS];

оперделЯет массив KEYTAB структур такого типа и отводит длЯ
них памЯть. Љаждый элемент массива ЯвлЯетсЯ структурой. ќто
можно было бы записать и так:

STRUCT KEY  \(
   CHAR *KEYWORD;
   INT  KEYCOUNT;
\);
STRUCT KEY KEYTAB [NKEYS];

    ’ак как структура KEYTAB фактически содержит постоЯнный
набор имен, то легче всего инициализировать ее один раз и
длЯ всех членов при определении. €нициализациЯ структур
вполне аналогична предыдущим инициализациЯм - за определени-
ем следует заключенный в фигурные скобки список инициализа-
торов:

 STRUCT KEY  \(
    CHAR *KEYWORD;
    INT  KEYCOUNT;
 \) KEYTAB[] =\(
    "BREAK", 0,
    "CASE", 0,
    "CHAR", 0,
    "CONTINUE", 0,
    "DEFAULT", 0,
    /* ... */
    "UNSIGNED", 0,
    "WHILE", 0
 \);

€нициализаторы перечислЯютсЯ парами соответственно членам
структуры. Ѓыло бы более точно заключать в фигурные скобки
инициализаторы длЯ каждой "строки" или структуры следующим
образом:

 \( "BREAK", 0 \),
 \( "CASE", 0 \),
 . . .


Ќо когда инициализаторы ЯвлЯютсЯ простыми переменными или
символьными строками и все они присутствуют, то во внутрен-
них фигурных скобках нет необходимости. Љак обычно, компилЯ-
тор сам вычислит число элементов массива KEYTAB, если иници-
ализаторы присутствуют, а скобки [] оставлены пустыми.
    Џрограмма подсчета ключевых слов начинаетсЯ с определе-
ниЯ массива KEYTAB. ведущаЯ программа читает свой файл вво-
да, последовательно обращаЯсь к функции GETWORD, котораЯ из-
влекает из ввода по одному слову за обращение. Љаждое слово
ищетсЯ в массиве KEYTAB с помощью варианта функции бинарного
поиска, написанной нами в главе 3. (Љонечно, чтобы эта функ-
циЯ работала, список ключевых слов должен быть расположен в
порЯдке возрастаниЯ).

 #DEFINE    MAXWORD   20

 MAIN()   /* COUNT "C" KEYWORDS */
 \(
 INT  N, T;
 CHAR WORD[MAXWORD];

 WHILE ((T = GETWORD(WORD,MAXWORD)) != EOF)
    IF (T == LETTER)
      IF((N = BINARY(WORD,KEYTAB,NKEYS)) >= 0)
         KEYTAB[N].KEYCOUNT++;
 FOR (N =0; N &lt; NKEYS; N++)
    IF (KEYTAB[N].KEYCOUNT > 0)
     PRINTF("%4D %S\N",
       KEYTAB[N].KEYCOUNT, KEYTAB[N].KEYWORD);
 \)
 BINARY(WORD, TAB, N) /* FIND WORD IN TAB[0]...TAB[N-1] */
 CHAR *WORD;
 STRUCT KEY TAB[];
 INT N;
 \(
  INT LOW, HIGH, MID, COND;

  LOW = 0;
  HIGH = N - 1;
  WHILE (LOW &lt;= HIGH) \(
    MID = (LOW+HIGH) / 2;
    IF((COND = STRCMP(WORD, TAB[MID].KEYWORD)) &lt; 0)
     HIGH = MID - 1;
    ELSE IF (COND > 0)
     LOW = MID + 1;
    ELSE
     RETURN (MID);
  \)
  RETURN(-1);
 \)
Њы вскоре приведем функцию GETWORD; пока достаточно сказать,
что она возвращает LETTER каждый раз, как она находит слово,
и копирует это слово в свой первый аргумент.


    ‚еличина NKEYS - это количество ключевых слов в массиве
KEYTAB . •отЯ мы можем сосчитать это число вручную, гораздо
легче и надежнее поручить это машине, особенно в том случае,
если список ключевых слов подвержен изменениЯм. Ћдной из
возможностей было бы закончить список инициализаторов указа-
нием на нуль и затем пройти в цикле сквозь массив KEYTAB,
пока не найдетсЯ конец.
    Ќо, поскольку размер этого массива полностью определен к
моменту компилЯции, здесь имеетсЯ более простаЯ возможность.
—исло элементов просто есть

SIZE OF KEYTAB / SIZE OF STRUCT KEY

дело в том, что в Языке "C" предусмотрена унарнаЯ операциЯ
SIZEOF, выполнЯемаЯ во времЯ компилЯции, котораЯ позволЯет
вычислить размер любого объекта. ‚ыражение

SIZEOF(OBJECT)

выдает целое, равное размеру указанного объекта. (ђазмер оп-
ределЯетсЯ в неспецифицированных единицах, называемых "бай-
тами", которые имеют тот же размер, что и переменные типа
CHAR). Ћбъект может быть фактической переменной, массивом и
структурой, или именем основного типа, как INT или DOUBLE,
или именем производного типа, как структура. ‚ нашем случае
число ключевых слов равно размеру массива, деленному на раз-
мер одного элемента массива. ќто вычисление используетсЯ в
утверждении #DEFINE длЯ установлениЯ значениЯ NKEYS:

#DEFINE NKEYS (SIZEOF(KEYTAB) / SIZEOF(STRUCT KEY))

    ’еперь перейдем к функции GETWORD. Њы фактически написа-
ли более общий вариант функции GETWORD, чем необходимо длЯ
этой программы, но он не на много более сложен. ”ункциЯ
GETWORD возвращает следующее "слово" из ввода, где словом
считаетсЯ либо строка букв и цифр, начинающихсЯ с буквы, ли-
бо отдельный символ. ’ип объекта возвращаетсЯ в качетве зна-
чениЯ функции; это - LETTER, если найдено слово, EOF длЯ
конца файла и сам символ, если он не буквенный.

 GETWORD(W, LIM)   /* GET NEXT WORD FROM INPUT */
 CHAR *W;
 INT LIM;
 \(
  INT C, T;
  IF (TYPE(C=*W++=GETCH()) !=LETTER) \(
       *W='\0';
       RETURN(C);
  \)


 WHILE (--LIM > 0)  \(
  T = TYPE(C = *W++ = GETCH());
  IF (T ! = LETTER && T ! = DIGIT) \(
       UNGETCH(C);
       BREAK;
  \)
 \)
 *(W-1) - '\0';
 RETURN(LETTER);
 \)

”ункциЯ GETWORD использует функции GETCH и UNGETCH, которые
мы написали в главе 4: когда набор алфавитных символов пре-
рываетсЯ, функциЯ GETWORD получает один лишний символ. ‚ ре-
зультате вызова UNGETCH этот символ помещаетсЯ назад во ввод
длЯ следующего обращениЯ.
    ”ункциЯ GETWORD обращаетсЯ к функции TYPE длЯ определе-
ниЯ типа каждого отдельного символа из файла ввода. ‚от ва-
риант, справедливый только длЯ алфавита ASCII.

  TYPE(C)  /* RETURN TYPE OF ASCII CHARACTER */
  INT C;
   \(
  IF (C>= 'A' && C&lt;= 'Z' \!\! C>= 'A' && C&lt;= 'Z')
       RETURN(LETTER);
  ELSE IF (C>= '0' && C&lt;= '9')
       RETURN(DIGIT);
  ELSE
       RETURN(C);
  \)


‘имволические константы LETTER и DIGIT могут иметь любые
значениЯ, лишь бы они не вступали в конфликт с символами,
отличными от буквенно-цифровых, и с EOF; очевидно возможен
следующий выбор

     #DEFINE   LETTER   'A'
     #DEFINE   DIGIT   '0'

функциЯ GETWORD могла бы работать быстрее, если бы обращениЯ
к функции TYPE были заменены обращениЯми к соответствующему
массиву TYPE[ ]. ‚ стандартной библиотеке Языка "C" предус-
мотрены макросы ISALPHA и ISDIGIT, действующие необходимым
образом.

    “пражнение 6-1
    --------------
    ‘делайте такую модификацию функции GETWORD и оцените,
как изменитсЯ скорость работы программы.

    “пражнение 6-2
    --------------
    Ќапишите вариант функции TYPE, не зависЯщий от конкрет-
ного наборасимволов.


    “пражнение 6-3
    --------------
    Ќапишите вариант программы подсчета ключевых слов, кото-
рый бы не учитывал поЯвлениЯ этих слов в заключенных в ка-
вычки строках.


        6.4. “казатели на структуры

    —тобы проиллюстрировать некоторые соображениЯ, свЯзанные
с использованием указателей и массивов структур, давайте
снова составим программу подсчета ключевых строк, используЯ
на этот раз указатели, а не индексы массивов.
    ‚нешнее описание массива KEYTAB не нужно изменЯть, но
функции MAIN и BINARY требуют модификации.

    MAIN()   /* COUNT C KEYWORD; POINTER VERSION */
    \(
   INT  T;
   CHAR WORD[MAXWORD];
   STRUCT KEY *BINARY(), *P;
   WHILE ((T = GETWORD(WORD, MAXWORD;) !=EOF)
     IF (T==LETTER)
     IF ((P=BINARY(WORD,KEYTAB,NKEYS)) !=NULL)
             P->KEYCOUNT++;
   FOR (P=KEYTAB; P>KEYTAB + NKEYS; P++)
     IF (P->KEYCOUNT > 0)
  PRINTF("%4D %S/N", P->KEYCOUNT, P->KEYWORD);
    \)
     STRUCT KEY *BINARY(WORD, TAB, N) /* FIND WORD */
    CHAR *WORD   /* IN TAB[0]...TAB[N-1] */
    STRUCT KEY TAB [];
    INT N;
    \(
   INT  COND;
   STRUCT KEY *LOW = &TAB[0];
   STRUCT KEY *HIGH = &TAB[N-1];
   STRUCT KEY *MID;
   WHILE (LOW &lt;= HIGH) \(
  MID = LOW + (HIGH-LOW) / 2;
  IF ((COND = STRCMP(WORD, MID->KEYWORD)) &lt; 0)
        HIGH = MID - 1;
  ELSE IF (COND > 0)
        LOW = MID + 1;
  ELSE
        RETURN(MID);
   \)
   RETURN(NULL);
    \)

    ‡десь имеетсЯ несколько моментов, которые стоит отме-
тить. ‚о-первых, описание функции BINARI должно указывать,
что она возвращает указатель на структуру типа KEY, а не на
целое; это объЯвлЯетсЯ как в функции MAIN, так и в BINARY.
…сли функциЯ BINARI находит слово, то она возвращает указа-
тель на него; если же нет, она возвращает NULL.


    ‚о-вторых, все обращениЯ к элементам массива KEYTAB осу-
ществлЯютсЯ через указатели. ќто влечет за собой одно сущес-
твенное изменение в функции BINARY: средний элемент больше
нельзЯ вычислЯть просто по формуле

  MID = (LOW + HIGH) / 2

потому что сложение двух указателей не дает какого-нибудь
полезного результата (даже после делениЯ на 2) и в действи-
тельности ЯвлЯетсЯ незаконным. эту формулу надо заменить на

  MID = LOW + (HIGH-LOW) / 2

в результате которой MID становитсЯ указателем на элемент,
расположенный посередине между LOW и HIGH.
    ‚ам также следует разобратьсЯ в инициализации LOW и
HIGH. указатель можно инициализировать адресом ранее опреде-
ленного объекта; именно как мы здесь и поступили.
    ‚ функции MAIN мы написали

  FOR (P=KEYTAB; P &lt; KEYTAB + NKEYS; P++)

…сли P ЯвлЯетсЯ указателем структуры, то любаЯ арифметика с
P учитывает фактический размер данной структуры, так что P++
увеличивает P на нужную величину, в результате чего P указы-
вает на следующий элемент массива структур. Ќо не считайте,
что размер структуры равен сумме размеров ее членов, - из-за
требований выравниваниЯ длЯ различных объектов в структуре
могут возникать "дыры".
    €, наконец, несколько второстепенный вопрос о форме за-
писи программы. …сли возвращаемаЯ функцией величина имеет
тип, как, например, в

     STRUCT KEY *BINARY(WORD, TAB, N)

Tо может оказатьсЯ, что имЯ функции трудно выделить среди
текста. ‚ свЯзи с этим иногда используетсЯ другой стиль за-
писи:

          STRUCT KEY *
      BINARY(WORD, TAB, N)

ќто главным образом дело вкуса; выберите ту форму, котораЯ
вам нравитсЯ, и придерживайтесь ее.


        6.5. ‘труктуры, ссылающиесЯ на себЯ

    Џредположим, что нам надо справитьсЯ с более общей зада-
чей, состоЯщей в подсчете числа поЯвлений всех слов в неко-
тором файле ввода. ’ак как список слов заранее не известен,
мы не можем их упорЯдочить удобным образом и использовать
бинарный поиск. Њы даже не можем осуществлЯть последователь-
ный просмотр при поступлении каждого слова, с тем чтобы ус-
тановить, не встречалось ли оно ранее; такаЯ программа будет
работать вечно. (Ѓолее точно, ожидаемое времЯ работы растет
как квадрат числа вводимых слов). Љак же нам организовать
программу, чтобы справитьсЯ со списком произвольных слов?


    Ћдно из решений состоит в том, чтобы все времЯ хранить
массив поступающих до сих пор слов в упорЯдоченном виде, по-
мещаЯ каждое слово в нужное место по мере их поступлениЯ.
O„нако это не следует делать, перемещаЯ слова в линейном
массиве, - это также потребует слишком много времени. ‚место
этого мы используем структуру данных, называемую доичным де-
ревом.
    Љаждому новому слову соответствует один "узел" дерева;
каждый узел содержит:
указатель текста слова
----------------------
счетчик числа поЯвлений
-----------------------
указатель узла левого потомка
-----------------------------
указатель узла правого потомка
------------------------------
Ќикакой узел не может иметь более двух детей; возможно от-
сутсвие детей или наличие только одного потомка.
    “злы создаютсЯ таким образом, что левое поддерево каждо-
го узла содержит только те слова, которые меньше слова в
этом узле, а правое поддерево только те слова, которые боль-
ше. —тобы определить, находитсЯ ли новое слово уже в дереве,
начинают с корнЯ и сравнивают новое слово со словом, хранЯ-
щимсЯ в этом узле. …сли слова совпадают, то вопрос решаетсЯ
утвердительно. …сли новое слово меньше слова в дереве, то
переходЯт к рассмотрению левого потомка; в противном случае
исследуетсЯ правый потомок. …сли в нужном направлении пото-
мок отсутствует, то значит новое слово не находитсЯ в дереве
и место этого недостающего потомка как раз и ЯвлЯетсЯ мес-
том, куда следует поместить новое слово. Џоскольку поиск из
любого узла приводит к поиску одного из его потомков, то сам
процесс поиска по существу ЯвлЯетсЯ рекурсивным. ‚ соответс-
твии с этим наиболее естественно использовать рекурсивные
процедуры ввода и вывода.
    ‚озвращаЯсь назад к описанию узла, Ясно, что это будет
структура с четырьмЯ компонентами:

STRUCT TNODE \( /* THE BASIC NODE */
   CHAR *WORD; /* POINTS TO THE TEXT */
   INT   COUNT; /* NUMBER OF OCCURRENCES */
   STRUCT TNODE *LEFT; /* LEFT CHILD */
   STRUCT TNODE *RIGHT; /* RIGHT CHILD */
\);

ќто "рекурсивное" описание узла может показатьсЯ рискован-
ным, но на самом деле оно вполне корректно. ‘труктура не
имеет права содержать ссылку на саму себЯ, но

STRUCT TNODE *LEFT;

описывает LEFT как указатель на узел, а не как сам узел.


    ’екст самой программы оказываетсЯ удивительно маленьким,
если, конечно, иметь в распорЯжении набор написанных нами
ранее процедур, обеспечивающих нужные действиЯ. Њы имеем в
виду функцию GETWORD длЯ извлечениЯ каждого слова из файла
ввода и функцию ALLOC длЯ выделениЯ места длЯ хранениЯ слов.
    ‚едущаЯ программа просто считывает слова с помощью функ-
ции GETWORD и помещает их в дерево, используЯ функцию TREE.

#DEFINE   MAXWORD   20
MAIN()    /* WORD FREGUENCY COUNT */
\(
    STRUCT TNODE *ROOT, *TREE();
    CHAR WORD[MAXWORD];
    INT   T;
    ROOT = NULL;
    WHILE ((T = GETWORD(WORD, MAXWORD)) \! = EOF)
       IF (T == LETTER)
            ROOT = TREE(ROOT, WORD);
    TREEPRINT(ROOT);
\)

    ”ункциЯ TREE сама по себе проста. ‘лово передаетсЯ функ-
цией MAIN к верхнему уровню (корню) дерева. Ќа каждом этапе
это слово сравниваетсЯ со словом, уже хранЯщимсЯ в этом уз-
ле, и с помощью рекурсивного обращениЯ к TREE просачиваетсЯ
вниз либо к левому, либо к правому поддереву. ‚ конце концов
это слово либо совпадает с каким-то словом, уже находЯщимсЯ
в дереве (в этом случае счетчик увеличиваетсЯ на единицу),
либо программа натолкнетсЯ на нулевой указатель, свидетель-
ствующий о необходимости созданиЯ и добавлениЯ к дереву но-
вого узла. ‚ случае созданиЯ нового узла функциЯ TREE возв-
ращает указатель этого узла, который помещаетсЯ в родитель-
ский узел.

 STRUCT TNODE *TREE(P, W)
        /* INSTALL W AT OR BELOW P */
 STRUCT TNODE *P;
 CHAR *W;
 \(
    STRUCT TNODE *TALLOC();
    CHAR *STRSAVE();
    INT COND;
    IF (P == NULL) \( /* A NEW WORD
       HAS ARRIVED */
         P == TALLOC(); /* MAKE A NEW NODE */
         P->WORD = STRSAVE(W);
         P->COUNT = 1;
         P->LEFT = P->RIGHT = NULL;
 \) ELSE IF ((COND = STRCMP(W, P->WORD)) == 0)
         P->COUNT++;     /* REPEATED WORD */
     ELSE IF (COND &lt; 0)/* LOWER GOES INTO LEFT SUBTREE */
         P->LEFT = TREE(P->LEFT, W);
 ELSE            /* GREATER INTO RIGHT SUBTREE */
         P->RIGHT = TREE(P->RIGHT, W);
 RETURN(P);
 \)


    ЏамЯть длЯ нового узла выделЯетсЯ функцией TALLOC, ЯвлЯ-
ющейсЯ адаптацией длЯ данного случаЯ функции ALLOC, написан-
ной нами ранее. Ћна возвращает указатель свободного прост-
ранства, пригодного длЯ хранениЯ нового узла дерева. (Њы
вскоре обсудим это подробнее). Ќовое слово копируетсЯ функ-
цией STRSAVE в скрытое место, счетчик инициализируетсЯ еди-
ницей, и указатели обоих потомков полагаютсЯ равными нулю.
ќта часть программы выполнЯетсЯ только при добавлении нового
узла к ребру дерева. Њы здесь опустили проверку на ошибки
возвращаемых функций STRSAVE и TALLOC значений (что неразум-
но длЯ практически работающей программы).
    ”ункциЯ TREEPRINT печатает дерево, начинаЯ с левого под-
дерева; в каждом узле сначала печатаетсЯ левое поддерево
(все слова, которые младше этого слова), затем само слово, а
затем правое поддерево (все слова, которые старше). …сли вы
неуверенно оперируете с рекурсией, нарисуйте дерево сами и
напечатайте его с помощью функции TREEPRINT ; это одна из
наиболее Ясных рекурсивных процедур, которую можно найти.

 TREEPRINT (P) /* PRINT TREE  P  RECURSIVELY */
 STRUCT TNODE *P;
 \(
    IF (P != NULL)    \(
       TREEPRINT (P->LEFT);
       PRINTF("%4D %S\N", P->COUNT, P->WORD);
       TREEPRINT (P->RIGHT);
    \)
\)

    Џрактическое замечание: если дерево становитсЯ "несба-
лансированным" из-за того, что слова поступают не в случай-
ном порЯдке, то времЯ работы программы может расти слишком
быстро. ‚ худшем случае, когда поступающие слова уже упорЯ-
дочены, настоЯщаЯ программа осуществлЯет дорогостоЯщую ими-
тацию линейного поиска. ‘уществуют различные обобщениЯ дво-
ичного дерева, особенно 2-3 деревьЯ и AVL деревьЯ, которые
не ведут себЯ так "в худших случаЯх", но мы не будем здесь
на них останавливатьсЯ.
    Џрежде чем расстатьсЯ с этим примером, уместно сделать
небольшое отступление в свЯзи с вопросом о распределении па-
мЯти. џсно, что в программе желательно иметь только один
распределитель памЯти, даже если ему приходитсЯ размещать
различные виды объектов. Ќо если мы хотим использовать один
распределитель памЯти длЯ обработки запросов на выделение
памЯти длЯ указателей на переменные типа CHAR и длЯ указате-
лей на STRUCT TNODE, то при этом возникают два вопроса. Џер-
вый: как выполнить то существующее на большинстве реальных
машин ограничение, что объекты определенных типов должны
удовлетворЯть требованиЯм выравниваниЯ (например, часто це-
лые должны размещатьсЯ в четных адресах)? ‚торой: как орга-
низовать описаниЯ, чтобы справитьсЯ с тем, что функциЯ ALLOC
должна возвращать различные виды указателей ?
    ‚ообще говорЯ, требованиЯ выравниваниЯ легко выполнить
за счет выделениЯ некоторого лишнего пространства, просто
обеспечив то, чтобы распределитель памЯти всегда возвращал
указатель, удовлетворЯющий всем ограничениЯм выравниваниЯ.
Ќапример, на PDP-11 достаточно, чтобы функциЯ ALLOC всегда
возвращала четный указатель, поскольку в четный адрес можно
поместить любой тип объекта. единственный расход при этом -
лишний символ при запросе на нечетную длину. Ђналогичные
действиЯ предпринимаютсЯ на других машинах. ’аким образом,
реализациЯ ALLOC может не оказатьсЯ переносимой, но ее ис-
пользование будет переносимым. ”ункциЯ ALLOC из главы 5 не
предусматривает никакого определенного выравниваниЯ; в главе
8 мы продемонстрируем, как правильно выполнить эту задачу.
    ‚опрос описаниЯ типа функции ALLOC ЯвлЯетсЯ мучительным
длЯ любого Языка, который серьезно относитсЯ к проверке ти-
пов. ‹учший способ в Языке "C" - объЯвить, что ALLOC возвра-
щает указатель на переменную типа CHAR, а затем Явно преоб-
разовать этот указатель к желаемому типу с помощью операции
перевода типов. ’аким образом, если описать P в виде

    CHAR *P;
то
    (STRUCT TNODE *) P

преобразует его в выражениЯх в указатель на структуру типа
TNODE . ‘ледовательно, функцию TALLOC можно записать в виде:

STRUCT TNODE *TALLOC()
\(
   CHAR *ALLOC();

   RETURN ((STRUCT TNODE *) ALLOC(SIZEOF(STRUCT TNODE)));
\)


это более чем достаточно длЯ работающих в настоЯщее времЯ
компилЯторов, но это и самый безопасный путь с учетом будую-
щего.

    “пражнение 6-4
    ----------------
    Ќапишите программу, котораЯ читает "C"-программу и печа-
тает в алфавитном порЯдке каждую группу имен переменных, ко-
торые совпадают в первых семи символах, но отличаютсЯ где-то
дальше. (‘делайте так, чтобы 7 было параметром).

    “пражнение 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, можно использовать
специальн