Директиви препроцесора

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

Примітка. Після директив препроцесора крапка з комою не ставиться.

1.18.1 Директива #include

Синтаксис:

#include "ім'я_файла"

#include <ім'я_файла>

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

Різниця між двома формами директиви полягає в методі пошуку пре процесором файла, що включається. Якщо ім'я файла розміщене в "кутових" дужках < >, то послідовність пошуку препроцесором заданого файла в каталогах визначається встановленими каталогами включення (include directories). Якщо ж ім'я файла заключне в лапки, то препроцесор шукає в першу чергу файл у поточній директорії, а потім вже у каталогах включення.

Робота директиви #include зводиться практично до того, що директива #include прибирається, а на її місце заноситься копія вказаного файла.

Текст файла, що включається може містити директиви препроцессора, і директиву #include зокрема. Це означає, що директива #include може бути вкладеною. Допустимий рівень вкладеності директиви #include залежить від конкретної реалізації компілятора.

#include <stdio.h> /* приклад 1*/

#include "defs.h" /* приклад 2*/

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

В другому прикладі в головний файл включається файл з ім'ям defs.h. Подвійні лапки означають, що при пошуку файла спочатку повинна бути переглянута директорія, що містить поточний файл.

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

#define myincl "c:\test\my.h"

#include myincl

1.18.2 Директива #define

Синтаксис:

#define ідентифікатор текст

#define ідентифікатор (список_параметрів) текст

Директива #define заміняє всі входження ідентифікатора у програмі на текст, що слідує в директиві за ідентифікатором. Цей процес називається макропідстановкою. Ідентифікатор замінюється лише в тому випадку, якщо він представляє собою окрему лексему. Наприклад, якщо ідентифікатор є частиною рядка або більш довгого ідентифікатора, він не замінюється. Якщо за ідентифікатором слідує список параметрів, то директива визначає макровизначення з параметрами.

Текст представляє собою набір лексем, таких як ключові слова, константи, ідентифікатори або вирази. Один або більше пробільних символів повинні відділяти текст від ідентифікатора (або заключених в дужки параметрів). Якщо текст не вміщується в рядку, то він може бути продовжений на наступному рядку; для цього слід набрати в кінці рядка символ обернений слеш \ і зразу за ним натиснути клавішу Enter.

Текст може бути опущений. В такому разі всі екземпляри ідентифікатора будуть вилучені з тексту програми. Але сам ідентифікатор розглядається як визначений і при перевірці директива # if дає значення 1.

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

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

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

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

Всередині тексту в директиві # define можуть знаходитися вкладені імена інших макровизначень або констант.

Після того, як виконана макропідстановка, отриманий рядок знову переглядається для пошуку інших імен констант і макровизначень. При повторному перегляді не розглядається ім'я раніше проведеної макропідстановки. Тому директива

#define a a

не призведе до за циклювання препроцесора.

Приклад 1:

#define WIDTH 80

#define LENGTH (WIDTH+10)

В даному прикладі ідентифікатор WIDTH визначається як ціла константа із значенням 80, а ідентифікатор LENGTH - як текст (WIDTH+10). Кожне входження ідентифікатора LENGTH у програму буде замінено на текст (WIDTH+10), який після розширення ідентифікатора WIDTH перетвориться на вираз (80+10). Дужки дозволяють уникнути помилок в операторах, подібних наступному:

val=LENGTH*20;

Після обробки програми препроцесором текст набуде вигляду:

val=(80+10)*20;

Значення, яке буде присвоєно змінній val рівне 1800. При відсутності дужок значення val буде рівне 280.

val=80+10*20;

Приклад 2:

#define MAX(x,y) ((x)>(y))?(x):(y)

В даному прикладі визначається макровизначення MAX. Кожне входження ідентифікатора MAX в тексті програми буде замінено на вираз ((x)>(y))?(x):(y), в якому замість формальних параметрів x та y підставляються фактичні. Наприклад, макровиклик:

MAX(1,2)

заміниться на вираз ((1)>(2))?(1):(2).

1.18.3 Директива #undef

Синтаксис:

#undef ідентифікатор

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

Після анулювання ідентифікатор може бути знову використаний директивою #define.

Приклад:

#define WIDTH 80

/* … */

#undef WIDTH

/* … */

#define WIDTH 20

1.18.4 Директиви #if, #elif, #else, #endif

Умовна компіляція дає можливість програмісту керувати виконанням директив препроцесора і компіляцією програмного коду. Кожна умовна директива препроцесора обчислює значення цілочисельного константного виразу.

Умовна директива препроцесора #if багато в чому схожа на оператор if. Її синтаксис має вигляд:

#if умова

...

[ #elif умова

…]

[ #elif умова

…]

[ #else

…]

#endif

Умова - це цілочисельний вираз. Якщо цей вираз повертає не нуль (істинно), то фрагмент коду, що розташований між директивою # if і директивою # endif, компілюється. Якщо ж вираз повертає нуль (хибно), то цей фрагмент коду ігнорується і препроцесором, і компілятором.

В умовах, окрім звичайних виразів, можна використовувати конструкцію:

defined (ідентифікатор)

defined повертає 1, якщо вказаний ідентифікатор раніше був визначений директивою # define, і повертає 0 в протилежному випадку.

Кількість директив # elif - довільна. Якщо директива # else присутня, то між нею і директивою # endif на даному рівні вкладеності не повинно бути інших директив # elif.

Приклад 1:

#if defined(CREDIT)

credit();

#elif defined (DEBIT)

debit();

#else

printerror();

#endif

В наведеному прикладі директиви # if, # elif, # else, # endif керують викликом однієї з трьох викликів функцій. Виклик функції credit () скомпілюється, якщо визначена іменована константа CREDIT. Якщо визначена іменована константа DEBIT, то скомпілюється виклик функції debit (). Якщо жодна із наведених іменованих констант не визначена, то скомпілюється виклик функції printerror ().

Приклад 2.

#if DLEVEL>5

#define SIGNAL 1

#if STACKUSE == 1

#define STACK 200

#else

#define STACK 100

#endif

#else

#define SIGNAL 0

#if STACKUSE == 1

#define STACK 100

#else

#define STACK 50

#endif

#endif

В другому прикладі показано два вкладених набори директив # if, # else, # endif. Перший набір директив оброблюється, якщо значення DLEVEL більше за 5. В протилежному випадку оброблюється другий набір.

1.18.5 Директиви #ifdef і #ifndef

Синтаксис:

#ifdef ідентифікатор

#ifndef ідентифікатор

Аналогічно директиві # if, за директивами # ifdef і # ifndef може слідувати набір директив # elif і директива # else. Набір директив повинен закінчуватися директивою # endif.

Використання директив # ifdef і # ifndef еквівалентне директиві # if, що використовує вираз з операцією defined (ідентифікатор). Ці директиви підтримуються виключно для сумісності з попередніми версіями компіляторів мови Сі. Тому замість цих директив рекомендується використовувати директиву # if з операцією defined (ідентифікатор).

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

Директива # ifndef протилежна за своєю дією директиві # ifdef. Якщо ідентифікатор не був визначений директивою # define, або його дія відмінена директивою # undef, то умова вважається істинною. В протилежному випадку умова хибна.

1.18.6 Директива #line

Синтаксис:

#line константа ["ім'я_файла"]

Директива препроцесора # line повідомляє компілятору мови Сі про зміну імені програми і порядку нумерації рядків. Ці зміни відбиваються лише на повідомленнях компілятора: файл програми буде тепер іменуватися як "ім'я_файла", а поточний рядок, що компілюється отримує номер, вказаний константою. Після обробки чергового рядка лічильник номера рядка збільшується на одиницю. У випадку зміни номера рядка й імені файла програми директивою # line, компілятор "забуває" їх попереднє значення і продовжує роботу вже з новими значеннями.

Поточний номер рядка і ім'я файла програми доступні в програмі через псевдозмінні з іменами __LINE__ і __FILE__. Ці псевдозмінні можуть використовуватися для виведення під час виконання програми повідомлень про точне місцезнаходження помилки.

Значенням псевдозмінної __FILE__ є рядок, що представляє ім'я файла, заключене в подвійні лапки. Тому для друку імені файлу програми не потрібно заключати сам ідентифікатор __FILE__ в подвійні лапки.

1.19 Динамічні структури даних

Незважаючи на те, що терміни тип даних та структура даних звучать дещо схоже, проте вони мають різний підтекст.

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

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

З динамічних структур даних найчастіше використовуються лінійні списки, стеки, черги та бінарні дерева.

1.19.1 Лінійні списки

Лінійний список - це скінченна послідовність однотипних елементів (вузлів). Кількість елементів у цій послідовності називається довжиною списку. Наприклад:

F=(1,2,3,4,5,6) - лінійний список, його довжина 6.

При роботі зі списками дуже часто доводиться виконувати такі операції:

• додавання елемента в початок списку;

• вилучення елемента з початку списку;

• додавання елемента в будь-яке місце списку;

• вилучення елемента з будь-якого місця списку;

• перевірку, чи порожній список;

• очистку списку;

• друк списку.

Основні методи зберігання лінійних списків поділяються на методи послідовного та зв'язаного зберігання.

Послідовне зберігання списків. Метод послідовного зберігання списків ґрунтується на використанні масиву елементів деякого типу та змінної, в якій зберігається поточна кількість елементів списку.

#define MAX 100 /* максимально можлива довжина списку */

typedef struct

{

int x; /* тут потрібно описати структуру елементів списку*/

} elementtype;

typedef struct

{

elementtype elements[MAX];

int count;

} listtype;

У вищенаведеному фрагменті програми описуються типи даних elementtype (визначає структуру елемента списку) та listtype (містить масив для зберігання елементів та змінну для зберігання поточного розміру списку).

Наводимо приклади реалізації функцій для виконання основних операцій над списками.

1. Ініціалізація списку (робить список порожнім).

void list_reset(listtype *list)

{

list->count=0;

};

2. Додавання нового елементу у кінець списку.

void list_add(listtype *list,elementtype element)

{

if (list->count==MAX) return;

list->elements[list->count++]=element;

};

3. Додавання нового елементу в позицію pos.

void list_insert(listtype *list,int pos,elementtype element)

{

int j;

if (pos<0||pos>list->count||pos>=MAX) return;

for (j=list->count;j>pos;j--)

{

list->elements[j]=list->elements[j-1];

};

list->elements[j]=element;

list->count++;

};

4. Вилучення елемента з номером pos.

void list_delete(listtype *list,int pos)

{

int j;

if (pos<0||pos>list->count) return;

for (j=pos+1;j<list->count;j++)

{

list->elements[j-1]=list->elements[j];

};

list->count--;

};

5. Отримання елемента з номером pos.

int list_get(listtype *list,int pos,elementtype *element)

{

if (pos<0||pos>list->count)

{

return 0;

};

*element=list->elements[pos];

return 1;

};

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

Зв'язане зберігання лінійних списків. Найпростіший спосіб зв'язати множину елементів - зробити так, щоб кожний елемент містив посилання на наступний. Такий список називається односпрямованим (однозв'язаним). Якщо додати в такий список ще й посилання на попередній елемент, то отримаємо двозв'язаний список. А список, перший та останній елементи якого зв'язані, називається кільцевим.

Структуру даних для зберігання односпрямованого лінійного списку можна описати таким чином:

typedef long elemtype;

typedef struct node

{

elemtype val;

struct node *next;

} list;

В даному фрагменті програми описуються декілька типів даних:

elemtype - визначає тип даних лінійного списку. Можна використовувати будь-який стандартний тип даних, включаючи структури.

list - визначає структуру елемента лінійного списку (val - значення, яке зберігається у вузлі, next - покажчик на наступний вузол).

Схематично лінійний односпрямований список виглядає так:

Реалізація основних операцій:

1. Включення елемента в початок списку.

list *addbeg(list *first, elemtype x)

{

list *vsp;

vsp = (list *) malloc(sizeof(list));

vsp->val=x;

vsp->next=first;

first=vsp;

return first;

}

2. Видалення елемента з початку списку.

list *delbeg(list *first)

{

list *vsp;

vsp=first->next;

free(first);

return vsp;

}

3. Включення нового елемента у список.

list *add(list *pred, elemtype x)

{

list *vsp;

vsp = (list *) malloc(sizeof(list));

vsp->val=x;

vsp->next=pred->next;

pred->next=vsp;

return vsp;

}

4. Видалення елемента зі списку.

elemtype del(list *pred)

{

elemtype x;

list *vsp;

vsp=pred->next;

pred->next=pred->next->next;

x=vsp->val;

free(vsp);

return x;

}

5. Друк значень списку.

void print(list *first)

{

list *vsp;

vsp=first;

while (vsp)

{

printf("%i\n",vsp->val);

vsp=vsp->next;

}

}

6. Перевірка, чи порожній список

int pust(list *first)

{

return!first;

}

7. Знищення списку

list *kill(list *first)

{

while (!pust(first)) first=delbeg(first);

return first;

}

Стеки

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

Стек реалізує принцип LIFO (last in - first out, останнім прийшов - першим пішов). Найбільш наглядним прикладом організації стеку може бути дитяча пірамідка, де додавання і знімання кілець здійснюється як раз відповідно до цього принципу.

Основні операції, які можна виконувати над стеками:

• додавання елемента в стек;

• вилучення елемента із стека;

• перевірка, чи порожній стек;

• перегляд елемента у вершині стека без видалення;

• очистка стека.

Стек створюється так само, як і лінійний список, так як стек є частковим випадком односпрямованого списку.

typedef long elemtype;

typedef struct node

{

elemtype val;

struct node *next;

} stack;

Реалізація основних операцій над стеками:

1. Початкове формування стеку

stack *first(elemtype d)

{

stack *pv=(stack*) calloc(1,sizeof(stack));

pv->val=d;

pv->next=NULL;

return pv;

};

2. Занесення значення в стек

void push(stack **top,elemtype d)

{

stack *pv=(stack*) calloc(1,sizeof(stack));

pv->val=d;

pv->next=*top;

*top=pv;

};

3. Вилучення елемента зі стека

elemtype pop(stack **top)

{

elemtype temp=(*top)->val;

stack *pv=*top;

*top=(*top)->next;

free(pv);

return temp;

};

Черги

Черга - це лінійний список, де елементи вилучаються з початку списку, а додаються в кінець (як звичайна черга в магазині).

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

Черга є частковим випадком односпрямованого списку. Вона реалізує принцип FIFO (first in - first out, першим прийшов - першим пішов).

Черги створюються аналогічно до лінійних списків та стеків.

typedef long elemtype;

typedef struct node

{

elemtype val;

struct node *next;

} queue;

1. Початкове формування черги

queue *first (elemtype d)

{

queue *pv=(queue*) calloc(1,sizeof(queue));

pv->val=d;

pv->next=NULL;

return pv;

}

2. Додавання елемента в кінець

void add (queue **pend, elemtype d)

{

queue *pv=(queue*) calloc(1,sizeof(queue));

pv->val=d;

pv->next=NULL;

(*pend)->next=pv;

*pend=pv;

}

3. Вилучення елемента з кінця

elemtype del(queue **pbeg)

{

elemtype temp=(*pbeg)->val

queue *pv=*pbeg;

*pbeg=(*pbeg)->next;

free(pv)

return temp;

}

1.19.4 Двійкові дерева

Бінарне дерево - це динамічна структура даних, що складається з вузлів (елементів), кожен з яких містить, окрім даних, не більше двох посилань на інші бінарні дерева. На кожен вузол припадає рівно одне посилання. Початковий вузол називається коренем дерева (рис 1.23.).

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

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

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

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

function way(дерево)

{

way(ліве піддерево);

обробка кореня;

way(праве піддерево);

};

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

Таким чином, дерева пошуку можна використовувати для сортування значень. При обході дерева вузли не видаляються.

Для бінарних дерев визначені наступні операції:

• включення вузла у дерево;

• пошук по дереву;

• обхід дерева;

• видалення вузла.

Для кожного рекурсивного алгоритму можна створити його нерекурсивний еквівалент.

Вузол бінарного дерева можна визначити як:

typedef struct sbtree

{

int val;

struct sbtree *left,*right;

} btree;

Реалізація деяких операцій з бінарними деревами.

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

btree *Search(btree *p, int v)

{

if (p==NULL) return(NULL); /* вітка порожня */

if (p->val == v) return(p); /* вершина знайдена */

if (p->val > v) /* порівняння з поточним вузлом */

return(Search(p->left,v)); /* ліве піддерево */

else

return(Search(p->right,v)); /* праве піддерево */

}

2). Включення значення в двійкове дерево (рис 1.33.):

btree *Insert(btree *pp, int v)

{

if (pp == NULL) /* знайдена порожня вітка */

{

btree *q = (btree*) calloc(1,sizeof(btree));

/* створити вершину дерева */

q->val = v; /* і повернути покажчик */

q->left = q->right = NULL;

return q;

}

if (pp->val == v) return pp;

if (pp->val > v) /* перейти в ліве піддерево */

pp->left=Insert(pp->left,v);

else

pp->right=Insert(pp->right,v);

/* перейти в праве піддерево*/

return pp;

}

3). Рекурсивний обхід двійкового дерева:

void Scan(btree *p)

{

if (p==NULL) return;

Scan(p->left);

printf("%i\n",p->val);

Scan(p->right);

}