Instrumente pentru definirea structurilor abstracte de date

Instrumente pentru definirea structurilor abstracte de date

Definirea operatiilor pentru tipuri abstracte de date

Pana acum am vazut cum se implementeaza operatiile unui ADT ca functi 757g68h i membre ale clasei ADT. Anumite operatii este mai natural sa le implementam ca functii obisnuite (membre).

// Fisierul "curs3-1.cpp"

// Programul urmator este un exemplu simplu de clasa.

#include <iostream.h>

class zi_din_an

;

int egal(zi_din_an data1, zi_din_an data2);

// Preconditie: data1 si data2 au valori

// Postconditie: Returneaza true daca data1 este

// aceeasi cu data2, si false in caz contrar.

int main()

int egal(zi_din_an data1, zi_din_an data2)

zi_din_an :: zi_din_an(int noua_zi, int noua_luna)

zi_din_an :: zi_din_an()

int zi_din_an :: obtine_ziua()

int zi_din_an :: obtine_luna()

void zi_din_an :: citire()

void zi_din_an :: afisare()

Vrem sa comparam doua date din an (zi,luna). Putem face acest lucru cu o functie care nu este gunctie membru.

In acest exemplu, functia egal compara doua obiecte de tip zi_din_an. Putem face functia egal ca fiind membra a clasei zi_din_an. Insa functiile membre sunt asociate unui obiect al clasei respective (apelul unei functii membre f() a unei clase C se face astfel C.f() ). Deci este dificil sa definim intr-o clasa functia membru egal (deoarece aceasta este compusa din 2 obiecte de tip zi_din_an).Functii friend (prietene)

Daca definim o clasa impreuna cu functii de acces, atunci putem folosi functiile de acces pentru definirea unei functii de testare a egalitatii a 2 obiecte nu pentru alt tip de calcule care depind de variabilele membre

private. (in cazul exemplului nostru, functiile obtine_ziua() si obtine_luna() sunt functii de acces).

Totusi codul este mai simplu si mai eficient definit daca accesam direct datele azi.zi si azi.luna (si nu prin intermediul functiilor de acces).

O functie friend a unei clase nu este o functie membru a acelei clase, dar ea are acces la membrii privati ale acelei clase ca o functie membru.

Declararea functiei egal ca functie friend se face scriind in definitia clasei zi_din_an:

friend int egal (zi_din_an data1, zi_din_an data2); Detalii in exemplul de mai jos:

// Fisierul "curs3-2.cpp"

// Programul urmator este un exemplu simplu de clasa.

#include <iostream.h>

class zi_din_an

;

int main()

int egal(zi_din_an data1, zi_din_an data2)

zi_din_an :: zi_din_an(int noua_zi, int noua_luna)

zi_din_an :: zi_din_an()

int zi_din_an :: obtine_ziua()

int zi_din_an :: obtine_luna()

void zi_din_an :: citire()

void zi_din_an :: afisare()

Deci pentru a declarara o functie friend, trebuie sa scriem in declaratia clasei prototipul functiei precedat de cuvantul friend. Prototipul ei poate fi plasat atat in sectiunea private, cat si in sectiunea public, dar aceasta va fi o functie public in ambele cazuri (de accea este mai clar sa se scrie direct in sectiunea public). Asadar am vazut ca putem defini functia egal fara functii de acces, dar folosind friend. Putem defini functie egal doar cu functii de acces, fara a folosi functii friend. In marea majoritate a cazurilor, singurul motiv pentru a face o functie friend este pentru a face definitia functiei mai simpla si eficienta; dar uneori acesta este un motiv rezonabil.

Recomandare: Aveti nevoie de prieteni !

Folosirea de functii membru si functii friend

Daca folosirea de functii de acces versus functii friend era o problema de gust si eficienta, problema declararii unei functii membre sau friend (deci nemembru) nu este chiar asa de simpla. Iata o regula simpla ce poate servi

la alegerea dintre functii membre si nemembre:

folositi o functie membru daca problema ce trebuie rezolvata de catre functie implica doar un obiect;

folositi o functie nemembra daca problema ce trebuie rezolvata de catre functie implica mai mult de un obiect (ex: functia egal din exemplele 1 si 2);

Exemplu:

In continuare, vom prezenta un program C++ care contine definitia unei clase numite Bani, care este un ADT pentru sume in dolari. Pentru memorarea sumei folosim o variabila membru privata tot_centi (de tip long) care reprezinta suma de bani exprimata in centi. Tipul de date abstract Bani contine 2 operatii care sunt functii friend: egal si adunare. Functia adunare intoarce un obiect a carui valoare este suma valorilor celor 2 argumente. Un apel de funtie de forma egal(suma1,suma2) returneaza true daca cele 2 obiecte suma1 si suma2 au valori ce reprezinta aceeasi suma de bani.// Fisierul "curs3-3.cpp"// Program ce descrie clasa Bani

#include <iostream.h>

#include <stdlib.h>

#include <ctype.h>

const int FALSE = 0;

const int TRUE = 1;

// clasa pentru sumele de bani in dolari

class Bani

;

// Prototipul unei functii ce va fi folosite in definitia functiei Bani :: citire.

int cifra_in_int(char c);

// Preconditie: "c" este unul din cifrele '0' pana la '9'

// Returneaza intregul asociat cifrei; de exemplu, cifra_in_int('3') returneaza 3.

int main()

Bani aduna(Bani suma1, Bani suma2)

int egal(Bani suma1, Bani suma2)

Bani :: Bani(long dolari, int centi)

Bani :: Bani(long dolari)

Bani :: Bani()

double Bani :: obtine_valoarea()

// Urmatoarea functie foloseste iostream.h, ctype.h, stdlib.h si constantele TRUE si FALSE

void Bani :: citire(istream& intrare)

else

negativ = FALSE;

// Daca intrarea este valida, atunci "un_caracter" este '$'

intrare >> dolari >> punct_zecimal >> cifra1 >> cifra2;

if ( un_caracter != '$' || punct_zecimal != '.'

|| !isdigit(cifra1) || !isdigit(cifra2) )

centi = cifra_in_int(cifra1) * 10 + cifra_in_int(cifra2);

tot_centi = dolari * 100 + centi;

if (negativ)

tot_centi = - tot_centi;

}

// Foloseste stdlib.h si iostream.h

void Bani :: afisare(ostream& iesire)

int cifra_in_int(char c)

Parametrul const

Un apel pin referinta este mai eficient decat un apel prin valoare. Un parametru valoare este o variabila locala care este initializata cu valoarea argumentului, deci dupa apel exista 2 copii ale argumentului.

In cazul parametrului adresa, parametrul este doar un loc care se inlocuieste cu argumentul, deci exista o singura copie a argumentului. Pentru parametri de tipuri simple (de ex. int, double) diferenta in eficienta este neglijabila, dar pentru parametrii aceasta diferenta poate fi importanata.

Astfel, are sens sa folosim parametri adresa in loc de parametri valoare pentru o clasa, chiar daca functia nu-si schimba parametrul.

Daca folosim un parametru adresa si functia nu schimba valoarea parametrului putem marca acest parametru astfel incat compilatorul sa stie ca acest parametru nu isi schimba valoarea. Pentru aceasta plasam modificatorul const in fata tipului parametrului. Acest parametru se numeste parametru constant. Exemplu: functia aduna din exemplul precedent se rescrie: friend Bani aduna (const Bani &suma1, const Bani &suma2);

De fapt mai exista o posibilitate de a modifica valoarea obiectului apelat.

Am vazut in exemplul precedent:

Bani m; m este un obiect a carui variabila membru private tot_centi = 0 m.citire(cin); dupa acest apel tot_centi va avea valoarea citita de la tastatura sau m = Bani(10,9); Modificatorul const se aplica obiectelor apelate in acelasi mod ca la parametri. Daca avem o functie membru care trebuie sa nu schimbe valoarea obiectului apela, putem marca functia cu modificatorul const scris la sfarsit. Exemplu: class Bani

Acesta trebuie scris nu numai in prototip, dar si in definitia functiei,

adica:

void Bani::afisare(ostream &iesire) const

Supraincarcarea operatorilor

Un operator (binar), cum ar fi +,-,/,% s.a.m.d., este de fapt o functie care este apelata folosind o sintaxa diferita pentru scrierea argumentelor sale.

Folosind un operator, argumentele sunt listate inainte si dupa operator; folosind o functie, argumentele sunt scrise in paranteza dupa numele functiei:

operator: a+b (lista in inordine)

+ functie: +ab (de fapt +(a,b) este lista in preordine)

a b calculul expresiei se face folosind lista in postordine

Definitia unui operator este scrisa in acelasi mod ca o definitie de functie, in plus scriind cuvantul rezervat operator inaintea numelui operatorului.

Operatorii predefiniti, cum ar fi +,==, s.a.m.d pot si supraincarcati sciind o noua definitie de functie pentru ei.

Exemplu:

friend Bani operator +(const Bani &suma1, const Bani &suma2);

Regului pentru supraincarcarea operatorilor:

cand supraincarcam un operator, macar un parametru trebuie sa fie de tipul claseiun operator supraincarcat poate fi (dar nu e obligatoriu) un prieten al unei clasenu puteti crea noi operatori. Putem doar sa-i supraincarcam pe cei existentinu putem schimba numarul de argumente pe care ii are un operator. De exemplu % este binar si nu poate fi supraincarcat ca unar;nu putem schimba precedenta unui operator. Un operator supraincarcat are aceeasi precedenta ca operatorul initial. De exemplu, x*y+z inseamna (x*y)+z chiar daca * si + sunt supraincarcati.urmatorii operatori nu pot fi supraincarcati: ., ::, .*, ?:supraincarcarea operatorilor =, [ ], -> va fi prezentata special mai tarziuConstructori pentru conversie de tip automata Exemplu: Bani suma1(100,60),suma2;

suma2 = suma1+25;

suma2.afisare(cout);

Operatorul + este supraincarcat pentru 2 argumente de tip Bani. Totusi se va afisa la ecran $125,60 care este rezultatul corect.

Intrebare: Cum a rezolvat compilatorul aceasta problema de conversie ?!

Variabila suma1 este de tip Bani. Constanta 25 poate si considerata de tip int sau long. Singurul mod in care sistemul stie ca 25 inseamna $25.00 este datorita constructorului Bani::Bani(long dolari)

Deci sistemul converteste automat intregul 25 la o valoare de tip Bani in care variabila membru tot_centi este egala cu 2500.

Astfel sistemul va apela operatorul de supraincarcare + pentru 2 argumente de tip Bani.

Intrebare: Se obtine eroare la urmatoarea instructiune ?

suma2 = suma1 + 25.67;

Supraincarcarea operatorilor unari

Vom supraincarca operatorul - care poate fi unar (operator de negatie) sau binar (operator de scadere).

// Fisierul "curs3-4.cpp"

// Program ce descrie clasa Bani

#include <iostream.h>

#include <stdlib.h>

#include <ctype.h>

const int FALSE = 0;

const int TRUE = 1;

// clasa pentru sumele de bani in dolari

class Bani

;

// Prototipul unei functii ce va fi folosite in definitia functiei

// Bani :: citire.

int cifra_in_int(char c);

// Preconditie: "c" este unul din cifrele '0' pana la '9'

// Returneaza intregul asociat cifrei; de exemplu, cifra_in_int('3') returneaza 3.

int main()

Bani operator +(const Bani& suma1, const Bani& suma2)

Bani operator -(const Bani& suma1, const Bani& suma2)

Bani operator -(const Bani& suma)

int operator ==(const Bani& suma1, const Bani& suma2)

Bani :: Bani(long dolari, int centi)

Bani :: Bani(long dolari)

Bani :: Bani()

double Bani :: obtine_valoarea() const

// Urmatoarea functie foloseste iostream.h, ctype.h, stdlib.h si constantele TRUE si FALSE

void Bani :: citire(istream& intrare)

else

negativ = FALSE;

// Daca intrarea este valida, atunci "un_caracter" este '$'

intrare >> dolari >> punct_zecimal >> cifra1 >> cifra2;

if ( un_caracter != '$' || punct_zecimal != '.'

|| !isdigit(cifra1) || !isdigit(cifra2) )

centi = cifra_in_int(cifra1) * 10 + cifra_in_int(cifra2);

tot_centi = dolari * 100 + centi;

if (negativ)

tot_centi = - tot_centi;

}

// Foloseste stdlib.h si iostream.h

void Bani :: afisare(ostream& iesire) const

int cifra_in_int(char c)

Supraincarcarea lui >> si <<

Operatorul de insertie << folosit de catre cout este similar cu +,- (si altii).

Exemplu:

cout << "Salut\n";

In exemplul de mai sus << are doua argumente: cout si sirul de caractere "Salut\n"

Exemplu:

Bani suma(100);

cout << "Am " << suma << "in buzunar\n"; Aceasta succesiune de operatori de insertie este echivalenta cu:

Bani suma(100);

cout << "Am ";

suma.afisare(cout);

cout << " in buzunar\n";

Problema in supraincarcarea operatorului << este sa decidem ce valoare trebuie sa intoarca expresia: cout << suma.

In exemplul de mai sus, expresia este echivalenta cu: ( (cout << "Am ") << suma) << " in buzunar\n";

Pentru ca evaluarea expresiei sa poata fi facuta, operatorul << trebuie sa returneze primul sau argument, care este un flux de tip stream.

Declararea acestor operatori de supraincarcare (<<,>>) se face astfel:

class Bani

Definirea unui ADT in fisiere separate

Cand se definieste un ADT ca o clasa putem plasa definitia clasei si implementarea functiilor membre in fisiere separate. Putem astfel compila fisierul ADT separat de orice program care foloseste acest ADT si putem folosi

acelasi ADT in orice programe diferite. ADT se scrie in 2 fisiere dupa cum urmeaza:

1.Punem definitia clasei intr-un fisier header numit fisier de interfata (de obiecei el are extensia .h). 2.Definitiile tuturor functiilor si operatorilor de supraincarcare sunt plasati in alt fisier numit fisier de implementare.
Acest fisier trebuie sa includa fisierul interfata de la punctul 1. #include "fisier.h" De obicei aceste fisiere au aceleasi nume, dar extensii diferite. Fisierul de implementare este compilat separat inaintea folosirii lui in orice program.

3.Partea principala a programului (functia main(), alte definitii de functii suplimentare, declaratii de constante) se scrie in alt fisier numit fisier de aplicatie. Acesta trebuie, de asemeni, sa includa directiva #include "fisier.h". Fisierul de aplicatie este compilat separat de fisierul de implementare. Executia intregului program necesita link-editarea (unirea de lagaturi) dintre codurile obiect produse de compilarea fisierului de aplicatie si a fisierului de implementare.// Fisierul "curs3-5.h"// Header ce descrie clasa Bani, prototipurile functiilor si operatorilor.

// Acest header se mai numeste si fisier de interfata.

#include <iostream.h>

#include <fstream.h>

#include <stdlib.h>

#include <ctype.h>

const int FALSE = 0;

const int TRUE = 1;

// clasa pentru sumele de bani in dolari

class Bani

;

// Prototipul unei functii ce va fi folosite in definitia functiei

// Bani :: citire.

int cifra_in_int(char c);

// Preconditie: "c" este unul din cifrele '0' pana la '9'

// Returneaza intregul asociat cifrei; de exemplu, cifra_in_int('3') returneaza 3.

// Fisierul "curs3-5.cpp"

// Fisier de implementare care contine definitiile tuturor functiilor si operatorilor de supraincarcare.

#include "curs3-5.h"

Bani operator +(const Bani& suma1, const Bani& suma2)

Bani operator -(const Bani& suma1, const Bani& suma2)

Bani operator -(const Bani& suma)

int operator ==(const Bani& suma1, const Bani& suma2)

Bani :: Bani(long dolari, int centi)

Bani :: Bani(long dolari)

Bani :: Bani()

double Bani :: obtine_valoarea() const

// Urmatoarea functie foloseste iostream.h, ctype.h, stdlib.h si constantele TRUE si FALSE

istream& operator >>(istream& intrare, Bani& suma)

else

negativ = FALSE;

// Daca intrarea este valida, atunci "un_caracter" este '$'

intrare >> dolari >> punct_zecimal >> cifra1 >> cifra2;

if ( un_caracter != '$' || punct_zecimal != '.'

|| !isdigit(cifra1) || !isdigit(cifra2) )

centi = cifra_in_int(cifra1) * 10 + cifra_in_int(cifra2);

suma.tot_centi = dolari * 100 + centi;

if (negativ)

suma.tot_centi = - suma.tot_centi;

return intrare;

}

// Foloseste stdlib.h si iostream.h

ostream& operator <<(ostream& iesire, const Bani& suma)

int cifra_in_int(char c)

// Fisierul "main3-5.cpp"

// Fisier de aplicatii care contine functia main().

#include "curs3-5.h"

int main()

fisier_iesire.open("iesire.dat");

if (fisier_iesire.fail())

fisier_intrare >> suma;

fisier_iesire << suma

<< " copiata din fisierul \"intrare.dat\".\n";

cout << suma

<< " copiata din fisierul \"intrare.dat\".\n";

fisier_intrare.close();

fisier_iesire.close();

return 0;

}

Exercitii si probleme propuse spre implementare

1. Definiti un ADT pentru numere rationale Q= (notatie m/n)

Definiti o clasa Rational care sa contina

- un constructor cu doua argumente int;

- un constructor cu un singur parametru int (numitorul va fi 1);

- un constructor fara argumente care initializeaza obiectul cu 0/1;

- supraincarcarea operatorilor >> si << (numerele se vor citi sub forma m/n, de exemplu 1/2, 15/32, ...). Pot exista si -1/2, 15/-32 sau -30/-45 - supraincarcarea operatorilor de tip Rational (standard):

==,<,>,<=,>=,+,-,* si /;

- definiti ADT in fisiere separate;

- eventual o normalizare (adica pot fi simplificate) adica 4/8 inseamna 1/2

2. Definiti un ADT pentru numere complexe C=.

Reprezentati un numar complex prin partea reala si cea imaginara. Clasa Complex trebuie sa contina:

-un constructor cu 2 parametri de tip double;

-un constructor cu 1 parametru de tip double -> re+0*i;

-un constructor fara argumente care initializeaza un obiect cu 0+0*i;

-supraincarcarea operatorilor ==,+,-,*,>> si <<;

-ADT-ul sa fie definit in fisiere separate;

3. Definiti un ADT pentru urmatoarea structura algebrica (ex. 21/31 Manual, Algebra, cls. XII-a)

A=ZxZ cu legile de compozitie:

(a,b)+(c,d)=(a+c,b+d)

(a,b)*(c,d)=(a*c-b*d,a*d+b-c);

Definiti o clasa Inel care sa "demonstreze" (verifice):

-(A,+,*) -inel comutativ (verificarea se face cu functii friend);

-determinati elementele inversabile ale inelului A;

-aratati ca A Z[i], unde Z[i]=;