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 предупредит о таких
конструкциях, если они по неосторожности все же появятся).
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) };
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 указателей на целые.
5.8. Массивы указателей; указатели указателей
Так как указатели сами являются переменными, то вы впол- не могли бы ожидать
использования массива указателей. Это действительно так. Мы проиллюстрируем это
написанием прог- раммы сортировки в алфавитном порядке набора текстовых строк, предельно
упрощенного варианта утилиты 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. На- сколько быстрее стала программа?
5.9. Инициализация массивов указателей
Рассмотрим задачу написания функции 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 не указан, компилятор сам подсчитывает количество
инициализаторов и соответственно устанавливает правильное число.
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 элементов; некоторые могут указывать на вектор из двух эле- ментов,
другие - из двадцати, а третьи могут вообще ни на что не указывать.
