Б. Керриган, Д. Ритчи Язык программирования C. Б. Керниган, Д. зык программирования и . Издание 3е, исправленное Перевод с английского под редакцией Вс. С. Штаркмана СанктПетербург 2003
 Скачать 31.48 Mb.
|
|
Упражнение 3.2. Напишите escape(s, t), которая при копи- ровании текста из t в s преобразует такие символы, как новая строка и табуляция в "видимые последовательности символов" (вроде \л и \t). Используйте инструкцию switch. Напишите функцию, выполняющую обратное преобразование эскейп-последовательностей в настоящие символы. 3.5. Циклы while и for Мы уже встречались с циклами while и for. В цикле (выражение) инструкция вычисляется выражение. Если его значение отлично от нуля, то выполня- ется инструкция, и вычисление выражения повторяется. Этот цикл про- должается до тех пор, пока выражение не станет равным нулю, после чего вычисления продолжатся с точки, расположенной сразу за инструкцией. Инструкция for for инструкция эквивалентна конструкции while { инструкция если не считать отличий в поведении инструкции continue, речь о кото- рой пойдет в параграфе 3. 7. С точки зрения грамматики три компоненты цикла for представляют собой произвольные выражения, но чаще и — это присваивания или вызовы функций, а - выражение отношения. из этих трех 3.5. Циклы while и for _ _ 85 выражений может отсутствовать, но точку с запятой опускать нельзя. При отсутствии или считается, что их просто нет в конструкции цик- ла; при отсутствии предполагается, что его значение как бы всегда истинно. Например, for (;;) { есть "бесконечный" цикл, выполнение которого, вероятно, прерывается каким-то другим способом, например с помощью инструкций Ь reak или return. Какой цикл выбрать: while или f o r - это дело вкуса. Так, в while = == ' '' с == с == ; /* обойти символы-разделители */ нет ни инициализации, ни пересчета параметра, поэтому здесь больше подходит while. Там, где есть простая инициализация и пошаговое увеличение значе- ния некоторой переменной, больше подходит цикл так как в этом цик- ле организующая его часть сосредоточена в начале записи. на- чало обрабатывающего первые п элементов массива, имеет следу- ющий вид: for (i = 0; i < Это похоже на в Фортране и в Сходство, однако, не вполне точное, так как в Си индекс и его предельное значение могут изменяться внутри цикла, и значение индекса i выхода из цикла всегда определено. Поскольку три компоненты цикла могут быть произвольными выражениями, организация f о не ограничива- ется только случаем арифметической прогрессии. Однако включать в за- головок цикла вычисления, не имеющие отношения к инициализации и инкрементированию, считается плохим стилем. Заголовок лучше оста- вить только для операций управления циклом. В качестве более внушительного примера приведем другую версию про- граммы at выполняющей преобразование строки в ее числовой эквива- лент. Это более общая версия по сравнению с рассмотренной в главе 2, в том смысле, что она игнорирует левые символы-разделители (если они есть) и должным образом реагирует на знаки + и -, которые могут стоять перед цифрами. (В главе 4 будет рассмотрен вариант atof, который осу- ществляет подобное преобразование для чисел с плавающей точкой.) 86 _ _ Глава 3. Управление Структура программы отражает вид вводимой информации: символы-разделители, если они знак, если он целую часть и ее На каждом шаге выполняется определенная часть работы и четко фикси- руется ее результат, который затем используется на следующем шаге. Обработка данных заканчивается на первом же символе, который не мо- жет быть частью числа. ttinclude /* преобразование s в целое число; версия 2 */ int i, n, sign; /* игнорировать символы-разделители */ for (i = 0; sign = (s[i] == '-') ? -1: 1; if (s[i] == '+' s[i] == /* пропуск знака */ for (n = 0; i++) n = 10 * n + (s[i] - return sign * n; } Заметим, что в стандартной библиотеке имеется более совершенная фун- кция преобразования строки в длинное целое (long int) - функция st (см. параграф 5 приложения В). Преимущества, которые дает централизация управления циклом, ста- новятся еще более очевидными, когда несколько циклов вложены друг в друга. Проиллюстрируем их на примере сортировки массива целых чи- сел методом Шелла, предложенным им в г. Основная идея этого алго- ритма в том, что на ранних стадиях сравниваются далеко отстоящие друг от друга, а не соседние элементы, как в обычных перестановочных сорти- ровках. Это приводит к быстрому устранению массовой неупорядоченно- сти, благодаря чему на более поздней стадии остается меньше работы. Ин- тервал между сравниваемыми элементами постепенно уменьшается до еди- ницы, и в этот момент сортировка сводится к обычным перестановкам со- седних элементов. Программа shellsort имеет следующий вид: /* shellsort: v v в возрастающем порядке */ void shellsort (int v [], int n) 3.5. Циклы while и for __ 87 int gap, temp; for (gap = n/2; gap > 0; gap /= 2) (i = gap; i < n; i++) for (j = i - gap; j >= 0 && v[j] > v[j + j -= gap) { temp = v[j] = v[j v[j + gap] = temp; Здесь использованы три вложенных друг в друга цикла. Внешний управ- ляет интервалом gap между сравниваемыми элементами, сокращая путем деления пополам от п/2 до нуля. Средний цикл перебирает элемен- ты. Внутренний - сравнивает каждую пару элементов, отстоящих друг от друга на расстоянии gap, и переставляет элементы в неупорядоченных парах. Так как gap обязательно сведется к единице, все элементы в конеч- ном счете будут упорядочены. Обратите внимание на то, что универсаль- ность цикла f o r позволяет сделать внешний цикл по форме похожим на другие, хотя он и не является арифметической прогрессией. Последний оператор Си - это (запятая), которую чаще всего ис- пользуют в инструкции f о г. Пара выражений, разделенных запятой, вы- числяется слева направо. Типом и значением результата являются тип и значение правого выражения, что позволяет в инструкции в каждой из трех компонент иметь по нескольку выражений, например вести два индекса параллельно. Продемонстрируем это на примере функции которая "переворачивает" строку s, оставляя результат в той же строке s: /* reverse: переворачивает строку s (результат в s) */ void reverse(char { int i, for (i = 0, j = strlen(s)-1; i < j; i++, j { с = s[j] = c; 3. Управление Запятые, разделяющие аргументы функции, переменные в объявлениях и пр. не являются операторами-запятыми и не обеспечивают вычислений слева направо. Запятыми как операторами следует пользоваться умеренно. Более всего они уместны в конструкциях, которые тесно связаны друг с другом (как в программы reverse), а также в макросах, в которых многосту- пенчатые вычисления должны быть выражены одним выражением. За- пятой-оператором в программе можно было бы воспользоваться и при обмене символами в проверяемых парах элементов строки, мысля этот обмен как одну отдельную операцию: for (i = 0, j = strlen(s)-1; i < j; i++, с = s[i], s[i] = s[j], s[j] = c; Упражнение 3.3. Напишите функцию s2), заменяющую сокращенную запись наподобие в строке s1 эквивалентной полной записью . . xyz в s2. В s1 допускаются буквы (прописные и строчные) и цифры. Следует уметь справляться с такими случаями, как a-b-c, -9 и Считайте знак - в начале или в конце s1 обычным символом минус. 3.6. Цикл do-while Как мы говорили в главе в циклах 1е и f о проверка условия окон- чания цикла выполняется наверху. В Си имеется еще один вид цикла, while, в котором эта проверка в отличие от while и f o r делается внизу после каждого прохождения тела цикла, т. е. после того, как тело вы- полнится хотя бы один раз. Цикл do-while имеет следующий синтаксис: do инструкция while (выражение); Сначала выполняется инструкция, затем вычисляется выражение. Если оно истинно, то инструкция выполняется снова и т. д. Когда выражение становится ложным, цикл заканчивает работу. Цикл эквивален- тен циклу в Паскале с той лишь разницей, что в первом чае указывается условие продолжения цикла, а во втором условие его окончания. Опыт показывает, что цикл do-while используется гораздо реже, чем while и f o r . Тем не менее потребность в нем время от времени возникает, как, например, в функции (обратной по отношению к atoi), преоб- 3.6. Цикл _ _ разующей число в строку символов. Выполнить такое преобразование оказалось несколько более сложным делом, чем ожидалось, поскольку простые алгоритмы генерируют цифры в обратном порядке. Мы остано- вились на варианте, в котором сначала формируется обратная последова- тельность цифр, а затем она реверсируется. /* преобразование в строку s */ void itoa(int n, { int i, sign; if = n) < 0) /* сохраняем знак */ n = -n; /* делаем n положительным */ i = 0; do { /* генерируем цифры в обратном порядке */ s[i++] = n % 10 + /* следующая цифра */ } while /= 10) > /* исключить ее */ if (sign < 0) s[i++] = s[i] = Конструкция do-while здесь необходима или по крайней мере удобна, поскольку в s посылается хотя бы один символ, даже если n равно нулю. В теле цикла одну инструкцию мы выделили фигурными скобками (хотя они и избыточны), чтобы неискушенный читатель не принял по ошибке слово while за начало цикла while. Упражнение 3.4. При условии, что для представления чисел используется дополнительный код, наша версия itoa не справляется с самым большим по модулю отрицательным числом, значение которого равняется ), где п - размер слова. Объясните, чем это вызвано. Модифицируйте программу таким образом, чтобы она давала правильное значение указанного числа независимо от машины, на которой выполняется. Упражнение 3.5. Напишите функцию которая переводит целое п в строку s, представляющую число по основанию В частности, 16) помещает в s текст числа п в шестнадцатеричном виде. Упражнение 3.6. Напишите версию itoa с дополнительным третьим аргументом, задающим минимальную ширину поля. При необходимости преобразованное число должно слева дополняться пробелами. 3. Управление 3.7. Инструкции break и continue Иногда бывает удобно выйти из цикла не по результату проверки, осу- ществляемой в начале или в конце цикла, а каким-то другим способом. Такую возможность для циклов f o r , while и do-while, а также для пере- ключателя switch предоставляет инструкция Эта инструкция вы- зывает немедленный выход из самого внутреннего из объемлющих ее циклов или переключателей. Следующая функция, t rim, удаляет из строки завершающие пробелы, табуляции, символы новой строки; используется в ней для выхода из цикла по первому обнаруженному справа символу, отличному от на- званных. /* trim: удаляет завершающие пробелы, табуляции и новые строки */ int { int n; for (n = strlen(s)-1; n >= 0; if (s[n] s[n] != && s[n] != break; s[n+1] = return n; } С помощью функции можно получить длину строки. Цикл for просматривает его в обратном порядке, начиная с конца, до тех пор, пока не встретится символ, отличный от пробела, табуляции и новой строки. Цикл прерывается, как только такой символ обнаружится или n станет отрицательным (т. е. вся строка будет просмотрена). Убедитесь, что функ- ция ведет себя правильно и в случаях, когда строка пуста или состоит толь- ко из символов-разделителей. Инструкция continue в чем-то похожа на break, но применяется го- раздо реже. Она вынуждает ближайший объемлющий ее цикл while или do-while) начать следующий шаг итерации. Для while и do-while это означает немедленный переход к проверке условия, а для - к прира- щению шага. Инструкцию continue можно применять только к циклам, но не к switch. Внутри переключателя switch, расположенного в цикле, она вызовет переход к следующей итерации этого цикла. Вот фрагмент программы, обрабатывающий только неотрицательные элементы массива а (отрицательные пропускаются). 3.8. Инструкция goto и метки for i < n; i++) { if (a[i] < 0) /* пропуск отрицательных элементов */ continue; /* обработка положительных элементов */ } К инструкции conti часто прибегают тогда, когда оставшаяся часть цикла сложна, а замена условия в нем на противоположное и введение еще одно- го уровня приводят к слишком большому числу уровней вложенности. 3.8. Инструкция goto и метки В Си имеются порицаемая многими инструкция goto и метки для пере- хода на них. Строго говоря, в этой инструкции нет никакой необходимо- сти, и на практике почти всегда легко без нее обойтись. До сих пор в на- шей книге мы не использовали goto. Однако существуют случаи, в которых goto может пригодиться. Наи- более типична ситуация, когда нужно прервать обработку в некоторой глубоко вложенной структуре и выйти сразу из двух или большего числа вложенных циклов. Инструкция здесь не поможет, так как она обе- спечит выход только из самого внутреннего цикла. В качестве примера рассмотрим следующую конструкцию: for (...) { if (disaster) /* если бедствие */ goto error; /* уйти на ошибку */ error: /* обработка ошибки */ Такая организация программы удобна, если подпрограмма обработки ошибочной ситуации не тривиальна и ошибка может встретиться в не- скольких местах. Метка имеет вид обычного имени переменной, за которым следует дво- еточие. На метку можно перейти с помощью goto из любого места данной функции, т. е. метка видима на протяжении всей функции. В качестве еще одного примера рассмотрим такую задачу: определить, есть ли в массивах а и b совпадающие элементы. Один из возможных ва- риантов ее реализации имеет следующий вид: 92 Глава 3. Управление for i < n; for (j = 0; j < j++) if (a[i] == goto found; /* нет одинаковых элементов */ found: /* обнаружено совпадение: a[i] == b[j] */ Программу нахождения совпадающих элементов можно написать и без goto, правда, заплатив за это дополнительными проверками и еще одной переменной: found = 0; for (i = 0; i < n && i for (j = 0; j < m && if (a[i] == found = if (found) /* обнаружено == */ - else /* нет одинаковых элементов */ За исключением редких случаев, подобных только что приведенным, программы с применением goto, как правило, труднее для понимания и сопровождения, чем программы, решающие те же задачи без goto. Хотя мы и не догматики в данном вопросе, все же думается, что к goto следует прибегать крайне редко, если использовать эту инструкцию вообще. Глава 4 Функции и структура программы Функции разбивают большие вычислительные задачи на более мелкие и позволяют воспользоваться тем, что уже сделано другими разработчи- ками, а не начинать создание программы каждый раз "с нуля". В выбран- ных должным образом функциях "упрятаны" несущественные для дру- гих частей программы детали их функционирования, что делает програм- му в целом более ясной и облегчает внесение в нее изменений. Язык проектировался чтобы функции были эффективными и про- стыми в использовании. Обычно программы на Си состоят из большого числа небольших функций, а не из немногих больших. Программу можно располагать в одном или нескольких исходных файлах. Эти файлы мож- но компилировать отдельно, а загружать вместе, в том числе и с ранее откомпилированными библиотечными функциями. Процесс загрузки здесь не рассматривается, поскольку он различен в разных системах. Объявление и определение функции - это та область, где стандартом ANSI в язык внесены самые существенные изменения. Как мы видели в главе 1, в описании функции теперь разрешено задавать типы аргумен- тов. Синтаксис определения функции также изменен, так что теперь объявления и определения функций соответствуют друг другу. Это по- зволяет компилятору обнаруживать намного больше ошибок, чем рань- ше. Кроме того, если типы аргументов соответствующим образом объяв- лены, то необходимые преобразования аргументов выполняются автомати- чески. Стандарт вносит ясность в правила, определяющие области видимос- ти имен; в частности, он требует, чтобы для каждого внешнего объекта было только одно определение. В нем обобщены средства инициализа- ции: теперь можно инициализировать автоматические массивы и струк- туры. 94 Глава 4. Функции и структура программы Улучшен также препроцессор Си. Он включает более широкий набор директив условной компиляции, предоставляет возможность из макро- аргументов генерировать строки в кавычках, а кроме того, содержит бо- лее совершенный механизм управления процессом макрорасширения. Основные сведения о функциях Начнем с того, что сконструируем программу, печатающую те строки вводимого текста, в которых содержится некоторый "образец", заданный в виде строки символов. программа представляет собой частный слу- чай функции системы UNIX.) Рассмотрим пример: в результате по- иска образца в строках текста Ah Love! could you and I with Fate conspire To grasp this sorry Scheme of Things entire, Would not we shatter it to bits — and then Re-mould it nearer to the Heart's Desire! мы получим Ah Love! could you and I with Fate conspire Would not we shatter it to bits — and then Re-mould it nearer to the Heart's Desire! Работа по поиску образца четко распадается на три этапа: while еще строка) f содержит напечатать ее Хотя три составляющие процесса поиска можно поместить в функ- цию main, же лучше сохранить приведенную структуру и каждую ее часть реализовать в виде отдельной функции. Легче иметь дело с тремя небольшими частями, чем с одной большой, поскольку, если несуществен- ные особенности реализации скрыты в функциях, вероятность их неже- лательного воздействия друг на друга минимальна. Кроме того, оформ- ленные в виде функций соответствующие части могут оказаться полез- ными и в других программах. Конструкция "while (существует еще строка)" реализована в getline (см. главу а фразу ее" можно записать с помощью гото- вой функции Таким образом, нам остается перевести на Си толь- ко то, что определяет, входит ли заданный образец в |