В качестве более внушительного примера приведем другую версию программы 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 обязательно сведется к единице, все элементы в конечном счете будут упорядочены. Обратите внимание на то, что универсальность цикла