Язык программирования Си Брайан Керниган, Деннис Ритчи 3е издание Версия 1 Table of Contents
 Скачать 2.33 Mb.
|
|
Упражнение 4.3. Исходя из предложенной нами схемы, дополните программу-калькулятор таким образом, чтобы она "понимала" оператор получения остатка от деления ( % ) и отрицательные числа. Упражнение 4.4. Добавьте команды, с помощью которых можно было бы печатать верхний элемент стека (с сохранением его в стеке), дублировать его в стеке, менять местами два верхних элемента стека. Введите команду очистки стека. Упражнение 4.5. Предусмотрите возможность использования в программе библиотечных функций sin , exp и pow . См. библиотеку в приложении В (параграф 4). Упражнение 4.6. Введите команды для работы с переменными (легко обеспечить до 26 переменных, каждая из которых имеет имя, представленное одной буквой латинского алфавита). Добавьте переменную, предназначенную для хранения самого последнего из напечатанных значений. Упражнение 4.7. Напишите программу ungets(s) , возвращающую строку s во входной поток. Должна ли ungets "знать" что-либо о переменных buf и bufр , или ей достаточно пользоваться только функцией ungetch ? Упражнение 4.8. Предположим, что число символов, возвращаемых назад, не превышает 1. Модифицируйте с учетом этого факта функции getch и ungetch Упражнение 4.9. В наших функциях не предусмотрена возможность возврата EOF . Подумайте, что надо сделать, чтобы можно было возвращать EOF , и скорректируйте соответственно программу. Упражнение 4.10. В основу программы калькулятора можно положить применение функции getline , которая читает целиком строку; при этом отпадает необходимость в getch и ungetch . Напишите программу, реализующую этот подход. 4.4. Области видимости Функции и внешние переменные, из которых состоит Си-программа, каждый раз компилировать все вместе нет никакой необходимости. Исходный текст можно хранить в нескольких файлах. Ранее скомпилированные программы можно загружать из библиотек. В связи с этим возникают следующие вопросы: Как писать объявления, чтобы на протяжении компиляции используемые переменные были должным образом объявлены? В каком порядке располагать объявления, чтобы во время загрузки все части программы оказались связаны нужным образом? Как организовать объявления, чтобы они имели лишь одну копию? Как инициализировать внешние переменные? Начнем с того, что разобьем программу-калькулятор на несколько файлов. Конечно, эта программа слишком мала, чтобы ее стоило разбивать на файлы, однако разбиение нашей программы позволит продемонстрировать проблемы, возникающие в больших программах. Областью видимости имени считается часть программы, в которой это имя можно использовать. Для автоматических переменных, объявленных в начале функции, областью видимости является функция, в которой они объявлены. Локальные переменные разных функций, имеющие, однако, одинаковые имена, никак не связаны друг с другом. То же утверждение справедливо и в отношении параметров функции, которые фактически являются локальными переменными. Область действия внешней переменной или функции простирается от точки программы, где она объявлена, до конца файла, подлежащего компиляции. Например, если main , sp , val , push и pop определены в одном файле в указанном порядке, т. е. main() {…} int sp = 0; double val[MAXVAL]; void push(double f){…} double pop(void) {…} то к переменным sp и val можно адресоваться из push и pop просто по их именам; никаких дополнительных объявлений для этого не требуется. Заметим, что в main эти имена не видимы так же, как и сами push и pop Однако, если на внешнюю переменную нужно сослаться до того, как она определена, или если она определена в другом файле, то ее объявление должно быть помечено словом extern Важно отличать объявление внешней переменной от ее определения. Объявление объявляет свойства переменной (прежде всего ее тип), а определение, кроме того, приводит к выделению для нее памяти. Если строки int sp; double val[MAXVAL]; расположены вне всех функций, то они определяют внешние переменные sp и val, т. е. отводят для них память, и, кроме того, служат объявлениями для остальной части исходного файла. А вот строки extern int sp; extern double val[]; объявляют для оставшейся части файла, что sp — переменная типа int , a val — массив типа double (размер которого определен где-то в другом месте); при этом ни переменная, ни массив не создаются, и память им не отводится. На всю совокупность файлов, из которых состоит исходная программа, для каждой внешней переменной должно быть одно-единственное определение; другие файлы, чтобы получить доступ к внешней переменной, должны иметь в себе объявление extern . (Впрочем, объявление extern можно поместить и в файл, в котором содержится определение.) В определениях массивов необходимо указывать их размеры, что в объявлениях extern не обязательно. Инициализировать внешнюю переменную можно только в определении. Хотя вряд ли стоит организовывать нашу программу таким образом, но мы определим push и pop в одном файле, a val и sp — в другом, где их и инициализируем. При этом для установления связей понадобятся такие определения и объявления: В файле 1: extern int sp; extern double val[]; void push(double f ) {…} double pop(void) {…} В файле 2: int sp = 0; double val[MAXVAL]; Поскольку объявления extern находятся в начале файла1 и вне определений функций, их действие распространяется на все функции, причем одного набора объявлений достаточно для всего файла1. Та же организация extern -объявлений необходима и в случае, когда программа состоит из одного файла, но определения sp и val расположены после их использования. 4.5. Заголовочные файлы Теперь представим себе, что компоненты программы-калькулятора имеют существенно большие размеры, и зададимся вопросом, как в этом случае распределить их по нескольким файлам. Программу main поместим в файл, который мы назовем main.с ; push, pop и их переменные расположим во втором файле, stack.с ; a getop — в третьем, getop.с . Наконец, getch и ungetch разместим в четвертом файле getch.с ; мы отделили их от остальных функций, поскольку в реальной программе они будут получены из заранее скомпилированной библиотеки. Существует еще один момент, о котором следует предупредить читателя, — определения и объявления совместно используются несколькими файлами. Мы бы хотели, насколько это возможно, централизовать эти объявления и определения так, чтобы для них существовала только одна копия. Тогда программу в процессе ее развития будет легче и исправлять, и поддерживать в нужном состоянии. Для этого общую информацию расположим в заголовочном файле calc.h , который будем по мере необходимости включать в другие файлы. (Строка #include описывается в параграфе 4.11.) В результате получим программу, файловая структура которой показана ниже: calc.h: #define NUMBER '0' void push(double); double pop(void); int getop(char[]); int getch(void); void ungetch(int); main.c: #include #include #include "calc.h" #define MAXOP 100 main() { … } getop.c: #include #include #include "calc.h" getop (){ … } stack.c: #include #include "calc.h" #define MAXVAL 100 int sp = 0; double val[MAXVAL]; void push(double) { … } double pop(void) { … } getch.c: #include #define BUFSIZE 100 char buf [BUFSIZE]; int bufp = 0; int getch(void) { … } void ungetch(int) { … } Неизбежен компромисс между стремлением, чтобы каждый файл владел только той информацией, которая ему необходима для работы, и тем, что на практике иметь дело с большим количеством заголовочных файлов довольно трудно. Для программ, не превышающих некоторого среднего размера, вероятно, лучше всего иметь один заголовочный файл, в котором собраны вместе все объекты, каждый из которых используется в двух различных файлах; так мы здесь и поступили. Для программ больших размеров потребуется более сложная организация с большим числом заголовочных файлов. 4.6. Статические переменные Переменные sp и val в файле stack.с , а также buf и bufp в getch.с находятся в личном пользовании функций этих файлов, и нет смысла открывать к ним доступ кому-либо еще. Указание static , примененное к внешней переменной или функции, ограничивает область видимости соответствующего объекта концом файла. Это способ скрыть имена. Так, переменные buf и bufp должны быть внешними, поскольку их совместно используют функции getch и ungetch , но их следует сделать невидимыми для "пользователей" функций getch и ungetch Статическая память специфицируется словом static , которое помещается перед обычным объявлением. Если рассматриваемые нами две функции и две переменные компилируются в одном файле, как в показанном ниже примере: static char buf[BUFSIZE]; /* буфер для ungetch */ static int bufp = 0; /* след, свободная позиция в buf */ int getch(void) { ... } void ungetch(int c) { ... } то никакая другая программа не будет иметь доступ ни к buf , ни к bufp , и этими именами можно свободно пользоваться в других файлах для совсем иных целей. Точно так же, помещая указание static перед объявлениями переменных sp и val , с которыми работают только push и pop , мы можем скрыть их от остальных функций. Указание static чаще всего используется для переменных, но с равным успехом его можно применять и к функциям. Обычно имена функций глобальны и видимы из любого места программы. Если же функция помечена словом static , то ее имя становится невидимым вне файла, в котором она определена. Объявление static можно использовать и для внутренних переменных. Как и автоматические переменные, внутренние статические переменные локальны в функциях, но в отличие от автоматических они не возникают только на период работы функции, а существуют постоянно. Это значит, что внутренние статические переменные обеспечивают постоянное сохранение данных внутри функции. Упражнение 4.11. Модифицируйте функцию getop так, чтобы отпала необходимость в функции ungetch Подсказка: используйте внутреннюю статическую переменную. 4.7. Регистровые переменные Объявление register сообщает компилятору, что данная переменная будет интенсивно использоваться. Идея состоит в том, чтобы переменные, объявленные register , разместить на регистрах машины, благодаря чему программа, возможно, станет более короткой и быстрой. Однако компилятор имеет право проигнорировать это указание. Объявление register выглядит следующим образом: register int x; register char с; и т. д. Объявление register может применяться только к автоматическим переменным и к формальным параметрам функции. Для последних это выглядит так: f( register unsigned m, register long n) { register int i; … } На практике существуют ограничения на регистровые переменные, что связано с возможностями аппаратуры. Располагаться в регистрах может лишь небольшое число переменных каждой функции, причем только определенных типов. Избыточные объявления register ни на что не влияют, так как игнорируются в отношении переменных, которым не хватило регистров или которые нельзй разместить на регистре. Кроме того, применительно к регистровой переменной независимо от того, выделен на самом деле для нее регистр или нет, не определено понятие адреса (см. главу 5). Конкретные ограничения на количество и типы регистровых переменных зависят от машины. 4.8. Блочная структура Поскольку функции в Си нельзя определять внутри других функций, он не является языком, допускающим блочную структуру программы в том смысле, как это допускается в Паскале и подобных ему языках. Но переменные внутри функций можно определять в блочно-структурной манере. Объявления переменных (вместе с инициализацией) разрешено помещать не только в начале функции, но и после любой левой фигурной скобки, открывающей составную инструкцию. Переменная, описанная таким способом, "затеняет" переменные с тем же именем, расположенные в объемлющих блоках, и существует вплоть до соответствующей правой фигурной скобки. Например, в if (n > 0) { int i; /* описание новой переменной i */ for (i = 0; i < n; i++) … } областью видимости переменной i является ветвь if , выполняемая при n>0 ; и эта переменная никакого отношения к любым i , расположенным вне данного блока, не имеет. Автоматические переменные, объявленные и инициализируемые в блоке, инициализируются каждый раз при входе в блок. Переменные static инициализируются только один раз при первом входе в блок. Автоматические переменные и формальные параметры также "затеняют" внешние переменные и функции с теми же именами. Например, в int x; int у; f(double x) { double у; … } х внутри функции f рассматривается как параметр типа double , в то время как вне f это внешняя переменная типа int . То же самое можно сказать и о переменной y С точки зрения стиля программирования, лучше не пользоваться одними и теми же именами для разных переменных, поскольку слишком велика возможность путаницы и появления ошибок. 4.9. Инициализация Мы уже много раз упоминали об инициализации, но всегда лишь по случаю, в ходе обсуждения других вопросов. В этом параграфе мы суммируем все правила, определяющие инициализацию памяти различных классов. При отсутствии явной инициализации для внешних и статических переменных гарантируется их обнуление; автоматические и регистровые переменные имеют неопределенные начальные значения ("мусор"). Скалярные переменные можно инициализировать в их определениях, помещая после имени знак = и соответствующее выражение: int x = 1; char squote = '\''; long day = 1000L * 60L * 60L * 24L; /* день в миллисекундах */ Для внешних и статических переменных инициализирующие выражения должны быть константными, при этом инициализация осуществляется только один раз до начала выполнения программы. Инициализация автоматических и регистровых переменных выполняется каждый раз при входе в функцию или блок. Для таких переменных инициализирующее выражение — не обязательно константное. Это может быть любое выражение, использующее ранее определенные значения, включая даже и вызовы функций. Например, в программе бинарного поиска, описанной в параграфе 3.3, инициализацию можно записать так: int binsearch(int x, int v[], int n) { int low = 0; int high = n - 1; int mid; а не так: int low, high, mid; low = 0; high = n - 1; В сущности, инициализация автоматической переменной — это более короткая запись инструкции присваивания. Какая запись предпочтительнее — в большой степени дело вкуса. До сих пор мы пользовались главным образом явными присваиваниями, поскольку инициализация в объявлениях менее заметна и дальше отстоит от места использования переменной. Массив можно инициализировать в его определении с помощью заключенного в фигурные скобки списка инициализаторов, разделенных запятыми. Например, чтобы инициализировать массив days , элементы которого суть количества дней в каждом месяце, можно написать: int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; Если размер массива не указан, то длину массива компилятор вычисляет по числу заданных инициализаторов; в нашем случае их количество равно 12. Если количество инициализаторов меньше числа, указанного в определении длины массива, то для внешних, статических и автоматических переменных оставшиеся элементы будут нулевыми. Задание слишком большого числа инициализаторов считается ошибкой. В языке нет возможности ни задавать повторения инициализатора, ни инициализовать средние элементы массива без задания всех предшествующих значений. Инициализация символьных массивов — особый случай: вместо конструкции с фигурными скобками и запятыми можно использовать строку символов. Например, возможна такая запись: char pattern[] = "ould"; представляющая собой более короткий эквивалент записи char pattern[] = {'о', 'u', 'l', 'd', '\0'}; В данном случае размер массива равен пяти (четыре обычных символа и завершающий символ '\0' ). 4.10. Рекурсия В Си допускается рекурсивное обращение к функциям, т.е. функция может обращаться сама к себе, прямо или косвенно. Рассмотрим печать числа в виде строки символов. Как мы упоминали ранее, цифры генерируются в обратном порядке — младшие цифры получаются раньше старших, а печататься они должны в правильной последовательности. Проблему можно решить двумя способами. Первый — запомнить цифры в некотором массиве в том порядке, как они получались, а затем напечатать их в обратном порядке; так это и было сделано в функции itoa , рассмотренной в параграфе 3.6. Второй способ — воспользоваться рекурсией, при которой printd сначала вызывает себя, чтобы напечатать все старшие цифры, и затем печатает последнюю младшую цифру. Эта программа, как и предыдущий ее вариант, при использовании самого большого по модулю отрицательного числа работает неправильно. #include /* printd: печатает n как целое десятичное число */ void printd(int n) { if (n < 0) { putchar('-'); n = -n; } if (n / 10) printd(n / 10); putchar(n % 10 + '0'); } Когда функция рекурсивно обращается сама к себе, каждое следующее обращение сопровождается получением ею нового полного набора автоматических переменных, независимых от предыдущих наборов. Так, в обращении printd(123) при первом вызове аргумент n = 123,при втором — printd получает аргумент 12, при третьем вызове — значение 1. Функция рrintd на третьем уровне вызова печатает 1 и возвращается на второй уровень, после чего печатает цифру 2 и возвращается на первый уровень. Здесь она печатает 3 и заканчивает работу. Следующий хороший пример рекурсии — это быстрая сортировка, предложенная Ч. А. Р. Хоаром в 1962 г. Для заданного массива выбирается один элемент, который разбивает остальные элементы на два подмножества — те, что меньше, и те, что не меньше него. Та же процедура рекурсивно применяется и к двум полученным подмножествам. Если в подмножестве менее двух элементов, то сортировать нечего, и рекурсия завершается. Наша версия быстрой сортировки, разумеется, не самая быстрая среди всех возможных, но зато одна из самых простых. В качестве делящего элемента мы используем серединный элемент. /* qsort: сортирует v[left]...v[right] по возрастанию */ void qsort(int v[], int left, int right) { int i, last; void swap(int v[], int i, int j); if (left >= right) /* ничего не делается, если */ return; /* в массиве менее двух элементов */ swap(v, left, (left + right)/2); /* делящий элемент */ last = left; /* переносится в v[0] */ for(i = left+1; i <= right; i++) /* деление на части */ if (v[i] < v[left]) swap(v, ++last, i); swap(v, left, last); /* перезапоминаем делящий элемент */ qsort(v, left, last-1); qsort(v, last+1, right); } В нашей программе операция перестановки оформлена в виде отдельной функции ( swap ), поскольку встречается в qsort трижды. /* swap: поменять местами v[i] и v[j] */ void swap(int v[], int i, int j) { int temp; temp = v[i]; v[i] = v[j]; v[j] = temp; } Стандартная библиотека имеет функцию qsort , позволяющую сортировать объекты любого типа. Рекурсивная программа не обеспечивает ни экономии памяти, поскольку требуется где-то поддерживать стек значений, подлежащих обработке, ни быстродействия; но по сравнению со своим нерекурсивным эквивалентом она часто короче, а часто намного легче для написания и понимания. Такого рода программы особенно удобны для обработки рекурсивно определяемых структур данных вроде деревьев; с хорошим примером на эту тему вы познакомитесь в параграфе 6.5. |