Брайан Керниган - Язык программирования Си. Издание 3-е, исправленное

• Название: Язык программирования Си. Издание 3-е, исправленное
• Автор: Брайан Керниган
• Издательство: Невский Диалект
• Жанр: Программирование
• Год: 2001
• ISBN: 0-13-110362-8

Книга широко известных авторов, разработчиков языка Си, переработанная и дополненная с учетом стандарта ANSI для языка Си, 2-е английское издание которой вышло в 1988 году, давно стала классикой для всех изучающих и/или использующих как Си, так и Си++. Русский перевод этой книги впервые был выпущен изд- вом "Финансы и статистика" в 1992 г. и с тех пор пользуется неизменным спросом читателей.

Для настоящего третьего русского издания перевод заново сверен с оригиналом, в него внесены некоторые поправки, учитывающие устоявшиеся за прошедшие годы изменения в терминологии, а так же учтены замечания, размещенные автором на странице http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html.

Для программистов, преподавателей и студентов.

Издание подготовлено при участии издательства "Финансы и статистика"

---

В главе 1 мы написали программу, подсчитывающую число вхождений в текст каждой цифры, символов-разделителей (пробелов, табуляций и новых строк) и всех остальных символов. В ней мы использовали последовательность if…else if…else. Теперь приведем вариант этой программы с переключателем switch:

#include ‹stdio.h›

main() /* подсчет цифр, символов-разделителей и прочих символов */

{

 int c, i, nwhite, nother, ndigit[10];

 nwhite = nother = 0;

 for (i = 0; i ‹ 10; i++)

  ndigit[i] = 0;

 while ((с = getchar()) != EOF) {

  switch (c) {

  case '0': case '1': case '2': case '3': case '4':

  case '5': case '6': case '7': case '8': case '9':

   ndigit[c - '0']++;

   break;

  case ' ':

  case '\n':

  case '\t':

   nwhite++;

   break;

  default:

   nother++;

   break;

  }

 }

 printf("цифр =");

 for(i = 0; i ‹ 10; i++)

  printf (" %d", ndigit[i]);

 printf(", символов-разделителей = %d, прочих = %d\n",

  nwhite, nother);

 return 0;

}

Инструкция break вызывает немедленный выход из переключателя switch. Поскольку выбор ветви case реализуется как переход на метку, то после выполнения одной ветви case, если ничего не предпринять, программа провалится вниз на следующую ветвь. Инструкции break и return - наиболее распространенные средства выхода из переключателя. Инструкция break используется также для принудительного выхода из циклов while, for и do-while (мы еще поговорим об этом чуть позже).

"Сквозное" выполнение ветвей case вызывает смешанные чувства. С одной стороны, это хорошо, поскольку позволяет несколько ветвей case объединить в одну, как мы и поступили с цифрами в нашем примере. Но с другой - это означает, что в конце почти каждой ветви придется ставить break, чтобы избежать перехода к следующей. Последовательный проход по ветвям - вещь ненадежная, это чревато ошибками, особенно при изменении программы. За исключением случая с несколькими метками для одного вычисления, старайтесь по возможности реже пользоваться сквозным проходом, но если уж вы его применяете, обязательно комментируйте эти особые места.

Добрый вам совет: даже в конце последней ветви (после default в нашем примере) помещайте инструкцию break, хотя с точки зрения логики в ней нет никакой необходимости. Но эта маленькая предосторожность спасет вас, когда однажды вам потребуется добавить в конец еще одну ветвь case.

Упражнение 3.2. Напишите функцию escape (s,t), которая при копировании текста из t в s преобразует такие символы, как новая строка и табуляция в "видимые последовательности символов" (вроде \n и \t). Используйте инструкцию switch. Напишите функцию, выполняющую обратное преобразование эскейп- последовательностей в настоящие символы.

3.5 Циклы while и for

Мы уже встречались с циклами while и for. В цикле

while (выражение)

 инструкция

вычисляется выражение. Если его значение отлично от нуля, то выполняется инструкция, и вычисление выражения повторяется. Этот цикл продолжается до тех пор, пока выражение не станет равным нулю, после чего вычисления продолжатся с точки, расположенной сразу за инструкцией.

Инструкция for

for (выр1; выр2; выр3)

 инструкция

эквивалентна конструкции

выр1;

while (выр2) {

 инструкция

 выр3;

}

если не считать отличий в поведении инструкции continue, речь о которой пойдет в параграфе 3.7.

С точки зрения грамматики три компоненты цикла for представляют собой произвольные выражения, но чаще выр1 и выр3 - это присваивания или вызовы функций, а выр2 - выражение отношения. Любое из этих трех выражений может отсутствовать, но точку с запятой опускать нельзя. При отсутствии выр1, или выр3 считается, что их просто нет в конструкции цикла; при отсутствии выр2, предполагается, что его значение как бы всегда истинно. Например,

for (;;) {

 :

}

есть "бесконечный" цикл, выполнение которого, вероятно, прерывается каким-то другим способом, например с помощью инструкций break или return. Какой цикл выбрать: while или for - это дело вкуса. Так, в

while ((c = getchar()) == ' ' || c == '\n' || c == '\t')

 ; /* обойти символы-разделители */

нет ни инициализации, ни пересчета параметра, поэтому здесь больше подходит while.

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

for (i = 0; i ‹ n; i++)

 …

Это похоже на DO-циклы в Фортране и for-циклы в Паскале. Сходство, однако, не вполне точное, так как в Си индекс и его предельное значение могут изменяться внутри цикла, и значение индекса i после выхода из цикла всегда определено. Поскольку три компонента цикла могут быть произвольными выражениями, организация for-циклов не ограничивается только случаем арифметической прогрессии. Однако включать в заголовок цикла вычисления, не имеющие отношения к инициализации и инкрементированию, считается плохим стилем. Заголовок лучше оставить только для операций управления циклом.

В качестве более внушительного примера приведем другую версию программы atoi, выполняющей преобразование строки в ее числовой эквивалент. Это более общая версия по сравнению с рассмотренной в главе 2, в том смысле, что она игнорирует левые символы-разделители (если они есть) и должным образом реагирует на знаки + и -, которые могут стоять перед цифрами. (В главе 4 будет рассмотрен вариант atof, который осуществляет подобное преобразование для чисел с плавающей точкой.)

Структура программы отражает вид вводимой информации:

игнорировать символы-разделители, если они есть

получить знак, если он есть

взять целую часть и преобразовать ее

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

#include ‹ctype.h›

/* atoi: преобразование s в целое число; версия 2 */

int atoi(char s[])

{

 int i, n, sign;

 /* игнорировать символы-разделители */

 for (i = 0; isspace(s[i]); i++)

  ;

 sign = (s[i] == '-') ? -1 : 1;

 if (s[i] == '+' || s[i] == '-') /* пропуск знака */

  i++;

 for (n = 0; isdigit(s[i]); i++)

 n = 10 * n + (s[i] - '0');

 return sign * n;

}

Заметим, что в стандартной библиотеке имеется более совершенная функция преобразования строки в длинное целое (long int) - функция strtol (см. параграф 5 приложения B).

Преимущества, которые дает централизация управления циклом, становятся еще более очевидными, когда несколько циклов вложены друг в друга. Проиллюстрируем их на примере сортировки массива целых чисел методом Шелла, предложенным им в 1959 г. Основная идея этого алгоритма в том, что на ранних стадиях сравниваются далеко отстоящие друг от друга, а не соседние элементы, как в обычных перестановочных сортировках. Это приводит к быстрому устранению массовой неупорядоченности, благодаря чему на более поздней стадии остается меньше работы. Интервал между сравниваемыми элементами постепенно уменьшается до единицы, и в этот момент сортировка сводится к обычным перестановкам соседних элементов. Программа shellsort имеет следующий вид:

/* shellsort: сортируются v[0]… v[n-1] в возрастающем порядке */

void shellsort (int v[], int n)

{

 int gap, i, j, temp;

 for (gap = n/2; gap › 0; gap /= 2)

  for (i = gap; i ‹ n; i++)

   for (j = i - gap; j ›= 0 && v[j] › v[j+gap]; j -= gap) {

    temp = v[j];

    v[j] = v[j + gap];

    v[j + gap] = temp;

   }

}

Здесь использованы три вложенных друг в друга цикла. Внешний управляет интервалом gap между сравниваемыми элементами, сокращая его путем деления пополам от n/2 до нуля. Средний цикл перебирает элементы. Внутренний - сравнивает каждую пару элементов, отстоящих друг от друга на расстоянии gap, и переставляет элементы в неупорядоченных парах. Так как gap обязательно сведется к единице, все элементы в конечном счете будут упорядочены. Обратите внимание на то, что универсальность цикла for позволяет сделать внешний цикл по форме похожим на другие, хотя он и не является арифметической прогрессией.