Kernighan, B. W. and Ritchie, D. M. "The 'C' Programming Language"; Chapter 5
Указатели и массивы
Указатель - это переменная, содержащая адрес другой переменной.Указатели очень широко используются в языке "C". Это происходитотчасти потому, что иногда они дают единственную возможность выразитьнужное действие, а отчасти потому, что они обычно ведут к болеекомпактным и эффективным программам, чем те, которые могут быть полученыдругими способами.
Указатели обычно смешивают в одну кучу с операторами goto, характеризуяих как чудесный способ написания программ, которые невозможно понять.Это безусловно справедливо, если указатели используются беззаботно;очень просто ввести указатели, которые указывают на что-то совершеннонеожиданное. Однако, при определенной дисциплине, использованиеуказателей помогает достичь ясности и простоты. Именно этот аспектмы попытаемся здесь проиллюстрировать.
Содержание
- 5.1. Указатели и адреса
- 5.2. Указатели и аргументы функций
- 5.3. Указатели и массивы
- 5.4. Адресная арифметика
- 5.5. Указатели символов и функции
- 5.6. Указатели - не целые.
- 5.7. Многомерные массивы.
- 5.8. Массивы указателей; указатели указателей
- 5.9. Инициализация массивов указателей
- 5.10. Указатели и многомерные массивы
- 5.11. Командная строка аргументов
- 5.12. Указатели на функции
- 5.2. Указатели и аргументы функций
Указатели и адреса
Так как указатель содержит адрес об'екта, это дает возможность"косвенного" доступа к этому об'екту через указатель. Предположим,что х - переменная, например, типа int, а рх - указатель, созданныйнеким еще не указанным способом. Унарная операция & выдает адресоб'екта, так что оператор
pxх = &x;присваивает адрес x переменной px; говорят, что px "указывает" на x.Операция & применима только к переменным и элементам массива,конструкции вида &(х-1) и &3 являются незаконными. Нельзя такжеполучить адрес регистровой переменной.
Унарная операция * рассматривает свой операнд как адрес конечнойцели и обращается по этому адресу, чтобы извлечь содержимое.Следовательно, если y тоже имеет тип int, то
y = *px;присваивает y содержимое того, на что указывает px. Такпоследовательность
px = &x;y = *px;присваивает y то же самое значение, что и оператор
y = x;переменные, участвующие во всем этом необходимо описать:
int x, y;int *px;C описанием для x и y мы уже неодонократно встречались. Описаниеуказателя
int *px;является новым и должно рассматриваться как мнемоническое;оно говорит, что комбинация *px имеет тип int. Это означает, что еслиpx появляется в контексте *px, то это эквивалентно переменной типа int.Фактически синтаксис описания переменной имитирует синтаксис выражений,в которых эта переменная может появляться. Это замечание полезно вовсех случаях, связанных со сложными описаниями. Например,
double atof(), *dp;говорит, что atof() и *dp имеют в выражениях значения типа double.
Вы должны также заметить, что из этого описания следует, что указательможет указывать только на определенный вид об'ектов.
Указатели могут входить в выражения. Например, если px указывает нацелое x, то *px может появляться в любом контексте, где можетвстретиться x. Так оператор
y = *px + 1;присваивает y значение, на 1 большее значения x;
printf("%d\n", *px)печатает текущее значение x;d = sqrt(double) *px)получает в d квадратный корень из x, причем до передачи функции sqrtзначение x преобразуется к типу double. (смотритеглаву 2).
В выражениях вида
y = *px + 1;унарные операции * и & связаны со своим операндом более крепко, чемарифметические операции, так что такое выражение берет то значение, накоторое указывает рх, прибавляет 1 и присваивает результат переменнойy. Мы вскоре вернемся к тому, что может означать выражение
y = *(px + 1);
Ссылки на указатели могут появляться и в левой части присваиваний.Если px указывает на x, то
*px = 0;полагает х равным нулю, а
*px += 1;увеличивает его на единицу, как и выражение
(*px) + 1;Круглые скобки в последнем примере необходимы; если их опустить, топоскольку унарные операции, подобные * и ++, выполняются справа налево,это выражение увеличит px, а не ту переменную, на которую он указывает.
И наконец, так как указатели являются переменными, то с ними можнообращаться, как и с остальными переменными. Если py - другой указательна переменную типа int, то
py = px;копирует содержимое рх в py, в результате чего py указывает на то же,что и px.
Указатели и аргументы функций
Так как в "C" передача аргументов функциям осуществляется "по значению",вызванная процедура не имеет непосредственной возможности изменитьпеременную из вызывающей программы. Что же делать, если вамдействительно надо изменить аргумент? Например, программа сортировкизахотела бы поменять два нарушающих порядок элемента с помощью функциис именем swap. Для этого недостаточно написать
swap(a, b);определив функцию swap при этом следующим образом:
swap(x, y) /* wrong */ int x, y; { int temp; temp = x; x = y; y = temp; }Из-за вызова по значению swap не может воздействовать на агументыа и b в вызывающей функции.К счастью, все же имеется возможность получить желаемый эффект.Вызывающая программа передает указатели подлежащих изменению значений:
swap(&a, &b);Так как операция & выдает адрес переменной, то &a является указателемна a. В самой swap аргументы описываются как указатели и доступ кфактическим операндам осуществляется через них.
swap(px, py) /* interchange *px and *py */ int *px, *py; { int tmp; temp = *px; *px = *py; *py = temp; }Указатели в качестве аргументов обычно используются в функциях, которыедолжны возвращать более одного значения. (можно сказать, что swapвозвращает два значения, новые значения ее аргументов). В качествепримера рассмотрим функцию getint, которая осуществляет преобразованиепоступающих в своболном формате данных, разделяя поток символов нацелые значения, по одному целому за одно обращение. Функция getintдолжна возвращать либо найденное значение, либо признак конца файла,если входные данные полностью исчерпаны. Эти значения должнывозвращаться как отдельные об'екты, какое бы значение ни использовалосьдля EOF, даже если это значение вводимого целого.
Одно из решений, основывающееся на описываемой вглаве 7 функции вводаscanf, состоит в том, чтобы при выходе на конец файла getint возвращалаEOF в качестве значения функции; любое другое возвращенное значениеговорит о нахождении нормального целого. Численное же значениенайденного целого возвращается через аргумент, который должен бытьуказателем целого. Эта организация разделяет статус конца файла ичисленные значения.
Следующий цикл заполняет массив целыми с помощью обращений к функцииgetint:
int n, v, array[size]; for (n = 0; n < size && getint(&v) != EOF; n++) array[n] = v;В результате каждого обращения v становится равным следующему целомузначению, найденному во входных данных. Обратите внимание, что вкачестве аргумента getint необходимо указать &v а не v. Использованиепросто v скорее всего приведет к ошибке адресации, поскольку getintполагает, что она работает именно с указателем.
Сама getint является очевидной модификацией написанной нами ранеефункции atoi:
getint(pn) /* get next integer from input */int *pn;{ int c,sign; while ((c = getch()) == ' ' \|\| c == '\n' \|\| c == '\t'); /* skip white space */ sign = 1; if (c == '+' \|\| c == '-') { /* record sign */ sign = (c == '+') ? 1 : -1; c = getch(); } for (*pn = 0; c >= OC' && c <= '9'; c = getch()) *pn = 10 * *pn + c - '0'; *pn *= sign; if (c != EOF) ungetch(c); return(c);}Выражение *pn используется всюду в getint как обычная переменная типаint. Мы также использовали функции getch и ungetch (описанные вглаве 4),так что один лишний символ, кототрый приходится считывать, может бытьпомещен обратно во ввод.- Упражнение 5-1.
- Напишите функцию getfloat, аналог getint для чисел с плавающей точкой.Какой тип должна возвращать getfloat в качестве значения функции?
Указатели и массивы
В языке "C" существует сильная взаимосвязь между указателями и массивами, настолько сильная, что указатели и массивы действительно следуетрассматривать одновременно. Любую операцию, которую можно выполнить спомощью индексов массива, можно сделать и с помощью указателей. Вариантс указателями обычно оказывается более быстрым, но и несколько болеетрудным для непосредственного понимания, по крайней мере дляначинающего. Описание
int a[10]определяет массив размера 10, т.е. набор из 10 последовательныхоб'ектов, называемых a[0], a[1], ..., a[9]. Запись a[i] соответствуетэлементу массива через i позиций от начала. Если pa - указательцелого, описанный как
int *paто присваивание
pa = &a[0]приводит к тому, что pa указывает на нулевой элемент массива a; этоозначает, что pa содержит адрес элемента a[0]. Теперь присваивание
x = *paбудет копировать содержимое a[0] в x.
Если ра указывает на некоторый определенный элемент массива a, то поопределению pa+1 указывает на следующий элемент, и вообще pa-iуказывает на элемент, стоящий на i позиций до элемента, указываемого pa,а pa+i на элемент, стоящий на i позиций после. Таким образом, если paуказывает на a[0], то
*(pa+1)ссылается на содержимое a[1], pa+i - адрес a[i], а *(pa+i) - содержимоеa[i].
Эти замечания справедливы независимо от типа переменных в массиве a.Суть определения "добавления 1 к указателю", а также его распространенияна всю арифметику указателей, состоит в том, что приращениемасштабируется размером памяти, занимаемой об'ектом, на которыйуказывает указатель. Таким образом, i в pa+i перед прибавлениемумножается на размер об'ектов, на которые указывает pa.
Очевидно существует очень тесное соответствие между индексацией иарифметикой указателей. В действительности компилятор преобразуетссылку на массив в указатель на начало массива. В результате этого имямассива является указательным выражением. Отсюда вытекает нескольковесьма полезных следствий. Так как имя массива является синонимомместоположения его нулевого элемента, то присваивание pa = &a[0] можнозаписать как pa = a.
Еще более удивительным, по крайней мере на первый взгляд, кажется тотфакт, что ссылку на a[i] можно записать в виде *(a+i).При анализировании выражения a[i] в языке "C" оно немедленнопреобразуется к виду *(a+i); эти две формы совершенно эквивалентны.Если применить операцию & к обеим частям такого соотношенияэквивалентности, то мы получим, что &a[i] и a+i тоже идентичны: a+i -адрес i-го элемента от начала a. С другой стороны, если pa являетсяуказателем, то в выражениях его можно использовать с индексом: pa[i]идентично *(pa+i). Короче, любое выражение, включающее массивы ииндексы, может быть записано через указатели и смещения и наоборот,причем даже в одном и том же утверждении.
Имеется одно различие между именем массива и указателем, котороенеобходимо иметь в виду. Указатель является переменной, так чтооперации pa=a и pa++ имеют смысл. Но имя массива является константой, ане переменной: конструкции типа a=pa или a++,или p=&a будут незаконными.
Когда имя массива передается функции, то на самом деле ей передаетсяместоположение начала этого массива. Внутри вызванной функции такойаргумент является точно такой же переменной, как и любая другая, такчто имя массива в качестве аргумента действительно являетсяуказателем, т.е. переменной, содержащей адрес. Мы можем использоватьэто обстоятельство для написания нового варианта функции strlen,вычисляющей длину строки.
strlen(s) /* return length of string s */ char *s; { int n; for (n = 0; *s != '\0'; s++) n++; return(n); }Операция увеличения s совершенно законна, поскольку эта переменнаяявляется указателем; s++ никак не влияет на символьную строку вобратившейся к strlen функции, а только увеличивает локальную дляфункции strlen копию адреса.Описания формальных параметров в определении функции в виде
char s[];и
char *s;совершенно эквивалентны; какой вид описания следует предпочесть,определяется в значительной степени тем, какие выражения будутиспользованы при написании функции. Если функции передается имямассива, то в зависимости от того, что удобнее, можно полагать, чтофункция оперирует либо с массивом, либо с указателем, и действоватьдалее соответвующим образом. Можно даже использовать оба видаопераций, если это кажется уместным и ясным.
Можно передать функции часть массива, если задать в качестве аргументауказатель начала подмассива. Например, если а - массив, то как
f(&a[2])так и
f(a+2)передают функции f адрес элемента a[2], потому что и &a[2], и a+2являются указательннми выражениями, ссылающимися на третий элемент аaВнутри функции f описания аргументов могут присутствовать в виде:
f(arr) int arr[]; { ... }или f(arr) int *arr; { ... }Что касается функции f, то тот факт, что ее аргумент в действительностиссылается к части большего массива,не имеет для нее никаких последствий.Адресная арифметика
Если р является указателем, то каков бы ни был сорт об'екта, накоторый он указывает, операция p++ увеличивает p так, что он указываетна следующий элемент набора этих об'ектов, а операция p +=i увеличиваетp так, чтобы он указывал на элемент, отстоящий на i элементов оттекущего элемента.эти И аналогичные конструкции представляют собойсамые простые и самые распространенные формы арифметики указателейили адресной арифметики.
Язык "C" последователен и постоянен в своем подходе к адреснойарифметике; об'единение в одно целое указателей, массивов и адреснойарифметики является одной из наиболее сильных стBрон языка. Давайтепроиллюстрируем некоторые из соответствующих возможностей языка напримере элементарной (но полезной, несмотря на свою простоту)программы распределения памяти. Имеются две функции: функцияalloc(n)возвращает в качестве своего значения указатель p, который указываетна первую из n последовательных символьных позиций, которые могутбыть использованы вызывающей функцию alloc программой для хранениясимволов; функция free(р) освобождает приобретенную таким образомпамять, так что ее в дальнейшем можно снова использовать. Программаявляется "элементарной", потому что обращения к free должныпроизводиться в порядке, обратном тому, в котором производилисьобращения к alloc. Таким образом, управляемая функциями alloc и freeпамять является стеком или списком, в котором последний вводимыйэлемент извлекается первым. Стандартная библиотека языка "C"содержит аналогичные функции, не имеющие таких ограничений, и, крометого, в главе 8мы приведем улучшенные варианты. Между тем, однако,для многих приложений нужна только тривиальная функция alloc дляраспределения небольших участков памяти неизвестных заранееразмеров в непредсказуемые моменты времени.
Простейшая реализация состоит в том, чтобы функция раздавалаотрезки большого символьного массива, которому мы присвоили имяallocbuf. Этот массив является собственностью функций alloc и free.Так как они работают с указателями, а не с индексами массива,никакой другой функции не нужно знать имя этого массива. Он можетбыть описан как внешний статический, т.е. он будет локальным поотношению к исходному файлу, содержащему alloc и free, и невидимымза его пределами. При практической реализации этот массив можетдаже не иметь имени; вместо этого он может быть получен в результатезапроса к операционной системе на указатель некоторого неименованногоблока памяти.
Другой необходимой информацией является то, какая часть массиваallocbuf уже использована. Мы пользуемся указателем первогосвободного элемента, названным allocp. Когда к функции alloc обращаютсяза выделением n символов, то она проверяет, достаточно ли осталось дляэтого места в allocbuf. Если достаточно, то alloc возвращает текущеезначение allocp (т.е. начало свободного блока), затем увеличивает егона n, с тем чтобы он указывал на следующую свободную область. Функцияfree(р) просто полагает allocp равным р при условии, что р указываетна позицию внутри allocbuf.
#define NULL 0 /* pointer value for error report */#define allocsize 1000 /* size of available space */static char allocbuf[allocsize];/* storage for alloc */static char *allocp = allocbuf; /* next free position */char *alloc(n) /* return pointer to n characters */int n;{ if (allocp + n <= allocbuf + allocsize) { allocp += n; return(allocp - n); /* old p */ } else /* not enough room */ return( NULL );}free(p) /* free storage pointed by p */char *p;{ if (p >= allocbuf && p < allocbuf + allocsize) allocp = p;}Дадим некоторые пояснения. Вообще говоря, указатель может бытьинициализирован точно так же, как и любая другая переменная, хотяобычно единственными осмысленными значениями являются NULL (этообсуждается ниже) или выражение, включающее адреса ранееопределенных данных соответствующего типа. Описание
static char *allocp = allocbuf;определяет allocp как указатель на символы и инициализирует его так,чтобы он указывал на allocbuf, т.е. на первую свободную позицию приначале работы программы. Так как имя массива является адресом егонулевого элемента, то это можно было бы записать в виде
static char *allocp = &allocbuf[0];используйте ту запись, которая вам кажется более естественной.С помощью проверки
if( allocp + n <= allocbuf + allocsize )выясняется, осталось ли достаточно места, чтобы удовлетворить запросна n символов. Если достаточно, то новое значение allocp не будетуказывать дальше, чем на последнюю позицию allocbuf. Если запросможет быть удовлетворен, то alloc возвращает обычный указатель(обратите внимание на описание самой функции). Если же нет, то allocдолжна вернуть некоторый признак, говорящий о том, что больше местане осталось. В языке "Си" гарантируется, что ни один правильныйуказатель данных не может иметь значение нуль, так что возвращениенуля может служить в качестве сигнала о ненормальном событии, вданном случае об отсутствии места. Мы, однако, вместо нуля пишем NULL,с тем чтобы более ясно показать, что это специальное значение указателя.Вообще говоря, целые не могут осмысленно присваиваться указателям, ануль - это особый случай.
Проверки вида
if (allocp + n <= allocbuf + aloocsize)и
if (p >= allocbuf && p < allocbuf + allocsize)демонстрируют несколько важных аспектов арифметики указателей. Во-первых,при определенных условиях указатели можно сравнивать. Если p и qуказывают на элементы одного и того же массива, то такие отношения, как<, >= и т.д., работают надлежащим образом. Например,
p < qистинно, если p указывает на более ранний элемент массива, чем q.Отношения == и != тоже работают. Любой указатель можно осмысленнымобразом сравнить на равенство или неравенство с NULL. Но ни за чоонельзя ручаться, если вы используете сравнения при работе с указателями,указывающими на разные массивы. Если вам повезет, то на всех машинахвы получите очевидную бессмыслицу. Если же нет, то ваша программабудет правильно работать на одной машине и давать непостижимыерезультаты на другой.
Во-вторых, как мы уже видели, указатель и целое можно складывать ивычитать. Конструкция
p + nподразумевает n-ый об'ект за тем, на который p указывает в настоящиймомент. Это справедливо независимо от того, на какой вид об'ектов pдолжен указывать; компилятор сам масштабирует n в соответствии сопределяемым из описания p размером об'ектов, указываемых с помощьюpр.Например, на pdp-11 масштабирующий множитель равен 1 для char, 2 дляint и short, 4 для long и float и 8 для double.
Вычитание указателей тоже возможно: если р и q указывают на элементыодного и того же массива, то p-q - количество элементов между p и q.Этот факт можно использовать для написания еще одного вариантафункции strlen:
strlen(s) /* return length of string s */ char *s; { char *p = s; while (*p != '\0') p++; return(p-s); }При описании указатель р в этой функции инициализирован посредствомстроки s, в результате чего он указывает на первый символ строки.В цикле while по очереди проверяется каждый символ до тех пор, покане появится символ конца строки \0. Так как значение \0 равно нулю,а while только выясняет, имеет ли выражение в нем значение 0, то вданном случае явную проверку можно опустить. Такие циклы частозаписывают в видеwhile (*p) p++;
Так как p указывает на символы, то оператор p++ передвигает p каждыйраз так, чтобы он указывал на следующий символ. В результате p-s даетчисло просмотренных символов, т.е. длину строки. Арифметика указателейпоследовательна: если бы мы имели дело с переменными типа float, которыезанимают больше памяти, чем переменные типа char, и если бы p былуказателем на float, то оператор p++ передвинул быpр на следующееfloat. Таким образом, мы могли бы написать другой вариант функцииalloc, распределяющей память для float, вместо char, просто замениввсюду в alloc и free описатель char на float. Все действия суказателями автоматически учитывают размер об'ектов, на которые ониуказывают, так что больше ничего менять не надо.
За исключением упомянутых выше операций (сложение и вычитание указателяи целого, вычитание и сравнение двух указателей), вся остальнаяарифметика указателей является незаконной. Запрещено складывать двауказателя, умножать, делить, сдвигать или маскировать их, а такжеприбавлять к ним переменные типа float или double.
Указатели символов и функции
Строчная константа, как, например,
"i am a string"является массивом символов. Компилятор завершает внутреннеепредставление такого массива символом \0, так что программы могутнаходить его конец. Таким образом, длина массива в памяти оказываетсяна единицу больше числа символов между двойными кавычками.
По-видимому чаще всего строчные константы появляются в качествеаргументов функций, как, например, в
printf ("hello, world\n");Когда символьная строка, подобная этой, появляется в программе, тодоступ к ней осуществляется с помощью указателя символов; функцияprintf фактически получает указатель символьного массива.Конечно, символьные массивы не обязаны быть только аргументамифункций. Если описать message как
char *message;то в результате оператора
message = "now is the time";переменная message станет указателем на фактический массив символов.Это не копирование строки; здесь участвуют только указатели. В языке"C" не предусмотрены какиe-либо операции для обработки всей строкисимволов как целого.
Мы проиллюстрируем другие аспекты указателей и массивов, разбираядве полезные функции из стандартной библиотеки ввода-вывода, котораябудет рассмотрена в главе 7.
Первая функция - это strcpy(s,t), которая копирует строку t в строку s.Аргументы написаны именно в этом порядке по аналогии с операциейприсваивания, когда для того, чтобы присвоить t к s обычно пишут
s = t;сначала приведем версию с массивами:
strcpy(s, t) /* copy t to s */ char s[], t[]; { int i; i = 0; while ((s[i] = t[i]) != '\0') i++; }Для сопоставления ниже дается вариант strcpy с указателями.
strcpy(s, t) /* copy t to s; pointer version 1 */ char *s, *t; { while ((*s = *t) != '\0') { s++; t++; } }Так как аргументы передаются по значению, функция strcpy можетиспользовать s и t так, как она пожелает. Здесь они с удобствомполагаются указателями, которые передвигаются вдоль массивов, поодному символу за шаг, пока не будет скопирован в s завершающий в tсимвол \0.На практике функция strcpy была бы записана не так, как мы показаливыше. Вот вторая возможность:
strcpy(s, t) /* copy t to s; pointer version 2 */ char *s, *t; { while ((*s++ = *t++) != '\0') ; }Здесь увеличение s и t внесено в проверочную часть. Значением *t++является символ, на который указывал t до увеличения; постфикснаяоперация ++ не изменяет t, пока этот символ не будет извлечен.Точно так же этот символ помещается в старую позицию s, до того как sбудет увеличено. Конечный результат заключается в том, что все символы,включая завершающий \0, копируются из t в s.И как последнее сокращение мы опять отметим, что сравнение с \0является излишним, так что функцию можно записать в виде
strcpy(s, t) /* copy t to s; pointer version 3 */ char *s, *t; { while (*s++ = *t++) ; }Хотя с первого взгляда эта запись может показаться загадочной, онадает значительное удобство. Этой идиомой следует овладеть уже хотя быпотому, что вы с ней будете часто встречаться в "C"-программах.Вторая функция - strcmp(s, t), которая сравнивает символьные строки s иt, возвращая отрицательное, нулевое или положительное значение всоответствии с тем, меньше, равно или больше лексикографически s, чем t.Возвращаемое значение получается в результате вычитания символов изпервой позиции, в которой s и t не совпадают.
strcmp(s, t) /* return <0 if s<t, 0 if s==t, >0 if s>t */ char s[], t[]; { int i; i = 0; while (s[i] == t[i]) if (s[i++] == '\0') return(0); return(s[i]-t[i]); }Вот версия strcmp с указателями:strcmp(s, t) /* return <0 if s<t, 0 if s==t, >0 if s>t */char *s, *t;{for ( ; *s == *t; s++, t++)if (*s == '\0')return(0);return(*s-*t);}Так как ++ и -- могут быть как постфиксными, так и префикснымиоперациями, встречаются другие комбинации * и ++ и --, хотя и менеечасто.
Например
*++pувеличивает р до извлечения символа, на который указывает р, а
*--pсначала уменьшает p.
- Упражнение 5-2.
- Напишите вариант с указателями функции strcat изглавы 2:strcat(s, t) копирует строку t в конец s.
- Упражнение 5-3.
- Напишите макрос для strcpy.
- Упражнение 5-4.
- Перепишите подходящие программы из предыдущих глав и упражнений,используя указатели вместо индексации массивов. Хорошие возможностидля этого предоставляют функции getline /главы1 и 4/,atoi, itoaи их варианты /главы 2, 3 и 4/, reverse/глава 3/, index иgetop /глава 4/.
Указатели - не целые.
Вы, возможно, обратили внимание в предыдущих "C"-программах на довольнонепринужденное отношение к копированию указателей. В общем это верно,что на большинстве машин указатель можно присвоить целому и передатьего обратно, не изменив его; при этом не происходит никакогомасштабирования или преобразования и ни один бит не теряется. Ксожалению, это ведет к вольному обращению с функциями, возвращающимиуказатели, которые затем просто передаются другим функциям, -необходимые описания указателей часто опускаются. Рассмотрим, например,функцию strsave(s), которая копирует строку s в некоторое место дляхранения, выделяемое посредством обращения к функции alloc, ивозвращает указатель на это место. Правильно она должна быть записанатак:
char *strsave(s) /* save string s somewhere */ char *s; { char *p, *alloc(); if ((p = alloc(strlen(s)+1)) != NULL) strcpy(p, s); return(p); }На практике существует сильное стремление опускать описания: *strsave(s) /* save string s somewhere */ { char *p; if ((p = alloc(strlen(s)+1)) != NULL) strcpy(p, s); return(p); }Эта программа будет правильно работать на многих машинах, потому чтопо умолчанию функции и аргументы имеют тип int, а указатель и целоеобычно можно безопасно пересылать туда и обратно. Однако такой стильпрограммирования в своем существе является рискованным, посколькузависит от деталей реализации и архитектуры машины и может привести кнеправильным результатам на конкретном используемом вами компиляторе.Разумнее всюду использовать полные описания. (отладочная программаlint предупредит о таких конструкциях, если они по неосторожностивсе же появятся).Многомерные массивы.
В языке "C" предусмотрены прямоугольные многомерные массивы, хотя напрактике существует тенденция к их значительно более редкомуиспользованию по сравнению с массивами указателей. В этом разделе мырассмотрим некоторые их свойства.
Рассмотрим задачу преобразования дня месяца в день года и наоборот.Например, 1-ое марта является 60-м днем невисокосного года и 61-мднем високосного года. Давайте введем две функции для выполненияэтих преобразований: day_of_year преобразует месяц и день в день года,а month_day преобразует день года в месяц и день. Так как эта последняяфункция возвращает два значения, то аргументы месяца и дня должны бытьуказателями:
month_day(1977, 60, &m, &d)полагает м равным 3 и d равным 1 (1-ое марта).
Обе эти функции нуждаются в одной и той же информационной таблице,указывающей число дней в каждом месяце. Так как число дней в месяцев високосном и в невисокосном году отличается, то проще представитьих в виде двух строк двумерного массива, чем пытаться прослеживать вовремя вычислений, что именно происходит в феврале. Вот этот массив ивыполняющие эти преобразования функции:
static int day_tab[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(year, month, day) /* set day of year */ int year, month, day; /* from month & day */ { int i, leap; leap = year%4 == 0 && year%100 != 0 || year%400 == 0; for (i = 1; i < month; i++) day += day_tab[leap][i]; return(day); } month_day(year, yearday, pmonth, pday) /*set month,day */ int year, yearday, *pmonth, *pday; /* from day of year */ { leap = year%4 == 0 && year%100 != 0 || year%400 == 0; for (i = 1; yearday > day_tab[leap][i]; i++) yearday -= day_tab[leap][i]; *pmonth = i; *pday = yearday; }Массив day_тав должен быть внешним как для day_of_year, так и дляmonth_day, поскольку он используется обеими этими функциями.Массив day_тав является первым двумерным массивом, с которым мы имеемдело. По определению в "Си" двумерный массив по существу являетсяодномерным массивом, каждый элемент которого является массивом.Поэтому индексы записываются как
day_tab[i][j]а не
day_tab [i, j]как в большинстве языков. В остальном с двумерными массивами можно восновном обращаться таким же образом, как в других языках. Элементыхранятся по строкам, т.е. при обращении к элементам в порядке ихразмещения в памяти быстрее всего изменяется самый правый индекс.
Массив инициализируется с помощью списка начальных значений,заключенных в фигурные скобки; каждая строка двумерного массиваинициализируется соответствующим подсписком. Мы поместили в началомассива day_тав столбец из нулей для того, чтобы номера месяцевизменялись естественным образом от 1 до 12, а не от 0 до 11. Так какза экономию памяти у нас пока не награждают, такой способ проще,чем подгонка индексов.
Если двумерный массив передается функции, то описание соответствующегоаргумента функции должно содержать количество столбцов; количествострок несущественно, поскольку, как и прежде, фактически передаетсяуказатель. В нашем конкретном случае это указатель об'ектов,являющихся массивами из 13 чисел типа int. Таким образом, если бытребовалось передать массив day_тав функции f, то описание в fимело бы вид:
f(day_tab) int day_tab[2][13]; { ... }Так как количество строк является несущественным, то описаниеаргумента в f могло бы быть таким:int day_tab[][13];или таким
int (*day_tab)[13];в которм говорится, что аргумент является указателем массива из 13целых. Круглые скобки здесь необходимы, потому что квадратныескобки [] имеют более высокий уровень старшинства, чем *; как мыувидим в следующем разделе, без круглых скобок
int *day_tab[13];является описанием массива из 13 указателей на целые.
Массивы указателей; указатели указателей
Так как указатели сами являются переменными, то вы вполне могли быожидать использования массива указателей. Это действительно так. Мыпроиллюстрируем это написанием программы сортировки в алфавитномпорядке набора текстовых строк, предельно упрощенного вариантаутилиты sort операционной систем UNIX.
В главе 3мы привели функцию сортировки по шеллу, которая упорядочиваламассив целых. Этот же алгоритм будет работать и здесь, хотя теперьмы будем иметь дело со строчками текста различной длины, которые, вотличие от целых, нельзя сравнивать или перемещать с помощью однойоперации. Мы нуждаемся в таком представлении данных, которое быпозволяло удобно и эффективно обрабатывать строки текста переменнойдлины.
Здесь и возникают массивы указателей. Если подлежащие сортировкесроки хранятся одна за другой в длинном символьном массиве(управляемом, например, функцией alloc), то к каждой строке можнообратиться с помощью указателя на ее первый символ. Сами указателиможно хранить в массиве. Две строки можно сравнить, передав ихуказатели функции strcmp. Если две расположенные в неправильномпорядке строки должны быть переставлены, то фактически переставляютсяуказатели в массиве указателей, а не сами тексты строк. Этимисключаются сразу две связанные проблемы: сложного управления памятьюи больших дополнительных затрат на фактическую перестановку строк.
Процесс сортировки включает три шага:
- чтение всех строк ввода
- их сортировка
- вывод их в правильном порядке
Как обычно, лучше разделить программу на несколько функций всоответствии с естественным делением задачи и выделить ведущуюфункцию, управляющую работой всей программы.
Давайте отложим на некоторое время рассмотрение шага сортировки исосредоточимся на структуре данных и вводe-выводе. Функция,осуществляющая ввод, должна извлечь символы каждой строки, запомнитьих и построить массив указателей строк. Она должна также подсчитатьчисло строк во вводе, так как эта информация необходима присортировке и выводе. Так как функция ввода в состоянии справитьсятолько с конечным числом вводимых строк, в случае слишком большогоих числа она может возвращать некоторое число, отличное отвозможного числа строк, например -1. Функция осуществляющая вывод,должна печатать строки в том порядке, в каком они появляются вмассиве указателей.
#define NULL 0 #define lines 100 /* max lines to be sorted */ main() /* sort input lines */ { char *lineptr[lines]; /*pointers to text lines */ int nlines; /* number of input lines read */ if ((nlines = readlines(lineptr, lines)) >= 0) { sort(lineptr, nlines); writelines(lineptr, nlines); } else printf("input too big to sort\n"); } #define maxlen 1000 readlines(lineptr, maxlines) /* read input lines */ char *lineptr[]; /* for sorting */ int maxlines; { int len, nlines; char *p, *alloc(), line[maxlen]; nlines = 0; while ((len = getline(line, maxlen)) > 0) if (nlines >= maxlines) return(-1); else if ((p = alloc(len)) == NULL) return (-1); else { line[len-1] = '\0'; /* zap newline */ strcpy(p,line); lineptr[nlines++] = p; } return(nlines); }Символ новой строки в конце каждой строки удаляется, так что онникак не будет влиять на порядок, в котором сортируются строки. writelines(lineptr, nlines) /* write output lines */ char *lineptr[]; int nlines; { int i; for (i = 0; i < nlines; i++) printf("%s\n", lineptr[i]); }Существенно новым в этой программе является описание
char *lineptr[lines];которое сообщает, что lineptr является массивом из lines элементов,каждый из которых - указатель на переменные типа char. Это означает,что lineptr[i] - указатель на символы, а *lineptr[i] извлекает символ.
Так как сам lineptr является массивом, который передается функцииwritelines, с ним можно обращаться как с указателем точно таким жеобразом, как в наших более ранних примерах. Тогда последнююфункцию можно переписать в виде:
writelines(lineptr, nlines) /* write output lines */ char *lineptr[]; int nlines; { int i; while (--nlines >= 0) printf("%s\n", *lineptr++); }Здесь *lineptr сначала указывает на первую строку; каждое увеличениепередвигает указатель на следующую строку, в то время как nlinesубывает до нуля.Справившись с вводом и выводом, мы можем перейти к сортировке.Программа сортировки по шеллу изглавы 3 требует очень небольшихизменений: должны быть модифицированы описания, а операциясравнения выделена в отдельную функцию. Основной алгоритм остаетсятем же самым, и это дает нам определенную уверенность, что онпо-прежнему будет работать.
sort(v, n) /* sort strings v[0] ... v[n-1] */ char *v[]; /* into increasing order */ int n; { int gap, i, j; char *temp; for (gap = n/2; gap > 0; gap /= 2) for (i = gap; i < n; i++) for (j = i - gap; j >= 0; j -= gap) { if (strcmp(v[j], v[j+gap]) <= 0) break; temp = v[j]; v[j] = v[j+gap]; v[j+gap] = temp; } }Так как каждый отдельный элемент массива v (имя формального параметра,соответствующего lineptr) является указателем на символы, то и темрдолжен быть указателем на символы, чтобы их было можно копироватьдруг в друга.Мы написали эту программу по возможности более просто с тем,чтобы побыстрее получить работающую программу. Она могла бы работатьбыстрее, если, например, вводить строки непосредственно в массив,управляемый функцией readlines, а не копировать их в line, а затем вскрытое место с помощью функции alloc. Но мы считаем, что будетразумнее первоначальный вариант сделать более простым для понимания,а об "эффективности" позаботиться позднее. Все же, по-видимому,способ, позволяющий добиться заметного ускорения работы программысостоит не в исключении лишнего копирования вводимых строк. Болеевероятно, что существенной разницы можно достичь за счет заменысортировки по шеллу на нечто лучшее, например, на метод быстройсортировки.
В главе 1 мы отмечали, что поскольку в циклах while и for проверкаосуществляется до того, как тело цикла выполнится хотя бы один раз,эти циклы оказываются удобными для обеспечения правильной работыпрограммы при граничных значениях, в частности, когда ввода вообщенет. Очень полезно просмотреть все функции программы сортировки,разбираясь, что происходит, если вводимый текст отсутствует.
Инициализация массивов указателей
Рассмотрим задачу написания функции month_name(n), которая возвращаетуказатель на символьную строку, содержащую имя n-го месяца. Этоидеальная задача для применения внутреннего статического массива.Функция month_name содержит локальный массив символьных строк и приобращении к ней возвращает указатель нужной строки. Тема настоящегораздела - как инициализировать этот массив имен.
Синтаксис вполне аналогичен предыдущим инициализациям:
char *month_name(n) /* return name of n-th month */int n;{ static char *name[] = { "illegal month", "january", "february", "march", "april", "may", "jun", "july", "august", "september", "october", "november", "december" }; return ((n < 1 \|\| n > 12) ? name[0] : name[n]);}Описание массива указателей на символы name точно такое же, каканалогичное описание lineptr в примере с сортировкой. Инициализаторомявляется просто список символьных строк;каждая строка присваиваетсясоответствующей позиции в массиве. Более точно, символы i-ой строкипомещаются в какоe-то иное место, а ее указатель хранится в name[i].Поскольку размер массива name не указан, компилятор сам подсчитываетколичество инициализаторов и соответственно устанавливаетправильное число.Указатели и многомерные массивы
Начинающие изучать язык "C" иногда становятся в тупик перед вопросомо различии между двумерным массивом и массивом указателей, таким какname в приведенном выше примере. Если имеются описания
int a[10][10]; int *b[10];то a и b можно использовать сходным образом в том смысле, что кака[5][5], так и в[5][5] являются законными ссылками на отдельное числотипа int. Но а - настоящий массив: под него отводится 100 ячеек памятии для нахождения любого указанного элемента проводятся обычныевычисления с прямоугольными индексами. Для в, однако, описаниевыделяет только 10 указателей; каждый указатель должен быть установлентак, чтобы он указывал на массив целых. Если предположить, чтокаждый из них указывает на массив из 10 элементов, то тогда гдe-тобудет отведено 100 ячеек памяти плюс еще десять ячеек для указателей.Таким образом, массив указателей использует несколько большийоб'ем памяти и может требовать наличие явного шага инициализации.Но при этом возникают два преимущества: доступ к элементуосуществляется косвенно через указатель, а не посредствомамножения и сложения, и строки массива могут иметь различные длины.Это означает, что каждый элемент в не должен обязательноуказывать на вектор из 10 элементов; некоторые могут указывать навектор из двух элементов, другие - из двадцати, а третьи могутвообще ни на что не указывать.
Хотя мы вели это обсуждение в терминах целых, несомненно, чащевсего массивы указателей используются так, как мы продемонстрировалина функции month_name, - для хранения символьных строк различнойдлины.
Командная строка аргументов
Системные средства, на которые опирается реализация языка "C",позволяют передавать командную строку аргументов или параметровначинающей выполняться программе. Когда функция main вызывается кисполнению, она вызывается с двумя аргументами. Первый аргумент(условно называемый argc) указывает число аргументов в команднойстроке, с которыми происходит обращение к программе;второйаргумент (argv) является указателем на массив символьных строк,содержащих эти аргументы, по одному в строке. Работа с такимистроками - это обычное использование многоуровневых указателей.
Самую простую иллюстрацию этой возможности и необходимых при этомописаний дает программа есно, которая просто печатает в одну строкуаргументы командной строки, разделяя их пробелами. Таким образом,если дана команда
echo hello, worldто выходом будет
hello, world
По соглашению argv[0] является именем, по которому вызываетсяпрограмма, так что argc по меньшей мере равен 1. В приведенномвыше примере argc равен 3, а argv[0], argv[1] и argv[2] равнысоответственно "есно", "hello," и "world". Первым фактическимагументом является argv[1], а последним - argv[argc-1]. Еслиargc равен 1, то за именем программы не следует никакой команднойстроки аргументов. Все это показано в есно:
main(argc, argv) /* есho arguments; 1st version */int argc;char *argv[];{ int i; for (i = 1; i < argc; i++) printf("%s%с", argv[i], (i<argc-1) ? ' ' : '\n');}Поскольку argv является указателем на массив указателей, то существуетнесколько способов написания этой программы, использующих работу суказателем, а не с индексацией массива. Мы продемонстрируем дваварианта.main(argc, argv) /* echo arguments; 2nd version */int argc;char *argv[];{ while (--argc > 0) printf("%s%с",*++argv, (argc > 1) ? ' ' : '\n');}Так как argv является указателем на начало массива строк-аргументов,то, увеличив его на 1 (++argv), мы вынуждаем его указывать наподлинный аргумент argv[1], а не на argv[0]. Каждое последующееувеличение передвигает его на следующий аргумент;при этом *argvстановится указателем на этот аргумент. Одновременно величинаargc уменьшается;когда она обратится в нуль, все аргументы будутуже напечатаны.
Другой вариант:
main(argc, argv) /* есho arguments; 3rd version */int argc;char *argv[];{ while (--argc > 0) printf((argc > 1) ? "%s" : "%s\n", *++argv);}эта версия показывает, что аргумент формата функции printf можетбыть выражением, точно так же, как и любой другой. Такое использованиевстречается не очень часто, но его все же стоит запомнить.Как второй пример, давайте внесем некоторые усовершенствованияв программу отыскания заданной комбинации символов изглавы 4.Если вы помните, мы поместили искомую комбинацию глубоко внутрьпрограммы, что очевидно является совершенно неудовлетворительным.Следуя команде grep системы UNIX, давайте изменим программу так,чтобы эта комбинация указывалась в качестве первого аргументастроки.
#define maxline 1000main(argc, argv) /* find pattern from first argument */int argc;char *argv[];{ char line[maxline]; if (argc != 2) printf ("usage: find pattern\n"); else while (getline(line, maxline) > 0) if (index(line, argv[1] >= 0) printf("%s", line);}Теперь может быть развита основная модель, иллюстрирующаядальнейшее использование указателей. Предположим, что нам надопредусмотреть два необязательных аргумента. Один утверждает:"напечатать все строки за исключением тех, которые содержатданную комбинацию", второй гласит:"перед каждой выводимой строкойдолжен печататься ее номер".
Общепринятым соглашением в "C"-программах является то, что аргумент,начинающийся со знака минус, вводит необязательный признак илипараметр. Если мы, для того, чтобы сообщить об инверсии, выберем-x, а для указания о нумерации нужных строк выберем -n("номер"),то команда
find -x -n theпри входных данных
now is the timefor all good mento come to the aidof their party.должна выдать
2:for all good men
Нужно, чтобы необязательные аргументы могли располагаться впроизвольном порядке, и чтобы остальная часть программы независела от количества фактически присутствующих аргументов.В частности, вызов функции index не должен содержать ссылкуна argv[2], когда присутствует один необязательный аргумент,и на argv[1], когда его нет. Более того, для пользователейудобно, чтобы необязательные аргументы можно было об'единитьв виде:
"find -nx the"Вот сама программа:
#define maxline 1000main(argc, argv) /* find pattern from first argument */int argc;char *argv[];{ char line[maxline], *s; lCng lineno = 0; int except = 0, number = 0; while (--argc > 0 && (*++argv)[0] == '-') for (s = argv[0]+1; *s != '\0'; s++) switch (*s) { case 'x': except = 1; break; case 'n': number = 1; break; default: printf("find: illegal option %с\n", *s); argc = 0; break; } if (argc != 1) printf("usage: find -x -n pattern\n"); else while (getline(line, maxline) > 0) { lineno++; if ((index(line, *argv) >= 0) != except) { if (number) printf("%ld: ", lineno);A printf("%s", line); } }}Аргумент argv увеличивается перед каждым необязательным аргументом,в то время как аргумент argc уменьшается. Если нет ошибок, то вконце цикла величина argc должна равняться 1, а *argv должноуказывать на заданную комбинацию. Обратите внимание на то, что*++argv является указателем аргументной строки;(*++argv)[0] -ее первый символ. Круглые скобки здесь необходимы, потому что безних выражение бы приняло совершенно отличный (и неправильный) вид*++(argv[0]). Другой правильной формой была бы **++argv.add 2 3 4 + *
вычисляет 2*(3+4).entab m+n
означающую табуляционные остановки через каждые n столбцов,начиная со столбца м. Выберите удобное (для пользователя) поведениефункции по умолчанию.tail -n
печатает последние n строк. Программа должна действовать рационально,какими бы неразумными ни были бы ввод или значение n. Составьтепрограмму так, чтобы она оптимальным образом использовала доступнуюпамять:строки должны храниться, как в функции sort, а не в двумерноммассиве фиксированного размера.
Указатели на функции
В языке "C" сами функции не являются переменными, но имеется возможностьопределить указатель на функцию, который можно обрабатывать, передаватьдругим функциям, помещать в массивы и т.д. Мы проиллюстрируем это,проведя модификацию написанной ранее программы сортировки так, чтобыпри задании необязательного аргумента -n она бы сортировала строкиввода численно, а не лексикографически.
Сортировка часто состоит из трех частей - сравнения, котороеопределяет упорядочивание любой пары об'ектов, перестановки,изменяющей их порядок, и алгоритма сортировки, осуществляющегосравнения и перестановки до тех пор, пока об'екты не расположатсяв нужном порядке. Алгоритм сортировки не зависит от операцийсравнения и перестановки, так что, передавая в него различныефункции сравнения и перестановки, мы можем организовать сортировкупо различным критериям. Именно такой подход используется в нашейновой программе сортировки.
Как и прежде, лексикографическое сравнение двух строк осуществляетсяфункцией strcmp, а перестановка функцией swap; нам нужна еще функцияnumcmp, сравнивающая две строки на основе численного значения ивозвращающая условное указание того же вида, что и strcmp. Эти трифункции описываются в main и указатели на них передаются в sort.В свою очередь функция sort обращается к этим функциям через ихуказатели. Мы урезали обработку ошибок в аргументах с тем, чтобысосредоточиться на главных вопросах.
#define lines 100 /* мax number of linestC be sorted */main(argc, argv) /* sort input lines */int argc;char *argv[];{ char *lineptr[lines]; /* pointers to text lines */ int nlines; /* number of input lines read */ int strcmp(), numcmp(); /* comparsion functions */ int swap(); /* exchange function */ int numeric = 0; /* 1 if numeric sort */ if(argc>1 && argv[1][0] == '-' && argv[1][1]=='n') numeric = 1; if(nlines = readlines(lineptr, lines)) >= 0) { if (numeric) sort(lineptr, nlines, numcmp, swap); else sort(lineptr, nlines, strcmp, swap); writelines(lineptr, nlines); } else printf("input too big to sort\n");}Здесь strcmp, nimcmp и swap - адреса функций;так как известно,что это функции, операция & здесь не нужна совершенно аналогичнотому, как она не нужна и перед именем массива. Передача адресов функцийорганизуется компилятором.
Второй шаг состоит в модификации sort:
sort(v, n, comp, exch) /* sort strings v[0] ... v[n-1] */char *v[]; /* into increasing order */int n;int (*comp)(), (*exch)();{ int gap, i, j; for(gap = n/2; gap > 0; gap /= 2) for(i = gap; i < n; i++) for(j = i-gap; j >= 0; j -= gap) { if((*comp)(v[j], v[j+gap]) <= 0) break; (*exch)(&v[j], &v[j+gap]); }}Здесь следует обратить определенное внимание на описания. Описаниеint (*comp)()говорит, что сомр является указателем на функцию, которая возвращаетзначение типа int. Первые круглые скобки здесь необходимы;без нихописаниеint *comp()говорило бы, что comp является функцией, возвращающей указатель нацелые, что, конечно, совершенно другая вещь.
Использование comp в строке
if (*comp)(v[j], v[j+gap]) <= 0)полностью согласуется с описанием:comp - указатель на функцию,*comp - сама функция, а
(*comp)(v[j], v[j+gap])- обращение к ней. Круглые скобки необходимы для правильногооб'единения компонентов.
Мы уже приводили функцию strcmp, сравнивающую две строки попервому численному значению:
numcmp(s1, s2) /* compare s1 and s2 numerically */char *s1, *s2;{ double atof(), v1, v2; v1 = atof(s1); v2 = atof(s2); if(v1 < v2) return(-1); else if(v1 > v2) return(1); else return (0);}Заключительный шаг состоит в добавлении функции swap, переставляющейдва указателя. Это легко сделать, непосредственно используя то, чтомы изложили ранее в этой главе.
swap(px, py) /* interchange *px and *py */char *px[], *py[];{ char *temp; temp = *px; *px = *py; *py = temp;}Имеется множество других необязятельных аргументов, которые могутбыть включены в программу сортировки:некоторые из них составляютинтересные упражнения.