Язык С (Керниган, Ричи). Язык сиБ. В. Керниган, Д. М. Ричи
 Скачать 1.46 Mb.
|
|
Упражнение 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. Указатели - не целые. Вы, возможно, обратили внимание в предыдущих “с”-программах на довольно непринужденное отношение к копированию указателей. В общем это верно, что на большинстве машин указатель можно присвоить целому и передать его обратно, не изменив его; при этом не происходит никакого масштабирования или преобразования и ни один бит не теряется. к сожалению, это ведет к вольному обращению с функциями, возвращающими 110 «Язык С» Б.В. Керниган, Д.М. Ричи указатели, которые затем просто передаются другим функциям, - необходимые описания указателей часто опускаются. Рассмотрим, например, функцию 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); на практике существует сильное стремление опускать описания: *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 преобразует день года в месяц и день. Так как эта последняя функция возвращает два значения, то аргументы месяца и дня должны быть указателями: «Язык С» Б.В. Керниган, Д.М. Ричи 111 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] как в большинстве языков. В остальном с двумерными массивами можно в основном обращаться таким же образом, как в других языках. Элементы хранятся по строкам, т.е. При обращении к элементам в порядке их размеще- 112 «Язык С» Б.В. Керниган, Д.М. Ричи ния в памяти быстрее всего изменяется самый правый индекс. Массив инициализируется с помощью списка начальных значений, заключенных в фигурные скобки; каждая строка двумерного массива инициа- лизируется соответствующим подсписком. Мы поместили в начало массива 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 мы привели функцию сортировки по шеллу, которая упорядочивала массив целых. Этот же алгоритм будет работать и здесь, хотя теперь мы будем иметь дело со строчками текста различной длины, которые, в «Язык С» Б.В. Керниган, Д.М. Ричи 113 отличие от целых, нельзя сравнивать или перемещать с помощью одной операции. Мы нуждаемся в таком представлении данных, которое бы позволяло удобно и эффективно обрабатывать строки текста переменной длины. Здесь и возникают массивы указателей. Если подлежащие сортировке сроки хранятся одна за другой в длинном символьном массиве (управляемом, например, функцией 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”); \) 114 «Язык С» Б.В. Керниган, Д.М. Ричи #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[]; «Язык С» Б.В. Керниган, Д.М. Ричи 115 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. но мы считаем, что будет разумнее первоначальный вариант сделать более простым для понимания, а об “эффективности” позаботиться позднее. Все же, по-видимому, способ, 116 «Язык С» Б.В. Керниган, Д.М. Ричи позволяющий добиться заметного ускорения работы программы состоит не в исключении лишнего копирования вводимых строк. Более вероятно, что существенной разницы можно достичь за счет замены сортировки по шеллу на нечто лучшее, например, на метод быстрой сортировки. В главе 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]); \) «Язык С» Б.В. Керниган, Д.М. Ричи 117 Описание массива указателей на символы 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 элементов; некоторые могут указывать на вектор из двух эле- ментов, другие - из двадцати, а третьи могут вообще ни на что не указывать. Хотя мы вели это обсуждение в терминах целых, несомненно, чаще всего массивы указателей используются так, как мы продемонстрировали на функции MONTH_NAME, - для хранения символьных строк различной длины. Упражнение 5-6. Перепишите функции DAY_OF_YEAR и MONTH_DAY, используя вместо индексации указатели. 5.11. Командная строка аргументов Системные средства, на которые опирается реализация языка “с”, позволяют передавать командную строку аргументов или параметров начинающей выполняться программе. Когда функция MAIN вызывается к исполнению, она 118 «Язык С» Б.В. Керниган, Д.М. Ричи вызывается с двумя аргументами. Первый аргумент (условно называемый ARGC) указывает число аргументов в командной строке, с которыми происходит обращение к программе; второй аргумент (ARGV) является ука- зателем на массив символьных строк, содержащих эти аргументы, по одному в строке. Работа с такими строками - это обычное использование многоуров- невых указателей. Самую простую иллюстрацию этой возможности и необходимых при этом описаний дает программа ECHO, которая просто печатает в одну строку аргументы командной строки, разделяя их пробелами. Таким образом, если дана команда ECHO HELLO, WORLD то выходом будет HELLO, WORLD по соглашению ARGV[0] является именем, по которому вызывается программа, так что ARGC по меньшей мере равен 1. В приведенном выше примере ARGC равен 3, а ARGV[0], ARGV[1] и ARGV[2] равны соответ- ственно “ECHO”, “HELLO,” и “WORLD”. Первым фактическим агументом является ARGV[1], а последним - ARGV[ARGC-1]. Если ARGC равен 1, то за именем программы не следует никакой командной строки аргументов. Все это показано в ECHO: MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 1ST VERSION */ INT ARGC; CHAR *ARGV[]; \( INT I; FOR (I = 1; I < ARGC; I++) PRINTF(“%S%C”, ARGV[I], (I Поскольку ARGV является указателем на массив указателей, то существует несколько способов написания этой программы, использующих работу с указателем, а не с индексацией массива. Мы продемонстрируем два варианта. MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 2ND VERSION */ INT ARGC; CHAR *ARGV[]; \( WHILE (—ARGC > 0) PRINTF(“%S%C”,*++ARGV, (ARGC > 1) ? ‘ ‘ : ‘\N’); \) Так как ARGV является указателем на начало массива строк-аргументов, «Язык С» Б.В. Керниган, Д.М. Ричи 119 то, увеличив его на 1 (++ARGV), мы вынуждаем его указывать на подлинный аргумент ARGV[1], а не на ARGV[0]. Каждое последующее увеличение пере- двигает его на следующий аргумент; при этом *ARGV становится указателем на этот аргумент. одновременно величина ARGC уменьшается; когда она об- ратится в нуль, все аргументы будут уже напечатаны. Другой вариант: MAIN(ARGC, ARGV) /* ECHO ARGUMENTS; 3RD VERSION */ INT ARGC; CHAR *ARGV[]; \( WHILE (—ARGC > 0) PRINTF((ARGC > 1) ? “%S” : “%S\N”, *++ARGV); \) Эта версия показывает, что аргумент формата функции PRINTF может быть выражением, точно так же, как и любой другой. Такое использование встречается не очень часто, но его все же стоит запомнить. Как второй пример, давайте внесем некоторые усовершенствования в программу отыскания заданной комбинации символов из главы 4. Если вы помните, мы поместили искомую комбинацию глубоко внутрь программы, что очевидно является совершенно неудовлетворительным. Следуя утилите GREP системы UNIX, давайте изменим программу так, чтобы эта комбинация указывалась в качестве первого аргумента строки. #DEFINE MAXLINE 1000 MAIN(ARGC, ARGV) /* FIND PATTERN FROM FIRST ARGUMENT */ INT ARGC; CHAR *ARGV[]; \( CHAR LINE[MAXLINE]; IF (ARGC != 2) PRINTF (“USAGE: FIND PATTERN\N”); ELSE WHILE (GETLINE(LINE, MAXLINE) > 0) IF (INDEX(LINE, ARGV[1] >= 0) PRINTF(“%S”, LINE); \) Теперь может быть развита основная модель, иллюстрирующая дальнейшее использование указателей. Предположим, что нам надо предусмотреть два необязательных аргумента. Один утверждает: “напечатать все строки за исключением тех, которые содержат данную комбинацию”, второй гласит: “перед каждой выводимой строкой должен печататься ее номер”. Общепринятым соглашением в “с”-программах является то, что аргумент, 120 «Язык С» Б.В. Керниган, Д.М. Ричи начинающийся со знака минус, вводит необязательный признак или параметр. Если мы, для того, чтобы сообщить об инверсии, выберем -X, а для указания о нумерации нужных строк выберем -N(“номер”), то команда FIND -X -N THE при входных данных NOW IS THE TIME FOR ALL GOOD MEN TO COME TO THE AID OF THEIR PARTY. Должна выдать 2:FOR ALL GOOD MEN Нужно, чтобы необязательные аргументы могли располагаться в произвольном порядке, и чтобы остальная часть программы не зависела от количества фактически присутствующих аргументов. в частности, вызов функции INDEX не должен содержать ссылку на ARGV[2], когда присутствует один необязательный аргумент, и на ARGV[1], когда его нет. Более того, для пользователей удобно, чтобы необязательные аргументы можно было объединить в виде: FIND -NX THE вот сама программа: #DEFINE MAXLINE 1000 MAIN(ARGC, ARGV) /* FIND PATTERN FROM FIRST ARGUMENT */ INT ARGC; CHAR *ARGV[]; \( CHAR LINE[MAXLINE], *S; LONG LINENO = 0; INT EXCEPT = 0, NUMBER = 0; WHILE (—ARGC > 0 && (*++ARGV)[0] == ‘-’) FOR (S = ARGV[0]+1; *S != ‘\0’; S++) SWITCH (*S) \( CASE ‘X’: EXCEPT = 1; BREAK; CASE ‘N’: NUMBER = 1; BREAK; DEFAULT: «Язык С» Б.В. Керниган, Д.М. Ричи 121 PRINTF(“FIND: ILLEGAL OPTION %C\N”, *S); ARGC = 0; BREAK; \) IF (ARGC != 1) PRINTF(“USAGE: FIND -X -N PATTERN\N”); ELSE WHILE (GETLINе(LINE, MAXLINE) > 0) \( LINENO++; IF ((INDEX(LINE, *ARGV) >= 0) != EXCEPT) \ IF (NUMBER) PRINTF(“%LD: “, LINENO); PRINTF(“%S”, LINE); \) \) \) Аргумент ARGV увеличивается перед каждым необязательным аргумен- том, в то время как аргумент ARGC уменьшается. если нет ошибок, то в конце цикла величина ARGC должна равняться 1, а *ARGV должно указывать на заданную комбинацию. Обратите внимание на то, что *++ARGV является указателем аргументной строки; (*++ARGV)[0] - ее первый символ. Круглые скобки здесь необходимы, потому что без них выражение бы приняло совер- шенно отличный (и неправильный) вид *++(ARGV[0]). Другой правильной формой была бы **++ARGV. |