ЯЗЫК С
5.Указатели и массивы
Указатель - это переменная, содержащая адрес другой пе-
ременной. указатели очень широко используются в языке "C".
Это происходит отчасти потому, что иногда они дают единст-
венную возможность выразить нужное действие, а отчасти пото-
му, что они обычно ведут к более компактным и эффективным
программам, чем те, которые могут быть получены другими спо-
собами.
Указатели обычно смешивают в одну кучу с операторами
GOTO, характеризуя их как чудесный способ написания прог-
рамм, которые невозможно понять. Это безусловно спрAведливо,
если указатели используются беззаботно; очень просто ввести
указатели, которые указывают на что-то совершенно неожидан-
ное. Однако, при определенной дисциплине, использование ука-
зателей помогает достичь ясности и простоты. Именно этот ас-
пект мы попытаемся здесь проиллюстрировать.
5.1. Указатели и адреса
Так как указатель содержит адрес объекта, это дает воз-
можность "косвенного" доступа к этому объекту через указа-
тель. Предположим, что х - переменная, например, типа INT, а
рх - указатель, созданный неким еще не указанным способом.
Унарная операция & выдает адрес объекта, так что оператор
рх = &х;
присваивает адрес х переменной рх; говорят, что рх "ука-
зывает" на х. Операция & применима только к переменным и
элементам массива, конструкции вида &(х-1) и &3 являются не-
законными. Нельзя также получить адрес регистровой перемен-
ной.
Унарная операция * рассматривает свой операнд как адрес
конечной цели и обращается по этому адресу, чтобы извлечь
содержимое. Следовательно, если Y тоже имеет тип INT, то
Y = *рх;
присваивает Y содержимое того, на что указывает рх. Так пос-
ледовательность
рх = &х;
Y = *рх;
присваивает Y то же самое значение, что и оператор
Y = X;
Переменные, участвующие во всем этом необходимо описать:
INT X, Y;
INT *PX;
- 99 -
с описанием для 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
унарные операции * и & связаны со своим операндом более
крепко, чем арифметические операции, так что такое выражение
берет то значение, на которое указывает PX, прибавляет 1 и
присваивает результат переменной Y. Мы вскоре вернемся к то-
му, что может означать выражение
Y = *(PX + 1)
Ссылки на указатели могут появляться и в левой части
присваиваний. Если PX указывает на X, то
*PX = 0
- 100 -
полагает X равным нулю, а
*PX += 1
увеличивает его на единицу, как и выражение
(*PX)++
Круглые скобки в последнем примере необходимы; если их опус-
тить, то поскольку унарные операции, подобные * и ++, выпол-
няются справа налево, это выражение увеличит PX, а не ту пе-
ременную, на которую он указывает.
И наконец, так как указатели являются переменными, то с
ними можно обращаться, как и с остальными переменными. Если
PY - другой указатель на переменную типа INT, то
PY = PX
копирует содержимое PX в PY, в результате чего PY указывает
на то же, что и PX.
5.2. Указатели и аргументы функций
Так как в "с" передача аргументов функциям осуществляет-
ся "по значению", вызванная процедура не имеет непосредст-
венной возможности изменить переменную из вызывающей прог-
раммы. Что же делать, если вам действительно надо изменить
аргумент? например, программа сортировки захотела бы поме-
нять два нарушающих порядок элемента с помощью функции с
именем SWAP. Для этого недостаточно написать
SWAP(A, B);
определив функцию SWAP при этом следующим образом:
SWAP(X, Y) /* WRONG */
INT X, Y;
{
INT TEMP;
TEMP = X;
X = Y;
Y = TEMP;
}
из-за вызова по значению SWAP не может воздействовать на
агументы A и B в вызывающей функции.
К счастью, все же имеется возможность получить желаемый
эффект. Вызывающая программа передает указатели подлежащих
изменению значений:
SWAP(&A, &B);
- 101 -
так как операция & выдает адрес переменной, то &A является
указателем на A. В самой SWAP аргументы описываются как ука-
затели и доступ к фактическим операндам осуществляется через
них.
SWAP(PX, PY) /* INTERCHANGE *PX AND *PY */
INT *PX, *PY;
{
INT TEMP;
TEMP = *PX;
*PX = *PY;
*PY = TEMP;
}
Указатели в качестве аргументов обычно используются в
функциях, которые должны возвращать более одного значения.
(Можно сказать, что SWAP вOзвращает два значения, новые зна-
чения ее аргументов). В качестве примера рассмотрим функцию
GETINT, которая осуществляет преобразование поступающих в
своболном формате данных, разделяя поток символов на целые
значения, по одному целому за одно обращение. Функция GETINT
должна возвращать либо найденное значение, либо признак кон-
ца файла, если входные данные полностью исчерпаны. Эти зна-
чения должны возвращаться как отдельные объекты, какое бы
значение ни использовалось для EOF, даже если это значение
вводимого целого.
Одно из решений, основывающееся на описываемой в главе 7
функции ввода SCANF, состоит в том, чтобы при выходе на ко-
нец файла GETINT возвращала EOF в качестве значения функции;
любое другое возвращенное значение говорит о нахождении нор-
мального целого. Численное же значение найденного целого
возвращается через аргумент, который должен быть указателем
целого. Эта организация разделяет статус конца файла и чис-
ленные значения.
Следующий цикл заполняет массив целыми с помощью обраще-
ний к функции GETINT:
INT N, V, ARRAY[SIZE];
FOR (N = 0; N = '0' && C = ALLOCBUF && P = ALLOCBUF && P = и т.д., работают
надлежащим образом. Например,
P 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 */
CHAR *S, *T;
{
FOR ( ; *S == *T; S++, T++)
IF (*S == '\0')
RETURN(0);
RETURN(*S-*T);
}
так как ++ и -- могут быть как постфиксными, так и
префиксными операциями, встречаются другие комбинации * и
++ и --, хотя и менее часто.
Например
*++P
- 111 -
увеличивает P до извлечения символа, на который указывает
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/.
5.6. Указатели - не целые.
Вы, возможно, обратили внимание в предыдущих "с"-прог-
раммах на довольно непринужденное отношение к копированию
указателей. В общем это верно, что на большинстве машин ука-
затель можно присвоить целому и передать его обратно, не из-
менив его; при этом не происходит никакого масштабирования
или преобразования и ни один бит не теряется. к сожалению,
это ведет к вольному обращению с функциями, возвращающими
указатели, которые затем просто передаются другим функциям,
- необходимые описания указателей часто опускаются. Рассмот-
рим, например, функцию 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);
}
на практике существует сильное стремление опускать описания:
- 112 -
*STRSAVE(S) /* SAVE STRING S SOMEWHERE */
{
CHAR *P;
IF ((P = ALLOC(STRLEN(S)+1)) != NULL)
STRCPY(P, S);
RETURN(P);
}
Эта программа будет правильно работать на многих маши-
нах, потому что по умолчанию функции и аргументы имеют тип
INT, а указатель и целое обычно можно безопасно пересылать
туда и обратно. Однако такой стиль программирования в своем
существе является рискованным, поскольку зависит от деталей
реализации и архитектуры машины и может привести к непра-
вильным результатам на конкретном используемом вами компиля-
торе. Разумнее всюду использовать полные описания. (Отладоч-
ная программа LINT предупредит о таких конструкциях, если
они по неосторожности все же появятся).
5.7. Многомерные массивы.
В языке "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)
};
- 113 -
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 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. Так как за экономию памяти у нас
пока не награждают, такой способ проще, чем подгонка индек-
сов.
Если двумерный массив передается функции, то описание
соответствующего аргумента функции должно содержать количес-
тво столбцов; количество строк несущественно, поскольку, как
и прежде, фактически передается указатель. В нашем конкрет-
ном случае это указатель объектов, являющихся массивами из
- 114 -
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 указателей на целые.
5.8. Массивы указателей; указатели указателей
Так как указатели сами являются переменными, то вы впол-
не могли бы ожидать использования массива указателей. Это
действительно так. Мы проиллюстрируем это написанием прог-
раммы сортировки в алфавитном порядке набора текстовых
строк, предельно упрощенного варианта утилиты SORT операци-
онной систем UNIX.
В главе 3 мы привели функцию сортировки по шеллу, кото-
рая упорядочивала массив целых. Этот же алгоритм будет рабо-
тать и здесь, хотя теперь мы будем иметь дело со строчками
текста различной длины, которые, в отличие от целых, нельзя
сравнивать или перемещать с помощью одной операции. Мы нуж-
даемся в таком представлении данных, которое бы позволяло
удобно и эффективно обрабатывать строки текста переменной
длины.
Здесь и возникают массивы указателей. Если подлежащие
сортировке сроки хранятся одна за другой в длинном символь-
ном массиве (управляемом, например, функцией ALLOC), то к
каждой строке можно обратиться с помощью указателя на ее
первый символ. Сами указатели можно хранить в массиве. две
строки можно сравнить, передав их указатели функции STRCMP.
- 115 -
Если две расположенные в неправильном порядке строки должны
быть переставлены, то фактически переставляются указатели в
массиве указателей, а не сами тексты строк. Этим исключаются
сразу две связанные проблемы: сложного управления памятью и
больших дополнительных затрат на фактическую перестановку
строк.
Процесс сортировки включает три шага:
чтение всех строк ввода
их сортировка
вывод их в правильном порядке
Как обычно, лучше разделить программу на несколько функций в
соответствии с естественным делением задачи и выделить веду-
щую функцию, управляющую работой всей программы.
Давайте отложим на некоторое время рассмотрение шага сорти-
ровки и сосредоточимся на структуре данных и вводе-выводе.
Функция, осуществляющая ввод, должна извлечь символы каждой
строки, запомнить их и построить массив указателей строк.
Она должна также подсчитать число строк во вводе, так как
эта информация необходима при сортировке и выводе. так как
функция ввода в состоянии справиться только с конечным чис-
лом вводимых строк, в случае слишком большого их числа она
может возвращать некоторое число, отличное от возможного
числа строк, например -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
- 116 -
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 = 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 = 0; J -= GAP) \(
IF (STRCMP(V[J], V[J+GAP]) 12) ? NAME[0] : NAME[N]);
\)
- 119 -
Описание массива указателей на символы NAME точно такое же,
как аналогичное описание LINEPTR в примере с сортировкой.
Инициализатором является просто список символьных строк;
каждая строка присваивается соответствующей позиции в масси-
ве. Более точно, символы I-ой строки помещаются в какое-то
иное место, а ее указатель хранится в NAME[I]. Поскольку
размер массива NAME не указан, компилятор сам подсчитывает
количество инициализаторов и соответственно устанавливает
правильное число.
5.10. Указатели и многомерные массивы
Начинающие изучать язык "с" иногда становятся в тупик
перед вопросом о различии между двумерным массивом и масси-
вом указателей, таким как 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, используя
вместо индексации указатели.
- 120 -
5.11. Командная строка аргументов
Системные средства, на которые опирается реализация язы-
ка "с", позволяют передавать командную строку аргументов или
параметров начинающей выполняться программе. Когда функция
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 0)
PRINTF("%S%C",*++ARGV, (ARGC > 1) ? ' ' : '\N');
\)
- 121 -
Так как 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);
\)
Теперь может быть развита основная модель, иллюстрирую-
щая дальнейшее использование указателей. Предположим, что
нам надо предусмотреть два необязательных аргумента. Один
утверждает: "напечатать все строки за исключением тех, кото-
рые содержат данную комбинацию", второй гласит: "перед каж-
дой выводимой строкой должен печататься ее номер".
- 122 -
Общепринятым соглашением в "с"-программах является то,
что аргумент, начинающийся со знака минус, вводит необяза-
тельный признак или параметр. Если мы, для того, чтобы сооб-
щить об инверсии, выберем -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;
- 123 -
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
- 124 -
означающую табуляционные остановки через каждые N столбцов,
начиная со столбца M. Выберите удобное (для пользователя)
поведение функции по умолчанию.
Упражнение 5-10.
---------------
Напишите программу для функции TAIL, печатающей послед-
ние N строк из своего файла ввода. Пусть по умолчанию N рав-
но 10, но это число может быть изменено с помощью необяза-
тельного аргумента, так что
TAIL -N
печатает последние N строк. программа должна действовать ра-
ционально, какими бы неразумными ни были бы ввод или значе-
ние N. Составьте программу так, чтобы она оптимальным обра-
зом использовала доступную память: строки должны храниться,
как в функции SORT, а не в двумерном массиве фиксированного
размера.
5.12. Указатели на функции
В языке "с" сами функции не являются переменными, но
имеется возможность определить указатель на функцию, который
можно обрабатывать, передавать другим функциям, помещать в
массивы и т.д. Мы проиллюстрируем это, проведя модификацию
написанной ранее программы сортировки так, чтобы при задании
необязательного аргумента -N она бы сортировала строки ввода
численно, а не лексикографически.
Сортировка часто состоит из трех частей - сравнения, ко-
торое определяет упорядочивание любой пары объектов, перес-
тановки, изменяющей их порядок, и алгоритма сортировки, осу-
ществляющего сравнения и перестановки до тех пор, пока
объекты не расположатся в нужном порядке. Алгоритм сортиров-
ки не зависит от операций сравнения и перестановки, так что,
передавая в него различные функции сравнения и перестановки,
мы можем организовать сортировку по различным критериям.
Именно такой подход используется в нашей новой программе
сортировки.
Как и прежде, лексикографическое сравнение двух строк
осуществляется функцией STRCMP, а перестановка функцией
SWAP; нам нужна еще функция NUMCMP, сравнивающая две строки
на основе численного значения и возвращающая условное указа-
ние того же вида, что и STRCMP. Эти три функции описываются
в MAIN и указатели на них передаются в SORT. В свою очередь
функция SORT обращается к этим функциям через их указатели.
мы урезали обработку ошибок в аргументах с тем, чтобы сосре-
доточиться на главных вопросах.
- 125 -
#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 = 0; J -= GAP) \(
IF((*COMP)(V[J], V[J+GAP]) V2)
RETURN(1);
ELSE
RETURN (0);
\)
Заключительный шаг состоит в добавлении функции SWAP,
переставляющей два указателя. Это легко сделать, непосредст-
венно используя то, что мы изложили ранее в этой главе.
- 127 -
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
для номеров страниц).
[ Назад ]
[ Далее ]