До 12, а не от 0 до 11. Так как за экономию памяти у нас пока не награждают, такой способ проще, чем подгонка индек-сов

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. На-

сколько быстрее стала программа?

Похожие работы

Анализ обыденного языка: общая характеристика направления

Скачать

48443

0

0

... основаниям. При этом философская абстракция языка оказывается неразрывно связана с основными темами и движениями философии в целом. Более конкретно, на ранние стадии традиционно рассматриваемого в рамках АФ анализа обыденного языка глубокое влияние оказала философия Дж. Э. Мура, особенно его учение о здравом смысле, согласно которому такие понятия, как «человек», «мир», «я», «внешний мир», « ...

Русский язык в современной Молдове

Скачать

43709

0

0

... и других странах СНГ, а также облегчение доступа к русской и мировой культуре и науке. Таким образом, судя по данным наших исследований, востребованность русского языка осталась в республике достаточно высокой. Многие представители современной молдавской молодежи продолжают, как их отцы и деды, тянуться к русской культуре, научным и техническим достижениям России. Русский язык остается языком ...

Неиндоевропейские языки

Скачать

39778

0

1

... рисуночное словесно-слоговое письмо). Памятники среднеэламского периода (14—12 вв. до н.э.) выполнены аккадской клинописью. Памятники новоэламского периода относятся к 8—6 вв. до н.э. Был официальным языком в персидском государстве Ахеменидов в 6—4 вв. предполагается, что он, подвергшись влиянию древнеперсидского, сохранился до раннего средневековья. 7. Бурушаски язык Язык бурушаски ( ...

Индоевропейские языки

Скачать

64931

0

0

... /диалект), скифский, согдийский, среднеперсидский, таджикский, таджриши (язык/диалект), талышский, татский, хорезмийский, хотаносакский, шугнано-рушанская группа языков, ягнобский, язгулямский и др. Они относятся к индоиранской ветви индоевропейских языков. Области распространения: Иран, Афганистан, Таджикистан, некоторые районы Ирака, Турции, Пакистана, Индии, Грузии, Российской Федерации. Общее ...