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