раммах на довольно непринужденное отношение к копированию
указателей. В общем это верно, что на большинстве машин ука-
затель можно присвоить целому и передать его обратно, не из-
менив его; при этом не происходит никакого масштабирования
или преобразования и ни один бит не теряется. к сожалению,
это ведет к вольному обращению с функциями, возвращающими
указатели, которые затем просто передаются другим функциям,
- необходимые описания указателей часто опускаются. Рассмот-
рим, например, функцию 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)
Полагает M равным 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_TAB должен быть внешним как для DAY_OF_YEAR, так
и для MONTH_DAY, поскольку он используется обеими этими фун-
кциями.
Массив DAY_TAB является первым двумерным массивом, с ко-
торым мы имеем дело. По определению в "C" двумерный массив
по существу является одномерным массивом, каждый элемент ко-
торого является массивом. Поэтому индексы записываются как
DAY_TAB[I][J]
а не
DAY_TAB [I, J]
как в большинстве языков. В остальном с двумерными массивами
можно в основном обращаться таким же образом, как в других
языках. Элементы хранятся по строкам, т.е. При обращении к
элементам в порядке их размещения в памяти быстрее всего из-
меняется самый правый индекс.
Массив инициализируется с помощью списка начальных зна-
чений, заключенных в фигурные скобки; каждая строка двумер-
ного массива инициализируется соответствующим подсписком. Мы
поместили в начало массива DAY_TAB столбец из нулей для то-
го, чтобы номера месяцев изменялись естественным образом от
1 до 12, а не от 0 до 11. Так как за экономию памяти у нас
пока не награждают, такой способ проще, чем подгонка индек-
сов.
Если двумерный массив передается функции, то описание
соответствующего аргумента функции должно содержать количес-
тво столбцов; количество строк несущественно, поскольку, как
и прежде, фактически передается указатель. В нашем конкрет-
ном случае это указатель объектов, являющихся массивами из
13 чисел типа INT. Таким образом, если бы требовалось пере-
дать массив DAY_TAB функции 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.
Если две расположенные в неправильном порядке строки должны
быть переставлены, то фактически переставляются указатели в
массиве указателей, а не сами тексты строк. Этим исключаются
сразу две связанные проблемы: сложного управления памятью и
больших дополнительных затрат на фактическую перестановку
строк.
Процесс сортировки включает три шага:
чтение всех строк ввода
их сортировка
вывод их в правильном порядке
Как обычно, лучше разделить программу на несколько функций в
соответствии с естественным делением задачи и выделить веду-
щую функцию, управляющую работой всей программы.
Давайте отложим на некоторое время рассмотрение шага сорти-
ровки и сосредоточимся на структуре данных и вводе-выводе.
Функция, осуществляющая ввод, должна извлечь символы каждой
строки, запомнить их и построить массив указателей строк.
Она должна также подсчитать число строк во вводе, так как
эта информация необходима при сортировке и выводе. так как
функция ввода в состоянии справиться только с конечным чис-
лом вводимых строк, в случае слишком большого их числа она
может возвращать некоторое число, отличное от возможного
числа строк, например -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) является указателем на
символы, то и TEMP должен быть указателем на символы, чтобы
их было можно копировать друг в друга.
Мы написали эту программу по возможности более просто с
тем, чтобы побыстрее получить работающую программу. Она мог-
ла бы работать быстрее, если, например, вводить строки не-
посредственно в массив, управляемый функцией READLINES, а не
копировать их в LINE, а затем в скрытое место с помощью фун-
кции ALLOC. но мы считаем, что будет разумнее первоначальный
вариант сделать более простым для понимания, а об "эффектив-
ности" позаботиться позднее. Все же, по-видимому, способ,
позволяющий добиться заметного ускорения работы программы
состоит не в исключении лишнего копирования вводимых строк.
Более вероятно, что существенной разницы можно достичь за
счет замены сортировки по шеллу на нечто лучшее, например,
на метод быстрой сортировки.
В главе 1 мы отмечали, что поскольку в циклах WHILE и
FOR проверка осуществляется до того, как тело цикла выпол-
нится хотя бы один раз, эти циклы оказываются удобными для
обеспечения правильной работы программы при граничных значе-
ниях, в частности, когда ввода вообще нет. Очень полезно
просмотреть все функции программы сортировки, разбираясь,
что происходит, если вводимый текст отсутствует.
Упражнение 5-5
--------------
Перепишите функцию READLINES таким образом, чтобы она
помещала строки в массив, предоставляемый функцией MAIN, а
не в память, управляемую обращениями к функции ALLOC. На-
сколько быстрее стала программа?
Рассмотрим задачу написания функции 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-ой строки помещаются в какое-то
иное место, а ее указатель хранится в NAME[I]. Поскольку
размер массива NAME не указан, компилятор сам подсчитывает
количество инициализаторов и соответственно устанавливает
правильное число.
Начинающие изучать язык "с" иногда становятся в тупик
перед вопросом о различии между двумерным массивом и масси-
вом указателей, таким как NAME в приведенном выше примере.
Если имеются описания
INT A[10][10];
INT *B[10];
то A и B можно использовать сходным образом в том смысле,
что как A[5][5], так и B[5][5] являются законными ссылками
на отдельное число типа INT. Но A - настоящий массив: под
него отводится 100 ячеек памяти и для нахождения любого ука-
занного элемента проводятся обычные вычисления с прямоуголь-
ными индексами. Для B, однако, описание выделяет только 10
указателей; каждый указатель должен быть установлен так,
чтобы он указывал на массив целых. если предположить, что
каждый из них указывает на массив из 10 элементов, то тогда
где-то будет отведено 100 ячеек памяти плюс еще десять ячеек
для указателей. Таким образом, массив указателей использует
несколько больший объем памяти и может требовать наличие яв-
ного шага инициализации. Но при этом возникают два преиму-
щества: доступ к элементу осуществляется косвенно через ука-
затель, а не посредством умножения и сложения, и строки мас-
сива могут иметь различные длины. Это означает, что каждый
элемент B не должен обязательно указывать на вектор из 10
элементов; некоторые могут указывать на вектор из двух эле-
ментов, другие - из двадцати, а третьи могут вообще ни на
что не указывать.
Хотя мы вели это обсуждение в терминах целых, несомнен-
но, чаще всего массивы указателей используются так, как мы
продемонстрировали на функции MONTH_NAME, - для хранения
символьных строк различной длины.
Упражнение 5-6
--------------
Перепишите функции DAY_OF_YEAR и MONTH_DAY, используя
вместо индексации указатели.
Системные средства, на которые опирается реализация язы-
ка "с", позволяют передавать командную строку аргументов или
параметров начинающей выполняться программе. Когда функция
MAIN вызывается к исполнению, она вызывается с двумя аргу-
ментами. Первый аргумент (условно называемый ARGC) указывает
число аргументов в командной строке, с которыми происходит
обращение к программе; второй аргумент (ARGV) является ука-
зателем на массив символьных строк, содержащих эти аргумен-
ты, по одному в строке. Работа с такими строками - это обыч-
ное использование многоуровневых указателей.
Самую простую иллюстрацию этой возможности и необходимых
при этом описаний дает программа ECHO, которая просто печа-
тает в одну строку аргументы командной строки, разделяя их
пробелами. Таким образом, если дана команда
ECHO HELLO, WORLD
то выходом будет
HELLO, WORLD
по соглашению ARGV[0] является именем, по которому вызывает-
ся программа, так что ARGC по меньшей мере равен 1. В приве-
денном выше примере ARGC равен 3, а ARGV[0], ARGV[1] и
ARGV[2] равны соответственно "ECHO", "HELLO," и "WORLD".
Первым фактическим агументом является ARGV[1], а последним -
ARGV[ARGC-1]. Если ARGC равен 1, то за именем программы не
следует никакой командной строки аргументов. Все это показа-
но в ECHO:
MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 1ST VERSION */
INT ARGC;
CHAR *ARGV[];
\(
INT I;
FOR (I = 1; I < ARGC; I++)
PRINTF("%S%C", ARGV[I], (I<ARGC-1) ? ' ' : '\N');
\)
Поскольку ARGV является указателем на массив указателей, то
существует несколько способов написания этой программы, ис-
пользующих работу с указателем, а не с индексацией массива.
Мы продемонстрируем два варианта.
MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 2ND VERSION */
INT ARGC;
CHAR *ARGV[];
\(
WHILE (--ARGC > 0)
PRINTF("%S%C",*++ARGV, (ARGC > 1) ? ' ' : '\N');
\)
Так как ARGV является указателем на начало массива строк-ар-
гументов, то, увеличив его на 1 (++ARGV), мы вынуждаем его
указывать на подлинный аргумент ARGV[1], а не на ARGV[0].
Каждое последующее увеличение передвигает его на следующий
аргумент; при этом *ARGV становится указателем на этот аргу-
мент. одновременно величина ARGC уменьшается; когда она об-
ратится в нуль, все аргументы будут уже напечатаны.
Другой вариант:
MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 3RD VERSION */
INT ARGC;
CHAR *ARGV[];
\(
WHILE (--ARGC > 0)
PRINTF((ARGC > 1) ? "%S" : "%S\N", *++ARGV);
\)
Эта версия показывает, что аргумент формата функции PRINTF
может быть выражением, точно так же, как и любой другой. Та-
кое использование встречается не очень часто, но его все же
стоит запомнить.
Как второй пример, давайте внесем некоторые усовершенст-
вования в программу отыскания заданной комбинации символов
из главы 4. Если вы помните, мы поместили искомую комбинацию
глубоко внутрь программы, что очевидно является совершенно
неудовлетворительным. Следуя утилите GREP системы UNIX, да-
вайте изменим программу так, чтобы эта комбинация указыва-
лась в качестве первого аргумента строки.
#DEFINE MAXLINE 1000
MAIN(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);
\)
Теперь может быть развита основная модель, иллюстрирую-
щая дальнейшее использование указателей. Предположим, что
нам надо предусмотреть два необязательных аргумента. Один
утверждает: "напечатать все строки за исключением тех, кото-
рые содержат данную комбинацию", второй гласит: "перед каж-
дой выводимой строкой должен печататься ее номер".
Общепринятым соглашением в "с"-программах является то,
что аргумент, начинающийся со знака минус, вводит необяза-
тельный признак или параметр. Если мы, для того, чтобы сооб-
щить об инверсии, выберем -X, а для указания о нумерации
нужных строк выберем -N("номер"), то команда
FIND -X -N THE
при входных данных
NOW IS THE TIME
FOR ALL GOOD MEN
TO COME TO THE AID
OF THEIR PARTY.
Должна выдать
2:FOR ALL GOOD MEN
Нужно, чтобы необязательные аргументы могли располагать-
ся в произвольном порядке, и чтобы остальная часть программы
не зависела от количества фактически присутствующих аргумен-
тов. в частности, вызов функции INDEX не должен содержать
ссылку на ARGV[2], когда присутствует один необязательный
аргумент, и на ARGV[1], когда его нет. Более того, для поль-
зователей удобно, чтобы необязательные аргументы можно было
объединить в виде:
FIND -NX THE
вот сама программа:
#DEFINE MAXLINE 1000
MAIN(ARGC, ARGV) /* FIND PATTERN FROM FIRST ARGUMENT */
INT ARGC;
CHAR *ARGV[];
\(
CHAR LINE[MAXLINE], *S;
LONG 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 %C\N", *S);
ARGC = 0;
BREAK;
\)
IF (ARGC != 1)
PRINTF("USAGE: FIND -X -N PATTERN\N");
ELSE
WHILE (GETLINе(LINE, MAXLINE) > 0) \(
LINENO++;
IF ((INDEX(LINE, *ARGV) >= 0) != EXCEPT) \
IF (NUMBER)
PRINTF("%LD: ", LINENO);
PRINTF("%S", LINE);
\)
\)
\)
Аргумент ARGV увеличивается перед каждым необязательным
аргументом, в то время как аргумент ARGC уменьшается. если
нет ошибок, то в конце цикла величина ARGC должна равняться
1, а *ARGV должно указывать на заданную комбинацию. Обратите
внимание на то, что *++ARGV является указателем аргументной
строки; (*++ARGV)[0] - ее первый символ. Круглые скобки
здесь необходимы, потому что без них выражение бы приняло
совершенно отличный (и неправильный) вид *++(ARGV[0]). Дру-
гой правильной формой была бы **++ARGV.
Упражнение 5-7
--------------
Напишите программу ADD, вычисляющую обратное польское
выражение из командной строки. Например,
ADD 2 3 4 + *
вычисляет 2*(3+4).
Упражнение 5-8
--------------
Модифицируйте программы ENTAB и DETAB (указанные в ка-
честве упражнений в главе 1) так, чтобы они получали список
табуляционных остановок в качестве аргументов. Если аргумен-
ты отсутствуют, используйте стандартную установку табуляций.
Упражнение 5-9
--------------
Расширьте ENTAB и DETAB таким образом, чтобы они воспри-
нимали сокращенную нотацию
ENTAB M +N
означающую табуляционные остановки через каждые N столбцов,
начиная со столбца M. Выберите удобное (для пользователя)
поведение функции по умолчанию.
Упражнение 5-10
---------------
Напишите программу для функции TAIL, печатающей послед-
ние N строк из своего файла ввода. Пусть по умолчанию N рав-
но 10, но это число может быть изменено с помощью необяза-
тельного аргумента, так что
TAIL -N
печатает последние N строк. программа должна действовать ра-
ционально, какими бы неразумными ни были бы ввод или значе-
ние N. Составьте программу так, чтобы она оптимальным обра-
зом использовала доступную память: строки должны храниться,
как в функции SORT, а не в двумерном массиве фиксированного
размера.
В языке "с" сами функции не являются переменными, но
имеется возможность определить указатель на функцию, который
можно обрабатывать, передавать другим функциям, помещать в
массивы и т.д. Мы проиллюстрируем это, проведя модификацию
написанной ранее программы сортировки так, чтобы при задании
необязательного аргумента -N она бы сортировала строки ввода
численно, а не лексикографически.
Сортировка часто состоит из трех частей - сравнения, ко-
торое определяет упорядочивание любой пары объектов, перес-
тановки, изменяющей их порядок, и алгоритма сортировки, осу-
ществляющего сравнения и перестановки до тех пор, пока
объекты не расположатся в нужном порядке. Алгоритм сортиров-
ки не зависит от операций сравнения и перестановки, так что,
передавая в него различные функции сравнения и перестановки,
мы можем организовать сортировку по различным критериям.
Именно такой подход используется в нашей новой программе
сортировки.
Как и прежде, лексикографическое сравнение двух строк
осуществляется функцией STRCMP, а перестановка функцией
SWAP; нам нужна еще функция NUMCMP, сравнивающая две строки
на основе численного значения и возвращающая условное указа-
ние того же вида, что и STRCMP. Эти три функции описываются
в MAIN и указатели на них передаются в SORT. В свою очередь
функция SORT обращается к этим функциям через их указатели.
мы урезали обработку ошибок в аргументах с тем, чтобы сосре-
доточиться на главных вопросах.
#DEFINE LINES 100 /* MAX NUMBER OF LINES
TO BE SORTED */
MAIN(ARGC, ARGV) /* SORT INPUT LINES */
INT ARGC;
CHAR *ARGV[];
\(
CHAR *LINEPTR[LINES]; /* POINTERS TO TEXT LINES */
INT NLINES; /* NUMBER OF INPUT LINES READ */
INT STRCMP(), NUMCMP(); /* COMPARSION FUNCTIONS */
INT SWAP(); /* EXCHANGE FUNCTION */
INT NUMERIC = 0; /* 1 IF NUMERIC SORT */
IF(ARGC>1 && ARGV[1][0] == '-' && ARGV[1][1]=='N')
NUMERIC = 1;
IF(NLINES = READLINES(LINEPTR, LINES)) >= 0) \(
IF (NUMERIC)
SORT(LINEPTR, NLINES, NUMCMP, SWAP);
ELSE
SORT(LINEPTR, NLINES, STRCMP, SWAP);
WRITELINES(LINEPTR, NLINES);
\) ELSE
PRINTF("INPUT TOO BIG TO SORT\N");
\)
Здесь STRCMP, NIMCMP и SWAP - адреса функций; так как извес-
тно, что это функции, операция & здесь не нужна совершенно
аналогично тому, как она не нужна и перед именем массива.
Передача адресов функций организуется компилятором.
Второй шаг состоит в модификации SORT:
SORT(V, N, COMP, EXCH) /* SORT STRINGS V[0] ... V[N-1] */
CHAR *V[]; /* INTO INCREASING ORDER */
INT N;
INT (*COMP)(), (*EXCH)();
\(
INT GAP, I, J;
FOR(GAP = N/2; GAP > 0; GAP /= 2)
FOR(I = GAP; I < 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)()
говорит, что 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;
\)
Имеется множество других необязятельных аргументов, ко-
торые могут быть включены в программу сортировки: некоторые
из них составляют интересные упражнения.
Упражнение 5-11
---------------
Модифицируйте SORT таким образом, чтобы она работала с
меткой -R, указывающей на сортировку в обратном (убывающем)
порядке. Конечно, -R должна работать с -N.
Упражнение 5-12
---------------
Добавьте необязательный аргумент -F, объединяющий вместе
прописные и строчные буквы, так чтобы различие регистров не
учитывалось во время сортировки: данные из верхнего и нижне-
го регистров сортируются вместе, так что буква 'а' прописное
и 'а' строчное оказываются соседними , а не разделенными це-
лым алфавитом.
Упражнение 5-13
---------------
Добавьте необязательный аргумент -D ("словарное упорядо-
чивание"), при наличии которого сравниваются только буквы,
числа и пробелы. Позаботьтесь о том, чтобы эта функция рабо-
тала и вместе с -F.
Упражнение 5-14
---------------
Добавьте возможность обработки полей, так чтобы можно
было сортировать поля внутри строк. Каждое поле должно сор-
тироваться в соответствии с независимым набором необязатель-
ных аргументов. (предметный указатель этой книги сортировал-
ся с помощью аргументов -DF для категории указателя и с -N
для номеров страниц).
Структура - это набор из одной или более переменных,
возможно различных типов, сгруппированных под одним именем
для удобства обработки. (В некоторых языках, самый известный
из которых паскаль, структуры называются "записями").
Традиционным примером структуры является учетная карточ-
ка работающего: "служащий" описывается набором атрибутов та-
ких, как фамилия, имя, отчество (ф.и.о.), адрес, код соци-
ального обеспечения, зарплата и т.д. Некоторые из этих атри-
бутов сами могут оказаться структурами: ф.и.о. Имеет нес-
колько компонент, как и адрес, и даже зарплата.
указателей. В общем это верно, что на большинстве машин ука-
затель можно присвоить целому и передать его обратно, не из-
менив его; при этом не происходит никакого масштабирования
или преобразования и ни один бит не теряется. к сожалению,
это ведет к вольному обращению с функциями, возвращающими
указатели, которые затем просто передаются другим функциям,
- необходимые описания указателей часто опускаются. Рассмот-
рим, например, функцию 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)
Полагает M равным 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_TAB должен быть внешним как для DAY_OF_YEAR, так
и для MONTH_DAY, поскольку он используется обеими этими фун-
кциями.
Массив DAY_TAB является первым двумерным массивом, с ко-
торым мы имеем дело. По определению в "C" двумерный массив
по существу является одномерным массивом, каждый элемент ко-
торого является массивом. Поэтому индексы записываются как
DAY_TAB[I][J]
а не
DAY_TAB [I, J]
как в большинстве языков. В остальном с двумерными массивами
можно в основном обращаться таким же образом, как в других
языках. Элементы хранятся по строкам, т.е. При обращении к
элементам в порядке их размещения в памяти быстрее всего из-
меняется самый правый индекс.
Массив инициализируется с помощью списка начальных зна-
чений, заключенных в фигурные скобки; каждая строка двумер-
ного массива инициализируется соответствующим подсписком. Мы
поместили в начало массива DAY_TAB столбец из нулей для то-
го, чтобы номера месяцев изменялись естественным образом от
1 до 12, а не от 0 до 11. Так как за экономию памяти у нас
пока не награждают, такой способ проще, чем подгонка индек-
сов.
Если двумерный массив передается функции, то описание
соответствующего аргумента функции должно содержать количес-
тво столбцов; количество строк несущественно, поскольку, как
и прежде, фактически передается указатель. В нашем конкрет-
ном случае это указатель объектов, являющихся массивами из
13 чисел типа INT. Таким образом, если бы требовалось пере-
дать массив DAY_TAB функции 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.
Если две расположенные в неправильном порядке строки должны
быть переставлены, то фактически переставляются указатели в
массиве указателей, а не сами тексты строк. Этим исключаются
сразу две связанные проблемы: сложного управления памятью и
больших дополнительных затрат на фактическую перестановку
строк.
Процесс сортировки включает три шага:
чтение всех строк ввода
их сортировка
вывод их в правильном порядке
Как обычно, лучше разделить программу на несколько функций в
соответствии с естественным делением задачи и выделить веду-
щую функцию, управляющую работой всей программы.
Давайте отложим на некоторое время рассмотрение шага сорти-
ровки и сосредоточимся на структуре данных и вводе-выводе.
Функция, осуществляющая ввод, должна извлечь символы каждой
строки, запомнить их и построить массив указателей строк.
Она должна также подсчитать число строк во вводе, так как
эта информация необходима при сортировке и выводе. так как
функция ввода в состоянии справиться только с конечным чис-
лом вводимых строк, в случае слишком большого их числа она
может возвращать некоторое число, отличное от возможного
числа строк, например -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) является указателем на
символы, то и TEMP должен быть указателем на символы, чтобы
их было можно копировать друг в друга.
Мы написали эту программу по возможности более просто с
тем, чтобы побыстрее получить работающую программу. Она мог-
ла бы работать быстрее, если, например, вводить строки не-
посредственно в массив, управляемый функцией READLINES, а не
копировать их в LINE, а затем в скрытое место с помощью фун-
кции ALLOC. но мы считаем, что будет разумнее первоначальный
вариант сделать более простым для понимания, а об "эффектив-
ности" позаботиться позднее. Все же, по-видимому, способ,
позволяющий добиться заметного ускорения работы программы
состоит не в исключении лишнего копирования вводимых строк.
Более вероятно, что существенной разницы можно достичь за
счет замены сортировки по шеллу на нечто лучшее, например,
на метод быстрой сортировки.
В главе 1 мы отмечали, что поскольку в циклах WHILE и
FOR проверка осуществляется до того, как тело цикла выпол-
нится хотя бы один раз, эти циклы оказываются удобными для
обеспечения правильной работы программы при граничных значе-
ниях, в частности, когда ввода вообще нет. Очень полезно
просмотреть все функции программы сортировки, разбираясь,
что происходит, если вводимый текст отсутствует.
Упражнение 5-5
--------------
Перепишите функцию READLINES таким образом, чтобы она
помещала строки в массив, предоставляемый функцией MAIN, а
не в память, управляемую обращениями к функции ALLOC. На-
сколько быстрее стала программа?
Рассмотрим задачу написания функции 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-ой строки помещаются в какое-то
иное место, а ее указатель хранится в NAME[I]. Поскольку
размер массива NAME не указан, компилятор сам подсчитывает
количество инициализаторов и соответственно устанавливает
правильное число.
Начинающие изучать язык "с" иногда становятся в тупик
перед вопросом о различии между двумерным массивом и масси-
вом указателей, таким как NAME в приведенном выше примере.
Если имеются описания
INT A[10][10];
INT *B[10];
то A и B можно использовать сходным образом в том смысле,
что как A[5][5], так и B[5][5] являются законными ссылками
на отдельное число типа INT. Но A - настоящий массив: под
него отводится 100 ячеек памяти и для нахождения любого ука-
занного элемента проводятся обычные вычисления с прямоуголь-
ными индексами. Для B, однако, описание выделяет только 10
указателей; каждый указатель должен быть установлен так,
чтобы он указывал на массив целых. если предположить, что
каждый из них указывает на массив из 10 элементов, то тогда
где-то будет отведено 100 ячеек памяти плюс еще десять ячеек
для указателей. Таким образом, массив указателей использует
несколько больший объем памяти и может требовать наличие яв-
ного шага инициализации. Но при этом возникают два преиму-
щества: доступ к элементу осуществляется косвенно через ука-
затель, а не посредством умножения и сложения, и строки мас-
сива могут иметь различные длины. Это означает, что каждый
элемент B не должен обязательно указывать на вектор из 10
элементов; некоторые могут указывать на вектор из двух эле-
ментов, другие - из двадцати, а третьи могут вообще ни на
что не указывать.
Хотя мы вели это обсуждение в терминах целых, несомнен-
но, чаще всего массивы указателей используются так, как мы
продемонстрировали на функции MONTH_NAME, - для хранения
символьных строк различной длины.
Упражнение 5-6
--------------
Перепишите функции DAY_OF_YEAR и MONTH_DAY, используя
вместо индексации указатели.
Системные средства, на которые опирается реализация язы-
ка "с", позволяют передавать командную строку аргументов или
параметров начинающей выполняться программе. Когда функция
MAIN вызывается к исполнению, она вызывается с двумя аргу-
ментами. Первый аргумент (условно называемый ARGC) указывает
число аргументов в командной строке, с которыми происходит
обращение к программе; второй аргумент (ARGV) является ука-
зателем на массив символьных строк, содержащих эти аргумен-
ты, по одному в строке. Работа с такими строками - это обыч-
ное использование многоуровневых указателей.
Самую простую иллюстрацию этой возможности и необходимых
при этом описаний дает программа ECHO, которая просто печа-
тает в одну строку аргументы командной строки, разделяя их
пробелами. Таким образом, если дана команда
ECHO HELLO, WORLD
то выходом будет
HELLO, WORLD
по соглашению ARGV[0] является именем, по которому вызывает-
ся программа, так что ARGC по меньшей мере равен 1. В приве-
денном выше примере ARGC равен 3, а ARGV[0], ARGV[1] и
ARGV[2] равны соответственно "ECHO", "HELLO," и "WORLD".
Первым фактическим агументом является ARGV[1], а последним -
ARGV[ARGC-1]. Если ARGC равен 1, то за именем программы не
следует никакой командной строки аргументов. Все это показа-
но в ECHO:
MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 1ST VERSION */
INT ARGC;
CHAR *ARGV[];
\(
INT I;
FOR (I = 1; I < ARGC; I++)
PRINTF("%S%C", ARGV[I], (I<ARGC-1) ? ' ' : '\N');
\)
Поскольку ARGV является указателем на массив указателей, то
существует несколько способов написания этой программы, ис-
пользующих работу с указателем, а не с индексацией массива.
Мы продемонстрируем два варианта.
MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 2ND VERSION */
INT ARGC;
CHAR *ARGV[];
\(
WHILE (--ARGC > 0)
PRINTF("%S%C",*++ARGV, (ARGC > 1) ? ' ' : '\N');
\)
Так как ARGV является указателем на начало массива строк-ар-
гументов, то, увеличив его на 1 (++ARGV), мы вынуждаем его
указывать на подлинный аргумент ARGV[1], а не на ARGV[0].
Каждое последующее увеличение передвигает его на следующий
аргумент; при этом *ARGV становится указателем на этот аргу-
мент. одновременно величина ARGC уменьшается; когда она об-
ратится в нуль, все аргументы будут уже напечатаны.
Другой вариант:
MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 3RD VERSION */
INT ARGC;
CHAR *ARGV[];
\(
WHILE (--ARGC > 0)
PRINTF((ARGC > 1) ? "%S" : "%S\N", *++ARGV);
\)
Эта версия показывает, что аргумент формата функции PRINTF
может быть выражением, точно так же, как и любой другой. Та-
кое использование встречается не очень часто, но его все же
стоит запомнить.
Как второй пример, давайте внесем некоторые усовершенст-
вования в программу отыскания заданной комбинации символов
из главы 4. Если вы помните, мы поместили искомую комбинацию
глубоко внутрь программы, что очевидно является совершенно
неудовлетворительным. Следуя утилите GREP системы UNIX, да-
вайте изменим программу так, чтобы эта комбинация указыва-
лась в качестве первого аргумента строки.
#DEFINE MAXLINE 1000
MAIN(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);
\)
Теперь может быть развита основная модель, иллюстрирую-
щая дальнейшее использование указателей. Предположим, что
нам надо предусмотреть два необязательных аргумента. Один
утверждает: "напечатать все строки за исключением тех, кото-
рые содержат данную комбинацию", второй гласит: "перед каж-
дой выводимой строкой должен печататься ее номер".
Общепринятым соглашением в "с"-программах является то,
что аргумент, начинающийся со знака минус, вводит необяза-
тельный признак или параметр. Если мы, для того, чтобы сооб-
щить об инверсии, выберем -X, а для указания о нумерации
нужных строк выберем -N("номер"), то команда
FIND -X -N THE
при входных данных
NOW IS THE TIME
FOR ALL GOOD MEN
TO COME TO THE AID
OF THEIR PARTY.
Должна выдать
2:FOR ALL GOOD MEN
Нужно, чтобы необязательные аргументы могли располагать-
ся в произвольном порядке, и чтобы остальная часть программы
не зависела от количества фактически присутствующих аргумен-
тов. в частности, вызов функции INDEX не должен содержать
ссылку на ARGV[2], когда присутствует один необязательный
аргумент, и на ARGV[1], когда его нет. Более того, для поль-
зователей удобно, чтобы необязательные аргументы можно было
объединить в виде:
FIND -NX THE
вот сама программа:
#DEFINE MAXLINE 1000
MAIN(ARGC, ARGV) /* FIND PATTERN FROM FIRST ARGUMENT */
INT ARGC;
CHAR *ARGV[];
\(
CHAR LINE[MAXLINE], *S;
LONG 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 %C\N", *S);
ARGC = 0;
BREAK;
\)
IF (ARGC != 1)
PRINTF("USAGE: FIND -X -N PATTERN\N");
ELSE
WHILE (GETLINе(LINE, MAXLINE) > 0) \(
LINENO++;
IF ((INDEX(LINE, *ARGV) >= 0) != EXCEPT) \
IF (NUMBER)
PRINTF("%LD: ", LINENO);
PRINTF("%S", LINE);
\)
\)
\)
Аргумент ARGV увеличивается перед каждым необязательным
аргументом, в то время как аргумент ARGC уменьшается. если
нет ошибок, то в конце цикла величина ARGC должна равняться
1, а *ARGV должно указывать на заданную комбинацию. Обратите
внимание на то, что *++ARGV является указателем аргументной
строки; (*++ARGV)[0] - ее первый символ. Круглые скобки
здесь необходимы, потому что без них выражение бы приняло
совершенно отличный (и неправильный) вид *++(ARGV[0]). Дру-
гой правильной формой была бы **++ARGV.
Упражнение 5-7
--------------
Напишите программу ADD, вычисляющую обратное польское
выражение из командной строки. Например,
ADD 2 3 4 + *
вычисляет 2*(3+4).
Упражнение 5-8
--------------
Модифицируйте программы ENTAB и DETAB (указанные в ка-
честве упражнений в главе 1) так, чтобы они получали список
табуляционных остановок в качестве аргументов. Если аргумен-
ты отсутствуют, используйте стандартную установку табуляций.
Упражнение 5-9
--------------
Расширьте ENTAB и DETAB таким образом, чтобы они воспри-
нимали сокращенную нотацию
ENTAB M +N
означающую табуляционные остановки через каждые N столбцов,
начиная со столбца M. Выберите удобное (для пользователя)
поведение функции по умолчанию.
Упражнение 5-10
---------------
Напишите программу для функции TAIL, печатающей послед-
ние N строк из своего файла ввода. Пусть по умолчанию N рав-
но 10, но это число может быть изменено с помощью необяза-
тельного аргумента, так что
TAIL -N
печатает последние N строк. программа должна действовать ра-
ционально, какими бы неразумными ни были бы ввод или значе-
ние N. Составьте программу так, чтобы она оптимальным обра-
зом использовала доступную память: строки должны храниться,
как в функции SORT, а не в двумерном массиве фиксированного
размера.
В языке "с" сами функции не являются переменными, но
имеется возможность определить указатель на функцию, который
можно обрабатывать, передавать другим функциям, помещать в
массивы и т.д. Мы проиллюстрируем это, проведя модификацию
написанной ранее программы сортировки так, чтобы при задании
необязательного аргумента -N она бы сортировала строки ввода
численно, а не лексикографически.
Сортировка часто состоит из трех частей - сравнения, ко-
торое определяет упорядочивание любой пары объектов, перес-
тановки, изменяющей их порядок, и алгоритма сортировки, осу-
ществляющего сравнения и перестановки до тех пор, пока
объекты не расположатся в нужном порядке. Алгоритм сортиров-
ки не зависит от операций сравнения и перестановки, так что,
передавая в него различные функции сравнения и перестановки,
мы можем организовать сортировку по различным критериям.
Именно такой подход используется в нашей новой программе
сортировки.
Как и прежде, лексикографическое сравнение двух строк
осуществляется функцией STRCMP, а перестановка функцией
SWAP; нам нужна еще функция NUMCMP, сравнивающая две строки
на основе численного значения и возвращающая условное указа-
ние того же вида, что и STRCMP. Эти три функции описываются
в MAIN и указатели на них передаются в SORT. В свою очередь
функция SORT обращается к этим функциям через их указатели.
мы урезали обработку ошибок в аргументах с тем, чтобы сосре-
доточиться на главных вопросах.
#DEFINE LINES 100 /* MAX NUMBER OF LINES
TO BE SORTED */
MAIN(ARGC, ARGV) /* SORT INPUT LINES */
INT ARGC;
CHAR *ARGV[];
\(
CHAR *LINEPTR[LINES]; /* POINTERS TO TEXT LINES */
INT NLINES; /* NUMBER OF INPUT LINES READ */
INT STRCMP(), NUMCMP(); /* COMPARSION FUNCTIONS */
INT SWAP(); /* EXCHANGE FUNCTION */
INT NUMERIC = 0; /* 1 IF NUMERIC SORT */
IF(ARGC>1 && ARGV[1][0] == '-' && ARGV[1][1]=='N')
NUMERIC = 1;
IF(NLINES = READLINES(LINEPTR, LINES)) >= 0) \(
IF (NUMERIC)
SORT(LINEPTR, NLINES, NUMCMP, SWAP);
ELSE
SORT(LINEPTR, NLINES, STRCMP, SWAP);
WRITELINES(LINEPTR, NLINES);
\) ELSE
PRINTF("INPUT TOO BIG TO SORT\N");
\)
Здесь STRCMP, NIMCMP и SWAP - адреса функций; так как извес-
тно, что это функции, операция & здесь не нужна совершенно
аналогично тому, как она не нужна и перед именем массива.
Передача адресов функций организуется компилятором.
Второй шаг состоит в модификации SORT:
SORT(V, N, COMP, EXCH) /* SORT STRINGS V[0] ... V[N-1] */
CHAR *V[]; /* INTO INCREASING ORDER */
INT N;
INT (*COMP)(), (*EXCH)();
\(
INT GAP, I, J;
FOR(GAP = N/2; GAP > 0; GAP /= 2)
FOR(I = GAP; I < 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)()
говорит, что 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;
\)
Имеется множество других необязятельных аргументов, ко-
торые могут быть включены в программу сортировки: некоторые
из них составляют интересные упражнения.
Упражнение 5-11
---------------
Модифицируйте SORT таким образом, чтобы она работала с
меткой -R, указывающей на сортировку в обратном (убывающем)
порядке. Конечно, -R должна работать с -N.
Упражнение 5-12
---------------
Добавьте необязательный аргумент -F, объединяющий вместе
прописные и строчные буквы, так чтобы различие регистров не
учитывалось во время сортировки: данные из верхнего и нижне-
го регистров сортируются вместе, так что буква 'а' прописное
и 'а' строчное оказываются соседними , а не разделенными це-
лым алфавитом.
Упражнение 5-13
---------------
Добавьте необязательный аргумент -D ("словарное упорядо-
чивание"), при наличии которого сравниваются только буквы,
числа и пробелы. Позаботьтесь о том, чтобы эта функция рабо-
тала и вместе с -F.
Упражнение 5-14
---------------
Добавьте возможность обработки полей, так чтобы можно
было сортировать поля внутри строк. Каждое поле должно сор-
тироваться в соответствии с независимым набором необязатель-
ных аргументов. (предметный указатель этой книги сортировал-
ся с помощью аргументов -DF для категории указателя и с -N
для номеров страниц).
Структура - это набор из одной или более переменных,
возможно различных типов, сгруппированных под одним именем
для удобства обработки. (В некоторых языках, самый известный
из которых паскаль, структуры называются "записями").
Традиционным примером структуры является учетная карточ-
ка работающего: "служащий" описывается набором атрибутов та-
ких, как фамилия, имя, отчество (ф.и.о.), адрес, код соци-
ального обеспечения, зарплата и т.д. Некоторые из этих атри-
бутов сами могут оказаться структурами: ф.и.о. Имеет нес-
колько компонент, как и адрес, и даже зарплата.