Programare Procedurala

Universitatea "Lucian Blaga" din Sibiu Facultatea de Ştiinţe

Prof.univ.dr. Valer Roşca

CAPITOLE DE PROGRAMARE PROCEDURALĂ

Sibiu 2008

Prof.dr.Valer Roşca ULBS

1

Prefaţă Prezenta lucrare, intitulată Capitole de programare procedurală, se adresează studenţilor de la specializarea Informatică, de la Facultatea de Ştiinţe, Universitatea Lucian Blaga din Sibiu. Lucrarea a fost concepută ca manual în sprijinul cursului de Programare procedurală, care se predă în semestrul I al anului I, studiii de licenţă, pentru a acoperi câteva capitole fundamentale de programare. In elaborarea lucrării s-a avut în vedere că există o bogată literatura de specialitate, inclusiv cărţi on-line, în limba română şi în limba engleză, care pot să fie utilizate de studenţi în studiul programării C/C++, dar se simte nevoia, cel puţin pentru o tematică de bază, să se adopte o tratare orientată, mai cu seamă, spre tehnica programării. Cele cinci capitole acoperă aspectele fundamentale cu privire la programarea structurilor dinamice de date (cu referire la liste şi arbori), la lucrul cu fişiere, inclusiv tratarea algoritmicii pentru probleme reprezentative, la modul în care se poate realiza prezentarea grafică a datelor (cu unele elememte de animaţie), la controlul monitorului în modul consolă, cu câteva elemente de programare a sunetelor, pentru a realiza o interfaţă atractivă a programelor şi, lucrarea se încheie, cu un capitol de facilităţi pe care le oferă, în plus, limbajul C++ pentru realizarea programării procedurale. Desigur că lucrarea presupune cunoştinţele de bază pentru programare în limbalul C/C++ şi, prin studiul ei, studenţii pot aprofunda, într-un număr relativ redus de pagini, părţile corespunzătoare din programa disciplinei menţionate. Lucrarea poate fi parcursă secvenţial sau prin selecţie, având la dispoziţie un cuprins sub formă de linkuri interne.

Autor: Prof.univ.dr. Valer Roşca Prof.dr.Valer Roşca ULBS

2

CUPRINS 1. Structuri dinamice de date 1.1 Pointeri 1.1.1 Declararea şi utilizarea pointerilor 1.1.2 Operaţii asupra pointerilor 1.1.3 Echivalenţa indexării şi expresiei cu pointeri. Scăderea pointerilor 1.1.4 Pointerii şi parametrii funcţiilor 1.1.5 Declaraţii cu pointeri şi interpretarea lor

1.2 Variabile dinamice 1.3 Array-uri dinamice 1.4 Liste înlănţuite şi arbori 1.4.1 Liste înlănţuite 1.4.2 Arbori binari

1.5 Realizarea operaţiilor de bază pe liste înlănţuite 1.5.1 Traversarea unei liste 1.5.2 Inserarea într-o listă 1.5.3 Stergere într-o listă 1.5.4 Distrugerea unei liste

1.6 Realizarea operaţiilor de bază pe arbori binari de căutare 1.6.1 Traversarea arborilor binari 1.6.2 Căutarea în arbori binari 1.6.3 Inserare în arbori binari de căutare

1.7 Realizarea programelor care utilizează structuri dinamice 1.8 Un exemplu de utilizare a structurilor dinamice

2. Utilizarea fişierelor 2.1 Tipuri de fişiere admise 2.2 Implementarea lucrului cu fişiere 2.2.1 Streamuri 2.2.2 Controlul unui stream 2.2.3 Modul de lucru cu streamul

2.3 Citire din streamuri text 2.3.1 Citire la nivel de caracter 2.3.2 Citire la nivel de câmp 2.3.3 Citire la nivel de linie

2.4 Scriere în streamuri text 2.4.1 Scriere la nivel de caracter 2.4.2 Scriere la nivel de câmp

Prof.dr.Valer Roşca ULBS

3

2.4.3 Scriere la nivel de linie

2.5 Citire şi scriere în streamuri binare 2.6 Controlul sfârşitului de fişier şi poziţionarea în fişier 2.7 Algoritmica lucrului cu fişiere 2.7.1 Prelucrarea secvenţială 2.7.2 Controlul paginilor în realizarea rapoartelor 2.7.3 Construirea fişierelor binare pentru aplicaţii de evidenţă 2.7.4 Indexarea fişierelor 2.7.5 Prelucrare pe grupe de articole

2.8 Un exemplu de aplicaţie de lucru cu fişier binar

3. Prezentarea grafică a datelor 3.1 Regimul grafic al monitorului 3.2 Utilizarea modului grafic 3.3 Grafică în culori 3.4 Vizor pentru desen 3.5 Desen prin puncte şi vectori 3.6 Raportul de aspect 3.7 Scrierea textelor în modul grafic 3.8 Primitive pentru figuri 3.9 Transformarea coordonatelor 3.10 Elemente de animaţie 3.5.1 Aspecte generale 3.5.2 Facilităţii pentru animaţie date de sistemul grafic

4. Controlul monitorului şi al difuzorului 4.1 Regimul text al monitorului 4.2 Facilităţi de lucru cu texte în modul pagină 4.2.1 Stabilirea unui mod text al consolei 4.2.2 Utilizarea ferestrelor de scriere

4.3 Facilităţi de sunet

5. Facilităţi în C++ pentru programare procedurală 5.1 Declararea de articole 5.2 Referinţe 5.3 Operatorii de alocare şi de eliberare 5.4 Funcţii cu argumente implicite 5.5 Supraîncărcarea funcţiilor 5.6 Tipuri abstracte de date

Prof.dr.Valer Roşca ULBS

4

1. Structuri dinamice de date Limbajul C, prin mecanismul lucrului cu pointeri, oferă programatorilor facilităţi deosebite pentru construirea şi utilizarea variabilelor dinamice, a listelor şi a arborilor.

1.1 Pointeri Aşa după cum s-a arătat într-un capitol anterior, pointerii sunt variabile de adresă legate de un anumit tip de dată standard sau declarat de programator. Mecanismul utilizării pointerilor oferă o mai mare fexibilitate în folosirea memoriei, decât referirea directă prin variabile statice. Figura 1.1 sugerează modul în care, prin utilizarea adresei dată de un pointer, se accesează valoarea dintr-o altă locaţie de memorie. Referirea locaţiei se face indirect şi tehnica aceasta este denumită referire prin indirectare.

Adresă

Valoare

numepointer

Fig.1.1 – Referirea locaţiilor prin pointeri

1.1.1 Declararea şi utilizarea pointerilor Din punctul de vedere al limbajului, un pointer trebuie, mai întâi, să fie declarat şi apoi să fie încărcat cu adresa locaţiei, înainte de a putea fi utilizat. In secvenţele care urmează, se utilizează pointeri la tipuri standard şi la o structură de date. double x = 3.65, *px, z; int k = 5; struct {int *a; char t; double y;} s, *ps; px = &x; ps = &s;

Prof.dr.Valer Roşca ULBS

5

(*ps).y = 1.2; ps->a = &k; z = *px + ps->y + *(ps->a); Se remarcă modul simplu de utilizare a pointerului px, sub forma *px, pentru a referi valoarea 3.65, din locaţia variabilei x. In cazul utilizării structurilor de date, limbajul oferă forme alternative de scriere care sunt echivalente. In această secvenţă, referirea la variabila y, de forma (*ps).y este echivalentă cu forma ps->y. Programatorii preferă forma ultimă care este mai uşor de înţeles, mai ales atunci când apar indirectări în lanţ, aşa cum este cazul cu referirea valorii la care trimite pointerul a: forma *(ps->a) este mai clară decât forma *((*ps).a). In aceste scrieri * şi -> sunt consideraţi operatori de indirectare şi, în expresii, ei se bucură de proprietatea de asociativitate la dreapta. De aceea, referirile de forma p1->(p2>…->(pn-1->(pn->a))…) pot fi scrise, fără paranteze sub forma p1->p2->…->pn->a şi devin mai clare. 1.1.2 Operaţii asupra pointerilor Limbajul stabileşte operaţiile acceptate aupra variabilelor pointeri, având în vedere structura adresei de memorie ca un cuplu de forma (adresă segment, deplasare în segment), aşa cum este cazul modelelor de memorie cu segmente. De exemplu, o operaţie de adunare între doi pointeri nu este corectă deoarece nu produce o adresă validă, adunarea părţilor de adresă de segment ne având sens. Redăm, în continuare, operaţiile acceptate, cu modul de scriere şi semificaţia acestuia. • Adunarea/scăderea unei constante întregi pozitive se redă prin expresia pointer ± k şi este interpretată în raport de tipul pointerului. Adresa rezultat se determină sub forma pointer ± k*sizeof(tip), unde tip este tipul de care este legat pointerul. In particular, adunarea sau scăderea lui k=1 nu înseamnă incrementare/decrementare, ci agăugarea lungimii tipului. Atenţie, deci, la forma de scriere şi la semificaţia expresiei respective ! In secvenţa: double x, *px, *pz; double *py; py = NULL; px = &x; px = px + 4; pz = px; se atribuie lui px adresa x, & fiind operatorul de adresă. Apoi, noua valoare a lui px este adresa lui x mărită cu 4*8 = 32 şi nu cu 4, cum s-ar putea crede din forma instrucţiunii de atribuire. • Atribuirea de valoare are semificaţie pentru oricare pointer, dacă aceasta este valoarea convenţionaă NULL, având semificaţia de adresă nulă. In secvenţa de mai sus, py primeşte o astfel de valoare. Altminteri, unui pointer poate să i se atribuie numai adresa unei variabile de acelaşi tip sau valoarea unui pointer de acelaşi tip. In secvenţa de mai sus, x şi px se referă la acelaşi tip double, de aceea atribuirea px = &x este corectă. Din aceleaşi motiv, este corectă şi atribuirea pz = px. • Compararea se poate face cu valoarea NULL pentru oricare pointer, utilizând operatorii = şi !=. Altminteri, compararea are sens numai pentru pointeri de acelaşi tip şi în expresiile respective pot fi utilizaţi oricare dintre operatorii relaţionali. Pentru secvenţa de mai sus, se pot scrie expresii relaţionale de forma px != py , pz > px etc. 1.1.3 Echivalenţa indexării şi expresiei cu pointeri. Scăderea pointerilor

Prof.dr.Valer Roşca ULBS

6

Aşa după cum se ştie, un array în C are o structură aparte, numele de variabilă dat acestuia fiind considerat un pointer constant la primul element. In aceste condiţii, limbajul a introdus, următoarea echivalenţă: tab[k] ≡ *(tab+k) unde tab este numele variabilei array, iar k este indice. Aplicând regula de semificaţie a expresiei cu pointeri din dreapta, rezultă modul de calcul al adresei şi faptul că, în ambele cazuri, este referit acelaşi element, dar prin forme diferite de scriere. Echivalenţa este valabilă şi pentru array-uri n-domensionale, însă expresia, fiind funcţie de n indici şi de dimensiunile declarate, aşa cum rezultă din modul de liniarizare, prezentat în capitolul referitor la acest tip de date, este mai dificil de utilizat Echivalenţa pune în evidenţă şi posibilitatea de a scădea doi pointeri de acelaşi tip, dacă, în plus, ei au şi aceeaşi adresă de segment, aşa cum este cazul a doi pointeri încărcaţi cu adresele unor elemente din acelaşi array. Dacă se presupune că q=&tab[k] şi p=&tab[k+n], atunci se deduce succesiv: p-q = *(tab+k+n)- *(tab+k) = *(tab+k+n-tab-k) = n. Se observă cum diferenţa, în acest caz, produce ca rezultat un număr natural, reprezentând numărul de componente care se găsesc în array între cele două ranguri. Trebuie semnalat aici că pointerii de tip array fiind pointeri constanţi, nu pot fi modificaţi prin operaţii de adunare cu constante şi nici prin atribuire, dar pot să fie supuşi la acele operaţii care nu le afectează valoarea. 1.1.4 Pointerii şi parametrii funcţiilor In multe situaţii, transferul parametrilor la funcţii se realizează prin adresă, adică prin intermediul pointerilor. După cum se ştie, o astfel de metodă de transfer este obligatorie în cazurile în care funcţia trebuie să modifice valoarea parametrului actual corespunzător, dar ea se utilizează uneori şi în cazul stucturilor de date, pentru a evita multiplicarea datelor prin copiere şi încărcarea suplimentară a timpului de execuţie. In aceste condiţii, protecţia datelor şi a pointerilor împotriva modificărilor accidentale este esenţială. In scrierea funcţiilor care se găsesc în astfel de situaţii, programatorul poate să utilizeze facilităţile pe care le oferă limbajul pentru a declara date constane şi pointeri constanţi, prin utilizarea corespunzătoare a modificatoruli const. Modificatorul const poate fi plasat, într-o declaraţie cu pointeri, în patru poziţii, cu semificaţia care este prezentată cu ajutorul declaraţiilor care urmează: int* pv = 100; // pointer non-const la data non-const int* const pv = 100; // pointer const la data non-const const int* pv = 100; // pointer non-const la data const const int* const pv = 100; // pointer const la data const Dacă transferul prin adresă este făcut pentru structuri voluminoase, în vederea eliminării copierilor costisitoare, parametrul actual se recomandă a fi protejat declarând parametrul formal corespunzător ca o dată constantă. Declaraţia trebuie să fie precedată de modificatorul const, aşa cum se observă în secvenţa care urmează, unde, în funcţia sum(), arrayul x este declarat constant şi orice încercare de modificare a componentelor sale va fi semnalată ca eroare de către compilator. double sum(const double* x, int n) { int k; double s; for(s=1, k=0; k
Prof.dr.Valer Roşca ULBS

7

} Pentru pointeri, la fel ca şi pentru alte variabile, se utilizează modificatorul const, pentru a declara că valoarea pointerului respectiv este nemodificabilă. Caracterul de pointer constant, nu afectează posibilitatea de a modifica valoarea din locaţia referită de pointer. In schiţa de funcţie care urmează, pointerii pp şi chp sunt declaraţi constanţi, în vreme ce pointerul pm nu. Astfel, atribuirea pm=p este corectă, în vreme ce atribuirea pp=pp+4 va determina compilatorul să semnaleze o eroare de sintaxă. Atribuirile constantelor 5.25 şi 'a' sunt corecte, ele referindu-se la valoarea pe care o va conţine locaţia respectivă, referită prin pointer constant. void func(double const* pp, char const* chp, double* pm) { *pp = 5.25; *chp = 'a'; pp = pp +4; /* Atribuire incorecta */ pm = pp; /* Atribuire corecta */ } Se atrage atenţia asupra poziţiei modificatorului const în declararea de pointer constant ! Dacă s-ar face o declaraţie de forma const double* pp, atunci valoarea din locaţie este constantă şi nu poate fi modificată şi compilatorul ar semnala eroare la atribuirea *pp = 5.25. Pentru cazul parametrilor array, problema protecţiei pointerului respectiv este automat rezolvată, dacă declaraţia parametrului este de forma tip numearray[]. In baza echivalenţei indexării cu o expresie cu pointer, aşa cum s-a discutat mai sus, există şi posibilitatea de a declara ca parametru formal un pointer şi acesta să primească, la apelul funcţiei, adresa dată de un pointer la un array, cu elemente de acelaşi tip. In acest caz, se recomandă să se declare parametrul formal ca un pointer constant, pentru a proteja adresa array-ului parametru actual. In secvenţa care urmează, în funcţia prodscal() pointerul pp este automat protejat la modificare, în timp ce pm nu este, deşi ambii au corespondent, la apel, adrese de array. ...... long prodscal(int pp[], int n, int* pm) {long s; int k; s = 0; for(k = 0; k < n; k++) s = s + pp[k] * pm[k]; return s; } ..... void main() { int a[5] = {3, 4, 2, 1, 7}; int b[5] = {-4, 3, 2, 5, 6}; long psc; psc = prodscal(a, 5, b); ....... } Pentru protecţie, este recomandabil ca prototipul funcţiei să se declare sub forma: long prodscal(int pp[], int n, int const* pm).

Prof.dr.Valer Roşca ULBS

8

O atenţie deosebită trebuie acordată situaţiei în care o variabilă pointer din apelator trebuie să poată fi modificată printr-o funcţie. La fel ca în cazul variabileleor obişnuite, este necesar un parametu formal la care să se aplice transferul prin adresă. Un astfel de parametru trebuie declarat ca un pointer, adică el este un pointer la pointer. In secvenţa care urmează, este schiţată o funcţie la care se transferă un astfel de pointer, presupunând cazul unei stive înlănţuite la care se şterge un nod şi, prin această operaţie pointerul pentru topul stivei se modifică. Deoarece parametrii de tipul pointer la pointer, sunt utilizaţi, mai ales, în legătură cu structurile dinamice de date, în această secvenţă, s-a ales un astfel de caz, funcţia free() facând parte din sistemul de alocare a memoriei dinamice. Detalii despre memoria dinamică, sistemul de alocare şi structurile dinamice sunt date în alte paragrafe ale acestui capitol. /* Declararea functiei */ int stergenod(NOD** top) {NOD* p; if(!*top) return 1; p = (*top)->link; free(*top); *top = p; return 0; } /* Apelul functiei */ . . . . . NOD *cap; . . . . . int r = stergenod(&cap); . . . . . In această secvenţă, variabila pointer cap trebuie să se actualizeze ca urmare a ştergerii nodului din vârful stivei. In acest scop, parametrul formal top este declarat pointer la pointer şi trebuie să se supună regulii de indirectare discutate mai sus, pentru a accesa valoarea, aşa cum se observă în instrucţiunile funcţiei. La apel, pentru variabila pointer cap, se transmite subprogramului adresa, la fel ca pentru oricare variabilă obişnuită. Tipul NOD, construit de programator, este un struct ce descrie structura unui element al stivei. De regulă, un element are cel puţin un câmp pentru informaţie şi o adresă care punctează spre elementul următor (link). In multe cazuri, este convenabil ca o funcţie să întoarcă un pointer la o variabilă în care funcţia a construit rezultatul, în locul rezultatului însuşi. Trebuie, însă, acordată atenţie validităţii pointerului, după revenirea din funcţie în apelator, având în vedere existenţa variabilei pe care o desemnează. După cum se ştie, variabilele declarate într-o funcţie sunt variabile locale, de clasă automatic, cărora li se alocă memorie pe stiva sistem în momentul intrării în funcţia respectivă şi memoria ocupată de acestea este automat eliberată înainte de reîntoarcerea la apelator. In aceste condiţii, un pointer la o variabilă locală nu are sens în apelator, deoarece zona de memorie pe care o adresează nu mai există. O primă modalitate de rezolvare a acesteri situaţii, este aceea a schimbării clasei de memorie pentru variabila în cauză, prin declararea ei de clasă static. In acest mod, variabilei respective i se alocă spaţiu în segmentul de date al programului şi aceasta rămâne alocată pe toată durata execuţiei programului. In secvenţa care urmează, se schiţează un astfel de caz şi se sugerează modul de utilizare a rezultatului. double* func(...) {static double x; double* px = &x; . . . . . . . . return px;

Prof.dr.Valer Roşca ULBS

9

} . . . . . . . . double* d, y, z=5.25; d = func(...); y = *d + z; . . . . . . . . O altă modalitate este aceea a construirii unei variabile dinamice în funcţia respectivă, deoarece zona de memorie alocată ei este persistentă, adică aceasta este accesibilă, pe bază de adresă şi după întoarcerea la apelator. In secvenţa care urmează se sugerează acest mod de rezolvare, considerând cazul de mai sus. double* func(...) {double* px; px = (double*)malloc(sizeof(double)); . . . . . . . . return px; } . . . . . . . . double* d, y, z=5.25; d = func(...); y = *d + z; . . . . . . . . In această secvenţă, pointerului px i se atribuie adresa unei zone de memorie dinamică, solicitată sistemului de alocare prin funcţia malloc(). Rezultatul se construieşte în această zonă şi adresa ei este cea care se transmite apelatorului. Pe baza discuţiei de mai sus, se pot face următoarele recomandări pentru transferul parametrilor şi a rezultatului la funcţii: • pentru variabile scalare nemodificabile, transfer prin valore; • pentru structuri voluminoase, transfer prin adresă. Arrayul se transferă implicit prin adresă; • pentru variabile modificabile, indiferent de mărime, transfer prin adresă; • pentru rezultat ca variabilă locală retunare prin valoare: • pentru rezultat în heap, returnare prin pointer; • pentru structuri voluminoase nemodificabile, ca parametru sau ca rezultat, se declară pointer la dată constantă şi/sau rezultat constant aşa cum se sugerează în declaraţia: const tip* func(const tip* pv); 1.1.5 Declaraţii cu pointeri şi interpretarea lor Utilizarea pointerilor, benefică altminteri, poate să aducă şi neajunsuri, printre care semnalăm dificultatea de a descifra programe sursă. Un caz tipic, îl constiuie interpretarea declaraţiilor complexe, pentru care, în cele ce urmează se dă, sub formă de algoritm, un îndrumar. In continuare, se dau câteva exemple, succesiunea entităţilor care se analizează fiind marcate prin numere de ordine 1. Se începe cu identificatorul din declaraţie. 2. Se merge spre dreapta căutând o entitate sub forma unei perechi de paranteze rotunde ( ) sau drepte [ ]. O succesiune de două sau mai multe perechi de paranteze drepte se considerată ca o entitate unică. 3. Dacă s-a selectat o entitate, se interpretează ca funcţie, respectiv array. 4. Se schimbă sensul de deplasare înspre stânga căutând o entitate *, dată de cel mai apropiat caracter de acest fel care nu a fost încă analizat. Dacă * este precedat de modificatorul const, atunci această sucsesiune formează o entitate. Se interprezează entitatea ca indicaţie de pointer sau pointer constant şi se continuă cu deplasare spre stânga.

Prof.dr.Valer Roşca ULBS

10

5. Dacă în căutarea spre stânga, se întâlneşte o paranteză rotundă deschisă (, atunci entitatea care este cuprinsă între această paranteză şi perechea ei dreapta este considerată tratată şi algoritmul se reia de la pasul 2. 6. Dacă în căutarea spre dreapta, se ajunge la o paranteză rotundă închisă ), atunci algoritmul se reia de la pasul 4. 2. Dacă în căutarea spre dreapta, se ajunge la sfârşitul declaraţiei, atunci se încheie căutarea şi se interpretează declaraţia de tip.

Exemplul 1: char* (* ( * var )(int))[10]

7

6

4

2

1

5

3

1. Identificatorul var este declarat ca 2. un pointer la 3. o funcţie care are un parametru întreg şi care returnează 4. un pointer la 5. un array de 10 elemente care sunt 6. pointeri la 2. tipul char

Exemplul 2: double ( * var (double (*)[3])) [5]

5

3

1

2

4

1. Identificatorul var desemnează o funcţie care are un parametru şi returnează 2. un pointer la 3. un array cu 3 componente 4. de tip double Parametrul funcţiei esteun pointer la un array cu 5 componente de tipul double

Prof.dr.Valer Roşca ULBS

11

Exemplul 3:

struct s * (* var[5])[5] 6

5

1

3

2

4

1. Idetificatorul var este 2. un array cu 5 componente care sunt 3. pointeri la 4. un array cu 5 componente care sunt 5. pointeri la 6. tipul struct s

Exemplul 4: unsigned int * ( * const* var [5][10])(void) 7

6

4

3

1

2

5

1. Identificatorul var este 2. o matrice cu 5 linii şi 10 coloane 3. pointeri constanţi la 4. un pointer la 5. o funcţie care nu are parametrii şi returnează 6. un pointer la 2. un întreg fără semn Declaraţiile de funcţii, incluse, se analizează în acelaşi mod, depinzând de poziţia lor. In exemplul care urmează sunt trei funcţii, analiza începe cu funcţia intermediară. De remarcat prezenţa parantezelor care o delimitează, fără care scrierea ar fi fost eronată sintactic.

Prof.dr.Valer Roşca ULBS

12

Exemplul 5:

void ( * var (int,double(*)(int) ) )(int) 5

3

1

2

4

1. Identificatorul var este 2. o funcţie – 1 care are doi parametri şi returnează 3. un pointer la 4. o funcţie – 2 cu un parametru întreg care returnează 5. un void Funcţia 1 are un parametru întreg şi un parametru care este pointer la o funcţie -3 care are un parametru intreg şi returnează un double

1.2 Variabile dinamice La fel ca şi alte limbaje, limbajul C implementează posibilitatea utilizării spaţiului de memorie disponibil, denumit spaţiu de memorie dinamică sau spaţiu heap, potrivit unui model prestabilit pentru memoria internă. Utilizarea acestui spaţiu se bazează pe pointeri, ca variabile prin care se pot accesa locaţii de memorie, denumite blocuri. In plus faţ de cazul static, blocurile de memorie pot să fie controlate - alocate şi eliberate - la momentul execuţiei programului, prin sistemul pe care limbajul îl oferă, denumit sistem de gestiune a memoriei heap. Datorită posibilităţiilor de utilizare şi a posibilităţilor de control, un cuplu (pointer, bloc heap) este denumit variabilă dinamică. Variabilele dinamice pot fi utilizate independent sau pot fi asamblate în structuri de variabile, prin care se pot implementa structuri complexe de date, cunoscute ca structuri dinamice de date. In fig. 1.2, este redat modelul logic al memoriei interne în sistemele de operare DOS (UNIX, MS-DOS), de referinţă pentru implementarea sistemului de gestiune heap.

Prof.dr.Valer Roşca ULBS

13

Spaţiul heap Spaţiul pentru stiva sistem Spaţiul de date statice ale programului Spaţiul pentru codul programului Spaţiul pentru antetul programului

Fig. 1.2 – Modelul logic al memoriei interne pentru un program C Sistemului de gestiune pentru heap pune la dispoziţia programatorului o mulţime de funcţii, prin care programul poate aloca şi elibera, la momentul execuţiei programului, blocuri de memorie, de lungimi variabile, la care să se refere prin pointeri. Mulţimea de funcţii, conform standardului ANSI, conţine un nucleu obligatoriu, la care o anumită implementare a limbajului poate adăuga şi alte funcţii. In acest capitol, se face referire numai la sistemul de gestiune heap recomandat de standard, pentru a asigura construirea de programe portabile. Prototipurile funcţiilor sistemului de gestiune a memorie heap, la fel ca în cazul altor biblioteci, sunt declarate în fişierul header alloc.h care trebuie să fie inclus în programul sursă, atunci când se face uz de acest spaţiu. • Alocarea de blocuri de memorie presupune apelul uneia din funcţiile de alocare/realocare următoare: void * malloc(size_t blocksize); void * calloc(size_t nitem, size_t blockitemsize); void * realloc(void* pblock, size_t blocksize); In aceste prototipuri, size_t este tipul intreg, întâlnit şi la alte funcţii, definit în mai multe fişiere header, printre care şi fişierul alloc.h. Acest tip permite declararea unor întregi foarte mari, întregi care ar putea fi necesari în exprimarea unor cereri de blocuri, având în vedere că lungimile acestora se exprimă în bytes. Lungimea blocului cerut este dată prin parametrul blocksize, în cazul funcţiei malloc() sau este produsul dintre numărul de elemente nitem şi lungimea unui element, în cazul funcţiei calloc(). Ultima funcţie este utilizată, mai ales, în legătură cu alocarea spaţiului pentru array-uri cu număr variabil de componente (array dinamic). Ambele funcţii de alocare întorc adresa blocului, ca pointer nelegat de un tip de dată, pointer void, care poate fi NULL, dacă spaţiul heap liber nu are disponibil un bloc de mărimea cerută. In acest mod, programatorul poate controla, testând valoarea pointerului, dacă alocarea s-a realizat sau nu şi poate decide în consecinţă. Trebuie, de asemenea, remarcat faptul că programatorul trebuie să reţină adresa returnată de alocator, într-o variabilă pointer, legată de tipul de date pe care urmează să-l conţină blocul, pentru utilizare ulterioară. Rezultă, de aici, necesitatea de a converti, prin cast, pointerul void la tipul dorit, ceea ce, poate însemna utilizarea unei alocări de forma:

Prof.dr.Valer Roşca ULBS

14

tip * pblock; if(pblock = (tip*)functiealocare(parametri)) {/* Spatiu alocat. Utilizare pointer pblock */} else { /* Rezolvare situatie de lipsa de spatiu */ } In textul care urmează, se alocă spaţiu pentru un real dublu, pentru un articol, care urmează a fi utilizat ca nod al unei liste, şi pentru un array intreg cu n componente, utilizând o secvenţă fără testare de reuşită: #include #include void main() {......................... /* Definiri de tipuri si de variabile */ double* predab; typedef struct art {char info[50]; art* next; } NOD; NOD* cap; int* arrayint; .......................... /* Alocare de blocuri */ predab = (double*)malloc(sizeof(double)); cap = (NOD*)malloc(sizeof(NOD)); n = 80; arrayint = (int*)calloc(n, sizeof(int)); .......................... /* Utilizarea blocurilor alocate */ *predab = -5.75L; strcpy(cap->info, " "); cap->next = NULL; for(int k = 0; k < n; k++) arrayint[k] = 0; } Aşa cum rezultă din text, se recomandă ca lungimea blocului sau a elementului de bloc, în funcţiile de alocare, să se indice prin operatorul sizeof(), pentru a evita specificarea eronată a lungimii. Se remarcă, de asemenea, modul de conversie şi utilizare, având în vedere tipurile blocurilor şi a câmpurilor pe care acestea le conţin. Funcţia realloc() este utilizată în cazul în care un bloc alocat anterior trebuie să fie reajustat ca mărime, potrivit parametrului blocksize specificat. Funcţia întoarce pointer nul, dacă nu este posibilă realocarea. Dacă se utilizează valoarea NULL, ca parametru pentru pointerul la bloc, atunci această funcţie este echivalentă cu malloc(). Noul bloc poate fi obţinut prin prelungirea vechiului bloc sau poate fi alocat pe un spaţiu nou. In ambele cazuri, conţinutul blocului este conservat până la minimum ditre cele două lungimi. • Eliberarea blocurilor alocate se realizează prin funcţia free() care are un prototip simplu: void free(void* pblock); Pentru exemplele de mai sus, eliberarea se face sub forma: free(predab); free(cap); free(arrayint);

Prof.dr.Valer Roşca ULBS

15

In încheierea acesui paragraf, se face precizarea că implementările limbajului C utilizează, în general o metodă de gestiune a spaţiului heap, denumită garbage collection (colectarea rezidurilor). Potrivit acestei metode, evidenţa spaţiului liber şi ocupat se ţine pe mai multe liste, cu blocuri de mărimi diferite. Alocarea unui bloc, înseamnă scoaterea lui din lista de spaţiu disponibil şi trecerea lui într-o listă de spaţiu ocupat. Atunci când programul cere o eliberare de bloc, blocul respectiv este, de regulă marcat ca disponibil, fără să fie returnat unei liste de spaţiu liber. La anumite intervale de timp, sistemul de gestiune declanşează procesul de eliberare proriu-zis, comasând blocuri adiacente, marcate ca disponibile, pentru a construi blocuri libere de lungime cât mai mare, pe care le evidenţiază în liste corespunzătoare. Acest proces se aplică şi atunci când, la o cerere de alocare, nici una din listele de spaţiu liber nu poate oferi un astfel de bloc. Alocarea eşuează, dacă, şi după colectare (de reziduri), cererea nu poate fi satisfăcută. Prin acest sistem, se asigură o funcţionare, cât mai îndelungată posibil, a programelor care utilizează memoria heap fără a a încărca exagerat timpul de execuţie al programului cu timp necesar procesului de gestiune a acestui spaţiu. In fine, menţionăm că în C++, au fost introduşi operatorii (new, dispose), pentru a facilita utilizarea spaţiului heap, legat, mai ales, de tehnica programării orientate pe obiecte, care sunt prezentaţi în lucrare, în capitolul de facilităţi ale acestui limbaj.

1.3 Array-uri dinamice Aşa după cum se cunoaşte, în limbaj există posibilitatea declarării şi referirii, prin indexare, a array-urilor uni şi multidimensionale. Acestea sunt variabile de clasă automatic al căror spaţiu de memorie le este atribuit în segmentul de date al programului sau pe stiva sistem, la dimensiunile maxime declarate şi acest spaţiu, în timpul execuţiei programului, nu mai poate fi ajustat (mărit sau micşorat) şi nici nu poate fi eliberat, atunci când rolul acelui array a încetat. In programele mari, în condiţiile în care determinarea spaţiului maxim necesar pentru astfel de structuri este dificilă, utilizarea eficientă a memoriei trebuie să fie o preocupare a programatorului. O soluţie posibilă este aceea a construirii de structuri array în memoria heap care să poată fi dinamic ajustate dimensional şi să poată fi eliberate în timpul execuţiei programului. Structurile array construite în heap poartă denumirea de array dinamic. Acestea păstrează proprietatea de spaţiu compact, dar pierd, cu excepţia celor unidimensionale, posibilitatea referirii directe prin indexare. Pentru array-urile unidimensionale, pe baza echivalenţei între expresia de indexare, cu un indice, şi expresia de indirectare asociată, aşa cum s-a arătat mai înainte în acest capitol, există posibilitatea utilizarii alternative a celor două modalităţi. •O primă abordare este aceea a construirii unui array cu spaţiu la dimensiuni efective, care, în timpul execuţiei programului nu mai trebuie ajustat dimensional, denumit array dinamic neajustabil. Formal, un asfel de array este un tuplu de forma (n, psp, bloc), unde n este numărul efectiv (maxim) de elemente, iar psp este pointerul la blocul de spaţiu din heap. După cum se observă, un astfel de array este o variabilă dinamică şi utilizarea lui revine la realizarea următoarei secvenţe de acţiuni: - declararea unui pointer la tipul de dată pe care urmează să îl conţină elementele: tip* psp; - preluarea spaţiului din heap: psp = (tip*)malloc(n*sizeof(tip)); - utilizarea elementelor, fie prin indexare psp[k] , fie prin indirectare *(psp +k), unde k este poziţia( rangul) elementului, în convenţia de referire cu indice întreg, cu valori începând zero. Controlul încadrării în blocul de spaţiu se realizează prin raportarea la valoarea n-1 sau la adresa (psp + n-1), ca adresă a ultimului element ; - eliberarea spaţiului, atunci când array-ul nu mai este necesar: free(psp);

Prof.dr.Valer Roşca ULBS

16

In listingul 1.1, utilizând un array dinamic neajustabil, funcţia main() introduce un şir de n date întregi, utilizând adresarea cu indexare şi le însumează, folosind referirea prin indirectare. Listingul 1.1 – Utilizarea unui array dinamic neajustabil #include #include void main() {int n, k, s; int *psp, *p; printf(" Numarul de componente: "); scanf("%d", &n); psp = (int*)malloc(n*sizeof(int)); printf("Componentele: "); for(k=0; k < n; k++) scanf("%d", &psp[k]); s = 0; for(p = psp; p < (psp + (n-1)*sizeof(int)); p++) s = s + (*p); printf("Suma este %d ", s); } •Cazul general este cel al unui array dinamic ajustabil. Un astfel de array este un tuplu de forma (nelem, pozelem, psp, bloc), unde nelem este numărul maxim de elemente care pot fi înserate în array la dimensiunea curentă a blocului de memorie alocat, iar pozelem dă rangul ultimului element efectiv încărcat. Iniţial, este necesar ca aceste variabile să aibă valorile: nelem = 0; pozelem = -1; psp = NULL; Lucrul cu un astfel de array este ceva mai complicat, deoarece operaţiile de inserare a unui elemente în array pot cere o creştere a spaţiului pe care acesta îl posedă la un anumit moment, inclusiv momentul iniţial, când un asfel de spaţiu nu există. De aceea, pentru un asfel de array este necesar să se construiască funcţii care să poată realiza înserări, cu realocare de spaţiu, precum şi alte operaţii, cum ar fi preluarea elementului de un anumit rang, cu controlul încadrării în limita numărului de elemente efectiv prezente în array. In cele ce urmează, se sugerează o listă de astfel de funcţii care ar putea asigura o funcţionalitate cât mai completă: - funţie pentru înserarea unui element la sfârşit, după ultimul element efectiv prezent; - funcţie pentru înserarea unui element pe o poziţie interioară k, cu deplasarea spre dreapta a elementelor pentru a face loc; - funcţie de înlocuire a valorii unui element de rang k; - funcţie de preluare a valorii ultimului element; - funcţie de preluare a valorii elementuli de rang k; - funcţie de încărcare de array prin citire de la consolă; - funcţi de afişare de array pe monitor, - funcţie de sortare de array etc. In continuare, cu titlu de exemplu, în listingul 1.2 este redată o funcţie de înserare a unui element pe poziţia k şi una de preluare a valorii elementului de rang k. Aici s-a făcut ipoteza, care va fi discutată mai în detaliu într-un paragraf următor, că tuplu care defineşte un

Prof.dr.Valer Roşca ULBS

17

array dinamic ajustabil se defineşte ca un tip de dată struct, pentru date de tip double, de forma: typedef struct {int nelem; int pozelem; double *psp; } DINARRAY; In aceste condiţii, programul apelator declară variabile de tip DINARRAY, atunci când doreşte o astfel de structuri, le iniţializează cum s-a arătat mai sus şi transferă funcţiilor de lucru cu array pointeri de acest tip. De exemplu, aceste acţiuni, cu apelul funcţiei de înserare, sunt sugerate de secvenţa de instrucţiuni care urmează: DINARRAY vectdin, *pvect; vectdin.nelem = 0; vectdin.pozelem = -1; vectdin.psp = NULL; pvect = &vectdin; . . . . . . . . . . . . . . . . . . . . int err = setitemat(pvect, 5, -200.75); Listingul 1.2 – Funcţia de înserare şi funcţia de preluare pentru un array dinamic ajustabil /* Functia de inserare a unui element pe pozitia k */ int setitemat(DINARRAY* pa, int k, double x) {double *r; if(k<0 || k>pa->pozelem) return 2; if(pa->pozelem +1 > pa->nelem) {r = (double*)realloc(pa->psp, (pa->nelem +50)*sizeof(double)); if(!r) return 1; pa->psp = r; pa->nelem += 50; } for(int i= pa->pozelem + 1; i > k; i--) p[i]=p[i-1]; pa->psp[k] = x; pa->pozelem++; return 0; } /* Functia de preluare a valorii elementului de rang k */ int getitemat(DINARRAY* pa, int k, double *x) {if(k<0 || k>pa->pozelem) return 2; *x = pa->psp[k]; return 0; } Se observă că funcţia de înserare verifică, mai întâi, corectitudinea indicelui k şi dacă acesta este în afara limitelor, returnează codul 2. Când înserarea este corect definită, se verifică dacă mai este spaţiu pentru a putea deplasa spre dreapta elementele. Dacă blocul nu are cel puţin un element neocupat, se face o realocare, cu suplimentare a blocului cu 50 de elemente. Dacă realocarea eşuează, funcţia returnează codul 1, pentru a arăta că inserarea nu s-a putut realiza, din lipsă de spaţiu. Dacă blocul a fost realocat, se reîncarcă corespunzător pointerul la spaţiu, deoarece blocul ar fi putut să fie alocat pe alt amplasament şi se modifică numărul maxim de elemente posibile, în noile condiţii. Apoi, se face deplasarea, din poziţia k, spre dreapta cu o poziţie, se înscrie, în poziţia k, valoarea x, se actualizează

Prof.dr.Valer Roşca ULBS

18

informaţia cu privire la poziţia ultimului element prezent şi funcţia returnează codul 0, pentru a marca reuşita. Funcţia de preluare a elementului de rang k, verifică indicile k. Dacă acesta ete incorect, operaţia de preluare eşuează, funcţia întoarce codul 2 şi valoarea lui x este nedeterminată. Dacă preluarea reuşeşte, funcţia returnează codul 0 şi x conţine valoare corectă.

1.4 Liste înlănţuite şi arbori Frecvent, în programele scrise în C, sunt necesare liste înlănţuite şi arbori binari, ca structuri dinamice de date care să faciliteze rezolvarea diferitelor clase de probleme. Cu scopul de a fixa elementele necesare înţelegerii mecanismelor de implementare în limbaj, în acest paragraf, se face o scurtă trecere în revistă a acestor tipuri de structuri. 1.4.1 Liste înlănţuite Listele de date sunt compuse din articole, denumite noduri, dispuse într-o anumită ordine. In fiecare nod, rezidă informaţia propriu-zisă, la care se adaugă o informaţie specială, care să materializeze legătura nodului respectiv cu vecinii săi. Aceasta înseamnă că lista de date trebuie să se construiască într-un spaţiu adresabil, de exemplu heap, informaţia de legătură fiind adresa (adresele) blocului (blocurilor) vecinului (vecinilor). Dacă se notează cu P = {p1, p2, …, pn} mulţimea adreselor din spaţiul de construcţie, la care se adaugă valoarea NULL, pentru a desemna adresa vidă şi se notează cu D = {d1, d2,…, dn} mulţimea informaţiilor care vor fi conţinute de de nodurile listei, atunci se pot defini formal listele simplu şi dublu înlănţuite, după cum urmează. O listă simplu înlănţuită sau listă asimetrică este cuplu (cap, La) unde La este mulţimea { (di, pi) | di є D, pi є P }, pe care s-a definit o relaţie de ordine, cu cap = p0, ca adresă a blocului care conţine perechea (d1, p1), cu pi, 1≤ i ≤ n-1 ca adresă a blocului care conţine perechea (di+1, pi+1) şi cu pn = NULL, pentru perechea (dn, pn). O listă dublu înlănţuită sau listă simetrică este tripletul (prim, Ls, ultim), unde Ls este mulţimea { (pi, di, si) | di є D, pi, si є P }, pe care s-a definit o relaţie de ordine directă, cu Prim = p0, ca adresă a blocului care conţine tuplul (p1, d1, s1), cu pi, 1≤ i ≤ n-1 ca adresă a blocului care conţine tuplul (pi+1, di+1, si+1) şi cu pn = NULL, pentru (pn, dn, sn) şi o relaţie de ordine inversă, cu ultim = pn+1, ca adresă a blocului care conţine tuplul (pn, dn, sn), cu si, unde n ≥ i ≥ 2, ca adresă ablocului (pi-1, di-1, si-1) şi cu s1 = NULL. Convenind să se figureze nodurile prin dreptunghiuri şi legăturile prin săgeţi, cu valoarea NULL ca legare la pământ, cele două tipuri de liste se pot reprezenta grafic aşa cum se arată în fig.1.3.

Prof.dr.Valer Roşca ULBS

19

d1

d2

dn-1

dn

cap

d1

d1

d1

prim

d1

ultim Fig.1.3 – Liste înlănţuite

Figura sugerează că nodurile unei liste simplu înlănţuite pot fi "vizitate" numai într-un singur sens, de la nodul de pointer cap spre nodul cu legătură la pământ (ultimul nod), deoarece, pentru fiecare nod se cunoaşte numai succesorul său imediat. O adtfel de listă, prin convenţie, este vidă, adică nu are nici un nod, atunci când pointerul cap = NULL. Similar, pentru o listă dublu înlănţuită, vizitarea se poate face de la nodul dat de pointerul prim spre nodul ultim, dar şi invers, de la nodul dat de pointerul ultim spre primul nod, deoarece fiecare nod interior are legătură spre succesorul imediat, în ordine directă şi spre predecesorul imediat, în ordine inversă. Dacă lista dublu înlănţuită este vidă, atunci prim = ultim =NULL. Listele cresc dinamic, plecând de la situaţia de listă vidă, adăugând mereu câte un nod şi se micşoreasză dinamic, ştergând câte un nod. Cele două operaţii tipice, denumite adăugare/ştergere sau înserare/ştergere, fac ca, în timpul execuţiei programului respectiv, structura şi numărul de noduri ale listei să sufere o permanentă schimbare. Astfel, o listă poate trece de mai multe ori între situaţia de listă vidă şi nevidă, în general, pe alt amplasament, datorită faptului că, la înserare se solicită un nou bloc, iar la ştergere se eliberează câte un bloc, care, până la o nouă înserare, poate fi ocupat de altă structură. După locul unde se fac cele două operaţii tipice, se disting stivele şi cozile, ca liste particulare, deosebit de utile în programare. Stiva înlănţiută (stack) este o listă asimetrică la care operaţia de înserare şi operaţia de ştergere se fac numai la primul nod (nodul de cap), care, în acest caz este denumit vârful stivei sau top. Datorită acestui comportament sau disciplină de lucru, bine sugerat de modul în care se garează şi se scot vagoanele într-o linie închisă la un capăt, stivele se mai numesc liste LIFO (Last-In-First-Out = ultimul–intrat–primul-ieşit). La o stivă, de regulă se vizitează numai nodul top, dar nu este exclusă vizitarea şi a altor noduri, caz în care vizitarea presupune o operaţie de traversare a stivei, totală sau parţială. Datorită acestui comportament, stiva este o structură frecvent utilizată în diferite probleme care presupun o atare disciplină în lucrul cu datele. Coada înlănţuită (queue) este o listă asimetrică la care operaţia de înserare se face la capătul dat de pointerul ultim, iar operaţia de ştergere se face la capătul dat de pointerul prim. Coada este denumită listă FIFO (First-In-First-Out=primul-intratprimul-ieşit), deoarece materializează comportamentul obişnuit pentru tratarea cozilor cotidiene: cozi de persoane, cozi de automobile etc. Prin analogie cu aceste cozi, capătul la care se face ştergerea este denumit faţa cozii, operaţia de ştergere este denumită servire, iar pointerul spre acest nod este notat fata. Similar, nodul după care se poate face o înserare

Prof.dr.Valer Roşca ULBS

20

este este denumit spatele cozii şi pointerul se notează spate. Tratarea corectă a unei cozi presupune totdeauna doi pointeri, pentru oricare din operaţiile care modifică coada şi este suficentă cunoaşterea unui singur pointer, pointerul de faţă, în cazul unei operaţii de traversare. 1.4.2 Arbori binari Păstrând notaţiile introduse în paragraful anterior, se poate defini formal un arbore binar sau arbore de ordinul doi, utilizând o schemă recursivă. Un arbore binar este cuplul (cap, A2), unde A2 este o mulţime de forma { (pi, di, si) | di є D, pi, si є P } care îndeplineşte următoarele condiţii: 1) există unic nodul de adresă p0 care conţine tripletul (p1, d1, s1), numit nod rădăcina al arborelui şi cap = p0; 2) diferenţa A2 – {( p1, d1, s1)} se descompune în mulţimile A21 şi A22, cu A21∩ A22 = Ø; 3) dacă A21 = Ø, atunci p1=NULL, iar dacă A21 ≠ Ø, atunci există unic (pk, dk, sk) în A21 astfel încât p1 să fie adresa blocului acestui element, numit succesor stânga al lui ( p1, d1, s1) ; 4) dacă A22 = Ø, atunci s1=NULL, iar dacă A22 ≠ Ø, atunci există unic (pr, dr, sr) în A22 astfel încât s1 să fie adresa blocului acestui element, numit succesor dreapta al lui ( p1, d1, s1) ; 5) A21 şi A22 sunt arbori binari. Dacă se reprezintă nodurile arborelui binar la fel ca la liste, se poate obţine o imagine de forma celei din fig.1.4, situaţia de arbore vid fiind marcată convenţional prin valoarea NULL a pointerului cap. Se observă că, într-un arbore binar, fiecare nod are cel mult doi succesori direcţi, iar structura de noduri care derivă din acesta poate fi considerată un arbore, numit subarbore, a cărui rădăcină este nodul considerat. Nodurile arborelui binar care nu au succesori direcţi sunt denumite frunze. De asemenea, trebuie remarcat faptul că în tehnica lucrului cu abori binari se utilizează adesea o terminologie împrumutată din structurile de tip arbore genealogic. Astfel, se vorbeşte de nod tată şi copii săi, pentru a desemna un nod şi succesorii săi direcţi, noduri fraţi şi noduri veri, descendenţi şi ascendenţi etc. La fel ca la liste, operaţiile la arbori se referă la înserarea şi ştergerea de noduri care fac ca un arbore să crească sau să descrească dinamic, dar, din punctul de vedere al realizării, acestea sunt mai complicate. Ambele operaţii solicită o operaţie de traversare parţială, pentru a depista nodul după care trebuie făcută înserarea sau nodul care trebuie şters, operaţie care, de regulă se bazează, pentru identificare, pe informaţia conţinută în noduri. Această categorie de arbori binari, pentru care structura este dată prin relaţia care există între informaţiile distincte pe care nodurile le conţin sunt denumiţi arbori binari de căutare. In continuare, pentru exemplificarea modului de implementare, se consideră, în detaliu, numai această categorie.

Prof.dr.Valer Roşca ULBS

21

cap d1

d2

d3

d5

d4

d6

d7 Fig.1.4 – Arbore binar

Dacă se notează cu info partea din structura unui nod care conţine informaţia, cu llink câmpul de legătură spre succesorul stânga, iar cu rlink câmpul de legătură spre succesorul dreapta, atunci un arbore binar este arbore de căutare dacă, pentru oricare nod de adresă p, diferit de o frunză, sunt adevărate următoarele relaţii de dominare: p->info > p->llink->info; p->info < p->rlink->info. Relaţiile de mai sus trebuie interpretate astfel: oricare nod îşi domină subarborele stânga şi este dominat de subarborele său dreapta. In fig.1.5 este reprezentat un exemplu de astfel de arbore, în care, pentru simplitate, informaţia, de tip caracter, este înscrisă în cerculeţe, iar legăturile sunt redate prin săgeţi.

Prof.dr.Valer Roşca ULBS

22

f

d

b

a

h

e

g

i

c

Fig.1.5 – Arbore binar de căutare

Dacă un astfel de arbore este traversat în întregime, adică se vizitează, într-o anumită ordine, fiecare nod, se poate obţine o listă liniarizată a informaţiilor conţinute în arbore. Traversarea completă a unui arbore binar, inclusiv a arborilor binari de căutare, se poate face în mai multe moduri, după ordinea în care se selectează sucesorii direcţi, în raport cu momentul selectării nodului respectiv ca rădădcină de subarbore. Teoretic, este comod să se definească traversarea în mod recursiv, pe baza subarborelui stânga S, a subarborelui dreapta D şi a rădăcinii R a acestuia, astfel: • traversare în preordine (RSD) – pentru fiecare subarbore se vizitează rădăcina R, se traversează în preordine subarborele stânga S şi apoi se traversează în preordine subarborele dreapta D; • traversare în ordine simetrică (SRD) – pentru fiecare subarbore se traversează în ordine simetrică subarborele stânga S, se vizitează rădăcina R, şi apoi se traversează în ordine simetrică subarborele dreapta D; • traversare în postordine (SDR) – pentru fiecare subarbore se traversează în postordine subarborele stânga S, se traversează în postordine subarborele dreapta D şi apoi se vizitează rădăcina R. Pentru exemplul din fig.1.5 se obţin următoarele liste liniare: f, d, b, a, c, e, h, g, i – pentru preordine (RSD); a, b, c, d, e, f, g, h, i – pentru ordine simetrică (SRD); a, c, b, e, d, g, i, h, f – pentru postordine (SDR). Se obsrvă că lista care se obţine printr-o traversare în ordine simetrică este o listă sortată, de aceea un arbore de căutare traversat complet, în această ordine, poate reprezenta o metodă de sortare, denumită sortare pe arbore binar.

1.5 Realizarea operaţiilor de bază pe liste înlănţuite Asupra listelor se pot realiza diferite operaţii, dar, în cele ce urmează, prezentarea se limitează la operaţiile de traversare, înserare şi ştergere, pentru care este recomandabil şi comod să se construiască funcţii cu parametri.

Prof.dr.Valer Roşca ULBS

23

Oricare program care trebuie să implementeze astfel de operaţii trebuie să definească un tip de dată pentru nodul listei. In modul cel mai simplu, tipul NOD este un articol în care, pentru simplitate, informaţia este considerată ca string. Pentru o listă simplu înlănţuită, tipul poate fi definit astfel: #define n 50 typedef char informatie[n]; typedef struct art {informatie info; struct art* succesor; }NOD; Depinzând de situaţie, definiţia se poate adapta pentru liste dublu înlănţuite şi diferite tipuri de informaţie, inclusiv pentru cazul în care informaţia este un alt articol sau un array dinamic. In ultimul caz, blocul de informaţie fiind variabil, nodul trebuie să conţină un pointer spre spaţiul heap al blocului. 1.5.1 Traversarea unei liste Operaţia de taversare este o operaţie de vizitare a nodurilor listei, în ordinea specifică acesteia. Aceasta se poate realiza, printr-o funcţie, numită funcţie de traversare, ca o traversare totală sau poate fi o traversare parţială de căutare. • Traversarea totală presupune vizitarea tuturor nodurilor, de la capătul ales, până la sfârşitul listei, fără ieşire din funcţia de traversare. Cu fiecare nod localizat, se pot executa prelucrări general valabile, pentru toate nodurile, şi/sau prelucrări specifice, condiţionate, de informaţia conţinută de noduri. Prelucrările care se fac asupra unui nod constituie operaţia de tratare de nod. Dacă este necesar, în raport de informaţia conţinută în nod, nodurile care sunt supuse operaţiei de tratare pot fi alese, operaţia de traversare, în acest caz, fiind denumită traversare totală cu selecţie. In listingul 1.3 este redată, pentru exemplificare, structura unei funcţii de traversare totală cu selecţie, pentru o listă sumplu înlănţuită, în care operaţia de tratare s-a presupus că este realizată de o altă funcţie, denumită tratare(). Listingul 1.3 – Structura generală a funcţiei de traversare a unei liste sumplu înlănţuită cu selecţie int traversare(NOD* inceput, char * infsel) {NOD* p; /* Rezolvarea situatiei de lista vida */ if(!inceput) return 1; /* Traversarea listei nevide */ p = inceput; do {if(conditie-de-selectie) tratare(p); p = p->succesor; } while (p); return 0; } In structura funcţie de traversare, trebuie remarcată, în primul rând, lista de parametri. Parametrul, denumit inceput este un pointer spre nodul cu care se începe traversarea, de regulă, nodul de început - dat de pointerul cap al listei. Inceputul traversării poate fi şi un alt nod, atunci când este necesară o traversare totală a unei subliste terminală a acesteia. Parametrul pointer primit aici este un parametru prin valoare şi este conservat de funcţia de

Prof.dr.Valer Roşca ULBS

24

traversare din motive de semantică, mai ales dacă acesta este pointerul de cap şi, în consecinţă, este introdus un pointer de lucru p, numit pointer de traversare. Parametrul infsel este destinat primirii informaţiei de selecţie, adică a informaţiei cu care se stabileşte, prin expresia denumită conditie-de-selectie, dacă nodul curent va fi tratat sau nu. Condiţia de selectie este specifică, dar aici s-a meţinut presupunerea că informaţia din noduri este un text şi, prin urmare, parametrul trebuie să fie un pointer la char. In al doilea rând, trebuie observat modul în care este conceput codul funcţiei de traversare, din punctul de vedere al asigurării caracterului general al acestei funcţii şi anume tratarea stării listei. Aici, funcţia distinge cele două cazuri, prin rezultatul întreg pe care îl returnează apelatorului: valoarea 1, pentru situaţia de listă vidă şi valoarea 0, dacă lista este nevidă, având cel puţin un nod şi a fost traversată. In al treile rând, se remarcă bucla de ciclare do, pentru controlul traversării, când lista este nevidă. Nodul curent, accesat prin pointerul de traversare p, este livrat sau nu funcţiei tratare(), în raport de valoarea de adevăr a condiţiei de selectie. Apoi, indiferent de caz, se trece la un alt nod, prin linia de avans p = p->succesor care obţine adresa nodului succesor sau valoarea NULL, dacă lista s-a terminat. Funcţia de tratare, prin pointerul p primit, îşi accesează informaţiile din nod şi realizează tratamentul adecvat. Dacă, în listingul 1.3, se renunţă la selecţie, se obţine o funcţie de traversare totală normală, eventual de la ultimul nod spre început, dacă lista este dublu înlănţuită şi se înlocuieşte legătura succesor cu legătura predecesor. •Traversarea parţială este, de regulă, concepută ca o traversare de căutare şi presupune vizitarea în ordine a nodurilor, de la capătul ales, spre sfârşitul listei, pentru a localiza un nod care îndeplineşte o condiţie dată, în raport cu informaţia conţinută. Traversarea listei se termină cu succes, atunci când s-a localizat un astfel de nod (primul, dacă pot exista mai multe noduri care îndeplinesc codiţia impusă) sau fără succes (insucces), dacă un astfel de nod nu există şi a fost atins sfârşitul listei. In listingul 1.4, este redată, pentru exemplificare, structura unei funcţii de căutare, pe o listă simplu înlănţuită, în ipoteza că informaţia din noduri este de tip text. Funcţia returnează apelatorului o adresă sau pointer, prin care îl informează asupra situaţiei întâlnite, pe baza următoarei convenţii: - rezultat = NULL → lista vidă sau insucces; - rezultat ≠ NULL → succes şi rezutatul este adresa nodului găsit. Listingul 1.4 – Structura generală a funcţiei de traversare pentru căutare pe o listă simplu înlănţuită NOD* căutare(NOD* inceput, char * infsel) {NOD *p, *s; s = NULL; p = inceput; /* Rezolvarea situatiei de lista vida */ if(!inceput) return s; /* Traversarea listei nevide */ do {if(conditie-de-cautare) {s = p; break; } else p = p->succesor; } while (p); return s; }

Prof.dr.Valer Roşca ULBS

25

Parametrii au aceeasi semificaţie ca la procedura anterioară, iar conditie-decautare este expresia pe care trebuie să o îndeplinească informaţia din nodul curent, în raport cu informaţia dată de parametrul infsel. Rezultatul căutării se pregăteşte prin pointerul ajutător s care, atunci când lista este nevidă, în bucla do, rămâne pe valoarea NULL, dacă nu există un nod care să satisfacă cerinţa impusă sau primeşte valoarea pointerului p, numit pointer de traversare, dacă nodul curent este cel corespunzător. •Traversarea parţială cu pointer de urmărire este o variantă a traversării de căutare, necesară, de multe ori, în lucrul cu listele simplu înlănţuite când interesează nu numai adresa nodului care îndeplineşte criteriul de căutare ci şi adresa predecesorului imediat al acestuia. Aşa, de exemplu este cazul ştergerii unui nod, când refacerea legăturilor nu este posibilă, dacă nu se posedă şi adresa predecesoruuli nodului care se şterge. In acest tip de traversare, faţă cazul anterior, funcţia de căutare trebuie să prevadă încă un parametru, de tip pointer la pointer la nod, prin care să se returneze adresa predecesorului. In listingul 1.5, este redată structura funcţiei de traversare cu urmărire, unde acest pointer, denumit pointer de urmărire, este parametrul r, declarat sub forma NOD** r. In listingul model, s-au utilizat următoarele convenţii, cu privire la valorile pointerilor: - rezultat NULL, r = NULL → lista vidă; - rezultat NULL, r ≠ NULL → insucces, r conţine adresa ultimului nod a listei; - rezultat ≠ NULL, r = NULL → succes, rezultatul este adresa primului nod al listei şi acesta îndeplineşte criteriul de căutare, nu există predecesor; - rezultat ≠ NULL, r ≠ NULL → succes, rezultatul este adresa nodului care îndeplineşte criteriul de căutare, iar r conţine adresa predecesorului său. Listingul 1.5 – Structura generală a funcţiei de traversare pentru căutare, cu pointer de urmărire, pe o listă simplu înlănţuită NOD* traversarecuurmarire(NOD* inceput, char * infsel, NOD** r) {NOD *p, *s, *pr; s = pr = NULL; p = inceput; /* Rezolvarea situatiei de lista vida */ if(!p) return s; /* Verificarea primului nod */ if(conditie-de-cautare) {s = p; *r =pr; return s; } /* Traversarea listei care are cel putin doua noduri */ pr = p; p = p -> succesor; do {if(conditie-de-cautare) {s = p; break; } else {pr = p; p = p->succesor; } } while (p); *r = pr; return s;

Prof.dr.Valer Roşca ULBS

26

} In funcţiile de căutare, conditie-de-cautare este o expresie care trebuie scrisă pentru nodul curent, adică în raport de pointerul de traversare p. In ipotezele făcute aici, trebuie utilizată funcţia de comparare de şiruri de caractere şi această condiţie se scrie sub forma: strcmp(p->info, infsel) θ 0; unde operatorul relaţional θ se înlociueşte cu unul din operatorii ==, <, >, depinzând de cerinţa pe care trebuie să o indeplinească informaţia din nod faţă de informaţia de selecţie: - informaţia din nod == informaţia de selecţie; - informaţia din nod < informaţia de selecţie; - informaţia din nod > informaţia de selecţie; Trebuie acordată atenţie apelului unei astfel de funcţii care, pe poziţia parametrului r, trebuie să transfere o adresă unei variabile pointer, aşa cu sugerează secvenţa următoare: NOD *inceput, *p, *r; ....... p = traversarecuurmarire(inceput, "textde informatie", &r); 1.5.2 Inserarea într-o listă Inserarea unui nod nou se poate realiza la unul din capetele listei sau în interiorul listei, după sau înaintea unui nod dat. Pentru îndeplinirea unei astfel de sarcini, pentru fiecare caz, se recomandă construirea unei funcţii, numită funcţie de înserare. O astfel de funcţie trebuie să cunoască pointerul sau pointerii care definesc lista, informaţia care trebuie să fie pusă în nod şi, adresa nodului referinţă, dacă înserarea nu se face la un capăt. De regulă, apelatorul are sarcina să posede informaţiile cerute de funcţia de înserare, iar, dacă este necesar apelatorul va realiza traversarea prealabilă a listei, cu căutare, pentru a construi unele din aceste informaţii. Funcţia de înserare trebuie să actualizeze pointerii caracteristici ai listei, dacă înserarea îi afectează, şi să realizeze corect înserarea şi în situaţi în care lista este vidă. La înserare, în general, trebuie avută în vedere situaţia în care se modifică pointerii caracteristici. De aceea, toţi pointerii care vor suferii modificări în funcţia de înserare, modificări care trebuie să se regăsească ca atare în apelator, trebuie să fie declaraţi de tipul pointer la pointer la nod. Corespunzător, la apel, argumentele trebuie să fie adrese de variabile pointeri. • Inserarea în capul listei este specifică stivelor înlănţuite, dar poate fi aplicată şi la o listă oarecare. Din punct de vedere algoritmic, nu ridică probleme deosebite, aşa cum se poate deduce din listingul 1.6, în care se construieşte un model de funcţie pentru o listă simplu înlănţuită, cu informaţie de tip text. Grafic, înserarea în faţă se ilustrează ca în fig.1.6 a. Listingul 1.6 – Structura generală a funcţiei de înserare în capul unei liste simplu înlănţuită int inserareinceput(NOD** inceput, char * infnod) {NOD *p; /* Alocare si pregatire nod */ p = (NOD*)malloc(sizeof(NOD)); if(!p) return 1; strcpy(p->info, infnod); p->succesor = NULL; /* Legarea nodului nou, cu actualizarea pointerului de inceput*/ if(!*inceput) *inceput = p; /* Lista a fost vida */ else { p->succesor = *inceput;

Prof.dr.Valer Roşca ULBS

27

*inceput = p; }; return 0; }

/* Lista a avut cel putin un nod */

In acest listing, parametrul infnod aduce informaţia de pus în nod care, după alocarea de spaţiu - adresa în p - se copiază în nod, legătura acestuia spre succesor fiind iniţializată NULL. Dacă lista este vidă, atunci acest nod devine cap al listei şi pointerul inceput devine egal cu p. Dacă lista are cel puţin un nod, atunci nodul nou p, trebuie să puncteze spre nodul dat de pointerul inceput şi acest pointer se actualizează cu adresa lui p, pentru a arăta noul cap al listei. De remarcat faptul că funcţia testează situaţia de lipsă de spaţiu şi întoarce, ca rezultat, valoarea 1 (adevărat), pentru a marca lipsa de spaţiu şi valoarea 0, dacă alocarea a reuşit. Dacă lista este dublu înlănţuită, atunci funcţia de înserarea are doi pointeri caracteristici (inceput şi sfarsit) care trebuie să figureze în lista de parametri. Funcţia trebuie să iniţializeze la NULL ambele legături ale nodului nou şi să facă legarea acestuia sub forma: /* Lista a fost vida */ *inceput = p; *sfarsit = p; /* Lista a avut cel putin un nod */ p->succesor = *inceput; (*inceput)->predecesor = p; *inceput = p; Dacă lista dublu înlănţuită a fost vidă, funcţia actualizează ambii pointeri caracteristici, pentru a puncta spre nodul nou, ca unic nod al listei. Atunci când lista are cel puţin un nod, trebuie ca fostul nod de inceput să puncteze, prin legătura sa predecesor spre nodul nou p, dar numai pointerul inceput trebuie actualizat, pointerul sfarsit trebuind să rămână cu vechea sa valoare. • Inserarea la sfârşitul listei este specifică cozilor, dar poate fi aplicată şi la o listă oarecare. Din punct de vedere algoritmic, nu ridică probleme deosebite, aşa cum se poate deduce din listingul 1.7, în care s-a construit un model de funcţie pentru o listă simplu înlănţuită, cu informaţie de tip text. Grafic, înserarea în faţă se ilustrează ca în fig.1.6 - b. De remarcat aici faptul că funcţia trebuie să primească pointerii caracteristici ai listei, de inceput şi sfărşit, pe care trebuie să îi actualizeze corespunzător. Dacă lista a fost vidă, ambii pointeri punctează spre noul nod. Dacă lista a avut cel puţin un nod, ultimul său nod trebuie să trimită spre nodul nou, iar pointerul de sfârsit trebuie să arate spre nodul înserat.

Prof.dr.Valer Roşca ULBS

28

a) Inserare în capul listei p 1

inceput

inceput

b) Inserare la sfarsitul listei

p 1

inceput

sfarsit

sfarsit

c) Inserare după un nod dat dupanod

inceput

2

p

1

Fig.1.6 – Inserare în listă asimetrică

Listingul 1.7 – Structura generală a funcţiei de înserare la sfârşitul unei liste simplu înlănţuită int inseraresfarsit(NOD** inceput, NOD** sfarsit, char * infnod) {NOD *p; /* Alocare si pregatire nod */ p = (NOD*)malloc(sizeof(NOD)); if(!p) return 1; strcpy(p->info, infnod); p->succesor = NULL; /* Legarea nodului nou, cu actualizarea pointerului de inceput*/ if(!*inceput) /* Lista a fost vida */ {*inceput = p; *sfarsit = p; } else /* Lista a avut cel putin un nod */ { (*sfarsit)->succesor = p; *sfarsit = p; }; return 0; }

Prof.dr.Valer Roşca ULBS

29

Pentru liste dublu înlănţuite, este necesar să se modififice corespunzător secvenţele de instrucţiuni date în cazul înserării la început, modificând capătul de referinţă, adică înlocuind pointerul spre predecesor cu pointerul spre succesor, astfel: /* Lista a fost vida */ *inceput = p; *sfarsit = p; /* Lista a avut cel putin un nod */ (*sfarsit)->succecesor = p; p->predecesor = *sfarsit; *sfarsit = p; • Inserarea după un anumit nod al listei se aplică la o listă oarecare. In acest caz, funcţia de înserare trebuie să cunoască, în plus faţă de pointerii caracteristici, adresa nodului după care se face înserarea. In cele ce urmează, cu titlu de exemplu, se presupune că funcţia primeşte un pointer dupanod, cu adresa nodului după care se face înserarea şi pe care apelatorul o poate obţine, de exemplu, prin traversare cu pointer de urmărire. Este recomandabil ca funcţia de înserare să considere, de asemenea, situaţia în care se solicită înserarea după un nod dar lista este vidă, adică o situaţie pentru care parametrii inceput =NULL şi dupanod ≠ NULL. In listingul 1.8, în ipoteza că pointerul dupanod este adresa unui nod al listei, este construită funcţia model de înserare, iar situaţia este ilustrată grafic în fig.1.6 – c. Listingul 1.8 – Structura generală a funcţiei de înserare după un nod dat la o listă simplu înlănţuită int inseraredupa(NOD** inceput, NOD* dupanod, char * infnod) {NOD *p; /* Alocare si pregatire nod */ p = (NOD*)malloc(sizeof(NOD)); if(!p) return 1; strcpy(p->info, infnod); p->succesor = NULL; /* Legarea nodului nou */ if(!*inceput) *inceput = p; /* Lista a fost vida */

else /* Lista a avut cel putin un nod */ {p->succesor = dupanod->succesor; dupanod->succesor = p; }; return 0; } Dacă nu există siguranţa că pointerul dupanod conţine o adresă corectă a unui nod al listei când aceasta este nevidă, se poate introduce o secvenţă de verificare prin traversare. Dacă, în traversare, adresa nodului dupanod nu este egală cu adresa nici unui nod al listei, se refuză înserarea şi funcţia reîntoarce valoare 2, ca mesaj de eroare. Dacă lista este dublu înlănţuită, atunci funcţia trebuie să primească ambii pointeri specifici. In cazul de listă nevidă, de exemplu, când înserarea nu se face după ultimul nod, legăturile trebuie modificate astfel:

Prof.dr.Valer Roşca ULBS

30

p->succesor = dupanod->succesor; p->predecesor = dupanod; dupanod->succesor->predecesor = p; dupanod->sucecesor = p; 1.5.3 Stergere într-o listă La fel ca la înserare, ştergerea poate să se refere la nodul din capul listei, la nodul ultim al listei sau la un nod oarecare din interiorul listei. Se pot construi funcţii de ştergere, pentru fiecare caz, eventual cu obligaţia funcţiei de a returna informaţia pe care o conţine nodul ce este şters. In continuare, se presupune această situaţie şi se consideră că informaţia este de tipul text. La fel ca la înserare, ştergerea poate modifica valorile pointerilor caracteristici. De aceea, toţi pointerii care vor suferii modificări în funcţia de ştergere, modificări care trebuie să se regăsească ca atare în apelator, trebuie să fie declaraţi de tipul pointer la pointer la nod. Corespunzător, la apel, argumentele trebuie să fie adrese de variabile pointeri. • Stergerea nodului din capul listei este tipică pentru stive şi cozi, dar se poate utiliza şi în cazul listelor oarecare. Funcţia de stergere trebuie să primească, ca parametri, pointerul sau pointerii caracteristici ai listei şi un pointer la char pentru un spaţiu al al apelatorului în care să primească informaţia din nodul care se şterge. Pentru a distinge dacă informaţia returnată este semificativă, adică lista nu a fost vidă, funcţia trebuie să întoarcă un rezultat 1, dacă lista a fost vidă şi un rezultat 0, în caz contrar. In listingul 1.9 este redată o astfel de funcţie, pentru o listă simplu înlănţuită. Listingul 1.9 – Structura generală a funcţiei de ştergere în capul unei liste simplu înlănţuită int stergecap(NOD** inceput, char* infodinnod) {NOD *p; if(!*inceput) return 1; /* Lista a fost vida */ /* Stergere nod de cap, lista nu este vida */ p = (*inceput)->succesor; strcpy(infodinnod, (*inceput)->info); free(*inceput); *inceput = p; return 0; } Soluţia ca apelatorul să îşi aloce spaţiu pentru a primi informaţia din nodul care se şterge este recomandabilă, pentru ca blocul de memorie să nu rămână ne eliberat după utilizare, aşa cum, de regulă, se întâmplă dacă funcţia de ştergere alocă în heap spaţiul şi returnează la apelator numai adresa acestuia. In acest caz, apelul s-ar putea realiza ca în secvenţa care urmează: char t[10]; int r; . . . . . r = stergecap(&cap, t); • Stergerea nodului ultim al listei este tipică pentru cozi, când funcţia de ştergere trebuie să primească ambii pointerii caracteristici, dar se poate utiliza şi în cazul listelor oarecare. Dacă lista este simplu înlănţuită, funcţia de ştergere trebuie să cunoască şi adresa nodului predecesor al ultimului nod. Pentru a simplifica sarcinile apelatorului, funcţia de

Prof.dr.Valer Roşca ULBS

31

ştergere însăşi poate să execute o traversare care să depisteze predecesorul nodului ultim. Dacă lista este dublu înlănţuită, această adresă este conţinută în structura nodului ultim, în legătura denumită predecesor. Deoarece cozile solicită operaţii frecvente de ştergere, ele se pot proiecta ca liste dublu înlănţuite (decozi - dequeue), pentru ca operaţia de ştergere să se realizeze uşor, fără traversare. In continuare, pentru a arăta în ce constă, din punct de vedere algoritmic, o traversare de stabilire a acestei adrese, se presupune o listă simplu înlănţuită. Listingul 1.10 redă structura funcţiei de ştergere, în acest caz. Listingul 1.10 – Structura generală a funcţiei de ştergere a nodului ultim al unei liste simplu înlănţuită int stergesfarsit(NOD** inceput, char * infdinnod) {NOD *p, *r; infodinnod = NULL; /* Lista a fost vida */ if(!*inceput) return 1; /* Lista are un singur nod si devine vida */ strcpy(infdinnod, (*inceput)->info); free(*inceput); *inceput = NULL; return 0; /* Lista are cel putin doua noduri si se traverseaza */ r = *inceput; p = (*inceput)->succesor; while (p != NULL) /* Traversare */ {r =p; p = p->succesor; } /* Se sterge nodul sfarsit si lista ramane nevida */ strcpy(infdinnod, p->info); free(p); r->succesor = NULL; return 0; } In această funcţie, r este pointerul de urmărire care rămâne în urma pointerului de traversare p şi, în final, dă adresa predecesorului nodului de sfârşit. Pe baza lui, se actualizează la NULL legătura, nodul r devenind nod ultim. • Stergerea unui nod oarecare, de regulă, presupune că nodul de şters se dă prin informaţia pe care o conţine. In acest caz, funcţia de ştergere trebuie să realizeze o traversare cu pointer de urmărire, pentru a obţine adresa nodului de şters şi a predecesorului său. In listingul 1.11, se apelează funcţia traversarecuurmarire(), în care se presupune o condiţie de selecţie pe egal. Se observă modul de apel al acestei funcţii care primeşte pointerul de început (*inceput), informaţia pentru selecţie şi adresa variabilei pointer r (&r). Listingul 1.11 – Structura generală a funcţiei de ştergere a unui nod oarecare al unei liste simplu înlănţuită int stergeoarecare(NOD** inceput, char* infsel, char * infdinnod) {NOD *p, *r; p = traversarecuurmarire(*inceput, infsel, &r); if((p==NULL) && (r==NULL))return 1; /* Lista este vida */ if((p==NULL) && (r!=NULL))return 2; /* Nu exista nodul de sters */ if((p!=NULL) && (r==NULL)) /* Se sterge primul nod */ {strcpy(infdinnod, p->info);

Prof.dr.Valer Roşca ULBS

32

*inceput = p->succesor; free(p); return 0; } if((p!=NULL) && (r!=NULL)) {strcpy(infdinnod, p->info); r->succesor = p->succesor; free(p); return 0; }

/* Se sterge nodul p */

In această funcţie, s-a extins codificarea rezultatului întors, pentru a sesiza şi situaţia când nodul care se cere a fi şters nu există în listă, situaţie ce poate apare, mai ales, datorită informaţiei greşite ce o conţine parametrul infsel. De remarcat corecţia care se aplică asupra pointerului inceput, în cazul în care se şterge primul nod. De asemenea, trebuie acordată atenţie modului în care se apelează funcţia, potrivit unei secvenţe de forma: char t[10]; int n; . . . . . . n = stergeoarecare(&cap,"text", t); Dacă, pentru o astfel de listă, se ţine şi un pointer de sfarşit, denumit sfarsit, atunci funcţia trebuie să îl primească în lista de parametri şi trebuie să distingă cazul când nodul care se şterge este ultimul. In mod corespunzător, secvenţa situaţiei, marcată prin comentariul /* Se sterge nodul p */, trebuie modificată astfel: if(p!=NULL && r!=NULL) /* Se sterge nodul p */ {strcpy(infdinnod, p->info); r->succesor = p->succesor; if(p->succesor==NULL)*sfarsit = r; free(p); return 0; Pentru cazul listelor dublu înlănţuite, funcţiile de ştergere se realizează uşor, lista conţinând informaţii de legătură care facilitează accesarea nodurilor în ambele direcţii. Lăsăm cititorului, ca exerciţiu, realizarea funcţiilor corespunzătoare, având ca model funcţiile scrise la liste simplu înlănţuite. 1.5.4 Distrugerea unei liste După cum se poate uşor constata, la terminarea lucrului cu o listă, aceasta poate să fie nevidă şi, în consecinţă, programul trebuie să elibereze spaţiul ocupat. Această operaţie este denumită distrugere de listă şi ea trebuie să elibereze spaţiul nod cu nod. Operaţia poate fi programată printr-o funcţie adecvată, aşa cum rezultă din listingul 1.12. Listingul 1.12 – Distrugerea unei liste void ditrugelista(NOD* inceput) {NOD* p; while(!inceput) {p = inceput; inceput = inceput->succesor; free(p); } }

Prof.dr.Valer Roşca ULBS

33

1.6 Realizarea operaţiilor de bază pe arbori binari de căutare La fel ca şi la liste, un program care trebuie să implementeze operaţiile pe arbori binari trebuie să definească un tip de dată pentru nodul arborelui. In modul cel mai simplu, tipul NOD este un articol în care, pentru simplitate, informaţia este considerată ca string şi defineşte cele două legături spre succesorii direcţi (stânga = llink, dreapta = rlink): #define n 50 typedef char informatie[n]; typedef struct art {informatie info; art *llink, *rlink; }NOD; Depinzând de situaţie, definiţia se poate adapta pentru diferite tipuri de informaţie, inclusiv pentru cazul în care informaţia este un array dinamic. In ultimul caz, nodul trebuie să conţină un pointer spre spaţiul heap care se alocă array-ului. In cele ce urmează, având în vedere numai tratarea modului în care se pot implementa operaţiile, se insistă asupra operaţiilor de traversare, căutare şi înserare, considerând arborii binari de căutare. Problema distrugerii unui astfel de arbore se abordează în legătură cu exemplul de la sfârşitul capitolului. 1.6.1 Traversarea arborilor binari Traversarea arborilor binari se realizează ca o traversare totală, în una din ordinile definite anterior: preordine, ordine simetrică şi postordine. Traversarea parcurge nodurile, potrivit metodei respective, indiferent de informaţia pe care acestea o conţin. In acest proces, fiecare nod este diponibil, pe rând, pentru a i se aplica operaţiile de tratare dorite. La fel ca în cazul listelor, se presupune că aceste operaţii sunt realizate de funcţia tratare(p), unde p este pointerul la nodul curent disponibil. Traversarea poate fi programată într-o funcţie traversare() care poate fi realizată iterativ sau recursiv. In cele ce urmează se dicută, în detaliu, numai traversarea în ordine simetrică. Pentru celelalte tipuri de traversări, se pot implementa funcţii, într-o manieră analogă, modificând corespunzător funcţia pentru traversare simetrică • Traversarea iterativă în ordine simetrică presupune o funcţie care primeşte un pointer spre rădăcina arborelului şi, la fiecare nod vizitat, apelează funcţia de tratare pe care o oferă programul. Deoarece legăturile în arbore sunt totdeauna de la un nod părinte spre succesorii săi direcţi, o traversare în ordine simetrică (SRD) presupune ca după ce s-a vizitat, în ordine simetrică, subarborele stânga, să se revină la rădăcina acestuia, adică să se facă o revenire în sens invers direcţiei legăturii lleft. Acest lucru nu este posibil, decât dacă rădăcinile subarborilor, în ordinea în care se trece prin ele înainte, sunt memorate. Dacă memorarea acestora se realizează într-o stivă înlănţuită, atunci drumul înapoi se poate reconstitui extrăgând adresele de noduri în ordine inversă memorării, adică exact aşa cum lucrează o astfel de listă. In listingul 1.13, în care se prezintă codul funcţiei de traversare, stiva de lucru are partea de informaţie de tip adresă, denumită adrnodarbore, partea de legătură este denumită urmator, iat vârful stivei este gestionat prin pointerul top. Pentru a distinge cele două tipuri de noduri, tipul pentru nodul arborelui este denumit NODABORE, iar cel al stivei de lucru este NODSTIVA. In fine, se face ipoteză simplificatoare, că există spaţiu heap suficient pentru a putea construi stiva şi pentru cea mai lungă ramură a arborelui. Dealtfel, ipoteza este plauzibilă, dacă se are în vedere că la o ramură de 10000 de noduri, sunt necesari 80000 de bytes sau cca. 80 KB, ceea ce, pentru memoriile actuale este un spaţiu mic.

Prof.dr.Valer Roşca ULBS

34

Listingul 1.13 – Structura funcţie de traversare iterativă în ordine simetrică a unui arbore binar void traversareSRD(NODARBORE* cap) {NODSTIVA *top, *r; NODARBORE *p; p=cap; top=NULL; do { while(p!=NULL) /* Pune adresa nodului arborelui in stiva */ {r = (NODSTIVA*)malloc(sizeof(NODSTIVA)); r->adrnodarbore = p; r->urmator = top; top = r; p = p->llink; /* Deplasare spre stanga */ } /* Extrage o adresa de nod al arborelui din stiva */ if(!top) {p = top->adrnodarbore; top = top->urmator; r = top; free(r); tratare(p); /* Tratare nod p */ p = p->rlink; /* Deplasare spre dreapta */ } } while(p != NULL || top != NULL); } Dacă se urmăreşte codul funcţiei, se constată că stiva creşte, iniţial de la stivă vidă, pe măsură ce se face o deplasare spre stânga în arbore (p = p->llink), până la un nod care are succesor stânga vid. In momentul când un astfel de nod a fost introdus în stivă, deplasarea stânga se opreşte, se extrage nodul din vârful stivei, acesta se tratează, prin funcţia tratare(p) şi apoi se face o schimbare a direcţiei de deplasare (p = p->rlink), spre subarborele dreapta al nodului tratat. Ciclul este reluat cu punerea în stivă a nodului rădăcină al acestui subarbore şi acesta este traversat spre stânga, până la un nod cu succesor stânga vid etc, atâta timp cât cel puţin unul dintre pointerul p şi pointerul top sunt nenuli, adică mai există noduri ne vizitate. • Traversarea recursivă în ordine simetrică poate fi o tratare mai simplă, din punct de vedere algoritmic, aşa cum rezultă din listingul 1.14. O astfel de abordare, deşi extrem de simplă, poate să nu dea satisfacţie, pentru arbori voluminoşi, având în vedere spaţiul de memoriei al stivei sistem, mult mai redus decât spaţiul heap şi necesarul de memorie mai mare pentru a memora în stivă stările de întrerupere, potrivit tehnicii de execuţie a funcţiilor recursive. Listingul 1.14 - Structura funcţie de traversare recursivă în ordine simetrică a unui arbore binar void traversareSRD(NODARBORE* k) {if(k->llink != NULL) traversareSRD(k->llink); tratare(k); if((k = k->rlink)!= NULL) traversareSRD(k); }

Prof.dr.Valer Roşca ULBS

35

1.6.2 Căutarea în arbori binari Aşa după cum s-a arătat într-un paragraf anterior, la arborii binari de căutare, structura este definită de o relaţie de dominare definită pe informaţia conţinută în noduri. Acest tip de arbore îşi găseşte utilizarea în programele care stochează iniţial informaţii care posedă o astfel de structură şi apoi, la diferite momemte de timp, verifică dacă o anumită informaţie este deja achiziţionată. Datorită modului de memorare, pentru mulţimi mari de informaţii, un arbore de căutare poate fi mai eficient, ca timp mediu de căutare, decât o stocare a acestor informaţii ca un array, la care trebuie adăugată şi facilitatea ca arborele să crească dinamic, prin inserare, atunci când o informaţie nu se găseşte, dar se vrea adăugarea ei. In acest paragraf, se consideră căutarea ca un proces pur, ceea ce presupune că arborele este deja creat şi o funcţie, denumită funcţie de căutare, stabileşte dacă o informaţie, dată ca parametru, este sau nu în arborele de căutare. In listingul 1.15 este redată o astfel de funcţie, în ipoteza cunoscută cu privire la structura de nod. Funcţia primeşte pointerul cap la rădăcina arborelui şi intoarce ca rezultat un pointer valid p la ultimul nod vizitat. Din punct de vedere algoritmic, căutarea se realizează prin deplasare alternativă, cu pointerul p, fie în subarborele stânga fie în subarborele dreapta, în raport de relaţia informaţiei dată de parametrul infodat cu informaţia info, conţinută de nodul curent. Se constată cu uşurinţă că informaţia nu există în arbore, dacă în procesul deplasării prin subarbori s-a ajuns prima dată la un nod frunză (terminal). Listingul 1.15 - Structura funcţie de căutare pe un arbore binar de căutare int cautarearb(NODARBORE* cap, char* infodat, NODARBORE** pp) {NODARBORE *p; int terminat, succes, rel; terminat = succes = 0; p = cap; do {rel = strcmp(infodat, p->info); if(rel == 0) /* Informatia s-a gasit */ {succes = 1; terminat = 1; } else /* Informatia inca nu s-a gasit */ {if(rel < 0) /* Deplasare stanga sau terminat*/ {if(p->llink != NULL) p = p->llink; else terminat = 1; /* Informatia nu exista */ } else /* Deplasare dreapta sau terminat */ {if(p->rlink != NULL) p = p->rlink; else terminat = 1; /* Informatia nu exista */ } } } while(!terminat); *pp = p; return (succes); } In codul funcţiei, s-a utilizat o ciclare pe baza variabilei boolene terminat care pleacă pe 0 (fals) şi primeşte valoare 1 (adevărat), fie atunci când s-a găsit nodul ce conţine informaţia, fie atunci când se ajunge la un nod terminal. Variabila succes, de acelaşi tip, evidenţiază eşecul căutării (valoarea 0) sau succesul acestui proces (valoarea 1). In final, funcţia întoarce valoarea variabilei succes şi pointerul p al ultimului nod vizitat. In acest fel,

Prof.dr.Valer Roşca ULBS

36

procedura de căutare poate fi utilizată în operaţii de înserare (vezi paragraful următor), nodul ultim vizitat va fi cel de care se va lega un nod nou, atunci când informaţia nu s-a găsit. Se atrage atenţia asupra modului de declarare a parametrului pp, ca pointer la pointer la nod, adică sub forma NODARBORE** pp, pentru ca adresa nodului ultim vizitat să poată ajunge în apelator. In consecinţă, pentru apel, parametrul actual corespunzător trebuie decarat sub forma NODARBORE *p şi transferat prin adresă, sub forma &p. 1.6.3 Inserare în arbori binari de căutare Operaţia de înserare este mecanismul general prin care se construieşte, din aproape în aproape, un arbore binar de căutare. Operaţia de înserare se poate programa ca o funcţie de înserare care, la fiecare apel, adaugă la arborele existent un nod nou. Inserarea unui nod nou trebuie să implementeze relaţia de dominare specifică. In listingul 1.16 este prezentată o astfel de funcţie care primeşte, în lista de parametri, pointerul la rădăcina arborelui, la primul apel pointer NULL, şi un pointer la informaţia de pus în nod. La fel ca alte funcţii de înserare, funcţia ia în considerare situaţia spaţiului heap şi elimină situaţia când aceeaşi informaţie se repetată. Situaţiile acestea sunt codificate către apelator, prin rezultatul întreg pe care funcţia îl întoarce: valoarea 1, dacă spaţiul s-a epuizat, valoarea 0, dacă a existat spaţiu pentru nod şi înserarea s-a realizat şi valoarea 2, dacă informaţia respectivă există deja într-un nod. Listingul 1.16 - Structura funcţie de înserare în arbore binar de căutare int inserarearb(NODARBORE** cap, char* infodat) {NODARBORE *p, *q; int s; q = (NODARBORE*)malloc(sizeof(NODARBORE)); if(!q) return 1; /* Lipsa spatiu */ /* Pregatire nod nou */ strcpy(q->info, infodat); q->llink = q->llink = NULL; /* Inserarea nodului q */ if(!*cap) *cap = q; /* Arbore vid, prima inserare */ else /* Inserare dupa o cautare */ {s = cautarearb(*cap, infodat, &p) ; if(s == 1) /* Informatia exista deja */ {free(q); return 2; } /* Legarea nodului nou */ if(strcmp(infodat, p->info)p->llink = q; else p->rlink = q; return 0; } } Trebuie remarcat faptul că, în funcţia de înserare s-a apelat funcţia de căutare cautarearb(). Variabila s recepţionează rezultatul căutării şi, în cazul în care aceasta are valoarea 1, informaţia există deja în nod, de aceea, nodul q pregătit deja se eliberează, deoarece inserarea nu se face. Dacă informaţia nu există, nodul p este cel la care trebuie legat nodul q, fie ca succesor stânga, fie ca succesor dreapta, pe baza relaţiei de comparare a informaţiei infodat cu informaţia info din p.

Prof.dr.Valer Roşca ULBS

37

1.7 Realizarea programelor care utilizează structuri dinamice Pentru a putea manipula, cu mai multă uşurinţă, diferitele structuri de date, inclusiv în situaţiile în care se utilizează mai multe structuri de acealşi fel, în programul respectiv, este recomandabil să se construiască tipuri de date: listă arbore, array etc. Un astfel de tip de dată, în tehnica programării procedurale, poate fi conceput ca un articol, descris prin struct, care să definească elemntele caracteristice drept câmpuri: pointeri, număr de noduri (elemente), unitatea de alocare şi realocare etc. In aceste condiţii, utilizând aceleaşi funcţii, se pot manevra structuri de acelaşi fel, prin declararea de variabile de acest tip. Fiecare astfel de structură dinamică este perfect identificată de o variabilă şi, prin notaţia prefixată cu punct, cu numele acelei variabile, se disting elementele, fără confuzie. Tipurile struct definite pot să fie extinse ulterior, în tehnica programării cu tipuri abstracte sau în tehnica programării orientată pe obiecte, astfel încât să încorporeze şi funcţiile de manipulare, prin utilizarera limbajului C++. Mai mult, se poate depăşi specificitatea impusă de tipul de dată al informaţiei din noduri, dacă se utilizează proprietatea de genericitate evitânduse constucţia sistemului de funcţii pentru fiecare caz. In concluzie, pentru a construi un program bun pentru lucrul cu o structură dinamică de date, cu informaţii de un anumit fel, este necesar să se ţină seama de următoarele recomandări: • să se definească un tip de dată pentru nodul (elementul) structurii care să introducă tipul de dată al elementelor şi, dacă este cazul, legăturile; • să se definească un tip de dată pentru structura respectivă care să cuprindă elementele caracteristice ale acelui fel de structură; • să se declare şi să se definească funcţiile necesare, pentru utilizarea structurii respective. In paragrafele anterioare, s-a arătat cum se defineşte tipul de dată pentru nod şi cum trebuie abordată construcţia funcţiilor necesare manevrării structurii dinamice respective. In acest punct, exemplificăm definirea tipului prin două astfel de structuri dinamice. • Pentru un array dinamic se poate declara un tip de forma: typedef struct {informatie* pblock; int nelem; int pozelem} DINARRAY; unde pblock este pointerul la spaţiul heap compact alocat, la un anumit moment, acelei structurii, nelem reprezintă numărul de elemente care pot fi conţinute în spaţiul alocat, iar pozelem arată poziţia ultimului element prezent în array, potrivit convenţiei de numerotare dată de limbaj. Pe baza tipului declarat, se poate defini o variabilă vectdin, sub forma: DINARRAY vectdin; şi pot fi referite aceste elemente ca vectdin.pblock, vectdin.nelem, vectdin.pozelem. La momentul de început, stuctura trebuie să fie vidă, adică este necesar să se iniţializeze structura declarată, sub forma: vectdin.pblock = NULL; vectdin.nelem = 0; vectdin.pozele = -1; In aceste condiţii, funcţiile asociate structurii dinamice trebuie să primească valorile sau adresele elementelor caracteristice, după cum acestea nu vor fi sau vor fi modificate în funcţiile respective. Ele pot să fie transferate individual, aşa cum s-a arătat într-un paragraf

Prof.dr.Valer Roşca ULBS

38

anterior sau, mai comod, global, ca un unic parametru, sub forma unui pointer la aceea structură. In acest ultim caz, se recomandă o declaraţie de forma: DINARRAY vectdin, * pvectdin; ceea ce impune o iniţializare a pointerului sub forma pvectdin = &vectdin. In funcţiile respective, dacă se face ipoteza denumirii la fel a parametrului formal corespunzător, elementele necesare trebuie referite în notaţia prefixată cu săgeată, pe baza acestui parametru, sub forma: pvectdin->numeelement. •Pentru o coadă, de exemplu, tipul este definit de mai puţine elemente caracteristice şi se poate declara sub forma: typedef struct {NODCODA* fata; NODCODA* spate;} COADA; unde fata şi spate sunt pointeri la începutul şi respectiv ultimil nod. Corespunzător, se poate declara o variabilă, vcoda iniţial vidă: COADA vcoda; vcoada.fata = NULL; vcoada.spate = NULL; La fel ca mai sus, şi în acest caz, se poate alege una din variante, pentru transferul parametrilor la funcţiile asociate. Fiind numai două elemete, se poate utiliza, fără complicaţii de scriere, transferul individual, de pointeri. Se recomandă ca tipurile care trebuie declarate, împreună cu prototipurile funcţiilor de lucru cu structura dinamică respectivă, să se constituie sub forma unui fişier header *.h, iar definirele de funcţii să se construiască într-un alt fişier *.c. In felul acesta, se obţin structuri cu un grad mai ridicat de reutilizare care să poată fi folosite şi în alte programe, cu modificări minime. In fine, pentru a avea o viziune mai completă asupra acestui mod de lucru, se poate urmării exemplul din paragraful care urmează. Se atrage atenţia că tehnica de mai sus poate fi aplicată cu succes în cazul în care funcţiile care utilizează tipul respectiv nu sunt recursive. In cazul funcţiilor recursive, este nevoie să se construiască replici ale structurii dinamice, pentru fiecare apel, ceea ce poate conduce foarte repede la epuizarea stivei sistem.

1.8 Un exemplu de utilizare a structurilor dinamice Pentru a ilustra modul în care se pot utiliza structurile dinamice în rezolvarea de probleme, se consideră următorul caz: Să se realizeze un program care să furnizeze o listă alfabetică, pentru o mulţime de termeni (cuvinte) care se dau de la tastatură. Rezolvare: Deoarece este vorba de o mulţime de cuvinte, a construi lista cerută revine la a realiza o sortare a acestora, pe baza ordinii lexicografice. Cum mulţimea are un număr nedefinit de cuvinte, de lungimi diferite, este preferabil să se utilizeze un arbore de sortare, aşa cum s-a arătat în paragraful referitor la arbori binari. Arborele binar de sortare oferă posibilitatea de a stoca cuvintele în heap, pe un spaţiu strict necesar, ceea ce poate asigura sortarea unui mare număr de termeni. Aceasta înseamnă că în structura nodului arborelui nu se înscrie informaţia, ci un pointer la blocul unde se memorează cuvântul respectiv. Se ştie că, după construcţia arborelui, prin traversare în ordine simetrică, se obţine o listă sortată a cuvintelor. Trebuie ţinut seama că această listă poate fi mare şi, în plus, trebuie

Prof.dr.Valer Roşca ULBS

39

să fie redată pe hârtie. De aceea, lista sortată trebuie să fie înscrisă pe un fişier care, ulterior să poată fi listat, într-un anumit format. Inlisingul 1.17 este redat conţinutul fişierului header al aplicaţiei, denumit arbsort.h. Acesta se presupune că se găseşte pe directorul curent şi cuprinde declararea tipurilor de date şi prototipurile funcţiilor necesare. Aici trebuie remarcat faptul că nodul arborelui nu conţine cuvântul, ci un pointer la spaţiul din heap, strict necesar, unde se memorează cuvântul respectiv. De asemenea, se observă că tipul pentru arborele de sortare posedă, pe lângă pointerul cap şi un pointer la fişierul pe care se va găsi lista de cuvinte. Listingul 1.17 – Fişierul antet arbsort.h /* Definirea nodului arborelui */ typedef struct nod {char* pinf; struct nod* llink; struct nod* rlink; } NODARBORE; /* Definirea arborelui de sortare */ typedef struct {NODARBORE* cap; FILE* fc;} ARBORESORTARE; /* Definirea prototipurilor functiilor pentru arbore */ int cautarearb(ARBORESORTARE* pa, char* infodat, NODARBORE** p); int inserarearb(ARBORESORTARE* pa, char* infodat); void traversareSRD(NODARBORE* k, FILE *f); void traversareRSD(NODARBORE* p); In listingul 1.18 este redat fişierul funcţiei principale. Funcţia main() declară variabilele necesare, iniţializează variabilele de tip structură şi construieşte arborele de sortare, prin conversaţie la consolă, apelând funcţia de înserare. După ce arborele a fost construit, se apelează funcţia de traversare, pentru a crea, pe un fişier deja deschis în directorul curent, lista sortată a cuvintelor, fiecare cuvânt fiind scris pe un rând distinct. In final, este apelată funcţia care distruge arborele, ptin traversare în postordine. Listingul 1.18 – Fişierul programului principal, pentru sortarea de cuvinte pe arbore #include #include #include "arbsort.h" /* Functia principala main() */ void main() {ARBORESORTARE as; char cuv[80]; int sp; /* Introducerea cuvintelor. Constructia arborelui */ as.cap = NULL; as.fc = NULL; printf("\nDati cate un cuvant.\n" "Terminati prin cuvant vid (ENTER):\n"); scanf("%s", cuv); while(strlen(cuv)!= 0) {sp = inserare(&as, cuv); if(!sp) {printf("\nNu mai pot fi introduse cuvinte; lipsa spatiu !\n"); break;

Prof.dr.Valer Roşca ULBS

40

} printf("\nDati cate un cuvant.\n" "Terminati prin cuvant vid (ENTER):\n"); scanf("%s", cuv);

} /* Traversarea arborelui pentru sortarea cuvintelor */ as.fc = fopen("Listacuv.txt", "w"); traversareSRD(as.cap, as.fc); fclose(as.fc); printf("\nLista sortata a cuvintelor se gaseste in fisierul\n " "Listacuv.txt, pe directorul curent.\n"); /* Distrugerea arborelui, pentru eliberarea spatiului */ traversareRSD(as.cap); } Funcţiile sunt implemetate în listingul 1.19, considerând fişierul sursă arbsort.c, pe directorul curent. Funcţiile care se utilizează aici sunt cele discutate anterior, la care s-au adus unele modificări şi la care s-a adăugat funcţia de distrugere de arbore, prin treaversare în postordine. Funcţile de căutare şi de înserare sunt legate între ele, funcţia de înserare apelând, pentru fiecare cuvânt, funcţia de căutare. Dacă se urmăreşte codul sursă al acestor funcţii, se constată că există o modificare, impusă de structura nodului arborelui care conţine pointer la informaţia din nod. Atunci, la înserare este necesar să se aloce spaţiu atât pentru nod cât şi pentru informaţie şi spaţiile respective să se iniţializeze corespunzător, aşa cum rezultă din secvenţa: q = (NODARBORE*)malloc(sizeof(NODARBORE)); t = (char*)malloc(sizeof(infodat)+1); . . . . . . . . . . . . . /* Pregatire nod nou */ q->pinf = t strcpy(t, infodat); q->llink = q->llink = NULL; Atunci când căutarea este fără succes, pointerul p aduce adresa nodului după care trebuie să aibă loc înserarea. Subarborele în care se leagă nodul nou este dat de comparaţia între informaţia din nod şi cuvântul dat. Relaţia de comparare a informaţiei dată cu cea din nod este de forma strcmp(infodat, p->pinf), având în vedere pointerul pinf la informaţie. La funcţia de căutare, s-a modificat numai modul de comparare a informaţiilor, având în vedere structura nodului, aşa cum arată instrucţiunea: rel = strcmp(infodat, p->pinf). Listingul 1.19 –Funcţiile programului de sortare pe arbore- fişierul arbsort.c #include #include #include #include "arbsort.h" /* Functia de cautare pe un arbore binar de cautare */ int cautarearb(ARBORESORTARE* pa, char* infodat, NODARBORE** pp) {NODARBORE *p; int terminat, succes, rel; terminat = succes = 0; p = pa->cap;

Prof.dr.Valer Roşca ULBS

41

if(!p) return succes; /* Arbore vid. Informatia nu exista */ do {rel = strcmp(infodat, p->pinf); if(rel == 0) /* Informatia s-a gasit */ {succes = 1; terminat = 1; } else /* Informatia inca nu s-a gasit */ {if(rel < 0) /* Deplasare stanga sau terminat*/ {if(p->llink != NULL) p = p->llink; else terminat = 1; /* Informatia nu exista */ } else /* Deplasare dreapta sau terminat */ {if(p->rlink != NULL) p = p->rlink; else terminat = 1; /* Informatia nu exista */ } } } while(!terminat); *pp = p; return (succes); } /* Functia de inserare in arbore binar de cautare */ int inserarearb(ARBORESORTARE* pa, char* infodat) {NODARBORE *p, *q; char *t; int r; q = (NODARBORE*)malloc(sizeof(NODARBORE)); if(!q) return 1; /* Lipsa spatiu pentru nod */ t = (char*)malloc(sizeof(infodat)+1); if(!t) return 1; /* Lipsa spatiu pentru informatie */ /* Pregatire nod nou */ q->pinf = t; strcpy(t, infodat); q->llink = q->rlink = NULL; /* Inserarea nodului q */ if(!pa->cap) {pa->cap = q; /* Arbore vid, prima inserare */ return 0; } /* Inserare dupa o cautare */ p = pa->cap; r = cautarearb(pa, infodat, &p) ; if(r == 1) /* Informatia exista deja */ {free(q); free(t); return 2; } /* Legarea nodului nou */ r = strcmp(infodat, p->pinf); if(r < 0) p->llink = q; else p->rlink = q; return 0; }

Prof.dr.Valer Roşca ULBS

42

/* Functia de traversare recursivă in ordine simetrică */ void traversareSRD(NODARBORE* k, FILE *f) {if(k->llink != NULL) traversareSRD(k->llink, f); fprintf(f, " %s \n", k->pinf); if((k->rlink)!=NULL) traversareSRD(k->rlink, f); } /* Functia de traversare recursiva în postordine pentru distrugere arbore*/ void traversareRSD(NODARBORE* p) {NODARBORE *s, *d; s = p->llink; d = p->rlink; free(p->pinf); free(p); if(!s) traversareRSD(s); if(!d) traversareRSD(d); }

Funcţia de traversare în postordine (RSD), este implementată recursiv şi are sarcina să elibereze spaţiul ocupat de nodurile arborelui. Se observă că, funcţia tratează rădăcina p a unui subarbore, în sensul ştergerii spaţiului pentru informaţie şi apoi a spaţiului nodului însuşi. După tratarea rădăcinii, dacă există subarborele stânga şi/sau dreapta, adresaţi respectiv prin pointerii s şi d, aceştia sunt traversaţi în postordine, operând similar pe rădăcinile acestora. Traversarea se termină atunci când ambii subarbori sunt vizi. In fine, se remarcă faptul că funcţiile de traversare primesc numai parametri implicaţi şi nu se utilizează parametrii de tipul ARBORESORTARE. In cazul în care s-ar utiliza un astfel de parametru, de exemplu la traversarea simetrică, la fiecare apel, trebuie să se construiască un subarbore de acest tip, aşa cum rezultă din secvenţa care urmează şi spaţiul stivei sistem poate fi repede epuizat, fără ca traversarea să fie completă. void traversareSRD(ARBORESORTARE* pa) {ARBORESORTARE ps, pd; NODARBORE *k; k = pa->cap; if(k->llink != NULL) {ps.cap = k->llink; ps.fc = pa->fc; traversareSRD(&ps); } fprintf(pa->fc, " %s \n", k->pinf); if((k->rlink)!=NULL) {pd.cap = k->rlink; pd.fc = pa->fc; traversareSRD(&pd); } }

Prof.dr.Valer Roşca ULBS

43

2. Utilizarea fişierelor Un program comunică cu mediul sistemului, în principal, prin intermediul fişierelor. Fişierele reprezintă principalul mijloc de organizare a datelor de mare volum care au un caracter persistent. Un fişier odată creat poate fi reutilizat, cu o mulţime de programe şi la diferite momente de timp, eventual, după ce a fost adus la zi, din punctul de vedere al conţinutului, dacă este cazul. Un fişier este o colecţie de date memorate pe suport magnetic, de regulă disc magnetic, organizate întru-un anumit mod, pentru a putea fi regăsite ulterior. Modul în care sunt organizate datele pe suport magnetic reprezintă nivelul fizic al fişieruli, iar modul cum aceste date sunt văzute în procesul de prelucrare este nivelul logic de organizare. Nivelul fizic presupune utilizarea pistelor şi sectoarelor discului pentru memorarea datelor ca secvenţe binare, în vreme ce nivelul logic asigură fişierului o structură orientată spre utilizator în care fişierul este văzut ca o colecţie de unităţi de date: linii de text sau blocuri de bytes (articole). Sistemul de operare este responsabil cu implementarea lucrului cu fişierele şi oferă asistenţa necesară prin intermediul unei biblioteci de rutine, denumită Sistem de gestiune a fişierelor – SGF. Limbajele de programare utilizează SGF şi îşi crează o bibliotecă specifică de subrutine prin care programatorii, utilizatori ai acelui limbaj, pot realiza prelucrări la nivelul logic. Principiile şi regulile după care se memorează datele pe mediul extern, constituie o metodă de organizare de fişier. Un sistem de operare poate implementa mai multe metode de organizare, dar metoda secvenţială este o metodă generală standardizată. Modul în care se regăsesec unităţile de date în fişierul logic constituie tipul de acces. Dacă, în ordinea logică specifică a unităţilor de date, o unitate nu poate fi localizată decât prin parcurgerea integrală a unităţilor care o preced, accesul este secvenţial. Dacă o unitate poate fi selectată independent de celelalte, accesul este direct. Toate metodele de organizare admit accesul secvenţial, iar unele metode permit şi accesul direct. Lucrul cu un fişier presupune operaţii care se referă la fişier ca o entitate evidenţiată în sistemul de operare (operaţii de gestiune) şi operaţii de prelucrare propriu-zisă a datelor pe care fişierul le conţine. Operaţiile de gestiune se referă la înscrierea fişierului, sub un anumit nume, în sistemul de evidenţă practicat de sistemul de operare (sistem de directori, foldere), redenumirea fişierului, mutarea fişierului în alt director de evidenţă sau pe alt dispozitiv, realizarea de copii, ştergerea fişierului din evidenţă şi a datelor sale atunci când este perimat etc. Operaţiile propriu-zise se referă la utilizarea datelor în programe pentru calcule, situaţii, rapoarte etc (operaţia de consultare), şi la actualizarea periodică a acestora, dacă acest lucru este necesar, prin modificarea valorilor unor articole existente (modificare), ştergerea articolelor perimate (ştergere) şi adăugare de articole noi (adăugare). Operaţiile de modificare, ştergere şi adăugare sunt denumite operaţii de actualizare, o metodă putând să le suporte pe toate sau numai o parte dintre ele. In practică, fişierele pot să fie utilizate în programe ca structuri ajutătoare de date externe, fie ca o prelungire temporară a memoriei interne, datorită volumuli mare de rezultate intermediare, fie ca mijloc de comunicarea între programele unei aplicaţii. Astfel de fişiere, de regulă, nu se actualizează şi, în final sunt şterse. Cele mai frecvente aplicaţii de prelucrare de date utilizează fişiere persistente care se actualizează periodic, denumite fişiere de evidenţă. Un fişier de evidenţă poate fi utilizat în comun de mai multe aplicaţii, eventual concomitent şi el are o perioadă lungă de viaţă . In acest capitol, vor fi discutate principalele aspecte de implementare şi utilizare a fişierelor în limbajul C. In acest sens, sunt prezente şi câteva paragrafe care se referă la algoritmica prelucrării, constituindu-se în recomandări care pot uşura scrierea de programe de aplicaţie, în condiţiile în care implementarea dată de limbaj nu asigură suficiente facilităţi.

Prof.dr.Valer Roşca ULBS

44

2.1 Tipuri de fişiere admise Limbajul C implementează o singură metodă de organizare, în două variante şi anume metoda secvenţială (fig.2.1). In metoda secvenţială, fişierul este considerat ca o secvenţă de entităţi de date, terminată printr-o secvenţă specială de caractere, denumită marca de sfârşi de fişier EOF (End Of File).

linie

linie

linie

linie

EOF

linie

Marcă de sfâşit fişier (EOF)

Separator (marcă) de linie (CR/LF)

a) Fişier text b bloc

0.b

bloc

1.b

bloc

bloc

2.b

bloc

bloc

EOF

5.b

b) Fişier binar

Fig.2.1 – Organizarea fişierelor secvenţiale pe disc

Un fişier de tip text este constituit din linii de caractere de lungimi diferite, ca număr de caractere, de aceea este necesară delimitarea lor printr-o secvenţă specială de caractere fără grafie, caracterele CR/LF, denumită marcă de linie (rând sau articol). Liniile având un conţinut semificativ (numere întregi, numere reale, caractere), prelucrarea acestor fişiere presupune conversia intre forma internă şi cea externă de reprezentare a valorilor, la memorare (scriere) şi, respectiv, extragere (citire) a acestora din fişier. Fişierele text asigură compatibiblitatea între sisteme de calcul şi între limbaje de programare, fiind conforme cu reguli de organizare general acceptate. De aceea, ele sunt utilizate pentru schimbul de date între aplicaţii. Un fişier de tip text, văzut ca spaţiu de unităţi logice de date, este, prin definiţie, un spaţiu ne adresabil. Aceasta înseamnă că fişierul se crează, scriind liniile de date una după alata, de la începutul fişierului spre sfârşitul său, adică operaţia de creare a fişierului se face în access secvenţial. Odată creat, operaţia de consultare a datelor se realizează, de asemenea, citind unităţile de date, în acces secvenţial, fie de la început spre sfârşit, fie de la sfârsit spre începutul său. In acest tip de fişiere, nu pot fi realizate operaţii care presupun poziţionarea undeva în interiorul acestui spaţiu, cum ar fi operaţiile de ştergere de linii, înserare de noi linii sau cele de modificare de conţinut la anumite linii, numite, împreună, operaţii de actualizare de fişier. Deoarece sfârşitul de fişier poate fi detectat, fişierele de tip text pot fi extinse prin adugare la sfârşit, operaţie ce presupune eliminarea mărcii EOF, scrierea secvenţială a noilor linii şi apoi refacerea mărcii de sfârşit de fişier. Având în vedere

Prof.dr.Valer Roşca ULBS

45

modul de selectare a liniilor de text în realizarea operaţiilor fundamentale, despre fişierele de tip text se spune că sunt fişiere cu acces secvenţial. Un fişier de tip binar este o secvenţă de blocuri de bytes care pot avea sau nu aceeaşi lungime şi al căror conţinut nu are semificaţie pentru sistemul de gestiune al fişierelor. In lucrul cu aceste fişiere blocurile sunt citite şi scrise ca secvenţe de biţi, fără interpretare, de aceea, despre aceste blocuri se spune că sunt imagini de memorie internă. Fişierele binare, în forma lor generală, sunt utilizate de aplicaţii, mai ales, ca o prelungire a memoriei interne, atunci când sunt implicate rezultate intermediare de mare volum. Fişierele binare, fiind fişiere secvenţiale, pot avea, de asemenea, comportamentul descris mai înainte, din punctul de vedere al operaţiilor posibile şi al realizării acestora la nivel de bloc. In plus, datorită faptului că, prin definiţie, blocurile nu au o semantică, este posibil ca în fişier să se scrie şi să se citească blocuri de mărimi diferite, în acelaşi program sau în programe distincte. Altfel spus, într-un fişier binar, programele pot vedea după dorinţă împărţirea în blocuri, adică structura de bloc a acestor fişiere este virtuală. Datorită acestui fapt, are sens poziţionarea oriunde în fişier şi realizarea unei prelucrăti specifice, începând cu acea poziţie. Sistemul de gestiune al fişierelor oferă, în acest sens, operaţia de poziţionare pe un anumit byte, considerînd numerotarea poziţiilor acestora începând cu zero (poziţie relativă). Se spune că un fişier binar admite şi acces direct, prin poziţie relativă. Dacă fişierul binar este creat cu blocuri de aceeaşi lungime b, aşa cum se sugerează în figura 2.1, atunci mecanismul adresării directe poate fi utilizat sistematic, adresa de început a unui bloc, ca poziţie relativă a primului său byte, putând fi calculată, pe baza lungimii comune a blocurilor şi a numărului n al blocului respectiv. Dacă, prin program, blocului i se dă o anumită semificaţie informaţională ca o structură de tipul struct şi fiecare bloc poate fi identificat unic în fişier prin valorile unui câmp al acestei structuri, denumit cheie primară, atunci numărul n ≥ 1 îl poate genera programul însuşi. Programul defineşte o transformare de poziţie de bloc, pe baza cheii primare, ca o funcţie şi, pe baza ei, calculează pozţia relativă pe a acestuia, aşa cum se arată în relaţiile care urmează: n = n(CheiePrimară) pe = (n - 1) * b. Sub această formă, fişierele, binare pot fi utilizate în realizarea unor sisteme de programe pentru aplicaţii practice cum ar fi: aplicaţie de gestiune a studenţilor unei facultăţi (universităţi), de gestiune a materialelor, a salariaţilor unei companii, a cărţilor dintr-o bibliotecă etc, deoarece oferă atât acces secvenţial cât şi acces direct dirijat prin conţinutul blocurilor. In toate aceste cazuri, un bloc cuprinde informaţii despre un obiect: student, material, salariat, carte etc, iar cheia primară este matricolul studentului, codul materialului, marca salariatului sau cota cărţii.

2.2 Implementarea lucrului cu fişiere La fel ca şi alte limbaje, limbajul C implementează lucrul cu fişiere prin intermediul unei biblioteci de funcţii, definite în fişierul header stdio.h şi bazate pe conceptul de stream. 2.2.1 Streamuri Pentru a uniformiza modul de lucru cu fişierele disc şi cu alte dipozitive de intrare/ieşire, limbajul introduce noţiunea de stream. Un stream este un concept logic care defineşte o secvenţă de bytes, cu sau fără o anumită structură, care este sursă de date de intrare sau purtător de date de ieşire. Pentru a putea lucra cu un fişier, în această tehnică, programul trebuie să definească un stream şi să îl asocieze cu fişierul fizic, ca suport de memorare externă de date. Operaţia de asociere între un stream şi un fişier este denumită deschidere de fişier. După ce streamul nu mai este necesar, programul trebuie să realizeze o operaţie de închidere de fişier care

Prof.dr.Valer Roşca ULBS

46

desface asocierea acestuia cu fişierul. Operaţiile de deschidere şi închidere, permit ca, într-un program, acelaşi stream să poată fi asociat succesiv cu mai multe fişiere. Observaţie: Aşa după cum se ştie deja, există streamuri asociate implicit cu tastatura şi monitorul, dispozitive indispensabile oricărui program. Pentru acestea, fişierul stdio.h defineşte streamurile standard: stdin , pentru intarea de la tastatură şi stdout, pentru ieşirea pe monitor. Pentru aceste dispozitive, denumite fişiere interactive, compilatorul generază automat deschiderea, la începutul programului şi închiderea, la sfârşitul programului.

Program

Fişier intrare

Tampon de intrare 1 2

Citire:

Scriere:

Variabile de intrare

1 - Umplere 2 - Extracţie

3 - I nserţie 4 - Golire

Prelucrare

Variabile de ieşire

3 4

Tampon de ieşire

Fişier ieşire

Fig.2.2 – Prelucrarea fişierelor prin stream

Prin acest mecanism, programul lucrează în mod direct cu streamul, din care citeşte sau în care scrie câmpuri de bytes, ajutat de funcţiile din biblioteca standard de intrare/ieşire, fără să fie preocupat de comunicarea acestuia cu fişierul asociat. Deoarece , modul de lucru cu streamurile standard, pentru tastatură şi monitor, a fost tratat într-un capitol anterior, în acest capitol se detaliază aspectele de lucrul cu fişiere pe disc. După cum sugerează şi fig.2.2, un stream posedă un spaţiu de memorie, ca un array de bytes, de o anumită mărime, numit tampon (buffer), prin intermediul căruia se vehiculează bytes fişierului şi asupra streamului se efectuează operaţii de citire/scriere. O operaţie de citire înseamnă o extracţie din tampon a unui câmp de bytes, tratarea acestuia într-un anumit mod şi atribuirea valorii rezultate prin prelucrare, unei variabile a programului. O operaţie de citire poate găsi un tampon nevid sau poate întâlni situaţia de tampon gol şi, în consecinţă, ea trebuie să execute o umplere cu noi date din fişier. Dacă operaţia de citire curentă, aflată într-o astfel de situaţie, preia date până la reumplerea tamponului sau până la ternimarea fişierului, dacă acesta are mai puţini bytes decât capacitatea acestuia, atunci nu ori care operaţie subsecventă de citire trebuie să realizeze preluare de date din fişier. Astfel, prin definirea unui tampon suficient de mare, operaţiile de

Prof.dr.Valer Roşca ULBS

47

citire devin mai eficiente, deoarece se reduce numărul de accese la dispozitiv care sunt mari consumatoare de timp. O operaţie de scriere în stream înseamnă inserţie a unui câmp de bytes în tampon, începând cu o anumită poziţie. Operaţii succesive scriu, în continuare în tampon, atâta timp cât acesta are un spaţiu rămas suficient pentru lungimea câmpului pe care îl tratează operaţia respectivă (operaţia curentă). In caz contrar, operaţia curentă realizează o golire a conţinutului tamponului pe fişier şi apoi îşi înserează în tampon câmpul pe care trebuie să-l scrie. Similar cazului operaţiei de citire, un tampon suficient de mare evită accesele repetate la dispozitiv şi îmbunăţeşte timpul operaţiilor de scriere a datelor în fişier. Limbajul implementează două tipuri de streamuri: stream de tip text şi stream de tip binar. Un stream de tipul text (text stream) este un stream cu o anumită structură. Un astfel de stream constă din una sau mai multe linii de text, ca secvenţe de caractere terminate prin caracterul newline (’\n’). Acest tip de stream este destinat realizării şi prelucrării de fişiere secvenţiale de tip text care, afişate pe dispozitive ce recunosc secvenţa de caractere CR/LF ca o comandă de trecere pe rând nou, cum este monitorul şi imprimanta, produc pagini de text. Datorită difernţei de structură, operaţiile de prelucrare trebuie să aplice un tratament suplimentar, pentru a asigura trecerea dela convenţia pe care o respectă streamul la cea care este utilizată de fişier. Atunci când se preiau date din fişier, funcţia care face reumplerea streamului trebuie să înlocuiască, în tamponul curent, secvenţa de caractere CR/LF cu un singur caracter newline, iar atunci când se depun date în fişier, din tampon, funcţia care realizează operaţia trebuie să înlocuiască, în prealabil, caracterul newline cu secvenţa de caracter CR/LF . Operaţiile de citire şi scriere într-un stream de tip text presupun conversii între forma caractere şi forma internă de reprezentate a valorilor pe care câmpurile de bytes le reprezintă. Un stream de tip binar (binary stream) este un stream fără structură care conţine câmpuri de bytes sau blocuri cărora, în operaţiile de citire/scriere nu lise dă nici o semificaţie. Se spune că aceste operaţii se fac la nivel de imagine de memorie, adică o operaţie de citire extrage din stream secvenţa de biţi corespunzătoare unui bloc şi îi stochează în memoria internă , iar o operaţie de scriere depune în stream secvenţa de biţi conţinuţă de un bloc de memorie internă. Un stream binar se poate asocia cu un fişier care a fost creat printr-un stream binar sau se poate asocia cu un fişier de tip text, dacă programul nu doreşte să ia în seamă semificaţia de caractere a blocurilor. De asemenea, trebuie observat că programele pot trata un fişier cu stream binar, citind şi scriind blocuri de aceeaşi mărime sau de mărimi diferite. Atunci când fişierul reprezintă un conţinut cu semificaţie pentru program (dar nu şi pentru operaţiile de intrare/ieşire), fişierul se crează scriind blocuri egale, iar la citire, de regulă, mărimea blocului este aceeaşi cu cea de la momentul creării. 2.2.2 Controlul unui stream Alături de funcţii, fişierul header stdio.h conţine tipul structurat de date, denumit FILE care asigură declararea unui stream ca o structură dinamică de date. O structură de tipul FILE memorează starea unui stream sub formă de câmpuri de date întregi, de biţi (flags) sau de caractere şi cuprinde informaţii cum sunt: • indicator de eroare (flag) – este pus pe o valoare 1 de o funcţie care întâlneşte o eroare de citire sa scriere în fişier; • indicator de sfârşit de fişier (flag) – este pus pe valoarea 1 de o funcţie de citire, dacă întâlneşte sfârşitul de fişier; • indicator de poziţie în stream (pointer) – specifică poziţia următorului byte în stream care poate fi accesat (citit sau scris); • indicatori pentru modul de prelucrare (flags) – există un indicator pentru a preciza utilizarea streamului pentru citire, pentru scriere şi pentru citire/scriere. Indicatorii sunt mutual exclusivi, valoarea 1 arată permisiunea, iar 0 interdicţia; • indicator de stream binar (flag) – valoarea 1 arată tipul binar, iar valoarea 0 tip text. Implicit streamul se consideră text;

Prof.dr.Valer Roşca ULBS

48

• tamponul streamului – specifică adresa unui array de tipul char în heap (pointer) şi mărimea acestuia (număr întreg), de regulă, mărimea prestabilită în fişierul stdio.h; • nivelul de umplere/golire al tamponului – număr întreg care specifică numărul de bytes existenţi în tampon după o operaţie de umplere, respectiv de înserare etc. Pentru a uşura lucrul cu streamuri, fişierul stdio.h declară şi o serie de constante simbolice, cum este constanta EOF necesară pentru testarea faptului că o funcţie de citire a întâlnit sfârşitul de fişier, sau BUFSIZ care defineşte mărimea tamponului streamului (implicit 512 bytes) etc. Nu este recomandabil ca programul să modifice, prin referiri pe baza pointerului, nici unul din câmpurile structurii aferente, dar programul trebuie să utilizeze pointerul, ca parametru, în funcţiile de lucru cu streamul. NumaI funcţiile de I/O pot controla, pe bază de pointer, structura pentru streamul respectiv. 2.2.3 Modul de lucru cu streamul Programul care doreşte să prelucreze un fişier, trebuie să realizeze paşii care urmează. 1). Declararea streamului. Se declară câte o variabilă pointer de tipul FILE pentru fiecare stream. De exemplu: FILE *strmIntr, *strmIes; // Stream intarare si stream iesire 2). Deschiderea streamului. Pentru construcţia structurii de stare, se utilizează funcţia fopen(), într-o expresie de atribuire de forma: pointer_la_stream=fopen(). Urmare a unei astfel de atribuiri, în heap se construieşte o structură de stare pentru stream care este iniţializată corespunzător şi pointerul la stream este încărcat cu adresa blocului de memorie alocat acestei structuri. Funcţia fopen() are prototipul următor: FILE *fopen( const char *filename, const char *mode ); Parametrul filename este un pointer care dă specificatorul fişierului. Specificatorul urmează regulile de construcţie ale sistemului de operare, cu menţiunea că separatorul între părţile acestuia trenuie să fie \\, având în vedere semificaţia caracterului \ în scrierea caracterelor fără grafie. In cazul în care specificatorul este incomplet, se aplică regulile sistemului de operare cu privire la discul curent, directorul curent şi extensia implicită. Parametrul mode este un pointer care specifică, sub formă de string, modul de prelucrare al streamuli şi tipul de stream. Se pot utiliza stringurile care sunt redate în tabelul 2.1. Tabelul 2.1 – Valorile posibile pentru parametrul mode la deschidere Stringul Semificaţie Deschide un fişier existent pentru citire in modul text. Dacă fişierul nu ″r″ există sau nu poate fi găsit, operaţia eşuează. Deschide un fişier vid pentru scriere în modul text. Dacă fişierul există, ″w″ conţinutul său este distrus. Deschide un fişier, in modul text, pentru adăugare la sfârşit. Dacă fişierul ″a″ nu există sau nu poate fi găsit, operaţia crează un fişier vid. Deschidere, în modul text, pentru citire/scriere. Fişierul trebuie să existe, ″r+″ altfel operaţia eşuează. Deschidere, în modul text, un fişier vid pentru scriere/citire. Dacă fişierul ″w+″ există, conţinutul său este distrus. Deschide un fişier, in modul text, pentru adăugare la sfârşit şi citire. Dacă ″a+″ fişierul nu există sau nu poate fi găsit, operaţia crează un fişier vid.

Prof.dr.Valer Roşca ULBS

49

″rb″ ″wb″ ″rb+″ ″wb+″

Deschide un fişier existent pentru citire in modul binar. Dacă fişierul nu există sau nu poate fi găsit, operaţia eşuează. Deschide un fişier vid pentru scriere în modul binar. Dacă fişierul există, conţinutul său este distrus. Deschidere, în modul binar, pentru citire/scriere. Fişierul trebuie să existe, altfel operaţia eşuează. Deschidere, în modul binar,a unui fişier vid pentru scriere/citire. Dacă fişierul există, conţinutul său este distrus.

Trebuie remarcat faptul că, atunci când un stream se deschide pentru adăugare la sfârşit, toate operaţiile de scriere se fac numai la sfârşitul fişierului, iar eventualele operaţii de citire sunt posibile numai în partea deja scrisă. Eticheta de sfârşit de fişier este ştearsă, dacă este cazul, numai în momentul în care apare prima operaţie ce presupune adăugarea de date noi la fişier. Dacă operaţia de deschidere eşuează, funcţia fopen() întoarce un pointer NULL. Altminteri valoarea returnată este un pointer valid chiar spre structura de stare a streamului. Această valoare reprezintă modul prin care se poate controla dacă deschiderea a reuşit. In exemplul care urmează, se deschid două fişiere: unul pentru intrare şi altul pentru ieşire, considerând că deschiderea fişierului de ieşire trebuie să aibă loc numai dacă a putut fi deschis fişierul de intrare şi se schiţează o structură corespunzătoare a funcţiei main(). #include void main() { FILE *strmIntr, strmIes; char fnameIntr []=″C:\\DirDate\\DirPers\\Personal.txt″; // Deschiderea fisierului de intrare strmIntr=fopen(fnameIntr, ″r″); if(!strmIntr) {puts(″Fisierul de intrare nu poate fi deschis !″); exit(1); } // Deschiderea fisierului de iesire strmIes=fopen(″A:\\Salarii.txt″, ″w″); if(!strmIntr) {puts(″Fisierul de iesire nu poate fi deschis !″); fclose(strmIntr); exit(1); } // Prelucrarea fisierului deschis ca intrare si // scriere pe fisierul deiesire ................................. // Inchiderea fisierelor fclose(strmIntr); fclose(strmIes); } 3). Prelucrarea streamului. Se utilizează funcţiile de I/O pentru a citi şi/sau scrie în stream. Pentru modul în care se realizează această etapă, a se vedea paragrafele următoare. Aici, trebuie făcută observaţia că există diferenţe de implementare a modului de prelucrare, pentru diferite platforme C, de aceea, pentru o tratare uniformă şi pentru a asigura o portabilitate cât mai mare a programelor, vor fi tratate numai funcţiile standardului ANSI. De asemenea, se face menţiunea că tratarea nu este exhaustivă, fiind comentate şi exemplificate cele mai uzuale dintre funcţiile legate de prelucrare a fişierelor.

Prof.dr.Valer Roşca ULBS

50

4). Inchiderea streamului. Se apelează funcţia fclose(), aşa cum rezultă din exemplul de mai sus. Această funcţie are rolul de a încheia prelucrarea, prin golirea tamponului, dacă acesta nu s-a umplut la ultima operaţie de scriere (bloc scurt) şi apoi de a elibera resursele ocupate de stream. Operaţia de închidere este recomandabil să se facă imediat ce prelucrarea cu un stream s-a încheiat, mai ales atunci când se utilizează multe fişiere în program, astfel încât să se asigure , mai bine, resursele necesare celorlalte fişiere care se prelucrează în continuare.

2.3 Citire din streamuri text Operaţiile de citire a streamurilor de tipul text sunt asistate de o serie de funcţii specifice care sunt capabile să extragă câmpuri de bytes din stream, să le analizeze din punctul de vedere al scrierii corecte, eventual, să convertească forma externă caractere în formă internă codificată şi să atribuie valoarea astfel obţinută unei variabile de tip corespunzător. In streamurile de tipul text, pot apare o serie de caractere care separă câmpurile, denumite spaţii albe (whitespaces sau simplu ws). Sunt considerate caractere ws caracterul blank, caracterul tab şi newline. Toate celelalte caractere, exceptând %, sunt considerate caractere non-whitespace. Există mai multe posibilităţi de lucru din punctul de vedere al mărimii şirului de caractere care se extrage: la nivel de caracter, la nivel de câmp de caractere cu semificaţie sau la nivel de linie de text, pe care le prezentăm succint, în continuare. 2.3.1 Citire la nivel de caracter Citirea la nivel de caracter este asigurată de funcţia fgetc() care are următorul prototip: int fgetc( FILE *stream ); Această funcţie întoarce caracterul din poziţia curentă din stremul de intrare sau valoarea EOF, dacă s-a detectat sfârşitul de fişier. Funcţia nu distinge între caracterele cu şi fără grafie, de aceea cracterul citit poate fi oarecare, inclusiv newline. De exemplu, pentru streamul de intrare de mai sus se poate scrie: char c; c = fgetc(strmIntr); 2.3.2 Citire la nivel de câmp Citirea la nivel de câmp, denumită şi citire formatată, reprezintă parte centrală a prelucrării streamurilor text şi se referă la şiruri de caractere care au o anumită semantică: numere întregi, numere reale, texte etc. Funcţia care asigură acest mod de citire este fscanf() care are următorul prototip: int fscanf( FILE *stream, const char *format [, argument ]... ); După cum se observă din acest prototip, lista de parametrii a acestei funcţii are trei părţi: pointerul stream la streamul de intrare, formatul format de intrare şi o listă de variabile de intrare, desemnată prin construcţia de meta limbaj [, argument ].... Deoarece, prin citire se urmăreşte să se asigneze valori, provenite din fişier, unor variabile ale programului, de diferite tipuri de date, lista de argumente, denumită listă de intrare, care reprezintă aceste variabile, este elementul central. Lista de intrare este o listă de adrese ale variabilelor respective care pot să fie variabile simple, câmpuri ale unor structuri de date de tipul struct sau elemente de array. In consecinţă, în această listă, variabile trebuie să fie precedate de operatorul de adresă &, sub forma &var. Sistemul oferă posibilitatea de a citi formatat global şiruri de caractere şi de a le memora în structuri array de tipul char. In acest caz, deoarece, o variabilă array este, prin definiţie, variabilă de adresă (pointer), în lista de intrare, numele acesteia nu trebuie precedată cu operatorul de adresă.

Prof.dr.Valer Roşca ULBS

51

Parametrul format este un string, constitui din subşiruri de caractere predefinite, denumite specificatori de format care descriu cum trebuie tratate câmpurile din streamul de intrare. Un specificator de format poate conţine şi alte caractere, diferite de caracterele specifice. Pentru fiecare variabilă din lista de intrare, trebuie să existe în format un specificator de format. Specificatorii de format se pun încorespondenţă, de la stânga la dreapta, cu variabilele din lista de intrare. Un specificator de format este totdeauna introdus prin caracterul % şi are următoarea formă generală: %[*][width] [{h | l | L}]type In această construcţie, prezentată în metalimbaj, parantezele drepte arată opţionalitate elementuli pe care îl încadrează, perechea de acolade arată alegerea unui elemet dintre elementele pe care acestea le conţin, separate prin bare verticale, iar elementele subliniate trebuie să fie înlocuite potrivit semificaţiei dată de textul respectiv. •Singurul element obligatoriu este cel denumit type care este un caracter, dintr-o mulţime prestabilită şi care arată tipul de dată pentru interpretarea câmpului corespunzător din stream: număr, string sau caracter. Tabelul 2.2 prezintă caracterele posibile şi semificaţia lor, având în vedere tipurile de date care pot fi citite în C. In acest context, un specificator de format poate avea forma simplă %type, ca de exemplu: ″%d″ - specificator pentru un câmp ce reprezintă un număr întreg, ″%f″ - specificator pentru un câmp ce reprezintă un număr real, ″%s″ - specificator pentru un câmp ce reprezintă un string etc. •Caracterele h, l, L, denumite modificatori de tip, pot precede caracterul pentru indicarea tipului unui câmp, numai în cazul câmpurilor numerice şi au semificaţia: h – short int, l – long int sau double, dacă şirul de caractere reprezintă un număr real, L – long double. Modificatorii reprezintă o posibilitate de a desemna unele tipuri de date, pentru care nu există definit un caracter specific de tip. •Elementul width este un număr natural care specifică numărul maxim de caractere care compun câmpul. Tabelul 2.2 – Caraterele pentru tip de dată în specificatorii de format Caracter de tip Semificaţie Intreg (int) redat în baza 10 d Intreg (int) redat în baza 8 o Intreg (int) redat în baza 10, 8 sau 16 i Intreg fără semnn(unsigned int) redat în baza 10 u Intreg (int) redat în baza 16 x Intreg (long int) redat în baza 16 X Real (float) redat în baza 10 scriere matematică sau ştiinţifică e, E, f, g, G String (char [ ] ) s Caracter (char) c Pointer p •Caracterul * în specificatorul de format este denumit caracter de suprimare a atribuirii şi el spune funcţiei de citire să extragă câmpul curent din stream dar să nu realizeze tratarea lui. Limbajul stabileşte reguli cu privire la modul în care decurge scanarea streamului de intrare şi extragerea câmpurilor. Procesul de scanare porneşte de la o anumită poziţie în stream, denumită caracter următor, evidenţiat dinamic de indicatorul de poziţie al streamului, care, la începutul unui nou tampon, este primul caracter. Cu excepţia cazului câmpurilor descrise cu specificatorul %c, în procesul de scanare sunt eliminate caracterele ws şi un câmp începe cu primul caracter diferit de ws. După ce un câmp a fost extras, caracter următor devine caracterul care succede ultimului caracter ce compune câmpul extras.

Prof.dr.Valer Roşca ULBS

52

Limbajul defineşte următoarele reguli cu privire la caracterele succesive se compun un câmp în stream: •toate caracterele până la, dar fără a include, următorul ws; •toate caracterele până la primul caracter care nu poate fi convertit sub specificatorul respectiv de format; •cel mult n caractere, unde n este numărul care defineşte, în specificatorul de format , numărul maxim de caractere în câmp (width). Dacă în formatul de intrare apar secvenţe de caractere care nu sunt caractere de format, atunci acestea trebuie să corespundă exact cu secvenţa curentă de caractere din câmpul de intrare. Aceste caractere sunt scanate, dar nu sunt reţinute pentru câmpul ce va fi convertit prin specificatorul de format. Dacă apare un conflict, aceste caractere rămân în câmpul de intrare ca şi cum nu ar fi fost scanate. Scanarea pentru extragerea unui câmp se poate încheia înainte de apariţia unui ws sau poate fi abandonată şi se trece la scanarea următorului câmp, în una din următoarele situaţii: •specificatorul de format conţine caracterul de suprimare a atribuirii; •s-a citit numărul maxim n caractere, prevăzut de specificatorul de format; •următorul caracter nu poate fi convertit sub specificatorul de format respectiv. Atunci când este stopată scanarea unui câmp, pentru una din aceste cauze, se presupune că primul caracter pentru scanarea următorului câmp va fi caracterul care a determinat oprirea. Operaţia de citire se termină în următoarele circumstanţe: • următorul caracter pentru câmpul de intrare curent este în conflict cu caracterul nonwhitespace corespunzător din format; •următorul caracter în câmpul curent este un caracter ce marchează sfârşitul de fişier; •formatul de intrare a fost în întregime utilizat. Limbajul prevede câteva convenţii care se aplică la unii specificatori de format, astfel: •Specificatorul ″%c″ determină extragerea următorului caracter, ori care ar fi acesta, inclusiv un ws. Pentru a sări un ws şi a extrage următorul caracter non-whitespace trebuie utilizat specificatorul ″%1s″; •Pentru specificatorul de forma ″%nc″, unde n este lungimea câmpului, adresa corespunzătoare din lista de intrare trebuie să fie adresa unui array cu n elemente char; •Pentru specificatorul de format ″%s″, adresa corespunzătoare din lista de intrare, trebuie să fie un array char cu cel puţin n+1 caractere, dacă trebuie citit un câmp string de lungime n. In array, după ultimul caracter este memorat caracterul null ca terminator de string. Caracterele ws care încheie un câmp string de intrare sunt blanc şi newline; •Pentru specificatorii de format ai numerelor reale, câmpul de intrare poate fi un număr scris în convenţia matematică sau ştiinţifică, în sistem octal, zecimal sau hexazecimal. NOTĂ: In diferite implementări, dar în afară de standardul ANSI, există un specificator de format util pentru a defini stringuri în care sunt acceptate numai anumite caractere şi care are forma %[set-de-caractere]. Intre parantezele drepte se enumeră caracterele ce vor fi acceptate, eventual sub forma de domenii de caractere şi constituie setul-de-căutare. Dacă primul caracter în setul de caractere este caracterul caret ^ , atunci se defineşte un set de căutare complementar celui specificat de caracterele care urmează acestui caracter. De exemplu, %[a-cdfg] defineşte un string care poate conţine ori câte şi în ori ce ordine dintre caracterele a, b, c, d, f, g, iar %[^abc] defineşte pentru string oricare caractere cu excepţia lui a, b, c. Specificarea setului de căutare este sensitivă la litere mari şi mici. De exemplu, %[AFa-f] specifică toate literele mari şi mici din intervalul respectiv. Dacă se uilizează scrierea sub formă de interval, atunci acestea trebuie să fie închise şi disjuncte. In condiţiile unui astfel de

Prof.dr.Valer Roşca ULBS

53

specificator de format, câmpul de intrare nu mai este delimitat de ws, ci de apariţia unui caracter care nu aparţine setului de căutare definit de specificator. După execuţie, funcţia fscanf() întoarce o valoare întreagă semificând numărul de variabile cărora li s-a atribuit efectiv valoare prin citire. Acest număr nu include un câmp scanat, cu care nu s-a puptut realiza atribuirea, adică o valoare zero arată că nu s-a realizat nici o atribuire, primul câmp a fost scanat, dar n-a putut fi convertit. Dacă survine o altfel de eroare în timpul primei scanării sau apare sfârşitul de fişier în cursul acesteia, funcţia returnează valoarea EOF. Rezultă că valoarea returnată este un instrument pentru a face o verificare cu privire la modul de încheiere a operaţiei de citire, dar o valoare egală cu numărul de variabile din lisata de intrare nu este o certitudine de reuşită, ci o indicaţie de posibilă corectitudine. 2.3.3 Citire la nivel de linie Dintr-un stream de tipul text , pot fi citite linii de text, prin utilizarea funcţiei fgets(): char *fgets( char *string, int n, FILE *stream ); Linia este compusă din toate caracterele, începând cu poziţia curentă, fără nici o eliminare de ws, până se întâlneşte caracterul newline, inclusiv acest caracter sau până fost citite n – 1 caractere, care din aceste două evenimente apare primul. Linia de text este memorată în array-ul de tipul char, desemnat prin parametrul string şi i se adaugă caracterul null, terminator de string. Dacă citirea detectează o eroare sau sfârşitul de fişier, funcţia întoarce pointerul NULL, altminteri returnează chiar adresa zonei de memorare. Trebuie acordată atenţie dimensionării zonei de memorare, pentru ca să poată fi stocate toate caracterele, inclusiv caracterul null, altminteri funcţia va semnala o situaţie de eroare.

2.4 Scriere în streamuri text Operaţiile de scriere în streamurile de tip text, la fel ca şi cele de citire, se pot realiza la nivel de caracter, de câmp şi la nivel de linie. Poziţia de la care începe memorarea în stream a şirului de caractere este evidenţiată dinamic în structura de stare, prin indicatorul de poziţie. Operaţiile de scriere în streamuri de tip text sunt asistate de o serie de funcţii specifice, inclusiv de funcţii capabile să construiască şirul de caractere de scris prin conversia valorilor unor expresii. 2.4.1 Scriere la nivel de caracter Scrierea la nivel de caracter este asigurată de funcţia fputc() care are următorul prototip: int fputc(int c, FILE *stream ); Această funcţie scrie caracterul c în poziţia curentă din stremul de ieşire şi întoarce caracterul scris sau valoarea EOF, dacă s-a detectat un eveniment de eroare. Funcţia nu distinge între caracterele cu şi fără grafie, de aceea cracterul scris poate fi oarecare, inclusiv newline. De exemplu, pentru streamul de ieşire de mai sus se poate scrie: char c = '*'; fputc(c, strmIntr); 2.4.2 Scriere la nivel de câmp Scrierea la nivel de câmp, denumită şi scriere formatată, reprezintă o formă importantă a prelucrării streamurilor text. Funcţia care asigură acest mod de scriere este fprintf() care are următorul prototip: int fprintf( FILE *stream, const char *format [, argument ]... );

Prof.dr.Valer Roşca ULBS

54

După cum se observă din acest prototip, lista de parametrii a acestei funcţii, la fel ca şi corespondenta ei la citire, are trei părţi: pointerul stream la streamul de ieşire, formatul format de ieşire şi o listă de expresii de ieşire, desemnată prin construcţia de meta limbaj [, argument ]....După execuţie reuşită, funcţia întoarce numărul de caractere care au fost înserate în stream. Dacă la execuţie survine o eroare, funcţia returnează o valoare EOF. Deoarece, prin scriere se urmăreşte să se memoreze în fişier valori ale unor expresii de calcul din program, lista de argumente, denumită listă de ieşire, este determinantă. Lista de ieşire poate cuprinde ori care expresie corectă în limbaj care produce o valoare ce poate fi convertită în formă caractere. In mod uzual, din motive de simplitate, lista de ieşire se exprimă prin variabile simple şi constante. Trebuie evitată confuzia cu funcţia de citire, reţinând că aici se scriu variabilele (identificatorii) şi nu adresele variabilelor, deoarece acestea desemneară valorile. In consecinţă, structurile de date de tipul struct şi array, cu elemete de alte tipuri decât char, nu pot fi scrise decât prin componentele lor, fiecare din acestea reprezentând o valoare. Există o excepţie importantă care se referă la posibilitatea de a scrie formatat global şiruri de caractere memora în structuri array de tipul char şi terminate prin caraterul null. In acest caz, în lista de ieşire se scrie identificatorul de array. Parametrul format este un string, constituit din specificatori de format care descriu cum trebuie tratate câmpurile pentru streamul de ieşire, caratere non-format şi secvenţe de control (secvenţe escape). Pentru fiecare variabilă din lista de intrare, trebuie să existe în format un specificator de format. Specificatorii de format se pun încorespondenţă, de la stânga la dreapta, cu variabilele din lista de intrare. Caracterele non-format şi secvenţele escape sunt înserate în streamul de ieşire în poziţiile care rezultă din locurile ocupate în format. Un specificator de format de ieşire este totdeauna introdus prin caracterul % şi are următoarea formă generală: %[flags] [width][.precision] [{h | l | L}]type In această construcţie, prezentată în metalimbaj, parantezele drepte arată opţionalitate elementului pe care îl încadrează, perechea de acolade arată alegerea unui elemet, dintre elementele pe care acestea le conţin, separate prin bare verticale, iar elementele subliniate trebuie să fie înlocuite potrivit semificaţiei dată de textul respectiv. •Singurul element obligatoriu este cel denumit type care este un caracter, dintr-o mulţime prestabilită şi care arată tipul de dată: număr, string sau caracter şi conversia la care trebuie să fie supusă pentru producerea câmpului corespunzător din stream. Caracterele prezentate în tabelul 2.2 se utilizează şi în specificatorii de format de ieşire, cu unele precizări care vor fi făcute în continuare. Astfel, un specificator de format de ieşire poate avea, de asemenea, forma simplă %type, ca de exemplu: ″%d″ - specificator pentru un câmp ce reprezintă un număr întreg, ″%f″ - specificator pentru un câmp ce reprezintă un număr real, ″%s″ - specificator pentru un câmp ce reprezintă un string etc. Pentru numere reale, formatul ″%f″ înseamnă scriere în formă matematică, în timp ce ″%e″ şi ″%E″ se utilizează pentru scrierea în formă ştiinţifică, cu litera e sau E separator al mantisei de exponent. Formatele ″%g″ şi ″%G″ construiesc câmpul de ieşire în scriere matematică sau ştiinţifică, depinzând de magnitudinea numărului şi precizia cerută pentru acesta. Se alege forma ştiinţifică numai dacă exponentul numărului este ≤ -4 sau este mai mare sau egal cu numărul care, în specificatorul de format, exprimă precizia. •Caracterele h, l, L, sunt modificatori de tip care pot precede caracterul pentru indicarea tipului unui câmp, numai în cazul câmpurilor numerice şi au semificaţia: h – short int, l – long int sau double, dacă şirul de caractere reprezintă un număr real, L – long double. Modificatorii reprezintă posibilitatea de a desemna unele tipuri de date, pentru care nu există caracter specific de tip. •Elementul width este un număr natural n care specifică numărul maxim de caractere care compun câmpul de ieşire (mărimea zonei de scriere). In mod implicit, dacă lungimea

Prof.dr.Valer Roşca ULBS

55

şirului de ieşire, eventual rezultat prin conversie, este mai mică decât n, acesta este aliniat la dreapta şi este completat cu spaţii la stânga. Caracterul blank este, implicit, caracterul de umplere. Dacă width este redat printr-un caracter *, atunci se consideră că argumentul din lista de ieşire care succede argumentul curent ce se prelucrează cu specificatorul respectiv, ca număr întreg, nu este valoarea ce trebuie scrisă, ci este specificaţia de mărime de zonă de scriere. Acest mod de specificare, permite construirea de câmpuri dinamice ca mărime, variabilele de dimensionare trebuind să fie iniţializate înainte de apelul funcţiei de scriere. Dacă width este mai mic decât cel mai mic număr de poziţii caracter necesare sau specificaţia de mărime de zonă lipseşte, funcţia de ieşire utilizează o zonă de mărime suficientă pentru scrierea completă a valorii respective. •Elementul precision se referă, în general, la numărul de zecimale care se vor reţine în scrierea numerelor reale. Dacă, în specificatorul de format, precizia este numărul întreg m, atunci vor fi reţinute primele m zecimale, după ce s-a aplicat operaţia de rotunjire, iar dacă m=0, atunci se reţine numai partea întreagă a numărului (fără marca zecimală). Dacă elementul precision se redă prin caractertul * , atunci se presupune că precizia este specificată printr-o variabilă din lista de ieşire care poate să fie prima variabilă sau poate să fie a doua variabilă spre dreapta, dacă şi partea de width s-a exprimat prin *, după argumentul care se tratează curent. Dacă precizia se utilizează şi pentru valori întregi, atunci ea este luată în considerare numai atunci când m excede numărul d de cifre pe care îl are numărul şi are drept efect umplerea la dreapta cu m – d zerouri. Astfel, se pot realiza programe care lucrează intern cu numere întregi micşorate cu o putere a lui 10 şi apoi, la scriere, acestea să fie redate în mărimea lor naturală. O menţiune aparte trebuie făcută pentru specificatorii de scriere de stringuri care utilizează precizia m, deoarece, în cazul în care m este mai mic decât lungimea stringului, se scriu numai primele m caractere. •Partea flags se redă printr-un caracter care defineşte modul de aliniere în zona de scriere, scrierea semnului numerelor, a caracterelor blank, a punctuli zecimal (marca zecimală) şi a prefixului de număr octal şi hexazecimal. Se utilizează următoarele caractere: - pentru a specifica aliniere la stânga şi umplere cu spaţii la dreapta; + pentru a specifica redarea obligatorie a semnului sub forma + sau -; 0 pentru a defini caracterul zero drept caracter de umplere la numere; # pentru a specifica o prelucrare suplimentară pentru numere care se stabileşte în raport de carcterul type astfel: x, X – se pune în prefixul de scriere pentru numere hexa; e, E, f – la numere reale se utilizează totdeauna marca zecimală; g, G – la fel ca mai sus, dar la partea fracţionară se completează numărul de zecimale cu zerouri, până la specificaţia de precizie. 2.4.3 Scriere la nivel de linie Intr-un stream de tipul text , pot fi scrise, ca un tot, linii de text, prin utilizarea funcţiei fputs(): int fputs( char *string, FILE *stream ); In acest caz, linia este compusă din toate caracterele din zona dată de parametrul string, până se întâlneşte caracterul null, exclusiv acest caracter. Linia de text este memorată în streamul de ieşire, începând poziţia curentă din tampon şi, la sfârşitul ei nu se adaugă caracterul newline, aşa cum procedează funcţia puts(), pentru streamul stdio. Funcţia returnează numărul de caractere scrise sau valoarea EOF, dacă scrierea detectează o eroare.

Prof.dr.Valer Roşca ULBS

56

2.5 Citire şi scriere în streamuri binare Operaţiile de citire şi scriere în streamurile binare se realizează la nivel de bloc de bytes, prin funcţiile fread() şi fwrite() care au prototipurile: size_t fread(void *buff, size_t bsz, size_t count, FILE *stream ); size_t fwrite(const void *buff, size_t bsz, size_t count, FILE *stream ); De la început, trebuie observată prezenţa, în prototipuri, a tipului de date size‗t care este un tip întreg, definit în fişierul stdio.h care defineşte numere întregi foarte mari, ceea ce asigură posibilitarea de a lucra cu fişiere şi blocuri mari de date. Parametrii au următoarea semificaţie: •parametrul buff este zona de memorie internă care memorează blocurile de date manipulate prin aceste funcţii. O astfel de zonă poate fi definită ca un array sau ca o dată structurată struct ; •parametrul bsz este un număr întreg, mai mare sau egal cu unu, care defineşte mărimea maximă a blocului care se manipulează; •parametrul count este un număr întreg, mai mare sau egal cu unu care stabileşte numărul maxim blocuri de lungime bsz care se doreşte a fi manipulate la execuţia funcţiei respective. Funcţia fread() citeşte cel mult count blocuri de lungime bsz bytes, din streamul de intrare şi le memorează în zona de memorie buff. Indicatorul de poziţie în stream este avansat cu numărul de bytes citiţi în total, astfel încât, o operaţie subsecventă printr-o funcţie fread() poate continua preluarea din stream, dacă datele deja există sau poate realiza o nouă umplere a tamponului streamului. Dacă streamul deschis la intrare este asociat cu un fişier de tip text, atunci funcţia fread() înlocuieşte perechea de caractere CR/LF cu un singur caracter newline. Funcţia fread() returnează numărul de blocuri complete efectiv citite, număr care poate fi mai mic decât cel precizat prin parametrul count, dacă a apărut o eroare sau dacă sa întâlnit sfârşitul de fişier, fără ca ultimul bloc să fie complet. Funcţiile ajutătoare feof() şi ferror() pot fi utilizate pentru a putea distinge situaţia survenită. Funcţia fwrite() înserează în tampon, începând cu poziţia curentă, dată de indicatorul de poziţie al acestuia, până la count blocuri, fiecare de lungime bsz, din zona de memorie buff. Indicatorul de poziţie al streamului de ieşire este incrementat cu numărul de bytes efectiv înseraţi în tamponul streamului. Dacă streamul a fost deschis ca stream text, atunci funcţia fwrite() înlocuieşte fiecare caracter newline cu secvenţa de caractere CR/LF. La în terminare, funcţia fwrite() returnează numărul de blocuri complete efectiv înserate care poate fi mai mic decât count, dacă a apărut o situaţie de eroare.

2.6 Controlul sfârşitului de fişier şi poziţionarea în fişier Aşa după cum s-a arătat în partea de început a acestui capitol, prelucrarea fişierelor este adesea o prelucrare secvenţială ciclică, în care fiecare entitate citită este tratată în acelaşi mod şi iterarea se încheie atunci când se detectează sfărşitul de fişier. Sistemul de funcţii de intrare/ieşire oferă funcţia feof() care testează flagul corespunzător din structura FILE şi întoarce o valoare întregă nenulă, corespunzătoare situaţie de sfârşit de fişier sau valoarea 0, pentru situaţia contrară. Funcţia are următorul prototip: int feof( FILE *stream ); Prelucrarea fişierelor binare se poate realiza şi în acces direct, dacă programul defineşte poziţia de început a blocului care trebuie tratat. Implementarea streamurilor binare introduce o modalitate de control a poziţiei în fişier şi funcţii care să permită definirea şi

Prof.dr.Valer Roşca ULBS

57

aflarea (interogarea) acesteia. In fig. 2.3 se prezintă întuitiv modul în care este concepută poziţionarea, având în vedere cele trei posibilităţi de referinţă (origine): începutul de fişier, poziţia curentă în fişier şi sfârşitul de fişier.

+offset

pe

- offset Inceput fişier

SEEK‗SET

- offset

pe

Poziţie curentă

SEEK‗CUR

+ offset

Sfârşit fişier

SEEK‗END

Fig.2.3 – Poziţia efectivă pe în fişier în raport de origine şi offset

Poziţia efectivă pe se calculează ca sumă algebrică între un număr care desemnează originea, exprimat prin una din constantele SEEK_SET, SEEK_CUR, SEEK_END, definite în stdio.h şi o deplasare (offset). Dacă se prelucrează blocuri de o mărime bsz şi blocul respectiv este al n - lea faţă de origine, spre dreapta, respectiv spre stânga, poziţia pe a începutului blocului dorit (primul byte din stânga), se face astfel: pe=SEEK_SET pe=SEEK_CUR pe=SEEK_END pe=SEEK_CUR

+ (n-1)*bsz + (n-1)*bsz n*bsz n*bsz.

Pentru orice fişier deschis pe un dispozitiv care admite poziţionare directă, sistemul de operare păstrează un pointer la fişier, exprimat ca o variabilă întregă de tipul long. Acest pointer este actualizat corespunzător după oricare operaţie de citire/scriere. Valoarea lui poate fi modificată şi aflată prin program (interogare), pe baza apelului unor funcţii specifice. Dacă fişierul este un fişier curat binar, adică fără caractere CR/LF, poziţionarea prin program se face fără probleme, calculul de poziţie, aşa cum s-a indicat mai sus, este totdeauna corect, deoarece blocul văzut în stream şi cel fizic sunt identice. La fişierele text care sunt asociate cu un stream binar, datorită modului în care sunt tratate secvenţele CR/LF, blocul intern şi cel extern diferă. In acest caz, există garanţia poziţionării corecte numai pe începutul de fişier, sfârşitul de fişier şi o repoziţionare pe poziţia curentă, dar numai dacă valoarea pointerului de poziţie s-a obţinut prin interogarea sistemului de operare. Aşa se explică prezenţa mai multor funcţii legate de poziţionare şi interogare a poziţiei pe care fişierul stdio.h le prevede. Un prim grup de funcţii sunt fseek() şi ftell(), pentru poziţionare şi respectiv interogarea relativă, descrisă mai sus. Aceste funcţii au prototipurile următoare: int fseek( FILE *stream, long offset, int origine ); long ftell( FILE *stream ); şi se utilizează, de regulă, atunci când fişierul este un fişier curat binar, creat în modul de lucru cu stream binar asociat.

Prof.dr.Valer Roşca ULBS

58

Parametrii celor două funcţii au semificaţia prezentată mai înainte, de aceea, aici trebuie remarcate numai valorile pe care aceste funcţii le returnează. Funcţia fseek() returnează zero în caz de poziţionare reuşită şi o valoare negativă în caz de eroare. Funcţia ftell() returnează valoarea pointerului la fişier, în caz de reuşită şi o valoare negativă, în caz de eroare. Valoarea de poziţie returnată de ftell() este calculată ca offset faţă de începutul de fişier ca origine. Dacă este necesară o nouă poziţionare, atunci această valoare returnată de ftell() poate fi utilizată ca offset în funcţia fseek(). Un al doilea grup de două funcţii complementare fgetpos() şi fsetpos(), prima pentru a interoga poziţia pointerului în fişier şi a doua pentru a seta poziţia acestuia, utilizează o schemă de poziţionare absolută, referitor la începutul fişierulu. Acestea au prototipurile: int fgetpos( FILE *stream, fpos_t *pos ); int fsetpos( FILE *stream, const fpos_t *pos ); Tipul de date fpos_t este definit în stdio.h ca un un tip întreg lung. Parametrul pos este cel care recepţionează valoarea pentru pointerul fişierului în interogarea cu fgetpos() şi este sursă de valoare pentru fsetpos(). Funcţiile pot fi utilizate, ca alternativă, în cazul fişierelor curat binare, pentru a evita poziţionarea relativă. Un astfel de mod de lucru este util, în măsura în care poziţia curentă ce se obţine prin interogare este apoi reutilizată, pentru repoziţionarea pe acelaşi bloc, iar modificarea curentă a pointerului este realizată prin funcţiile citire/scriere. O prelucrare, în acest sens, apare ca singura corectă în cazul fişierelor text, având în vedere observaţia făcută la începutul paragrafului cu privire la prelucrarea binară a fişierelor text.

2.7 Algoritmica lucrului cu fişiere In realizarea unor aplicaţii complexe care utilizează fişiere, se ridică o serie de probleme cu privire la proiectarea conţinutului fişierelor şi a algoritmilor de lucru cu acestea. Aşa sunt, de exemplu, aplicaţiile în care fişierele sunt utilizate pentru evidenţă, care presupun operaţii de actualizare, pentru care este necesară organizarea de fişiere cu acces direct care să poată face distincţie între blocuri, prin cheie primară şi să poată sesiza dacă un bloc are sau nu un conţinut valid. Programatorul trebuie să suplinească lipsa în limbaj a unor facilităţi în acest sens, de aceea, în cele ce urmează se atrage atenţia aupra unora din ele şi se sugerează modul în care pot să fie depăşite. In toate consideraţiile care se fac în continuare, se presupune că fişierele se prelucrareză la nivel delinie sau de bloc, pentru care se utilizează termnul de articol. 2.7.1 Prelucrarea secvenţială Aplicaţiile practice de evidenţă presupun, de multe ori, prelucrarea integrală a unui fişier, în care fiecare articol face obiectul aceluiaşi mod de tratare (prelucrare pe articole). Din punct de vedere algoritmic, se poate da o schemă generală de lucru în care se construiesc proceduri ce trebuie să cuprindă obligatoriu anumite elemente. In fig.2.4, aceast mod de prelucrare, denumit prelucrare secvenţială, este redat sub formă de schemă logică. In programarea operaţiilor schemei de prelucrare, se recomandă construirea de funcţii pentru cele trei proceduri care să fie apoi apelate de funcţia main(), aşa cum se sugerează în listingul 2.2. In această rezolvare, funcţiile au drept parametru, pointerul la stream, funcţia de prelucrare are, în plus şi un pointer la articol şi fiecare funcţie poate avea şi alţi parametri, după necesităţi. Se poate concepe un program care să definească, inclusiv streamu, variabile globale acele variabile care sunt utilizate de funcţii, fiecare din ele urmând să-şi definească propriile variabile locale. Schema generală poate fi particularizată pentru diferite situaţii de prelucrare, scriind corespunzător codul funcţiilor implicate, funcţia main() rămânând aceeaşi.

Prof.dr.Valer Roşca ULBS

59

•Deschidere fisier f •Operatii care se fac la inceput de fisier

STAR

Inceput_fisie

•Citire articol curent •Tratare articol curent Da

NOT EOF(f) Nu Sfarsit_fisier

Prelucrare

•Operatii care se fac la sfarsit de fisier •Inchidere fisier f

STOP

Fig.2.4 – Scema generală de prelucrare secvenţială a unui fişier

Listingul 2.2 – Programarea schemei de prelucrare secvenţială #include // Definirea unui tip pentru articol typedef {……………} ARTICOL; // Declararea prototipurilor functiilor void Inceput_fisier(FILE *f,…); void Prelucrare(FILE *f, ARTICOL *a,…); void Sfarsit_fisier(FILE *f,…); // Definirea functie main() void main(void) {FILE *f; ARTICOL a; ……… Inceput_fisier(f,…); while (!feof(f)) Prelucrare(f,&a,…); Sfarsit_fisier(f,…); } // Definirea funcţiilor 2.7.2 Controlul paginilor în realizarea rapoartelor Prelucrarea unor fişiere poate să conducă la realizarea de rapoarte pentru care se cere un anumit mod de punere în pagină şi de numerotare a paginilor. Implementarea lucrului cu fişiere în C nu oferă nici o facilitate, în acest sens, de aceea programatorul trebuie să construiască un mecanism prin care să poată controla punerea în pagină. Problema realizării de rapoarte cu aspect deosebit este complexă, de aceea, în discuţia care urmează se sugerează numai modul în care se poate concepe un algoritm simplu de control al paginării. Se presupune cazul prelucrării secvenţiale a unui fişier f şi obţinerii unui fişier g de tipul text

Prof.dr.Valer Roşca ULBS

60

pe care se scrie raportul şi care apoi este trimis spre împrimare. Acest mod de lucru este tipic, având în vedere că imprimarea propriu-zisă, în reţele de calculatoare, este un proces separat, controlat de un server de imprimare. In esenţă, controlul paginării se bazează pe variabile ajutătoare pentru contorizarea rândurilor scrise contrand şi construirea numerelor de pagină contpag. Aici, se face ipoteza că programul construieşte raportul pe un anumit tip de pagină pe care este disponibil un anumit număr de rânduri maxr, pentru scrierea cu fontul implicit. Pentru realizarea algoritmică, se dezvoltă corespunzător procedurilie din schema prelucrării secvenţiale, aşa cum rezultă din fig.2.5. S-a presupus că la scrierea unui rând se consumă nr linii, inclusiv liniile goale necesare, iar procedura CapRap(), de construire a capului unei pagini, consumă rc linii. Se remarcă, de asemenea, modul în care se comandă saltul la pagină, în această procedură, prin scrierea unei linii care conţine secvenţa escape formată din caracterul '\f' (formfeed).

Inceput_fisier

•Deschide fisierul f de intrare •Deschide fisierul g pentru raport

contpag = 0 contrand = maxr + 1

Prelucrare

CapRap

Cireste din f articol curent

contpag++

Scrie in g

'\f'

Prelucreaza articolul curent Da

Nu contrand > maxr

Alte operatii specifice

IESIRE

CapRap

Scrie lini in g pentru rand

• Scrie in g numar pagina • Scrie in g antet • Scrie in g titlu • Scrie in g cap tabel

contrand = rc

IESIRE Sfarsit_fisier

contrand += nr

Alte operatii specifice

IESIRE

• Inchide fisierul f • Inchide fisierul g

IESIRE

Fig.2.5 – Algoritmizarea controlului pentru punere în pagină

Prof.dr.Valer Roşca ULBS

61

2.7.3 Construirea fişierelor binare pentru aplicaţii de evidenţă Fişierele de evidenţă trebuie să poată suporta, în general, toate operaţiile de actualizare: inserare de articole, modificare de articole şi ştergere de articole. Implementarea eficientă a acestor operaţii presupune, în primul rând, valorificarea posibilităţii de acces direct, deoarece, la un moment dat, un număr redus de articole trebuie să fie supuse unor astfel de operaţii. Adresarea directă este uşor implementabilă, cum s-a arătata anterior, dacă articolele posedă o cheie primară, cu valori naturale, iar articolele, în perioada de viaţă a fişierului, acoperă relativ dens (peste 75%) intervalul valorilor posibile. In acest caz, se poate construi aceea transformare n, pentru numărul blocului unui articol, ca o funcţie de forma: n=n(CheiePrimară)=CheiePrimară – ValoreMinimăCheiePrimară Se remarcă, apoi, ideea că fişierul se dimensionează pentru o anumită perioadă de viaţă, suficient de lungă şi orice operaţie, inclusiv operaţia de înserare de articole, se face numai în interiorul acestui spaţiu. In momentul în care apar articole care trebuie înserate în afara cadrului iniţial al fişierului, acesta trebuie să fie reorganizat. Acest mod de lucru presupune o posibilitate de a distinge între blocurile în care s-a înscris un articol şi cele care sunt încă ne ocupate, pentru a evita erorile de suprascriere, datorate unor greşeli de specificare a cheii primare. In al treilea rând, se constată că operaţia de ştergere nu poate fi o ştergere fizică, deoarece, din punct de vedere practic, ar însemna reutilizarea unor valori de cheie primară pentru a identifica alte articole (obiecte) şi acest lucru poate crea confuzii. De aceeea, operaţia de ştergere se face ca o ştergere logică, ceea ce înseamnă păstrarea articolelor în fişier, dar marcarea lor ca inactive. Din consideraţiile de mai sus, rezultă că programatorul trebuie să gândească o structură de articol (fig.2.6) care, prin valorile codificate ale indicatorului de serviciu IS, să permită distincţia între situaţiile în care se poate găsi un bloc: bloc gol, activ sau inactiv şi să conceapă o operaţie de preformare pentru fişier. Preformarea fişierului în seamnă construirea fişierului, la dimensiunile maxime necesare, cu blocuri goale, adică blocuri pentru care indicatorul de serviciu IS să fie zero.

IS

CHEIE PRIMARĂ

RESTUL ARTICOLULUI

• 0 – bloc gol • 1 – bloc activ • 2 – bloc inactiv

Fig.2.6 – Structura blocului pentru un fişier de evidenţă

Realizarea unei structuri de bloc de acest fel, permite derularea corectă a accesului secvenţial, cu posibilitatea de a distinge articolele efective şi, în plus, este posibil un control

Prof.dr.Valer Roşca ULBS

62

asupra validităţii unor operaţii de actualizare, evitându-se distrugerile de articole datorită erorilor de furnizare, de către utilizator, a cheii primare de access (cheie de căutare). Pentru scrierea efectivă a sistemului de programe se pot adopta mai multe tehnici: programe distincte pe operaţii, programe pe grupuri de operaţii (program multifuncţional), sau o tehnică mixtă. Tehnica adoptată depinde, în general, de frecvenţa operaţilor şi de necesitatea de evitare a redundanţei codului. Aşa de exemplu, operaţiile de actualizare se pot incorpora în acelaşi program multifuncţional, dacă ele se execută, în timp, cu o frecvenţă redusă şi codul necesar nu este disproporţionat între aceste operaţii. Se poate adopta o strategie de construcţie a unui program de modificare, dacă această operaţie este frecventă şi un program de actualizare prin înserare şi ştergere. In principiu, este recomandabil să existe un program separat de înserare în acces direct care poate fi utilizat în orice situaţie, inclusiv în timpul primei încărcări cu articole (populare iniţială) care, de regulă, fiind de volum mare, trebuie să fie executată în mai multe etape. Pentru operaţiile care presupun consultarea fişierului, în general, se construiesc programe distincte. Din punct de vedere algoritmic, programele au specificitate, dar, în general, se poate face uz de o schemă de prelucrare secvenţială, dacă se distinge corect postura fişierului de evidenţă în prelucrarea respectivă. Din acest punct de vedere, fişierul de evidenţă poate fi fişier conducător sau fişier condus. Dacă articolele fişierului de evidenţă trebuie tratate secvenţial, iar prelucrarea se încheie când s-a detectat sfârşitul lui, atunci algoritmul tipic de prelucrare este dat de schema prelucrării secvenţiale, prezentată mai înante, în care fişierul de evidenţă este fişier conducător. Aşa este cazul programelor care consultă fişierul pentru realizarea de situaţii sau rapoarte. Dacă fişierul de evidenţă este prelucrat, ca urmare a unui proces secvenţial desfăşurat pe baza altui fişier, schema de prelucrare este, de asemenea, una secvenţială, dar cu alt fişier pe post de fişier conducător. Pentru operaţiile de actualizare de mare volum, de exemplu, este recomandabil ca datele de intrare implicate să fie colectate pe un fişier secvenţial care se extinde, pe măsură ce apar date noi şi periodic, acest fişier este utilizat ca fişier conducător, pentru a realiza actualizarea fişierului de evidenţă. In cazul operaţiilor de actualizare a fişierului de evidenţă, când volumul de date de intrare este redus şi acestea se furnizează direct de la tastatură, tastatura poate fi considerată ca fişier conducător. Tastatura este, deasemenea, fişier conducător, în multe operaţii de consultare aleatoare a fişierului de evidenţă, când utilizatorul doreşte să obţină informaţii din anumite articole. Datorită structurii sale ceva mai deosebite, pentru exemplificare algoritmică, se consideră cazul unui program multifuncţional (fig.2.7). Programul, în întregimea sa, este condus prin tastatură, pe baza unui meniu care se afişează pe monitor ca o listă de operaţii codificate într-un anumit fel, de exemplu prin litere, din care utilizatorul poate alege una. Pentru încheierea procesului, meniul trebuie să cuprindă o operaţie, codificată cu litera T în schemă, care conduce la oprirea execuţiei. Fiecare din operaţiile posibile poate fi imaginată ca o funcţie care, algoritmic, este o subschemă de prelucrare secvenţială, cu fişierul de evidenţă ca fişier conducător sau un alt fişier pe acest post. 2.7.4 Indexarea fişierelor Indexarea unui fişier, denumit fişier bază, este o operaţie de construire a unui alt fişier asociat, denumit fişier index care să faciliteze regăsirea articolelor în acces direct din fişierul de bază. Unui fişier bază i se pot asocia mai multe fişiere index, pentru a putea asigura regăsirea în acces direct a articolelor după mai multe criterii. ■ Index primar. Dacă indexarea se face după cheia primară, atunci indexul este denumit index primar. Un astfel de index este necesar să se asocieze unui fişier de evidenţă, în cazul în care cheia primară nu este proprie pentru definirea numărului blocului asociat unui articol. Aşa de exemplu, este cazul unui fişier de cărţi, pentru care cheia primară este este cota cărţii, exprimată ca un şir de caractere cu o anumită semificaţie pe subşiruri (cota cărţilor se obţine prin codificare zecimală), inproprie pentru calcul. In aceeaşi situaţie se găsesc şi cheile primare obţinute prin codificare secvenţială prin numere naturale cu care se poate calcula numărul blocului, dar utilizarea practică a lor este ineficientă ca spaţiu pe disc, în cazul în

Prof.dr.Valer Roşca ULBS

63

care articolele, în perioada de viaţă a fişierului, lasă goluri prea multe (peste 25% din întregul spaţiu).

START

MENIU(op)

DA op!='T '

op

NU 'A'

'N' 'B'

fA

fB

fN

STOP

MENIU(op)

Fig.2.7 – Schema generală a unui program multifuncţional

Un index primar este, în ultimă analiză, o funcţie definită tabelar care asociază, la fiecare valoare a cheii primare, un număr n≥0, reprezentând numărul relativ al blocului în care este memorat, în fişierul bază, articolul respectiv. Din punct de vedere informatic, un fişier index este un fişier cu articole de forma (ValoareCheiePrimară, n) care poate fi construit, de exemplu, ca un tabel (fig.2.8), sortat după valorile cheii primare, considerată câmp de indexare. In figură, se prezintă fişierul bază şi fişierul index asociat, presupunând, pentru simplitate, o cheie desemnată print-o singură literă.

Prof.dr.Valer Roşca ULBS

64

Fişer bază

F

B

0

A

1

D

2

M

3

4

R

C

5

E

6

O

7

P

8

L

9

10

Q

11

Fişier index (.NDX)

A 2 B 1 C 6 D 3 E 7 F 0 L 10 M 4 O 8 P9 Q 11

Fig.2.8 – Index primar asociat unui fişier bază

Pentru exemplificare algoritmică (fig.2.9), se presupune o cheie primară de tip caracter şi se consideră cazul în care fişierul index poate fi stocat, în întregime în memoria internă, ca un array T, de articole de forma (CH, B), unde CH memorează valorile câmpului de indexare, iar B numărul relativ de bloc în fişierul bază. In aceste condiţii, a construi indexul înseamnă a crea şi sorta intern array-ul T şi apoi a scrie T pe disc. In construirea lui T, se citieşte secvenţial fişierul de bază, în articolul a, cu câmpul a.CP pentru valorile cheii primare şi, pentru fiecare articol citit care are a.IS = 1, se înscrie un element în T, în ordinea în care vin articolele, variabila n fiind cea care ţine evidenţa numerelor relative de bloc din fişier, iar m pe cea a intrărilor în T. Pentru sortare, se aplică o metodă oarecare de sortare, de exemplu metoda transpoziţiei, ţinând seama că ordinea de sortare se determină prin compararea valorilor consecutive T[k-1].CH şi T[k].CH, k≥2, dar se interschimbă, dacă este cazul intrarea k în întregimea ei, cu intrarea k-1. Scrierea lui T sortat pe disc se poate realiza ca un bloc unic care acoperă toate intrările efectiv ocupate. Dacă T se declară ca array static, de o mărime maximă, atunci apare implicit situaţia când se completează cel mult un număr de intrări care nu totdeauna umplu pe T. Pentru utilizare ulterioară, este convenabil să se reţină în fişierul de index şi numărul de intrări efectiv ocupate în T şi, în acest sens, se poate rezerva prima intrare si să înscrie acest număr în T[0].B. Astfel, în T, intrările efective pentru articolele fişierului de bază încep de la unu. Operaţiile de atribuire de tip şir de caractere şi comparare caracter trebuie să fie funcţii scrise de programator, având în vedere că este nevoie de copiere si de comparare de şiruri de aceeaşi lungime care nu au caracterul null terminator. Pentru funcţia de copiere se aplică o atribuire la nivel de caracter, iar pentru funcţia de comparare, necesară în sortare, trebuie aplicată o relaţie lexicografică de forma string1 > string2 şi funcţia va întoarce 1 dacă relaţia este adevărată şi 0 altfel. ■ Index regular. Indexarea poate fi aplicată şi după alte câmpuri ale articolululi, dacă se doreşte să se creeze un instrument pentru acces rapid la articolele care îndeplinesc o anumită condiţie în raport cu valorile câmpului de indexare. Practica programării recomandă tipul de index,

Prof.dr.Valer Roşca ULBS

65

denumit index regular, care cuprinde câte o intrare separată pentru fiecare articol şi admite valori multiple identice pentru câmpul de indexare. Indexul se ţine sortat, de regulă crescător, după valorile câmpului de indexare. Intr-un astfel de index, se pun în evidenţă secvenţe de articole care au aceeaşi valoare pentru câmpul de indexare, dar sunt localizate aleator. Rezultă că indexul regular este un instrument care permite o prelucrare sortată a articolelor fişierului de bază, după valorile câmpului de indexare, fără ca fişierul de bază să fie reorganizat fizic faţă de momentul creării. Adică, indexul regular reprezintă o sortare logică a fişierului de bază, de care pot beneficia toate prelucrările secvenţiale care presupun sortare după câmpul utilizat în indexare. Un astfel de exemplu va fi dat în paragraful următor. Trebuie remarcat, de asemenea, că un index regular poate asigura răspuns la unele întrebări cu privire la conţinutul fişierului de bază, fără ca acesta să fie prelucrat, fişierul de index fiind singura sursă pentru răspuns. De exemplu, dacă se presupune un fişier de evidenţă a salariaţilor unei companii şi indexarea se face după câmpul Salariu, din articolul acestui fişier, atunci fişierul de index poate răspunde singur la întrebări cu caracter statistic de genul: •numărul de salariaţi (ponderea) care au un anumit nivel de salaraiu; •numărul de salariaţi pe fiecare nivel de salarizare practicat de companie; •numărul salariaţilor care au un salariu mai mic (mai mare) decât un nivel dat etc. In fine, se constată că, din punct de vedere algoritmic, un index regular se poate crea similar cazului indexului primar.

Deschide fisier baza b

m=0 n = -1

Sfarsit_fisier

Prelucrare

Inceput_fisier

Inchide fisier baza b

Citeste articol din b

T[0].B = m

n=n+1 NU

DA Sortare(T)

a.IS=1 IESIRE m=m+1

Deschide fisier index x

Copiere(T[m].CH, a.CP) Scrie T in x T[m].B = n Inchide fisier index x

IESIRE

IESIRE

Fig.2.9 – Algoritmul de indexare după cheie primară

Prof.dr.Valer Roşca ULBS

66

■ Utilizarea indexului primar. In ipoteza făcută la crearea indexilor, un program de prelucrare pe bază de index, trebuie să încarce fişierul de index în array-ul T, înainte de oricare operaţie de acces la fişierul de bază. Pentru o operaţie de acces, cu o cheie de căutare CC, trebuie derulaţi următorii paşi: 1. Se caută secvenţial în T intrarea în care valoarea câmpului CH al acesteia este identică cu CC. Dacă această valoare este găsită în intarea k se trece la pasul 2. Dacă nu există valoarea CC în nici o intrare din T se tratează cazul de excepţie, de exemplu, prin mesaj către utilizator şi operaţia de acces este terminată. Aici trebuie remarcat că, datorită indexului sortat, situaţia de căutare fără succes poate fi sesizată şi înainte de parcurgerea integrală a lui T, imediat ce valoarea CC devine mai mare decât valoatrea curentă CH. 2. Se preia în n numărul blocului T[k].B şi se calculează poziţia de început a acestuia, pe baza relaţiei pe = (n -1) * LungimeBloc. Se comandă, prin funcţia fseek(), poziţionarea în fişierul de bază, relativ la începutul fişierului şi cu offsetul pe. 3. Se execută operaţia de citire sau scriere necesară. Consideraţiile cu privire la indexare reprezintă o punere în temă. In practică problematica indexării este mult mai vastă şi complexă, iar realizarea indexilor cere structuri de date mai eficiente, ca de exemplu structurile de tipul arbore binar echilibrat. O problemă deosebită este cea a întreţinerii indexilor, având în vedere operaţiile de înserare şi ştergere de articole. O modalitate acceptabilă de întreţinere ar putea fi aceea a reindexării tuturor indexilor după execuţia programelor de inserare/ştergere. In condiţiile exemplificate mai sus, reindexarea se poate realiza cu acelaşi program cu care s-a realizat indexarea, reconstruind, de fiecare dată, indexul. Dacă fişierul de evidenţă are articole cu multe câmpuri şi, pentru o bună parte din ele, se construiesc indexi, apare o problemă suplimentară, de evidenţă a fişierelor index, deoarece, cu timpul ar putea apare uitarea, din punctul de vedere al desinaţiei şi/sau actualizării lor. In practică, problema se rezolvă prin construirea unui index complex, denumit index structural, care înglobează, prin structură de date adecvată, toţi indexii unui fişier. 2.7.5 Prelucrare pe grupe de articole In lucrul cu fişierele binare, sunt cazuri în care prelucrarea trebuie realizată pe grupe omogene de articole. O astfel de prelucrare este eficientă, dacă fişierului de prelucrat i se asociază un index de tip regular, construit după câmpul ale cărui valori definesc grupele de articole. De exemplu, dacă fişierul de evidenţă este un fişier de salariaţi, care aparţin unor unităţi organizatorice ale companiei (birouri, ateliere etc) şi această apartenenţă este memorată în articole prin valorile (codificate) ale unui câmp denumit compartiment, atunci se poate obţine, de exemplu, o situaţie care arată, pentru fiecare compartiment care este fondul de salarii necesar. Fondul de salarii, pentru un compartiment, se obţine sumând salariile din grupul de articole ale salariaţilor care aparţin de acel compartiment. Câmpul după care se definesc grupele este denumit caracteristică de grupare CG sau caracteristică de control şi prelucrarea pe grupe este cunoscută ca o prelucrare cu grupare sau cu control după o caracteristică. (Deoare ce, de multe ori la nivelul grupelor se fac sume pe anumite câmpuri, prelucrarea se numeşte şi cu grad de total). In practică, este uzual ca prelucrarea cu grupare să determine la nivelul fiecărei grupe, mărimi cum sunt: numărul de articole, valorile extreme pentru un anumit câmp, suma valorilor pentru un câmp, media valorilor pentru un câmp etc. Acestea pot fi determinate separat sau mai multe din ele în aceeaşi prelucrare. Indiferent de de mărimile care se calculează, aspectul central al prelucrării se referă la controlul asupra grupelor, având în vedere că acestea se constituie ad-hoc şi nu au o delimitare marcată fizic. Singurul mod în care grupele pot fi sesizate este mecanismul controlului curent de apartenenţă, pe baza valorilor caracteristicii de grupare CG şi a ipotezei de sortare introdusă de indexul regular care se bazează pe următoarele reguli: •primul articol dintr-o grupă, prin valoarea caracteristicii de grupare, dă valoarea ACG care caracterizează grupa;

Prof.dr.Valer Roşca ULBS

67

•oricare alt articol al gupei are valoarea caracteristicii de grupare CG egală cu ACG.

Citire_baza

START

k=k+1

Inceput_fisier

NU

DA k≤m

DA SF=0 n = T[k].B pe = n * LungimeBloc

NU

Inceput_grupa

Pozitionare in b la pozitia data de pe

SF = 1

SF=0 si ACG= a.CG

DA

Citeste articol din b Prelucrare

Sfarsit_fisier NU

STOP

IESIRE

Sfarsit_grupa

Procedura ========= Inceput_fisier

Operaţii ======== •Deschirere fisier baza b • Incarcare index in T • m =T[0].B ; k = 1; SF = 0 • Citire_baza (citire initiala) • Operatii specifice la inceput de fisier

Inceput_grupa

• ACG = CG • Operatii specifice la inceput de grupa

Prelucrare

• Operatii de prelucrare a articolului citit • Citire_baza (citire curenta)

Sfarsit_grupa

• Operatii specifice la sfarsit de grupa

Sfarsit_fisier

• Inchidere fisier baza b • Operatii specifice la sfarsit de fisier

Fig.2.10 – Schema generală de prelucrare cu grupare a unui fişier

Prof.dr.Valer Roşca ULBS

68

In baza acestui mecanism, rezultă că se poate aplica o schemă de lucru secvenţial, care marchează începutul prelucrării unei grupe prin memorarea în variabila ACG a valorii CG citită din primul articol al acesteia. Următorul articol citit, în ordinea dată de sortare, aparţine aceleaşi grupe, dacă valoarea citită pentru CG este egală cu ACG. Altminteri, grupa s-a terminat şi începe o altă grupă. O situaţie aparte are ultima grupă care se termină atunci când citirea curentă constată că nu mai există articole. Astfel, se pot formula reguli generale pentru terminarea unei grupe şi pentru terminarea prelucrării însăşi, de forma: •o grupă se termină atunci când, în procesul citirii secvenţiale, se schimbă valoarea caracteristicii de control CG faţă de variabila ACG sau nu mai există articole; •prelucrarea se încheie atunci când nu mai există articole de citit. In figura 2.10, este redată o schemă generală care poate fi aplicată, prin particularizare corespunzătoare a procedurilor, pentru oricare problemă de prelucrare de acest tip. Prelucrarea unei gupe presupune un număr necunoscut de paşi, dar cel puţin unu, de aceea structura de control fundamentală este o ciclare cu condiţie logică. Dacă se ţine seama de faptul că ultima grupă se încheie la terminarea fişierului, pentru uniformitatea tratării, prelucrarea întregului fişier nu se poate face prin ciclare cu numărător, pe baza valorii m=T[0].B care arată numărul articole active. De aceea s-a introdus o variabilă SF, pentru realizarea ciclării la nivel de fişier care, iniţial are valoarea 0, semificând faptul că fişierul de bază nu a fost în întregime prelucrat şi valoarea 1, atunci când nu mai sunt articole de prelucrat. Accesul la articolele fişieruli de bază se face prin procedura Citire_baza care se foloseşte de indexul asociat. Pentru claritatea algoritmului s-au notat T[k].CG şi T[k].B câmpurile din intrarea k a lui T. Procedura de citire citeşte articolul din fişierul de bază, dacă un astfel de articol mai există sau atribuie valoarea 1 variabilei SF, dacă nu mai sunt articole de prelucrat. Controlul terminării articolelor se face după după numărul m=T[0].B, prin variabila de contorizare k. Procedurile de prelucrare cuprind operaţii obligatorii şi operaţii specifice. Prin particularizarea operaţiilor specifice se pot obţine schemele pentru diferite cazuri de prelucrare. Atunci când programatorul trebuie să rezolve o astfel de problemă, trebuie să distingă aceste operaţii şi, eventual, să îşi realizeze algoritmul detaliat, la nivelul acestor proceduri.

2.8 Un exemplu de aplicaţie de lucru cu fişier binar Pentru a clarifica modul în care pot fi utlizate direct fişierele binare, s-a construit o aplicaţie condusă prin meniu. Aplicaţia trebuie să creeze şi să actualizeze un fişier de salariaţi (suboperaţia de modificare salariu) care, pentru simplitate, are un articol cu următoarea structură: marca: întreg ≥ 100; nume: text de cel mult 30 caractere (numai nume fără prenume !); salariu: întreg lung. Funcţia principală main() a aplicaţie este monitor multifuncţional care lansează operaţiile de preformare, inserare, actualizare şi afişare a fişierului, pe baza opţiunii dată de utilizator, la solicitarea funcţiei pentru meniu Meniu(). Operaţia de afişare a fost introdusă pentru a putea vizualiza fişierul, după creare şi după actualizare, pentru control, având în vedere că acesta, ca fişier binar, nu este direct lizibil. Pentru fiecare din cele patru operaţii, sa realizat o funcţie: FormatFile(), InsertFile(), UpdateFile() şi ViewFile(). Pentru a reduce redundanţa codului, s-a introdus o funcţie pentru deschidere de fişier OpenFile() care este apelată corespunzător de funcţiile pentru operaţii. In acest program, redat în listingul 2.1, s-au preferat variabilele globale legate de fişier. In acest sens, s-a definit tipul de date SALARIAT şi s-a declarat o variabilă fişier fprs, alături de o variabilă articol artS, ca zonă tampon, care vor fi utilizate în toate operaţiile cu fişierul, din alte puncte ale aplicaţiei. De asemenea, s-a presupus că fişierul are un director şi un nume predefinit, specificatorul acestuia fiind variabila globală pstrFile. De remarcat, de

Prof.dr.Valer Roşca ULBS

69

asemenea, modul de control asupra operaţiei de deschidere, cu utilizarea variabilei globale a sistemului errno şi a funcţiei strerror(), pentru a obţine mesajul de eroare. Listingul 2.1 – Fisierul aplicaţiei cu fişier binar #include #include #include #include #include #define nMaxArt 10 /* Declarare tip de data pentru articolul fisierului */ typedef struct {int IS; int marca; char nume[31]; long salariu;} SALARIAT; /* Declarare fisier si a zonei sale articol */ FILE *fprs; SALARIAT artS; char pstrFile[]="C:\\CCurs\\Personal.dat"; /* Prototipuri de functii */ char Meniu(); int OpenFile(char * mode); void FormatFile(); void InsertFile(); void UpdateFile(); void ViewFile(); /* Functia principala */ void main(void) {char op; op = Meniu(); while(op != 'T') {switch(op) {case 'P': FormatFile(); break; case 'I': InsertFile(); break; case 'M': UpdateFile(); break; case 'L': ViewFile(); break; default:puts("Operatie necunoscuta !"); } op = Meniu(); } getch(); } /* Functia de pentru meniu */ char Meniu() { char op; clrscr(); puts("\nMENIU"); puts("P - Preformare fisier"); puts("I – Inserare articole in fisier");

Prof.dr.Valer Roşca ULBS

70

}

puts("M - Modificare salariu"); puts("L - Listare fisier"); puts("T - Terminare"); printf("Operatia dorita: "); scanf("%1s", &op); op = toupper(op); return op;

/* Functia pentru deschidere de fisier */ int OpenFile(char * mode) { char* opn; fprs = fopen( pstrFile, mode); if (!fprs) { opn = strerror(errno); printf( "\nNu se poate deschide fisierul %s,\n " "Causa : %s,\n", pstrFile, opn); return 0; } else return 1; } /* Functia pentru preformare FormatFile */ void FormatFile() {int k; artS.IS = 0; artS.salariu = 0; strcpy(artS.nume, " "); if(!OpenFile("wb") exit(1); for(k=0; k= 100 ) && (m_marca <= 100 + nMaxArt – 1)) { /* Verificarea non prezentei articolului */ offset=(m_marca-100)*sizeof(SALARIAT); fseek(fprs, offset, SEEK_SET); fread(&artS, sizeof(SALARIAT), 1, fprs); if(artS.IS == 0) {/* Pregatire si scriere articol in fisier */ artS.marca = m_marca; printf("Nume: "); scanf("%s",m_nume);

Prof.dr.Valer Roşca ULBS

71

strcpy(artS.nume, m_nume); printf("Salariu: "); scanf("%ld", &m_salariu); artS.salariu = m_salariu; artS.IS = 1; /* Scrire articol in fisier in acces direct */ fseek(fprs, offset, SEEK_SET); fwrite(&artS, sizeof(SALARIAT), 1, fprs); } else printf("\n EROARE : Articol deja prezent. "); printf("\nMarca: "); scanf("%d", &m_marca);

} fclose(fprs); }

/* Functia pentru actualizare UpdateFile */ void UpdateFile() { int m_marca, m_proc; long nSal,vSal, offset; /* Deschiderea de fisier pentru citire/sciere. Iesire, la esec. */ if(!OpenFile("r+b")) exit(1); /* Secventa de actualizare a fisierului */ puts("\n Se introduc, pe rand, marcile articolele de modificat.\n " " Procesul se termina prin marca zero.\n "); printf("\nMarca: "); scanf("%d", &m_marca); while ((m_marca >= 100 ) && (m_marca <= 100 + nMaxArt – 1)) { /* Verificarea prezentei articolului */ offset=(m_marca-100)*sizeof(SALARIAT); fseek(fprs, offset, SEEK_SET); fread(&artS, sizeof(SALARIAT), 1, fprs); if(artS.IS == 1) {/* Modificarea interna a salariului */ printf("Procentul: "); scanf("%d", &m_proc); vSal=artS.salariu; nSal=(long)(vSal+m_proc*vSal/100); artS.salariu=nSal; /* Rescriere articol in acces direct */ fseek(fprs, offset, SEEK_SET); fwrite(&artS, sizeof(SALARIAT), 1, fprs); } else printf("\n EROARE : Articol inexistent. "); printf("\nMarca: "); scanf("%d", &m_marca); } fclose(fprs); } /* Functia pentru listarea fisierului ViewFile */ void ViewFile() { FILE* fperslst; int nByteR; char txt[50]; /* Deschiderea de fisier pentru citire */

Prof.dr.Valer Roşca ULBS

72

}

if(!OpenFile("rb")) exit(1); /* Secventa de listare a fisierului */ fperslst = fopen("C:\\CCurs\\Personal.lst", "w"); /* Introducere cap tabel */ fprintf(fperslst, "Marca Nume" " Salariu\n"); fprintf(fperslst, "-----------------------" "-----------------------\n"); /* Citire fisier si introducere articole in tabel */ nByteR=fread(&artS, sizeof(SALARIAT), 1, fprs); while (nByteR) { if(artS.IS == 1) {/* Punere in lista */ sprintf(txt, "%5d %-30s %8ld\n", artS.marca, artS.nume, artS.salariu); txt[strlen(txt)] = '\0'; fputs(txt, fperslst); } nByteR=fread(&artS, sizeof(SALARIAT), 1, fprs); } fclose(fperslst); fclose(fprs);

Preformarea fişierului se realizează prin funcţia FormatFile(). Aceasta pregăteşte un articol astS gol pe care îl scrie secvenţial în toate cele nMaxArt poziţii ale fişierului. Popularea fişierului se face prin funcţia InsertFile() care posedă variabile pentru fiecare din câmpurile viitorului articolului. Funcţia cere, pe rând, componentele unui articol, pregăteşte articolul în artS şi îl înscriere, în acces direct, în fişier. Poziţionarea corectă pe începutul zonei de înscriere a unui articol ţine seama că poziţia este o funcţie de marcă şi de lungimea articolului, aşa cum rezultă din instrucţiunea de calcul pentru variabila offset. Funcţia verifică dacă articolul nu este deja prezent. Procesul de înserare se încheie atunci când, la solicitarea mărcii pentru un nou articol, se dă marcă 0. In acest fel, fişierul poate fi populat, în sesiuni diferite şi extins ulterior, în acelaşi mod. Actualizarea fişierului este realizată prin intermediul funcţiei UpdateFile(). Actualizarea se realizează la unele articole, date prin marcă şi constă în majorarea salariului, la fiecare din acestea, cu un procent specific. Funcţia solicită marca salariatului la care se face mărirea, accesează articolul, solicită procentul de majorare, efectuează modificarea intern şi apoi rescrie articolul. Funcţia lucrează corect, având în vedere structura articolelor. Procesul de modificare se încheie, atunci când, la solicitarea unei noi mărci , se răspunde cu 0. Afişarea fişierului pentru control se realizează prin funcţia ViewFile(), sub formă de raport, pe un fişier de tip text care poate fi ulterior afişat sau imprimat. Fişierul este localizat la fel şi are acelaşi nume cu fişierul de evidenţă, dar diferă prin extensie (.lst). Fişierul se citeşte secvenţial, la nivel de articol binar şi, pentru fiecare articol activ citit se scrie o linie de text în fişierul listă. De remarcat modul în care se urmăreşte aici sfârşitul de fişier, pe baza numărului de bytes citiţi, ştiind că funcţia fread() întoarce zero, atunci când nu mai există articol de citit.

Prof.dr.Valer Roşca ULBS

73

3. Prezentarea grafică a datelor Prezentarea grafică este o modalitate alternativă de afişare a datelor pe monitor care poate facilita inţelegerea şi interpretarea acestora.

3.1 Regimul grafic al monitorului Posibilitatea de a realiza imagini grafice este asigurată de regimul grafic al monitorului. In acest regim, ecranul monitorului este un spaţiu matriceal de puncte (pixeli), cu originea în colţul din stânga sus al ecranului , cu axa Ox orientată spre dreapta şi axa Oy orientată în jos (fig.3.1). Un punct din acest spaţiu are coordonatele (x,y) care exprimă plasarea sa pe coloana x şi linia y. Valorile coordonatelor sun numere pozitive ale căror valori maxime xmax, ymax sunt date de rezoluţia plăcii grafice.

(0, 0)

X

(x, y)

Y

(xmax, ymax)

Fig.3.1 – Ecranul în modul grafic

A afişa date în acest regim înseamnă, în ultimă instanţă, a aprinde cu anumite culori mulţimi de pexeli (desen prin pixeli) sau a trasa colorat segmente de dreaptă (desen prin vectori). Desenul prin pixeli şi desenul prin vectori sunt cele două modalităţi de desenare pe care le suportă, prin hardware, regimul grafic al monitorului. Dacă se are în vedere codificarea binară a culorilor posibile, atunci ori ce imagine se exprimă numeric binar, dacă fiecărui pixel i se asociază culoarea cu care acesta este aprins. Aşa dar, o imagine video se prezintă ca o matrice binară, pe care partea de hardware o utilizează în comanda tubului catodic al monitorului pentru a ilumina corespunzător punctele suprafeţei fosforescente a acestuia. In realizarea imaginii sunt implicate componente hardware şi software. Partea hardware implicată în realizarea imaginilor grafice este placa grafică a monitoruli care cuprinde memoria video şi interfaţa video. • Memoria video, de o anumită mărime, de exemplu 1MB, este o memorie RAM care are rolul de a stoca, sub formă binară, imaginea care se afişează pe ecran. Memoria video este împărţită în pagini, fiecare pagină corespunzând unui ecran. Dacă memoria are mai mult de o pagină, atunci se pot pregăti mai multe ecrane şi, la un moment dat, una din acestea este aleasă ca pagină video, adică pagina care asigură imaginea pe monitor.

Prof.dr.Valer Roşca ULBS

74

• Interfaţa video este partea de comandă (circuitele logice) care asigură preluarea, cu o anumită frecvenţă, a imaginii din memoria video şi care realizează, pe baza ei, semnalele de comandă pentru tubul monitorului de creare şi menţinere a imaginii pe ecran. Refacerea imaginii este realizată cu o frecvenţă de peste 50Hz, astfel încât ochiul uman percepe imaginea ca fiind continuă. Plăcile grafice ale monitoarelor sunt realizate după un anumit standard şi pot să lucreze cu mai multe nivele de rezoluţie şi de culori (moduri grafice). Un mod grafic al unei plăci înseamnă o anumită rezoluţie, un anumit număr de culori şi un anumit număr de pagini pentru memoria video. Partea de software legată de realizarea imaginii este driverul de placă. Acesta asigură servicile necesare pentru iniţializarea şi comanda interfeţei video. Fiecare tip de placă are instalat în sistemul de operare un driver propriu, livrat o dată cu placa respectivă.

3.2 Utilizarea modului grafic In limbajul de programare C, programatorului i se oferă posibilitatea de a utiliza regimul grafic al monitorului, prin intermediul unui ansamblu de componente care comportă trei părţi (sistem grafic): • biblioteca de funcţii, în forma obiect, care oferă serviciile necesare construirii imaginilor. Prototipurile funcţiilor sunt definite în fişierul header graphics.h care conţine, de asemenea, constante simbolice şi structuri de date necesare în lucrul cu funcţiile bibliotecii. • driverele de plăci grafice, sub forma unor unor fişiere executabile cu extensia .bgi. • fonturi pentru afişarea textelor, sub forma de fişiere cu extensia .chr. In instalarea implicită a limbajului, componentele pentru modul grafic sunt plasate întrun director separat, denumit BGI. Pentru a pute fi utilzat, sistemul grafic trebuie să fie instalat în memorie şi iniţializat, iar după folosire, trebuie eliberate resursele care i-au fost afectate. De aceea, biblioteca grafică oferă două funcţii complementare initgraph() şi closegraph() prin apelul cărora se realizează cele două operaţii. Funcţia de iniţializare are forma: void initgraph(int *graphdriver, int *graphmode, char *pathtodriver) Funcţia de iniţializare alocă spaţiu de memorie pentru driverul de placă specificat de parametrul graphdriver, încarcă driverul din directorul dat de parametrul pathtodriver, trece monitorul în regimul grafic şi realizează iniţializările necesare: stabileşte modul grafic pe baza parametruli graphmode, setează la valorile prestabilite variabila pentru punctul curent, paleta de culori, vizorul de desen, variabila de eroare etc. Programatorul poate alege driverul şi un mod grafic aferent dintr-o mulţime prestabilită. Aceste elemete sunt definite în fişierul graphics.h sub forma unor constante simbolice. De exemplu, VGA este constanta pentru a defini driverul de placă grafică VGA, iar constanta VGAHI defineşte modul cel mai inalt acceptat de aceasta: rezoluţie de 640x480, paletă de 16 culori şi o singură pagină de memorie video. Funcţia acceptă o manieră alternativă de stabilire a driverului şi a modului, denumită autodetecţie. Dacă se iniţializează parametrului graphdriver cu valoarea dată de constanta DETECT, atunci funcţia interoghează sistemul pentru a afla driverul pentru placa cu care este echipat monitorul calculatorului şi alege modul cu cea mai mare rezoluţie al acesteia. De regulă, se preferă autodetecţia, dacă acest mod de alegere nu influienţează negativ imaginea. Dacă imaginea a fost proiectată pentru o anumită placă şi un anumit mod, atunci alegerea trebuie să fie explicită. Aici se are în vedere că plăcile actuale asigură emularea unor plăci inferioare lor, realizate după standardul IBM. Aşa de exemplu, o placă VGA poate lucra ca o placă EGA. Iniţializarea modului grafic poate reuşi sau poate fi ratată, datorită unor cauze cum ar fi insuficenţa memoriei pentru încărcarea driverului, lipsa driverului solicitat, imposibilitatea de a realiza autodetecţia etc. De aceea, biblioteca de funcţii oferă funcţia graphresult() cu care se

Prof.dr.Valer Roşca ULBS

75

poate interoga o variabilă pentru rezultatul iniţializării, pe care funcţia de iniţializare o pune pe zero, la reuşită şi pe o valoare negativă, în caz de eşec. Funcţia grapherrormsg(), care primeşte ca argument codul de eroare întors de graphresult(), întoarce mesajul de eroare aferent ca un string. Reuşita iniţializării poate fi testată comparând valoarea întoarsă de graphresult() cu constanta simbolică grOk. Rezultă, din cele de mai sus, că într-un program care foloseşte regimul grafic, codul poate fi structurat aşa cum se sugerează în listingul 3.1, unde s-a făcut ipoteza că desenarea are loc în funcţia main(). Listingul 3.1 – Structura codului unui program care utilizează modulul de grafică #include .... void main() { int graphdriver, graphmode, err; .... graphdriver = DETECT; initgraph(graphdriver, graphmode, ″C:\\TC\\BGI″); err = graphresult(); if(err != grOk) {printf(″* Eroare de initializare: %s″, grapherrormsg(err)); exit(1); } /* Desenarea imaginii */ .... closegraph(); }

3.3 Grafică în culori Modulul grafic în C oferă posibilitatea realizării de imagini colorate, potrivit cu facilităţile pe care le asigură placa grafică. Sistemul implementează culorile pe principiul paletei de culori. O paletă de culori este un array cu maximum MAXCOLR + 1 componente care se pot încărca cu codurile unor culori, unde constanta MAXCOLR este definită în graphics.h. Există o paletă implicită (defaultpalette) care este iniţializată la momentul încărcării sistemului grafic de funcţia initgraph(). Programatorul poate crea propria sa paletă, într-o structură de tipul palettetype, definit în fişierul graphics.h care, în afară de un array, denumit colors, cu componente char, are un câmp size de specificare a numărului de culori pentru driverul şi modul curent. Odată stabilită o paletă de culori, se presupune că referirea la culorile pe care le conţine se face prin poziţia lor relativă, conformă cu valorile posibile pentru indexul acestuia. Astfel, valoarea 0 se referă la culoarea al cărui cod este în componenta de rang 0, valoarea 1 se referă la culoarea al cărui cod este în componenta de rang 1 etc. Pe baza paletei, programatorul poate stabili cele două culori pe care le utilizează la un moment dat (culorile curente): culoarea de fond şi culoarea de desen. Culoarea de fond (background color) se referă la spaţiul pe care se face desenul, toţi pixelii din această zonă, fiind aprinşi cu aceeaşi culoare. Culoarea de desen (foreground color) este cea cu care se modifică pixelii fondului, pentru a pune în evidenţă imaginea dorită. Dacă programatorul nu stabileşte aceste culori, atunci, implicit, este utilizată culoarea din prima intare a paletei, pentru fond şi cea din ultima intare a paletei, pentru culoarea de desen. De exemplu, în paleta implicită pentru placă VGA, cu paletă de 16 culori, intrarea de rang 0 conţine culoarea negru, iar intrarea de rang 15 conţine culoarea alb, adică desenul se va face cu alb pe fond negru. Programatorul are la îndemână o serie de funcţii pentru a manevra culorile. ■ Determinarea paletei. Deoare ce caracteristicile de culoare depind de placa grafică şi modul grafic selectat, se poate obţine un program relativ portabil, dacă acesta se scrie

Prof.dr.Valer Roşca ULBS

76

astfel încât să îşi determine singur facilităţile pe care le poate utiliza. Pentru aceasta se pot utiliza funcţii cum sunt: • getmaxcolor() – funcţie, fără parametri, care întoarce o valoare intreagă reprezentând indexul maxim din paletă care poate fi utilizat pentru a referi culoarea de desen; • getpalettesize() – funcţie, fără parametri, care întoarce o valoare de tip întreg reprezentând numărul maxim de intrări care pot fi încărcate în paletă pentru modul grafic curent; • getdefaultpalette() – funcţie, fără parametri, care returnează un pointer la paleta implicită, iniţializată la încărcarea driverului; • getpalette(&paleta) – funcţie care încarcă în variabila paleta, de tipul palettetype, conţinutul structurii care defineşte paleta curentă. ■ Modificarea paletei curente. Programatorul poate modifica culorile într-o paletă, selectiv sau global, la toate culorile, dar pentru aceasta trebuie să cunoască codurile de culoare. Codurile culorilor sunt definite prin constante simbolice în fişierul graphics.h pentru tipurile de plăci acceptate. De exemplu, pentru placa VGA, la fel ca la placa EGA, sunt definite constante pentru 16 culori, ca de exemplu, EGA_WHITE, EGA_RED, EGA_MAGENTA, EGA_GREEN, EGA_LIGHTRED etc. Se uitlizează funcţiile: • setallpalette(paleta) – funcţie care încarcă întreaga paletă curentă cu valorile de culoare pe care le dă variabila paleta, de tipul palettetype, încărcată în prealabil cu codurile de culoare; • setpalette(index, codecolor) – funcţie care permite modificarea intrării de rang index, în care se înscrie culoarea dată de constanta codecolor. Dacă unul sau ambii parametrii sunt eronaţi, intrarea rămâne nemofificată şi se semnalează o eroare care poate fi aflată prin grapgresult(). In ambele situaţii, modificarea paletei curente atrage după sine modificarea culorilor desenului existent pe ecran, în concordanţă cu noua configuraţie de culori. Acest lucru poate fi utilizat cu scopul de a produce efecte de culoare deosebite sau pentru a releva un desen ascuns, prin modificarea treptată a culorilor. ■ Determinarea şi modificarea culorilor de fond şi de desen. Funcţiile din această categorie sunt cel mai frecvent utilizate pentru a afla sau defini cele două culori, având în vedere convenţia cu privire la indexul acestora: • setbkcolor (codecolor) – funcţia modifică poziţia de index 0, pentru culoarea de fond, din paleta curentă la culoarea dată de parametrul codecolor; • getbkcolor() – funcţie, fără parametri, care returnează codul culorii de fond, din elementul de index 0, pentru paleta curentă; • setcolor (codecolor) – funcţia modifică poziţia de index maxim, la culoarea dată de parametrul codecolor, pentru culoarea de desen, din paleta curentă; • getcolor() – funcţie, fără parametri, care returnează codul culorii de desen, situată in elementul de index maxim, din paleta curentă. Orice modificare a unor culori afectează numai desenul care urmează a fi realizat şi aceste modificări râmân în vigoare până la o altă setare. In secvenţa care urmează, se salvează cele două culori din paleta curentă, se modifică culoarea de fond la roşu (cod 4) şi cea de desen la albastru (cod 1), se şterge ecranul la culoarea de fond, se desenează o bară albastră şi apoi se restaurează culorile iniţiale: int ColorF, colorD; ColorF = getbkcolor(); ColorD = getcolor(); setbkcolor(4); setcolor(1); cleardevice(); bar(20, 10, 60, 80); setbkcolor(ColorF); setcolor(ColorD);

Prof.dr.Valer Roşca ULBS

77

3.4 Vizor pentru desen Pentru o mai mare flexibilitate în realizarea imaginilor grafice s-a introdus conceptul de vizor de desen. Un vizor (viewport) este o suprafaţă rectangulară de pixeli, delimitată de un dreptunghi virtual care are laturile paralele cu axele de coordonate, definită în interiorul spaţiului grafic al monitorului. Un astfel de dreptunghi se poate defini cu ajutorul funcţiei setviewport() care cere precizarea coordonatelor punctelor pentru colţul stânga-sus şi dreapta-jos: void setviewport(int

v1, int v3, int v2, int v4, int clip)

Aici (v1, v3) şi (v2, v4) sunt coordonatele în spaţiul ecran pentru colţul stânga-sus şi respectiv dreapta-jos ale dreptunghiului, iar parametrul clip se referă la decuparea desenului la limitele vizorului. Dacă nu este setat un vizor curent, se presupune vizorul de dimensiune maximă care este întregul spaţiu ecran (vizor implicit). Vizorul implicit are coordonatele colţurilor (0, 0) şi (getmaxx(), getmaxy()), unde cele două funcţii returnează coordonatele maxime pentru modul grafic ales. Dacă se dau valori incorecte pentru vizor, în raport cu valorile posibile, vizorul nu se setează şi se semnalează eroare. De aceea, pentru a nu ajunge într-o astfel de situaţie, este recomandabil să se stabilească dimensiunile vizorului în raport de coordonatele maxime ale spaţiului. variabila CP care păstrează Odată cu stabilirea vizorului, se iniţializează coordonatele ultimului punct accesat de o funcţie de desenare, denumit punct grafic curent (Current Position) . Vizorul respectiv devine spaţiul curent în care se face desenul, iar toate funcţiile care sunt folosite pentru desenarea propriu-zisă lucrează în coordonate relative la originea vizorului curent care este colţul stânga-sus (v1, v3). Datorită acestei interpretări, la setarea vizorului, punctul curent CP este pus pe (0, 0), pentru ca originea vizorului să fie punctul iniţial. Parametrul clip poate lua valoarea 1, dacă nu se permite ca desenul să depăşească graniţele vizorului sau valoarea 0, în caz contrar. Atunci când desenul realizat printr-o funcţie de desenare depăşeşte spaţiul vizorului, partea excedentară este decupată (clipping) şi nu va fi vizibilă. Se protejează astfel desenul din vizoarele vecine vizorului curent. Un program poate să aibă mai multe vizoare, pentru a crea o imagine mai deosebită, pe care le setează şi resetează într-o anumită ordine. Dacă programul utilizează difeite opţiuni, de exemplu pentru culori, stil de linie etc, după ce a stabilit un anumit vizor curent, atunci acestea sunt valabile numai în interiorul acestuia. Astfel, vizoarele se particularizează şi imaginile în vizor devin mai atractive. De exemplu, culoarea de fond aleasă poate fi efectiv utilizată prin ştergerea acelui vizor prin apelul funcţiei clearviewport(). In secvenţă care urmează se definesc două vizoare. In primul se desenează un cerc, cu grosime implicită de linie, în al doilea vizor se desenează un dreptunghi cu linie groasă şi apoi se revine la primul vizor pentru a tăia cercul cu o linie groasă. Vizoarele se definesc cu clipping şi utilizează culori diferite: roşu şi alb pentru primul şi albatru cu roşu, pentru al doilea. #define CLIP_ON 1 /* Desen in primul vizor */ setviewport(10, 20, 200, 150, CLIP_ON); setbkcolor(4); clearvieport(); setcolor(15); circle(85, 45, 50); /* Desen in al doilea vizor */ setviewport(95, 200, getmaxx() – 80, getmaxy – 40, CLIP_ON);

Prof.dr.Valer Roşca ULBS

78

setbkcolor(1); clearvieport(); setcolor(4); setlinestyle(SOLID_LINE,0, THICK_WIDTH); rectangle(5, 10, getmaxx()- 130, getmaxy()- 50); /* Redesenare in primul vizor */ setviewport(10, 20, 200, 150, CLIP_ON); setlinestyle(SOLID_LINE,0, THICK_WIDTH); line(15, 120, 160, 30);

3.5 Desen prin puncte şi vectori Desenul prin puncte este un mod natural de realizare a imaginilor neuniforme care presupun dierite submulţimi de pixeli care dau suprafeţe specific colorate, fără o anumită regularitate. Biblioteca de funcţii oferă funcţiile putpixel() şi getpixel(), cu următoarele prototipuri: void putpixel (int x, int y, int color); unsigned getpixel(int x, int y); Funcţia putpixel() aprinde pixelul de coordonate (x, y), din vizorul curent, cu culoarea de cod color, iar getpixel() întoarce codul culorii cu care este aprins un pixel cu astfel de coordonate. Biblioteca de funcţii implementează modul de desen prin vectori bazat pe mulţimile regulate de pixeli pe care le presupun segmentele de dreaptă trasate între două puncte. Acest mod facilitează realizarea imaginilor oferind funcţii care pot trasa segmente cu un anumit stil (tip şi grosime de linie) şi cu anumite culori. Funcţiile utilizează culoarea de desen curentă şi stilul de linie curent. Linia implicită este continuă şi are grosimea de un pixel (linie subţire). Programatorul poate seta un alt stil de linie care rămâne valabil până la o nouă setare, prin intermediul funcţiei setlinestyle() , cu prototipul: void setlinestyle(int linetype, unsigned pattern, int thickness). Parametrul linetype se poate exprima prin valorile 0 – 4 sau constantele simbolice (SOLID_LINE, DOTTED_LINE, CENTER_LINE, DASHED_LINE, corespunzătoare USERBIT_LINE), iar parametrul thickness defineşte grosimea liniei, prin valorile 1 şi 2 (NORM_WIDTH, THICK_ WIDTH ) ca linie subţire de un pixel sau linie groasă de trei pixeli. Parametrul pattern dă un model de linie, atunci când tipul de linie este definit de programator (parametrul linetype = 4). Modelul se defineşte prin şirul de 16 biţi ai acestui parametru, pe baza convenţiei că un bit 1 înseamnă pixel aprins, iar un bit 0 un pixel stins. Prin reluare ciclică, se trasează cu acest model linii de ori ce lungime. De exemplu, valoarea 0xF053 (în binar şirul de biţi 1111000001010011) defineşte o linie de forma •••• • • ••. Pentru desenarea de linii există o serie de funcţii care lucrează în vizorul curent şi diferă numai prin ipotezele cu privire la punctul de început şi punctul final al segmentului: void line(int x1, int y1, int x2, int y2); void lineto(int x2, int y2); void linerel(int dx2, dy2). Pentru funcţia line(), trebuie date explicit coordonatele ambelor capete, în timp ce pentru celelalte două, punctul iniţial este considerat automat punctul grafic curent CP. Aceste două funcţii sunt comode, atunci când se leagă între ele segmente pentru a defini linii frânte, când extremitatea iniţială a unui segment coincide cu extremitatea finală a segmentului precedent. In funcţia linerel(), coordonatele punctului final al segmentului care se trasează nu se dau explicit, ci se specifică deplasările dx2, dy2 pe care funcţia trebuie să le adauge algebric la coordonatele punctuli grafic curent pentru a obţine aceste coordonate.

Prof.dr.Valer Roşca ULBS

79

Dacă se are în vedere că punctul grafic curent se poate obţine prin funcţiile fără parametri getx() şi gety(), se pot pune în evidenţă relaţiile de calcul pe care le utilizează funcţiile de trasare pentru a obţine coordonatele absolute (xe, ye) în spaţiul ecran ale unui punct: xe = v1 + x; ye = v3 + y - pentru specificare explicită ; xe = v1 + getx() + dx; ye = v3 + gety() + dy - pentru specificare relativă. Funcţiile de desenare aplică automat clipingul la limitele vizorului, dar, pentru a nu se produce deformare a imaginii, punctul grafic curent este totdeauna fixat la valoarea dată de extremitatea finală a segmentuli specificat prin parametri. Sistemul grafic îi permite programatoruli să mute punctul grafic curent după dorinţă, prin apelul funcţiilor: void moveto(int x2, int y2); void moverel(int dx2, dy2); în care parametrii au semificaţia prezentată la funcţiile de trasare. In exemplul care urmează, se consideră punctele P1(20, 45), P2(40, 25), P3(65, 70), P4(130, 70), date în coordonate absolute ecran care se desenează într-un vizor ale cărui vărfuri sunt (20, 10), (130, 45). Cele trei moduri de scriere a secvenţei de apel pentru desen sunt redate în tabelul 3.1, iar efectul desenării este dat de fig.3.2. Tabelul 3.1 – Secvenţe de apel pentru desenarea punctelor P1 – P4 Cu line() Cu lineto() Cu linerel() moveto( 10, 30) moveto(10, 30) line(10, 30, 30, 10) lineto ( 30, 10) linerel (20, -20) line(30, 10, 55, 55) lineto ( 55, 55) linerel (25, 40) line(55, 55, 70, 25) lineto ( 70, 25) linerel (15, -30)

Prof.dr.Valer Roşca ULBS

80

(0, 0)

(10, 15) (30, 10) (95, 20) (70, 25)

(10, 30)

(120, 55)

(65, 70)

Fig.3.2 – Reprezentarea liniei frânte a punctelor P1 – P4 relativ la vizor In fine, trebuie făcută observaţia că desenarea punctelor şi a segmentelor supune regulii de combinare a pixelilor acestora cu pixelii fondului pentru a realiza un desen opac sau transparent, aşa cum se va arăta în paragraful cu privire la elementele de animaţie.

3.6 Raportul de aspect In realizarea desenelor prin segmente apare un fenomen de deformare care poate fi deranjant. Acesta se datorează formei pixelilor care, cu excepţia modurilor de mare rezoluţie, nu sunt de formă pătratică, ci dreptunghiulară. Aceasta face să se aplice implicit unităţi de măsură diferite pe cele două axe, chiar şi atunci când intenţia programatorului este aceea de a utiliza aceeaşi unitate. In aceste cazuri, deformarea poate fi atenuată dacă, în realizarea desenului, se aplică aplică o anumită corecţie asupra numărului de pixeli ai segmentelor, corecţie dată de raportul dintre cele două dimensiuni ale pixelului. Dacă se notează cu Lpx lungimea pe axa Ox şi cu Ipy înălţimea pe axa Oy a unui pixel, atunci raportul Ra = Ipy / Lpx, denumit raport de aspect, poate fi uitilizat pentru a determina, în pixeli, lungimile segmentelor care se desenează. Pentru a obţine cele două valori, se poate utiliza funcţia getaspectratio() care are forama; void getaspectratio(int * Lpx, int *Ipy) în care cele două valori se dau normalizate la 10000, adică * Ipy = 10000 şi * Lpx ≤ 10000. Dacă se notează cu n numărul de pixeli ai unui segment AB orizontal şi cu m numărul de pixeli ai unui segment vertical CD, atunci petru ca lungimile lor să se găsească într-un raport k, trebuie ca m (n) să se determine în raport de n (m) prin relaţiile: m = Ra * n / k; n = m * k / Ra. Pentru segmente oblice care au un anumit raport, lucrurile sunt mai complicate, având în vedere că acestea sunt aproximate prin pixeli, după un algoritm intern plăcii grafice, care presupune aprinderea celor mai apropiaţi pixeli de linia teoretică, în raport cu panta

Prof.dr.Valer Roşca ULBS

81

acesteia. Dacă se cere desenarea unui segment de o lungime dată în milimetri, atunci o soluţie posibilă ar fi aceea de a construi un dreptunghi virtual care să aibă segmentul respectiv drept diagonală şi pe baza lungimii laturilor să se determine punctele de colţ ale dreptunghiului între care se desenează segmentul oblic. In exemplul următor se desenează, pe întrgul ecran, un pătrat cu latura orizontală de m = 80 de pixeli şi vârful stânga-sus în punctul (50, 30). Deoarece k este 1, numărul de pixeli pentru latura verticală va fi n = 80 / Ra, iar secvenţa de desenare este: int Lpx, Ipy, n; double Ra; getaspectratio(&Lpx, &Ipy); Ra = Ipy/(double)Lpx; n = 80/Ra; moveto( 50, 30); lineto(130, 30); lineto(130, 30+n); lineto( 50, 30+n); lineto( 50, 30); Funcţiile pentru primitive, cum sunt cele de desenare de cercuri şi elipse, utilizează raportul de aspect pentru ca desenul să fie real (cercul să fie cerc şi nu elipsă, de exemplu). Dacă, în condiţiile de utilizare a raportului de aspect, continuă să existe probleme de deformare, acestea se datorează reglajului de aliniere al monitorului. Pogramatorul poate modifica dinamic valorile pentru Lpx şi Ipy, pe bază funcţiei setaspectratio(), cu aceeaşi parametrii ca şi funcţia getaspectratio(), pentru a obţine o potrivire mai bună, acest mod de lucru fiind echivalentul software al reglajului hardware de aliniere al monitorului.

3.7 Scrierea textelor în modul grafic In mod uzual, imaginile grafice conţin text explicativ pentru scrierea cărora sistemul grafic prevede unele facilităţi. In mod implicit, funcţiile de scriere de text utilizează culorile curente de fond şi de desen, textele sunt scrise cu un font prestabilit, de o anumită mărime, scrierea este pe direcţie orizontală şi textul este aliniat la stânga pe un punct, dat de cursorul grafic (punctul grafic curent CP). ■ In mod dinamic, programatorul poate modifica unele atribute ale scrierii prin apelul funcţiilor de setare, pe care le prezentăm, în continuare. • Fontul. Programatorul poate alege între 5 fonturi predefinite, pe care le referă prin codurile 0 – 4 sau prin constantele simbolice corespunzătoare (DEFAULT_FONT, TRIPLEX_FONT, SMALL_FONT, SANS_SERIF_FONT, GOTHIC_FONT). DEFAULT_FONT este fontul matriceal implicit, de 8x8 pixeli, celelate sunt fonturi care se desenează prin segmente (fonturi vectoriale). Programatorul poate instala propriile fonturi vectoriale, astfel încât numărul total de fonturi instalate curent să fie în limita capacităţii tabelei interne a sistemului grafic utilizată în acest sens (maxim 20 de fonturi curent instalate). Un font este instalat temporar, adică acesta este disponibil numai pe timpul execuţiei programului respectiv de grafică. Pentru instalare, se presupune că fontul este memorat pe disc, într-un fişier de extensie .CHR şi instalarea înseamnă încăracarea fişierului respectiv în memorie şi asocierea fontului cu un număr intreg (handle) cu care poate fi apoi referit (vezi funcţia settextstyle()). Instalarea se realizează prin apelul funcţiei installuserfont() care are forma: int installuserfont(char *pathtofont); în care parametrul reprezintă specificatorul fişierului, iar valoarea întoarsă este un handle.

Prof.dr.Valer Roşca ULBS

82

Un font instalat poate fi redimensionat, caraterele acestuia putând fi modificate uniform, prin creştere cu acelaşi factor pe ambele dimensiuni sau pentru fiecare dimensiune în parte (lăţime sau înălţime). • Direcţia de scriere. Diecţia de scriere poate fi orizontală , desemnată prin valoarea 0 (HORIZ_DIR) sau verticală, desemnată prin valoarea 1 (VERT_DIR). Implicită este direcţia orizontală. Caracteristicile de mărime şi de direcţie de scriere constituie stilul textului şi acesta poate fi definit, odată cu algerea fontului, apelând funcţia settextsyle() care are forma: void settextstyle(int font, int direction, int charsize); Fontul dorit se precizează prin handle în parametrul font, direcţia se dă prin parametrul direction, iar factorul de mărire a caracterelor se dă prin parametrul charsize. Factorul de mărire poate fi un număr între 1 şi 10, valoarea 1 însemnând mărimea de definiţie. De exemplu, un font care are matricea de definiţie de caracter de 8x8, la un facor de mărire de 3 va scrie caracterele pe o matrice de 24x24. Dacă mărirea este neuniformă, atunci parametrul charsize trebuie să fie 0 şi factorii de mărire se dau prin apelul funcţiei setusercharsize() care are prototipul: void setusercharsize(int multx, int divx, int multy, int divy); Primii doi parametrii dau factorul multx / divx, pentru lăţimea de caracter, iar ceilalţi doi se utilizează pentru factorul multy / divy, pentru înălţimea caracterelor. De exemplu, dacă fontul curent trebuie să scrie caractere de două ori mai late şi de 1.5 ori mai înalte, atunci cei patru parametrii sunt 2, 1, 3, 2. • Alinierea. Alinierea se face pe direcţia de scriere, în raport cu punctul grafic curent. Pentru scriere orizontală, alinierea poate fi la stânga (valoare 0 – LEFT_TEXT), centrată (valoare 1 – CENTER_TEXT) şi la dreapta (valoare 2 – RIGHT_TEXT). Pentru direcţia de scriere verticală, alinierea poate fi jos (valoare 0 – BOTTOM_TEXT), centrată (valoare 1 – CENTER_TEXT) şi sus (valoare 2 – TOP_TEXT). Pentru a alege modul de aliniere, se apelează funcţia settextjustify() care are forma: void settextjustify(int horiz, int vert); ■ Pentru scriere efectivă, textul de scris trebuie să se prezinte sub formă de string, conform cu regulile de marcare a sfârşitului prin caracterul null. Se poate utiliza una din funcţiile: void outtext(char *string); void outtextxy(x, y, char *string); Dacă se utilizează prima funcţie de scriere outtext(), atunci alinierea se face pe punctul grafic curent, iar, dacă scrierea este orizontală cu aliniere la stânga, după scriere, punctul grafic curent este actualizat, ţinând seama de lungimea textului scris şi fontul utilizat. Dacă se utilizează outtextxy(), atunci punctul de referinţă pentru alinierea textului se dă prin coordonate (x, y) şi, după scriere, punctul grafic curent nu este afectat. Scrierea, cu oricare din cele două funcţii, se face în vizor, adică funcţiile aplică clippingul asupra textului care depăşeşte limita vizorului pe direcţia de scriere. De asemenea, funcţiile de scriere ţin cont de setarea modului de scriere, la fel ca şi alte primitive de desenare, cum s-a arătat şi pentru cazul desenării prin vectori. In exemplul care urmează, se scrie de 4 ori textul ″Limbajul C/C++″ cu fonturile predefinite. Textul se scrie centrat orizontal pe linia mediană verticală a ecranului, începând cu linia y = 50, fiecare linie fiind scrisă cu o altă culoare şi cu o altă mărime: int x, y, k;

Prof.dr.Valer Roşca ULBS

83

char textstr[]=″Limbajul C/C++″; cleardevice(); settextjustify(CETNTER_TEXT, CENTER_TEXT); x=getmaxx()/2; y=50; for (k=1; k<=4; k++) { setcolor(k); settextstyle(k, HORIZ_DIR, k); outtextxy(x,y, textstr); y=y+textheight(textstr)+8; } Uneori, există necesitatea de a cunoaşte lăţimea şi/sau înălţimea textului care se scrie. Se pot utiliza funcţiile textwidth() şi textheight(), aşa cum rezultă şi din exemplul de mai înainte.

3.8 Primitive pentru figuri Pentru a facilita realizarea imaginilor, sistemul grafic posedă funcţii, numite primitive grafice, pentru câteva figuri plane reprezentative: dreptunghiuri, cercuri, elipse, poligoane etc. Unele din aceste primitive umplu figura desenată cu o culoare compactă sau cu un anumit model de haşură. Toate funcţiile au fost concepute să deseneze în vizorul curent, adică în coordonate relativ la originea (v1, v3) a acestuia şi să aplice clippingul. Ca şi funcţiile pentru desenarea de vectori, primitivele utilizează, pentru contur, tipul de linie şi culoarea curent selectate. Dacă o primitivă umple interiorul figurii desenate cu o culoare compactă, atunci aceasta este, implicit, culoarea de desen curentă. Dacă programatorul doreşte haşurarea interiorului figurii, atunci poate alege un anumit model de umplere cu culoare compactă sau haşurare dintr-o mulţime de stiluri prestabilite (2 modele de umplere şi 9 stiluri de haşuri) sau poate să îşi definească propriul model de haşurare. Pentru a alege un model predefinit se utilizează funcţia setfillstyle() care are prototipul: void setfillstyle(int pattern, int color). Parametrul pattern dă, sub forma uni număr întreg sau constantă simbolică, tipul de haşură, iar parametrul color indică culoarea cu care se face haşurarea. In listingul 3.2, este construit un program care utilizează toate modelele predefinite. Listingul 3.2 – Modele de umplere şi haşurare implicite #include #include #include #include #include /* constante pentru numele stilurilo acceptate */ char *fname[] = { "EMPTY_FILL", "SOLID_FILL", "LINE_FILL", "LTSLASH_FILL", "SLASH_FILL", "BKSLASH_FILL", "LTBKSLASH_FILL", "HATCH_FILL", "XHATCH_FILL",

Prof.dr.Valer Roşca ULBS

84

"INTERLEAVE_FILL", "WIDE_DOT_FILL", "CLOSE_DOT_FILL", "USER_FILL" }; int main(void) { /* Auto detectarea modului grafic */ int gdriver = DETECT, gmode, errcode; int style, mdx, mdy; char stylestr[40]; /* Initializarea regimului grafic */ initgraph(&gdriver, &gmode, ""); errcode = graphresult(); if (errorcode != grOk) { printf("Eroare sistem grafic: %s\n", grapherrormsg(errcode)); exit(1); } mdx = getmaxx() / 2; mdy = getmaxy() / 2; for (style = EMPTY_FILL; style < USER_FILL; style++) { /* Slecteaza stilul de umplere */ setfillstyle(style, getmaxcolor()); /* Preia denumirea stilului din array */ strcpy(stylestr, fname[style]); /* Deseneaza o bara umpluta */ bar3d(0, 0, mdx-10, mdy, 0, 0); /* Scrie sub bara textul de definire al stilului */ outtextxy(mdx, mdy, stylestr); /* Asteapta apasarea unei taste pentru a continua */ getch(); cleardevice();

}

} /* Inchide regimul grafic */ getch(); closegraph(); return 0;

Dacă programatorul doreşte un model propriu de umplere prin haşurare, atunci trebuie să definească modelul acestuia prin apelul funcţiei setuserpattern() care are forma: void setuserpattern(char *upattern, int color). Parametrul upattern este un array de 8 bytes care este interpretat ca şir de 64 de biţi. Un bit de valoare 1 indică aprinderea pixelului, la culoarea dată, prin cod, de parametrul color .

Prof.dr.Valer Roşca ULBS

85

Modelul este reutilizat ciclic, până când întreaga suprafaţă interioară a figurii este umplută. De exemplu, apelul funcţiei sub forma: char upattern[] = {″0xff″, ″0x00″, ″0xff″, ″0x00″, ″0xff″, ″0x00″, ″0xff″, ″0x00″}; setuserpattern(upattern, 4); produce o haşură orizontală, de culoare roşie, de forma ••••

••••

••••

.

Principalele primitive pentru figuri sunt grupate pe tipuri după cum rezultă din cele ce urmează. • Primitive pentru dreptunghiuri şi bare. Primitivele pentru aceste tipuri de figuri sunt: void rectangle(int x1, int y1, int x2, int y2); void bar(int x1, int y1, int x2, int y2); void bar3d(int x1, int y1, int x2, int y2, int depth, int topflag); unde (x1, y1) reprezintă colţul stânga-sus, iar (x2, y2) desemnează colţul dreapta-jos al dreptunghiului. Funcţia rectangle() desenează conturul unui dreptunghi, cu linia de stil şi culoare curente, iar funcţia bar() desenează un dreptunghi umplut, cu stilul de umplere curent, dar fără contrur. Funcţia bar3d() consideră o bară (dreptunghi în spaţiu) a cărui faţă este dreptunghiul definit de coordonatele date ca parametru, umplut cu stilul curent, bara are o grosime dată de parametrul depth, iar capacul superior este vizibil sau nu, după cum parametrul topflag este 1 sau 0. • Primitive pentru linii poligonale şi poligoane. Sistemul oferă două proceduri cu care se pot desena linii poligonale închise, respectiv poligoane umplute: void drawpoly(int numpoints, int *polypoints); void fillpoly(int numpoints, int *polypoints). In ambele cazuri, primul parametru precizează numărul de vârfuri, iar al doilea este un array de tipul pointtype, definit în graphics.h, adică un array care are drept componente articole care definesc coordonatele x şi y ale unui punct. Pentru ca linia poligonală să se închidă, trebuie ca numărul de componente ale acestuia să fie numpoints+1, ultima componentă fiind egală cu prima. Funcţia drawpoly() trasează conturul poligonului cu atributele de culoare şi stil de linie curente. Funcţia fillpoly() desenează un poligon umplut cu stilul de culoare şi haşură curent. De exemplu, secvenţa care urmează, desenează un pentagon haşurat cu linii roşii înclinate spre dreapta: pointtype pentagon[6]; pentagon[0].x=50; pentagon[0].y=80; pentagon[1].x=100; pentagon[1].y=60; pentagon[2].x=150; pentagon[2].y=90; pentagon[3].x=120; pentagon[3].y=130; pentagon[4].x=60; pentagon[4].y=110; pentagon[5].x=50; pentagon[5].y=80; setfillstyle(SLASH_FILL, 4); fillpoly(5, pentagon); • Primitive pentru arce, cercuri şi elipse. Funcţiile din această categorie utilizează atributele de culoare şi umplere curente, dar stilul de linie este totdeauna linie continuă. Unghiurile care intervin ca parametri sunt exprimate în grade, măsurate în sens invers acelor de ceasornic

Prof.dr.Valer Roşca ULBS

86

(sens trigonometric), adică cu 00 la ora 3 şi 900 la ora 12. Funcţiile utilizează implicit raportul de aspect pentru a elimina deformarea. Funcţiile de bază sunt: void arc(int x, int y, int stung, int finung, int raza); void circle(int x, int y, int raza); void ellipse(int x,int y,int stung,int finung,int xraza,int yraza); void fillellipse(int x, int y, int xraza, int yraza); pieslice(int x, int y, int stung, int finug, int raza); sector(int x, int y, int stung, int finung, int xraza,int yraza); Parametrii stung şi finung se referă la unghiul de start şi unghiul final, iar raza, xraza şi yraza desemnează razele figurii. Figura se desenează cu centrul în punctul (x, y). Funcţia circle() desenează conturul unui cerc, iar funcţia arc() desenează un arc de cerc care, la limită, poate fi un cerc, depinzând de alegerea unghiurilor. Funcţia pieslice() desenează un sector de cerc umplut care poate fi, la limită, un cerc umplut. Aproape similar este şi cazul elipselor: funcţia ellipse() desenează un arc sau un contur de elipsă, funcţia sector() desenează un sector de elipsă sau o elipsă umplută, iar funcţia fillellipse() desenează o elipsă umplută. De exemplu, secvenţa care urmează desenează un arc, un sector de cerc umplut şi o elipsă umplută: arc(150, 100, 0, 270, 50); pieslice(getmaxx/2, getmaxy/2, 0, 360, 100); fillellipse(150, 150, 300, 75); Trebuie remarcat şi faptul că sistemul grafic posedă şi alte funcţii care permit realizarea de desenete complexe, cum de exemplu este funcţia getarccoords() care furnizează informaţii necesare racordării arcelor cu segmente sau funcţia floodfill() care permite umplerea unei suprafeţe cu o culoare etc. In listingul 3.3, este redat un program care desenează, prin bare în spaţiu, de diferite culori, o histogramă pentru producţia de carne (mii tone) într-o serie de n ani, cu n≤5. Listingul 3.3 – Program pentru desenarea unei histograme prin bare în spaţiu #include #include #define h 100 #define baza 250 #define lat 30 #define dist 30 #define gros 10 #define peste 40 #define sub 5 #define pstart -5 #define font 3 #define titlx 10 #define titly 10 typedef unsigned int vector[10]; unsigned int maxp( vector prod, int n); void main(void) {int an, driver, mode, err, x1,y1,x2,y2, n, i; int charsize, pattern, color; unsigned int pmax; vector p; double k;

Prof.dr.Valer Roşca ULBS

87

char pstr[8]; char anstr[4]; /* Intrarea in regimul grafic */ driver=DETECT; initgraph(driver, mode, ″C:\TC\BGI″); err=graphresult(); if(err != grOk) {printf(″ Eroare regim grafic: %s\n″, grapherrormsg(err)); exit(1); } /* Introducerea datelor */ printf(″\n Numar de ani (<= 10): ″); scanf(″ %d ″, &n); pintf(″\n Primul an al seriei: ″); scanf(″%d″, &an); printf(″\n Productia pe ani: ″); for(i=0; i
Prof.dr.Valer Roşca ULBS

88

/* Desenarea liniei baza */ setlinestyle(0, 0, 3); line(pstart, y2, (n+1)*(lat+dist), y2); getch(); } /* Functia de maxim */ unsigned int maxp( vector prod, int n) {unsigned int i, m; m=prod[0]; for(i=1; i
3.9 Transformarea coordonatelor In realizarea graficii computerizate adesea desenul dintr-un vizor este o reproducere, prin micşoare sau mărire a unui desen dintr-un dreptunghi al unui spaţiu cartezian. Dacă se consideră că dreptunghiul din spaţiul real are laturile paralele cu axele, atunci problema care trebuie rezolvată este aceea a determinării coordonatelor punctelor din vizor care corespund punctelor cunoscute din dreptughiul spaţiului real. Figura 3.3 sugerează relaţia dintre cele două dreptunghiuri şi introduce notaţiile care vor fi utilizate în continuare.

Prof.dr.Valer Roşca ULBS

89

x (v1, v3)

(xe0, ye0)

y Y

(xe, ye)

(w1, w3)

(v2, v4)

(xr0, yr0) X (xr, yr) (w2, w4)

Fig.3.3 – Transformarea coordonatelor

Dacă imaginea din spaţiul real este considerată încadrată de dreptunghiul (w1, w3), (w2, w4), iar vizorul este definit de colţurile (v1, v3), (v2, v4), atunci, din asemănarea imaginilor din cele două spaţii şi ţinând seama de orientarea axelor, se pot scrie următoarele egalităţi de rapoarte:

xe − xe 0 v2 − v1 = xr − xr0 w2 − w1 ye − ye 0 v4 − v3 = yr0 − yr w3 − w4

(1)

Dacă se explicitează xe, ye, ţinând seama de faptul că xr0, yr0 şi xe0, ye0 sunt centrele dreptunghiurilor corespunzătoare, se obţine un sistem de relaţii care dau coordonatele absolute ale punctului (xe, ye), în spaţiul ecran:

v2 - v1 v1.w2 − v2.w1 xr + w2 - w1 w2 − w1 (2) v4 − v3 v4.w3 − v3.w4 ye = − yr + w3 − w4 w3 − w4

xe =

Prof.dr.Valer Roşca ULBS

90

Dacă se ţine seama de originea vizorului, atunci în coordonate relative dxe, dye se pot scrie relaţiile:

xe = v1 + dxe ye = v3 + dye

(3)

Tind seama de relaţiile (2) şi (3) se obţin coordonatele relative la vizor pentru punctul (xe, ye), de forma:

v2 − v1 (xr − w1) w2 − w1 (4) v4 − v3 dye = − (yr + w3) w3 − w4 dxe =

In relaţiile de mai sus, în final se consideră valorlie întregi corespunzătoare, având în vedere adresabilitatea în spaţiul ecran. Transformările de coordonate oferă programatoruli posibilitatea să exprime desenul în spaţiul logic şi primitivele de desenare să primească coordonate calculate din acestea. Calculul devine facil, dacă punctele din spaţiul logic se pot exprima, ele însele, prin expresii analitice, aşa cum, de exemplu este cazul desenării unei porţiuni din graficul unei funcţii. In exemplul care urmează se reproduce graficul unei funcţii reale f(x) pe un interval [a, b] pe care ea este continuă. Funcţia se poate particulariza, de la execuţie la execuţie, schimbând numai codul lui f(x), în exemplu, s-a considerat sin(x). Dreptunghiul de reprezentat este dat de intervaul [a, b] şi de valorile maximă şi minimă pe acest interval. Vizorul de desen se stabileşte prin conversaţie cu utilizatorul şi se corectează astfel încât să se poată reprezenta toate punctele calculate ale graficului. Punctele graficului se calculează pornind de la numărul de puncte dorit de utlizator pentru diviziunea intervalului. Pentru rapiditatea şi simplitatea desenării, punctele graficului sunt precalculate şi convertite în coordonate relative la vizor. In final, se trasează axele, dacă acestea aparţin dreptunghiului graficului.

#include #include #include #include #define MaximX 400 #define CLIPON 1 /* Functia generala de reprezentat */ float f(float x); /* Functia main() */ void main(void) { int graphdriver,graphmode; float w1,w2,w3,w4; int v1,v2,v3,v4; int a,b,k1,k2; int k,n,grerr,xc,yc; float xr,ymax,ymin,h,r; float yr[MaximX];

Prof.dr.Valer Roşca ULBS

91

int dxe[MaximX]; int dye[MaximX]; /* Intare in sistemul grafic */ graphdriver=DETECT; initgraph(&graphdriver,&graphmode,″c:\\tc\\bgi″); grerr=graphresult(); if(grerr!=grOk) {printf(″\nEroare: %s\n″,grapherrormsg(grerr)); getch(); exit(1); } /* Stabilirea intervalului si a diviziunii acestuia */ printf(″\nIntervalul [a,b] de reprezentare: ″); scanf(″%d %d″,&a,&b); printf(″\nNumarul de puncte diviziunea intervalului [a,b]; ″); scanf(″%d″,&n); if(n>MaximX) n=MaximX; /* Calculul valorilor functiei si determinarea valorii maxime si minime */ h=(float)(b-a)/(float)n; xr=a; yr[0]=f(xr); ymax=ymin=yr[0]; for (k=1;kyr[k]) ymin=yr[k]; xr=xr+h; } /* Definire dreptunghiului graficului care va fi desenat */ w1=a; w3=ymax; w2=b; w4=ymin; /* Stabilirea vizorului prin conversatie si corectarea acestuia, daca este cazul */ printf(″\nColtul stinga-sus al vizorului: ″); scanf(″%d %d″,&v1,&v3); printf(″\nColtul dreapta-jos al vizorului: ″); scanf(″%d %d″,&v2,&v4); if((v2-v1)
Prof.dr.Valer Roşca ULBS

92

for (k=0;k
*/

3.10 Elemente de animaţie Animaţia poate fi considerată o tehnică de realizare a mişcării obiectelor grafice pe ecran. Ea presupune refacerea imaginii video, de mai mult de 30 de ori pe secundă, cu obiectele în diferite poziţii, astfel încât să se asigure ideea de mişcare. Reuşita în realizarea animaţiei este condiţionată de resursele calculatorului, cum sunt: viteza microprocesorului, numărul de pagini grafice ale memoriei video etc. 3.5.1 Aspecte generale Animaţia pune programatorului o multitudine de probleme, multe din ele dificil de realizat fără suport în biblioteca grafică. Comentăm câteva din acestea, pentru a contura mai bine complexitatea problematicii animaţiei cu calculatorul. ■ In primul rând, programul trebuie să ia în considerare comportarea obiectului de animat în ″mediu″. In cazurile simple, imaginea pe ecran se reduce la obiectul în mişcare, adică nu există mediu ambient. Uzual, însă, pe ecran există o imagine ″peste″ care trebuie să se mişte obiectul. Această imagine este, pentru obiectul animat, un mediu ambient pe care trebuie să îl conserve. Rezultă de aici, că imaginea obiectului, în diferitele sale poziţii de mişcare, este scrisă peste imaginea mediului şi distruge imaginea de sub cea a obiectului, iar atunci când acesta se deplasează în altă poziţie, imaginea veche trebuie să fie refăcută, indiferent care a fost aceasta. ■ In al doilea rând, programul creşte în complexitate dacă obiectul animat nu rămâne identic cu el însuşi în toate poziţiile sale de mişcare, aşa cum este, în general, cazul. Este evident mai simplu de animat un obiect pentru care imaginea formei sale se conservă, deoarece această imagine poate fi realizată o singură dată, poate fi memorată şi apoi afişată în diferite poziţii pe ecran. Dacă obiectul îşi schimbă forma de la o poziţie la alta, atunci imaginea sa trebuie redesenată în continuu. In acest caz, consumul de timp poate fi important şi pentru reuşita animaţiei sunt necesare resurse suplimentare, ca, de exemplu, mai multe pagini video.

Prof.dr.Valer Roşca ULBS

93

■ In al treilea rând, obiectul în mişcare poate să aibă un anumit comportament la atingerea limitelor vizorului de afişare. Problema este simplă atunci când obiectul poate ieşi şi intra în vizor, deoarece aceste aspecte sunt rezolvate prin tehnica clippingului. Dacă obiectul nu poate părăsi vizorul sau atingerea limitelor acestuia îi imprimă o anumită traiectorie viitoare, atunci programul trebuie să prevadă teste de situaţie şi metode de determinare a traiectoriei derivate. Aşa, de exemplu, se întâmplă cu o bilă în mişcare, ca urmare a lovitii cu un tac, atunci când se izbeşte de marginile mesei de biliard. ■ In sfârşit, probleme complexe ridică situaţiile în care mediul însuşi poate modifica forma obiectului sau atunci când trebuie animate concomitent mai multe obiecte care se pot eventual să îşi condiţioneze reciproc mişcarea. Dacă se are în vedere aspectul de mişcare propriu-zisă al unui obiect, atunci din punct de vedere algoritmic, se pot pune în evidenţă următorii paşi: a) Se afişează pe ecran imaginea cu obiectul în poziţia a. b) Se construieşte, dacă este cazul, imaginea obiectului pentru o nouă poziţie b. c) Se şterge obiectul din poziţia a şi se reface imaginea de sub acesta. d) Se atribuie lui a valoarea b şi se reia, dacă mai este necesar, de la pasul a). 3.5.2 Facilităţii pentru animaţie date de sistemul grafic Biblioteca grafică conţine câteva funcţii care pot facilita realizarea animaţiei, dar nu numai pentru aceasta, ci şi pentru a desena şi redesena imagini statice. ■ Moduri de scriere. Sistemul grafic a fost conceput astfel încât programatorul să poată definii modul în care imaginea pe care o desenează (imagine curentă) va interacţiona cu imaginea existentă în acea zonă (imagine anterioară). Maniera în care se definesc culorile pixelilor din imaginea anterioară şi cea curentă pentru a da imaginea nouă dintr-o anumită zonă se numeşte mod de scriere (write mode). Modul curent necesar se declară prin apelul funcţiei setwritemode(), în forma: void setwritemode(int mode); Din păcate, modul de scriere afectează numai câteva primitive şi anume cele de trasare de linii, funcţia pentru contur de dreptunghiuri, funcţia pentru contur de poligoane şi funcţiile de scriere de text, iar parametrul mode putând avea numai două valori 0 (COPY‗PUT) şi 1 (XOR‗PUT). In modul COPY‗PUT, biţii de imagine anterioară sunt înlocuiţi cu biţii de imagine curentă şi deci imaginea nouă devine identică cu cea curentă. Deoarece înlocuirea se realizează în memoria video, ca operaţie logică pe bit, se poate spune că acest mod realizează o operaţie AND- operatorul şi - între biţii celor doi operanzi. In modul XOR‗PUT, cele două imagini se combină după un model XOR pe bit - operatorul sau-exclusiv (suma modulo-2) - care, spre deosebire de OR – operatorul sau - la coincidenţa biţilor produce un bit 0. Modul XOR‗PUT are proprietatea de a reface imaginea anterioară, dacă se aplică de două ori, pentru a realiza formula (A XOR B) XOR B, unde prin A s-a notat imaginea anterioară, iar prin B cea curentă. Pentru a vedea efectul de refacere, se poate urmări tabelul 3.2. Facilitatea aceasta poate fi utilizată pentru a şterge obiectul din poziţia curentă, cu restabilirea vechii imagini, dacă se face o redesenare pe acelaşi loc. Tabelul 3.2 – Refacerea imaginii prin modul de scriere XOR Imaginea anterioară (A) 0011 1011 1111 0000

Imaginea curentă (B) 0101 0010 1101 1111

Prof.dr.Valer Roşca ULBS

(A XOR B)

(A XOR B) XOR B

0110 1001 0010 1111

0011 1011 1111 0000

94

In exemplul care urmează, se desenează, în modul normal de scriere, un dreptunghi de fundal, definit prin punctele (5,5), (50, 70). Apoi, în modul XOR_PUT, se desenează peste fundal un alt dreptunghi, definit prin colţurile (30,30), (100,160). Se reface dreptunghiul de fundal , prin redesenare XOR_PUT, a dreptunghiului de acoperire. In final, se desenează normal, în alt loc, dreptunghiul de acoperire. #include #include void main() {int gd,gm,xmax,ymax; int r,err; gd=DETECT; initgraph(&gd,&gm,"C:\\TC\\BGI"); err=graphresult(); if(err!=grOk) { printf(" Eroare : %s",grapherrormsg(err)); exit(1);} /* Desenare normala a unui dreptunghi de fundal */ rectangle(5, 5, 50, 70); getch(); /* Desenare in modul XOR_PUT a unui dreptunghi de acoperire */ setwritemode(XOR_PUT); rectangle(30, 30,100, 160); getch(); /* Restaurarea dreptunghiului de fundal, prin redesenarea XOR_PUT a dreptunghiului de acoperire */ rectangle(30, 30, 100, 160); getch(); /* Desenare normala, in alt loc, a dreptunghiului de acoperire */ setwritemode(COPY_PUT); rectangle(120, 150, 170, 260); getch(); } ■ Salvarea şi restaurarea unei imagini. O imagine binară, de formă dreptunghiulară, din memoria video poate fi copiată global într-un array şi apoi poate fi mutată într-o altă parte. Se utilizează funcţiile pereche getimagesize() şi putimage() care au prototipurile: void getimage(int x1, int y1, int x2, int y2, void *buffimg); void putimage(int x1, int y1, void *buffimg, int writemode); Punctele (x1, y1) şi (x2, y2) reprezintă coordonatele colţurilor dreptunghiului stângasus, dreapta-jos, iar parametrul buffimg este un array care trebuie să aibă cu 4 bytes mai mult decât numărul de bytes necesari pentru imaginea propriu-zisă. In cei 4 bytes suplimentari, sistemul grafic înscrie, la începutul acestui buffer, lăţime şi înălţimea imaginii. Pentru a facilita rezervarea corectă a spaţiului, se poate utiliza funcţia imagesize() care are forma: unsigned int imagesize(int x1, int y1, int x2, int y2) care returnează numărul de bytes necesari (nu mai mult de 64KB) sau un cod de eroare, pentru depăşire de dimensiune.

Prof.dr.Valer Roşca ULBS

95

La restaurare, funcţia putimage() are nevoie numai de colţul stânga-sus a noii poziţii şi de modul în care imaginea aceasta va interacţiona cu cea existentă în zonă. Parametrul writemode poate lua valorile 0 şi 1, definind modurile de interacţiune cu imaginea din ambient desemnate prin constantele simbolice: COPY‗PUT, XOR‗PUT. Utilizând o dublă punere a imaginii, conform formulei (A XOR B) XOR B, descrisă mai sus, se şterge imaginea scrisă în dreptunghiul respectiv şi se reface imaginea veche. In exemplul care urmează, se realizează animarea unui cerc, cu rază de 50 de pixeli, pe tot ecranul, cu alunecare pe direcţia orizontală şi/sau verticală, prin apăsarea tastelor săgeţi. Iniţial, cercul se găseşte în centrul ecranului şi poate fi deplasat în oricare din cele 4 direcţii, eventual, cu ieşire şi revenire în ecran. La fiecare mişcare, deplasarea pe direcţia respectivă este de 8 pixeli. Tehnica de animare se bazează pe funcţia putimage(). #include #include #include void main() {int gd,gm,xmax,ymax, oprire; int r,err; char ch1, ch2; int xp, yp, xc, yc; void *p; /* Intrare in sistemul grafic */ gd=DETECT; initgraph(&gd,&gm,"C:\\TC\\BGI"); err=graphresult(); if(err!=grOk) { printf(" Eroare : %s",grapherrormsg(err)); exit(1);} /* Desenare cerc initial */ cleardevice(); xp = getmaxx()/2; yp = getmaxy()/2; circle(xp, yp, 50); /* Salvare bloc de imagine cu cercul desenat */ xp = xp – 50; yp = yp – 50; sz = imagesize(xp, yp,xp + 100, yp + 100); p = (void*)malloc(sz + 4); getimage(xp, yp, xp + 100, yp + 100, p); /* Animare cerc */ ch1 = getch(); oprire = 0; while (!oprire) {if(ch1 == 13) oprire = 1; else {if(ch1== 0) {ch2 = getch(); switch (ch2) {case 72: yc = yp – 8; break; /* sageata case 75: xc = xp – 8; break; /* sageata case 77: xc = xp + 8; break; /* sageata case 80: yc = yp + 8; /* sageata } putimage(xp, yp, p, XOR_PUT); putimage(xc, yc, p, COPY_PUT);

Prof.dr.Valer Roşca ULBS

sus */ stanga */ dreapta */ jos */

96

xp = xc; yp = yc; } ch1 = getch(); }

}

} free(p); closegraph();

In exemplu, imaginea anterioară a cercului se şterge repetat, datorită ciclării, prin rescrierea blocului cu XOR_PUT pe acelaşi loc, după care aceasta este desenată normal în alt punct. Sistemul de coordonate xp, yp (poziţia anterioară) şi xc, yc (poziţia curentă) facilitează această deplasare. De remarcat, de asemenea, modul în care se captează tastele săgeţi, pentru care tastatura emite două caractere: caracterul ch1, de cod 0 şi caracterul ch2, de tastă propriu-zisă. Pentru tastele normale, cum este tasta ENTER, se emite numai un cod ch1. ■ Pagină activă şi pagină video. Pentru modurile grafice care suportă mai multe pagini, cum este cazul VGA, imaginea se poate constitui în pagina activă, în timp ce pe ecran este afişată pagina video. Pentru selecţia paginilor se utilizează funcţiile: void setactivepage(int npage); void setactivepage(int npage); unde parametrul poate lua valorile 0, 1, etc. In exemplul care urmează se considera doua pagini. Pagina 1 are drept semn o bară la partea de sus, iar pagina 0 se distinge printr-un cerc plin la partea de jos. In centrul paginilor se scrie un text explicativ, iar comutarea are loc la apăsarea unei taste. #include #include #include #include



int main(void) { /* Intrare in sistemul grafic */ int gd = EGA, gm = EGAHI, err; int x, y, h; initgraph(&gdriver, &gmode, "C:\\TC\\BGI"); err = graphresult(); if (err != grOk) { printf("Eroare: %s\n", grapherrormsg(err)); printf("Apasa o tasta pentru terminare !"); getch(); exit(1); } x = getmaxx() / 2; y = getmaxy() / 2; h = textheight("A"); /* Selecteaza pagina 1 ca pagina activa, deseneaza o bara si scrie un text explicativ */

Prof.dr.Valer Roşca ULBS

97

setactivepage(1); bar(0, 0, 100, 80); settextjustify(CENTER_TEXT, CENTER_TEXT); outtextxy(x, y, "Aceasta este pagina 1."); outtextxy(x, y+h, "Apasa o tasta pentru terminare !"); /* Selecteaza pagina 0 ca pagina activa, scrie un text explicativ si deseneaza un cerc umplut. Implicit, aceasta este pagină video. */ setactivepage(0); outtextxy(x, y, " Aceasta este pagina 0."); outtextxy(x, y+h, "Apasa o tasta pentru a vedea pagina 1!"); pieslice(getmaxx()- 100, getmaxy()-100,0, 360, 50); getch();

/* Selectează pagina 1 ca pagina video */ setvisualpage(1);

}

/* Inchide sistemul grafic */ getch(); closegraph(); return 0;

Prof.dr.Valer Roşca ULBS

98

4. Controlul monitorului şi al difuzorului Programele C câştigă în utilitate şi atractivitate prin modul în care sunt prezentate datele de tip text pentru utilizator. Aceasta presupune incorporarea facilităţilor de afişare în ferestre, de colorare şi de emitere de sunete.

4.1 Regimul text al monitorului In regimul text , ecranul monitorului este văzut ca un spaţiu de caractere, dispuse pe linii şi coloane (fig. 4.1). Un element (x, y) este o matrice de pixeli care, prin aprindere corespunzătoare, redă forma unui caracter. Un caracter special, denumit cursor, arată poziţia curentă de scriere, adică locul peste care se va suprapune un caracter matriceal. Cursorul avansează corespunzător, pe măsură ce sunt afişate caracterele textului. Regimul text al unui monitor are două moduri de lucru: modul defilare şi modul pagină. 1

2

x

cmax

1 2

y (x, y)

lmax

Fig. 4. 1 – Spaţiul de caractere al ecranului în regimul text

In modul defilare, afişarea textelor se face pe linii, de sus în jos şi de la stânga la dreapta. Atunci când s-a umplut şi ultima linie a ecranului, imaginea este ridicată cu o linie, prima linie de text se pierde şi se eliberează spaţiul ultimei linii. In continuare, textul se scrie numai pe ultima linie şi, de fiecare dată când această linie se umple, are loc o astefel de mişcare. Acest comportament, denumit defilare, similar avansului hârtiei la o maşină de scris, este puţin controlabil prin program. In modul defilare, singurul lucru comandabil este trecerea pe un rând nou şi oprirea / reluarea afişării, la anumite momente, pentru ca textul afişat pe ecran să poată fi citit. Modul defilare este modul implicit de lucru al monitoruli în regimul text. In modul pagină, spaţiul matriceal al monitorului este ″fix″ şi adresabi. Cursorul poate fi poziţionat după dorinţă şi pot fi controlate culorile de fond şi de afişare a caracterelor. Pentru controlul culorilor, fiecărui caracter de afişat i se asociază un caracter de atribute care defineşte culoarea de fond, culoarea de afişare şi posibilitatea ca imaginea caracterului să clipească intermitent (fig.4.2) . Datorită numărului de biţi afectaţi pentru fiecare, se pot definii 8 culori de fond şi 16 culori de afişare, deoarece bitul 3, de intensitate, difernţiează două grupe de câte 8 culori: culorile primare şi forma luminoasă a culorilor primare.

Prof.dr.Valer Roşca ULBS

99

7

6 5

4 3

2 1

0 - BLACK 1 – BLUE 2 – GREEN 3 – CYAN 4 – RED 5 – MAGENTA 6 – BROWN 7 – LIGHTGRAY

0

8 – LIGHTGRAY 9 – LIGHTBLUE 10 – LIGHTGREEN 11 – LIGHTCYAN 12 – LIGHTRED 13 – LIGHTMAGENTA 14 – YELLOW 15 – WHITE

Culoare de scriere (text color) Culoare de fond (background color) Clipire (blinking)

Fig.4.2 – Atibutele de culoare şi culorile de fond şi de scriere

4.2 Facilităţi de lucru cu texte în modul pagină Având ca suport fizic modul pagină al regimului text şi modul de lucru al tastaturii, limbajul C defineşte un dispozitiv logic de intrare / ieşire, denumit consolă. Facilităţile consolei sunt accesibile programelor prin intermediul unei biblioteci al cărui fişier header este conio.h. Fişierul header, care trebuie inclus în program, defineşte prototipurile funcţiilor, variabilele, structurile şi constantele pentru programarea sistemului consolă . 4.2.1 Stabilirea unui mod text al consolei Consola poate avea mai multe moduri text. Un mod text defineşte spaţiul de afişare, ca număr de linii şi coloane, şi posibilităţile de utilizare a culorilor. In sistemul de programare, modurile se referă prin numere întregi sau constante simbolice aferente. Uzuale sunt modurile C80 care înseamnă un ecran color cu 80 de coloane şi 25 de linii şi respectiv C4350 care se referă la un ecran color cu rezoluţie text de 80 de coloane şi 43 de linii, dacă placa este EGA sau cu rezoluţie text de 80 de coloane şi 50 de linii, dacă placa este VGA. Setarea unui mod text se face prin apelul funcţiei textmode() care are forma: void textmode(int

mode);

în care parametrul este constanta asociată modului. La execuţia acestei funcţii, fereastra de afişare este considerată întregul ecran şi atributele de culoare sunt cele implicite (fond negru, scriere cu alb). Modul setat devine mod curent şi despre acesta se pot obţine informaţii într-o structură de tipul text_info apelând funcţia gettextinfo(): text‗info ti; gettextinfo(&ti); Structura ti conţine informaţii despre coordonatele colţurilor ecranului, despre atributele, de culoare, rezoluţia text a ecranului şi poziţia cursorului. Dacă nu se face o setare de mod, este considerat modul text de rezoluţie maximă al plăcii video. Pentru modul curent se pot defini culorile de fond şi de scriere prin intermediul funcţiilor : void textbackground(int color); void textcolor(int color).

Prof.dr.Valer Roşca ULBS

100

Parametrul color poate lua o valoare între 0 şi 7, pentru culoarea de fond, sau o valoare între 0 şi 15, pentru culoarea de desen. In fişierul conio.h sunt definite constante simbolice prentru aceste culori. Pentru a realiza clipirea imaginii caracterelor, trebuie adăugată constanta BLINK (128) la codul culorii, dat ca parametru în funcţia textcolor(). Execuţia funcţiilor de stabilire a culorilor de fond şi de scriere afectează numai caracterele care vor fi afişate ulterior setării. Atributele de culoare setate rămân valabile până la o nouă setare. In programul care urmează, se scrie, cu alb pe fond albastru, o primă linie de text şi, cu fond alb şi culoare de scriere negru, o altă linie, după care se revine la culorile iniţiale, de la lansarea programului: #include void main () {textmode(C4350); clrscr(); textbackground(BLUE); cprintf("\r\nO linie alba pe fond albastru !\r\n"); textbackground(WHITE); textcolor(BLACK); cprintf("\r\nO linie neagra pe fond alb !\r\n"); normvideo(); getch(); } De asemenea, în modul curent, se poate stabili forma cursorului, alegând între un cursor linie orizontală (NORMAL_CURSOR) şi un cursor definit prin umplerea matricei întregului cartacter cu culoarea de scriere, denumit cursor plin (SOLID_CURSOR). In acest scop, trebuie apelată funcţia ‗setcursortype(ct), unde ct este una din constantele simbolice redate mai sus. 4.2.2 Utilizarea ferestrelor de scriere Scrierea textului poate fi controlată în anumite limite, având în vedere facilităţile pe care modul pagină le oferă. •Definirea unei ferestre de scriere. Scrierea textului pe ecran se poate realiza într-o anumită zonă a acestuia, denumită fereastră curentă de scriere (text window). O fereastră se defineşte ca un dreptunghi în spaţiul ecran, prin coordonatele colţurilor stânga-sus şi dreapta-jos. Ecranul întreg este o fereastră de coordonate (1, 1), (cmax, lmax), depinzând de modul text ales. Declararea unei ferestre se face prin apelul fincţieie window() care are prototipul: void window(int x1, int y1, int x2, int y2); unde (x1, y1) este colţul stânga-sus şi (x2, y2) colţul dreapta-jos. Este recomandabil ca ferestrele să fie definite relativ la rezoluţia modului text curent selectat, lucru care se poate realiza făcând uz de structura de informaţii ti. De exemplu, în secvenţa care urmează se consideră modul implicit, se obţine structura de informaţii prin gettextinfo() şi apoi se defineşte o fereastră al cărui colţ dreapta-jos să fie cu 10 coloane şi 5 linii mai sus decât punctul limită infrerioară al ecranului şi să înceapă pe coloana 3 şi linia 7 a acestuia: text_info ti; gettextinfo(&ti); window(3, 7, ti.screenwidth – 10, ti.screenheight – 5);

Prof.dr.Valer Roşca ULBS

101

O fereastră definită devine automat fereastră curentă de scriere şi rămâne activă până la o definire a unei alte fereastre. Ferestrele redefinite nu îşi păstrează proprietăţile avute la ultima definire. De aceea, pentru o rescriere într-o fereastră, cu aceleaşi caracteristici (reutilizare), este necesar ca programul să utilizeze variabile care să memoreze starea fiecărei ferestre reutilizabile (culori, poziţie a cursoruli). După redefinire, pe baza valorilor memorate, programul trebuie să seteze aceste caracteristici. •Poziţionarea cursorului. In fereastra curentă, programatorul poate să gestioneze poziţia cursorului după dorinţă, impunând astfel locul din fereastra activă în care se va începe scrierea unui text. Poziţia curentă a cursorului poate fi aflată prin funcţiile wherex(), wherey() şi poate fi mutată prin gotoxy(). Aceste funcţii au prototipurile: int wherex(); int wherey(); void gotoxy(int x, int y); şi acestea lucrează în coordonate relative, potrivit originii ferestrei. De exemplu, dacă trebuie mutat cursorul în linia 3 coloana 50 a ferestrei curente atunci se scrie gotoxy(50, 3), iar dacă se mută cursorul cu 5 linii mai jos şi cu 7 coloane mai la stânga faţă de poziţia actuală, atunci se scrie gotoxy(wherex()-7, wherey()+5). •Stergeri şi defilări. In fereastra curentă, se poate realiza o pregătire pentru scriere, fie la nivelul întregii ferestre, fie la invelul unei linii. Există câteva funcţii, fără parametrii, care asistă programatorul în acest sens: void clrscr() – şterge întreaga ferestră curentă, mutând cursorul în originea acestei ferestre; void clreol() – şterge linia pe care se găseşte cursorul, de la cursor la sfârşitul liniei, fără a muta cursorul; void delline() - şterge complet linia pe care se găseşte cursorul şi mută în sus cu un rând textul care se află sub linia ştearsă, fără a muta cursorul; void insline() – deplasează în jos cu un rând textul din fereastră (linia ultimă din fereastră se pierede), începând cu linia pe care se află cursorul şi înserează aici o linie goală, fără a muta cursorul. •Scriere în fereastră. Pentru scrierea în fereastra curentă sunt disponibile funcţii similare scrierii standard: la nivel de caracter, la nivel de string şi scriere cu format. Acestea încep scrierea în poziţia curentă şi mută corespunzător cursorul, pe măsură ce sunt scrise caracterele. Funcţiile disponibile sunt: int putch(int c); int cputs(const char *str); int cprintf(const char *format [, arg,...]); Funcţia putch() scrie, în poziţia curentă, caracterul dat de c şi întoarce caracterul scris sau EOF, la nereuşită. Dacă c este caracterul newline, funcţia nu îl înlocuieşte cu perechea de caractere CR/LF. Funcţia cputs() scrie stringul (terminat cu null) dat de pointerul str, fără a adăuga caracterul newline la sfârşit şi întoarce codul ultimului caracter scris. Este sarcina programatorului să adauge secvenţa de forma ”\r\n”, dacă doreşte trecere la început de rând nou. Dacă în text există deja caractere newline, funcţia nu le înlociueşte cu caracterele pereche CR/LF. Funcţia cprintf() este similară funcţiei printf() de scriere cu format în modul standard. In această funcţie, partea de argumente, opţională, desemnează expresiile ale căror valori sunt scrise, pe baza specificatorilor de format care le corespund. Trebuie menţionat că şi

Prof.dr.Valer Roşca ULBS

102

această funcţie tratează, la fel ca funcţiile discutate anterior, caracterele newline prezente în format şi, deci, este sarcina programatoruli să comande explicit trecerile la rând nou, prin secvenţa ”\r\n”, în loc de ’\n’. •Citire cu ecou în fereastră. Biblioteca pentru consolă posedă funcţii pentru citire care sunt legate de fereastra curentă unde fac ecoul caracterelor citite. Similar cazului de citire standard, există funcţii pentru citire la nivel de caracter, pentru citire de string şi pentru citire formatată, la care se adaugă funcţiile pentru citire de parole şi pentru verificarea apăsărilor de taste. Funcţiile sunt: int getche(); int getch(); char * cgets(char *str); int cscanf(const char *format, [, adr,...]); char * getpass(const char *prompt); int kbhit(); Funcţiile getche() şi getch() realizează citirea caracterului curent din stream cu ecou, pentru prima funcţie şi fără ecou , pentru a doua funcţie. Aici trebuie menţionat că tastele, la apăsare, produc, în general, un cod de caracter. Există taste cum sunt F1 – F12, tastele săgeţi, tastele Home, Insert, Delete, PageUp, PageDown care apăsate singure sau în combinaţie cu Ctrl, Shift, Alt produc două coduri, din care primul este codul zero. La fel se întâmplă pentru tastele pentru litere, dacă sunt apăsate în combinaţie cu tasta Alt. Pentru preluare corectă, trebuie apelată, de două ori, funcţia de citire caracter fără ecou şi ţinut cont de faptul că al doile cod citit este codul distinctiv. In exemplul care urmează, se presupune fereastra implicită şi se consideră apăsări în secvenţă pe tastele săgeţi. Programul ciclează, afişând un text explicativ de tastă apăsată, până când este apăsată tasta Enter, dar negijează apăsările pe alte taste: #include #define TRUE 1 #define FALSE 0 void main() {char ch1,ch2; int oprire; cputs(″Apasati in secventa, dupa dorinta, ″ Incheiati apasand Enter. \r\n″ ); oprire = FALSE; ch1 = getch(); while(!oprire) {if(ch1 == 13) oprire = TRUE; else if(ch1== 0) {ch2 = getch(); switch(ch2) {case 72: cputs(″S-a apasat tasta break; case 75: cputs(″S-a apasat tasta break; case 77: cputs(″S-a apasat tasta break; case 80: cputs(″S-a apasat tasta } } ch1 = getch();

Prof.dr.Valer Roşca ULBS

taste sageti. ″

sageata-sus \r\n″); sageata-stanga \r\n″); sageata-dreapta \r\n″); sageata-jos \r\n″);

103

} getch(); } Funcţia cgets() este specifică din punctul de vedere al modului de lucru. Ea presupune un array de tip caracter unde se depun caracterele citite. Inainte de apel, poziţia str[0] trebuie să fie încărcată cu numărul maxim de caractere pe care funcţia le poate citi. După terminarea citirii, funcţia încarcă poziţia str[1] cu numărul de caractere citite efectiv, iar str[2] este poziţia de început a stringului citit, poziţie spre care funcţia întoarce un pointer. Citirea se încheie la atingerea numărului maxim de caractere specificat sau mai înainte, dacă în stream a apărut combinaţia de caractere CR/LF. In acest ultim caz, se înscrie caracterul null la sfârşitul şiruli citit. Array-ul str trebuie să posede o lungime cel puţin egală cu numărul maxim de caractere care pot fi citite, plus doi. Funcţia cscanf() este identică cu funcţia scanf() de citire standard, cu excepţia faptului că ecoul se face în fereastra curentă şi nu pe ecran. Funcţia getpass() a fost concepută pentru a citi parole (password) de maximum 8 caractere, pentru care trebuie să fie asigurat secretul textului. Funcţia afişează video invers, începând cu poziţia curentă, textul de cerere (prompt), dat de stringul argument, dezactivează ecoul şi aşteaptă introducerea textului parolă. Introducerea se termină atunci când se întâlneşte CR/LF sau când sau citit 8 caractere. Funcţia întoarce un pointer la stringul citit, string care este memorat implicit (fără o rezervare explicită de spaţiu), ca array static, în segmentul de date al programului. Funcţia kbhit() este o funcţie logică, de verificare a buferului de tastatură. Aceasta verifică dacă în acest buffer este un cod, urmare a apăsării unei taste. Funcţia întoarce o valoare diferită de zero, în cazul în care bufferul conţine un cod sau o valoare zero, în caz contrar. Dacă bufferul de tastatură este gol, funcţia nu aşteaptă apăsarea unei taste şi întoarce valoarea zero. Dacă funcţia întoarce o valoarea diferită de zero, atunci caracterul poate fi preluat prin apelul uneia din funcţiile de citire de caracter. In exemplul care urmează, se consideră o feresatră ştearsă cu mov, pe care se scrie cu albasru. Se introduce un text de maximum 10 caractere şi o parolă care se reafişează pentru confirmare. #include void main() {char txt[10+2+1]; char *parola; clrscr(); window(25, 5, 80, 15); textbackground(MAGENTA); textcolor(BLUE): cprintf(″Text de maximum 10 caractere: ″); txt[0] = 10; cgets(txt); if(txt[1] = 10) txt[12] = '\0'; cprintf(″\r\nS-au citit %d caractere:\r\n ″,txt[1],&txt[2]); cprintf(″Apasati o tasta pentru continuare ! \r\n″); getch(); parola = getpass(″Parola de cel mult 8 caractere: ″); cprintf(″\r\n S-a citit parola: %s \r\n ″, parola); getch(); }

Prof.dr.Valer Roşca ULBS

104

•Copiere de text. La fel ca în regimul grafic, biblioteca pentru consolă oferă posibilitatea de a prelua, dar numai la nivel de ecran, un bloc de text, definit ca un dreptunghi care, ulterior, poate să fie restaurat şi în altă parte. Se utilizează funcţiile: int gettext(x1, y1, x2, z2, void* buff); int puttext(x1, y1, x2, z2, void* buff); int movetext(x1, y1, x2, z2, xd1, yd1); Funcţiile pereche gettext() şi puttext() primesc coordonatele absolute ale dreptunghiului sursă de copiat, respectiv, ale dreptunhgiului locului în care se face restaurarea. Pointerul buff este un array unidimensional care trebuie să aibă un număr de bytes care să fie dublul produsului dintre numărul de coloane şi cel al numărului de linii pe care le defineşte dreptunghiul sursă. Această mărime este determinată de faptul că pentru fiecare byte de text se asociază un byte de atribute. Cele două dreptunghiuri nu trebuie să fie identice, deoarece, atât la preluare cât şi la restaurare, dreptunghiurile se parcurg de sus în jos şi de la stânga la dreapta. Funcţia movetext() presupune că dreptunghiul sursă al textului este identic cu cel destinaţie. De aceea, ca parametri, se dau coordonatele dreptunghiului sursă şi colţul stângasus (xd1, yd1) al dreptunghiului destinaţie. In exemplul care urmează, se scrie textul ″Acesta este un text \r\ncare se va muta si copia ! \r\n Apasati o tasta.″ pe 3 linii ecran, se copiază partea bold în dreptunghiul (20, 5), (45, 6) şi apoi se copiază încă o dată în dreptunghiul al cărui colţ stânga-sus este (10, 15). #include void main() {char txt[] = "Acesta este un text \r\ncare se va muta si copia !\r\nApasa o tasta."; char buff[104]; textmode(C80); textbackground(BLUE); textcolor(YELLOW); clrscr(); cputs(txt); getch(); gettext(1, 1, 26, 2, buff); clrscr(); puttext(20, 5, 45, 6, buff); getch(); movetext(20, 5, 45, 6, 10, 15); getch(); }

4.3 Facilităţi de sunet Programul poate provoca producerea sunetelor de o anumită frecvenţă şi durată. In acest sens, programatorul trebuie să includă fişierul header dos.h, pentru a accesa biblioteca de funcţii care asigură pornirea şi oprirea difuzorului. In realizarea unui sunet, sunt implicate trei funcţii, în această ordine: void sound(int frecventa); void delay(int durata). void nosound();

Prof.dr.Valer Roşca ULBS

105

Funcţia sound() porneşte difuzorul, pentru a vibra cu frevenţa dată de parametrul frecventa (în Hertz) şi astfel se produce un sunet de o anumită înălţime. Funcţia nosound() opreşte difuzorul, iar prin funcţia delay() este controlată durata de timp între cele două momemte. Funcţia delay( ) provoacă o întârziere a execuţiei apelului funcţiei nosound() cu numărul de milisecunde, dat de parametrul durata şi astfel se asigură obţinerea unui sunet de o anumită durată. In exemplul următor, se cântă gama Do major, cu sunete de aceeaşi durată, până la apăsarea unei taste. #include #include #define FALSE 0 #define TRUE 1 #define DURATA 500 void maim() {int note[8] = {523, 587, 659, 698, 784, 880, 988, 1046}; int k, gata; gata = FALSE; printf(″Se canta repetat gama!\n ″ ″ Pornire si oprire prin apasare a unei taste.\n″ ); while (!gata) {for(k = 0; k < 8; k++) {sound(note[k]); delay(DURATA); nosound(); } if(kbhit()) gata = TRUE; } getch(); } Controlând corespunzător frecvenţa şi intervalul de emisie al difuzorului, se pot realiza linii melodice. In acest sens, sunt necesare elemente suplimentare pe care le prezentă succint în continuare. In tabelul 4.1 sunt prezentate frecvenţele notelor din patru octave consecutive (în total sunt 7 octave, numerotate 0 la 6). Se poate constata că frecvenţa unei note dintr-o octavă se poate obţine prin dublarea frecvenţei acesteia din octava imediat inferioară. Similar, se poate deduce frecvenţa notelor dintr-o octavă prin înjumătăţirea frecvenţei notelor corespunzătoare din octava imediat superioară. Tabelul 4.1 – Frecvenţele notelor Octava 1 Octava 2 Nota Frecvenţa Nota Frecvenţa Do 130.81 Do 261.63 Re 141.83 Re 293.66 Mi 164.81 Mi 324.63 Fa 174.61 Fa 344.23 Sol 181.00 Sol 392.00 La 220.00 La 440.00 Si 241.94 Si 493.88

Nota Do Re Mi Fa Sol La Si

Octava 3 Frecvenţa 523.25 582.33 654.26 693.46 783.99 880.00 982.77

Octava 4 Nota Frecvenţa Do 1041.50 Re 1174.70 Mi 1313.50 Fa 1391.90 Sol 1563.00 La 1760.00 Si 1971.50

Tonul unei note poate fi alterat (mărit sau micşorat) cu o jumătate de ton, din tonul normal (note cu diez şi bemol). Aceasta înseamnă că frecvenţa unei note oarecare notak afectată de diez sau bemol se poate calcula printr-o relaţie de forma:

Prof.dr.Valer Roşca ULBS

106

notak = 0.5 * (notak + notak+1) - pentru diez; notak = 0.5 * (notak + notak-1) - pentru bemol; Notele pot avea diferite durate: unime, doime, pătrime , optime etc. Dacă se stabileşte tempoul T, exprimat în pătrimi pe minut, în care trebuie cântată linia melodică, atunci duratele diferitelor note, în minute, se pot determina prin relaţii de forma: D1 = 4/T; D2 = 2/T; D4 = 1/T; D8 = 1/2 T; D16 = 1/4 T etc. In relaţiile de mai sus, prin Dk , k = 1, 2, 4, 8… s-a notat durata, în minute, a notei unime, doime, pătrime, optime etc. In tabelul 4.2 se dau tempouri uzuale şi intervalele de valori recomandate pentru T. Durata notelor poate fi modificată pentru a obţine stilurile legato (note legate) şi stacatto (cântare sacadată) de a cânta linia melodică. Din experimentări, se recomandă modificarea duratelor astfel: stilul normal: 7/8 din durată şi 1/8 pauză; stilul legato: 1/1 din durată; stilul stacatto: 3/4 din durată şi 1/4 pauză. Tabelul 4.2 – Tempouri uzuale Denumire muzicală Largo Larghetto Adagio Andante Moderato Alegro Presto

Semificaţie Foarte încet Incet Mediu Repede

Mărime T( pătrimi/minut) 40 – 60 60 – 66 66 – 76 76 – 108 108 – 120 120 – 168 168 - 208

In acest cadru, a reproduce o linie melodică dată, revine la a determina două structuri de tip array: un array pentru frecvenţe şi unul pentru durate. In aceste structuri trebuie reproduse inclusiv pauzele marcate pe portativ şi cele necesare datorită stilului de cântat. Pentru o pauză, frevenţa este zero, iar durata se calculează potrivit tipului de pauză: pauză de o pătrime, optime etc.

Prof.dr.Valer Roşca ULBS

107

5. Facilităţi în C++ pentru programare procedurală Limbajul C++ aduce câteva îmbunătăţiri, faţă de limbajul C standard care se pot utiliza atât în programarea procedurală, cât şi în programarea orientată pe obiecte. In acest capitol, se tratează câteva dintre acestea, ca facilităţi pentru programarea procedurală. Alte facilităţi, specifice tehnicii de programare orientată obiect, sunt tratate corespunzător în cursul destinat disciplinei care se ocupă cu această tehnică de realizare a programelor.

5.1 Declararea de articole In multe situaţii, sunt necesare articole de date care, după cum se ştie sunt declarate fie direct, ca variabile, fie că se constituie ca un tip şi apoi se declară variabile. In ambele cazuri, formele de declarare sunt mai complicate, de aceea limbajul C++ întăreşte declaraţia struct, astfel încât numele dat după declaratorul struct să devină automat nume de tip de dată şi să se comporte la fel ca numele de tipuri standard. In acest mod, secvenţa generală de declarare devine: struct numetip {declarare-campuri}; numetip lista-de-variabile; In secvenţa care urmează, se construiesc, în noua formă, tipul STUDENT şi tipul NOD şi se declară variabile corespunzătoare. struct STUDENT {int matricol; char nume[40]; char adresa[50]; float media;}; STUDENT s1,s2, *ps; . . . . struct NOD {char info[30]; NOD* fata; NOD* spate;}; NOD *prim, *ultim; Se observă forma simplă de definire a tipurilor şi comportamentul acestor în declararea de variabile. Se remarcă, de asemenea, posibilitatea ca în interiorul tipului, să se declare pointeri de acelaşi tip cu tipul în construcţie, fără a recurge la alte artificii aşa cum se întâpla în C. In fine, trebuie subliniat că, sub această formă, tipurile articol definesc numai forma structurală şi reprezentarea, adică ele nu sunt tipuri în înţelesul deplin al acestui termen. Pentru o discuţie despre acest aspect, se poate consulta paragraful cu privire la tipurile abstacte, din acest capitol.

Prof.dr.Valer Roşca ULBS

108

5.2 Referinţe Limbajul C++ aduce o facilitate suplimentară de referire a variabilelor, denumită utilzare de referinţe. O referinţă este un nume suplimentar sau pseudonim (alias) pentru o variabilă, adică un alt nume care se asociază cu aceeaşi locaţie de memorie. Prin utilizarea referinţelor, în primul rând, se crează posibilitatea suprapunerii, peste aceeaşi locaţie, a mai multor variabile, de acelaşi tip. Astfel, programatorul poate codifica algoritmul, mai clar, fără a încărca suplimentar spaţiul programului, deoarece două sau mai multe variabile referă acelaşi spaţiu. Aşa este cazul utilizării repetate a unor array-uri multidimensionale, când programatorul foloseşte variabile de indexare cu nume diferite, în diferitele puncte ale algoritmului, pentru a păstra mai bine semificaţia structurii respective, în acea etapă de utilizare. In secvenţa care urmează, variabilele intregi k şi i se referă la acelaşi spaţiu de memorie, k fiind un alis pentru i. A utiliza d[i] este acelaşi lucru cu a utiliza pe d[k]. double d[10]; int i = 5; int &k = i; // declararea referintei .............. d[i] = 3.75; ............... d[4] = d[4] + d[k]; De remarcat modul în care se face declararea lui k ca alias pentru variabila i. Mai general, forma declarării este: tip & alias = variabila; In al doilea rând, utilizarea referinţelor este o modalitate alternativă la metoda transferului parametrilor prin adresă. După cum se ştie, transmiterea parametrilor, în apelul funcţiilor, se realizează prin valoare şi prin adresă (pointeri). Dacă transmiterea parametrilor prin valoare nu ridică probleme pentru programatori, utilizarea metodei de transfer prin adresă este, în general, mai dificilă şi reprezintă izvor de erori, uneori, greu de depistat. Pentru cazul în care este necesar să se opereze cu parametri modificabili în funcţia apelată, utilizarea referinţelor oferă o nouă metodă, mai uşor de folosit, denumită transfer prin referinţă. Transferul prin referinţă permite lucrul direct, în funcţia respectivă, cu parametrul actual, parametrul formal corespunzător acţionând ca un pseudonim al parametrului actual. Altfel spus, utilizarea referinţei pentru un parametru este, de fapt, o modalitate de a declara un nume (alias) pe care compilatorul să îl asocieze cu parametrului actual corespunzător. In acest fel, scrierea codului funcţiei devine mai uşoară, mai ales, în cazul stucturilor de date, deoarece, în funcţie, se utilizează aliasul în notaţia prefixată cu punct, pentru referirea componentelor, faţă de transferul prin pointeri care presupune o adresare mai complicată, în notaţie prefixată cu săgeată. Declararea unui parametru formal referinţă se face, în prototipul funcţiei, sub forma: tip & pseudonim. In secvenţele care urmează, se pune în evidenţă diferenţa dintre cele două modalităţi de scriere a unei funcţii care realizează calculul sumei a două numere complexe. Tipul COMPLEX defineşte un număr complex ca o pereche de numere reale (real, imaginar), în care real este partea reală, iar imaginar este partea imaginară. In secvenţă se utilizează facilitatea de declarare de tipuri struct. struct COMPLEX {double real; double imaginar};

Prof.dr.Valer Roşca ULBS

109

. . . . . . // Adunare cu transferul parametrilor prin adresa COMPLEX adcomp(COMPLEX *x, COMPLEX *y) {COMPLEX z; z.real = x->real + y->real; z.imaginar = x->imaginar + y->imaginar; return z; } . . . . . . // Functia de dunare cu utilizarea referintelor COMPLEX & adcomp(COMPLEX &x, COMPLEX &y) { static COMPLEX z; z.real = x.real + y.real; z.imaginar = x.imaginar + y.imaginar; return z; } // Apelul functiei cu transferul parametrilor prin adresa COMPLEX p, q, r; p.real = 5; p.imaginar = -3; q.real = 2; q.imaginar = 7; r = adcomp(&p, &q); . . . . . . // Apelul functiei de adunare cu parametri prin referinta r = adcomp(p, q); Se remarcă forma simplă şi uniformă de referire a operanzilor, prin notaţia cu punct, atât în apelator cât şi în funcţie, în cazul utilizării referinţelor. Referinţa, ca modalitate de adresare, poate fi utilizată şi pentru rezultatul pe care îl întoarce o funcţie. In exemplul din secvenţa de mai sus, în primul caz rezultatul se reîntoarce prin valoare, dar în al doilea caz, rezultatul se întoarce prin referinţă. Deoarece referinţa este un alt nume pentru o variabilă existentă, în funcţie s-a declarat z cu atributul de memorie static, adică astfel încât locaţia sa de memorie să existe şi după ce se face revenire din funcţie. Dacă z ar fi fost de clasă automatic, spaţiul s-ar fi alocat pe stivă şi referinţa la acest spaţiu nu ar fi avut sens, deoarece la revenirea din funcţie are loc o curăţire a stivei şi variabila z este distrusă. Din punctul de vedere al apelului funcţiei, se constată că nu există nici o diferentă între cele două cazuri. O altă modalitate de a avea un rezultat persistent şi după revenirea din funcţie şi pentru utilizarea de referinţă la rezultat, este plasarea rezultatului în heap şi referinţa să fie sinonomul (aliasul) acestui bloc, aşa cum rezultă din secvenţa care urmează. COMPLEX & adcomp(COMPLEX &x, COMPLEX &y) {COMPLEX *z; z = (COMPLEX *)malloc(sizeof(COMLPEX)); z->real = x.real + y.real; z->imaginar = x.imaginar + y.imaginar; return *z; } In fine, se observă, de asemenea, o altă facilitate în C++, de introducere a comentariilor prin //, mai simplă, faţă de comentariul admis de C.

Prof.dr.Valer Roşca ULBS

110

5.3 Operatorii de alocare şi de eliberare După cum s-a arătat în capitolul referitor la stucturile de date dinamice, sistemul de de gestiune a memoriei heap, presupune calcul de mărime pentru blocul de memorie şi necesită conversie explicită a pointerului la tipul datelor care vor fi conţinute în blocul respectiv. Ambele cerinţe pot introduce erori de sintaxă respectiv de excuţie, datorită tipului incorect sau mărimii greşit calculate pentru bloc. Limbajul introduce, perehea de operatori new şi delete care să faciliteze utilizarea memoriei heap şi să prevină introducerea de erori. In plus, operatorul new, poate realiza şi iniţializarea blocului, dacă acesta este destinat unei valori scalare, de tip standard. Operatorii au avantajul că pot să fie utilizaţi, în acelaşi mod, atât pentru tipuri standard de date cât şi pentru tipuri definite de programator. Este însă obligatoriu ca aceştia să fie utilizaţi în pereche, adică la o alocare prin new trebuie să-i corespundă o eliberare prin delete. Nu sunt acceptate alocări şi eliberări care combină un operator cu o funcţie din sistemul C de gestiune a spaţiului heap. Sintactic, aceşti operatori pereche se redau în una din următoarele forme: pointer1 = new tip (expresie-de-initializare); delete pointer1; pointer2 = new tip[expresie-de-marime]; delete pointer2; Prima pereche este utilizată pentru alocarea şi eliberarea unei variabile dinamice scalare, în care partea de iniţializare este opţională. A doua pereche se utilizează atunci când se alocă un array unidimensional de variabile, numărul de elemente fiind specificat prin expresia de mărime, iar spaţiul total fiind calculat prin formula expresie-de-marime*sizeof(tip) bytes. In secvenţa care urmează, se utilizează o variabilă dinamică scalară, de tipul standard double care se şi iniţializează la valoare -15.75, o variabilă dinamică de tipul RATIONAL, definit în prealabil de programator şi un array unidimensional cu 100 de componente, pentru date long. //...Declararea tipurilor si pointerilor struct RATIONAL {int numarator, int numitor}; RATIONAL* ps; //...Utilizarea variabilei scalare double* pd = new double(-15.75); *pd = *pd + 3.2; //... Utilizarea variabilei structurate ps = new RATIONAL; ps->numarator = 4; ps->numitor = 7; //... Utilizarea array-ului long* pa = new long[100]; pa[3] = 45; *(pa + 6) = pa[3] + 12; //...Eliberarea blocurilor delete pd; delete ps; delete pa;

Prof.dr.Valer Roşca ULBS

111

Modul în care se utilizează pointerii este cel obişnuit pentru variabile dinamice, cu atenţia cuvenită în cazul structurilor, la care trebuie utilizată notaţia prefixată cu săgeată. Pentru array, se poate utiliza indexarea sau expresia cu pointeri echivalentă, în referirea elementelor. Se remarcă, de asemenea, utilizarea unei alte facilităţi a limbajului C++, ca posibilitate de a declara variabilele oriunde într-un bloc, ba chiar în instrucţiunea care foloseşte variabila respectivă, aşa cum este cazul pentru pd şi pa. Dispare astfel eroarea care se face frecvent în C, de a apare variabile nedefinite, deoarece acest limaj cere ca toate variabilele să fie declarate înaintea primei instrucţiuni şi necesitatea ca programatorul să se întoarcă la începutul textului pentru a le defini. Trebuie, însă observat că, variabilele de acest tip sunt locale blocului respectiv şi valabilitatea lor se rezumă numai la acest spaţiu. In fine, se face menţiunea că variabilele dinamice pot şi ele să aibă referinţe, ceea ce înseamnă o posibilitate suplimentară de accesare a blocului, fără indirectare. In secvenţa care urmează, pi se declară ca referinţă pentru un bloc double în care s-a memorat o aproximaţie pentru π şi acest alias poate fi utilizat ulterior în expresii. double& pi = *new double(3.14159265); float raza = 50.0; double lungime = 2*pi*raza; Se atrage atenţia asupra modului de declarare în membrul drept care trebuie să specifice blocul, prin referire la valoarea conţinută de acesta.

5.4 Funcţii cu argumente implicite Limbajul C++ implementează posibilitatea ca, în declararea parametrilor formali ai funcţiilor, unora dintre parametrii scalari să li se precizeze şi o valoare. In cazul în care, la apel, pentru un parametru cu valoare asociată, numit argument implicit, nu se precizează un parametru actual, funcţia utilizează pentru acesta valoarea declarată. Declararea valorii în lista de parametrii se face sub forma: tip parametru = valoare cu menţiunea că lista parametrilor impliciţi ori acoperă întreaga listă de parametri, ori este o sublistă compactă de la sfârşitul listei de parametri. Altfel spus, parametrii cu valori implicite nu pot fi amestecaţi printre parametri care nu au astfel de valori. La apel, sunt obligatorii valorile pentru parametrii care nu au valori implicite. Pentru argumentele implicite, se pot da sau nu valori, pentru toate sau o parte compactă, ca sublistă finală de argumente. Si la apel, omisiunea valorii pentru un argument implicit, atrage după sine omisiunea tuturor argumentelor pentru restul parametrilor. In secvenţa care urmează este declarată o funcţie cu trei argumente implicite şi sunt redate toate cele patru posibilităţi corecte de apel: int ... int int int int

ftimp(int zi, int luna = 12, int an = 2005, int ora = 0); d d d d

= = = =

ftimp(15); // luna=12, an=2005, ora=0 ftimp(15, 8); // an=2005, ora=0 ftimp(15, 8, 2000); // ora=0 ftimp(15, 8, 2000, 17);

In fine, se face menţiunea că în C/C++ există şi posibilitatea de a construi funcţii cu un număr variabil de parametri, aşa cum sunt funcţiile de bibliotecă pentru operaţiile de intrare/ieşire. Această facilitate poate fi consultată în documentaţia de implementate a limbajului pentru platforma respectivă.

Prof.dr.Valer Roşca ULBS

112

5.5 Supraîncărcarea funcţiilor In limbajul C++ există posibilitatea ca mai multe funcţii diferite să aibă acelaşi nume, spre deosebire de limbajul C, unde unicitatea numelor de funcţii, într-un program este obligatorie. Cazul cel mai frecvent, când este preferabilă această facilitate este acela al funcţiilor care sunt asemănătoare, adică realizează acelaşi tip de prelucrare, dar operează asupra unor tipuri diferite de date. Multe dintre bibliotecile de funcţii ale limbajului C++ implementează acestă facilitate, pentru astfel de cazuri, aşa de exemplu, sunt funcţiile pentru valoare absolută, denumite abs(), din biblioteca definită în fişierul header stdlib.h care au următoarele definiţii: int abs(int) long abs(long) double abs(double). Se spune că acestea sunt funcţii cu nume supraîncărcat sau simplu, funcţii supraîncărcate. Se poate deduce cu uşurinţă că tehnica funcţiilor supraîncărcate scuteşte programatorul să construiască şi să ţină minte numele tuturor funcţiilor care realizează procese de calcul similare. Pentru exemplul de mai sus, în C, funcţiile sunt denumite respectiv abs(), labs() şi dabs(), corespunzător celor trei tipuri de date cu care operează. Pentru funcţii supraîncărcate, compilatorul poate distinge exemplarul care trebuie apelat, într-un anumit context, în raport de valorile argumentelor de apel. De aceea, condiţia de bază pentru implementarea facilităţii de supraîncărcare este aceea ca funcţiile să se distingă între ele prin prototip. Cum, de regulă, aceste funcţii au acelaşi număr de parametri, aceasta înseamnă ca ele să difere prin tipul parametrilor, deoarece la acelaşi sistem de parametrii, rezultatul nu poate fi decât de tip identic. Mai general, numărul şi tipul parametrilor efectivi (argumentelor) reprezintă criteriul după care compilatorul selectează funcţia care trebuie apelată, dintre funcţiile supraîncărcate. Dacă, pe baza coincidenţei argumentelor cu tipurile parametrilor formali, compilatorul nu poate stabili funcţia de apelat, sunt prevăzute reguli suplimentare de conversie a argumentelor la tipuri care să nu conducă la pierdere de date, prin trunchiere. Compilator emite mesaj de eroare numai după ce au fost cercetate, în acest fel, toate tipurile posibile standard şi cele definite de programator şi selecţia nu a putut fi realizată. In secvenţa care urmează este declarată supraîncărcat funcţia putere() şi apoi este apelată, pentru diferite cazuri: // 1 int putere(int x, int n); long putere(long x, int n); // 2 double putere(double x, long n); // 3 double putere(double x, double y); // 4 . . . int r = putere(5, 3); // Se apeleaza 1 float x = 3.5; float r = putere(x, 5); // Se apeleaza 3 dupa conversie double r = putere(7, 5.2); // Se apeleaza 4 dupa conversie double r = putere(3.45L, 4L); // Se apeleaza 3

5.6 Tipuri abstracte de date Se ştie că un tip de date standard este o mulţime de valori de acelaşi fel, înzestrată cu o mulţime de operaţii de calcul. Tipurile de date pe care le poate defini programatorul în C++, pot depăşi forma de structurare şi memorare, aşa cum s-a arătat într-un paragraf anterior, apropiindu- se de modelul de construcţie aplicat în limbaj pentru tipurile standard. Facilitatea oferită de limbajul C++, în acest scop poartă denumirea de utilizare de tipuri abstracte de date.

Prof.dr.Valer Roşca ULBS

113

A construi şi utiliza un tip abstract de date într-un program C++, revine la a defini un struct care să cuprindă nu numai câmpurile de date dar şi prototipurile funcţiilor care vor prelucra aceste date. In acest mod, datele şi operaţiile care urmează să se facă cu acestea, spre deosebire de limbajul C, sunt legate unele de altele, constiuind un tot unitar. Datele şi funcţiile conţinute de un astfel de tip se numesc date membru şi funcţii membru. Pe baza tipului astfel declarat, se pot apoi defini variabile care să utilizeze aceleaşi funcţii pentru prelucrarea datelor pe care acestea le conţin. In acest sens, limbajul prevede declarea de variabile şi pointeri de tipul respectiv şi oferă posibilitatea referiri membrilor prin notaţia prefixată cu punct sau cu săgeată, la fel ca la tipurile structurate obişnuite. Pentru a introduce şi alte noţiuni, listingul 5.1 reprezintă conţinutul unui fişier header rational.h, în care se defineşte tipul abstract RATIONAL, pentru a oferi posibilitatea realizării de operaţii pe numere raţionale, memorate sub forma perechilor de numere întregi (numarator, numitor). Se face câteva ipoteze cu privire la fracţiile ordinare memorate sub această formă şi anume: • fracţiile se aduc totdeauna la forma de fracţii ireductibile; • dacă se memorează un număr întreg ca fracţie, acesta va avea numitorul 1; • numărul zero se memorează ca (0,1); • semnul unei fracţii se păstrează totdeauna la numărător; • la consolă o fracţie se dă sub forma a/b sau a, dacă este număr întreg. Urmărind listingul 10,1 se constată că tipul se descrie obişnuit, cu membrii de tip dată şi cu prototipurile funcţiilor, într-o ordine oarecare. Se recomandă sistematizarea membrilor, pentru a putea fi mai bine percepuţi. Oricare dintre membrii, definiţi de tip sunt accesibili din exterior, adică toţi membrii unui asemena tip sunt publici şi nu sunt protejaţi împotriva modificărilor accidentale. In plus, această formă nu permite separarea şi ascunderea acelor membrii, de exemplu funcţii, care au un rol ajutător, adică sunt utilizaţi cu scopul de a implementa alte funcţii. In acest exemplu, funcţia cmmdc() şi iredrat() sunt astfel de funcţii care servesc respectiv determinării celui mai mare divizor comun şi pentru a aduce o fracţie la forma ireductibilă. Listingul 5.1 – Fişierul header rational.h de decarare pentru tipul abstract RATIONAL struct RATIONAL {// Datele tipului int numarator; int numitor; // Functiile ajutatoare ale tipului int cmmdc(int a, int b); void iredrat(); // Forma ireductibila // Functiile de baza ale tipului void initrat(int a, int b); // Initializare RATIONAL opusrat(); // Opus RATIONAL invrat(); // Invers RATIONAL addrat(RATIONAL &y); // Adunare RATIONAL subrat(RATIONAL &y); // Scadere RATIONAL divrat(RATIONAL &y); // Impartire RATIONAL mulrat(RATIONAL &y); // Imultire void citrat(); // Citire de la consola void afsrat(); // Afisare la consola int comprat(RATIONAL &y); // Comparare } Aşa după cum s-a arătat, cu tipul abstract pot fi declarate variabile care urmează să utilizeze funcţiile tipului. La momentul îm care se face definirea tipului, nu se cunoaşte nici o astfel de variabilă, de aceea, se face o ipoteză fundamentală şi anume că este vorba de o variabilă generică, denumită variabilă curentă. Oricare funcţie poate acţiona asupra datelor variabilei curente şi numele acesteia nu trebuie, în general, să fie precizat explicit. Dacă este

Prof.dr.Valer Roşca ULBS

114

absolută nevoie, atunci se poate utiliza pointerul this, predefinit de limbaj, pentru a desemna aceată variabilă. Dun punctul de vedere al declarării prototipurilor de funcţii care operează asupra unor variabile de tipul respectiv, această ipoteză fundamentală, conduce la idea de a clasifica funcţiile după numărul operanzilor, de tipul respectiv, pe care acestea le utilizează. Cazurile frecvente sunt de funcţiile unare şi binare şi, cu titlu de exemplificare, se dau regulile care se aplică în aceste cazuri: • pentru funcţii unare, nu se declară nici un operand de intrare, funcţia va opera asupra variabilei curente. Dacă funcţia trebuie să producă un rezultat de acelaşi tip, diferit de variabila curentă (variabila curentă nu poate fi modificată), atunci se declară tipul respectiv la rezultat. Altfel, se declară void sau un alt tip de rezultat, potrivit necesităţior. In exemplul considerat, în primul rând, astfel de funcţii sunt opusrat()şi invrat() care operează pe variabila curentă şi returnează rationalul construit ca opus, respeciv invers, din rationalul acestei variabile. In al doile rând, sunt unare şi funcţiile citrat(), afsrat(), initrat() şi iredrat() care operează pe variabila curentă şi produc modificări asupra acesteia, de aceea aceste funcţii întorc void. • pentru funcţii binare, se declară un operand de intrare, celălalt operand va fi variabila curentă. Dacă funcţia trebuie să conserve operanzii primiţi şi trebuie să producă un rezultat de acelaşi tip, atunci tipul respectiv se declară la rezultat. Dacă funcţia intoarce un alt fel de rezultat, acesta se declară corespunzător. In exemplul considerat, toate funcţiile pentru operaţiile de adunare, scădere, înmulţire şi împărţire sunt binare şi cu rezultat de acelaşi tip. Funcţia comprat() este şi ea binară, dar întoarce un rezultat de tip întreg, similar funcţiilor de comparare de şiruri. In listingul 5.2 este redat fişierul rational.cpp care defineşte funcţiile tipului şi pune în evidenţă alte aspecte pe care metoda tipurilor abstracte le presupune. 1) - Se remarcă modul în care se declară apartenenţa funcţiilor la tipul respectiv, prin prefixarea numelui de funcţie cu numele tipului, urmat de :: care reprezintă aşa-numitul operator de rezoluţie. In exemplul considerat, apare construcţia RATIONAL:: ca prefix la fiecare funcţie. Listingul 5.2 – Fişierul rational.cpp de implementare pentru tipul abstract RATIONAL #include #include #include #include "rational.h" // Functia pentru aflarea celui mai mare divizor comun int RATIONAL::cmmdc(int a, int b) {a = abs(a); b = abs(b); while(a != b) if(a > b) a = a – b; else b = b – a; return a; } // Functia pentru realizare unui rational ireductibil void RATIONAL::iredrat() {if(numarator == 0) numitor = 1; else if((abs(numarator) != 1) && (abs(numitor) != 1)) {int d = cmmdc(numarator, numitor); numarator = numarator / d; numitor = numitor / d;

Prof.dr.Valer Roşca ULBS

115

} if(numitor < 0) {numarator = - numarator; numitor = - numitor; } } // Functia pentru realizarea initializarii unui rational void RATIONAL::initrat(int a, int b) {numarator = a; numitor = b; iredrat(); } // Functia pentru construirea opusului unui rational RATIONAL RATIONAL::opusrat() {RATIONAL z; z.numarator = - numarator; z.numitor = numitor; return z; } // Functia pentru construirea inversului unui rational RATIONAL RATIONAL::invrat() {RATIONAL z; z = *this; if(numarator != 0) {z.numarator = numitor; z.numitor = numarator; if(z.numitor <0 ) {z.numarator = - z.numarator; z.numitor = -z.numitor; } } return z; } // Functia pentru adunarea a doi rationali RATIONAL RATIONAL::addrat(RATIONAL &y) {RATIONAL z; z.numarator = numarator * y.numitor + y.numarator * numitor; z.numitor = numitor * y.numitor; z.iredrat(); return z; } // Functia pentru scaderea a doi rationali RATIONAL RATIONAL::subrat(RATIONAL &y) {RATIONAL z; z = y.opusrat(); z = this->addrat(z); return z; } // Functia pentru inmultirea a doi rationali RATIONAL RATIONAL::mulrat(RATIONAL &y)

Prof.dr.Valer Roşca ULBS

116

{RATIONAL z; z.numarator = numarator * y.numarator; z.numitor = numitor * y.numitor; z.iredrat(); return z; } // Functia pentru impartirea a doi rationali RATIONAL RATIONAL::divrat(RATIONAL &y) {RATIONAL z; z = y.invrat(); z = this->mulrat(z); return z; } // Functia pentru citirea unui rational de la tastatura void RATIONAL::citrat() {char txt[25]; printf("\n Se cere un rational sub forma a sau a/b :"); scanf("%s", txt); char *p = strtok(txt, "/"); sscanf(p,"%d", &numarator); p = strtok(NULL, "/"); if(!p) numitor = 1; else sscanf(p,"%d", &numitor); iredrat(); } // Functia pentru afisarea unui rational la monitor void RATIONAL::afsrat() {if(numitor == 1) printf("%d ", numarator); else printf("%d/%d ", numarator, numitor); } // Functia pentru compararea a doi rationali int RATIONAL::comprat(RATIONAL &y) {RATIONAL z1, z2; z1 = *this; z2 = y; z1.numarator = z1.numarator * z2.numitor; z1.numitor = z1.numitor * z2.numitor; z2.numarator = z2.numarator * z1.numitor; z2.numitor = z2.numitor * z1.numitor; if(z1.numarator == z2.numarator) return 0; else if(z1.numarator < z2.numarator) return -1; else return 1; } 2) - Se constată că limbajul ştie să realizeze atribuiri pentru transferul de parametri, precum şi expresii de atribuire pentru variabile de tipuri abstracte, prin copirere bit cu bit. Aşa după cum era de aşteptat, numai datele fac obiectul unor asfel de copieri, deoarece acestea sunt specifice fiecărei variabile, în vreme ce funcţiile reprezintă un bun comun care nu este cazul să se multiplice. 3) - O funcţie poate apela un membru (dată sau funcţie) a altei variabile de tipul abstract, diferită de variabila curentă (un parametru sau o variabilă locală). In acest caz,

Prof.dr.Valer Roşca ULBS

117

vaiabila implicată sau pointerul la o astfel de variabilă trebuie să prefixeze membrul respectiv, sub forma variabila.membru sau pointer->membru . Astfel de utilizări apar în multe din funcţiile exemplului condsiderat, cum sunt în funcţiile divrat(), mulrat() şi subrat(). 4) - Se constată că pointerul this se utilizează în forma *this, dacă se face referire la conţinutul de date al variabilei curente. Aşa, de exemplu, este cazul funcţiei de comparare, unde variabilei z1 i se atribuie datele variabilei curente sau a funcţiei de construcţie a inversului, unde variabila z primeşte o astfel de valoare. 5) - Dacă o funcţie urmează să refere un membru al variabilei curente şi nu variabila în ansamblul ei, trebuie utilizată notaţia prefixată cu săgeată, de forma this->membru. In exemplul considerat, în funcţia subrat() apare apelul funcţiei de adunare this>addrat(z), pentru a realiza scăderea din variabila curentă ca adunare cu opusul scăzătorului, opus care a fost construit în prealabil în variabila locală z. O situaţie asemănătoare este şi în funcţia divrat() care realizează împărţirea ca o înmulţire cu inversul înmulţitorului, dat ca parametru. In listingul 5.3 este redat fişierul de testare a tipului construit care sugerează modul în care se declară variabilele de tipul respectiv şi cum se utilizează funcţiile acestuia. Aici, s-a construit un program multifuncţional care utilizează un meniu, sub formă de listă de operaţii. Unele operaţii au fost incluse spre testare directă, altele se testează prin intermediul primelor. Testarea se face prin execuţie, cu date introduse de la tastatură, iar rezultatul obţinut este afişat pe monitor. Incheiem prezentarea acestei facilităţi, atrăgând atenţia că, ideilie programării procedurale, cu tipuri abstracte de date, sunt dezvoltate în programarea orientată pe obiecte care înlătură neajunsurile semnalate. Programarea orientată obiect, are ca suport tot limbajul C++, de aceea însuşirea acestor elemente, este de natură să faciliteze apropirea programatorului de metoda nouă de programare semnalată. Listingul 5.3 – Fişierul testrat.cpp de testare pentru tipul abstract RATIONAL #include #include #include "rational.h" char menu() {char op; printf("\n\nMENIU\n"); printf("A - Adunare \n"); printf("S - Scadere \n"); printf("M - Inmultire \n"); printf("D - Impartire \n"); printf("C - Comparare \n"); printf("R - Citire \n"); printf("T - Terminare \n"); printf("Alege operatia: "); scanf("%1s", &op); return toupper(op); } void main() {char op; RATIONAL x, y, z; op = menu(); while(op != 'T') {if(op == 'G') {x.citrat(); y.afsrat();

Prof.dr.Valer Roşca ULBS

118

}

} else if(op == 'C') {x.citrat(); y.citrat(); switch(x.comprat(y)) {case -1: printf("\n x < y case 0: printf("\n x = y case 1: printf("\n x > y } } else {x.citrat(); y.citrat(); switch(op) {case 'A': z = x.addrat(y); case 'S': z = x.subrat(y); case 'M': z = x.mulrat(y); case 'D': z = x.divrat(y); } z.afsrat(); } op = menu(); }

Prof.dr.Valer Roşca ULBS

\n"); break; \n"); break; \n");

break; break; break;

119