по существу является одномерным массивом, каждый элемент ко-
торого является массивом. Поэтому индексы записываются как
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 < NLINES; I++)
PRINTF(“%S\N”, LINEPTR[I]);
\)
Существенно новым в этой программе является описание
CHAR *LINEPTR[LINES];
которое сообщает, что LINEPTR является массивом из LINES
элементов, каждый из которых - указатель на переменные типа
CHAR. Это означает, что LINEPTR[I] - указатель на символы, а
*LINEPTR[I] извлекает символ.
Так как сам LINEPTR является массивом, который передает-
ся функции WRITELINES, с ним можно обращаться как с указате-
лем точно таким же образом, как в наших более ранних приме-
· 117 -
рах. Тогда последнюю функцию можно переписать в виде:
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, а затем в скрытое место с помощью фун-
· 118 -
кции 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]);
\)
· 119 -
Описание массива указателей на символы NAME точно такое же,
как аналогичное описание LINEPTR в примере с сортировкой.
Инициализатором является просто список символьных строк;
каждая строка присваивается соответствующей позиции в масси-
ве. Более точно, символы I-ой строки помещаются в какое-то
иное место, а ее указатель хранится в NAME[I]. Поскольку
размер массива NAME не указан, компилятор сам подсчитывает
количество инициализаторов и соответственно устанавливает
правильное число.
5.10. Указатели и многомерные массивы
Начинающие изучать язык “с” иногда становятся в тупик
перед вопросом о различии между двумерным массивом и масси-
вом указателей, таким как NAME в приведенном выше примере.
Если имеются описания
INT A[10][10];
INT *B[10];
то A и B можно использовать сходным образом в том смысле,