Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ ІІІ. МОВИ ПРОГРАМУВАННЯ С ТА С++

printf ("%s", **chpp++); printf ("%s", **++chpp+3);

}

?

23. Написати програму калькулятору для обчислення ариф- метичних виразів, поданих в ОПЗ: а) для цілих виразів (використати функцію getint із вправи 20); б) для дійсних виразів (використати функцію getdouble із вправи 21). Додати в калькулятор стандартні арифметичні функції й можливість запам'ятовувати в однолітерних змінних про- міжні результати обчислень і використовувати їх у пода- льших обчисленнях. Вирази вводяться з клавіатури.

24. Лексемою називається: а) послідовність символів, розта- шована між порожніми символами тексту (табуляція, про- біл, кінець рядка, кінець файла); б) слово латинського ал- фавіту; в) ідентифікатор; г) літерал; д) десяткове натура- льне число; е) двійкове число; є) ціле число; ж) дійсне чис- ло; з) вісімкове число; и) шістнадцяткове число. Написати функцію: а) int token (char *s, char *t), що здійс-

нює пошук першої лексеми в рядку s і повертає її в рядку t. Функція повертає n>0, якщо лексему знайдено і n – її довжина; інакше – 0, б) те саме, що й у а), але скористати- ся стандартною функцією strtok.

25.За допомогою функції: а) int token (char *s, char *t) (вправа 25); б) strtok знайти всі ідентифікатори С- програми, що 1) вводиться з клавіатури; 2) розміщена в символьному рядку.

26.У прикл. 3.44 показано, як можна реалізувати паралельне сортування числового масиву за кількома різними поряд-

ками. Реалізувати бінарний пошук елемента в масиві, по- рядок елементів у якому задається окремим масивом: а) індексів; б) покажчиків.

27. Написати варіанти функцій із передаванням результатів через параметри-покажчики для: а) обчислення площі й периметра трикутника за трьома його сторонами; б) від- шукання за цілим n > 7 цілих a,b таких, що 5a +3b =n

та a +b є мінімальним.

28.Керування купою. Написати функцію char *alloc(int

n)для виділення поля вільної пам'яті (купи) заданого роз- міру. Результатом роботи процедури має бути NULL, якщо поле такого розміру не можна виділити. Написати функ- цію void afree(char *p) для звільнення пам'яті (повер-

нення у вільну зону виділеного раніше поля). Купа зада- ється статичним зовнішнім масивом з елементами типу

351

ПРОГРАМУВАННЯ

char s і розглядається як стек, вершина якого є початком вільної частини купи, а елементи нижче становлять задія- ну зону купи. Таким чином, і виділення пам'яті, і її звіль- нення жорстко прив'язані до вершини стека, а вказані функції реалізують стратегію "останнім прийшов – пер- шим пішов". Вершину стека задати статичним зовнішнім покажчиком, що рухається в межах стека.

29.Дано надвеликий одновимірний символьний масив розмі- ром 250 Мбайт. Знайти частоту входжень у ньому кожно- го символу кодової таблиці ASCII.

3.6.Функції

¾Специфікатори функцій

¾Виклики функцій

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

¾Покажчики як аргументи й результат роботи функцій

¾Функція main із параметрами

¾Функції й покажчики функцій як параметри функцій

¾Функції зі змінною кількістю параметрів

¾Вбудовані функції

¾Стандартна бібліотека*

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

Поняття функції як основної структурної одиниці С-програм уже розглядалось у підрозд. 3.1. Там само зазначалось, що воно є важли- вим засобом декомпозиції програм. У належно вибраних функціях завдяки їхній блочній структурі вдається приховати несуттєві для ін- ших підпрограм деталі, зробити їх зрозумілішими, полегшити пода- льшу модифікацію програм. Одного разу розроблені функції можна повторно використовувати в інших програмах.

352

Розділ ІІІ. МОВИ ПРОГРАМУВАННЯ С ТА С++

Функції, як і масиви, мають подвійну семантику – абстрактну й ре- алізаційну. З одного боку, ім'я функції позначає певний алгоритм об- робки даних, а з іншого – воно є покажчиком у системі спеціальних типів функціональних покажчиків. Кожен із таких типів визначаєть- ся типами параметрів і значень функцій. Покажчик конкретної фун- кції задається в заголовку функції ідентифікатором і є константою зі значенням адреси входу в машинний код даної функції. З такими покажчиками можна працювати так само, як і зі звичайними дани- ми-константами: їх можна присвоювати, організовувати у вигляді масивів, передавати як параметри, повертати як значення функцій тощо. Подібні покажчики, як і покажчики-масиви, не можуть бути змінені в програмі, оскільки рівень доступу до них, як і до будь-якої іншої константи, – лише для читання. Кожен із покажчиків функцій, у тому числі й стандартних, має бути явно описаний у програмі. Для декларації стандартних функцій до програми підключають заголовні файли з їхніми прототипами.

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

3.6.1. СПЕЦИФІКАТОРИ ФУНКЦІЙ

Загальний вигляд прототипу й опису функції, а також семантика оператора їхнього виклику розглядалися в підрозд. 3.1.3, 3.3.1. Зупини- мось тепер детальніше на специфікаторах функцій і покажчиків на них.

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

int hash (char* s){…} /*сучасна форма*/

int hash (s) char* s; {…} /*традиційна форма*/

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

Специфікатор функцій має вигляд:

<специфікатор-функції>::=<прямий-специфікатор> \ \([<список-параметрів>] | <список-параметрів>, …\)

<прямий-специфікатор>::=<простий-специфікатор>| \(<специфікатор-імені>\)| <специфікатор-функції>| <специфікатор-масиву>

353

ПРОГРАМУВАННЯ

<список-параметрів>::=<параметр>{,<параметр>} | <void> | <порожньо> <параметр>::=[<кваліфікатор_типу>]<тип> (<специфікатор-імені> | <абстрактний-специфікатор>)

<порожньо>::= ε 32

У С99 параметри обов'язково декларуються з типом33. Тип парамет- ра може бути будь-яким, за винятком void. При цьому параметри фу- нкціонального типу Т і параметри-масиви типу Т будуть замінюватися компілятором на покажчики типу Т. Існує три різновиди списку пара- метрів: а) порожній або, що те саме, одноелементний void; б) із фіксо- ваною кількістю параметрів; в) зі змінною кількістю параметрів. У ви- падках б) і в) параметр може бути з іменем або без такого. Абстракт- ний специфікатор – це специфікатор імені з вилученим елементом, який задає безпосередньо ім'я. Наприклад, параметрам з іменами int n та int p[] відповідають параметри з абстрактними специфікатора- ми відповідно int та int []. У списку зі змінною кількістю парамет- рів спочатку розташовується його фіксована частина, а неоголошені параметри замінюються трьома крапками (див. підрозд. 3.6.7).

Приклад 3.47. Прототипи функцій і описів функціональних пока- жчиків:

32ε – порожнє слово.

33У попередніх версіях параметр без типу вважався цілим.

354

int f10 (int n, int (*g)(void)); Ціла функція з двома параметрами – цілим і покажчиком цілих функцій без параметрів Ціла функція з двома параметрами –

цілим і цілою функцією без параметрів Функція без параметрів зі значеннями- покажчиками цілих функцій без пара- метрів

355

ПРОГРАМУВАННЯ

■

3.6.2. ВИКЛИКИ ФУНКЦІЙ

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

<виклик-функції>::=<вираз-виклик>|<вираз-виклик>; <вираз-виклик>::=(<константний-покажчик-функції> |\ |<покажчик-функції>|(*<покажчик-функції>\)) \ ([<список-фактичних-параметрів>]\) <список-фактичних-параметрів>::=<фактичний-параметр>

{,<фактичний-параметр> <фактичний-параметр>::=<вираз>

Оскільки в процесі передавання фактичних параметрів їхні зна- чення зводяться до типу формальних, то типи формальних і фактич- них параметрів мають бути узгодженими (див. підрозд. 3.2.4).

Приклад 3.49. Виклики функцій:

356

Розділ ІІІ. МОВИ ПРОГРАМУВАННЯ С ТА С++

■

3.6.3. РЕКУРСИВНІ ФУНКЦІЇ

У мові програмування С тіло функції може містити виклики інших функцій, що задекларовані вище в тексті програми. Це означає, що функція може містити виклики й себе самої, оскільки її заголовок є її прототипом і передує тілу функції – такі виклики називаються рекур- сивними. Функція з рекурсивними викликами називається рекурсив- ною. Рекурсивні функції відкривають шлях до реалізації індуктивних означень функцій та їхніх систем (див. підрозд. 2.6).

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

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

жить часова складність програми FA (n ).

Рекурсивні функції є природним засобом обробки індуктивно ви- значених структур даних. Покажемо, як програмуються деякі індук- тивно визначені функції з підрозд. 2.6.2.

Приклад 3.50. Програмування індуктивно визначених функцій:

1) /*Швидке піднесення до степеня n>=0*/ double spow1 (double a, unsigned int n)

{

if (n==0) return 1;

if (n%2) return a*spow1(a, n/2)*spow1(a, n/2);

357

ПРОГРАМУВАННЯ

else return spow1(a, n/2)*spow1(a, n/2);

}

double spow2 (double a, unsigned int n) {double p;

p=spow2(a, n/2); if (n==0) return 1;

if (n%2) return (a*y * y); else return (y*y);

}

2) /*Комутативне розбиття числа ІВФ19 */

long q(long n, long m)

{

if (n==1 || m==1) return 1;

return (m>=n?1+q(n,n-1):q(n-m,m)+q(n,m-1));

}

long f(long n) {return q(n,n);

}

3) /*розкладання натурального числа на прості множники ІВФ17 */

void g(long x, long y)

{

if (x==1) printf("1");

else if (x<y*y) printf("%dl", x);

else if (x%y==0) {printf("%dl:", y); g(x/y, y);} else g(x,y+2);

}

long f(long x)

{if (x%2==0) {printf("2:"); f(x/2);} else g(x,3);

}

Наприклад, виклик f(24) виведе на екран:

2:2:2:3:1

4) Ханойські вежі (ІВФ15 ). Результуюча послідовність пар операцій буде подана у стандартному вихідному потоці stdout у вигляді:

< x1,y1 > < x2,y2 >…

/*Ханойські вежі ІВФ15 */

void hanoi (short n, short x, short y)

{

if (n<1 || x<1 || y<1 || x>3 || y>3)

358

Розділ ІІІ. МОВИ ПРОГРАМУВАННЯ С ТА С++

{

printf("Помилка в даних"); return;

}

if (n==1) printf("<%d,% d>",x,y); else {

hanoi (n-1, x,6-x-y); printf("<%d,% d>", x,y); hanoi (n-1, 6-x-y, y);

}

}

■

Складніші приклади програмування й застосувань рекурсивних функцій можна знайти в розд. 4. Нерекурсивний варіант швидкого піднесення до степеня див. у прикл. 3.31.

3.6.4. ПОКАЖЧИКИ ЯК АРГУМЕНТИ Й РЕЗУЛЬТАТ РОБОТИ ФУНКЦІЙ

Функції можуть повертати покажчики, можна передавати покаж- чики як аргументи функцій. Якщо як фактичний параметр передати функції змінну, то функція отримає доступ до її копії, а не до самої змінної. Тому всі маніпуляції з копією в тілі функції не будуть мати жодного впливу на саму змінну – фактичний параметр. Що ж робити, якщо треба змінити змінну, а не її копію? Одним з варіантів є вико- ристання замість змінних покажчиків, що задають їхні адреси, як аргументів функції. Наприклад, у програмі сортування методом буль- башки (див. прикл. 4.3) необхідно поміняти місцями два елементи, що порушують порядок серед компонентів масиву. Це можна зробити за допомогою такої функції:

void swap(int *pa, int *pb)

{

int temp=*pa; *pa=*pb; *pb=temp;

}

Тоді, якщо потрібно поміняти місцями, наприклад, сусідні елементи масиву а з індексами i тa i+1, то достатньо викликати функцію swap і передати їй покажчики на ці елементи:

swap(&a[i], &a[i+1]); або swap(a+i, a+i+1);

359

ПРОГРАМУВАННЯ

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

Інша обставина, що спонукає до використання аргументів- покажчиків, суто економічна. У процесі побудови модифікованого тіла функції виділяється локальна пам'ять, куди копіюються значення аргументів, при цьому витрачаються такі важливі обчислювальні ре- сурси, як час роботи процесора та стек. Тому замість складних струк- тур даних – структур, об'єднань, їхніх похідних – краще передавати у функцію покажчики на них. Тоді у стек при виклику будуть копіюва- тися лише адреси даних, а не самі дані, що набагато ефективніше. Наприклад, нехай задано структуру

struct date { int day;

int month; unsigned year; };

Можна написати таку функцію для відображення дати:

void printDate(struct date d)

{

printf("%02d/%02d/%04d", d.day, d.month, d.year);

}

У процесі виклику функції буде виділено автоматичну пам'ять для збе- реження аргументу – структури d. Однак оптимальнішим був би такий варіант функції printDate з аргументом – покажчиком на структуру:

void printDate(struct date *pd)

{

printf("%02d/%02d/%04d", pd->day, pd->month, pd->year);

}

Класичними функціями, що повертають покажчики, є функції ди- намічного розподілу пам'яті, які повертають адреси полів або конста- нту NULL у випадку помилки – функції виділення пам'яті malloc, calloc і realloc (див. підрозд. 3.5.5).

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

360