Изучаем Cи (2001) [rus]
.pdfmain() возвращает какое-то значение, и мы отступали до сих пор от стандарта языка, не указывая его тип левее «main». Стандарт говорит нам, что функция main() возвращает значение int, поэтому правильнее будет писать
int main(){
…
return 0;
}
Функция main() — главная в программе. И она возвращает значение тому, кто главнее, то есть запустившей ее процедуре операционной системы. Далее во всех программах мы будем писать return 0; не задумываясь о судьбе возвращенного значения — просто потому, что это правильно и одобрено стандартом.
Функции с длинными руками
Только что мы видели, как функция change() (см. листинг 4.6 в предыдущем разделе), силится «схватить» переменную i, но — руки коротки! Все, чем располагает функция — лишь копия передаваемой переменной — сама переменная, живущая в основной программе, ей недоступна.
Но давайте подумаем, что будет, если передать функции не переменную, а указатель на нее. Поскольку функция получает копию переменной, она не может повлиять на сам указатель. Но она может записать все, что угодно туда, куда он направлен.
В листинге 4.7 показана программа, которая, как и в предыдущем пункте, пытается изменить переменную i.
Листинг 4.7.
#include <stdio.h>
void change(int *);
int main(){
84
int i;
i=2;
change(&i);
printf("вне= %d\n",i);
return 0;
}
void change(int *a){
*a += 3;
}
На этот раз успешно. Объявление (прототип) функции void change(int *) показывает, что она принимает указатель на переменную int. Указатель (вернее, его копия) передается функции в строчке change(&i). Внутри функции копия указателя называется a, и теперь раскрытие ссылки *a позволяет как угодно изменить переменную, на которую ссылается указатель a. Строчка *a += 3 прибавляет к переменной i основной программы тройку. Теперь после вызова функции change(&i) функция printf()выводит на экран пятерку, а не двойку.
Переданный указатель похож на веревочку, которая связывает две функции (вызвавшую и вызванную). Дерни за веревочку,
— откроется дверка к переменной, и вызванная функция сможет ее изменить. Впрочем, она может изменить и соседнюю переменную, если увеличит указатель на единицу. Здесь таится большая опасность, потому что функция ничего не знает о внешних переменных, в частности, ей не известно, указывает ли (a+1) на что-то действительно существующее. Нечаянно изменив указатель и записав что-то по новому адресу, она может испортить данные или всю программу.
Как мы уже поняли, передавать указатели опасно, но иногда без этого не обойтись. Например, в функциях, которые вводят данные с клавиатуры. Одна из таких функций — scanf() — делает работу, противоположную работе функции printf().
85
Если printf()выводит на экране переменные, то scanf() вводит их с клавиатуры и отображает на экране.
В листинге 4.8 показана программа, которая складывает два вводимых с клавиатуры числа.
Листинг 4.8
#include <stdio.h>
int main(){
int a,b;
scanf("%d%d", &a,&b);
printf("\n%d\n", a+b);
return 0;
}
Собственно вводом занимается функция scanf("%d%d", &a,&b), очень похожая на printf(). В ней тоже есть спецификация формата "%d%d", говорящая о том, что будут введены два целых числа. Но, в отличие от printf(), ей передаются не сами переменные, которые функция не в состоянии изменить, а указатели на них.
Чтобы получить сумму чисел, нужно после запуска программы ввести с клавиатуры первое число, нажать Enter , затем ввести второе число, и после нажатия Enter функция printf() покажет на экране сумму. Можно ввести числа и на одной строке, для чего печатается одно число, пробел, второе число и нажимается Enter.
Как мы уже поняли, указатель в руках функции становится опасным: с его помощью она может дотянуться не только до переменной, на которую он указывает, но и до чего угодно. «Укоротить руки» функции способно словечко const (от английского константа, постоянная величина).
Если функцию change(), показанную в листинге 4.10, записать как
void change(const int *a){
86
*a += 3;
}
компилятор выдаст сообщение об ошибке: Cannot modify a const object in function change. Это значит, что объект, на который ссылается указатель, постоянен и не может быть изменен.
Конечно, в функции change(), созданной именно для того, чтобы менять переменную, словечко const использовать нельзя. Но бывают функции, которым нужно только читать переменную, зная указатель на нее. Здесь слово const уместно и делает программу надежней и безопасней.
Рекурсия или «раз, два, три»
Не следует надолго уходить в себя, так как близкие нуждаются в общении с вами.
Из гороскопа.
Начнем этот раздел с простой задачки: вывести на экран три числа: 1, 2, 3. Есть много способов ее решения. Один из самых очевидных показан в листинге 4.9:
Листинг 4.9
#include <stdio.h>
int main()
{
int i;
for(i=1;i<4;i++)
printf("%d\n",i);
return 0;
}
Эта программа, успешно решает одну простую задачу. Приспособить ее к чему-то еще (кроме, быть может, вывода на экран многих идущих подряд чисел) невозможно — слишком
87
уж она буквальна и прямолинейна. Чтобы будить мысль и куда-то вести, ей, очевидно, недостает той доли безумия, которая есть в программе, показанной в листинге 4.10.
Листинг 4.10
#include <stdio.h> void CntTo3(int); void CntTo2(int); void CntTo1(int); int main()
{
int n; CntTo3(3); return 0;
}
void CntTo3(int p)
{
CntTo2(p-1); printf("%d\n",p);
}
void CntTo2(int p)
{
CntTo1(p-1); printf("%d\n",p);
}
void CntTo1(int p)
{
printf("%d\n",p);
88
}
Эта программа тоже выводит на экран три идущих подряд числа, но делает это совсем по-другому. Если посмотреть устройство функции CntTo3(p), решающей задачу вывода чисел 1, 2, 3, то окажется, что она разбивает задачу на две части:
1.Вывести числа 1, 2 (функция CntTo2())
2.Вывести число 3.
В свою очередь, функция CntTo2() использует такое же разбиение задачи:
1.Вывести число 1 (функция CntTo1())
2.Вывести число 2.
И только функции CntTo1() уже некуда отступать. Она выводит на экран единицу и возвращает управление функции CntTo2(), которая в свою очередь показывает двойку (ведь именно таково значение переданного ей аргумента p) и возвращает управление функции CntTo3(), которая выводит тройку — значение переданного ей аргумента p, после чего CntTo3() передает управление вызвавшей ее функции main(), и программа благополучно завершается.
Задача 4.6 Напишите программу, которая складывает три числа: 1+2+3 — примерно такую, как в листинге 4.10.
Теперь можно немножко обобщить нашу задачу. Предположим, необходимо вывести на экран n подряд идущих чисел от 1 до n. Эту задачу можно разбить на две:
1.Вывести числа от 1 до n-1
2.Вывести n
Точно так же задача вывода чисел от 1 до n-1 разбивается на две:
1.Вывести числа от 1 до n-2
2.Вывести n-1
89
и так далее, вплоть до единицы.
Такой способ решения задачи называется рекурсией. По сути, рекурсия — частный случай стратегии «разделяй и властвуй». Если от задачи можно «отколоть» кусочек, то нужно это сделать, потому что оставшаяся задача будет проще.
Но как решать рекурсивные задачи на компьютере? Приведенный способ (см. листинг 4.10) годится для вывода трех чисел, но для вывода сотни он слишком громоздок и попросту глуп.
Но давайте все-таки представим, как выглядела бы программа, показанная в листинге 4.10, если бы ее задачей было вывести не три подряд идущих числа, а сотню. Очевидно, такая программа принципиально мало отличалась бы от той, что выводит три числа. Только вместо трех функций в ней было бы сто!
Но вот что интересно: 99 из этих ста функций выполняли бы
абсолютно одинаковые действия:
void CntTo100(int p)
{
CntTo99(p-1); printf("%d\n",p);
}
void CntTo99(int p)
{
CntTo98(p-1); printf("%d\n",p);
}
…
void CntTo2(int p)
{
90
CntTo1(p-1);
printf("%d\n",p);
}
и только последняя, оказавшись «крайней» просто выводила бы на экран единицу!
То, что все эти 99 функций по сути, отличаются только названием, наводит на мысль: а нельзя ли записать это в виде одной единственной функции, которая 99 раз обращается сама к себе?
И такая возможность действительно есть, причем у любой функции, даже у main(). Функции, которые вызывают сами себя, так же как задачи, для решения которых они созданы, называются рекурсивными. Глядя на листинг 4.10, легко написать программу, использующую рекурсивную функцию для вывода идущих подряд цифр. Выглядеть она может так, как показано в листинге 4.11.
Листинг 4.11
#include <stdio.h> void CntTo(int); int main()
{
int n; CntTo(3); return 0;
}
void CntTo(int n)
{
if(n > 0){ CntTo(n-1); printf("%d\n",n);
91
}
}
Используемая здесь функция CntTo()может вывести на экран любую последовательность чисел, но для простоты мы по-прежнему будем выводить «1,2,3».
При первом обращении к функции CntTo()значение аргумента равно 3, и так как выражение (n > 0) истинно, CntTo() вызовется еще раз, но уже с аргументом n-1, равным двойке. Далее, раз двойка больше нуля, то CntTo() вызовется в третий раз, уже с единичным аргументом. Единица тоже больше нуля, и CntTo() будет вызвана в четвертый раз. На этот раз n равно 0, условие (n>0) не выполнится, и следующего вызова CntTo() не будет. Вместо вызова, произойдет возврат. Но куда? Чтобы понять это, полезно еще раз посмотреть цепочку функций CntTo3, CntTo2, CntTo1 в листинге 4.10., которая показывает нам, что же на самом деле творится при рекурсивном вызове.
Происходит странное: вызывается функция, которая называется так же, как и вызывающая, но на самом деле она другая. У нее свои переменные, независимые от переменных вызвавшей функции. Переменная, объявленная в вызывающей функции, никак не связана с одноименной переменной в вызванной функции. И когда управление передается вызвавшей функции, мы имеем дело со значением переменной именно в этой функции.
В нашем случае после четвертого вызова, когда n было равно нулю, функция возвращается к инструкции, следующей непосредственно за вызовом, то есть к printf("%d\n",n) Причем, n в данном случае — не какое-то абстрактное число, а значение параметра n в третьей копии CntTo(), то есть единица. Показав на экране «1», третья копия CntTo() вернется к вызвавшей ее второй копии, опять в то место, которое следует непосредственно за вызовом, то есть снова к printf("%d\n",n), но на этот раз n будет равно двум. Наконец, при третьем возврате будет выведена тройка.
92
Рис. 4.6. Закат и восход рекурсивной функции
На рис. 4.6 показано, как функция CntTo() «углубляется в себя». Если бы не условие if(n >0){}, функция ушла бы в себя и не вернулась. Поскольку вызов каждой копии функции требует памяти для хранения переменных, то после исчерпания памяти, программа должна была бы аварийно завершиться. Инструкция if() разрешает функции вызвать себя только четыре раза. С каждым разом функция уходит все глубже в себя, она «закатывается». Когда n становится равным нулю, начинается «восход». Функция возвращается во все свои более ранние копии, пока не высветятся все три числа. Затем она взойдет еще на одну ступеньку — и окажется в функции
main().
Завершим этот раздел еще одним примером рекурсивной функции, на этот раз — складывающей все числа от единицы до ста. Задача сложения идущих подряд чисел может быть решена в два этапа: сумма чисел от 1 до n равна n плюс сумма от 1 до n-1. Эта последняя сумма равна n-1 плюс сумма чисел от 1 до n-2 — и так до самой последней суммы от единицы до единицы. Программа, которая все это делает, показана в листинге 4.12.
Листинг 4.12.
#include <stdio.h>
int sum(int);
int main(){
int i;
printf("%d\n",sum(100));
return 0;
93