Язык С

и т, возвращая отрицательное, нулевое или положительное значение в соответствии с тем, меньше, равно или больше лексикографически S, чем T. Возвращаемое значение получается в результате вычитания символов из первой позиции, в которой S и T не совпадают.

STRCMP(S, T) /* RETURN <0 IF S<T, 0 IF S==T, >0 IF S>T */ CHAR S[], T[];

{ INT I;

I = 0;

WHILE (S[I] == T[I]) IF (S[I++] == '') RETURN(0);

RETURN(S[I]-T[I]);

}

Вот версия STRCMP с указателями: STRCMP(S, T) /* RETURN <0 IF S<T, 0 IF S==T, >0 IF S>T */ CHAR *S, *T;

{ FOR ( ; *S == *T; S++, T++) IF (*S == '') RETURN(0);

RETURN(*S-*T);

} так как ++ и—могут быть как постфиксными, так и префиксными операциями, встречаются другие комбинации * и ++ и --, хотя и менее часто.

Например *++P

111

увеличивает P до извлечения символа, на который указывает P, а *--P сначала уменьшает P.

Упражнение 5-2.

Напишите вариант с указателями функции STRCAT из главы 2: STRCAT(S, T) копирует строку T в конец S.

Упражнение 5-3.

Напишите макрос для STRCPY.

Упражнение 5-4.

Перепишите подходящие программы из предыдущих глав и упражнений, используя указатели вместо индексации массивов.

Хорошие возможности для этого предоставляют функции GETLINE /главы 1 и 4/, ATOI, ITOA и их варианты /главы 2, 3 и 4/, REVERSE /глава 3/, INDEX и GETOP /глава 4/.

5.6. Указатели - не целые.

Вы, возможно, обратили внимание в предыдущих “с”-программах на довольно непринужденное отношение к копированию указателей. В общем это верно, что на большинстве машин указатель можно присвоить целому и передать его обратно, не изменив его; при этом не происходит никакого масштабирования или преобразования и ни один бит не теряется. к сожалению, это ведет к вольному обращению с функциями, возвращающими указатели, которые затем просто передаются другим функциям, необходимые описания указателей часто опускаются. Рассмотрим, например, функцию STRSAVE(S), которая копирует строку S в некоторое место для хранения, выделяемое посредством обращения к функции ALLOC, и возвращает указатель на это место.

Правильно она должна быть записана так: CHAR STRSAVE(S) / SAVE STRING S SOMEWHERE */ CHAR *S;

{ CHAR *P, *ALLOC();

IF ((P = ALLOC(STRLEN(S)+1)) != NULL) STRCPY(P, S);

RETURN(P);

}

на практике существует сильное стремление опускать описания:

112

STRSAVE(S) / SAVE STRING S SOMEWHERE */

{ CHAR *P;

IF ((P = ALLOC(STRLEN(S)+1)) != NULL) STRCPY(P, S);

RETURN(P);

}

Эта программа будет правильно работать на многих машинах, потому что по умолчанию функции и аргументы имеют тип INT, а указатель и целое обычно можно безопасно пересылать туда и обратно. Однако такой стиль программирования в своем существе является рискованным, поскольку зависит от деталей реализации и архитектуры машины и может привести к неправильным результатам на конкретном используемом вами компиляторе. Разумнее всюду использовать полные описания. (Отладочная программа LINT предупредит о таких конструкциях, если они по неосторожности все же появятся).

5.7. Многомерные массивы.

В языке “C” предусмотрены прямоугольные многомерные массивы, хотя на практике существует тенденция к их значительно более редкому использованию по сравнению с массивами указателей. В этом разделе мы рассмотрим некоторые их свойства.

Рассмотрим задачу преобразования дня месяца в день года и наоборот. Например, 1-ое марта является 60-м днем невисокосного года и 61-м днем високосного года. Давайте введем две функции для выполнения этих преобразований: DAY_OF_YEAR преобразует месяц и день в день года, а MONTH_DAY преобразует день года в месяц и день. Так как эта последняя функция возвращает два значения, то аргументы месяца и дня должны быть указателями:

MONTH_DAY(1977, 60, &M, &D) Полагает M равным 3 и D равным 1 (1-ое марта).

Обе эти функции нуждаются в одной и той же информационной таблице, указывающей число дней в каждом месяце. Так как число дней в месяце в високосном и в невисокосном году отличается, то проще представить их в виде двух строк двумерного массива, чем пытаться прослеживать во время вычислений, что именно происходит в феврале. Вот этот массив и выполняющие эти преобразования функции:

STATIC INT DAY_TAB[2][13] = { (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31), (0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

};

DAY_OF_YEAR(YEAR, MONTH, DAY) /* SET DAY OF YEAR */

INT YEAR, MONTH, DAY; /* FROM MONTH & DAY */

{ INT I, LEAP;

LEAP = YEAR%4 == 0 && YEAR%100 != 0 !! YEAR%400 == 0;

FOR (I = 1; I < MONTH; I++) DAY += DAY_TAB[LEAP][I];

RETURN(DAY);

{

MONTH_DAY(YEAR, YEARDAY, PMONTH, PDAY) /*SET MONTH,DAY */ INT YEAR, YEARDAY, *PMONTH, PDAY; / FROM DAY OF YEAR */ { LEAP = YEAR%4 == 0 && YEAR%100 != 0 !! YEAR%400 == 0;

FOR (I = 1; YEARDAY > DAY_TAB[LEAP][I]; I++) YEARDAY -= DAY_TAB[LEAP][I];

*PMONTH = I;

*PDAY = YEARDAY;

}

Массив DAY_TAB должен быть внешним как для DAY_OF_YEAR, так и для MONTH_DAY, поскольку он используется обеими этими функциями.

Массив DAY_TAB является первым двумерным массивом, с которым мы имеем дело. По определению в “C” двумерный массив по существу является одномерным массивом, каждый элемент которого является массивом. Поэтому индексы записываются как

DAY_TAB[I][J] а не DAY_TAB [I, J]

как в большинстве языков. В остальном с двумерными массивами можно в основном обращаться таким же образом, как в других языках. Элементы хранятся по строкам, т.е. При обращении к элементам в порядке их размещения в памяти быстрее всего изменяется самый правый индекс.

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

)

#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] = ''; /* 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(“%SN”, 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(“%SN”, *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] :

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: