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

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

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

Приклад 3.57. Вбудована функція max(x,y):

/*Заголовний файл max.h*/

/*містить опис вбудованої функції max*/

inline max (double x, double y) { return ((x<y)? y : x);

}

/*Файл max.с містить виклики функції max із файла max.h*/ #include "max.h"

/*Визначення вбудованої функції max як зовнішньої*/ extern inline max (double, double);

…

printf ("%f", max(a,b)); ….

■

3.6.9. СТАНДАРТНА БІБЛІОТЕКА*

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

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

371

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

372

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

Основні функції введення-виведення (файл <stdіo.h>), математичні функції (файл <math.h>), функції для роботи з рядками (файл <string.h>) і покажчиками (файл <stdlib.h>) розглядалися раніше.

*Література для CР: С-функції [55, 102, 132, 133]; ознайоми-

тися з іншими функціями, макросами, типами й константами біб- ліотеки мови С можна в [55, 102, 136].

Контрольні запитання та вправи

1.Визначити структуру специфікатора функції.

2.Визначити структуру специфікатора імені функції.

3.Який вигляд має виклик функції?

4.Що таке формальні й фактичні параметри функції?

5.Які функції називаються рекурсивними?

6.Що таке глибина рекурсії?

7.Чим небезпечні великі глибина рекурсії й загальна кількість рекурсивних викликів?

8.Що таке пряма й непряма рекурсія?

9.Як описується покажчик і масив покажчиків функцій?

10.Що таке параметри функції main і яка їхня роль у ній?

11.Як описуються покажчики функцій у якості параметрів?

12.Як відбувається ініціалізація параметрів функцій зі змінною кількістю параметрів?

13.Описати параметри функції швидкого сортування масиву qsort.

14.Який тип мають змінні p та q: void (*p)(int x, int g(void));

int q (int *n, int (*g) (int, char)); сhar **q(void); int (*p)(int x);

сhar **q(int x); int (*p)(const int x);

int *p[] (int n,double *x int, (*q (void))(void) ? 15. Написати функцію, що за дійсними змінними x та y знахо-

16.Дано цілі числа m,n, p,q ≠ 0 . Знайти їхні найбільший спіль- ний дільник НСД(m,n, p,q ) і найменше спільне кратне

НСK (m,n, p,q ).

17.Напишіть рекурсивну функцію, що переставляє елементи рядка у зворотному порядку.

373

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

18.Написати рекурсивну функцію:

а) для друкування десяткових цифр числа типу int у обер- неному порядку;

б) int strcmp(char *x, char *y), яка порівнює два рядки; в) int strlencmp(char *x, char *y), яка порівнює дов-

жину двох рядків (повертає: 1, якщо |x|>|y|; 0, якщо

|x|=|y|; –1, якщо |x|<|y|);

г) int strрrе (char *x, char *y), яка перевіряє, чи є другий рядок префіксом першого;

д) int strch(char *x, char c) для обчислення частоти входжень символу в рядок.

19.Елімінувати рекурсію у функції (прикл. 3.50), що знаходить: а) комутативне розбиття числа; б) розкладання числа на прості множники.

20 * . Елімінувати рекурсію у функції: a) hanoi (прикл. 3.50) [1]; б) 91-й функції Мак-Картні (підрозд. 2.6.2). У б) обчислити

значення функції для n =1,200.

21.Побудувати трикутник Паскаля, що складається з коефіціє- нтів бінома Ньютона (a +b)n . Навести рекурсивний і нере- курсивний варіанти розв'язку [33].

22.Задача про ферзів, що домінують на дошці. Побудувати всі

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

23.Задача про коней (слонів), що домінують на дошці 8 ×8 . Побудувати можливе розташування: а) 12 коней, що атаку- ють усі вільні поля дошки; б) те саме, що й у а), але йдеться про 8 слонів.

24.Застосувати функцію qsort для впорядкування масиву ря- дків за їхньою довжиною.

25.Реалізувати бінарний пошук елемента в довільному впоряд- кованому масиві, порядок на елементах якого задає функ- ція-предикат Compare(x,y), а розташування елементів ма- сиву згідно з даним порядком – окремий масив: а) індексів; б) покажчиків.

26.У командному рядку задано масив цілих чисел. Відсортувати його й реалізувати рекурсивний бінарний пошук елемента у відсортованому масиві. Нерекурсивний алгоритм бінарного пошуку див. у підрозд. 4.1.2.

27.Написати функцію double scalar(double *a, double

*b, int n) для обчислення скалярного добутку двох век- торів довільної довжини. Знайти скалярний добуток двох

374

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

векторів, елементи яких вводяться з клавіатури. Довжина векторів задається в командному рядку.

28.Написати варіант калькулятора із вправи 23 із підрозд. 3.5 для виразу, що задається в командному рядку. При цьому кожному операнду й символу операції відповідає окремий аргумент.

29.Дано п'ять функцій: double f1(int i), …, double f5(int

i), що задають математичні функції: f1(x ) = sin(x * x ); f 2(x )= cos (x )* sin(x ); f 3(x )= x * x /2 , f 4(x) = ln(x * x /2)/x , f 5(x ) = tg(πx /4) . Реалізувати табуляцію цих функцій у табли- ці, у шапці якої відобразити номер функції, інтервал [a,b] і крок табуляції d (вводяться з клавіатури).

30.Описати функцію зі змінною кількістю цілих параметрів, що знаходить: а) НСД аргументів, б) НСК аргументів.

31.Описати функцію зі змінною кількістю різнотипних пара- метрів, що знаходить: а) середнє арифметичне аргументів; б) середнє геометричне аргументів.

3.7.Тип структур

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

¾Операції на структурах

¾Бітові поля

¾Тип об'єднань

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

Тип структур складають вектори з поіменованими компонентами певних фіксованих типів. Дані типу структур називаються структу- рами34, а компоненти структур – полями. На відміну від масивів, ти- пи полів усередині структури можуть бути різними, але не функціо- нальними (не типами функцій і покажчиків на них).

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

34 У деяких мовах (Кобол, ПЛ/1, Паскаль тощо) структури називаються записами.

375

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

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

Також допускаються структури з полями-покажчиками свого влас- ного типу, що дозволяє моделювати в мовах програмування індукти- вно визначені об'єкти, наприклад такі, як списки, дерева, графи то- що, робота з якими описується в підрозд. 4.3.

3.7.1. СПЕЦИФІКАТОРИ СТРУКТУР

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

<cпецифікатор-типу-структур>::=struct [<ім'я-тегу-структури>] \ {<cписок-полів>}|struct <ім'я-тегу-структури>

< ім'я-тегу-структури>::=<ідентифікатор> <cписок-полів>::=<поле>{,<поле>} <поле>::=<просте-поле> | <бітове-поле> <просте-поле>::=<опис-поля>

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

Приклад 3.58. Структура для подання дати в році:

struct date d2, Tab[10], *p; /*змінна-структура d2 типу date,

масив структур (таблиця) Tab типу date, покажчик р типу date*/

Змінні d, d2 визначені як структури, кожна з яких складається із трьох полів – day, month та year, змінна p – покажчик на таку струк- тура, а змінна Tab – масив із десяти таких структур. Змінні d2, Tab та р описані за допомогою тегу date ■

Як і у випадку масивів, декларація структур може задавати непов- ний тип. Наприклад, можна декларувати тільки ім'я тегу, а не сам

376

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

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

{struct first_node; /*неповний тип*/

struct second_node {struct first_node *left; …};/*повний тип*/ struct first_node {struct second_node *right; …}; /*повний тип*/

}

Перша декларація, окрім того що декларує ім'я тегу структури, ві- дміняє в блоці дію будь-яких раніше визначених тегів з іменем first_node.

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

struct node { іnt data;

struct node *next; /*node: неповний тип*/

}; /*node: повний тип*/

Деталі відповідної реалізації можна знайти в підрозд. 4.3.1. Компоненти структури розміщуються в загальному полі структури

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

Змінні-структури можна ініціалізувати в процесі опису. Ініціаліза-

тор структури має вигляд:

<ініціалізатор-структури>::={<ініціалiзатор-поля> \

{,<ініціалізатор-поля>}

}

Ініціалізатор поля має відповідати типу поля. Стандарт С99 дозво- ляє неконстантні ініціалізатори. Як і у випадку масивів, існують пра- вила для скорочення запису ініціалізаторів. Зокрема, якщо ініціаліза- торів полів менше ніж потрібно, то використовуються їхні значення за умовчанням. Якщо ж таких ініціалізаторів більше, то це викликає помилку в роботі компілятора.

Приклад 3.59. Описи змінних-структур з ініціалізацією:

377

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

struct date d={1, 9, 2008};

int n=9; struct date d={1, n}; /*еквівалентно опису struct date d={1, 9, 0}; */

struct date d={1, n, 2008, 0}; /*некоректний опис: константа 0

зайва*/

struct data {char *row, *сol; int matr [2][3]}s={"abc",NULL, {{2,2,2},{3,3,3}}}; ■

3.7.2. ОПЕРАЦІЇ НА СТРУКТУРАХ

На однотипних структурах можна виконувати операції присвою- вання, взяття адреси структури та її окремих полів і операції крапка '.' та стрілка '->', що забезпечують доступ до полів структури.

Операція крапка . за іменем структури s та її полем v будує складе- ну змінну s.v, яка є l-виразом і зв'язана із цим полем. Складена змінна має тип свого поля й забезпечує всі можливості доступу, визначені для змінних даного типу. Складена змінна має тип поля й забезпечує всі можливості доступу до нього, визначені для даних цього типу.

Операція стрілка -> за покажчиком p на структуру та її полем v будує l-вираз p->v, зв'язаний із цим полем у структурі, на яку посила- ється покажчик. Формально це можна записати так:

p->v de=f (*p).v,

де (*p) є розіменуванням покажчика p.

Приклад 3.60. Для змінних, описаних у прикл. 3.58, 3.59, можливі такі вирази:

d.day=1;

d.month=9;

d2.day=d.day; Tab [3].day=5; (*s.row=='a')=1 s.matr[1][1]=0; p->day=2;

*p=d; p.month++; ■

За стандартом С99 тип полів структури не може бути гнучким, але певна структура s може містити недовизначений масив вигляду Т х[ ] за умови, що цей масив є останнім полем у ній. Тоді звернення до змінних з індексами s.x[0], s.x[1], … синтаксично припустимі, але необхідно додатково забезпечити їхню семантичну коректність.

378

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

Приклад 3.61. Структура Vector для зображення динамічного ма- сиву та його довжини:

struct Vector {int n; float mas[];} *p; int m;/*реальна довжина масиву*/

…

/*виділення пам'яті для одного екземпляра структури Vector і елементів масиву*/

p=malloc (sizeof(struct Vector)+m*sizeof(float)); p->n=m;

p->mas=(float *) p++; /*адреса динамічного масиву*/

…

/*збільшення компонентів динамічного масиву на 1*/ for (int i=0; і<(p->n);i++) p->mas[i]++;

…

■

Операції порівняння для однотипних структур як векторів не ви- значені, але їх можна порівнювати покомпонентно, наприклад:

(d2.day= =d.day)&&(d2.month= =d.month)&&(d2.year= =d.year).

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

Приклад 3.62. Функція для додавання комплексних чисел:

ним значенням*/ //Повертає суму с3=с1+с2

complex Add_complex (complex c1, complex c2)

{

■

379

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

Унаступному прикладі показано, як обробляються таблиці, подані

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

Приклад 3.63 [55]. Підрахунок частоти входжень службових слів у текст С-програми. У програмі ініціалізується масив keytab структур із

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

#include <stdio.h> #include <ctype.h> #include <string.h>

//Опис та ініціалізація таблиці: у першому стовпчику розташовані // покажчики на службові слова, у другому – частота їхніх входжень // у текст

struct key {char *keyword; int keycount;} keytab []={ {"break", 0},

{"case", 0}, {"char", 0},

…

{"unsigned", 0}, {"while", 0}

};

#define MAXWORD 20

#define LETTER 'a'

іnt getword(char *w, int lim); /*Функція читання чергового сло-

ва*/

int type(int c); /*Визначення типу символу*/

int binary (char *word); /*Бінарний пошук у таблиці слова*/

int main()

{

int n, t;

char word[MAXWORD]; while((t=getword(word, MAXWORD))!=EOF) if(t==LETTER)

{

if((n=binary(word))>=0)

keytab[n].keycount++;

};

int count=(sizeof(keytab)/sizeof(struct key)); for(n=0; n<count; n++)

380