\chapter{Указатели и массивы}
\label{chapt:pointers_and_arrays}

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

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

Изменения, внесённые стандартом ANSI, связаны в основном с формулированием
точных правил работы с указателями. Он узаконил накопленный положительный опыт
программистов и удачные нововведения разработчиков компиляторов.
\index{указатель!void *@\texttt{void *}}%
\index{void *, указатель@\texttt{void *}, указатель}%
Кроме того, взамен \verb|char *| в качестве типа обобщённого указателя
предлагается тип \verb|void *| (указатель на \verb|void|).

\section{Указатели и адреса}

\index{переменная!адрес}%
Начнём с того, что рассмотрим упрощённую схему организации памяти. Память
типичной машины представляет собой массив последовательно пронумерованных и
проадресованных ячеек, с которыми можно работать по отдельности или связными
кусками. Применительно к любой машине верны следующие утверждения: один байт
может хранить значение типа \verb|char|, двухбайтовые ячейки могут
рассматриваться как целое типа \verb|short|, а четырёхбайтовые -- как целые
типа \verb|long|. Указатель -- это группа ячеек (как правило, две или четыре),
в которых может храниться адрес. Так, если \verb|c| имеет тип \verb|char|, а
\verb|p| -- указатель, ссылающийся на \verb|c|, то ситуация выглядит следующим
образом:

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

\noindent Унарный оператор \verb|&| выдаёт адрес объекта, так что инструкция

\begin{ShortCodePar}
p = &c;
\end{ShortCodePar}

\noindent присваивает адрес ячейки \verb|c| переменной \verb|p| (говорят, что
\verb|p| указывает на \verb|c| или, что то же, \verb|p| ссылается на \verb|c|).
Оператор \verb|&| применяется только к объектам, расположенным в памяти: к
переменным и элементам массивов. Его операндом не может быть ни выражение, ни
константа, ни регистровая переменная.

\index{оператор!косвенности \texttt{*}}%
Унарный оператор \verb|*| есть оператор \emph{раскрытия ссылки}. Применённый к
указателю он выдаёт объект, на который данный указатель ссылается. Предположим,
что \verb|x| и \verb|y| -- целые, а \verb|ip| -- указатель на \verb|int|.
Следующие несколько строк придуманы специально для того, чтобы показать, каким
образом декларируются указатели и используются операторы \verb|&| и \verb|*|.

\begin{ShortCodePar}
int x = 1, y = 2, z[10];
int *ip;            /* ip - указатель на int */

ip = &x;            /* теперь ip  указывает на x */
y = *ip;            /* y теперь равен 1 */
*ip = 0;            /* x теперь равен 0 */
ip = &z[0];         /* ip теперь указывает на z[0] */
\end{ShortCodePar}

\noindent Декларации \verb|x|, \verb|y| и \verb|z| нам уже знакомы.
\index{декларация!указателя}%
\index{указатель!декларация}%
Декларацию указателя \verb|ip|

\begin{ShortCodePar}
int *ip;
\end{ShortCodePar}
мы стремились сделать мнемоничной -- она гласит: <<выражение \verb|*ip| есть
нечто типа \verb|int|>>. Синтаксис декларации переменной <<подстраивается>> под
синтаксис выражений, в которых эта переменная может встретиться. Указанный
принцип применим и в отношении описаний функций. Например, запись

\begin{ShortCodePar}
double *dp, atof(char *);
\end{ShortCodePar}

\noindent означает, что выражение \verb|*dp| и \verb|atof(s)| имеют тип
\verb|double|‚ а аргумент функции \verb|atof| есть указатель на \verb|char|.

Вы, наверное, заметили, что указателю разрешено ссылаться только на объекты
заданного типа. (Существует одно исключение: <<указатель на \verb|void|>> может
ссылаться на объекты любого типа, но к такому указателю нельзя применять
оператор раскрытия ссылки. Мы вернёмся к этому в
разд.~\ref{sec:function_pointers}.)

Если \verb|ip| ссылается на \verb|x| целого типа, то \verb|*ip| можно
использовать в любом месте, где допустимо применение \verb|x|; например,

\begin{ShortCodePar}
*ip = *ip + 10;
\end{ShortCodePar}

\noindent увеличивает \verb|*ip| на $10$.

\index{вычисление, порядок}%
\index{оператор!приоритет}%
\index{порядок!вычислений}%
\index{приоритеты операторов}%
Унарные операторы \verb|*| и \verb|&| имеют более высокий приоритет, чем
арифметические операторы, так что присваивание

\begin{ShortCodePar}
y = *ip + 1
\end{ShortCodePar}

\noindent берет то, на что указывает \verb|ip|, и добавляет к нему $1$, а
результат присваивает переменной \verb|y|. Аналогично

\begin{ShortCodePar}
*ip += 1
\end{ShortCodePar}

\noindent увеличивает на единицу то, на что ссылается \verb|ip|; те же действия
выполняют

\begin{ShortCodePar}
++*ip
\end{ShortCodePar}

\noindent и

\begin{ShortCodePar}
(*ip)++
\end{ShortCodePar}

\noindent%
\index{указатели!арифметика с}%
В последней записи скобки необходимы, поскольку, если их не будет,
увеличится значение самого указателя, а не то, на что он ссылается. Это
обусловлено тем, что унарные операторы \verb|*| и \verb|++| имеют одинаковые
приоритет и порядок выполнения -- справа налево.

И наконец, так как указатели сами являются переменными, в тексте они могут
встречаться и без оператора раскрытия ссылки. Например, если \verb|iq| есть
другой указатель на \verb|int|, то

\begin{ShortCodePar}
iq = ip
\end{ShortCodePar}

\noindent копирует содержимое \verb|ip| в \verb|iq|, чтобы \verb|ip| и \verb|iq|
ссылались на один и тот же объект.

\section{Указатели и аргументы функций}

\index{вызов!по значению}%
Поскольку функции в Си в качестве своих аргументов получают значения параметров,
прямой возможности, находясь в вызванной функции, изменить переменную вызывающей
функции нет. В программе сортировки нам понадобилась функция \verb|swap|,
переставляющая местами два неупорядоченных элемента. Однако недостаточно
написать

\begin{ShortCodePar}
swap(a, b);
\end{ShortCodePar}

\noindent где функция \verb|swap| определена следующим образом:

\begin{LongCodePar}
void swap(int x, int y)          /* НЕВЕРНО */
{
    int temp;

    temp = x;
    x = y;
    y = temp;
}
\end{LongCodePar}

\noindent Поскольку \verb|swap| получает лишь \emph{копии} значений переменных
\verb|a| и \verb|b|, она не может повлиять на переменные \verb|a| и \verb|b| той
программы, которая к ней обратилась.

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

\begin{ShortCodePar}
swap(&a, &b);
\end{ShortCodePar}

\noindent Так как оператор \verb|&| получает адрес переменной, \verb|&a| есть
указатель на \verb|a|.
\index{функция!swap@\texttt{swap}}%
В самой функции \verb|swap| параметры должны быть описаны как указатели, при
этом доступ к значениям параметров будет осуществляться через них косвенно.

\begin{LongCodePar}
void swap(int *px, int *py)  /* перестановка *px и *py */
{
    int temp;

    temp = *px;
    *px = *py;
    *py = temp;
}
\end{LongCodePar}

\noindent Графически это можно изобразить следующим образом:

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

Аргументы-указатели позволяют функции осуществлять доступ к объектам вызвавшей
её программы и дают ей возможность изменить эти объекты.
\index{функция!getint@\texttt{getint}}%
Рассмотрим, например, функцию \verb|getint|, которая осуществляет ввод в
свободном формате одного целого числа и его перевод из текстового представления
в значение типа \verb|int|. Функция \verb|getint| должна возвращать значение
полученного числа или сигнализировать значением \verb|EOF| о конце файла, если
входной поток исчерпан. Эти значения должны возвращаться по разным каналам, так
как нельзя рассчитывать на то, что полученное в результате перевода число
никогда не совпадёт с \verb|EOF|.

Одно из решений состоит в том, чтобы \verb|getint| выдавала характеристику
состояния файла (исчерпан или не исчерпан) в качестве результата, а значение
самого числа помещала согласно указателю, переданному ей в виде аргумента.
Похожая схема действует в программе \verb|scanf|, которую мы рассмотрим в
разд.~\ref{sec:formatted-input}.

Показанный ниже цикл заполняет некоторый массив целыми числами, полученными с
помощью \verb|getint|.

\begin{ShortCodePar}
int n, array[SIZE], getint(int *);
for (n = 0; n < SIZE && getint(&array[n]) != EOF; n++)
    ;
\end{ShortCodePar}

\noindent Результат каждого очередного обращения к \verb|getint| посылается в
\verb|array[n]|, и \verb|n| увеличивается на единицу. Заметим, что существенным
здесь является то, что функции \verb|getint| передаётся адрес элемента
\verb|array[n]|. Если этого не сделать, у \verb|getint| не будет способа вернуть
в вызывающую программу переведённое целое число.

В предлагаемом нами варианте функция \verb|getint| выдаёт \verb|EOF| по концу
файла; нуль, если следующие вводимые литеры не представляют собою числа; и
положительное значение, если введённые литеры есть правильное число.

\begin{LongCodePar}
#include <ctype.h>
int getch(void);
void ungetch(int);
/* getint: читает следующее целое из ввода в *pn */
int getint(int *pn)
{
    int c, sign;
    while (isspace(c = getch()))
        ;           /* пропуск пробельных литер */
    if (!isdigit(c) && c != EOF && c != '+' && c != '-') {
        ungetch(c);   /* не число */
        return 0;
    }
    sign = (c == '-') ? -1 : 1;
    if (c == '+' || c == '-')
        c = getch();
    for (*pn = 0; isdigit(c); c = getch())
        *pn = 10 * *pn + (c - '0');
    *pn *= sign;
    if (c != EOF)
        ungetch(c);
    return c;
}
\end{LongCodePar}
%
% в оригинале слева в нижнем колонтитуле надпись ``4. Заказ № 13''
%

\noindent Везде в \verb|getint| под комбинацией \verb|*pn| подразумевается
обычная переменная типа \verb|int|. Функция \verb|ungetch| вместе с \verb|getch|
(разд.~\ref{sec:external_variables}) включена в программу, чтобы обеспечить
возможность отослать назад лишнюю прочитанную литеру.
%
% исправлена опечатка. В оригинале ``влючена в программу''
%

\paragraph{Упражнение 5.1.} Функция \verb|getint| написана так, что знаки
\verb|-| или \verb|+|, за которыми не следует цифра, она понимает как
<<правильное>> представление нуля. Скорректируйте программу таким образом, чтобы
она в подобных случаях возвращала прочитанный знак назад во ввод.

\paragraph{Упражнение 5.2.} Напишите функцию \verb|getfloat| -- аналог
\verb|getint| для чисел с плавающей точкой. Какой тип будет иметь результирующее
значение, выдаваемое функцией \verb|getfloat|?

\section{Указатели и массивы}

\index{индексирование массива!и указатели|(}%
\index{массив!а не указатель|(}%
\index{указатель!а не массив|(}%
В Си существует связь между указателями и массивами, и связь эта настолько
тесная, что эти средства лучше рассматривать вместе.
\index{индексирование массива}%
\index{массив!индексирование}%
Любой доступ к элементу массива, осуществляемый операцией индексирования, может
быть выполнен при помощи указателя. Вариант с указателями в общем случае
работает быстрее, но разобраться в нём, особенно непосвящённому, довольно
трудно.

Декларация

\begin{ShortCodePar}
int a[10];
\end{ShortCodePar}

\noindent определяет массив \verb|a| размера $10$, т.е. блок из $10$
последовательных объектов с именами \verb|a[0]|‚ \verb|a[1]|‚ \ldots ‚
\verb|a[9]|.

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

\noindent Запись \verb|a[i]| отсылает нас к \verb|i|-му элементу массива. Если
\verb|pa| есть указатель на \verb|int|, т.е. определён как

\begin{ShortCodePar}
int *pa;
\end{ShortCodePar}

\noindent то в результате присваивания

\begin{ShortCodePar}
pa = &a[0];
\end{ShortCodePar}

\noindent \verb|pa| будет указывать на нулевой элемент \verb|a|; иначе говоря,
\verb|pa| будет содержать адрес элемента \verb|a[0]|.

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

\noindent Теперь присваивание

\begin{ShortCodePar}
x = *pa;
\end{ShortCodePar}

\noindent будет копировать содержимое \verb|a[0]| в \verb|x|.

\index{указатели!арифметика с}%
Если \verb|pa| указывает на некоторый элемент массива, то \verb|pa+1| по
определению указывает на следующий элемент, \verb|pa+i| -- на \verb|i|-й
элемент после \verb|pa|, а \verb|pa-i| -- на \verb|i|-й элемент перед
\verb|pa|. Таким образом, если \verb|pa| указывает на \verb|a[0]|, то

\begin{ShortCodePar}
*(pa+1)
\end{ShortCodePar}

\noindent есть содержимое \verb|a[1]|, \verb|pa+i| -- адрес \verb|a[i]|, а
\verb|*(pa+i)| -- содержимое \verb|a[i]|.

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

Сделанные замечания верны безотносительно к типу и размеру элементов массива
\verb|a|. Смысл слов <<добавить $1$ к указателю>>, как и смысл любой арифметики
с указателями, в том, чтобы \verb|pa+1| указывал на следующий объект, а
\verb|pa+i| -- на \verb|i|-й после \verb|pa|.

Между индексированием и арифметикой с указателями существует очень тесная связь.
По определению значение переменной или выражения типа массив есть адрес нулевого
элемента массива. После присваивания

\begin{ShortCodePar}
pa = &a[0];
\end{ShortCodePar}

\noindent \verb|pa| и \verb|a| имеют одно и то же значение. Поскольку имя
массива есть не что иное, как адрес его начального элемента, присваивание
\verb|pa=&a[0];| можно также записать в следующем виде:

\begin{ShortCodePar}
pa = a;
\end{ShortCodePar}

Ещё более удивительно (по крайней мере на первый взгляд) то, что \verb|a[i]|
можно записать как \verb|*(a+i)|.
\index{массив!преобразование имени}%
\index{преобразование!имени массива}%
Встречая запись \verb|a[i]|, компилятор сразу преобразует её в \verb|*(a+i)|;
указанные две формы записи эквивалентны. Из этого следует, что полученные в
результате применения оператора \verb|&| записи \verb|&a[i]| и \verb|a+i| также
будут эквивалентными, т.е. и в том и в другом случае это адрес \verb|i|-го
элемента после \verb|a|. С другой стороны, если \verb|pa| -- указатель, то в
выражениях его можно использовать с индексом, т.е. запись \verb|pa[i]|
эквивалентна записи \verb|*(pa+i)|. Элемент массива одинаково разрешается
изображать и в виде указателя со смещением и в виде имени массива с индексом.

Между именем массива и указателем, выступающим в роли имени массива, существует
одно различие. Указатель -- это переменная, поэтому можно написать
\verb|pa = a| или \verb|pa++|. Но имя массива не является переменной, и записи
типа \verb|a = pa| или \verb|a++| не допускаются.

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

\begin{LongCodePar}
/* strlen: возвращает длину стринга */
int strlen(char *s)
{
    int n;
    for (n = 0; *s != '\0'; s++)
        n++;
    return n;
}
\end{LongCodePar}

\noindent Так как переменная \verb|s| -- указатель, к нему применима операция
\verb|++|; \verb|s++| никакого влияния на стринг литер функции, которая
обратилась к \verb|strlen|‚ не оказывает. Просто увеличивается на $1$ некоторая
копия указателя, находящаяся в личном пользовании функции \verb|strlen|. Это
значит, что все вызовы типа:

\begin{ShortCodePar}
strlen("Здравствуй, мир");    /* стринговая константа */
strlen(array);                /* char array[100];  */
strlen(ptr);                  /* char *ptr;  */
\end{ShortCodePar}

\noindent законны.

\index{декларация!указателя}%
\index{параметр}%
\index{указатель!декларация}%
Записи

\begin{ShortCodePar}
char s[];
\end{ShortCodePar}

\noindent и

\begin{ShortCodePar}
char *s;
\end{ShortCodePar}

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

\index{подмассив-аргумент}%
\index{указатель!аргумент}%
Функции можно передать часть массива, для этого аргумент должен указывать на
начало подмассива. Например, если \verb|a| -- массив, то в записях

\begin{ShortCodePar}
f(&a[2])
\end{ShortCodePar}

\noindent или

\begin{ShortCodePar}
f(a+2)
\end{ShortCodePar}

\noindent функции \verb|f| передаётся адрес подмассива, начинающегося с элемента
\verb|a[2]|. Внутри функции \verb|f| описание параметров может выглядеть как

\begin{ShortCodePar}
f(int arr[]) { ... }
\end{ShortCodePar}

\noindent или

\begin{ShortCodePar}
f(int *arr) { ... }
\end{ShortCodePar}

\noindent Следовательно, для \verb|f| тот факт, что параметр ссылается на часть
массива, а не на весь массив, не имеет значения.

\index{индекс отрицательный}%
\index{отрицательные индексы}%
\index{указатели!и индексирование}%
Если есть уверенность, что элементы массива существуют, то возможно
индексирование и в <<обратную>> сторону по отношению к нулевому элементу;
выражения \verb|p[-1]|, \verb|p[-2]| и т.д. не противоречат синтаксису языка и
ссылаются на элементы, стоящие непосредственно перед \verb|p[0]|. Разумеется,
нельзя <<выходить>> за границы массива и тем самым ссылаться на несуществующие
<<объекты>>.
\index{указатель!а не массив|)}%
\index{массив!а не указатель|)}%
\index{индексирование массива!и указатели|)}%


\section{Адресная арифметика}

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

Си последователен и единообразен в своём подходе к адресной арифметике. Это
соединение в одном языке указателей, массивов и адресной арифметики -- одна из
сильных его сторон. Проиллюстрируем сказанное построением простого
распределителя памяти, состоящего из двух программ.
\index{функция!alloc@\texttt{alloc}}%
Первая, \verb|alloc(n)|‚ возвращает указатель \verb|p| на \verb|n|
последовательно расположенных ячеек типа \verb|char|; программой, обращающейся к
\verb|alloc|, эти ячейки могут быть использованы для запоминания литер.
\index{функция!afree@\texttt{afree}}%
Вторая, \verb|afree(p)|‚ освобождает память для, возможно, повторной её
утилизации. Простота алгоритма обусловлена предположением, что обращения к
\verb|afree| делаются в обратном порядке по отношению к соответствующим
обращениям к \verb|alloc|. Таким образом, память, с которой работают
\verb|alloc| и \verb|afree|, является стеком (списком, в основе которого лежит
принцип <<последним вошёл, первым ушёл>>). В стандартной библиотеке имеются
функции \verb|malloc| и \verb|free|, которые делают то же самое, только без
упомянутых ограничений; в разд.~\ref{sec:memory_allocator} мы покажем, как они
выглядят.

Функцию \verb|alloc| легче всего реализовать, если условиться, что она будет
выдавать куски некоторого большого массива типа \verb|char|, который мы назовём
\verb|allocbuf|. Этот массив отдадим в личное пользование функциям \verb|alloc|
и \verb|afree|. Так как они имеют дело с указателями, а не с индексами массива,
то другим программам знать его имя не нужно. Кроме того, этот массив можно
определить в том же исходном файле, что и \verb|alloc| и \verb|afree|, объявив
его с классификатором \verb|static|, благодаря чему он станет невидимым вне
этого файла. На практике такой массив может и вовсе не иметь имени, поскольку
его можно запросить с помощью \verb|malloc| у операционной системы и получить
указатель на некоторый безымянный блок памяти.

Естественно, нам нужно знать, сколько элементов массива \verb|allocbuf| уже
занято. Мы введём указатель \verb|allocp|, который будет указывать на первый
свободный элемент. Если запрашивается память для \verb|n| литер, то \verb|alloc|
возвращает текущее значение \verb|allocp| (т.е. адрес начала свободного блока) и
затем увеличивает его на \verb|n|, чтобы указатель \verb|allocp| ссылался на
следующую свободную область. Если же пространства нет, то \verb|alloc| выдаёт
нуль. Функция \verb|afree(p)| просто устанавливает в \verb|allocp| значение
\verb|p|, если оно не выходит за пределы массива \verb|allocbuf|.

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

\begin{LongCodePar}
#define ALLOCSIZE 10000 /* размер доступного пространства */
static char allocbuf[ALLOCSIZE];   /* память для alloc */
static char *allocp = allocbuf;    /* ук-ль на своб. место */

char *alloc(int n)  /* возвращает указатель на n литер */
{
    if (allocbuf + ALLOCSIZE - allocp >= n) {
        allocp += n;        /* пространство есть */
        return allocp - n;  /* старое p */
    } else                  /* пространства нет */
        return 0;
}

void afree(char *p)  /* освобождается память по ук-лю p */
{
    if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
        allocp = p;
}
\end{LongCodePar}

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

\begin{ShortCodePar}
static char *allocp = allocbuf;
\end{ShortCodePar}

\noindent определяет \verb|allocp| как указатель на \verb|char| и инициализирует
его адресом массива \verb|allocbuf|, поскольку перед началом работы программы
массив \verb|allocbuf| пуст. Указанная декларация могла бы иметь и такой вид:

\begin{ShortCodePar}
static char *allocp = &allocbuf[0];
\end{ShortCodePar}

\noindent поскольку имя массива и есть адрес его нулевого элемента.

Проверка

\begin{ShortCodePar}
if (allocbuf + ALLOCSIZE - allocp >= n) {
\end{ShortCodePar}

\noindent контролирует, достаточно ли пространства, чтобы удовлетворить запрос
на \verb|n| литер. Если памяти достаточно, то новое значение для \verb|allocp|
должно указывать не далее чем на следующую позицию за последним элементом
\verb|allocbuf|. При выполнении этого требования \verb|alloc| выдаёт указатель
на начало выделенного блока литер (обратите внимание на описание типа самой
функции). Если требование не выполняется, функция \verb|alloc| должна выдать
какой-то сигнал о том, что памяти не хватает. Си гарантирует, что нуль никогда
не будет правильной ссылкой на данные, поэтому мы будем использовать его в
качестве признака аварийного события, в нашем случае нехватки памяти.

\index{неправильная арифметика с указателями}%
\index{указатели!неправильная арифметика с}%
\index{указатели!операция над}%
\index{указатели!сравнение}%
Указатели и целые не являются взаимозаменяемыми объектами.
\index{указатель!пустой}%
\index{null-указатель}%
Константа нуль -- единственное исключение из этого правила: её можно присвоить
указателю, и указатель можно сравнить с нулевой константой.
\index{файл!головной!<stdio.h>@\texttt{<stdio.h>}}%
\index{NULL@\texttt{NULL}}%
\index{stdio.h@\texttt{<stdio.h>}}%
Чтобы показать, что нуль -- это специальное значение для указателя, вместо цифры
нуль, как правило, записывают \verb|NULL| -- константу, определённую в файле
\verb|<stdio.h>|. С этого момента и мы будем ею пользоваться.

Проверки

\begin{ShortCodePar}
if (allocbuf + ALLOCSIZE - allocp >= n) {
\end{ShortCodePar}

\noindent и

\begin{ShortCodePar}
if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
\end{ShortCodePar}

\noindent демонстрируют несколько важных свойств арифметики с указателями.
\index{операции над!указателями}%
\index{сравнение указателей}%
Во-первых, при соблюдении некоторых правил указатели можно сравнивать. Если
\verb|p| и \verb|q| указывают на элементы одного массива, то к ним можно
применять операторы отношения \verb|==|, \verb|!=|, \verb|<|, \verb|>=| и т.д.
Например, отношение вида

\begin{ShortCodePar}
p < q
\end{ShortCodePar}

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

Во-вторых, как вы уже, наверное, заметили, указатели и целые можно складывать и
вычитать. Запись вида

\begin{ShortCodePar}
p + n
\end{ShortCodePar}

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

\index{вычитание из указателя}%
\index{указатели!вычитание}%
Допускается также вычитание указателей. Например, если \verb|p| и \verb|q|
ссылаются на элементы одного массива и \verb|p < q|, то \verb|q - p + 1| есть
число элементов от \verb|p| до \verb|q| включительно.
\index{стринг!длина}%
\index{функция!strlen@\texttt{strlen}}%
Этим фактом можно воспользоваться при написании ещё одной версии \verb|strlen|:

\begin{LongCodePar}
/* strlen: возвращает длину стринга s */
int strlen(char *s)
{
    char *p = s;
    while (*p != '\0')
        p++;
    return p - s;
}
\end{LongCodePar}

\noindent В своём определении \verb|p| инициализируется значением \verb|s|, т.е.
вначале \verb|p| указывает на первую литеру стринга. На каждом шаге цикла
\verb|while| проверяется очередная литера; цикл продолжается до тех пор, пока не
встретится \verb|'\0'|. Каждое продвижение указателя \verb|p| на следующую
литеру выполняется инструкцией \verb|p++|, и разность \verb|p-s| даёт число
пройденных литер, т.е. длину стринга. (Число литер в стринге может быть слишком
большим, чтобы хранить его в переменной типа \verb|int|.
\index{файл!головной!<stddef.h>@\texttt{<stddef.h>}}%
\index{ptrdiff{\_}t@\texttt{ptrdiff{\_}t}}%
Тип \verb|ptrdiff_t|, достаточный для хранения разности (со знаком) двух
указателей, определён в головном файле \verb|<stddef.h>|.
\index{size{\_}t@\texttt{size{\_}t}}%
Однако, если быть очень осторожными, нам следовало бы для возвращаемого
результата использовать тип \verb|size_t|‚ в этом случае наша программа
соответствовала бы стандартной библиотечной версии.
\index{оператор!sizeof@\texttt{sizeof}}%
Тип \verb|size_t| есть тип беззнакового целого, возвращаемого оператором
\verb|sizeof|.)

\index{неправильная арифметика с указателями}%
\index{указатели!коэффициент домножения целых в арифметике с}%
\index{указатели!неправильная арифметика с}%
Арифметика с указателями учитывает тип: если она имеет дело со значениями
\verb|float|, занимающими больше памяти, чем \verb|char|, и \verb|p| --
указатель на \verb|float|, то \verb|p++| продвинет \verb|p| на следующее
значение \verb|float|. Это значит, что другую версию \verb|alloc|, которая имеет
дело с элементами типа \verb|float|, а не \verb|char|, можно получить простой
заменой в \verb|alloc| и \verb|afree| всех \verb|char| на \verb|float|. Все
операции с указателями будут автоматически откорректированы в соответствии с
размером объектов, на которые ссылаются указатели.

\index{неправильная арифметика с указателями}%
\index{указатели!неправильная арифметика с}%
Допускаются следующие операции с указателями: присваивание значения указателя
другому указателю того же типа, сложение и вычитание указателя и целого,
вычитание и сравнение двух указателей, ссылающихся на элементы одного и того же
массива, а также присваивание указателю нуля и сравнение указателя с нулём. Все
другие операции с указателями не допускаются. Нельзя складывать два указателя,
перемножать их, делить, сдвигать, выделять разряды; указатель нельзя складывать
со значением типа \verb|float| или \verb|double|;
\index{указатель!void *@\texttt{void *}}%
\index{void *, указатель@\texttt{void *}, указатель}%
указателю одного типа нельзя даже присвоить указатель другого типа, не выполнив
предварительно операции приведения (исключение составляют лишь указатели типа
\verb|void *|).
\index{указатели!арифметика с|)}%


\section{Литерные указатели и функции}

\index{массив!литер}%
\index{константа!стринговая}%
\emph{Стринговая константа}, написанная в виде

\begin{ShortCodePar}
"I am a string"
\end{ShortCodePar}

\noindent есть массив литер. Во внутреннем представлении этот массив
заканчивается <<пустой>> литерой \verb|'\0'|, по которой программа может найти
конец стринга. Число занятых ячеек памяти на одну больше, чем количество литер,
помещённых между двойными кавычками.

Чаще всего стринговые константы используются в качестве аргументов функций, как,
например, в

\begin{ShortCodePar}
printf("здравствуй, мир\n");
\end{ShortCodePar}
%
% в оригинале опечатка ``здраствуй''
%

\noindent Когда такой литерный стринг появляется в программе, доступ к нему
осуществляется через литерный указатель; \verb|printf| получает указатель на
начало массива литер. Точнее, доступ к стринговой константе осуществляется через
указатель на её первый элемент.

Стринговые константы нужны не только в качестве аргументов функций. Если,
например, переменную \verb|pmessage| описать как

\begin{ShortCodePar}
char  *pmessage
\end{ShortCodePar}

\noindent то присваивание

\begin{ShortCodePar}
pmessage = "now is the time";
\end{ShortCodePar}

\noindent поместит в неё указатель на литерный массив, при этом сам стринг
\emph{не} копируется, копируется лишь указатель на него. Операции для работы со
стрингом как с единым целым в Си не предусмотрены.

\index{массив!а не указатель}%
\index{указатель!а не массив}%
Существует важное различие между следующими определениями:

\begin{ShortCodePar}
char amessage[] = "now is the time";  /* массив */
char *pmessage = "now is the time";   /* указатель */
\end{ShortCodePar}

\noindent \verb|amessage| -- это массив, имеющий такой объем, что в нём как раз
помещается указанная последовательность литер и \verb|'\0'|. Отдельные литеры
внутри массива могут изменяться, но \verb|amessage| всегда ссылается на одно и
то же место памяти. В противоположность ему \verb|pmessage| есть указатель,
инициализированный ссылкой на стринговую константу. А значение указателя можно
изменить, и тогда последний будет ссылаться на что-либо другое. Кроме того,
результат будет неопределён, если вы попытаетесь изменить содержимое константы.

\begin{figure}[H]
\center{\includegraphics[width=0.6629213\linewidth]{chapt5_sec5_img0.eps}}
\end{figure}
%
%  в картинке исправлены опечатки - неверное экранирование символа \'0' 
%

\index{массив!а не указатель}%
\index{указатель!а не массив}%
Дополнительные моменты, связанные с указателями и массивами, проиллюстрируем на
несколько видоизменённых вариантах двух полезных программ, взятых нами из
стандартной библиотеки. Первая из них, функция \verb|strcpy(s,t)|, копирует
стринг \verb|t| в стринг \verb|s|. Хотелось бы написать прямо \verb|s=t|‚ но
такой оператор копирует указатель, а не литеры. Чтобы копировать литеры, нам
нужно организовать цикл.
\index{функция!strcpy@\texttt{strcpy}}%
Первый вариант \verb|strcpy|, с использованием массива, имеет следующий вид:

\begin{LongCodePar}
/* strcpy: копирует t в s; вариант с индексируемым массивом */
void strcpy(char *s, char *t)
{
    int i;
    i = 0;
    while ((s[i] = t[i]) != '\0')
        i++;
}
\end{LongCodePar}

\noindent%
\index{функция!strcpy@\texttt{strcpy}}%
Для сравнения приведём версию \verb|strcpy| с указателями:

\begin{LongCodePar}
/* strcpy: копирует t в s; версия 1 (с указателями) */
void strcpy(char *s, char *t)
{
    while ((*s = *t) != '\0') {
        s++;
        t++;
    }
}
\end{LongCodePar}

\noindent Поскольку передаются лишь копии значений аргументов, \verb|strcpy|
может свободно пользоваться параметрами \verb|s| и \verb|t| как своими
локальными переменными. Они должным образом инициализированы указателями,
которые продвигаются каждый раз на следующую литеру в каждом из массивов до тех
пор, пока в копируемом стринге \verb|t| не встретится \verb|'\0'|.

\index{функция!strcpy@\texttt{strcpy}}%
На практике \verb|strcpy| так не пишут. Опытный программист предпочтёт более
короткую запись:

\begin{ShortCodePar}
/* strcpy: копирует t в s; версия 2 (с указателями) */
void strcpy(char *s, char *t)
{
    while ((*s++ = *t++) != '\0')
        ;
}
\end{ShortCodePar}

\noindent Продвижение \verb|s| и \verb|t| здесь осуществляется в управляющей
части цикла.
\index{операторы!постфиксные \texttt{++} и \texttt{\textminus\textminus}}%
Значением \verb|*t++| является литера, на которую указывает переменная \verb|t|
перед тем, как её значение будет продвинуто; постфиксный оператор \verb|++| не
изменяет указатель \verb|t|, пока не будет взята литера, на которую он
указывает. То же в отношении \verb|s|, сначала литера запомнится в позиции, на
которую указывает старое значение \verb|s|, и лишь после этого значение
переменной \verb|s| увеличится. Пересылаемая литера является одновременно и
значением, которое сравнивается с \verb|'\0'|. В итоге копируются все литеры, включая и заключительную литеру \verb|'\0'|.

\index{нуль, опущенная проверка на него}%
\index{функция!strcpy@\texttt{strcpy}}%
Заметив, что сравнение с \verb|'\0'| здесь лишнее (поскольку в Си ненулевое
значение выражения в условии трактуется и как его истинность), мы можем сделать
ещё одно и последнее сокращение текста программы:

\begin{ShortCodePar}
/* strcpy: копирует t в s; версия 3 (с указателями) */
void strcpy(char *s, char *t)
{
    while (*s++ = *t++)
        ;
}
\end{ShortCodePar}

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

\index{файл!головной!<string.h>@\texttt{<string.h>}}%
Что касается функции \verb|strcpy| из стандартной библиотеки \verb|<string.h>|‚
то она возвращает в качестве своего результата ещё и ссылку на новую копию
стринга.

\index{функция!strcmp@\texttt{strcmp}}%
Вторая программа, которую мы здесь рассмотрим, это \verb|strcmp(s,t)|. Она
сравнивает литеры стрингов \verb|s| и \verb|t| и возвращает отрицательное,
нулевое или положительное значение, если стринг \verb|s| соответственно
лексикографически меньше, равен или больше, чем стринг \verb|t|. Результат
получается вычитанием первых несовпадающих литер из \verb|s| и \verb|t|.

\begin{LongCodePar}
/* strcmp: выдаёт <0 при s<t, 0 при s==t, >0 при s>t */
int strcmp(char *s, char *t)
{
    int i;
    for (i = 0; s[i] == t[i]; i++)
        if (s[i] == '\0')
            return 0;
    return s[i] - t[i];
}
\end{LongCodePar}

\noindent Та же программа с использованием указателей записывается так:

\begin{LongCodePar}
/* strcmp: выдаёт <0 при s<t, 0 при s==t, >0 при s>t */
int strcmp(char *s, char *t)
{
    for ( ; *s == *t; s++, t++)
        if (*s == '\0')
            return 0;
    return *s - *t;
}
\end{LongCodePar}

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

\begin{ShortCodePar}
*--p
\end{ShortCodePar}

\noindent уменьшит \verb|p| прежде, чем по этому указателю будет получена
литера. Например, следующие два выражения:

\begin{ShortCodePar}
*p++ = val;   /* поместить val в стек */
val = *--p;   /* взять из стека значение и поместить в val */
\end{ShortCodePar}

\noindent являются стандартными записями для посылки в стек и взятия из
стека.~(См. разд.~\ref{sec:external_variables})

\index{файл!головной!<string.h>@\texttt{<string.h>}}%
Описания функций, упомянутых в этом разделе, а также ряда других стандартных
функций, работающих со стрингами, содержатся в головном файле \verb|<string.h>|.

\paragraph{Упражнение 5.3.} Используя указатели, напишите функцию 
\verb|strcat|, которую мы рассматривали в
гл.~\ref{chapt:types-operators-expressions} (функция \verb|strcat(s,t)| копирует
стринг \verb|t| в конец стринга \verb|s|).

\paragraph{Упражнение 5.4.} Напишите функцию \verb|strend(s,t)|, которая выдаёт
$1$, если стринг \verb|t| расположен в конце стринга \verb|s|, и нуль в
противном случае.

\paragraph{Упражнение 5.5.} Напишите варианты библиотечных функций
\verb|strncpy|, \verb|strncat| и \verb|strncmp|, которые оперируют с первыми
литерами своих аргументов, число которых не превышает \verb|n|. Например,
\verb|strncpy(t,s,n)| копирует не более \verb|n| литер \verb|t| в \verb|s|.
Полные описания этих функций содержатся в приложении~\ref{apx:stdlib}.

\paragraph{Упражнение 5.6.} Отберите подходящие программы из предыдущих глав и
упражнений и перепишите их, используя вместо индексирования указатели. Подойдут,
в частности, программы
\verb|getline|~(гл.~\ref{chapt:tutorial_intro}~и~\ref{chapt:functions_and_program_structure}),
\verb|atoi|, \verb|itoa| и их
варианты~(гл.~\ref{chapt:types-operators-expressions},~\ref{chapt:control_flow}~и~\ref{chapt:functions_and_program_structure}),
\verb|reverse|~(гл.~\ref{chapt:control_flow}), а также \verb|strindex| и
\verb|getop|~(гл.~\ref{chapt:functions_and_program_structure}).

\section{Массивы указателей, указатели на указатели}
\label{sec:arrays_of_pointers}

\index{массив!указателей}%
\index{указатели!массив из}%
Как и любые другие переменные, указатели можно группировать в массивы.
\index{программа!сортировки}%
\index{сортировка!текстовых строк}%
Для иллюстрации этого напишем программу, сортирующую в алфавитном порядке
текстовые строки; это будет упрощённый вариант программы \verb|sort| системы
UNIX.

В гл.~\ref{chapt:control_flow} мы привели функцию сортировки по Шеллу, которая
упорядочивает массив целых, а в гл.~\ref{chapt:functions_and_program_structure}
улучшили её, повысив быстродействие.

Те же алгоритмы используются и здесь,
однако теперь они будут обрабатывать текстовые строки, которые могут иметь
разную длину и сравнение или перемещение которых невозможно выполнить за одну
операцию. Нам необходимо выбрать некоторое представление данных, которое бы
позволило удобно и эффективно работать с текстовыми строками произвольной длины.
\index{сортировка!лексикографическая}%
Для этого воспользуемся массивом указателей на начала строк. Поскольку строки в
памяти расположены вплотную друг к другу, к каждой отдельной строке доступ
просто осуществлять через указатель на её первую литеру. Сами указатели можно
организовать в виде массива. Одна из возможностей сравнить две строки --
передать указатели на них функции \verb|strcmp|. Чтобы поменять местами строки,
достаточно будет поменять местами в массиве их указатели (а не сами строки).

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

\noindent Здесь снимаются сразу две проблемы: одна -- связанная со сложностью
управления памятью, а вторая -- с большими накладными расходами при
перестановках самих строк.

\index{модульность}%
Процесс сортировки распадается на три этапа:

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

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

Программа ввода должна прочитать и запомнить литеры всех строк, а также
построить массив указателей на строки. Она, кроме того, должна подсчитать число
введённых строк -- эта информация понадобится для сортировки и печати. Так как
функция ввода может работать только с конечным числом строк, то, если их введено
слишком много, она будет выдавать некоторое значение, которое никогда не
совпадёт ни с каким количеством строк, например, $-1$.

Программа вывода занимается только тем, что печатает строки, причём в том
порядке, в котором в массиве указателей на них расположены ссылки.

\index{функция!readlines@\texttt{readlines}}%
\index{функция!writelines@\texttt{writelines}}%
\begin{LongCodePar}
#include <stdio.h>
#include <string.h>
#define MAXLINES 5000       /* максимальное число строк */
char *lineptr[MAXLINES];    /* указатели на строки */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(char *lineptr[], int left, int right);

/* сортировка строк */
main()
{
    int nlines;     /* количество прочитанных строк */
    if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
        qsort(lineptr, 0, nlines-1);
        writelines(lineptr, nlines);
        return 0;
    } else {
        printf("ошибка: слишком много строк\n");
        return 1;
    }
}

#define MAXLEN 1000    /* максимальная длина строки */
int getline(char *, int);
char *alloc(int);

/* readlines: чтение строк */
int readlines(char *lineptr[], int maxlines)
{
    int len, nlines;
    char *p, line[MAXLEN];
    nlines = 0;
    while ((len = getline(line, MAXLEN)) > 0)
        if (nlines >= maxlines || (p = alloc(len)) == NULL)
            return -1;
        else {
            line[len-1] = '\0'; /* убираем литеру \n */
            strcpy(p, line);
            lineptr[nlines++] = p;
        }
    return nlines;
}

/* writelines: печать строк */
void writelines(char *lineptr[], int nlines)
{
    int i;
    for (i = 0; i < nlines; i++)
        printf("%s\n", lineptr[i]);
}
\end{LongCodePar}

\noindent Функция \verb|getline| взята из разд.~\ref{sec:char_arrays}.

Основное новшество здесь -- декларация \verb|lineptr|:

\begin{ShortCodePar}
char *lineptr[MAXLINES];
\end{ShortCodePar}

\noindent в которой сообщается, что \verb|lineptr| есть массив из
\verb|MAXFILES| элементов, каждый из которых представляет собой указатель на
\verb|char|. Иначе говоря, \verb|lineptr[i]| -- указатель на литеру, а
\verb|*lineptr[i]| -- литера, на которую он указывает (первая литера \verb|i|-й
строки текста).

\index{функция!writelines@\texttt{writelines}}%
Так как \verb|lineptr| -- имя массива, его можно трактовать как указатель, т.е.
так же, как мы это делали в предыдущих примерах, и \verb|writelines| переписать
следующим образом:

\begin{ShortCodePar}
/* writelines: печать строк */
void writelines(char *lineptr[], int nlines)
{
    while (nlines-- > 0)
        printf("%s\n", *lineptr++);
}
\end{ShortCodePar}

\noindent Вначале \verb|*lineptr| ссылается на первую строку; каждое приращение
указателя приводит к тому, что \verb|*lineptr| ссылается на следующую строку, и
делается это до тех пор, пока \verb|nlines| не станет нулём.

Теперь, когда мы разобрались с вводом и выводом, можно приступить к сортировке.
\index{быстрая сортировка}%
\index{функция!qsort@\texttt{qsort}}%
Быструю сортировку, описанную в гл.~\ref{chapt:functions_and_program_structure},
надо несколько модифицировать: нужно изменить декларации, а операцию сравнения
заменить обращением к \verb|strcmp|. Алгоритм остался тем же, и это даёт нам
определённую уверенность в его правильности.

\begin{LongCodePar}
/* qsort: сортирует v[left]...v[right] по возрастанию */
void qsort(char *v[], int left, int right)
{
    int i, last;
    void swap(char *v[], int i, int j);
    if (left >= right) /* ничего не делается, если       */
        return;        /* в массиве менее двух элементов */
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left+1; i <= right; i++)
        if (strcmp(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}
\end{LongCodePar}

\noindent%
\index{функция!swap@\texttt{swap}}%
Небольшие поправки требуются и в программе перестановки.

\begin{LongCodePar}
/* swap: переставить v[i] и v[j] между собой */
void swap(char *v[], int i, int j)
{
    char *temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}
\end{LongCodePar}

\noindent Так как каждый элемент массива \verb|v| (т.е. \verb|lineptr|) является
указателем на литеру, \verb|temp| должен иметь тот же тип, что и \verb|v| --
тогда можно будет осуществлять пересылки между \verb|temp| и элементами
\verb|v|.

\paragraph{Упражнение 5.7.} Напишите новую версию \verb|readlines|, которая
запоминала бы строки в массиве, определённом в \verb|main|, а не запрашивала
память посредством программы \verb|alloc|. Насколько быстрее эта программа?

\section{Многомерные массивы}

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

\index{преобразование!даты}%
Рассмотрим задачу перевода даты <<день-месяц>> в <<день года>> и обратно.
Например,
\index{високосный год, вычисление}%
1 марта -- это 60-й день невисокосного или 61-й день високосного года. Определим
две функции для этих преобразований:
\index{функция!day{\_}of{\_}year@\texttt{day{\_}of{\_}year}}%
функция \verb|day_of_year| будет преобразовывать месяц-день в день года‚ а
\index{функция!month{\_}day@\texttt{month{\_}day}}%
\verb|month_day| -- день года в месяц-день. Поскольку последняя функция
вычисляет два значения, аргументы месяц и день будут указателями. Так,

\begin{ShortCodePar}
month_day(1988, 60, &m, &d)
\end{ShortCodePar}

\noindent установит в \verb|m| число $2$, а в \verb|d| -- значение $29$ (29
февраля).

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

\begin{LongCodePar}
static char daytab[2][13] = {
    {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
    {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};

/* day_of_year: определяет день года по месяцу и дню */
int day_of_year(int year, int month, int day)
{
    int i, leap;
    leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
    for (i = 1; i < month; i++)
        day += daytab[leap][i];
    return day;
}

/* month_day: определяет месяц и день по дню года */
void month_day(int year, int yearday, int *pmonth, int *pday)
{
    int i, leap;
    leap = year%4 == 0 && year%100 != 0 || year%400 == 0;
    for (i = 1; yearday > daytab[leap][i]; i++)
        yearday -= daytab[leap][i];
    *pmonth = i;
    *pday = yearday;
}
\end{LongCodePar}
%%
%% исправлена опечатка
%% в оригинале "day_year"
%%

\noindent Напоминаем, что арифметическое значение логического выражения
(например, выражения, с помощью которого вычислялось \verb|leap|) равно нулю
(ложь) или единице (истина), так что мы можем использовать его как индекс в
массиве \verb|daytab|.

Массив \verb|daytab| должен быть внешним по отношению к обеим функциям
\verb|day_of_year| и \verb|month_day|, так как он нужен и той и другой. Мы
сделали его типа \verb|char|, чтобы проиллюстрировать законность применения типа
\verb|char| для малых целых.

Массив \verb|daytab| -- это первый массив из числа двумерных, с которыми мы ещё
не имели дела. Строго говоря, в Си двумерный массив рассматривается как
одномерный массив, каждый элемент которого -- также массив. Поэтому
индексирование изображается как

\begin{ShortCodePar}
daytab[i][j]         /* [строка][столбец] */
\end{ShortCodePar}

\noindent а не как

\begin{ShortCodePar}
daytab[i,j]          /* НЕВЕРНО */
\end{ShortCodePar}

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

Массив инициализируется списком начальных значений, заключённым в фигурные
скобки; каждая строка двумерного массива инициализируется соответствующим
подсписком. Нулевой столбец добавлен в начало \verb|daytab| лишь для того, чтобы
индексы, которыми мы будем пользоваться, совпадали с естественными номерами
месяцев от 1 до 12. Экономить пару ячеек памяти здесь нет никакого смысла, а
программа, в которой уже не надо корректировать индекс, выглядит более ясной.

\index{массив!имя в роли аргумента}%
\index{массив!декларация}%
\index{массив!а не указатель}%
\index{указатель!а не массив}%
Если двумерный массив передаётся функции в качестве аргумента, то декларация
соответствующего ему параметра должна содержать количество столбцов; количество
строк в данном случае несущественно, поскольку, как и прежде, функции будет
передана ссылка на массив строк, каждая из которых есть массив из 13 значений
типа \verb|char|. В нашем частном случае имеем указатель на объекты, являющиеся
массивами из 13 значений типа \verb|char|. Таким образом, если массив
\verb|daytab| передаётся некоторой функции \verb|f|, то эту функцию можно было
бы определить следующим образом:

\begin{ShortCodePar}
f(char daytab[2][13]) { ... }
\end{ShortCodePar}

\noindent Вместо этого можно записать

\begin{ShortCodePar}
f(char daytab[][13]) { ... }
\end{ShortCodePar}

\noindent поскольку число строк здесь не имеет значения, или

\begin{ShortCodePar}
f(char (*daytab)[13]) { ... }
\end{ShortCodePar}

\noindent последняя запись декларирует, что параметр есть указатель на массив из
13 значений типа \verb|char|. Скобки здесь необходимы, так как квадратные скобки
\verb|[]| имеют более высокий приоритет, чем \verb|*|. Без скобок декларация

\begin{ShortCodePar}
char *daytab[13]
\end{ShortCodePar}

\noindent определяет массив из 13 указателей на \verb|char|.
\index{по умолчанию!размер массива}%
В более общем случае только первое измерение (соответствующее первому индексу)
можно не задавать, все другие специфицировать необходимо.

В разд.~\ref{sec:complex_declarations} мы продолжим рассмотрение сложных
деклараций.

\paragraph{Упражнение 5.8.} В функциях \verb|day_of_year| и \verb|month_day| нет
никаких проверок правильности вводимых дат. Устраните этот недостаток.

\section{Инициализация массивов указателей}

\index{инициализация!массива}%
\index{функция!month{\_}name@\texttt{month{\_}name}}%
Напишем функцию \verb|month_name(n)|, которая возвращает ссылку на стринг литер,
содержащий название \verb|n|-го месяца. Эта функция идеальна для демонстрации
использования статического массива. Функция \verb|month_name| имеет в своём
личном распоряжении массив стрингов, на один из которых она и возвращает ссылку.
Ниже покажем, как инициализируется этот массив имён.

Синтаксис задания начальных значений аналогичен синтаксису предыдущих
инициализаций:

\begin{LongCodePar}
/* month_name: возвращает имя n-го месяца */
char *month_name(int n)
{
    static char *name[] = {
        "Неверный месяц",
        "Январь", "Февраль", "Март",
        "Апрель", "Май", "Июнь",
        "Июль", "Август", "Сентябрь",
        "Октябрь", "Ноябрь", "Декабрь"
    };
    return (n < 1 || n > 12) ? name[0] : name [n];
}
\end{LongCodePar}

\noindent Декларация, определяющая \verb|name| как массив указателей на литеры,
такая же, как и декларация \verb|lineptr| в программе сортировки.
Инициализатором служит список стрингов, каждому из которых соответствует
определённое место в массиве. Литеры \verb|i|-го стринга где-то размещены, и
указатель на них запоминается в \verb|name[i]|.
\index{массив!размер по умолчанию}%
Так как размер массива \verb|name| не специфицирован, компилятор вычислит его по
количеству заданных начальных значений.

\section{Указатели вместо многомерных массивов}

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

\begin{ShortCodePar}
int a[10][20];
int *b[10];
\end{ShortCodePar}

\noindent записи \verb|a[3][4]| и \verb|b[3][4]| будут синтаксически правильными
ссылками на некоторое значение типа \verb|int|. Однако только \verb|a| является
истинно двумерным массивом: для двухсот элементов типа \verb|int| будет выделена
память, а вычисление смещения элемента
\verb|a[|\textit{\Verb|строка|}\verb|,|\textit{\Verb|столбец|}\verb|]| от начала
массива будет вестись по формуле
$20\times\text{\textit{строка}}+\text{\textit{столбец}}$, учитывающей его
прямоугольную природу. Для \verb|b| же определяются только 10 указателей‚ причём
без инициализации. Инициализация должна задаваться явно -- либо статически,
либо в процессе счёта. Предположим, что каждый элемент \verb|b| ссылается на
двадцатиэлементный массив, в результате где-то будут выделены пространство, в
котором разместятся 200 значений типа \verb|int|, и ещё 10 ячеек для
указателей. Важное преимущество массива указателей в том, что строки такого
массива могут иметь разные длины. Таким образом, каждый элемент \verb|b| не
обязательно ссылается на двадцатиэлементный вектор; один может ссылаться на два
элемента, другой -- на пятьдесят, а некоторые и вовсе могут ни на что не
ссылаться.

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

\begin{ShortCodePar}
char *name[] = {"Неправильный месяц", "Янв", "Февр", "Март"};
\end{ShortCodePar}

\begin{figure}[H]
\center{\includegraphics[width=0.5617978\linewidth]{chapt5_sec9_img0.eps}}
\end{figure}
%
% исправлена опечатка:
% в оригинале все терминаторы написаны как \o
%

\noindent с определением и рисунком для двумерного массива:

\begin{ShortCodePar}
char aname[][15] = {"Неправ. месяц", "Янв", "Февр", "Март"};
\end{ShortCodePar}

\begin{figure}[H]
\center{\includegraphics[width=0.9831461\linewidth]{chapt5_sec9_img1.eps}}
\end{figure}
%
% исправлена опечатка:
% в оригинале все терминаторы написаны как \o
%

\paragraph{Упражнение 5.9.} Перепишите программы \verb|day_of_year| и
\verb|month_of_year|‚ используя вместо индексов указатели.

\section{Аргументы в командной строке}

\index{аргументы командной строки|(}%
\index{командная строка аргументы|(}%
В операционной среде, обеспечивающей поддержку Си, имеется возможность передать
аргументы или параметры запускаемой программе при помощи командной строки. В
момент вызова \verb|main| получает два аргумента.
\index{argc@\texttt{argc}}%
В первом, обычно называемом \verb|argc| (сокращение от argument count), стоит
количество аргументов, задаваемых в командной строке.
\index{argv@\texttt{argv}|(}%
Второй, \verb|argv| (от argument vector), является указателем на массив литерных
стрингов, содержащих сами аргументы. Для работы с этими стрингами обычно
используются указатели нескольких уровней.

\index{программа!echo@\texttt{echo}}%
Простейший пример -- программа \verb|echo| (<<эхо>>), которая печатает аргументы
своей командной строки в одной строчке, отделяя их друг от друга пробелами. Так,
команда

\begin{ShortCodePar}
echo Здравствуй, мир!
\end{ShortCodePar}

\noindent напечатает

\begin{ShortCodePar}
Здравствуй, мир!
\end{ShortCodePar}

\noindent По соглашению \verb|argv[0]| есть имя вызываемой программы, так что
значение \verb|argc| никогда не бывает меньше $1$. Если \verb|argc| равен $1$,
то в командной строке после имени программы никаких аргументов нет. В нашем
примере \verb|argc| равен $3$, и соответственно \verb|argv[0]|‚ \verb|argv[1]| и
\verb|argv[2]| есть стринги \verb|"echo"|, \verb|"Здравствуй,"| и \verb|"мир!"|.
Первый необязательный аргумент -- это \verb|argv[1]|‚ последний --
\verb|argv[argc-1]|. Кроме того, стандарт требует, чтобы \verb|argv[argc]|
всегда был пустым указателем.

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

\noindent%
\index{программа!echo@\texttt{echo}}%
Первая версия программы \verb|echo| трактует \verb|argv| как массив литерных
указателей.

\begin{LongCodePar}
#include <stdio.h>
/* эхо аргументов командной строки; версия 1 */
main(int argc, char *argv[])
{
    int i;
    for (i = 1; i < argc; i++)
        printf("%s%s", argv[i], (i < argc-1) ? " " : "");
    printf("\n");
    return 0;
}
\end{LongCodePar}

\noindent%
\index{программа!echo@\texttt{echo}}%
Так как \verb|argv| есть указатель на массив указателей, мы можем работать с ним
как с указателем, а не как с индексируемым массивом. Следующая программа
основана на продвижении \verb|argv|, он продвигается так, что его значение в
каждый отдельный момент ссылается на очередной указатель на \verb|char|; перебор
указателей заканчивается, когда исчерпан \verb|argc|.

\begin{LongCodePar}
#include <stdio.h>
/* эхо аргументов командной строки; версия 2 */
main(int argc, char *argv[])
{
    while (--argc > 0)
        printf("%s%s", *++argv, (argc > 1) ? " " : "");
    printf("\n");
    return 0;
}
\end{LongCodePar}

\noindent Аргумент \verb|argv| -- указатель на начало массива аргументных
стрингов. Использование в \verb|++argv| префиксного оператора \verb|++| приведёт
к тому, что первым будет напечатан \verb|argv[1]|, а не \verb|argv[0]|. Каждое
очередное продвижение указателя даёт нам следующий аргумент, на который
ссылается \verb|*argv|. В это же время значение \verb|argc| уменьшается на $1$,
и, когда оно станет нулём, все аргументы будут напечатаны.

Инструкцию \verb|printf| можно было бы написать и так:

\begin{ShortCodePar}
printf((argc > 1) ? "%s " : "%s", *++argv);
\end{ShortCodePar}

\noindent Как видим, формат в \verb|printf| может быть выражением.

\index{программа!поиска!по образцу}%
В качестве второго примера возьмём программу поиска образца, рассмотренную в
разд.~\ref{sec:functions_basics}, и несколько усовершенствуем её. Если вы
помните, образец для поиска мы <<вмонтировали>> глубоко в программу, а это,
очевидно, не лучшее решение. Построим нашу программу по аналогии с \verb|grep|
из UNIXа‚ т.е. так, чтобы образец для поиска задавался первым
\index{аргументы командной строки}%
аргументом в командной строке.

\begin{LongCodePar}
#include <stdio.h>
#include <string.h>
#define MAXLINE 1000
int getline(char *line, int max);
/* find: печать строк с образцом заданным 1-м аргументом */
main(int argc, char *argv[])
{
    char line[MAXLINE];
    int found = 0;
    if (argc != 2)
        printf("Используйте в find образец\n");
    else
        while (getline(line, MAXLINE) > 0)
            if (strstr(line, argv[1]) != NULL) {
                printf("%s", line);
                found++;
            }
    return found;
}
\end{LongCodePar}

\noindent Стандартная функция \verb|strstr(s,t)| выдаёт указатель на первый
найденный стринг \verb|t| в стринге \verb|s| или \verb|NULL|, если такого в
\verb|s| не оказалось. Её описание хранится в головном файле
\verb|<string.h>|.

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

По общему соглашению для Си-программ в системе UNIX знак минус перед аргументом
может иногда играть роль необязательного признака или дополнительного параметра.
Так, \verb|-x| служит признаком слова <<кроме>>, которое изменяет задание на
противоположное, а \verb|-n| указывает на потребность в нумерации строк. Тогда, например, команда

\begin{ShortCodeParWithCC}{\\\{\}}
find -x -n \textit{образец}
\end{ShortCodeParWithCC}

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

Необязательные аргументы разрешается располагать в любом порядке, при этом
лучше, чтобы остальная часть программы не зависела от числа представленных
аргументов. Кроме того, пользователю было бы удобно, если бы он мог
комбинировать необязательные аргументы, например, так:

\begin{ShortCodeParWithCC}{\\\{\}}
find -nx \textit{образец}
\end{ShortCodeParWithCC}

\noindent А теперь запишем нашу программу.

\begin{LongCodePar}
#include <stdio.h>
#include <string.h>
#define MAXLINE 1000
int getline(char *line, int max);

/* find: печать строк по образцу из 1-го аргумента */
main(int argc, char *argv[])
{
    char line[MAXLINE];
    long lineno = 0;
    int c, except = 0, number = 0, found = 0;
    while (--argc > 0 && (*++argv)[0] == '-')
        while (c = *++argv[0])
            switch (c) {
            case 'x':
                except = 1;
                break;
            case 'n':
                number = 1;
                break;
            default:
                printf("find: неверный парам. %c\n", c);
                argc = 0;
                found = -1;
                break;
            }
    if (argc != 1)
        printf("Используйте: find -x -n образец\n");
    else
        while (getline(line, MAXLINE) > 0) {
            lineno++;
            if ((strstr(line, *argv) != NULL) != except) {
                if (number)
                    printf("%ld:", lineno);
                printf("%s", line);
                found++;
            }
        }
    return found;
}
\end{LongCodePar}
%
% исправлена ошибка наборщика с отступами в оригинале
%

\index{указатели!арифметика с}%
Перед получением очередного аргумента \verb|argc| уменьшается на $1$, а
\verb|argv| <<продвигается>> на следующий аргумент. После завершения цикла при
отсутствии ошибок \verb|argc| содержит количество ещё не обработанных
аргументов, а \verb|argv| указывает на первый из них. Таким образом, \verb|argc|
должен быть равен $1$, а \verb|*argv| указывать на образец. Заметим, что
\verb|*++argv| является указателем на аргумент-стринг, а \verb|(*++argv)[0]| --
его первой литерой, на которую можно сослаться и другим способом:
\verb|**++argv|. Поскольку оператор индексации \verb|[]| имеет более высокий
приоритет, чем \verb|*| и \verb|++|, круглые скобки здесь обязательны, без них
запись трактовалась бы так же, как \verb|*++(argv[0])|. Именно эту запись мы
применим во внутреннем цикле, где просматриваются литеры конкретного аргумента.
Во внутреннем цикле выражение \verb|*++argv[0]| продвигает указатель
\verb|argv[0]|.

Потребность в более сложных указательных выражениях возникает не так уж часто.
Но если такое случится, то, разбивая процесс вычисления указателя на два или три
шага, вы облегчите восприятие этого выражения
\index{argv@\texttt{argv}|)}%
\index{командная строка аргументы|)}%
\index{аргументы командной строки|)}%


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

\begin{ShortCodePar}
expr 2 3 4 + *
\end{ShortCodePar}

\noindent вычисляется так же, как выражение $2\times(3+4)$.

\paragraph{Упражнение 5.11.} Усовершенствуйте программы \verb|entab| и
\verb|detab|~(см.~упражнения~\hyperref[parag:exc1.20]{1.20}~и~\hyperref[parag:exc1.21]{1.21}) таким образом, чтобы через аргументы
можно было задавать список <<стопов>> табуляции.

\paragraph{Упражнение 5.12.} Расширьте возможности \verb|entab| и \verb|detab|
таким образом, чтобы при обращении вида

\begin{ShortCodeParWithCC}{\\\{\}}
entab \textit{-m} \textit{+n}
\end{ShortCodeParWithCC}

\noindent <<стопы>> табуляции начинались $m$-й позиции и выполнялись через
каждые $n$ позиций. Разработайте удобный для пользователя вариант поведения
программы по умолчанию (когда нет никаких аргументов).

\paragraph{Упражнение 5.13.} Напишите программу \verb|tail|, печатающую $n$
последних введённых строк. По умолчанию значение $n$ равно $10$, но при желании
$n$ можно задать с помощью аргумента. Обращение вида

\begin{ShortCodeParWithCC}{\\\{\}}
tail -\textit{n}
\end{ShortCodeParWithCC}

\noindent печатает $n$ последних строк. Программа должна вести себя осмысленно
при любых входных данных и любом значении $n$. Напишите программу так, чтобы
наилучшим образом использовать память; запоминание строк организуйте, как в
программе сортировки, описанной в разд.~\ref{sec:arrays_of_pointers}, а не на
основе двумерного массива с фиксированным размером строки.

\section{Указатели на функции}
\label{sec:function_pointers}

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

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

\index{лексикографическая сортировка}%
\index{сортировка!лексикографическая}%
Лексикографическое сравнение двух строк выполняется функцией \verb|strcmp| (мы
уже использовали эту функцию в ранее рассмотренной программе сортировки); нам
также потребуется программа \verb|numcmp|, сравнивающая две строки как числовые
значения и возвращающая результат сравнения в том же виде, в каком его выдаёт
\verb|strcmp|. Эти функции описываются перед \verb|main|, а указатель на одну из
них передаётся функции \verb|qsort|. Чтобы сосредоточиться на главном, мы
упростили себе задачу, отказавшись от анализа возможных ошибок при задании
аргументов.

\begin{LongCodePar}
#include <stdio.h>
#include <string.h>
#define MAXLINES 5000       /* максимальное число строк */
char *lineptr[MAXLINES];    /* указатели на строки текста */
int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(void *lineptr[], int left, int right,
           int (*comp)(void *, void *));
int numcmp(char *, char *);

/* сортировка строк */
main(int argc, char *argv[])
{
    int nlines;        /* количество прочитанных строк */
    int numeric = 0;   /* 1, если сорт. по числ. знач. */
    
    if (argc > 1 && strcmp(argv[1], "-n") == 0)
        numeric = 1;
    if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
        qsort((void **) lineptr, 0, nlines-1,
          (int (*)(void*,void*))(numeric ? numcmp : strcmp));
        writelines(lineptr, nlines);
        return 0;
    } else {
        printf("введено слишком много строк\n");
        return 1;
    }
}
\end{LongCodePar}

\noindent В обращениях к функциям \verb|qsort|, \verb|strcmp| и \verb|numcmp| их
имена трактуются как адреса этих функций. Поэтому оператор \verb|&| перед ними
не нужен, как он был не нужен и перед именем массива.

\index{функция!qsort@\texttt{qsort}}%
Мы написали \verb|qsort| так, чтобы она могла обрабатывать данные любого типа, а
не только стринги литер. Как видно из прототипа, функция \verb|qsort| в качестве
своих аргументов ожидает массив ссылок, два целых значения и функцию с двумя
аргументами-указателями.
\index{указатель!void *@\texttt{void *}|(}%
\index{void *, указатель@\texttt{void *}, указатель|(}%
В качестве указателей-аргументов заданы указатели обобщённого типа
\verb|void *|. Любой указатель можно привести к типу \verb|void *| и обратно без
потери информации. Поэтому мы можем обратиться к \verb|qsort|, предварительно
преобразовав аргументы в \verb|void *|. Внутри функции сравнения её аргументы
будут приведены к нужному ей типу. На самом деле эти преобразования никакого
влияния на представления аргументов не оказывают, они лишь обеспечивают
согласованность типов для компилятора.

\begin{LongCodePar}
/* qsort: сортирует v[left]...v[right] по возрастанию */
void qsort(void *v[], int left, int right,
           int (*comp)(void *, void *))
{
    int i, last;
    void swap(void *v[], int, int);
    
    if (left >= right) /* ничего не делается, если       */
        return;        /* в массиве менее двух элементов */
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left+1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0)
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1, comp);
    qsort(v, last+1, right, comp);
}
\end{LongCodePar}

\noindent%
\index{прототип функции}%
\index{указатель!void *@\texttt{void *}}%
\index{функция!прототип}%
\index{void *, указатель@\texttt{void *}, указатель}%
Повнимательней приглядимся к декларациям. Четвёртый параметр функции
\verb|qsort|:

\begin{ShortCodePar}
int (*comp)(void *, void *)
\end{ShortCodePar}

\noindent сообщает, что \verb|comp| есть указатель на функцию, которая имеет два
аргумента-указателя и выдаёт результат типа \verb|int|.

Использование \verb|comp| в строке

\begin{ShortCodePar}
if ((*comp)(v[i], v[left]) < 0)
\end{ShortCodePar}

\noindent согласуется с декларацией <<\verb|comp| -- это указатель на
функцию>>, и, следовательно, \verb|*comp| есть функция, а

\begin{ShortCodePar}
(*comp)(v[i], v[left])
\end{ShortCodePar}

\noindent обращение к ней. Скобки здесь нужны, чтобы обеспечить правильную
трактовку декларации; без них декларация

\begin{ShortCodePar}
int *comp(void *, void *)        /* НЕВЕРНО */
\end{ShortCodePar}

\noindent описывала бы \verb|comp|, как функцию, возвращающую ссылку на
\verb|int|, а это совсем не то, что требуется.
\index{void *, указатель@\texttt{void *}, указатель|)}%
\index{указатель!void *@\texttt{void *}|)}%


Мы уже рассматривали функцию \verb|strcmp|, сравнивающую два стринга.
\index{функция!numcmp@\texttt{numcmp}}%
Ниже приведена функция \verb|numcmp|, которая сравнивает два стринга,
рассматривая их как числа; предварительно они переводятся в числовые значения
функцией \verb|atof|.

\begin{LongCodePar}
#include <stdlib.h>

/* numcmp: сравнивает s1 и s2 как числа */
int numcmp(char *s1, char *s2)
{
    double v1, v2;
    
    v1 = atof(s1);
    v2 = atof(s2);
    if (v1 < v2)
        return -1;
    else if (v1 > v2)
        return 1;
    else
        return 0;
}
\end{LongCodePar}

Программу сортировки можно пополнить и другими возможностями; реализовать
некоторые из них предлагается в качестве упражнений.

\paragraph{Упражнение 5.14.} Модифицируйте программу сортировки, чтобы она
реагировала на параметр \verb|-r|, указывающий, что объекты нужно сортировать в
обратном порядке, т.е. в порядке убывания. Обеспечьте, чтобы \verb|-r| работал и
вместе с \verb|-n|.

\paragraph{Упражнение 5.15.} Введите в программу необязательный параметр
\verb|-f|‚ задание которого делало бы неразличимыми литеры нижнего и верхнего
регистров (например, \verb|a| и \verb|A| должны оказаться при сравнении
равными).

\paragraph{Упражнение 5.16.} Предусмотрите в программе необязательный параметр
\verb|-d|‚ который заставит программу при сравнении учитывать только буквы,
цифры и пробелы. Организуйте программу таким образом, чтобы этот параметр мог
работать вместе с параметром \verb|-f|.

\paragraph{Упражнение 5.17.} Реализуйте в программе возможность работы с полями:
возможность сортировки по полям внутри строк. Для каждого поля предусмотрите
свой набор параметров. Предметный указатель этой книги\footnote{Здесь имеется в
виду оригинал книги на английском языке. -- \textit{Примеч. пер.}}
упорядочивался с параметрами: \verb|-df| для терминов и \verb|-n| для номеров
страниц.

\section{Сложные декларации}
\label{sec:complex_declarations}

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

\begin{ShortCodePar}
int *f();       /* f: фу-ция, возвращающая ук-ль на int */
int (*pf)();    /* pf: ук-ль на ф-цию, возвращающую int */
\end{ShortCodePar}

\noindent Приоритет префиксного оператора \verb|*| ниже, чем приоритет
\verb|()|, поэтому во втором случае скобки необходимы.

Хотя на практике по-настоящему сложные декларации встречаются редко, всё же
важно знать‚ как их понимать, а если потребуется, и как их конструировать.

Укажем хороший способ: декларации можно синтезировать, двигаясь небольшими
шагами с помощью \verb|typedef|; этот способ рассмотрен в
разд.~\ref{sec:typedef}. В настоящем разделе на примере двух программ,
осуществляющих преобразования правильных Си-деклараций в соответствующие им
словесные описания и обратно, мы демонстрируем иной способ конструирования
деклараций. Словесное описание читается слева направо.

\index{программа!dcl@\texttt{dcl}}%
Первая программа, \verb|dcl|, -- более сложная. Она преобразует Си-декларации в
словесные описания так, как показано в следующих примерах:

\begin{LongCodePar}
char **argv
    argv: указ. на указ. на char
int (*daytab)[13]
    daytab: указ. на массив[13] из int
void *comp()
    comp: функц. возвр. указ. на void
void (*comp)()
    comp: указ. на функц. возвр. void
char (*(*x())[])()
    x: функц. возвр. указ. на массив[] из указ. на функц.
       возвр. char
char (*(*x[3])())[5]
    x: массив[3] из указ. на функц. возвр. указ.
       на массив[5] из char
\end{LongCodePar}

Функция \verb|dcl| в своей работе использует грамматику, специфицирующую
декларатор. Эта грамматика строго изложена в разд.~\ref{apx:subsec:declarators}
приложения~\ref{apx:ref_manual}, а в упрощённом виде записывается так:

\begin{ShortCodeParWithCC}{\\\{\}}
\textit{dcl:}               \textit{optional} *\textit{'s} \textit{direct-dcl}
\textit{direct-dcl:}        \textit{name}
                   (\textit{dcl})
                   \textit{direct-dcl}()
                   \textit{direct-dcl}[\textit{optional size}]
\end{ShortCodeParWithCC}

\noindent Говоря простым языком, \textit{dcl} есть \textit{direct-dcl}, перед
которым может стоять \verb|*|\textit{'s} (т.е. одна или несколько звёздочек),
где \textit{direct-dcl} есть \textit{name} (имя), или \textit{dcl} в скобках, или
\textit{direct-dcl} с последующей парой скобок, или \textit{direct-dcl} с
последующей парой квадратных скобок, внутри которых может быть помещён размер
(\textit{size}).

Эту грамматику можно использовать для грамматического разбора деклараций.
Рассмотрим, например, такой декларатор:

\begin{ShortCodePar}
(*pfa[])()
\end{ShortCodePar}

\noindent Имя \verb|pfa| будет классифицировано как \textit{name} и,
следовательно, как \textit{direct-dcl}. Затем \verb|pfa[]| будет распознано как
\textit{direct-dcl}, а \verb|*pfa[]| -- как \textit{dcl} и, следовательно,
\verb|(*pfa[])| есть \textit{direct-dcl}. Далее \verb|(*pfa[])()| есть
\textit{direct-dcl} и, таким образом, \textit{dcl}. Этот грамматический разбор
можно проиллюстрировать
\index{дерево!разбора}%
деревом разбора (здесь \textit{direct-dcl} обозначено более коротко, а именно
\textit{dir-dcl}):

\begin{figure}[H]
\center{\includegraphics[width=0.7627119\linewidth]{chapt5_sec12_img0.eps}}
\end{figure}
%
% TODO: проверить правильность синтаксического дерева
%

\index{грамматический разбор методом рекурсивного спуска}%
\index{функция!dcl@\texttt{dcl}}%
\index{функция!dirdcl@\texttt{dirdcl}}%
Сердцевиной программы обработки декларатора является пара функций \verb|dcl| и
\verb|dirdcl|‚ осуществляющих грамматический разбор декларации согласно
приведённой грамматике. Поскольку грамматика определена рекурсивно, эти функции
обращаются друг к другу рекурсивно, по мере распознавания отдельных частей
декларации.
\index{рекурсивный спуск в грамматическом разборе}%
Метод, применённый в обсуждаемой программе для грамматического
разбора, называется рекурсивным спуском.

\begin{LongCodePar}
/* dcl: разбор декларатора */
void dcl(void)
{
    int ns;
    for (ns = 0; gettoken() == '*'; ) /* подсчёт звёздочек */
        ns++;
    dirdcl();
    while (ns-- > 0)
        strcat(out, " указ. на");
}
/* dirdcl: разбор непосредственного декларатора */
void dirdcl(void)
{
    int type;
    if (tokentype == '(') {      /* ( dcl ) */
        dcl();
        if (tokentype != ')')
            printf("ошибка: пропущена )\n");
    } else if (tokentype == NAME)     /* имя переменной */
        strcpy(name, token);
    else
        printf("ошибка: должно быть name или (dcl)\n");
    while ((type=gettoken()) == PARENS || type == BRACKETS)
        if (type == PARENS)
            strcat(out, " функц. возвр.");
        else {
            strcat(out, " массив");
            strcat(out, token);
            strcat(out, " из");
        }
}
\end{LongCodePar}

Приведённые программы служат только иллюстративным целям и не вполне надёжны.
Что касается \verb|dcl|, то её возможности существенно ограничены. Она может
работать только с простыми типами вроде \verb|char| и \verb|int| и не
справляется с типами аргументов в функциях и с квалификаторами подобными
\verb|const|. Лишние пробелы для неё опасны. Она не предпринимает никаких мер по
выходу из ошибочной ситуации, и поэтому неправильные декларации также
противопоказаны ей. Устранение этих недостатков мы оставляем до упражнений.

Ниже приведены глобальные переменные и главная программа.

\begin{LongCodePar}
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define  MAXTOKEN  100
enum { NAME, PARENS, BRACKETS };
void dcl(void);
void dirdcl(void);
int  gettoken(void);
int  tokentype;             /* тип последней лексемы */
char token[MAXTOKEN];       /* текст последней лексемы */
char name[MAXTOKEN];        /* имя */
char datatype[MAXTOKEN];    /* тип = char, int и т.д. */
char out[1000];             /* выдаваемый текст */

main()   /* преобразование декларации в словесное описание */
{
    while (gettoken() != EOF) {    /* 1-я лексема в строке */
        strcpy(datatype, token);   /* это тип данных */
        out[0] = '\0';
        dcl();         /* разбор остальной части строки */
        if (tokentype != '\n')
            printf("синтаксическая ошибка\n");
        printf("%s: %s %s\n", name, out, datatype);
    }
    return 0;
}
\end{LongCodePar}

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

\begin{LongCodePar}
int gettoken(void)     /* возвращает следующую лексему */
{
    int c, getch(void);
    void ungetch(int);
    char *p = token;
    while ((c = getch()) == ' ' || c == '\t')
        ;
    if (c == '(') {
        if ((c = getch()) == ')') {
            strcpy(token, "()");
            return tokentype = PARENS;
        } else {
            ungetch(c);
            return tokentype = '(';
        }
    } else if (c == '[') {
        for (*p++ = c; (*p++ = getch()) != ']'; )
            ;
        *p = '\0';
        return tokentype = BRACKETS;
    } else if (isalpha(c)) {
        for (*p++ = c; isalnum(c = getch()); )
            *p++ = c;
        *p = '\0';
        ungetch(c);
        return tokentype = NAME;
    } else
        return tokentype = c;
}
\end{LongCodePar}

\noindent Функции \verb|getch| и \verb|ungetch| были рассмотрены в
гл.~\ref{chapt:functions_and_program_structure}.

Обратное преобразование реализуется легче, особенно если не придавать значения
тому, что будут генерироваться лишние скобки.
\index{программа!undcl@\texttt{undcl}}%
Программа \verb|undcl| превращает фразу типа <<\verb|x| есть функция,
возвращающая указатель на массив указателей на функции, возвращающие
\verb|char|>>, которую мы будем представлять в виде

\begin{ShortCodePar}
x  ()  *  []  ()  char
\end{ShortCodePar}

\noindent в декларацию

\begin{ShortCodePar}
char  (*(*x())[])()
\end{ShortCodePar}

\noindent Сокращённая запись словесного описания позволяет воспользоваться
функцией \verb|gettoken|. Функция \verb|undcl| использует те же самые внешние
переменные, что и \verb|dcl|.

\begin{LongCodePar}
/* undcl: преобразует словесное описание в декларацию */
main()
{
    int type;
    char temp[MAXTOKEN];
    while (gettoken() != EOF) {
        strcpy(out, token);
        while ((type = gettoken()) != '\n')
            if (type == PARENS || type == BRACKETS)
                strcat(out, token);
            else if (type == '*') {
                sprintf(temp, "(*%s)", out);
                strcpy(out, temp);
            } else if (type == NAME) {
                sprintf(temp, "%s %s", token, out);
                strcpy(out, temp);
            } else
                printf("неверный элемент %s в фразе\n",token);
        printf("%s\n", out);
    }
    return 0;
}
\end{LongCodePar}
%
% исправлена опечатка
% отсутствовали ;
%
% в целях выравнивания
% строка      "printf("неверный элемент %s в фразе\n", token);"
% заменена на "printf("неверный элемент %s в фразе\n",token);",
% что не влияет на смысл кода
%

\paragraph{Упражнение 5.18.} Видоизмените \verb|dcl| таким образом, чтобы она
нормально обрабатывала ошибки во входной информации.

\paragraph{Упражнение 5.19.} Модифицируйте \verb|undcl| так, чтобы она не
генерировала лишних скобок.

\paragraph{Упражнение 5.20.} Расширьте возможности \verb|dcl|: функция должна
справляться с описателями типов её аргументов, квалификаторами \verb|const| и
т.д.