Массив инициализируется с помощью списка начальных значений, заключенных в фигурные скобки; каждая строка двумерного массива инициализируется соответствующим подсписком. Мы поместили в начало массива 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
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, с ним можно обращаться как с указателем точно таким же образом, как в наших более ранних приме
рах. Тогда последнюю функцию можно переписать в виде: 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 элементов; некоторые могут указывать на вектор из двух элементов, другие - из двадцати, а третьи могут вообще ни на что не указывать.