книги / Программирование на языке Си
..pdf252 |
Программирование на языке Си |
позволяет, во-первых, получить значение очередного (сначала первого) фактического параметра типа type. Вторая задача мак рокоманды va_arg() - заменить значение указателя factor на адрес следующего фактического параметра в списке. Теперь, узнав каким-то образом тип, например typel, этого следующего параметра, можно вновь обратиться к макросу:
va_arg (factor, typel)
Это обращение позволяет получить значение следующего фактического параметра и переадресовать указатель factor на фактический параметр, стоящий за ним в списке, и т.д.
Примечание. Реализация компиляторов Turbo C++ и Borland C++ запрещает использовать с макрокомандой va_arg( ) ти пы char, unsigned char, float. Данные типа char и unsigned char преобразуются при передаче в функцию с переменным количеством параметров в тип int, а данные типа float при водятся к типу double. Именно поэтому при выводе с помо щью printf() данных как типа float, так и типа double используются одни и те же спецификаторы % f и %е. Вывод данных типа char и unsigned char можно выполнять и по спецификации %d, и по спецификации %с.
Макрокоманда va_end() предназначена для организации корректного возврата из функции с переменным списком пара метров. Ее единственным параметром должен быть указатель типа va_list, который использовался в функции для перебора параметров. Таким образом, для наших иллюстраций вызов макрокоманды должен иметь вид:
va_end (factor);
Макрокоманда va_end() должна быть вызвана после того, как функция обработает весь список фактических параметров.
Макрокоманда va_end() обычно модифицирует свой аргу мент (указатель типа va_list), и поэтому его нельзя будет по вторно использовать без предварительного вызова макроса va_start().
Глава 5. Функции |
253 |
Примеры функций с переменным количеством парамет ров. Для иллюстрации особенностей использования описанных макросов рассмотрим функцию, формирующую в динамической памяти массив из*элементов типа double. Количество элементов определяется значением первого обязательного параметра функции, имеющего тип int. Значения параметров массива пе редаются в функцию с помощью переменного числа необяза тельных параметров типа double. Текст функции вместе с основной программой, из которой выполняется ее вызов:
#±nclude <stdarg.h> /* Для макросредств */ #include <stdlib.h> /* Для функции calloc( ) */ double * set_array (int k, ...)
{
int ^ ;
va_list par; /* Вспомогательный указатель */ double * rez; /* Указатель на результат */ rez=calloc(k,sizeof(double));
if (rez == NULL) return NULL;
va_start (par, k); /* "Настройка" указателя */ /* Цикл "чтения" параметров: */
for (i=0; i<k; i++) rez[i]=va_arg (par, double);
va_end .(par); return rez;
}
#include <stdio.h> void main( )
{
double * array; int j; |
|
int n=5; |
|
printf("\n"); |
2.0, 3.0, 4.0, 5.0); |
array=set_array (n, 1.0, |
|
if (array =— NULL) return; |
|
for {j=0; j<n; j++) |
[j]); |
printf ("\t%f", array |
|
free(array); |
|
}
254 |
Программирование на языке Си |
Результат выполнения программы:
1.000000 2.000000 3.000000 4.000000 5.000000
В теле функции обратите внимание на применение функции са11ос(), позволяющей выделить память для массива. Первый параметр функции са11ос() - количество элементов массива, второй - размер в байтах одного элемента. При неудачном вы делении памяти функция са11ос() возвращает нулевое значение адреса, что проверяет следующий ниже условный оператор.
В функциях с переменным количеством параметров есть один уязвимый пункт - если при "чтении" параметров с помо щью макроса va_arg() указатель выйдет за пределы явно ис пользованного списка фактических параметров, то результат, возвращаемый макросом va_arg(), не определен. Таким обра зом, в нашей функции set_array() количество явно заданных параметров переменного списка ни в коем случае не должно быть меньше значения первого фактического параметра (заме няющего int к).
Восновной программе m ain() определен указатель double * array, которому присваивается результат (адрес динамического массива), возвращаемый функцией set_array(). Затем с помо щью указателя array в цикле выполняется доступ к элементам массива, и их значения выводятся на экран дисплея.
Вследующей программе в качестве еще одной иллюстрации механизма обработки переменного списка параметров исполь зуется функция для конкатенации любого количества символь ных строк. Строки, предназначенные для соединения в одну строку, передаются в функцию с помощью списка указателейпараметров. В конце списка неопределенной длины всегда по мещается нулевой указатель NULL.
#±nclude |
<stdio.h> |
|
#include |
<string.h> /* Для функций обработки |
|
#include |
строк */ |
*/ |
<stdarg.h> /* Для макросредств |
#±nclude <stdlib.h> /* Для функции malloc( ) */ char *eoncat(char *sl, ...)
Глава 5. Функции |
255 |
{
va_list par;/* Указатель на параметры списка */
char |
*ер = |
si; |
|
|
char |
*string; |
|
|
|
int |
len = |
strlen(sl);/* Длина 1-ro параметра */ |
||
va_start(par, si); |
/* Начало |
переменного |
||
|
|
|
списка |
*/ |
/* Цикл вычисления общей длины параметровстрок : */
while (ер = va_arg(par, char *)) len += strlen(cp);
/* Выделение памяти для результата: */ string = (char *)malloc(len +1);
strcpy(string, si); /* Копируем 1-й параметр */ va_start(par, si); /* Начало переменного
списка */
/* Цикл конкатенации параметров строк: */ while (cp = va_arg(par, char *))
streat(string, cp); /* Конкатенация двух строк */
va_end(par); return string;
)
void main()
{
char* concat(char* si, ...); /* Прототип функции */
char* s; /* Указатель для результата */ s=concat("\nNulla ","Dies ","Sine ", "Linea!",
NULL); s = concat(s,
"- Ни одного дня без черточки!", "\n\t",
"(Плиний Старший о художнике Апеллесе)", NULL);
printf("\n%s",s) ;
Результат выполнения программы:
Nulla Uies Sine Linea! - Ни одного дня без черточки!
(Плиний Старший о художнике Апеллесе)
256 |
Программирование на языке Си |
В приведенной функции concat() количество параметров пе ременно, но их тип заранее известен и фиксирован. В ряде слу чаев полезно иметь функцию, параметры которой изменяются как по числу, так и по типам. В этом случае, как уже говори лось, нужно сообщать функции о типе очередного фактического параметра. Поучительным примером таких функций служат библиотечные функции форматного ввода-вывода языка Си:
int printf (const char* format,...); int scanf(const char* format,...);
В обеих функциях форматная строка, связанная с указателем format, содержит спецификации преобразования (%d - для де сятичных чисел, %е - для вещественных данных в форме с пла вающей точкой, % f - для вещественных значений в форме с фиксированной точкой и т.д.). Кроме того, эта форматная стро ка в функции printf( ) может содержать произвольные символы, которые выводятся на дисплей без какого-либо преобразования. Чтобы продемонстрировать особенности построения функций с переменным числом параметров, классики языка Си [1] реко мендуют самостоятельно написать функцию, подобную функ ции printf(). Последуем их совету, но для простоты разрешим использовать только спецификации преобразования "%d" и
" % Г .
/* Упрощенный аналог printf( ). |
*/ |
||||
По мотивам K&R, |
[2], стр. |
152 |
|||
#include <stdio.h> |
/* Для макросредств |
||||
#include <stdarg.h> |
|||||
|
|
переменного |
списка параметров */ |
||
void miniprint(char |
*format, |
...) |
|
||
va_list ар;/* |
Указатель на необязательный |
||||
char *р; |
|
параметр*/ |
|
|
|
/* Для просмотра строки format */ |
|||||
int ii; |
/* Целые параметры |
*/ |
|||
double dd; |
/* Параметры |
типа double */ |
|||
va_start(ар,format);/Настроились на первый |
|||||
for (р = |
format; |
параметр |
*/ |
||
*р; р++) |
|
|
Глава 5. Функции |
257 |
{
if (*р != '%')
{
printf("%с",*р);
continue;
}•
switch (*++р)
{ case 'd': ii = va_arg(ap,int); printf("%d",ii);
break;
case 'f': dd = va_arg(ap,double); printf(”%f”,dd);
break;
default: printf("%c",*p);
}/* Конец переключателя */
}/* Конец цикла просмотра строки-формата */ va_end(ap) ;/‘Подготовка к завершению функции*/
}
void main()
{
void miniprint(char *, ...); /* Прототип */ int k = 154;
double e = 2.718282;
miniprint("\пЦелое k= %d,\t4Hono e= %f",k,e);
}
Результат выполнения программы;
Целое k= 154, число е= 2.718282
Интересной особенностью предложенной функции miniprint() и ее серьезных прародителей - библиотечных функ ций языка Си printf() и scanf() - является использование одно го явного параметра и для задания типов последующих параметров, и для определения их количества. Для этого в стро ке, определяющей формат вывода, записывается последова тельность спецификаций, каждая из которых начинается символом Предполагается, что количество спецификаций равно количеству параметров в следующем за форматом списке. Конец обмена и перебора параметров определяется по достиже нию конца форматной строки, когда *р= = '\0'.
1 7 ~ 3124
258 |
Программирование на языке Си |
5.6. Рекурсивны е ф ункции
Рекурсивной называют функцию, которая прямо или косвен но сама вызывает себя. Именно возможность прямого или кос венного вызова позволяет различать прямую или косвенную рекурсию.
При каждом обращении к рекурсивной функции создается новый набор объектов автоматической памяти, локализованных в теле функции.
Рекурсивные алгоритмы эффективны, например, в тех зада чах, где рекурсия использована в определении обрабатываемых данных. Поэтому серьезное изучение рекурсивных методов нужно проводить, вводя динамические структуры данных с ре курсивной структурой. Рассмотрим вначале только принципи альные возможности, которые предоставляет язык Си для организации рекурсивных алгоритмов.
Еще раз отметим, что различают прямую и косвенную рекур сии. Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна. Если в теле функции явно ис пользуется вызов этой же функции, то имеет место прямая ре курсия, т.е. функция, по определению, рекурсивная (иначе - самовызываемая или самовызывающая: self-calling). Классиче ский пример - функция для вычисления факториала неотрица тельного целого числа.
long fact(int k)
{if (k < 0) return 0; if (k = 0) return 1; return k * fact(k-l);
}
Для отрицательного аргумента результат (по определению факториала) не существует. В этом случае функция возвратит нулевое значение. Для нулевого параметра функция возвращает
Глава 5. Функции |
259 |
значение 1, так как, по определению, 0! равен 1. В противном случае вызывается та же функция с уменьшенным на 1 значени ем параметра и результат умножается на текущее значение па раметра. Тем самым для положительного значения параметра к организуется вычисление произведения
к * (к-1) * (к-2) * . . . * 3 * 2 * 1 * 1
Обратите внимание, что последовательность рекурсивных обращений к функции fact() прерывается при вызове fact(O). Именно этот вызов приводит к последнему значению 1 в произ ведении, так как последнее выражение, из которого вызывается функция, имеет вид: l* fact(l-l)
В языке Си отсутствует операция возведения в степень, и следующая рекурсивная функция вычисления целой степени вещественного ненулевого числа может оказаться полезной (следует отметить, что в стандартной библиотеке есть функция pow() для возведения в степень данных типа double. См. При ложение 3):
double expo(double a, int n)
{ if |
(n == |
0) |
return 1; |
|
if |
(a = |
0.0) return 0; |
||
if |
(n > 0) |
return |
a * expo(a, n-1); |
|
if |
(n < |
0) |
return |
expo(a, n+1) / a; |
} |
|
|
|
|
При обращении вида expo(2.0, 3) рекурсивно выполняются вызовы функции ехро() с изменяющимся вторым аргументом: ехро(2.0,3), ехро(2.0,2), ехро(2.0,1), ехро(2.0,0). При этих вызо вах последовательно вычисляется произведение
2.0 * 2.0 * 2.0 * 1
и формируется нужный результат.
Вызов функции для отрицательного значения степени, на пример,
expo(5.0,-2)
эквивалентен вычислению выражения
expo(5.0,0) / 5.0 / 5.0
1 7 *
260 |
Программирование на языке Си |
Отметим математическую неточность, В функции ехро() для любого показателя при нулевом основании результат равен ну лю, хотя возведение в нулевую степень нулевого основания должно Приводить к ошибочной ситуации.
В качестве еще одного примера рекурсии рассмотрим функ цию определения с заданной точностью eps корня уравнения fix) ~ 0 на отрезке [а, 6]. Предположим для простоты, что ис ходные данные задаются без ошибок, т.е. eps > 0,fia) *fib) < 0, b > а, и вопрос о возможности существования нескольких кор ней на отрезке [а, 6] нас не интересует. Не очень эффективная рекурсивная функция для решения поставленной задачи содер жится в следующей программе:
#include <stdio.h> |
|
|
#include |
<math.h> /*Для математических функций*/ |
|
#±nclude |
<stdlib.h> |
/* Для функции exit() */ |
/* Рекурсивная функция для определения корня ма тематической функции методом деления пополам: */ double recRoot(double f(double), double a,
double b, double eps)
{
double fa = f(a), fb = f(b), c, fc; if (fa * fb > 0)
{
printf("ХпНеверен интервал локализации " "корня!");
exit(1);
)
с = |
(а + b) /2.0; |
|
|
|
fc = |
f (с); |
Ь |
- a < eps) |
|
if (fc = =0 . 0 || |
|
|||
return c ; |
< |
0.0) ? recRoot(f, a, |
c,eps): - |
|
return (fa * fc |
||||
|
|
|
recRoot(f, c, |
b,eps); |
)
int counter=0; /*Счетчик обращений к тестовой функции */
void main()
{
double root,
A=0.1, /* Левая граница интервала */
Глава 5. Функции |
261 |
В = 3.5, /* Правая граница интервала */
EPS = 5е-5; /* Точность локализации корня */ double giper(double); /* Прототип тестовой
функции */ root =* recRoot (giper, А, В, EPS);
printf("\пЧисло обращений к тестовой функции " "= %d",counter);
printf ("\пКорень =• %f",root);
)
/* Определение тестовой функции: */ double ^iper(double х)
{
counter++; /*Счетчик обращений - глобальная переменная */
return (2.0/х * cos(х/2.0));
}
Результат выполнения программы:
Число обращений к тестовой функции = 54 Корень = 3.141601
В рассматриваемой программе пришлось использовать биб лиотечную функцию exit(), прототип которой размещен в заго ловочном файле stdlib.h Функция exit() позволяет завершить выполнение программы и возвращает операционной системе значение своего параметра.
Неэффективность предложенной программы связана, напри мер, с излишним количеством обращений к программной реали зации функции, для которой определяется корень. При каждом рекурсивном вызове recRoot() повторно вычисляются значения f(a), f(b), хотя они уже известны после предыдущего вызова. Предложите свой вариант исключения лишних обращений к f ( ) при сохранении рекурсивности.
В литературе по программированию рекурсиям уделено дос таточно внимания как в теоретическом плане, так и в плане рас смотрения механизмов реализации рекурсивных алгоритмов. Сравнивая рекурсию с итерационными методами, отмечают, что рекурсивные алгоритмы наиболее пригодны в случаях, когда поставленная задача или используемые данные определены ре-