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