Программирование функций. Рекурсивные функции. Функции с переменным количеством параметров. Стандартные функции сортировки и поиска.
1.1. Определение функций.
Функция представляет собой поименованную последовательность инструкций, которая выполняет определенные действия. Функции используются для того, чтобы в теле программы не повторять одни и те же блоки инструкций несколько раз. Например, определим функцию, которая вычисляет сумму двух целых чисел.
int add ( int x, int y)
{
int z;
z = x + y;
return z;
}
Как видим, определение функции состоит из двух частей: заголовка и тела, которое представляет собой блок инструкций. Заголовок функции включает тип возвращаемого функцией значения, имя функции и список параметров. В нашем случае функция возвращает значение типа int, имеет имя add и два формальных параметра x и y. Для вычисления суммы внутри функции объявляется переменная z, которая не видна вне функции и поэтому называется локальной переменной. Полученное значение суммы возвращается в вызываемую программу инструкцией return.
Эта же функция может быть определена более кратко:
int add ( int x, int y)
{
return x + y;
}
То есть после ключевого слова return можно использовать выражение.
Если функции не возвращает никакого значения, то в языке С считается, что эта функция возвращает значение типа void, то есть пустое значение. В этом случае для выхода из функции используется инструкция return без выражения. Если выход из функции, не возвращающей значения, происходит как выход из блока, то в этом случае инструкцию return можно опустить. Например, следующая функция напечатает сумму двух чисел:
void print ( int x, int y)
{
printf (“x + y = %d\n”, x + y);
}
Если функция не имеет параметров, то вместо списка параметров пишется ключевое слово void, которое можно также опустить. Предпочтительнее использовать первый вариант, так как он явно указывает, что параметров нет. Например, следующая функция печатает сообщение:
void hello ( )
{
printf (“Hello.\n”);
}
Параметры функции можно рассматривать как локальные переменные, которые видны только в теле функции. Отсюда следует, что значения параметров можно изменять в теле функции. Например, можно написать следующую функцию:
int inc ( int n)
{
return ++n;
}
которая вернет значение n+1. Заметим, что функция
int inc ( int n)
{
return n++;
}
вернет значение n.
1.2. Прототипы функций.
Для предварительного описания функции может использоваться её объявление или прототип. В отличие от определения функции, прототип содержит только заголовок функции и не включает её тело. Прототипы функций используются в следующих случаях:
- функция определена в другом файле,
- функция определена после обращения к ней,
- функция определена в библиотеке функций, которая подключается к программе на этапе её компоновки или выполнения.
Например, функция сложения двух чисел имеет следующий прототип:
int add ( int x, int y);
При объявлении функции в списке параметров можно указывать только типы параметров, опуская их названия. Например, функцию add можно объявить следующим образом:
int add ( int, int);
Заметим, что объявление функции заканчивается символом ‘;’
1.3. Вызов функции.
Для вызова функции в программе пишется имя функции, за которым в скобках следует список аргументов, которые являются переменными и константами, определенными в программе. При этом происходит выполнение тела функции, в котором параметры заменяются значениями аргументов. Важно отметить, что тип аргумента должен соответствовать типу соответствующего параметра или допускать приведение к типу параметра. Кроме того, заметим, что функция должна быть объявлена или определена до своего вызова.
Ниже приведена программа, в которой вызывается функция сложения двух чисел.
#include <stdio.h>
int add (int x, int y)
{
return x + y;
}
int main()
{
int z;
// вызываем функцию
z = add (1, 2);
// печатаем результат
printf ("z = %d\n", z);
// можно вызвать функцию так
printf ("1 + 2 = %d\n", add(1, 2));
// можно также и так, но в этом случае непонятно зачем
add (1, 2);
return 1;
}
Если функция не имеет параметров, то при её вызове аргументы не указываются, но круглые скобки остаются. В следующей программе показан вызов функции hello.
#include <stdio.h>
void hello ( )
{
printf ("Hello.\n");
}
int main()
{
hello();
return 1;
}
В заключение этого параграфа сделаем два очень важных замечания. Во-первых, аргументы передаются в функцию по значению. То есть значения аргументов переписываются в параметры функции. Так как значение аргумента копируется в тело функции, то сам аргумент изменить в теле функции невозможно. Во-вторых, функция возвращает результат также по значению. То есть значение, вычисленное в инструкции return, копируется в переменную, которая определена в теле вызывающей программы и которой присваивается результат вычисления функции.
1.4. Рекурсивные функции.
В языке программирования С возможно определение рекурсивных функций. Например, определим рекурсивную функцию, которая вычисляет факториал натурального числа.
unsigned factorial(unsigned n)
{
if (!n)
return 1;
else
return n * factorial(n - 1);
}
1.5. Передача аргументов через указатели.
Для того чтобы функция могла изменить значения переменных, которые определены в программе, нужно передать в функцию указатели на эти переменные. Например, в следующей программе определена функция, которая увеличивает на единицу значение переменной, определенной в программе.
#include <stdio.h>
void inc(int* x)
{
++(*x);
}
int main()
{
int x = 1;
// вызываем функцию
inc(&x);
// печатаем результат
printf("x = %d\n", x);
return 1;
}
Отметим, что в этом случае в функцию должен передаваться адрес переменной, а не сама переменная.
1.6. Функции с переменным количеством параметров.
В языке программирования С допускается использование функций с переменным количеством параметров. В этом случае в конце списка параметров ставится многоточие (…). При этом предполагается, что в списке параметров присутствует хотя бы один параметр. Примерами функций с переменным количеством параметров являются стандартные функции scanf и printf. Например, можно определить функцию для сложения произвольного количества целых чисел следующим образом:
int add_num ( int n, …); // n - количество слагаемых
Для обработки функций с переменным количеством параметров используется переменная типа va_list и три макрокоманды
va_start ( va_list ap, last_arg); // инициализирует ap, где last_arg – имя последнего параметра
// в списке параметров функции перед многоточием
va_arg (va_list ap, type); // возвращает следующий аргумент типа type
va_end ( va_list ap); // обеспечивает правильную работу инструкции return в функции,
// которая использует эти макрокоманды
Эта переменная и макрокоманды определены в заголовочном файле <stdarg.h>.
Например, определенная ниже функция print распечатывает переменное количество целых чисел, которые передаются ей как параметры.
#include <stdio.h>
#include <stdarg.h>
int print(int n, ...)
{
va_list a;
// проверяем, есть ли параметры
if (n < 1)
{
printf("There are no numbers.\n");
return 0;
}
printf("Number of parameters = %d\n", n);
va_start(a, n); // инициализируем ‘a’ последним заданным аргументом
while (n) // распечатываем аргументы
{
printf("%d\n", va_arg(a, int));
--n;
}
va_end(a); // завершение продвижения по аргументам
return 1;
}
int main()
{
print(0);
print(1, 1);
print(2, 10, 20);
print(3, 100, 200, 300);
return 1;
}
1.7. Указатели на функции.
Имя функции является адресом этой функции в памяти. Язык программирования С позволяет определять указатели на функции. Например, следующая инструкция
int (*fp)(int x, int y);
объявляет переменную fp, которая является указателем на функцию. Причем эта функция должна иметь два параметра типа int и возвращать значение также типа int. В следующей программе функции сложения и вычитания двух чисел вызываются через указатель.
#include <stdio.h>
int add(int x, int y)
{
return x + y;
}
int sub(int x, int y)
{
return x - y;
}
int main()
{
int (*p)(int, int);
p = add;
// вызываем функцию через указатель
printf("1 + 2 = %d\n", (*p)(1, 2));
p = sub;
// можно вызвать функцию и так
printf("1 - 2 = %d\n", p(1, 2));
return 1;
}
Так как указателю на функцию могут присваиваться адреса различных функций при условии совпадения типа параметров и типа возвращаемого значения, то указатели на функции часто называют функторами.
1.8. Вызов стандартных функций сортировки и поиска.
На практике при работе с данными часто встречаются задачи сортировки массива и поиска элементов в отсортированном массиве. Причем массивы могут иметь разные типы. Чтобы облегчить решение таких задач, в стандартной библиотеке языка программирования С есть специальные функции qsort и bsearch, которые предназначены для решения этих задач.
Функция qsort выполняют сортировку массива, элементы которого имеют произвольный тип. Эта функция имеет следующий прототип:
void qsort ( void *base, size_t nelem, size_t size, int (*cmp) (const void *e1, const void *e2));
который описан в заголовочном файле <stdlib.h>. Кратко опишем назначение параметров этой функции:
base адрес массива,
nelem количество элементов в массиве,
size длина элемента в массиве,
comp указатель на функцию сравнения, которая возвращает:
- отрицательное число, если элемент e1 меньше элемента e2,
- 0, если элемент e1 равен элементу e2,
- положительное число, если элемент e1 больше элемента e2.
Функция qsort реализует «быстрый алгоритм» сортировки массивов.
Функция bsearch выполняет бинарный поиск элемента в отсортированном массиве. Эта функция имеет следующий прототип:
void* bsearch (const void *key, const void *base,
size_t nelem, size_t size, int (*cmp) (const void *ck, const void *ce);
который также описан в заголовочном файле <stdlib.h>. Первый параметр key этой функции является указателем на элемент, который нужно найти. Остальные параметры повторяют параметры функции qsort. В случае успешного завершения поиска функция bsearch возвращает адрес найденного элемента, а в случае неудачи NULL.
В следующей программе показан пример использования функций qsort и bsearch для сортировки целочисленного массива и дальнейшего поиска элементов в этом отсортированном массиве.
#include <stdio.h>
#include <stdlib.h>
// функция для сравнения элементов массива
int comp_int(const int* e1, const int* e2)
{
return (*e1 < *e2) ? -1 : ((*e1 == *e2) ? 0 : 1);
}
// программа сортировки элементов массива и поиска целого числа
int main()
{
int n; // размер массива
int* a; // массив
int i; // индекс
int k; // число для поиска
int* s; // адрес найденного числа
printf("Input an array size: ");
scanf("%d", &n);
a = (int*)malloc(n*sizeof(int));
// вводим массив
printf("Input elements: ");
for (i = 0; i < n; ++i)
scanf("%d", &a[i]);
// сортируем массив
qsort(a, n, sizeof(int),
(int (*)(const void*, const void*))comp_int);
// выводим отсортированный массив
printf("The sorted array: ");
for (i = 0; i < n; ++i)
printf("%d ", a[i]);
printf("\n");
// вводим число для поиска
printf("Input a number to search.\n>");
scanf("%d", &k);
// ищем это число в отсортированном массиве
if(!(s = (int*) bsearch(&k, a, n, sizeof(int),
(int (*)(const void*, const void*))comp_int)))
printf("There is no such an integer.\n");
else
printf("The integer index = %d.\n", s-a);
free(a);
return 1;
}