1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J

Във функционално отношение функцията е част от програмата, с изпълнението на която се получават определени резултати. Чрез използването на функции една програма може да се раздели на отделни модули. Предимствата на модулния подход са следните:

• 
  модулите могат да се програмират независимо един от друг;
  
• 
  модулите могат много лесно да се тестват за грешки и да се модифицират;
  
• 
  могат да се използват вече готови програми, оформени като модули;
  
• 
  логиката на цялата програмата става по-разбираема.
  

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

1. 
   Приложения в проблемната област.
   
2. 
   Модули, реализиращи основните операции над данните.
   
3. 
   Примитивни операции – конструктори, мутатори, селектори.
   
4. 
   Избор на представянето на данните.
   

При съставните типове данни, данните представляват редица от компоненти. Скаларните типове, поддържани в C++ са следните: булев, цял, реален, символен, изброен, указател, псевдоним. Съставните типове, поддържани в C++ са следните: масив, вектор, запис.

Нека T е име или дефиниция на тип. За типа T, T* е тип, наречен указател към T. Множеството от стойностите на типа T* се състои от адресите на променливите от тип T, заедно със специалната константа NULL (нулев указател), която може да бъде свързана с всеки указател, независимо от типа T. За променливите от тип указател се разпределят 4 байта памет.

Нека T е име или дефиниция на тип. За типа T, T& е тип, наречен псевдоним на T. Множеството от стойностите на типа T& се състои от всички вече дефинирани променливи от тип T.

Дефинирането на променлива от тип T& задължително е с инициализация – дефинирана променлива от тип T. След това не е възможно променливата-псевдоним да стане псевдоним на друга променлива.

Променливa, това е място за съхранение на данни, което може да съдържа различни стойности от някакъв определен тип. Идентифицира се със зададено от потребителя име. Една променлива се дефинира като се зададат нейното име и типа на стойностите, които може да приема. Типът определя броя на байтовете, в които ще се съхранява променливата. Мястото в паметта, където е записана стойността на променливата се нарича адрес на тази променлива. По-точно адресът на променливата е адресът на първия байт от множеството байтове, отделени за променливата. Намирането на адреса на една променлива става чрез унарния префиксен оператор & (амперсанд) със следния синтаксис: &<променлива>, където <променлива> е име на вече дефинирана в програмата променлива.

Адресите на променливите от един тип T могат да се присвояват на променливите от тип T* - указател към T.

*<променлива_от_тип_указател>. С други думи, този оператор извлича стойността на адреса, записан в променливата от тип указател с име <променлива­_­от_тип_указател>. Ако променливата-указател е от тип T*, то резултатът от прилагането на оператора * е данна от тип T – всички операции допустими за типа T са допустими и за нея.

Да разгледаме следния фрагмент.

int *p;

double *q;

p = p + 1;

q = q + 1;

Операторът p = p+1; свързва p не с предишната стойност на p, увеличена с 1, а с предишната стойност на p, увеличена с 1*4, където 4 е броят на байтовете, необходими за записването на данна от тип int (p е указател към int). Аналогично, q = q+1; увеличава стойността на q с 1*8, а не с 1, тъй като q е указател към тип double (8 байта са необходими за записване на данна от този тип). Общото правило е следното: ако p е указател от тип T*, стойността на p+i е p+i*sizeof(T), където sizeof (T) е функция, която намира броя на байтовете, необходими за записване на данна от тип T. При изваждането нещата стоят по аналогичен начин.

int i, j, k;

int * const b = &i;

b е константен указател към тип int и той не може да променя стойността си, но чрез него може да се променя стойността на i;

const int *c = &j;

c е указател към константа от тип int и той може да променя стойността си, но чрез него не може да се променя стойността на j;

const int * const d = &k;

d е константен указател към константа от тип int – той не може да променя стойността си и чрез него не може да се променя стойността на k, може да служи единствено за извличане на стойността на k.

Нека a е масив, дефиниран по следния начин:

int a[100];

Тъй като a е указател към a[0], то *a е стойността на a[0], т.е. *a и a[0] са два различни записа на стойността на първия елемент на масива. Тъй като елементите на масива са разположени последователно в паметта, a+1 е адресът на a[1],

a+2 е адресът на a[2] и т.н. a+99 е адресът на a[99]. Тогава *(a+i) е друг запис на a[i] (i = 0, 1, …, 99). Има обаче една особеност. Имената на масивите са константни указатели. Заради това, някои от аритметичните операции, приложими над указатели не могат да се приложат за масиви. Такива са ++, -- и присвояването на стойност. Използването на указатели е по-бърз начин за достъп до елементите на масива и заради това се предпочита. Индексираните променливи правят кода по-ясен и разбираем. В процеса на компилация всички конструкции от вида a[i] се преобразуват в *(a+i), т.е. операторът за индексиране се обработва от компилатора чрез адресна аритметика.

Името на двумерен масив е константен указател към първия елемент на едномерен масив от константни указатели. Ще изясним с пример казаното. Нека a е двумерния масив, дефиниран така:

int a[10][20];

Тогава a е константен указател към първия елемент на едномерния масив a[0], a[1], …, a[9], като всяко a[i] (i = 0, 1, …, 9) е константен указател към a[i][0]. При това положение имаме следните еквивалентни записи: **a  a[0][0], *a  a[0], *(a+1)  a[1], …,

*(a+9)  a[9], по-общо a[i]  *(a + i) (i = 0, 1, …, 9),

a[i][j]  (*(a + i))[j]  *(*(a + i) + j).

Ще разгледаме най-общото разпределение на оперативната памет за изпълнима програма на C++. Това разпределение зависи от изчислителната система, от типа на операционната система, а също от модела памет. Най-общо се състои от: програмен код, област на статичните данни, област на динамичните данни и програмен стек.

В частта програмен код е записан изпълнимият код на всички функции, изграждащи потребителската програма. В областта на статичните данни са записани глобалните обекти на програмата. За реализиране на динамични структури от данни се използват средства за динамично разпределяне на паметта. Чрез тях се заделя и се освобождава памет в процеса на изпълнение на програмата, а не преди това (при нейното компилиране). Тази памет е областта на динамичните данни. Програмният стек съхранява данните на функциите на програмата. Неговите елементи са блокове от памет, съхраняващи данни, дефинирани в някаква функция, които се наричат стекови рамки.

Ще разгледаме примерен фрагмент, който изчислява най-големият общ делител на две естествени числа. За целта дефинираме две функции: gcd (x, y), която намира най-големият общ делител на x и y и main, която се обръща към gcd

int gcd (int x, int y)

{ int h ;

while (y != 0)

{ h = x;

y = h % y;

}

return x;

int main ()

{ int a = 14, b = 21;

int r = gcd (a, b);

return 0;

}

Описанието на функцията gcd прилича на това на функцията main. Заглавието определя, че gcd е двуаргументна целочислена функция с цели аргументи. Името е произволен идентификатор, в случая е направен мнемоничен. Запазената дума int пред името на функцията е нейният тип (по-точно е типът на резултата на функцията). В кръгли скоби и отделени със запетая са описани параметрите x и y на gcd. Те са различни идентификатори и се предшестват от типовете си. Наричат се формални параметри за функцията. Тялото на функцията е блок, реализиращ алгоритъма на Евклид за намиране на най-големия общ делител на естествените числа x и y. Завършва с оператора

чрез който се прекратява изпълнението на функцията като стойността на израза след return се връща като стойност на gcd в мястото, в което е направено обръщението към нея.

Дефинициите на функциите main и gcd се записват в областта на паметта, определена за програмния код. Изпълнението на програмата започва с изпълнението на функцията main. Чрез първия ред от тялото на main се дефинират целите променливи

a и b, като на a се присвоява стойност 14 и на b стойност 21.

В тази последователност те се записват в дъното на програмния стек в стековата рамка на main. Чрез следващия oператор се дефинира цялата променлива r, като в стековата рамка на main, веднага след променливата b се отделят четири байта, в които ще се запише резултатът от обръщението gcd (a, b) към функцията gcd. Променливите a и b се наричат фактически параметри за това обръщение. Забелязваме, че типът им е същия като на съответните формални параметри x и y.

Сега ще опишем как се изпълнява обръщението gcd (a, b).

В програмния стек се генерира нов блок памет – стекова рамка за функцията gcd. Обръщението се осъществява на два етапа. Първият етап е свързването на формалните с фактическите параметри. В стековата рамка на gcd се отделят по четири байта за формалните параметри x и y в обратен ред на реда, в който са записани в заглавието. В тази памет се откопирват стойностите на съответните им фактически параметри. Отделят се също четири байта за т.н. return-адрес, адреса на мястото в main, където ще се върне резултатът, а също се отделя памет, в която се записва адресът на стековата рамка на извикващата функция (в случая main). И така на този етап формалните параметри x и y се свързват съответно със стойностите 14 (стойността на a) и 21 (стойността на b). Вторият етап е изпълнението на тялото на функцията gcd. На първата стъпка се заделя памет четири байта за дефинираната променлива h във върха на стековата рамка за gcd. Тъй като е в сила y != 0, стойността на h става 14, след това стойността на x става 21 и след това стойността на y става

14 % 21 = 14. С други думи, тук x и y размениха стойностите си.

На следващата итерация на цикъла отново y != 0, така че стойността на h става 21, стойността на x става 14 и след това стойността на y става 21 % 14 = 7. Отново y != 0, така че отново се изпълнява тялото на цикъла – стойността на h става 14, стойността на x става 7, стойността на y става 14 % 7 = 0. Това е последната итерация на цикъла и той приключва. Изпълнението на оператора return x; преустановява изпълнението на gcd като връща в main в мястото на прекъсването (return-адреса) стойността 7 на обръщението gcd (a, b). Отделената за gcd стекова рамка се освобождава. Указателят към върха на стека сочи края на стековата рамка на main. Изпълнението на програмата продължава с инициализацията на променливата r. Резултатът от обръщението gcd (a, b) се записва в отделената за r памет. След това се изпълнява оператора return 0; след което се освобождава и стековата рамка на main.

Функцията gcd реализира най-простото и чисто дефиниране и използване на функции – получава входните си стойности единствено чрез формалните си параметри и връща резултата си чрез оператора return. Забелязваме, че обръщението gcd (a, b) работи с копия на стойностите на a и b, запомнени в x и y, а не със самите a и b. В процеса на изпълнение на тялото на gcd, стойностите на x и y се променят, но това не оказва влияние на стойностите на фактическите параметри a и b. Такова свързване на формалните с фактическите параметри се нарича свързване по стойност или още предаване на параметрите по стойност.

При него фактическите параметри могат да бъдат не само променливи, но и изрази от типове, съвместими с типовете на съответните формални параметри.

В редица случаи се налага функцията да получи входа си чрез някои от формалните си параметри и да върне резултат не по обичайния начин (чрез оператор return), а чрез същите или други параметри. Ще разгледаме примерен фрагмент, който разменя стойностите на две реални променливи. Идеята е следната – ако дефинираме функция swap (double *x, double *y), която разменя стойностите на реалните променливи, към които сочат указателите x и y, то обръщението swap (&a, &b) би разменило стойностите

на a и b.

void swap (double *x, double *y)

{ double work = *x;

*x = *y;

*y = work;

return;

}

int main () {

swap (&a, &b);

return 0;

}

Функцията swap има подобна структура като на gcd. Но и заглавието и тялото и са по-различни. Типът на swap е указан чрез запазената дума void. Това означава, че функцията не връща стойност чрез оператора return. Затова в тялото на swap е пропуснат израза след return. Формалните параметри са указатели към double, а в тялото се работи със съдържанието на тези указатели. Забелязваме също, че обръщението към swap във функцията main не участва като аргумент на операция, а е оператор. Изпълнението се осъществява подобно на изпълнението на по-горния фрагмент с малки разлики – при първия етап на изпълнението на обръщението към swap в отделената памет за формалните параметри x и y се записват адресите на съответните им фактически параметри. Поради тази причина, промяната на стойностите, към които сочат формалните параметри x и y води до промяна на самите фактически параметри. Функцията swap получава входните си стойности чрез формалните си параметри и връща резултата си чрез тях. Забелязваме, че обръщението swap (&a, &b) работи не с копия на стойностите на a и b, а с техните адреси. В процеса на изпълнение на тялото на swap се променят стойностите на фактическите параметри a и b. Такова свързване на формалните с фактическите параметри се нарича свързване по указател или предаване на параметрите по указател или свързване по адрес. При този вид предаване на параметрите, фактическите параметри задължително са променливи указатели или адреси на променливи.

void swap (double &x, double &y)

{ double work = x;

x = y;

return;

int main () {

double a = 1.5, b = 2.75;

swap (a, b);

return 0;

}

Специфичното при изпълнението на фрагмента е следното – при първия етап от изпълнението на обръщението към swap, тъй като формалните параметри x и y са псевдоними на променливите

параметър a и аналогично параметърът y се закача за фактическия параметър b. Така всички действия с x и y в swap всъщност се изпълняват с фактическите параметри a и b от main съответно. Да забележим, че фактическите параметри, съответстващи на формални параметри-псевдоними при всички случаи са променливи. Тази реализация на swap е по-ясна от съответната с указатели. Тялото и реализира размяна на стойностите на две реални променливи без да се налага използването на адреси.

Възможно е в една програма, към една функция да се извършват обръщение на място, което предшества нейната дефиниция. В този случай дефиницията на функцията, която извършва това обръщение трябва да се предшества от декларацията на използваната функция. Декларацията на една функция се състои от нейното заглавие, последвано от ‘;’. В него имената на формалните параметри могат да се пропуснат.

Типът на една функция е произволен без масив, но се допуска да е указател. Ако е пропуснат, се подразбира int.

Списъкът от формалните параметри на една функция (още се нарича сигнатура) може да е празен или void. В случай, че е непразен, имената на параметрите трябва да са различни. Те заедно с името определят еднозначно функцията. Възможно е също един формален параметър да се специфицира със запазената дума const, което означава че неговата стойност няма да бъде променяна в рамките на тялото на функцията.

Операторът return връща резултата на функцията в мястото на извикването. Синтаксисът е следния: return [<израз>];. Тук return е запазена дума, <израз> е произволен израз от тип, съвместим с типа на функцията. Ако типът на функцията е void, <израз> се пропуска. Семантиката е следната: пресмята се стойността на <израз>, конвертира се до типа на функцията и връщайки получената стойност в мястото на извикването на функцията, прекратява нейното изпълнение. Да отбележим, че ако функцията не е void, тя задължително трябва да върне стойност. Това означава, че операторът return трябва да се намира във всички клонове на тялото.

Функциите могат да се дефинират в произволно място на програмата, но не и в други функции. Така за разлика от други езици за процедурно програмиране, в C++ не се допуска влагане на функции.

При стартирането на една програма се създава стековата рамка на главната функция, която се поставя в дъното на програмния стек. Във всеки момент от изпълнението на програмата, във върха на стека е стековата рамка на функцията, която се обработва в момента. Непосредствена под нея в стека стои стековата рамка на функцията, извършила обръщението към функцията, която се обработва в момента. Когато изпълнението на една функция завърши, стековата рамка на функцията, съответна на това обръщение се отстранява от стека.
Идентификаторите в C++ означават имена на константи, променливи, формални параметри, функции, класове. Най-общо казано има три вида области на идентификаторите – глобална, локална и област на клас. Областите се задават неявно – чрез позицията на дефиницията на идентификатора в програмата. Област на клас няма да разглеждаме.

Глобалните идентификатори са дефинираните извън дефинициите на функции променливи и константи и могат да се използват във всички функции на програмата, чиято дефиниция следва тяхната такава.

Повечето константи и променливи са локални идентификатори и имат локална област на действие. Те са дефинирани вътре във функциите и не са достъпни за кода в другите функции на модула. Областта им се определя според следното общо правило – започва от мястото на дефинирането и завършва в края на оператора (блока), в който е дефиниран идентификатора. Формалните параметри на функцията също имат локална видимост. Областта им на действие е цялото тяло на функцията. В различните области могат да се използват еднакви идентификатори. Ако областта на един идентификатор се съдържа в областта на друг идентификатор, първият се нарича нелокален за последния. В този случай е в сила правилото: Локалният идентификатор скрива нелокалния в областта си.

Освен чрез механизма за свързване на формалните параметри с фактически и чрез предаване на резултат чрез оператора return, функциите могат да обменят помежду си данни чрез глобални променливи. Първите два начина са основни и са за предпочитане, тъй като с тях се постигат по-ясни и разбираеми програми. От друга страна, използването на глобални променливи е по-ефективно, тъй като не изисква заместване.

Използването на глобални променливи обикновено се счита за лоша практика поради тяхната нелокалност: една глобална променлива потенциално може да се модифицира от всяко място в програмата и всяка част от програмата може да зависи от нея. Въпреки това, в някои случаи, глобалните променливи са подходящи за употреба, тъй като те могат да се използват за избягване на предаването на често използвани променливи в рамките на няколко функции. Ще разгледаме пример с една проста програма.

#include

int global = 3;

void ChangeGlobal ()

{ global = 5; }

int main ()

{ cout << global << endl;

ChangeGlobal();

cout << global << endl;

return 0;

}

Тъй като променливата global е глобална, няма нужда тя да се предава като параметър за да може да се използва от функции, различни от главната функция. Глобалната променлива може да се използва във всяка функция на програмата.

3

5

Езикът C++ поддържа две конструкции, които позволяват да се реализират рекурсивни алгоритми – това са структури с рекурсия и рекурсивни функции.

struct list {

int value;

list *next;

};

Указателят next, описан в тялото на структурата list сочи към променлива – структура от тип list. Тази структура може да се използва за реализация на едносвързан списък.

Под косвено обръщение разбираме следното – функцията F₁ извиква функцията F₂, функцията F₂ извиква функцията F₃, …, функцията F_n-1 извиква функцията F_n и след това функцията F_n извиква функцията F₁.

Сега ще разгледаме примерен фрагмент, който съдържа рекурсивна функция и ще проследим как той се изпълнява. Фрагментът ще пресмята m! за цяло число m, m  0.

int fact (int n)

{ if (n == 0) return 1;

else return n * fact (n-1);

}

int main ()

int n = fact (m);

return 0;

}

В тази фрагмент е описана рекурсивна функция fact, която приложена към цяло неотрицателно число връща факториела на числото. При изпълнението на програмата интересно е извършването на обръщение към fact с фактически параметър m, който има стойност 4.

се изпълнява операторът в else-частта, при което се извършва обръщение към fact с фактически параметър n-1, т.е. fact (3). По такъв начин преди завършването на първото обръщение към fact се прави второ обръщение към тази функция. За целта се генерира нова стекова рамка за новото обръщение към функцията fact, в която за формалния параметър n се откопира стойност 3.

Тялото на функцията fact започва да се изпълнява втори път (временно спира изпълнението на тялото на функцията fact, предизвикано от първото обръщение към нея). По аналогичен начин възникват още обръщения към функцията fact. При последното от тях, стойността на формалния параметър n е равна на 0 и тялото на fact се изпълнява напълно. В резултат, изпълнението на това обръщение завършва и за стойност на fact се връща 1. Тази стойност се връща в непосредствено предишното извикване на fact, което изчислява 1*1 = 1 и аналогично се извършва връщане назад по веригата от извикванията на fact, докато се стигне до първото извикване, което изчислява 4*6 = 24 и връща тази стойност в главната функция. Естествено, след завършването на всяко изпълнение на fact, стековата рамка, която отговаря за това изпълнение се освобождава.
В този конкретен случай, рекурсивното дефиниране на функцията факториел не е подходящо, тъй като съществува лесно итеративно решение. Ще отбележим, че тъй като в тялото на рекурсивната функция fact има само едно обръщение към fact, то тогава всяко извикване на fact поражда най-много едно извикване на fact.

Затова функцията fact още се нарича линейно рекурсивна.

Когато в тялото на една рекурсивна функция има повече от едно обръщение към самата нея и при това съществува извикване на функцията, което поражда повече от едно извикване към същата функиция, то рекурсивната функция се нарича разклонено рекурсивна. Пример е рекурсивната функция за изчисляване на n-тото число на Фибоначи (n естествено), която се дефинира така:

int fib (int n);

{ if (n == 0 || n == 1) return 1;

else return fib (n-2) + fib (n-1);

}

В случая всяко извикване на fib поражда две независими извиквания на fib, което води до експоненциална сложност на рекурсивния алгоритъм. От друга страна, съществува елементарен итеративен алгоритъм, който решава задачата с линейна сложност.

Съществуват обаче задачи, които се решават трудно ако не се използва рекурсия.

Простотата и компактността на рекурсивните функции проличава особено при работа с динамичните рекурсивни структури данни (които се дефинират чрез рекурсивни структури): свързан списък, стек, опашка, дърво. Основен недостатък на рекурсивните програми е намаляването на бързодействието поради загуба на време за копиране на параметрите в стека. Освен това се изразходва повече памет, особено при по-дълбока степен на вложеност на рекурсията.

Едно общо правило при създаването на рекурсивни функции е следното: когато реализираме рекурсия, във функцията трябва да има гранични условия за излизане от рекурсията, които задължително се достигат след краен брой вложени извиквания на рекурсивната функция. В противен случай се получава безкрайно зацикляне и обикновено програмата приключва аварийно поради препълване на програмния стек. За повишаване на ефективността на рекурсивните функции, всички локални променливи и параметри във функцията, които се използват само преди първото рекурсивно обръщение могат да се изнесат извън функцията като глобални.

По този начин се избягва излишното им повторно създаване в новата стекова рамка при изпълнение на рекурсивното обръщение.

Ще отбележим, че за всеки итеративен алгоритъм лесно може да се построи рекурсивен алгоритъм, който решава същата задача. Обратното също е вярно, тъй като е възможно рекурсията да се моделира итеративно, но само чрез използване на достатъчно голям потребителски стек.

За да илюстрираме подхода ще създадем програма за

рационално-числова аритметика. В програмата се дефинират функции за събиране, изваждане, умножение и деление на рационални числа по общоизвестните правила. Тези операции лесно могат да се реализират, ако има начин за конструиране на рационално число по зададени две цели числа, представящи съответно неговия числител и знаменател и ако има начини за извличане на числителя и знаменателя на рационално число.

Затова в програмата се дефинират следните функции:

void makerat(rat &r, int a, int b) – конструира рационално число r по зададени числител a и знаменател b;

int numer (rat &r) – извлича числителят на рационалното число r;

int denom (rat &r) – извлича знаменателят на рационалното число r.

В тези декларации rat е името на типа рационално число. Все още не знаем как са дефинирани трите функции, но ако предположим, че те са реализирани, то функциите за рационално-числова аритметика и процедурата за извеждане на рационално число могат лесно да се реализират. Например, функцията за събиране се реализира така:

rat sumrat (rat &r1, rat &r2)

{ rat r;

denom (r1) * denom (r2));

return r;

}

Останалите операции subrat, multrat, quotrat за изваждане, умножение и деление на рационални числа се реализират аналогично. Функцията за извеждане се дефинира така:

{ cout << numer (r) << ‘/’ << denom (r) << endl; }

Сега ще се върнем към представянето на рационалните числа, а също към реализация на примитивните операции: конструктора makerat и селекторите numer и denom. Тъй като рационалните числа се представят чрез наредена двойка от цели числа, удобно е използването на структура:

struct rat {

int num;

int den;

Тогава примитивните функции, които реализират конструктора и селекторите имат вида:

void makerat (rat &r, int а, int b)

{ r.num = a;

r.den = b;

}

int numer (rat &r)

int denom (rat &r)

{ return r.den; }

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

…

rat r1, r2, r3;

makerat (r2, 3, 4);

r3 = sumrat (r1, r2);

printrat (r3);

…

След изпълнението на този фрагмент ще се изведе 10/8.

• 
  използване на рационалните числа в проблемната област (намиране на сумата на 1/2 и 3/4);
  
• 
  реализиране на правилата за рационално-числова аритметика (sumrat, subrat, multrat, quotrat, printrat);
  
• 
  избор на представяне за рационалните числа и реализиране на примитивни конструктори и селектори (makerat, numer, denom);
  
• 
  работа на ниво структура.
  

void makerat (rat &r, int a, int b)

{ if (a == 0) { r.num = 0; r.den = 1; }

else { int aa = (a > 0) ? a : -a;

int ab = (b > 0) ? b : -b;

int g = gcd (aa, ab);

if ((a > 0 && b > 0) || (a < 0 && b < 0))

{ r.num = aa/g; r.den = ab/g; }

else { r.num = – aa/g; r.den = ab/g; }

}

С това проблемът със съкращаването на рационални числа е решен. За неговото решаване се наложи малка модификация, която засегна само конструктора makerat. Така илюстрирахме лесната модифицируемост на програмите, реализиращи подхода абстракция със структури данни.

За всеки тип данни е известно множество от допустимите стойности и множество от вградените функции и операции, допустими за този тип. Така възниква усещането, че представянето на рационално число като запис с две полета трябва да се обедини с примитивните операции (makerat, numer, denom). Последното е възможно, тъй като в C++ се допуска полетата на структура да бъдат функции. За да направим това в нашия пример извършваме следните стъпки:

1. 
   Включваме декларациите на makerat, numer и denom в дефиницията на структурата rat, като елиминираме формалният параметър r и в трите функции.
   

struct rat {

int num;

int den;

int numer();

int denom();

};

2. 
   Отразяваме промените в дефинициите на функциите makerat, numer и denom – премахваме формалният параметър r и пред името на всяка от тези функции поставяме името на структурата rat и операцията за разрешаване на достъп ::.
   

void rat::makerat (int a, int b)

{ if (a == 0) { num = 0; den = 1; }

else { int aa = (a > 0) ? a : -a;

int ab = (b > 0) ? b : -b;

int g = gcd (aa, ab);

if ((a > 0 && b > 0) || (a < 0 && b < 0))

{ num = aa/g; den = ab/g; }

else { num = – aa/g; den = ab/g; }

}

int rat::numer ()

int rat::denom (rat r)

{ return den; }

Функциите makerat, numer, denom при тази модификация се наричат член-функции на структурата rat. Извикването им се осъществява като полета на структура, например (r е променлива от тип rat) r.makerat(1, 5), r.denom(), r.numer().

Сега забелязваме, че във функциите sumrat, subrat, multrat, quotrat и printrat не се използват полетата на записа num и den, но ако направим опит за използването им даже на ниво main, той ще бъде успешен. Последното може да се забрани, ако се използва етикетите private: пред дефиницията на полетата num и den и public: пред декларациите на член-функциите. Структурата rat приема вида:

struct rat {

private:

int num;

public:

int numer();

int denom();

};

Опитът за използване на полетата num и den на структурата rat извън нейните член-функции води до грешка.

Така естествено достигнахме до понятието клас.

• 
  декларация на класа;
  
• 
  дефиниция на неговите член-функции (методи).
  

Достъпът до членовете на класовете може да се разглежда на следните две нива:

• 
  ниво член-функции;
  
• 
  ниво външни функции.
  

След като един клас е деклариран, трябва да се дефинират неговите методи. Член-данните на един клас се дефинират в рамките на тялото на класа. За член-функциите има два варианта: дефинират се в тялото на класа или извън тялото на класа, като във втория случай в тялото на класа се посочват само техните прототипи. Когато една член-функция се дефинира извън тялото на съответния клас, нейното име трябва да се предшества от името на класа, към който принадлежи член-функцията, последвано от бинарната операция за разрешаване на достъп.

В случай, че една член-функция на клас е дефинирана вътре в тялото на класа, тя се разглежда като вградена функция (inline).

Ще отбележим, че в тялото на дефиницията на член-функция явно не се използва обектът, върху който тя ще се приложи. Той участва неявно – чрез член-данните на класа. Поради това той се нарича неявен параметър на член-функцията. Останалите параметри, които участват явно в дефиницията на член-функцията се наричат явни. Всяка член-функция има точно един неявен параметър и нула или повече явни.

• 
  името на обекта в дефиницията е последвано от скоби, в които е поместен списък от начални стойности – тези стойности се предават като параметри в подходящ конструктор на класа;
  
• 
  името на обекта е последвано от знак за равенство и друг, вече дефиниран обект от класа.
  

При прекия достъп се използва името на обекта и името на данната или метода, разделени с ‘.’. При косвения достъп се използва името на указател към обекта и името на данната или метода, разделени с ‘->’. Двата метода за достъп са взаимнозаменяеми: x.a  (&x) -> a, px -> a  (*px).a.

При създаването на обекти на един клас, кодът на методите на този клас не се копира за всеки обект, а се намира само на едно място в паметта. Естествено, възниква въпросът по какъв начин методите на един клас разбират за кой обект на този клас са били извикани. Отговорът на този въпрос дава указателят this. Всяка член-функция на клас поддържа допълнителен неявен формален параметър указател this от тип <име_на_клас>*. Това става по следния начин: компилаторът преобразува всяка член-функция на клас до обикновена функция с уникално име и допълнителен параметър указателят this и вътре в тялото на тази функция преките обръщения към членове на класа се преобразуват към косвени обръщения чрез this, съответно, след това, компилаторът преобразува всяко обръщение към член-функция на класа в програмата до обръщение към съответната обикновена функция, като за фактически параметър, отговарящ на формалния параметър this се използва адресът на обекта, за който е била извикана член-функцията.
Създаването на обекти е свързано със заделяне на памет, запомняне на текущо състояние, задаване на начални стойности и други дейности, които се наричат инициализация на обекта. В езика C++ тези действия се изпълняват от специален вид член-функции на класовете – конструкторите. Конструкторът е член-функция, която се отличава от останалите член-функции по следните характеристики:

• 
  името на конструктора съвпада с името на класа;
  
• 
  типът на резултата на конструктора не се указва явно в неговата декларацията – винаги се подразбира, че е типът на указателя this;
  
• 
  конструкторът се изпълнява автоматично при създаване на обекти;
  
• 
  конструкторът не може да се извиква явно чрез обект или косвено чрез указател към обект.
  

В заглавието на един конструктор при неговата дефиниция, непосредствено след списъка с формалните параметри може да има инициализиращ списък. Чрез този списък член-данни на класа могат да се свържат с начални стойности. Инициализиращият списък е съставен от имена на член-данни на класа, последвани от скоби, в които е записана началната стойност на съответната член-данна, като отделните елементи на списъка се разделят със запетаи и в началото му се записва символът ‘:’. В конструктора една член-данна може да се инициализира или чрез инициализиращия списък или вътре в тялото на конструктора. По обясними причини за константните член-данни е възможен само първият начин за инициализация.

В рамките на една програма може да се извършва предефиниране на функции, което означава използване на функции с еднакви имена в една и съща област на видимост. При осъществяване на извикване към предефинирана функция, компилаторът търси варианта на функцията с възможно най-добро съвпадение. Като критерии за добро съвпадане имаме следните нива на съответствие: точно съответствие (по брой и тип на формалните и фактическите параметри) и съответствие чрез разширяване на типа на някои от параметрите. В един клас може да се дефинират няколко конструктора. Всички те имат едно и също име (името на класа), така че трябва да се различават по броя и/или типа на своите параметри. При създаването на един обект се изпълнява точно един от предефинираните конструктори. Кой конкретен конструктор да се изпълни се определя съгласно критерия за най-добро съвпадение.

В един клас може явно да е дефиниран, но може и да не е дефиниран конструктор. Във втория случай автоматично се създава т.н. конструктор по подразбиране. Този конструктор реализира множество от действия като: заделяне на памет за данните на обект, инициализиране на някои системни променливи и др. В първия случай, т.е. когато за класа има дефиниран поне един конструктор, тогава конструктор по подразбиране не се създава автоматично и за да може да се дефинират обекти без да се инициализират, потребителят сам трябва да дефинира подразбиращ се конструктор – той няма параметри или всичките му параметри са подразбиращи се.

Инициализацията на новосъздаден обект от даден клас може да зависи от друг обект на същия клас. За да се укаже такава зависимост се използва знакът за присвояване или скоби, в които се записва името на обекта-инициализатор. Самата инициализация в този случай се извършва от специален конструктор, наречен конструктор за присвояване (конструктор за копие). Този конструктор поддържа точно един параметър от тип const <име_на_клас> &. Ако в един клас явно не е дефиниран конструктор за присвояване, компилаторът автоматично създава такъв, в първия момент когато се наложи новосъздаден обект от класа да се инициализира с обект от същия клас. Освен при инициализация чрез обект, конструкторът за присвояване се използва и при предаване по стойност на обект като аргумент на функция, а също и при връщане на обект като резултат от изпълнение на функция. Изрично ще отбележим, че конструкторът за присвояване се използва само в описаните случаи, но не и при присвояване на един обект на друг извън инициализация. В последния случай се използва предефинираната операция за присвояване.