\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 #include #include #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{файл!головной!@\texttt{}}% \index{size{\_}t@\texttt{size{\_}t}}% (Строго говоря, \verb|sizeof| выдаёт беззнаковое целое, тип которого \verb|size_t| определён в головном файле \verb||.) Что касается объекта, то это может быть переменная, массив или структура. В качестве имени типа может выступать имя базового типа (\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||. \paragraph{Упражнение 6.1.} Наша версия \verb|getword| не обрабатывает должным образом знак подчёркивания, стринговые константы, комментарии и управляющие строки препроцессора. Напишите более совершенный вариант программы. \section{Указатели на структуры} \index{структура!указатель на неё}% \index{указатель!на структуру}% Для иллюстрации некоторых моментов, касающихся указателей на структуры и массивов структур, перепишем программу подсчёта ключевых слов, пользуясь для получения элементов массива вместо индексов указателями. \index{функция!binsearch@\texttt{binsearch}}% Внешняя декларация массива \verb|keytab| остаётся без изменения, а \verb|main| и \verb|binsearch| нужно модифицировать. \begin{LongCodePar} #include #include #include #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 У каждого узла может быть один или два сына, или узел вообще может не иметь сыновей. Узлы в дереве располагаются так, что по отношению к любому узлу левое поддерево содержит только те слова, которые лексикографически меньше, чем слово данного узла, а правое -- слова, которые больше него. Вот как выглядит дерево, построенное для фразы <> (<<настало время всем добрым людям помочь своей партии>>), по завершении процесса, в котором для каждого нового слова в него добавлялся новый узел: %% в окружении 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 #include #include #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||. \index{функция!talloc@\texttt{talloc}}% Таким образом, функцию \verb|talloc| можно записать следующим образом: \begin{ShortCodePar} #include /* 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|&| к ним не применим.