Опрацювання структур у функціях

На відміну від масивів, структури можна копіювати та присвоювати, оскільки мова С++ інтерпретує їх як звичайні змінні, а не як вказівники. Тому можна передавати значення структури у функцію через відповідний формальний параметр або повертати структуру як значення результату виконання функції.

Якщо певна структура опрацьовується функціями програми, то шаблон такої структури повинен бути описаний перед функціями, які використовують даний тип структури.

Використовують різні способи передавання структур у функцію для опрацювання: передавання цілих структур через відповідні параметри – структури; передавання адрес структур через параметри – вказівники на структури; передавання окремих полів структур. Залежно від конкретного випадку кожен з цих методів має свої переваги і недоліки.

Передавати цілу структуру в функцію не завжди раціонально – при кожному виклику функції для кожного параметра структурного типу буде створена змінна, для кожного з полів структури буде виконана операція копіювання. Часто більш ефективно передавати в функцію вказівника на структуру, в цьому випадку не витрачається час на операції створення структур і на копіювання значень полів, але всі дії виконується над оригіналом структури, а не над її копією.

Приклад програми. Є два масиви цілих чисел: в першому зберігаються порядкові номери студентів, в другому – рейтинги студентів. Сформувати масив структур, кожна з яких буде містити інформацію про окремого студента. В цьому масиві знайти порядкові номери студентів з найменшим і найбільшим рейтингом (вважати, що рейтинги унікальні), знайти середній рейтинг, кількість студентів з рейтингом нижчим середнього.

 

#ifndef STUDENT_H

#define STUDENT_H

#include <iostream>

using namespace std;

//-----------------------------------------------------------------

struct student {

int id;

int rating;

}; //--------------------------------------------------------------

void student_add(student a[ ], int pos, int new_id, int new_rating           ) {

a[ pos ].id = new_id;

a[ pos ].rating = new_rating;

} //---------------------------------------------------------------

void student_show(student * s) {

cout << "id = " << s->id << ", rating = " << s->rating <<           endl;

} //---------------------------------------------------------------

void student_show_all(student a[ ], int n) {

for (int i = 0; i < n; i++)

     student_show(&a[ i ]);

} //---------------------------------------------------------------

int student_max_rating(student a[ ], int n) {

int max = 0;

for (int i = 1; i < n; i++)

     if (a[ max ].rating < a[ i ].rating)

           max = i;

return max;

} //---------------------------------------------------------------

int student_min_rating(student a[ ], int n) {

int min = 0;

for (int i = 1; i < n; i++)

     if (a[ min ].rating > a[ i ].rating)

           min = i;

return min;

} //---------------------------------------------------------------

double student_avg(student a[ ], int n) {

double avg = 0;

for (int i = 0; i < n; i++)

     avg += a[ i ].rating;

return avg / n;

} //---------------------------------------------------------------

int student_nof_loosers(student a[ ], int n) {

int num = 0;

double avg = student_avg(a, n);

for (int i = 0; i < n; i++)

     if (a[ i ].rating < avg)

           num++;

return num;

}

#endif

 

#include "student.h"

#include <iostream>

using namespace std;

int main() {

const int N = 5;

int sid[ N ] = { 1, 2, 4, 5, 7 };

int srating[ N ] = { 75, 80, 90, 70, 95 };

student s[ N ];

for (int i = 0; i < N; i++)

     student_add(s, i, sid[ i ], srating[ i ]);

student_show_all(s, N);

cout << "max rating = " << student_max_rating(s, N) <<           endl;

cout << "min rating = " << student_min_rating(s, N) <<           endl;

cout << "avg   = " << student_avg(s, N)    <<           endl;

cout << "below avg = " << student_nof_loosers(s, N) <<           endl;

}

Вказівники на функції

Для оголошення вказівників на функцію використовують таку синтаксичну конструкцію:

 

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

 

Операція () – «функція», має вищий пріоритет, ніж операція * - «вказівник». Без дужок навколо * ім’я вказівника оголошення буде прототипом функції, яка використовує відповідні параметри і повертає значення, яке є вказівником. У списку параметрів вказують тільки типи без імен.

Для присвоєння вказівнику адреси певної функції можна використовувати її ім’я або вираз & ім’я функції. Коли вказівник отримав адресу функції, його можна застосовувати для звертання до цієї функції таким чином:

 

(* вказівник_на_функцію) (параметри_функції)

 

Наприклад:

 

#include <iostream>

using namespace std;

void print_hello(void) {

cout << "Hello from print_hello" << endl;

}

int plus_one(int a) {

return a + 1;

}

int main() {

// вказівник на функцію print_hello

void (* p1)(void);

print_hello();

p1 = print_hello;

(*p1)();

// вказівник на функцію plus_one

int (* p2)(int);

cout << plus_one(1) << endl;

p2 = & plus_one;

cout << (*p2)(2) << endl;

}

 

Створимо функцію, яка буде обчислювати значення визначеного інтеграла методом прямокутників. В функцію будемо передавати інтервал інтегрування, кількість частин, на які розбивається інтервал інтегрування, і вказівник на функцію, інтеграл якої необхідно знайти.

 

#include <iostream>

using namespace std;

double simpson(double (* f)(double), double a, double b, int n     ) {

double s = 0, h = (b - a) / n, x;

for (x = a + 0.5 * h; x < b; x += h)

     s += (*f)(x);

return s * h;

}

double f1(double x) {

return sin(x) + cos(x);

}

int main() {

cout << simpson(sin, 0, 1, 100) << endl;

cout << simpson(f1, 0, 1, 100) << endl;

double (* p)(double);

p = f1;

cout << simpson(p, 0, 1, 100) << endl;

}

Рекурсивні функції

Рекурсивними називають функції, які в процесі виконання звертаються самі до себе. Рекурсія може бути безпосередньою (пряма рекурсія) – коли з тіла функції викликається та сама функція, або посередньою (непряма рекурсія) – коли функція викликає інші функції, які безпосередньо або через треті функції звертаються до даної функції.

Здебільшого рекурсивні функції є лаконічними в записі і дають змогу наочно та стисло відобразити алгоритм розв’язання задачі. З іншого боку, рекурсивні звертання часто не легкі для сприйняття, аналізу та контролю. Вони можуть вимагати значних обсягів оперативної пам'яті і призводити до часових затримок в процесі виконання програми.

За способом реалізації рекурсивні виклики рекурсивні виклики функцій нічим не відрізняються від звичайних викликів: кожен раз створюється новий набір формальних параметрів і внутрішніх змінних програми, код функції виконується від самого початку. Результат виконання функції повертається в точку її виклику.

Розглянемо програму для знаходження факторіала:

 

#include <iostream>

using namespace std;

long fact1(int k) {

if(k < 0) return 0;

if(k == 0) return 1;

return k * fact1(k - 1);

}

long fact2(int k) {

if (k < 0) return 0;

int f = 1;

while (k) f *= k--;

return f;

}

int main() {

cout << fact1(5) << endl;

cout << fact2(5) << endl;

}

 

Рекурсивними викликами можна замінити циклічні процеси. В наступній програмі рекурсивні функції використовуються для виводу на екран елементів масиву. Перша функція виводить елементи масиву від першого до останнього, друга – від останнього до першого.

 

#include <iostream>

using namespace std;

void print1(int a[ ], int n) {

if (n == 0) return;

cout << *a << endl;

print1(a + 1, n - 1);

}

void print2(int a[ ], int n) {

if (n > 1) print2(a + 1, n - 1);

cout << *a << endl;

}

int main() {

const int N = 5;

int ar[ N ] = { 1, 2, 3, 4, 5 };

print1(ar, N);

print2(ar, N);

}

 

Ці функції демонструють важливі властивості рекурсивних функцій: оператори, записані перед рекурсивним викликом, виконуються в тому ж порядку, в якому відбуваються виклики функцій; оператори, розташовані після рекурсивного виклику, виконуються в зворотному порядку відносно рекурсивних викликів даної функції.

Розглянемо функції, призначені для знаходження чисел Фібоначчі.

 

#include <iostream>

using namespace std;

long knownf[ 47 ];

void init_fibo() {

int i;

knownf[ 0 ]=0;

knownf[ 1 ]=1;

for(i = 2; i < 47; i++)

knownf[ i ] = -1;

} //---------------------------------------------------------------

long fib1(long n) {

switch (n) {

case 0: return 0; break;

case 1: return 1; break;

default: return fib1(n – 1) + fib1(n – 2);

}

} //---------------------------------------------------------------

long fib2(long n){

int i;

if (knownf[ n ]!= -1)

return knownf[ n ];

else {

knownf[ n ] = fib2(n – 1)+fib2(n – 2);

return knownf[ n ];

}

} //---------------------------------------------------------------

void main() {

init_fibo();

cout << fib1(40) << endl;

cout << fib2(40) << endl;

}

 

При виклику функції fib1(12) буде виконуватись оператор return fib1(11) + fib1(10). Схематичноце можна представити так:

 

 

Рис. 11.1. Схема рекурсивних викликів для знаходження 12го числа Фібоначчі

 

Недоліком цієї функції є те, що знаходження більшості чисел Фібоначчі буде виконуватися декілька разів при кожному виклику функції. Цього можна позбутися, якщо зберігати знайдені числа Фібоначчі в окремому масиві, як це зроблено в функції fib2.

 

Класи пам'яті даних