учебное пособие. Часть1. Информатика

if ( n >= 0 )

printf ( "Фактоpиал n=%ld", fac (n)); else puts ( "Введены неверные данные" ); return 0;

}

Рассмотрим, как работает эта программа. Для вычисления fac(n) не- обходимо произвести рекурсивное обращение и вычислить fac(n-1). Это, в свою очередь, требует другого рекурсивного обращения для вычисления fac(n-2) и т. д. Таким образом, чтобы вычислить fac(n), нужно произ- вести n рекурсивных обращений, последнее из которых выполняется для fac(0)=1. Принято говорить, что глубина рекурсии, требуемой для вычис- ления fac(n), равна n. Чтобы рекурсивная функция не работала бесконеч- но, в теле функции обязательно должно быть предусмотрено тривиальное решение. Тривиальное решение – это такое решение, при котором функция не вызывает саму себя, а завершется рекурсивный цикл.

Другим примером рекурсивной функции является задача вычисления наибольшего общего делителя по алгоритму Евклида. Согласно этому алго- ритму, наибольшим общим делителем двух чисел будет меньшее из этих чи- сел, если остаток от целочисленного деления большего числа на меньшее ра- вен 0. В противном случае на следующем этапе находится наибольший об-

щий делитель остатка от целочисленного деления и меньшего из двух первых чисел и т. д.

// Пример pr51 #include <iostream> using namespace std; int nod ( int n, int m )

{

if ( n>m )

if ( n%m == 0 )

return m; // Тривиальное решение else

nod ( n%m, m ); else

if ( m%n == 0 )

return n; // Тривиальное решение else

nod(m%n,m);

}

int main ()

{

int n, m;

cout << "Введите n, m";

271

cin >> n >> m;

cout << "НОД=" << nod ( n, m ); return 0;

}

Следующий пример является более подходящим для демонстрации рекур- сии [15]. Во входном файле записана (без ошибок) формула следующего вида:

<фоpмула> ::= <цифpа> | (<фоpмула> <знак> <фоpмула>)

<знак> ::= + | - | *

<цифpа> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Ввести эту фоpмулу и вычислить ее значение. Hапpимеp:

5=5,

(2+5)=7

((2+5)*2)=14.

Из условия задачи следует, что если введена просто цифра, то это уже формула. Если в формуле используется знак операции, то формула должна быть записана в круглых скобках.

// Пример pr52 #include <cstdio> using namespace std; int form (void)

//Рекурсивная функция читает из входного файла символы,

// образующие пpавильную фоpмулу и вычисляет ее значение

{

char c, op; int x, y, f;

scanf ( "%c", &c); // Входной файл – клавиатура if ( c >= '0' && c <= '9' )

{ //Цифра тоже фоpмула – тривиальное решение f = c-'0';

return f;

}

else // Прочитали скобку

{

x = form(); // Вызов для чтения пеpвого опеpанда scanf ( "%c", &op ); // Чтение знака опеpации

y = form (); // Вызов для чтения втоpого опеpанда switch (op)

{

case '+' : f = x+y; break; case '-' : f = x-y; break; case '*' : f = x*y; break;

}

272

scanf ( "%c", &c ); // Чтение закрывающихся скобок return f;

}

}

int main ()

{

printf ( "\n Введите фоpмулу:" ); printf ( " f = %d", form ());

return 0;

}

Так как формула во входном файле записана правильно, то при вхож- дении в функцию form читается либо цифра, либо открывающаяся скобка. Пока не встретится цифра, функция будет вызывать саму себя, считывая та- ким образом открывающиеся скобки.

10.10. Указатели на функции

Иногда возникает необходимость задавать в качестве параметра функ- ции другую функцию. Функция может быть передана в другую функцию и трактоваться как данные. Указатель на функцию может быть описан как па- раметр и передаваться в функцию наряду с другими данными.

Прежде чем вводить указатель на функцию, напомним, что каждая функция характеризуется типом возвращаемого значения, именем, количест- вом, порядком следования и типами параметров. При использовании имени

функции без последующих скобок и параметров имя функции выступает в качестве указателя на эту функцию, и его значением служит адрес размеще- ния функции в памяти. Это значение адреса может быть присвоено другому указателю, а затем уже этот новый указатель можно применять для вызова функции. В определении нового указателя должен быть тот же тип, что и возвращаемое функцией значение и такие же параметры. Указатель на функ- цию определяется следующим образом [4]:

тип_функции (*имя_указателя) (спецификация_ параметров);

Например: float(*funptr)(char); − определение указателя funptr на функ- цию с параметром типа char, возвращающую значение типа float.

Если приведенную синтаксическую конструкцию записать без первых круглых скобок, то компилятор воспримет ее как прототип некой функции с именем funptr и параметром типа char, возвращающей значение указателя ти-

па float *.

Следующий пример демонстрирует как раз тот случай, когда функция возвращает значение указателя:

int *(*funptr1)(float*, int);

273

Таким образом, определен указатель funptr1 на функцию с параметрами типа указатель на float и типа int, возвращающую значение типа указатель на int.

Для удобства последующих применений и сокращений производных описаний рекомендуется с помощью идентификатора typedef вводить имя типа указателя на функцию.

Теперь рассмотрим еще одно определение типа: typedef float (*furavn)(float x);

Здесь сообщено, что furavn − это указатель на функцию с одним парамет- ром float, возвращающую значение типа float. Такое определение типа можно ис- пользовать, например, для написания универсальной функции определения кор- ней уравнения uravn, заголовок которой имеет следующий вид:

float uravn(furavn f, float a, float b);

Первым параметром функции uravn является функция f типа furavn. Это означает, что f − указатель на любую функцию от одного вещественного параметра, возвращающую тип float. Если функция my_fun определена так:

float my_fun ( float x )

{

return x*x-5;

}

то вызов функции uravn будет выглядеть следующим образом: float koren = uravn ( my_fun, a1, b1 );

Имя функции my_fun выступает в качестве указателя на эту функцию, и поэтому не требуется указания ссылки.

Следующая программа демонстрирует механизм передачи функций в качестве фактических параметров вызова. Программа выводит на экpан таб-

лицу двух функций sin1(x) = (sin (2x)+2)*(-x) и cos1(x) = (cos (2x)+2)*(-x).

Вычисление и печать значений этих функций реализуются в функции prinfunc, которой в качестве параметра передается номер позиции n на экра- не, куда будет выводиться очередной результат (с помощью этого параметра обеспечивается вывод в две колонки), и имя нужной функции [10].

// Пример pr53 #include <cstdio>

#include <cmath> using namespace std;

//Описание указателя на функцию typedef float (*my_fun)(float); float sin1 ( float x )

{

return (sin(2*x)+2)*(-x);

274

}

float cos1 ( float x )

{

return (cos(2*x)+2)*(-x);

}

void prinfunc(int n,my_fun f) // f-функция типа my_fun

{

const int c = 15; //Количество вычислений функций float x;

int i;

for ( i = 1; i <= c; i++ )

{

x = i*(2*3.14/c);

printf ( "%5.3f %18.5f \n", x, f(x));

}

prinfunc ( 40, cos1 ); return 0;

}

Разрешается применять массивы указателей на функции. Указатели на функции могут быть компонентами структур. Массивы указателей на функ- ции удобно применять при реализации систем, управляемых с помощью ме- ню. Каждому пункту меню ставится в соответствие реализующая его функ- ция, указатель на которую помещается в массив. Пользователю предлагается выбрать из меню нужный ему пункт (в простейшем случае он вводит номер выбираемого пункта), и по номеру пункта, как по индексу, из массива выби- рается соответствующий адрес функции. Обращение к функции по этому ад- ресу обеспечивает выполнение требуемых действий. Следующая программа демонстрирует такое использование указателей на функции. В программе pr54 в одномерном массиве в зависимости от выбранного пунк- та меню вычисляется: сумма положительных, количество нулевых и произведение ненулевых (будем считать, что такие элементы есть в масси- ве) элементов массива, либо завершается выполнение программы.

// Пример pr54 #include <cstdio>

275

using namespace std;

// Опpеделение функций для обработки меню: void add ( int *a, int n )

{

int s=0;

for(int i=0; i<n; i++) if ( a[i] > 0 ) s += a[i]; printf (“s = %d \n”, s);

}

void mult ( int *a, int n )

{

int p = 1;

for(int i=0; i<n; i++) if ( a[i]) p *= a[i]; printf (“p = %d \n”, p);

}

void count ( int *a, int n )

{

int k = 0;

for(int i=0; i<n; i++) if ( a[i] != 0 ) k++; printf (“k = %d \n”, k);

}

typedef void (*MENU) (int *,int); //Указатель на функцию

//Инициализация массива указателей на функцию MENU menugr[3] = { add, mult, count };

int main ()

{

puts ( "1 - сумма" );

puts ( "2 - произведение" ); puts ( "3 - количество" ); puts ( "4 - выход" );

int n;

printf("Введите число элементов в массиве”); scanf("%d",&n);

int *a = new int [n];

printf("Введите элементы массива”); for(int i=0; i<n; i++) scanf("%d",&a[i]);

while ( 1 )

{

while (1 )

{//Цикл продолжается до ввода правильного номера

276

puts ( "Введите номеp пункта меню" ); scanf ( "%d", &n );

if ( n >= 1 && n <= 4 ) break; puts("Ошибка в номеpе пункта");

}

if ( n != 4 )

(*menugr[n-1])(a, n); // Вызов функции по указателю else return 0;

}

}

Использование указателей на функции позволяет сделать программы более структурированными, избегать повторного кодирования.

Контрольные вопросы

1.Как определяется область действия идентификаторов?

2.Какие классы памяти используются в С++?

3.В каких случаях применяется перегрузка функций?

4.Какие преимущества имеют подставляемые функции?

5.Как определяются значения параметров, передаваемых по умолча-

нию?

6.Для чего служат шаблоны функций?

7.В каких случаях рекомендуется использование спецификатора

register ?

8.Какая функция называется рекурсивной?

9.Какая функция называется косвенно рекурсивной?

10.Где сохраняются локальные переменные и формальные параметры во время рекурсивного вызова?

11.Когда используются указатели на функции?

12.Как описываются указатели на функции?

13.Можно ли описать массив указателей на функции?

277

11. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

11.1. Одноcвязные списки

Очень часто динамическую память используют для создания связанных списков [14], которые применяются в тех случаях, когда трудно или вообще невозможно предсказать число объектов, обрабатываемых программой, и поэтому традиционные структуры данных, для которых требуется заранее определить максимальное число элементов, не применимы. В подобных си- туациях используются динамические объекты (узлы), которые создаются не заранее, а в моменты, определяемые логикой программы, и объединяются (связываются) с уже существующими объектами с помощью указателей. Начнем рассмотрение с линейных односвязных списков. Схема односвязного списка приведена на рис. 26, такая организация списка называется стеком (далее стек).

Самым подходящим типом для описания динамических объектов яв- ляются структуры, поля которых содержат информацию некоторого вида и обязательно указатель, предназначенный для организации связи с другим уз- лом списка. Структура стека предполагает, что очередной узел в списке по- средством этого указателя связывается с предыдущим узлом, а самый первый узел, как не имеющий предыдущего, имеет "пустой" (NULL) указатель. Ко- гда указатель имеет значение NULL, он не указывает ни на что. Указатель на первый узел (и тем самым на весь список) содержится в некоторой перемен- ной, которую называют вершиной стека. При такой организации односвяз- ных списков доступ осуществляется только к узлу, расположенному в вер- шине стека: новый элемент добавляется в вершину стека, удаляется элемент также из вершины стека. Стек часто называют структурой LIFO: last in

− first out (последний вошел − вышел первый).

Предположим, что входной файл содержит некоторую последователь- ность чисел, тогда сформировать стек можно с помощью следующей про- граммы:

278

веряем, не встретился ли конец файла и т. д. В первом построенном узле поле указателя получает значение NULL, и по окончании построения стека этот узел остается в самом низу (на дне стека). При прохождении стека это значе- ние используется для проверки, пройден ли стек до конца. Второй и после- дующие узлы пристраиваются сверху, и указатель top всегда указывает на последний созданный узел.

Пpи обработке списков необходимо рассмотреть вопросы, связанные с удалением и добавлением узлов из списка. Чаще всего эти операции выпол-

няются в вершине стека и в этом случае включение нового узла можно изобразить с помощью операторов (рис. 27):

top

info

link

info

link

.....

info

link

NULL

scanf ( "%c", &w );

node *newnode = new node; newnode->link = top; newnode->info = w;

top = newnode ;

280