Язык программирования Си Брайан Керниган, Деннис Ритчи 3е издание Версия 1 Table of Contents
 Скачать 2.33 Mb.
|
|
Упражнение 5.7. Напишите новую версию readlines , которая запоминала бы строки в массиве, определенном в main , а не запрашивала память посредством программы alloc . Насколько быстрее эта программа? 5.7. Многомерные массивы В Си имеется возможность задавать прямоугольные многомерные массивы, правда, на практике по сравнению с массивами указателей они используются значительно реже. В этом параграфе мы продемонстрируем некоторые их свойства. Рассмотрим задачу перевода даты "день-месяц" в "день года" и обратно. Например, 1 марта — это 60-й день невисокосного или 61-й день високосного года. Определим две функции для этих преобразований: функция day_of_year будет преобразовывать месяц и день в день года, a month_day — день года в месяц и день. Поскольку последняя функция вычисляет два значения, аргументы месяц и день будут указателями. Так вызов month_day( 1988, 60, &m, &d) присваивает переменной m значение 2, a d — 29 (29 февраля). Нашим функциям нужна одна и та же информация, а именно таблица, содержащая числа дней каждого месяца. Так как для високосного и невисокосного годов эти таблицы будут различаться, проще иметь две отдельные строки в двумерном массиве, чем во время вычислений отслеживать особый случай с февралем. Массив и функции, выполняющие преобразования, имеют следующий вид: static char daytab[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: определяет день года по месяцу и дню */ int day_of_year(int year, int month, int day) { int i, leap; leap = year%4 == 0 && year%100 != 0 i I year%400 == 0; for (i = 1; i < month; i++) day += daytab[leap][i]; return day; } /* month_day: определяет месяц и день по дню года */ void month_day(int year, int yearday, int *pmonth, int *pday) { int i, leap; leap = year%4 == 0 && year%100 != 0 || year%400 == 0; for (i = 1; yearday > daytab[leap][i]; i++) yearday -= daytab[leap][i]; *pmonth = i; *pday = yearday; } Напоминаем, что арифметическое значение логического выражения (например, выражения, с помощью которого вычислялось leap ) равно либо нулю (ложь), либо единице (истина), так что мы можем использовать его как индекс в массиве daytab Массив daytab должен быть внешним по отношению к обеим функциям day_of _year и month_day , так как он нужен и той и другой. Мы сделали его типа char , чтобы проиллюстрировать законность применения типа char для малых целых без знака. Массив daytab — это первый массив из числа двумерных, с которыми мы еще не имели дела. Строго говоря, в Си двумерный массив рассматривается как одномерный массив, каждый элемент которого — также массив. Поэтому индексирование изображается так: daytab[i][j] /* [строка] [столбец] */ а не так: daytab[i,j] /* НЕВЕРНО */ Особенность двумерного массива в Си заключается лишь в форме записи, в остальном его можно трактовать почти так же, как в других языках. Элементы запоминаются строками, следовательно, при переборе их в том порядке, как они расположены в памяти, чаще будет изменяться самый правый индекс. Массив инициализируется списком начальных значений, заключенным в фигурные скобки; каждая строка двумерного массива инициализируется соответствующим подсписком. Нулевой столбец добавлен в начало daytab лишь для того, чтобы индексы, которыми мы будем пользоваться, совпадали с естественными номерами месяцев от 1 до 12. Экономить пару ячеек памяти здесь нет никакого смысла, а программа, в которой уже не надо корректировать индекс, выглядит более ясной. Если двумерный массив передается функции в качестве аргумента, то объявление соответствующего ему параметра должно содержать количество столбцов; количество строк в данном случае несущественно, поскольку, как и прежде, функции будет передан указатель на массив строк, каждая из которых есть массив из 13 значений типа int , В нашем частном случае мы имеем указатель на объекты, являющиеся массивами из 13 значений типа int . Таким образом, если массив daytab передается некоторой функции f , то эту функцию можно было бы определить следующим образом: f(int daytab[2][13]) {…} Вместо этого можно записать f(int daytab[][13]) {…} поскольку число строк здесь не имеет значения, или f(int (*daytab)[13]) {…} Последняя запись объявляет, что параметр есть указатель на массив из 13 значений типа int . Скобки здесь необходимы, так как квадратные скобки [] имеют более высокий приоритет, чем * . Без скобок объявление int *daytab[13] определяет массив из 13 указателей на char . В более общем случае только первое измерение (соответствующее первому индексу) можно не задавать, все другие специфицировать необходимо. В параграфе 5.12 мы продолжим рассмотрение сложных объявлений. Упражйение 5.8. В функциях day_of_year и month_day нет никаких проверок правильности вводимых дат. Устраните этот недостаток. 5.8. Инициализация массивов указателей Напишем функцию month_name(n) , которая возвращает указатель на строку символов, содержащий название n -го месяца. Эта функция идеальна для демонстрации использования статического массива. Функция month_name имеет в своем личном распоряжении массив строк, на одну из которых она и возвращает указатель. Ниже покажем, как инициализируется этот массив имен. Синтаксис задания начальных значений аналогичен синтаксису предыдущих инициализаций: /* month_name: возвращает имя n-го месяца */ char *month_name(int n) { static char *name[] = { "Неверный месяц", "Январь", "Февраль", "Март", "Апрель", "Май", "Июнь", "Июль", "Август", "Сентябрь", "Октябрь", "Ноябрь", "Декабрь" }; return (а < 1 || n > 12) ? name[0] : name[n]; } Объявление name массивом указателей на символы такое же, как и объявление lineptr в программе сортировки. Инициализатором служит список строк, каждой из которых соответствует определенное место в массиве. Символы i -й строки где-то размещены, и указатель на них запоминается в name[i] . Так как размер массива name не специфицирован, компилятор вычислит его по количеству заданных начальных значений. 5.9. Указатели против многомерных массивов Начинающие программировать на Си иногда не понимают, в чем разница между двумерным массивом и массивом указателей вроде name из приведенного примера. Для двух следующих определений: int a[10][20]; int *b[10]; записи а[3][4] и b[3][4] будут синтаксически правильным обращением к некоторому значению типа int . Однако только а является истинно двумерным массивом: для двухсот элементов типа int будет выделена память, а вычисление смещения элемента а[строка][столбец] от начала массива будет вестись по формуле 20 х строка + столбец , учитывающей его прямоугольную природу. Для b же определено только 10 указателей, причем без инициализации. Инициализация должна задаваться явно — либо статически, либо в программе. Предположим, что каждый элемент b указывает на двадцатиэлементный массив, в результате где-то будут выделены пространство, в котором разместятся 200 значений типа int , и еще 10 ячеек для указателей. Важное преимущество массива указателей в том, что строки такого массива могут иметь разные длины. Таким образом, каждый элемент массива b не обязательно указывает на двадцатиэлементный вектор; один может указывать на два элемента, другой — на пятьдесят, а некоторые и вовсе могут ни на что не указывать. Наши рассуждения здесь касались целых значений, однако чаще массивы указателей используются для работы со строками символов, различающимися по длине, как это было в функции month_name . Сравните определение массива указателей и соответствующий ему рисунок: char *name[] = {"Неправильный месяц", "Янв", "Февр", "Март"}; с объявлением и рисунком для двумерного массива: char aname[][15] = {"Неправ. месяц", "Янв", "Февр", "Март"}; Упражнение 5.9. Перепишите программы day_of_year и month_day , используя вместо индексов указатели. 5.10. Аргументы командной строки В операционной среде, обеспечивающей поддержку Си, имеется возможность передать аргументы или параметры запускаемой программе с помощью командной строки. В момент вызова main получает два аргумента. В первом, обычно называемом argc (сокращение от argument count), стоит количество аргументов, задаваемых в командной строке. Второй, argv (от argument vector), является указателем на массив символьных строк, содержащих сами аргументы. Для работы с этими строками обычно используются указатели нескольких уровней. Простейший пример — программа echo ("эхо"), которая печатает аргументы своей командной строки в одной строчке, отделяя их друг от друга пробелами. Так, команда echo Здравствуй, мир! напечатает Здравствуй, мир! По соглашению argv[0] есть имя вызываемой программы, так что значение а где никогда не бывает меньше 1. Если argc равен 1, то в командной строке после имени программы никаких аргументов нет. В нашем примере argc равен 3, и соответственно argv[0] , argv[1] и argv[2] суть строки "echo" , "Здравствуй," и "мир!" . Первый необязательный аргумент — это argv[1] , последний — argv[argc- 1] . Кроме того, стандарт требует, чтобы argv[argc] всегда был пустым указателем. Первая версия программы echo трактует argv как массив символьных указателей. #include /* эхо аргументов командной строки: версия 1 */ main(int argc, char *argv[]) { int i; for (i = 1; i < argc; i++) printf("%s%s", argv[i], (i < argc-1) ? " " : ""); printf("\n"); return 0; } Так как argv — это указатель на массив указателей, мы можем работать с ним как с указателем, а не как с индексируемым массивом. Следующая программа основана на приращении argv , он приращивается так, что его значение в каждый отдельный момент указывает на очередной указатель на char ; перебор указателей заканчивается, когда исчерпан argc #include /* эхо аргументов командной строки; версия 2 */ main(int argc, char *argv[]) { while (--argc > 0) printf("%s%s", *++argv[i], (i < argc-1) ? " " : ""); printf("\n"); return 0; } Аргумент argv — указатель на начало массива строк аргументов. Использование в ++аrgv префиксного оператора ++ приведет к тому, что первым будет напечатан argv[1] , а не argv[0] . Каждое очередное приращение указателя дает нам следующий аргумент, на который указывает *argv . В это же время значение argc уменьшается на 1, и, когда оно станет нулем, все аргументы будут напечатаны. Инструкцию printf можно было бы написать и так: printf((argc > 1) ? "%s " : "%s", *++argv); Как видим, формат в printf тоже может быть выражением. В качестве второго примера возьмем программу поиска образца, рассмотренную в параграфе 4.1, и несколько усовершенствуем ее. Если вы помните, образец для поиска мы "вмонтировали" глубоко в программу, а это, очевидно, не лучшее решение. Построим нашу программу по аналогии с grep из UNIXa, т. е. так, чтобы образец для поиска задавался первым аргументом в командной строке. #include #include #define MAXLINE 1000 int getline(char *line, int max); /* find: печать строк с образцом, заданным 1-м аргументом */ main(int argc, char *argv[]) { char line[MAXLINE]; int found = 0; if (argc != 2) printf("Используйте в find образец\п"); else while (getline(line, MAXLINE) > 0) if (strstr(line, argv[1]) != NULL) { printf ("%s", line); found++; } return found; } Стандартная функция strstr(s, t) возвращает указатель на первую встретившуюся строку t в строке s или NULL , если таковой в s не встретилось. Функция объявлена в заголовочном файле Эту модель можно развивать и дальше, чтобы проиллюстрировать другие конструкции с указателями. Предположим, что мы вводим еще два необязательных аргумента. Один из них предписывает печатать все строки, кроме тех, в которых встречается образец; второй — перед каждой выводимой строкой печатать ее порядковый номер. По общему соглашению для Си-программ в системе UNIX знак минус перед аргументом вводит необязательный признак или параметр. Так, если -x служит признаком слова "кроме", которое изменяет задание на противоположное, а -n указывает на потребность в нумерации строк, то команда find -x -n образец напечатает все строки, в которых не найден указанный образец, и, кроме того, перед каждой строкой укажет ее номер. Необязательные аргументы разрешается располагать в любом порядке, при этом лучше, чтобы остальная часть программы не зависела от числа представленных аргументов. Кроме того, пользователю было бы удобно, если бы он мог комбинировать необязательные аргументы, например, так: find -nx образец А теперь запишем нашу программу. #include #include #define MAXLINE 1000 int getline(char *line, int max); /* find: печать строк образцами из 1-го аргумента */ main(int angc, char *argv[]) { char line[MAXLINE]; long lineno = 0; int c, except = 0, number = 0, found = 0; while (—argc > 0 && (*++argv)[0] == '-') while (c = *++argv[0]) switch (c) { case 'x': except = 1; break; case 'n' : number = 1; break; default: printf( "find: неверный параметр %с\п", с); argc = 0; found = -1; break; } if (argc != 1) printf ("Используйте: find -x -n образец\п"); else while (getline(line, MAXLINE) > 0) { lineno++; if ((strstr(line, *argv) != NULL) != except) { if (number) printf("%ld:", lineno); printf("%s", line); found++; } } return found; } Перед получением очередного аргумента argc уменьшается на 1, a argv "перемещается" на следующий аргумент. После завершения цикла при отсутствии ошибок argc содержит количество еще не обработанных аргументов, a argv указывает на первый из них. Таким образом, argc должен быть равен 1, а *аrgv указывать на образец. Заметим, что *++аrgv является указателем на аргумент-строку, a (*++argv)[0] — его первым символом, на который можно сослаться и другим способом: **++argv Поскольку оператор индексирования [] имеет более высокий приоритет, чем * и ++ , круглые скобки здесь обязательны, без них выражение трактовалось бы так же, как *++(argv[0]) . Именно такое выражение мы применим во внутреннем цикле, где просматриваются символы конкретного аргумента. Во внутреннем цикле выражение *++argv[0] приращивает указатель argv[0] Потребность в более сложных выражениях для указателей возникает не так уж часто. Но если такое случится, то разбивая процесс вычисления указателя на два или три шага, вы облегчите восприятие этого выражения. Упражнение 5.10. Напишите программу expr , интерпретирующую обратную польскую запись выражения, задаваемого командной строкой, в которой каждый оператор и операнд представлены отдельным аргументом. Например, expr 2 3 4 + * вычисляется так же, как выражение 2 х (3 + 4). Упражнение 5.11. Усовершенствуйте программы entab и detab (см. упражнения 1.20 и 1.21) таким образом, чтобы через аргументы можно было задавать список "стопов" табуляции. Упражнение 5.12. Расширьте возможности entab и detab таким образом, чтобы при обращении вида entab -m +n "стопы" табуляции начинались с m -й позиции и выполнялись через каждые n позиций. Разработайте удобный для пользователя вариант поведения программы по умолчанию (когда нет никаких аргументов). Упражнение 5.13. Напишите программу tail , печатающую n последних введенных строк. По умолчанию значение n равно 10, но при желании n можно задать с помощью аргумента. Обращение вида tail -n печатает n последних строк. Программа должна вести себя осмысленно при любых входных данных и любом значении n . Напишите программу так, чтобы наилучшим образом использовать память; запоминание строк организуйте, как в программе сортировки, описанной в параграфе 5.6, а не на основе двумерного массива с фиксированным размером строки. 5.11. Указатели на функции В Си сама функция не является переменной, но можно определить указатель на функцию и работать с ним, как с обычной переменной: присваивать, размещать в массиве, передавать в качестве параметра функции, возвращать как результат из функции и т.д. Для иллюстрации этих возможностей воспользуемся программой сортировки, которая уже встречалась в настоящей главе. Изменим ее так, чтобы при задании необязательного аргумента -n вводимые строки упорядочивались по их числовому значению, а не в лексикографическом порядке. Сортировка, как правило, распадается на три части: на сравнение, определяющее упорядоченность пары объектов; перестановку, меняющую местами пару объектов, и сортирующий алгоритм, который осуществляет сравнения и перестановки до тех пор, пока все объекты не будут упорядочены. Алгоритм сортировки не зависит от операций сравнения и перестановки, так что передавая ему в качестве параметров различные функции сравнения и перестановки, его можно настроить на различные критерии сортировки. Лексикографическое сравнение двух строк выполняется функцией strcmp (мы уже использовали эту функцию в ранее рассмотренной программе сортировки); нам также потребуется программа numcmp , сравнивающая две строки как числовые значения и возвращающая результат сравнения в том же виде, в каком его выдает strcmp . Эти функции объявляются перед main , а указатель на одну из них передается функции qsort . Чтобы сосредоточиться на главном, мы упростили себе задачу, отказавшись от анализа возможных ошибок при задании аргументов. #include #include #define MAXLINES 5000 /* максимальное число строк */ char *lineptr[MAXLINES]; /* указатели на строки текста */ int readlines(char *lineptr[], int nlines); void writelines(char *lineptr[], int nlines); void qsort(void *lineptr[], int left, int right, int (*comp)(void *, void *)); int numcmp(char *, char *); /* сортировка строк */ main(int argc, char *argv[]) { int nlines; /* количество прочитанных строк */ int numeric = 0; /* 1, если сорт, по числ. знач. */ if (argc > 1 && strcmp(argv[1], "-n") == 0) numeric = 1; if ((nlines = readlinesdineptr, MAXLINES)) >= 0) { qsort((void **) lineptr, 0, nlines-1, (int (*)(void*, void*))(numeric ? numcmp : strcmp)); writelines(lineptr, nlines); return 0; } else { printf("Введено слишком много строк\п"); return 1; } } В обращениях к функциям qsort , strcmp и numcmp их имена трактуются как адреса этих функций, поэтому оператор & перед ними не нужен, как он не был нужен и перед именем массива. Мы написали qsort так, чтобы она могла обрабатывать данные любого типа, а не только строки символов. Как видно из прототипа, функция qsort в качестве своих аргументов ожидает массив указателей, два целых значения и функцию с двумя аргументами-указателями. В качестве аргументов-указателей заданы указатели обобщенного типа void* . Любой указатель можно привести к типу void* и обратно без потери информации, поэтому мы можем обратиться к qsort , предварительно преобразовав аргументы в void* Внутри функции сравнения ее аргументы будут приведены к нужному ей типу. На самом деле эти преобразования никакого влияния на представления аргументов не оказывают, они лишь обеспечивают согласованность типов для компилятора. /* qsort: сортирует v[left]...v[ right] по возрастанию */ void qsort(void *v[], int left, int right, int (*comp)(void *, void *)) { int i, last; void swap(void *v[], int, int); if (left >= right) /* ничего не делается, если */ return; /* в массиве менее двух элементов */ swap(v, left, (left + right )/2); last = left; for (i = left+1; i <= right; i++) if ((*comp)(v[i], v[left]) < 0) swap(v, ++last, i); swap(v, left, last); qsort(v, left, last-1, comp); qsort(v, last+1, right, comp); } Повнимательней приглядимся к объявлениям. Четвертый параметр функции qsort : int (*comp)(void *, void *) сообщает, что comp — это указатель на функцию, которая имеет два аргумента-указателя и выдает результат типа int Использование comp в строке if ((*comp)(v[i], v[left]) < 0) согласуется с объявлением " comp — это указатель на функцию", и, следовательно, *comp — это функция, а (*comp)(v[i], v[left]) — обращение к ней. Скобки здесь нужны, чтобы обеспечить правильную трактовку объявления; без них объявление int *comp(void *, void *) /* НЕВЕРНО */' говорило бы, что comp — это функция, возвращающая указатель на int , а это совсем не то, что требуется. Мы уже рассматривали функцию strcmp , сравнивающую две строки. Ниже приведена функция numcmp , которая сравнивает две строки, рассматривая их как числа; предварительно они переводятся в числовые значения функцией atof #include /* numcmp: сравнивает s1 и s2 как числа */ int numcmp(char *s1, char *s2) { double v1, v2; v1 = atof(s1); v2 = atof(s2); if (v1 < v2) return -1; else if (v1 > v2) return 1; else return 0; } Функция swap , меняющая местами два указателя, идентична той, что мы привели ранее в этой главе за исключением того, что объявления указателей заменены на void* void swap(void *v[], int i, int j) { |