rt-g0_1fcd69d8-KnR_C-russian/chapters/chapter6.tex

\chapter{Структуры}
\label{chapt:structures}

Структура -- это одна или несколько переменных (возможно, различных типов),
которые для удобства работы с ними сгруппированы под одним именем. (В некоторых
языках, в частности в Паскале, структуры называются записями.) Структуры
помогают в организации сложных данных (особенно в больших программах), поскольку
позволяют группу связанных между собой переменных трактовать не как множество
отдельных элементов, а как единое целое.

Распространённый пример структуры -- строка платёжной ведомости. Она содержит
такие сведения о служащем, как его полное имя, адрес, номер карточки социального
страхования, зарплата и т.д. Некоторые из этих характеристик сами могут быть
структурами: например, полное имя состоит из нескольких компонент (фамилии‚
имени и отчества); аналогично адрес, и даже зарплата. Другой пример (более
типичный для Си) -- из области графики: точка есть пара координат,
прямоугольник есть пара точек и т.д.

Главные изменения, внесённые стандартом ANSI в отношении структур, -- это
введение для них операции присваивания. Структуры могут копироваться, над ними
могут выполняться операции присваивания, их можно передавать функциям в
качестве аргументов, а функции могут возвращать их в качестве результатов. В
большинстве компиляторов уже давно реализованы эти возможности, но теперь они
точно оговорены стандартом. Для автоматических структур и массивов теперь также
допускается инициализация.

\section{Основные сведения о структурах}

Сконструируем несколько графических структур. В качестве основного объекта
выступает точка с координатами $x$ и $y$, и пусть они имеют тип \verb|int|.

\begin{figure}[H]
\center{\includegraphics[width=0.3841808\linewidth]{chapt6_sec1_img0.eps}}
\end{figure}

\noindent%
\index{декларация!структуры}%
\index{структура!декларация}%
Указанные две компоненты можно поместить в структуру, описанную, например,
следующим образом:

\begin{ShortCodePar}
struct point {
    int x;
    int y;
};
\end{ShortCodePar}

Описание структуры начинается с ключевого слова \verb|struct| и содержит список
деклараций, заключённый в фигурные скобки.
\index{структура!тег}%
\index{тег!структуры}%
За словом \verb|struct| может следовать имя, называемое
\emph{тегом}\footnote{От английского слова tag -- ярлык, этикетка. --
\textit{Примеч. пер.}} \emph{структуры} (\verb|point| в нашем случае). Тег даёт
название структуре данного вида и далее может служить кратким обозначением той
части декларации, которая заключена в фигурные скобки.

\index{структура!имя члена}%
\index{член структуры, имя}%
Перечисленные в структуре переменные называются \emph{членами}. Имена членов и
тегов без каких-либо коллизий могут совпадать с именами обычных переменных (т.е.
не членов), так как они всегда различимы по контексту. Более того, одни и те же
имена членов могут встречаться в разных структурах, хотя, если следовать
хорошему стилю программирования, лучше одинаковые имена давать только близким по
смыслу объектам.

\index{декларация!структуры}%
\index{структура!декларация}%
Декларация структуры -- это тип. За правой фигурной скобкой, закрывающей список
членов, могут следовать переменные точно так же, как они могут быть указаны
после названия любого базового типа. Таким образом, запись

\begin{ShortCodePar}
struct { ... } x, y, z;
\end{ShortCodePar}

\noindent с точки зрения синтаксиса аналогична записи

\begin{ShortCodePar}
int x, y, z;
\end{ShortCodePar}

\noindent в том смысле, что каждая декларирует \verb|x|, \verb|y| и \verb|z| как
переменные указанного типа. Обе записи приведут к тому, что где-то будет
выделена память соответствующего размера.

\index{декларация!структуры}%
\index{структура!декларация}%
Декларация структуры, не содержащей списка переменных, не резервирует памяти:
она просто описывает шаблон, или образец структуры. Однако если структура имеет
тег, то этим тегом далее можно пользоваться при определении структурных
объектов. Например, с помощью заданной выше декларации структуры
\verb|point| строка

\begin{ShortCodePar}
struct point pt;
\end{ShortCodePar}

\noindent определяет структурную переменную \verb|pt| типа \verb|struct point|.
\index{инициализация!структуры}%
\index{структура!инициализация}%
\index{фигурные скобки}%
Структурную переменную при её определении можно инициализировать, формируя
список инициализаторов её членов в виде константных выражений:

\begin{ShortCodePar}
struct point maxpt = { 320, 200 };
\end{ShortCodePar}

\noindent Инициализировать автоматические структуры можно также присваиванием
или обращением к функции, возвращающей результат в виде структуры
соответствующего типа.

\index{оператор!доступа к члену структуры!точка@\texttt{.} (точка)}%
\index{структура!оператор доступа к её члену!\texttt{.} (точка)}%
Доступ к отдельному члену структуры осуществляется посредством конструкции вида:

\begin{ShortCodeParWithCC}{\\\{\}}
\textit{имя-структуры} . \textit{член}
\end{ShortCodeParWithCC}

\noindent Оператор доступа к члену структуры <<\verb|.|>> соединяет имя
структуры и имя члена. Чтобы напечатать, например, координаты точки \verb|pt|,
годится следующее обращение к \verb|printf|:

\begin{ShortCodePar}
printf("%d,%d", pt.x, pt.y);
\end{ShortCodePar}

\noindent Другой пример: чтобы вычислить расстояние от начала координат $(0, 0)$
до \verb|pt|, можно написать

\begin{ShortCodePar}
double dist, sqrt(double);
dist = sqrt((double)pt.x * pt.x + (double)pt.y * pt.y);
\end{ShortCodePar}

\index{структура!вложенная}%
Структуры могут быть вложены друг в друга. Одно из возможных представлений
прямоугольника -- это пара точек на углах одной из его диагоналей:

\begin{figure}[H]
\center{\includegraphics[width=0.5056180\linewidth]{chapt6_sec1_img1.eps}}
\end{figure}

\begin{ShortCodePar}
struct rect {
    struct point pt1;
    struct point pt2;
};
\end{ShortCodePar}

\noindent Структура \verb|rect| содержит две структуры \verb|point|. Если мы
декларируем \verb|screen| как

\begin{ShortCodePar}
struct rect screen;
\end{ShortCodePar}

\noindent то

\begin{ShortCodePar}
screen.pt1.x
\end{ShortCodePar}

\noindent ссылается на координату $x$ точки \verb|pt1| из \verb|screen|.

\section{Структуры и функции}

Единственно возможные операции над структурами -- это их копирование,
присваивание, взятие адреса с помощью \verb|&| и осуществление доступа к её
членам. Передача структур функциям в качестве аргументов и возврат их от
функций в виде результата также относятся к операциям копирования и
присваивания. Структуры нельзя сравнивать. Инициализировать структуру можно
списком константных значений её членов; автоматическую структуру можно
инициализировать также присваиванием.

Чтобы лучше познакомиться со структурами, напишем несколько функций,
манипулирующих точками и прямоугольниками. Возникает вопрос: а как передавать
функциям названные объекты? Существует по крайней мере три подхода: передавать
компоненты по отдельности, передавать всю структуру целиком и передавать
указатель на структуру. Каждый подход имеет свои плюсы и минусы.

\index{функция!makepoint@\texttt{makepoint}}%
Первая функция, \verb|makepoint|, получает два целых значения и возвращает
структуру \verb|point|.

\begin{LongCodePar}
/* makepoint: формирует точку по компонентам x и y */
struct point makepoint(int x, int y)
{
    struct point temp;
    temp.x = x;
    temp.y = y;
    return temp;
}
\end{LongCodePar}

\noindent Заметим: никакой путаницы из-за того, что имя аргумента совпадает с
именем члена структуры не возникает; более того, одно и то же имя подчёркивает
родство обозначаемых им объектов.

Теперь с помощью \verb|makepoint| можно выполнять динамическую инициализацию
любой структуры или формировать структурные аргументы для той или иной функции:

\begin{ShortCodePar}
struct rect screen;
struct point middle;
struct point makepoint(int, int);
screen.pt1 = makepoint(0, 0);
screen.pt2 = makepoint(XMAX, YMAX);
middle = makepoint((screen.pt1.x + screen.pt2.x)/2,
                   (screen.pt1.y + screen.pt2.y)/2);
\end{ShortCodePar}

\index{функция!addpoint@\texttt{addpoint}}%
Нам может понадобиться ряд функций, реализующих различные операции над точками.
В качестве примера рассмотрим следующую функцию:

\begin{ShortCodePar}
/* addpoint: сложение двух точек */
struct point addpoint(struct point p1, struct point p2)
{
    p1.x += p2.x;
    p1.y += p2.y;
    return p1;
}
\end{ShortCodePar}

\noindent Здесь оба аргумента и возвращаемое значение -- структуры. Мы
увеличиваем компоненты прямо в \verb|p1| и не используем для этого временной
переменной, чтобы подчеркнуть, что структурные параметры передаются по значению
так же, как и любые другие.

\index{функция!ptinrect@\texttt{ptinrect}}%
В качестве другого примера приведём функцию \verb|ptinrect|, которая проверяет:
находится ли точка внутри прямоугольника, относительно которого мы принимаем
соглашение, что в него входят его левая и нижняя стороны, но не входят верхняя и
правая.

\begin{ShortCodePar}
/* ptinrect: возвращает 1, если p в r, и 0 в прот. случае */
int ptinrect(struct point p, struct rect r)
{
    return p.x >= r.pt1.x && p.x < r.pt2.x
        && p.y >= r.pt1.y && p.y < r.pt2.y;
}
\end{ShortCodePar}

\noindent Здесь предполагается, что прямоугольник представлен в стандартном
виде, т.е. координаты точки \verb|pt1| меньше соответствующих координат точки
\verb|pt2|.
\index{функция!canonrect@\texttt{canonrect}}%
Следующая функция гарантирует получение прямоугольника в
каноническом виде.

\begin{LongCodePar}
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
/* canonrect: канонизация координат прямоугольника */
struct rect canonrect(struct rect r)
{
    struct rect temp;
    temp.pt1.x = min(r.pt1.x, r.pt2.x);
    temp.pt1.y = min(r.pt1.y, r.pt2.y);    
    temp.pt2.x = max(r.pt1.x, r.pt2.x);
    temp.pt2.y = max(r.pt1.y, r.pt2.y);
    return temp;
}
\end{LongCodePar}

Если функции передаётся большая структура, то, чем копировать её целиком,
эффективнее передать указатель на неё. Указатели на структуры ничем не
отличаются от указателей на обычные переменные. Декларация

\begin{ShortCodePar}
struct point *pp;
\end{ShortCodePar}

\noindent сообщает, что \verb|pp| есть указатель на структуру типа
\verb|struct point|. Если \verb|pp| ссылается на структуру \verb|point|, то
\verb|*pp| есть сама структура, а \verb|(*pp).x| и \verb|(*pp).y| -- её члены.
Используя указатель \verb|pp|, мы могли бы написать

\begin{ShortCodePar}
struct point origin, *pp;
pp = &origin;
printf("origin: (%d,%d)\n", (*pp).x, (*pp).y);
\end{ShortCodePar}

\noindent%
\index{оператор!приоритет}%
Скобки в \verb|(*pp).x| необходимы поскольку приоритет оператора \verb|.| выше,
чем приоритет \verb|*|. Выражение \verb|*pp.x| будет проинтерпретировано как
\verb|*(pp.x)|‚ что неверно, поскольку \verb|pp.x| не является указателем.

\index{оператор!доступа к члену структуры!через указатель \texttt{\textminus\textgreater}}%
\index{структура!оператор доступа к её члену!через указатель \texttt{\textminus\textgreater}}%
Указатели на структуры используются весьма часто, поэтому для доступа к её
членам была придумана ещё одна, более короткая форма записи. Если \verb|p| --
указатель на структуру, то

\begin{ShortCodeParWithCC}{\\\{\}}
p->\textit{член-структуры}
\end{ShortCodeParWithCC}

\noindent есть её отдельный член. (Оператор \verb|->| состоит из знака
\verb|-|, за которым сразу следует знак \verb|>|.) Поэтому \verb|printf| можно
переписать в виде

\begin{ShortCodePar}
printf("origin: (%d,%d)\n", pp->x, pp->y);
\end{ShortCodePar}

\index{оператор!приоритет}%
\index{приоритеты операторов}%
Оба оператора \verb|.| и \verb|->| выполняются слева направо. Таким образом, при
наличии декларации

\begin{ShortCodePar}
struct rect r, *rp = r;
\end{ShortCodePar}

\noindent следующие четыре выражения будут эквивалентны:

\begin{ShortCodePar}
r.pt1.x
rp->pt1.x
(r.pt1).x
(rp->pt1).x
\end{ShortCodePar}

\index{оператор!приоритет}%
\index{приоритеты операторов}%
Операторы доступа к членам структуры \verb|.| и \verb|->| вместе с операторами
вызова функции \verb|()| и индексации массива \verb|[]| занимают самое высокое
положение в иерархии приоритетов и выполняются раньше любых других операторов.
Например, если задана декларация

\begin{ShortCodePar}
struct {
    int len;
    char *str;
} *p;
\end{ShortCodePar}

\noindent то

\begin{ShortCodePar}
++p->len
\end{ShortCodePar}

\noindent увеличит на $1$ значение члена структуры \verb|len|, а не указатель
\verb|p|, поскольку в этом выражении как бы неявно присутствуют скобки:
\verb|++(p->len)|. Чтобы изменить порядок выполнения операций, нужны явные
скобки. Так, в \verb|(++p)->len|, прежде чем взять значение \verb|len|,
программа
%  
% в оригинале слева внизу страницы ``5. Заказ № 13''
%
продвинет указатель \verb|p|. В \verb|(p++)->len| указатель \verb|p| увеличится
после того, как будет взято значение \verb|len| (в последнем случае скобки не
обязательны).

\index{оператор!приоритет}%
\index{приоритеты операторов}%
По тем же правилам \verb|*p->str| обозначает содержимое объекта, на который
ссылается \verb|str|; \verb|*p->str++| продвинет указатель \verb|str| после
получения значения объекта, на который он указывал (как и в выражении вида
\verb|*s++|); \verb|(*p->str)++| увеличит значение объекта, на который ссылается
\verb|str|; \verb|*p++->str| продвинет \verb|p| после того, как будет получено
то, на что указывает \verb|str|.

\section{Массивы структур}

\index{массив!структур}%
\index{программа!подсчёта!ключевых слов}%
Рассмотрим программу, определяющую число вхождений каждого ключевого слова в
текст Си-программы. Нам нужно уметь хранить ключевые слова в виде массива
стрингов и счётчики ключевых слов в виде массива целых. Один из возможных
вариантов -- это иметь два параллельных массива:

\begin{ShortCodePar}
char *keyword[NKEYS];
int keycount[NKEYS];
\end{ShortCodePar}

\noindent Однако именно тот факт, что они параллельны, подсказывает нам другую
организацию хранения -- через массив структур. Каждое ключевое слово можно
описать парой характеристик

\begin{ShortCodePar}
char *word;
int count;
\end{ShortCodePar}

\noindent Такие пары составляют массив. Декларация

\begin{ShortCodePar}
struct key {
    char *word;
    int count;
} keytab[NKEYS];
\end{ShortCodePar}

\noindent описывает структуру типа \verb|key| и определяет массив \verb|keytab|,
каждый элемент которого есть структура этого типа и которому где-то будет
выделена память. Это же можно записать и по-другому:

\begin{ShortCodePar}
struct key {
    char *word;
    int count;
};
struct key keytab[NKEYS];
\end{ShortCodePar}

Так как \verb|keytab| содержит постоянный набор имён, его легче всего сделать
внешним массивом и инициализировать один раз в момент определения.
\index{массив!структур!инициализация}%
\index{инициализация!массивов структур}%
Инициализация структур аналогична ранее демонстрировавшимся инициализациям -- за
определением следует список инициализаторов, заключённый в фигурные скобки:

\begin{LongCodePar}
struct key {
    char *word;
    int count;
} keytab[] = {
    "auto", 0,
    "break", 0,
    /* ... */
    "while", 0
};
\end{LongCodePar}

\noindent%
\index{массив!структур!инициализация}%
\index{инициализация!массивов структур}%
Инициализаторы задаются парами, чтобы соответствовать конфигурации структуры.
Строго говоря, пару инициализаторов для каждой отдельной структуры следовало бы
заключить в фигурные скобки, как, например, в

\begin{ShortCodePar}
{ "auto", 0 },
{ "break", 0 },
...
\end{ShortCodePar}

\noindent Однако, когда инициализаторы -- простые константы или цепочки литер,
и все они имеются в наличии, во внутренних скобках нет необходимости.
\index{массив!размер по умолчанию}%
\index{по умолчанию!размер массива}%
Число элементов массива \verb|keytab| будет вычислено по количеству
инициализаторов, поскольку они представлены полностью, а внутри квадратных
скобок \verb|[]| ничего не задано.

Программа подсчёта ключевых слов начинается с определения \verb|keytab|.
Программа \verb|main| читает ввод, многократно обращаясь к функции
\verb|getword| и получая на каждом её вызове очередное слово. Каждое слово
ищется в \verb|keytab|.
\index{функция!binsearch@\texttt{binsearch}}%
Для этого используется функция бинарного поиска, которую
мы написали в гл.~\ref{chapt:control_flow}. Список ключевых слов должен быть
упорядочен в алфавитном порядке.

\begin{LongCodePar}
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
int getword(char *, int);
int binsearch(char *, struct key *, int);
/* подсчёт ключевых слов Си */
main()
{
    int n;
    char word[MAXWORD];
    while (getword(word, MAXWORD) != EOF)
        if (isalpha(word[0]))
            if ((n = binsearch(word, keytab, NKEYS)) >= 0)
                keytab[n].count++;
    for (n = 0; n < NKEYS; n++)
        if (keytab[n].count > 0)
            printf("%4d %s\n",
                keytab[n].count, keytab[n].word);
    return 0;
}
/* binsearch: найти слово в tab[0]...tab[n-1] */
int binsearch(char *word, struct key tab[], int n)
{
    int cond;
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high) {
        mid = (low+high) / 2;
        if ((cond = strcmp(word, tab[mid].word)) < 0)
            high = mid - 1;
        else if (cond > 0)
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}
\end{LongCodePar}
%  
% в оригинале слева внизу страницы ``5*''
%

\noindent Чуть позже мы рассмотрим функцию \verb|getword|, а сейчас нам
достаточно знать, что при каждом её вызове получается очередное слово, которое
запоминается в массиве, заданном первым аргументом.

\verb|NKEYS| -- количество ключевых слов в \verb|keytab|. Хотя мы могли бы
подсчитать число таких слов вручную, гораздо легче и безопасней сделать это с
помощью машины, особенно если список ключевых слов может быть изменён. Одно из
возможных решений -- поместить в конец списка инициализаторов пустой указатель
(\verb|NULL|) и затем перебирать в цикле элементы \verb|keytab|, пока не
встретится концевой элемент.

Но возможно и более простое решение. Поскольку размер массива полностью
определён во время компиляции и равен произведению количества элементов массива
на размер его отдельного элемента, число элементов массива можно вычислить по
формуле

\begin{ShortCodeParWithCC}{\\\{\}}
\textit{размер} keytab / \textit{размер} struct key
\end{ShortCodeParWithCC}

\noindent%
\index{оператор!sizeof@\texttt{sizeof}}%
В Си имеется унарный оператор \verb|sizeof|‚ который работает во время
компиляции. Его можно применять для вычисления размера любого объекта. Выражения

\begin{ShortCodeParWithCC}{\\\{\}}
sizeof \textit{объект}
\end{ShortCodeParWithCC}

\noindent и

\begin{ShortCodeParWithCC}{\\\{\}}
sizeof(\textit{имя типа})
\end{ShortCodeParWithCC}

\noindent выдают целые значения, равные размеру указанного объекта или типа в
байтах.
\index{файл!головной!<stddef.h>@\texttt{<stddef.h>}}%
\index{size{\_}t@\texttt{size{\_}t}}%
(Строго говоря, \verb|sizeof| выдаёт беззнаковое целое, тип которого
\verb|size_t| определён в головном файле \verb|<stddef.h>|.) Что касается
объекта, то это может быть переменная, массив или структура. В качестве имени
типа может выступать имя базового типа (\verb|int|, \verb|double|, \ldots) или
имя производного типа, например, структуры или указателя.

В нашем случае, чтобы вычислить количество ключевых слов, размер массива надо
поделить на размер одного элемента. Указанное вычисление используется в
инструкции \verb|#define| для установки значения \verb|NKEYS|:

\begin{ShortCodePar}
#define NKEYS (sizeof keytab / sizeof(struct key))
\end{ShortCodePar}

\noindent Этот же результат можно получить другим способом -- поделить размер
массива на размер какого-то его конкретного элемента:

\begin{ShortCodePar}
#define NKEYS (sizeof keytab / sizeof keytab[0])
\end{ShortCodePar}

\noindent Преимущество такого рода записей в том, что их не надо корректировать
при изменении типа.

\index{оператор!sizeof@\texttt{sizeof}}%
\index{if@\texttt{{\#}if}}%
Поскольку препроцессор не обращает внимания на имена типов, оператор
\verb|sizeof| нельзя применять в \verb|#if|. Но в \verb|#define| выражение
препроцессором не вычисляется, так что предложенная нами запись допустима.

\index{функция!getword@\texttt{getword}}%
Теперь поговорим о функции \verb|getword|. Мы написали \verb|getword| в
несколько более общем виде, чем требуется для нашей программы, но она от этого
не стала заметно сложнее. Функция \verb|getword| берет из входного потока
следующее <<слово>>. Под словом понимается цепочка букв-цифр, начинающаяся с
буквы, или отдельная непробельная литера. По концу файла функция выдаёт
\verb|EOF|, в остальных случаях её значением является код первой литеры слова
или код отдельной литеры, если она не буква.

\begin{LongCodePar}
/* getword: принимает следующее слово или литеру из ввода */
int getword(char *word, int lim)
{
    int c, getch(void);
    void ungetch(int);
    char *w = word;
    while (isspace(c = getch()))
        ;
    if (c != EOF)
        *w++ = c;
    if (!isalpha(c)) {
        *w = '\0';
        return c;
    }
    for ( ; --lim > 0; w++)
        if (!isalnum(*w = getch())) {
            ungetch(*w);
            break;
        }
    *w = '\0';
    return word[0];
}
\end{LongCodePar}
%
% исправлена опечатка 
% в оригинале не хватало закрывающей скобки в 
% while (isspace(c = getch())
%

Функция \verb|getword| обращается к \verb|getch| и \verb|ungetch|, которые мы
написали в гл.~\ref{chapt:functions_and_program_structure}. При завершении
набора букв-цифр оказывается, что \verb|getword| взяла лишнюю литеру. Обращение
к \verb|ungetch| позволяет вернуть её назад во входной поток. В \verb|getword|
используются также \verb|isspace| -- для пропуска пробельных литер,
\verb|isalpha| -- для идентификации букв и \verb|isalnum| -- для распознавания
букв-цифр. Все они описаны в стандартном головном файле \verb|<ctype.h>|.

\paragraph{Упражнение 6.1.} Наша версия \verb|getword| не обрабатывает должным
образом знак подчёркивания, стринговые константы, комментарии и управляющие
строки препроцессора. Напишите более совершенный вариант программы.

\section{Указатели на структуры}

\index{структура!указатель на неё}%
\index{указатель!на структуру}%
Для иллюстрации некоторых моментов, касающихся указателей на структуры и
массивов структур, перепишем программу подсчёта ключевых слов, пользуясь для
получения элементов массива вместо индексов указателями.

\index{функция!binsearch@\texttt{binsearch}}%
Внешняя декларация массива \verb|keytab| остаётся без изменения, а
\verb|main| и \verb|binsearch| нужно модифицировать.

\begin{LongCodePar}
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
int getword(char *, int);
struct key *binsearch(char *, struct key *, int);

/* подсчёт ключевых слов Си; версия с указателями */
main()
{
    char word[MAXWORD];
    struct key *p;
    while (getword(word, MAXWORD) != EOF)
        if (isalpha(word[0]))
            if ((p=binsearch(word, keytab, NKEYS)) != NULL)
                p->count++;
    for (p = keytab; p < keytab + NKEYS; p++)
        if (p->count > 0)
            printf("%4d %s\n", p->count, p->word);
    return 0;
}

/* binsearch: найти слово в tab[0]...tab[n-1] */
struct key *binsearch(char *word, struct key *tab, int n)
{
    int cond;
    struct key *low = &tab[0];
    struct key *high = &tab[n];
    struct key *mid;
    while (low < high) {
        mid = low + (high-low) / 2;
        if ((cond = strcmp(word, mid->word)) < 0)
            high = mid;
        else if (cond > 0)
            low = mid + 1;
        else
            return mid;
    }
    return NULL;
}
\end{LongCodePar}

Некоторые детали этой программы требуют пояснений. Первое, описание функции
\verb|binsearch| должно отражать тот факт, что она возвращает указатель на
\verb|struct key|, а не целое; соответствующие изменения коснулись как прототипа
функции, так и её заголовка. Если \verb|binsearch| находит слово, то она выдаёт
указатель на него, в противном случае она возвращает \verb|NULL|.
\index{указатели!арифметика с}%
Второе, к элементам \verb|keytab| доступ осуществляется в нашей программе через
указатели. Это потребовало значительных изменений в \verb|binsearch|.
Инициализаторами для \verb|low| и \verb|high| теперь служат указатели на начало
и на место сразу после конца массива.
\index{неправильная арифметика с указателями}%
\index{сравнение указателей}%
\index{указатели!неправильная арифметика с}%
\index{указатели!сравнение}%
Вычисление положения среднего элемента с помощью формулы

\begin{ShortCodePar}
mid = (low+high) / 2        /* НЕВЕРНО */
\end{ShortCodePar}

\noindent не годится, поскольку указатели нельзя складывать.
\index{вычитание из указателя}%
\index{указатели!вычитание}%
Однако к ним можно применить операцию вычитания, и так как \verb|high-low| есть
число элементов, присваивание

\begin{ShortCodePar}
mid = low + (high-low) / 2
\end{ShortCodePar}

\noindent установит в \verb|mid| указатель на элемент, лежащий посередине между 
\verb|low| и \verb|high|.

Самое важное при переходе на новый вариант программы -- сделать так, чтобы не
генерировались неправильные указатели и не было попыток обращений за пределы
массива. Проблема в том, что и \verb|&tab[-1]|, и \verb|&tab[n]| находятся вне
границ массива. Первый адрес определённо неверен, нельзя также осуществить
доступ и по второму адресу. По правилам языка, однако, гарантируется, что адрес
ячейки памяти, следующей сразу за концом массива (т.е. \verb|&tab[n]|), в
арифметике с указателями воспринимается правильно.

В главной программе мы написали

\begin{ShortCodePar}
for (p = keytab; p < keytab + NKEYS; p++)
\end{ShortCodePar}

\noindent%
\index{масштабирование целых в арифметике с указателями}%
\index{структура!размер}%
\index{указатели!коэффициент домножения целых в арифметике с}%
Если \verb|p| -- указатель на структуру, то при выполнении операций с \verb|p|
учитывается размер структуры. Поэтому \verb|p++| увеличит \verb|p| на такую
величину, чтобы выйти на следующий структурный элемент массива, а проверка
условия вовремя остановит цикл.

Не следует, однако, полагать, что размер структуры равен сумме размеров её
членов. Вследствие
\index{выравнивание!ограничения по}%
выравнивания объектов разной длины в структуре могут появляться безымянные
<<дыры>>. Так, например, если переменная типа \verb|char| занимает один байт, а
\verb|int| -- четыре байта, то для структуры

\begin{ShortCodePar}
struct {
    char c;
    int i;
};
\end{ShortCodePar}

\noindent может потребоваться восемь байт, а не пять. Оператор \verb|sizeof|
возвращает правильное значение. 

\index{программа!формат}%
Наконец, несколько слов относительно формата программы. Если функция возвращает
значение сложного типа, как, например, в нашем случае указатель на структуру:

\begin{ShortCodePar}
struct key *binsearch(char *word, struct key *tab, int n)
\end{ShortCodePar}

\noindent то имя функции <<высмотреть>> оказывается совсем не просто. В таких
случаях иногда пользуются записью вида:

\begin{ShortCodePar}
struct key *
binsearch(char *word, struct key *tab, int n)
\end{ShortCodePar}

\noindent Какой форме отдать предпочтение -- дело вкуса. Выберите ту, которая
больше всего вам нравится.

\section{Структуры со ссылками на себя}
\label{sec:self_reference_structures}

\index{программа!подсчёта!слов}%
\index{структура!ссылающаяся на себя}%
Предположим, что мы хотим решить более общую задачу -- написать программу,
подсчитывающую частоту встречаемости для \emph{любых} слов входного потока. Так
как список слов заранее не известен, мы не можем предварительно упорядочить его
и применить бинарный поиск. Было бы неразумно пользоваться и линейным поиском
каждого полученного слова, чтобы определять, встречалось оно ранее или нет -- в
этом случае программа работала бы слишком медленно. (Более точная оценка: время
работы такой программы пропорционально квадрату количества слов.) Как можно
организовать данные, чтобы эффективно справиться со списком произвольных слов?

Один из способов -- постоянно поддерживать упорядоченность уже полученных слов,
помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся
упорядоченность. Делать это передвижкой слов в линейном массиве не следует, --
хотя бы потому, что указанная процедура тоже слишком долгая. Вместо этого мы
воспользуемся структурой данных, называемой
\index{бинарное дерево}%
\index{дерево!бинарное}%
\emph{бинарным деревом}.

В дереве на каждое отдельное слово предусмотрен <<узел>>, который содержит:

\begin{ShortCodeParWithCC}{\\\{\}}
\textit{указатель на текст слова}
\textit{счётчик числа встречаемости}
\textit{указатель на левый сыновний узел}
\textit{указатель на правый сыновний узел}
\end{ShortCodeParWithCC}

\noindent У каждого узла может быть один или два сына, или узел вообще может не
иметь сыновей.

Узлы в дереве располагаются так, что по отношению к любому узлу левое поддерево
содержит только те слова, которые лексикографически меньше, чем слово данного
узла, а правое -- слова, которые больше него. Вот как выглядит дерево,
построенное для фразы <<now is the time for all good men to come to the aid of
their party>> (<<настало время всем добрым людям помочь своей партии>>), по
завершении процесса, в котором для каждого нового слова в него добавлялся новый
узел:
%% в окружении Verbatim моноширинным шрифтом выполнено дерево так как оно было в
%% оригинале книги. Однако, такое представление выглядит неясным и невнятным,
%% поэтому ниже представлен вариант дерева выполненный в синтаксисе пакета
%% xypic. Если по какой-то причине вам ближе оригинальное представление, вы
%% можете раскомментировать окружение Verbatim и закомментировать формулу xypic.
% \begin{Verbatim}[samepage=true,xleftmargin=\codeIndent]
%                now
%               /   \
%            is     the
%           / \     /   \
%        for  men of     time
%       /   \      \     /  \
%     all  good  party their to
%    /   \
% aid    come
% \end{Verbatim}

{\small
$$
\xymatrix@C=.5em{
&&&&&\text{now}\ar@{-}[dll]\ar@{-}[drr]&&&&\\
&&&\text{is}\ar@{-}[dl]\ar@{-}[dr]&&&&\text{the}\ar@{-}[dll]\ar@{-}[dr]&&\\
&&\text{for}\ar@{-}[dl]\ar@{-}[dr]&&\text{men}&
    \text{of}\ar@{-}[dr]&&&\text{time}\ar@{-}[dl]\ar@{-}[dr]&\\
&\text{all}\ar@{-}[dl]\ar@{-}[dr]&&\text{good}&&&
    \text{party}&\text{their}&&\text{to}\\
\text{aid}&&\text{come}&&&&&&&
}
$$
}

\noindent Чтобы определить, помещено ли уже в дерево вновь поступившее слово,
начинают с корня, сравнивая это слово со словом из корневого узла. Если они
совпали, то ответ на вопрос -- положительный. Если новое слово меньше слова из
дерева, то поиск продолжается в левом поддереве‚ если больше‚ то -- в правом.
Если же в выбранном направлении поддерева не оказалось, то этого слова в дереве
нет, а пустующая ссылка, говорящая об отсутствии поддерева, как раз то место,
куда нужно <<подвесить>> узел с новым словом.
\index{рекурсия}%
Описанный процесс по сути рекурсивен, так как поиск в любом узле использует
результат поиска в одном из своих сыновних узлов. В соответствии с этим для
добавления узла и печати дерева здесь наиболее естественно применить рекурсивные
функции.

Вернёмся к описанию узла, которое удобно представить в виде структуры с четырьмя
компонентами:

\begin{ShortCodePar}
struct tnode {      /* узел дерева */
    char *word;             /* указатель на текст */
    int count;              /* число вхождений */
    struct tnode *left;     /* левый сын */
    struct tnode *right;    /* правый сын */
};
\end{ShortCodePar}

\noindent Приведённое рекурсивное определение узла может показаться рискованным,
но оно правильное. Структура не может включать саму себя, но ведь

\begin{ShortCodePar}
struct tnode *left;
\end{ShortCodePar}

\noindent определяет \verb|left| как указатель на \verb|tnode|, а не сам
\verb|tnode|.

\index{структура!ссылающаяся на себя}%
\index{структуры взаимно рекурсивные}%
Иногда возникает потребность во взаимоссылающихся структурах: двух структурах,
ссылающихся друг на друга. Приём, позволяющий справиться с этой задачей,
демонстрирует следующий фрагмент:

\begin{LongCodePar}
struct t {
    ...
    struct s *p;     /* p указывает на s */
};
struct s {
    ...
    struct t *q;     /* q указывает на t */
};
\end{LongCodePar}

Вся программа удивительно мала -- правда, она использует вспомогательные
программы типа \verb|getword|, уже написанные нами.
\index{функция!addtree@\texttt{addtree}}%
Главная программа читает слова с помощью \verb|getword| и  вставляет их в дерево
посредством \verb|addtree|.

\begin{LongCodePar}
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAXWORD 100
struct tnode *addtree(struct tnode *, char *);
void treeprint(struct tnode *);
int getword(char *, int);
/* подсчёт частоты встречаемости слов */
main()
{
    struct tnode *root;
    char word[MAXWORD];
    root = NULL;
    while (getword(word, MAXWORD) != EOF)
        if (isalpha(word[0]))
            root = addtree(root, word);
    treeprint(root);
    return 0;
}
\end{LongCodePar}

Функция \verb|addtree| рекурсивна. Первое слово функция \verb|main| помещает на
верхний уровень дерева (корень дерева). Каждое вновь поступившее слово
сравнивается со словом узла и <<погружается>> или в левое, или в правое
поддерево с помощью рекурсивного обращения к \verb|addtree|. Через некоторое
время это слово обязательно либо совпадёт с каким-нибудь из имеющихся в дереве
слов (в этом случае к счётчику будет добавлена $1$), либо программа встретит
пустую ссылку, что послужит сигналом для заведения нового узла и добавления его
к дереву. Создание нового узла сопровождается тем, что \verb|addtree| возвращает
на него указатель, который вставляется в узел родителя.

\begin{LongCodePar}
struct tnode *talloc(void);
char *strdup(char *);
/* addtree: добавляет узел со словом w в p или ниже него */
struct tnode *addtree(struct tnode *p, char *w)
{
    int cond;
    if (p == NULL) {        /* слово встречается впервые */
        p = talloc();       /* создаётся новый узел */
        p->word = strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    } else if ((cond = strcmp(w, p->word)) == 0)
        p->count++;         /* это слово уже встречалось */
    else if (cond < 0)      /* < корня левого поддерева */
        p->left = addtree(p->left, w);
    else                    /* > корня правого поддерева */
        p->right = addtree(p->right, w);
    return p;
}
\end{LongCodePar}

Память для нового узла запрашивается с помощью программы \verb|talloc|, которая
возвращает указатель на свободное пространство, достаточное для хранения одного
узла дерева, а копирование нового слова в отдельное место памяти осуществляется
с помощью \verb|strdup|. (Мы рассмотрим эти программы чуть позже.) В тот (и
только в тот) момент, когда к дереву подвешивается новый узел, происходит
инициализация счётчика и заполнение пустыми ссылками указателей на сыновей. Мы
опустили (что неразумно) контроль ошибок, который должен выполняться при
получении значений от \verb|strdup| и \verb|talloc|.

\index{функция!treeprint@\texttt{treeprint}}%
Функция \verb|treeprint| печатает дерево в лексикографическом порядке; для
каждого узла она печатает его левое поддерево (все слова, которые меньше слова
данного узла), затем само слово и, наконец, правое поддерево (слова, которые
больше слова данного узла).

\begin{LongCodePar}
/* treeprint: упорядоченная печать дерева p */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}
\end{LongCodePar}

\index{рекурсия}%
Если вы не уверены, что досконально разобрались в том, как работает рекурсия,
<<проиграйте>> действия \verb|treeprint| на дереве, приведённом выше.

\index{эффективность}%
Практическое замечание: если дерево <<несбалансировано>> (что бывает, когда
слова поступают не в случайном порядке), то время работы программы может сильно
возрасти. Худший вариант, когда слова уже упорядочены; в этом случае затраты на
вычисления будут такими же, как при линейном поиске. Существуют обобщения
бинарного дерева, которые не страдают этим недостатком, но здесь мы их не
описываем.

\index{память!распределитель}%
\index{распределитель памяти}%
Прежде чем окончательно оставить этот пример, стоит сделать краткое отступление
от темы и поговорить о механизме запроса памяти. Очевидно, хотелось бы иметь
всего лишь одну функцию, выделяющую память, даже если эта память предназначается
для разного рода объектов. Но если одна и та же функция обеспечивает память,
скажем, и для указателей на \verb|char|, и для указателей на 
\verb|struct tnode|, то возникают два вопроса. Первый, как справиться с
требованием большинства машин, в которых объекты определённого типа должны быть
выровнены (например, целые часто должны размещаться, начиная с чётных адресов)?
И второе, как описать функцию, которая вынуждена в качестве результата выдавать
указатели разных типов?

\index{выравнивание!ограничения по}%
Вообще говоря, требования, касающиеся выравнивания, можно легко выполнить за
счёт некоторой потери памяти. Однако для этого возвращаемый указатель должен
быть таким, чтобы удовлетворялись любые ограничения, связанные с выравниванием.
Функция \verb|alloc|, описанная в гл.~\ref{chapt:pointers_and_arrays}, не
гарантирует нам любое конкретное выравнивание, поэтому мы будем пользоваться
\index{библиотечная функция!malloc@\texttt{malloc}}%
функцией \verb|malloc| из стандартной библиотеки, которая это делает. В
гл.~\ref{chapt:unix_system_interface} мы покажем один из способов её реализации.

\index{оператор!приведения к типу}%
Вопрос об описании типа таких функций, как \verb|malloc|, является камнем
преткновения в любом языке с жёсткой проверкой типов. В Си вопрос решается
естественным образом: \verb|malloc| объявляется как функция, которая возвращает
указатель на \verb|void|.
\index{преобразование!указателя}%
\index{указатель!преобразование}%
Полученный указатель затем явно приводится к желаемому типу. Описания
\verb|malloc| и связанных с ней функций находятся в стандартном головном файле
\verb|<stdlib.h>|.
\index{функция!talloc@\texttt{talloc}}%
Таким образом, функцию \verb|talloc| можно записать следующим образом:

\begin{ShortCodePar}
#include <stdlib.h>
/* talloc: создаёт tnode */
struct tnode *talloc(void)
{
    return (struct tnode *) malloc(sizeof(struct tnode));
}
\end{ShortCodePar}

\index{функция!strdup@\texttt{strdup}}%
Функция \verb|strdup| просто копирует стринг, указанный в аргументе, в место,
полученное с помощью \verb|malloc|:

\begin{LongCodePar}
char *strdup(char *s)  /* дублирует s */
{
    char *p;
    p = (char *) malloc(strlen(s)+1);    /* +1 для '\0' */
    if (p != NULL)
        strcpy(p, s);
    return p;
}
\end{LongCodePar}

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

Память, полученную с помощью \verb|malloc|, можно освободить для повторного
использования, обратившись к функции
\verb|free|~(см.~гл.~\ref{chapt:input-output}~и~\ref{chapt:unix_system_interface}).

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

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

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

\section{Просмотр таблиц}

\index{программа!поиска!в таблице}%
В этом разделе, чтобы проиллюстрировать новые аспекты применения структур, мы
напишем ядро пакета программ, осуществляющих вставку элементов в таблицы и их
поиск внутри таблиц. Этот пакет -- типичный набор программ, с помощью которых
работают с таблицами имён в любом макропроцессоре или компиляторе. Рассмотрим,
например, инструкцию \verb|#define|. Когда встречается строка вида

\begin{ShortCodePar}
#define  IN  1
\end{ShortCodePar}

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

\begin{ShortCodePar}
state = IN;
\end{ShortCodePar}

\noindent оно должно быть заменено на \verb|1|.

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

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

\begin{figure}[H]
\center{\includegraphics[width=0.5762712\linewidth]{chapt6_sec6_img0.eps}}
\end{figure}

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

\begin{ShortCodePar}
struct nlist {      /* элемент таблицы */
    struct nlist *next;     /* ук-ль на следующий элемент */
    char *name;             /* определяемое имя */
    char *defn;             /* замещающий текст */
};
\end{ShortCodePar}
%
% добавлены завершающие ``;''
% в оригинале их нет
%

\noindent А вот как записывается определение массива указателей:

\begin{ShortCodePar}
#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* таблица ук-лей */
\end{ShortCodePar}

\index{функция!hash@\texttt{hash}}%
Хэш-функция, используемая в \verb|lookup| и \verb|install|, суммирует коды литер
имени, тем самым <<замешивая>> их, и в качестве результата выдаёт остаток от
деления полученной суммы на размер массива указателей. Это не самый лучший
способ получения хэш-кода, но достаточно лаконичный и эффективный.

\begin{LongCodePar}
/* hash: получает хэш-код по стрингу s */
unsigned hash(char *s)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;
    return hashval % HASHSIZE;
}
\end{LongCodePar}

\noindent Беззнаковая арифметика гарантирует, что хэш-код будет неотрицательным.

\index{hash-таблица}%
Хэширование порождает стартовый индекс для массива \verb|hashtab|; если
соответствующий стринг в таблице есть, он может быть обнаружен только в списке
блоков, на начало которого указывает элемент массива \verb|hashtab| с этим
индексом.
\index{функция!lookup@\texttt{lookup}}%
Поиск осуществляется с помощью \verb|lookup|. Если \verb|lookup| находит элемент
с заданным стрингом, то он возвращает указатель на него, если не находит, то
возвращает \verb|NULL|.

\begin{LongCodePar}
/* 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;            /* не нашли */
}
\end{LongCodePar}

\noindent В \verb|for|-цикле функции \verb|lookup| для просмотра списка
используется стандартная конструкция

\begin{ShortCodePar}
for (ptr = head; ptr != NULL; ptr = ptr->next)
    ...
\end{ShortCodePar}

\index{функция!install@\texttt{install}}%
Функция \verb|install| обращается к \verb|lookup|, чтобы определить, имеется ли
в наличии вставляемый стринг. Если это так, то старое определение будет заменено
новым. В противном случае будет образован новый элемент. Если запрос памяти для
нового элемента не может быть удовлетворён, функция \verb|install| выдаёт
\verb|NULL|.

\begin{LongCodePar}
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;
}
\end{LongCodePar}
%
% исправлена опечатка в оригинале не хватает закрывающей скобки
% if ((np = (lookup(name)) == NULL) {  /* не найден */
%

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

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

\section{Средство \texorpdfstring{\protect\Verb|typedef|}{typedef}}
\label{sec:typedef}

\index{декларация!typedef@\texttt{typedef}}%
\index{typedef-декларация@\texttt{typedef}-декларация}%
Язык Си предоставляет средство, называемое \verb|typedef|, позволяющее давать
новые имена типам данных. Например, декларация

\begin{ShortCodePar}
typedef int Length
\end{ShortCodePar}

\noindent делает имя \verb|Length| синонимом \verb|int|. С этого момента тип
\verb|Length| можно применять в декларациях, в операторе приведения и т.д. точно
так же, как тип \verb|int|:

\begin{ShortCodePar}
Length len, maxlen;
Length *lengths[];
\end{ShortCodePar}

\noindent Аналогично декларация

\begin{ShortCodePar}
typedef char *String
\end{ShortCodePar}

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

\begin{ShortCodePar}
String p, lineptr[MAXLINES], alloc(int);
int strcmp(String, String);
p = (String) malloc(100);
\end{ShortCodePar}

Заметим, что объявляемый в \verb|typedef| тип стоит на месте имени переменной в
обычной декларации, а не сразу за словом \verb|typedef|. С точки зрения
синтаксиса слово \verb|typedef| занимает место, где обычно располагается
спецификатор класса памяти -- \verb|extern|, \verb|static| и т.д. Имена типов
записаны с заглавных букв для того, чтобы они выделялись.

Для демонстрации более сложных примеров применения \verb|typedef| воспользуемся
этим средством при задании узлов деревьев, с которыми мы уже встречались в
данной главе.

\begin{ShortCodePar}
typedef struct tnode *Treeptr;
typedef struct node { /* узел дерева: */
    char *word;             /* указатель на текст */
    int count;              /* число вхождений */
    Treeptr left;           /* левый сын */
    Treeptr right;          /* правый сын */
} Treenode;
\end{ShortCodePar}

\noindent В результате создаются два новых названия типов: \verb|Treenode|
(структура) и \verb|Treeptr| (указатель на структуру).
\index{функция!talloc@\texttt{talloc}}%
Теперь программу \verb|talloc| можно записать в следующем виде:

\begin{ShortCodePar}
Treeptr talloc(void)
{
    return (Treeptr) malloc(sizeof(Treenode));
}
\end{ShortCodePar}

Следует подчеркнуть, что декларация \verb|typedef| не создаёт новый тип, она
лишь сообщает новое имя уже существующего типа. Никакого нового смысла эти новые
имена не несут, они декларируют переменные в точности с теми же свойствами, как
если бы они были объявлены напрямую без переименования типа. Фактически
\verb|typedef| аналогичен \verb|#define| с тем лишь отличием, что, будучи
интерпретируемым компилятором, он может справиться с такой текстовой
подстановкой, которая не может быть обработана препроцессором.
\index{указатель!на функцию}%
\index{функция!указатель на}%
Например,

\begin{ShortCodePar}
typedef int (*PHI)(char *, char *);
\end{ShortCodePar}

\noindent определяет тип \verb|PHI| как <<указатель на функцию (двух аргументов
типа \verb|char *|), возвращающую \verb|int|>>, который, например, в программе
сортировки, описанной в гл.~\ref{chapt:pointers_and_arrays}, можно использовать
в таком контексте:

\begin{ShortCodePar}
PHI strcmp, numcmp;
\end{ShortCodePar}

\index{переносимость}%
Помимо просто эстетических соображений, для привлечения \verb|typedef|
существуют две важные причины. Первая -- параметризация программы, связанная с
проблемой переносимости. Если с помощью \verb|typedef| объявить типы данных,
которые, возможно, являются машинно-зависимыми, то при переносе программы на
другую машину потребуется внести изменения только в определения \verb|typedef|.
Одна из распространённых ситуаций -- использование \verb|typedef|-имён для
варьирования целыми величинами.
\index{size{\_}t@\texttt{size{\_}t}}%
Для каждой конкретной машины это предполагает соответствующие установки
\verb|short|, \verb|int| или \verb|long|, которые делаются аналогично установкам
стандартных типов, например, \verb|size_t| и \verb|ptrdiff_t|.

\index{программа!читаемость}%
Вторая причина, побуждающая к применению \verb|typedef|, -- желание сделать
более ясным текст программы. Тип, названный \verb|Treeptr| (от английских слов
tree -- дерево и pointer -- указатель) более понятен, чем тот же тип, записанный
как указатель на некоторую сложную структуру.

\section{Объединения}

\index{декларация!union@\texttt{union}}%
\index{union@\texttt{union}!декларация}%
\emph{Объединение} -- это переменная, которая может содержать (в разные моменты
времени) объекты различных типов и размеров. Все требования относительно
размеров и
\index{выравнивание!ограничения по}%
выравнивания выполняет компилятор.
\index{переносимость}%
Объединения позволяют хранить разнородные данные в одной и той же области памяти
без включения в программу машинно-зависимой информации. Эти средства аналогичны
вариантным записям в Паскале.

Примером использования объединений мог бы послужить сам компилятор, заведующий
таблицей символов, если предположить, что константы могут иметь тип \verb|int|,
\verb|float| или являться указателем на стринговый литерал и иметь тип
\verb|char *|. Значение каждой конкретной константы должно храниться в
переменной соответствующего этой константе типа. Работать с таблицей символов
всегда удобнее, если значения занимают одинаковую по объёму память и
запоминаются в одном и том же месте независимо от своего типа. Цель введения в
программу объединения -- иметь переменную, которая бы на законных основаниях
хранила в себе значения нескольких типов. Синтаксис объединений аналогичен
синтаксису структур. Приведём пример объединения.

\begin{ShortCodePar}
union u_tag {
    int ival;
    float fval;
    char *sval;
} u;
\end{ShortCodePar}

Переменная \verb|u| будет достаточно большой, чтобы в ней поместилась любая
переменная из указанных трёх типов; точный её размер зависит от реализации.
Значение одного из этих трёх типов может быть присвоено переменной \verb|u| и
далее использовано в выражениях, если это правомерно, т.е. если тип взятого ею
значения совпадает с типом последнего присвоенного ей значения. Выполнение этого
требования в каждый текущий момент -- целиком на совести программиста. В случае
<<рассогласованности>> типов результат зависит от реализации.

Синтаксис доступа к членам объединения следующий:

\begin{ShortCodeParWithCC}{\\\{\}}
\textit{имя-объединения} . \textit{член}
\end{ShortCodeParWithCC}

\noindent или

\begin{ShortCodeParWithCC}{\\\{\}}
\textit{указатель-на-объединение} -> \textit{член}
\end{ShortCodeParWithCC}

\noindent т.е. в точности такой, как в структурах. Если для хранения типа
текущего значения \verb|u| использовать, скажем, переменную \verb|utype|, то
можно написать такой фрагмент программы:

\begin{LongCodePar}
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);
else
    printf(”неверный тип %d в utype\n”, utype);
\end{LongCodePar}

Объединения могут входить в структуры и массивы, и наоборот. Запись доступа к
члену объединения, находящегося в структуре (как и структуры, находящейся в
объединении), такая же, как и для вложенных структур. Например, в массиве
структур

\begin{LongCodePar}
struct {
    char *name;
    int flags;
    int utype;
    union {
        int ival;
        float fval;
        char *sval;
    } u;
} symtab[NSYM];
\end{LongCodePar}

\noindent на \verb|ival| ссылаются следующим образом:

\begin{ShortCodePar}
symtab[i].u.ival
\end{ShortCodePar}

\noindent а к первой литере стринга \verb|sval| можно обратиться любым из
следующих двух способов:

\begin{ShortCodePar}
*symtab[i].u.sval
symtab[i].u.sval[0]
\end{ShortCodePar}

Фактически объединение -- это структура, все члены которой имеют нулевое
смещение относительно её базового адреса, размера, который позволяет поместиться
в ней самому большому её члену, и
\index{выравнивание!при помощи \texttt{union}}%
\index{union@\texttt{union}!выравнивание при помощи}%
выравнивание которой удовлетворяет всем типам объединения.
\index{операции над!объединениями}%
Операции, применимые к структурам, годятся и для объединений, т.е. законны
присваивание объединения и копирование его как единого целого, взятие адреса от
объединения и доступ к отдельным его членам.

Инициализировать объединение можно только значением, имеющим тип его первого
члена; таким образом, упомянутую выше переменную \verb|u| можно инициализировать
лишь значением типа \verb|int|.

В гл.~\ref{chapt:unix_system_interface} (на примере программы, заведующей
выделением памяти) мы покажем, как, применяя объединение, можно добиться, чтобы
расположение переменной было выровнено по соответствующей границе в памяти.

\section{Поля битов}

\index{битовое поле}%
\index{биты, образцы манипулирования}%
При дефиците памяти может возникнуть необходимость запаковать несколько объектов
в одно слово машины. Одна из обычных ситуаций, встречающаяся в задачах обработки
таблиц символов для компиляторов, -- это объединение групп однобитовых флажков.
Форматы некоторых данных могут от нас вообще не зависеть и диктоваться,
например, интерфейсами с аппаратурой внешних устройств; здесь также возникает
потребность адресоваться к частям слова.

Вообразим себе фрагмент компилятора, который заведует таблицей символов. Каждый
идентификатор программы имеет некоторую связанную с ним информацию, которая
сообщает, например, представляет ли он собой ключевое слово и к какому классу,
если это переменная, она принадлежит: внешняя и/или статическая и т.д. Самый
компактный способ кодирования такой информации -- расположить однобитовые флажки
в одном слове типа \verb|char| или \verb|int|.

\index{define@\texttt{{\#}define}!вместо \texttt{enum}}%
\index{enum@\texttt{enum}!а не \texttt{{\#}define}}%
Один из распространённых приёмов работы с битами основан на определении набора
<<масок>>, соответствующих позициям этих битов, как, например, в 

\begin{ShortCodePar}
#define KEYWORD  01        /* ключевое слово */
#define EXTERNAL 02        /* внешний */
#define STATIC   04        /* статический */
\end{ShortCodePar}

\noindent или в

\begin{ShortCodePar}
enum { KEYWORD = 01, EXTERNAL = 02, STATIC = 04 };
\end{ShortCodePar}

\noindent Числа должны быть степенями двойки. Тогда доступ к битам становится
делом <<побитовых операций>>, описанных в
гл.~\ref{chapt:types-operators-expressions} (сдвиг, маскирование, взятие
дополнения).

Некоторые виды записи выражений встречаются довольно часто. Так,

\begin{ShortCodePar}
flags |= EXTERNAL | STATIC;
\end{ShortCodePar}

\noindent устанавливает 1 в соответствующих битах переменной \verb|flags|,

\begin{ShortCodePar}
flags &= ~(EXTERNAL | STATIC);
\end{ShortCodePar}

\noindent обнуляет их, а

\begin{ShortCodePar}
if ((flags & (EXTERNAL | STATIC)) == 0) ...
\end{ShortCodePar}

\noindent оценивает условие как истинное, если оба бита нулевые.

\index{биты, образцы манипулирования}%
Хотя научиться писать такого рода выражения не составляет труда, вместо
побитовых логических операций можно пользоваться предоставляемым Си другим
способом прямого определения и доступа к полям внутри слова.
\index{битовое поле}%
\emph{Поле-битов} (или для краткости просто \emph{поле}) -- это некоторое
множество битов, лежащих рядом внутри одной, зависящей от реализации, единице
памяти, которую мы будем называть <<словом>>.
\index{битовое поле!декларация}%
\index{декларация!поля битов}%
Синтаксис определения полей и доступа к ним базируется на синтаксисе структур.
Например, строки \verb|#define|, фигурировавшие выше при задании таблицы
символов, можно заменить на определение трёх полей:

\begin{ShortCodePar}
struct {
    unsigned int is_keyword : 1;
    unsigned int is_extern  : 1;
    unsigned int is_static  : 1;
} flags;
\end{ShortCodePar}

\noindent%
\index{выравнивание!битового поля}%
Эта запись определяет переменную \verb|flags|, которая содержит три однобитовых
поля. Число, следующее за двоеточием, задаёт ширину поля. Поля декларированы как
\verb|unsigned int|, чтобы они воспринимались как беззнаковые величины.

На отдельные поля ссылаются так же, как и на члены обычных структур:
\verb|flags.is_keyword|, \verb|flags.is_extern|, и т.д. Поля <<ведут себя>> как
малые целые и могут участвовать в арифметических выражениях точно так же, как и
другие целые. Таким образом, предыдущие примеры можно написать более
естественным образом:

\begin{ShortCodePar}
flags.is_extern = flags.is_static = 1;
\end{ShortCodePar}

\noindent устанавливает 1 в соответствующие биты;

\begin{ShortCodePar}
flags.is_extern = flags.is_static = 0;
\end{ShortCodePar}

\noindent их обнуляет, а

\begin{ShortCodePar}
if (flags.is_extern == 0 && flags.is_static == 0)
\end{ShortCodePar}

\noindent проверяет их.

Почти все технические детали, касающиеся полей, в частности, может ли поле
перейти границу слова, зависят от реализации. Поля могут не иметь имени;
\index{битовое поле!выравнивание}%
с помощью безымянного поля (задаваемого только двоеточием и шириной)
организуется пропуск нужного количества разрядов. Особая ширина, равная нулю,
используется, когда требуется выйти на границу следующего слова.

На одних машинах поля размещаются слева направо, на других -- справа налево. Это
значит, что при всей полезности работы с ними, если формат данных, с которыми мы
имеем дело, дан нам свыше, то необходимо самым тщательным образом исследовать
порядок расположения полей; программы, зависящие от такого рода вещей, не
переносимы. Поля можно определять только с типом \verb|int|, а для того, чтобы
обеспечить переносимость, явно указывая \verb|signed| или \verb|unsigned|. Они
не могут быть массивами и не имеют адресов, и, следовательно, оператор \verb|&|
к ним не применим.