Тема 7. Процедурное, логическое, функциональное и объектно-ориентированное программирование
Основные отличия, достоинства, недостатки, перспективы развития. Основные парадигмы программирования. Базовые методы программирования.
Функции. Процедуры и функции как средства описания укрупненных операции обработки данных, способы подстановки параметров. Стандартные функции и процедуры.
Функция - это совокупность объявлений и операторов, обычно предназначенная для решения определенной задачи. Каждая функция должна иметь имя, которое используется для ее объявления, определения и вызова. В любой программе на СИ должна быть функция с именем main (главная функция), именно с этой функции, в каком бы месте программы она не находилась, начинается выполнение программы.
При вызове функции ей при помощи аргументов (формальных параметров) могут быть переданы некоторые значения (фактические параметры), используемые во время выполнения функции. Функция может возвращать некоторое (одно !) значение. Это возвращаемое значение и есть результат выполнения функции, который при выполнении программы подставляется в точку вызова функции, где бы этот вызов ни встретился. Допускается также использовать функции не имеющие аргументов и функции не возвращающие никаких значений. Действие таких функций может состоять, например, в изменении значений некоторых переменных, выводе на печать некоторых текстов и т.п.
С функциямив связаны три понятия - определение функции (описание действий, выполняемых функцией), объявление функции (задание формы обращения к функции) и ее вызов.
Определение функции задает тип возвращаемого значения, имя функции, типы и число формальных параметров, а также объявления переменных и операторы, называемые телом функции, и определяющие действие функции. В определении функции также может быть задан класс памяти.
int rus (unsigned char r) {
if (r>='А' && c<=' ')
return 1;
else
return 0;
}
В данном примере определена функция с именем rus, имеющая один параметр с именем r и типом unsigned char. Функция возвращает целое значение, равное 1, если параметр функции является буквой русского алфавита, или 0 в противном случае.
В СИ нет требования, чтобы определение функции обязательно предшествовало ее вызову. Определения используемых функций могут следовать за определением функции main, перед ним, или находится в другом файле. Однако для того, чтобы компилятор мог осуществить проверку соответствия типов передаваемых фактических параметров типам формальных параметров до вызова функции нужно поместить объявление (прототип) функции. Объявление функции имеет такой же вид, что и определение функции, с той лишь разницей, что тело функции отсутствует, и имена формальных параметров тоже могут быть опущены. Для функции, определенной в последнем примере, прототип может иметь вид
int rus (unsigned char r); или rus (unsigned char);
В программах на СИ широко используются, так называемые, библиотечные функции, т.е. функции предварительно разработанные и записанные в библиотеки. Прототипы библиотечных функций находятся в специальных заголовочных файлах, поставляемых вместе с библиотеками в составе систем программирования, и включаются в программу с помощью директивы #include.
Если объявление функции не задано, то по умолчанию строится прототип функции на основе анализа первой ссылки на функцию, будь то вызов функции или определение. Однако такой прототип не всегда согласуется с последующим определением или вызовом функции. Рекомендуется всегда задавать прототип функции. Это позволит компилятору либо выдавать диагностические сообщения, при неправильном использовании функции, либо корректным образом регулировать несоответствие аргументов, устанавливаемое при выполнении программы.
Определение функции имеет следующую форму:
[спецификатор-класса-памяти] [спецификатор-типа]
имя-функции ([список-формальных-параметров]) {
тело-функции
}
Необязательный спецификатор-класса-памяти задает класс памяти функции, который может быть static или extern.
Спецификатор-типа функции задает тип возвращаемого значения. Если спецификатор-типа не задан, то предполагается, что функция возвращает значение типа int. Функция не может возвращать массив или функцию, но может возвращать указатель на любой тип, в том числе и на массив и на функцию. Тип возвращаемого значения, задаваемый в определении функции, должен соответствовать типу в объявлении этой функции. Функция возвращает значение, если ее выполнение заканчивается оператором return, содержащим некоторое выражение. Указанное выражение вычисляется, преобразуется, если необходимо, к типу возвращаемого значения и возвращается в точку вызова функции в качестве результата. Если оператор return не содержит выражения или выполнение функции завершается после выполнения последнего ее оператора (без выполнения оператора return), то возвращаемое значение не определено. Для функций, не использующих возвращаемое значение, должен быть использован тип void, указывающий на отсутствие возвращаемого значения. Если функция определена как функция, возвращающая некоторое значение, а в операторе return при выходе из нее отсутствует выражение, то поведение вызывающей функции после передачи ей управления может быть непредсказуемым.
Список-формальных-параметров - это последовател-ть объявлений формальных параметров, разделенная запятыми. Формальные параметры - это переменные, используемые внутри тела функции и получающие значение при вызове функции путем копирования в них значений соответствующих фактических параметров. Список-формальных-параметров может заканчиваться запятой (,) или запятой с многоточием (,...), это означает, что число аргументов функции переменно. Однако предполагается, что функция имеет, по крайней мере, столько обязательных аргументов, сколько формальных параметров задано перед последней запятой в списке параметров. Такой функции может быть передано большее число аргументов, но над дополнительными аргументами не проводится контроль типов. Если функция не использует параметров, то наличие круглых скобок обязательно, а вместо списка параметров рекомендуется указать слово void. Порядок и типы формальных параметров должны быть одинаковыми в определении функции и во всех ее объявлениях. Типы фактических параметров при вызове функции должны быть совместимы с типами соответствующих формальных параметров. Для формального параметра можно задавать класс памяти register, при этом для величин типа int спецификатор типа можно опустить.
Идентификаторы формальных параметров используются в теле функции в качестве ссылок на переданные значения. Эти идентификаторы не могут быть переопределены в блоке, образующем тело функции, но могут быть переопределены во внутреннем блоке внутри тела функции.
При передаче параметров в функцию, если необходимо, выполняются обычные арифметические преобразования для каждого формального параметра и каждого фактического параметра независимо. После преобразования формальный параметр не может быть короче чем int, т.е. объявление формального параметра с типом char равносильно его объявлению с типом int. А параметры, представляющие собой действительные числа, имеют тип double.
Преобразованный тип каждого формального параметра определяет, как интерпретируются аргументы, помещаемые при вызове функции в стек. Несоответствие типов фактических аргументов и формальных параметров может быть причиной неверной интерпретации.
Тело функции - это составной оператор, содержащий операторы, определяющие действие функции. Все переменные, объявленные в теле функции без указания класса памяти, имеют класс памяти auto, т.е. они являются локальными. При вызове функции локальным переменным отводится память в стеке и производится их инициализация. Управление передается первому оператору тела функции и начинается выполнение функции, которое продолжается до тех пор, пока не встретится оператор return или последний оператор тела функции. Управление при этом возвращается в точку, следующую за точкой вызова, а локальные переменные становятся недоступными. При новом вызове функции для локальных переменных память распределяется вновь, и поэтому старые значения локальных переменных теряются.
Параметры функции передаются по значению и могут рассматриваться как локальные переменные, для которых выделяется память при вызове функции и производится инициализация значениями фактических параметров. При выходе из функции значения этих переменных теряются. Поскольку передача параметров происходит по значению, в теле функции нельзя изменить значения переменных в вызывающей функции, являющихся фактическими параметрами. Однако, если в качестве параметра передать указатель на некоторую переменную, то используя операцию разадресации можно изменить значение этой переменной.
Неправильное использование параметров:
void change (int x, int y) {
int k=x;
x=y;
y=k;
}
В данной функции значения переменных x и y, являющихся формальными параметрами, меняются местами, но поскольку эти переменные существуют только внутри функции change, значения фактических параметров, используемых при вызове функции, останутся неизменными. Для того чтобы менялись местами значения фактических аргументов можно использовать функцию приведенную в следующем примере.
Правильное использование параметров:
void change (int *x, int *y) {
int k=*x;
*x=*y;
*y=k;
}
При вызове такой функции в качестве фактических параметров должны быть использованы не значения переменных, а их адреса
change (&a,&b);
Вызов функции имеет следующий формат:
адресное-выражение ([список-выражений])
Функции с переменным кол-вом параметров. Подставляемые (инлайн-) функции.Перегрузка функций.
При объявлении функций имеется возможность задать значения аргументов по умолчанию. Например:
double expnt (double x, unsigned int e = 2) {
double result = 1;
for (int i = 0; i < e; i++)
result *= x;
return result;
}
int main() {
double y = expnt(3.14);
double x = expnt(2.9, 5);
return 1;
}
Необязательных аргументов может быть несколько. Если указан необязательный аргумент, то либо он должен быть последним в прототипе, либо все аргументы после него должны также иметь умолчания.
Если функция определена как inline, компилятор будет подставлять тело в функции в каждой точке ее вызова, вместо организации команд передачи управления функции и возврата из нее.
Допустимо иметь несколько функций с одним и тем же именем (перегрузкой имен функций), потому что функции различаются не только по именам, но и по типам аргументов. Если в дополнение к определенной выше функции sum мы определим еще одну функцию с тем же именем
double sum(double a, double b, double c) {
double result;
result = a + b + c;
return result;
}
это будет считаться новой функцией.
Важен не только тип аргументов, но и их количество. Можно определить функцию sum, суммирующую четыре аргумента:
int sum(int x1, int x2, int x3, int x4) {
return x1 + x2 + x3 + x4;
}
Рекурсивные алгоритмы и средства их представления в языке Си, особенности исполнения рекурсивных подпрограмм. Рекурсивные функции. Программирование рекурсивных алгоритмов.
Рекурсивные алгоритмы – это алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения.
У попа была собака, он ее любил, она съела кусок мяса, ...
Этот глист страдал глистами, которые страдали глистами сами.
15 негритят пошли купаться в море, ...
Покраска забора и очистка капусты как примеры рекурсии. Факториал, числа Фибоначчи, обход дерева.
Любая функция в программе на языке СИ может быть вызвана рекурсивно, т.е. она может вызывать саму себя. Компилятор допускает любое число рекурсивных вызовов. При каждом вызове для формальных параметров и переменных с классом памяти auto и register выделяется новая область памяти, так что их значения из предыдущих вызовов не теряются, но в каждый момент времени доступны только значения текущего вызова. Переменные, объявленные с классом памяти static, не требуют выделения новой области памяти при каждом рекурсивном вызове функции и их значения доступны в течение всего времени выполнения программы.
Классический пример рекурсии - это математическое определение факториала n!
n! = 1 при n=0;
n*(n-1)! при n>1
Рекурсивное вычисление факториала имеет вид:
long fakt(int n) {
return ( (n==1) ? 1 : n*fakt(n-1) );
}
Число рекурсивных вызовов функций ограничивается ресурсом памяти компьютера и при слишком большом числе рекурсивных вызовов может произойти переполнение стека.
Рассмотрим головоломку Ханойская башня. Есть одна пирамидка с дисками и два пустых стержня. Перенести пирамидку на другой стержень по одному диску и чтобы сверху маленьких дисков никогда не было дисков большего размера. Решение: Перенести верхний диск на один стержень, потом оставшуюся укороченную пирамидку на другой стержень и свержу положить первый диск. Укороченная пирамидка из одного диска переносится элементарно.
int move(int N, int n1, int n2, int n3)
//n1 – откуда, n2 – куда, n3 – вспомог. Стержень
if (N=1) {
move1(n1, n2)
} else {
move(N-1, n1, n3, n2)
move1(n1, n2)
move(N-1, n3, n2, n1)
}
}