Curs21.TIPURI DE DATE1.1. DATE I INFORMAIInpracticsefacedeosebirentreodatioinformaie. Exempleleoferitencelemai multecazuri sunt edificatoare. Existi tendinedeaoferi definiii pentrudatei pentru informaii. Dilemele cnd o informaie este considerat dat i cnd o dat este o informaie, sunt rezolvate pentru muli specialiti, dar rmn dileme pentru o alt categorie de specialiti.Din punct de vedere al programatorului, ceea ce face obiectul prelucrrii sunt de fapt iruri de bii care reprezint date sau informaii, funcie de contextul n care sunt generate i de modul n care se interpreteaz rezultatele. Pentru a nu complica i mai mult problematica, se consider c n activitatea de programare se opereaz cu date. Toate intrrile i ieirile programelor sunt date. Sistemele de prelucrare, nssunt intitulate ncontinuare sisteme informaionalesau sisteme informatice, n mod ornamental din punctul de vedere al programatorilor.nrealitate, atunci cndacesteafuncioneazcorect, prelucreazntr-adevr informaii. Atunci cnd, ns, fluxurile sunt greoaie i determin un nivel de istorism costisitor, prelucrrile sunt ale unor date certe.Pentru ca n literatura de specialitate capitolul deinut descrierii operanzilor informaii sau date se numete STRUCTURI DE DATE, n continuare, nu se mai face deosebirea dintre informaie i dat. Utilizatorii sunt aceia care decide dac ofer spre prelucrare informaii sau date i dac rezultatele prelucrrii sunt date sau sunt informaii.1.2 CLASIFICRI ALE DATELORExist numeroase puncte de vedere de a aborda gruparea datelor, fiecare constituindu-se ntr-un criteriu. Ceea ce este ns adevrat, este legat de faptul c fiecrei date i se ataaz totalitatea atributelor ce rezult din multitudinea de clasificri ce se iau n considerare.a) Criteriul variabilitii grupeaz datele n:- dateconstante, carenusemodificntr-unintervaldetimpsaupedurataexecuiei programului;n cazul n care pentru a face un program lizibil constantele sunt puse n coresponde cu anumii identificatori,n programe sunt vehiculai acetia din urm, formnd constantele simbolice.- date variabile, ale cror niveluri se modific fie ntr-uninterval de timp, fie pe parcursul execuiei unui program; ntotdeauna se vorbete de o valoare iniial, valori intermediare i o valoare final; numrul valorilor intermediare determin mecanismele necesare prelucrrilor, includerea n structuri repetitive sau stocarea lor n fiiere; b) Criteriul compunerii difereniaz datele astfel:- datesimplesauelementare, fiecareavndoanumitsemnificaiei fiindindependentede celelalte date care apar ntr-un context specificat; datele elementare se mai numesc atomi;- datecompusesaustructurate, formatedindateelementaresaudatelarndul lorstructurate; fiecare component are o anumit poziie n cadrul structurii i mpreun cu celelalte formeaz un ntreg; ntre prile care alctuiesc o dat compus exist legturi n primul rnd de coninut i numai toate la un loc caracterizeaz un fenomen, un proces sau un individ dintr-o colectivitate: apartenena i poziia fiecrei componente se precizeaz explicit la descrierea datei structurate;c) Criteriul semnificaiei coninutului conduce la:- datecare fac obiectul operaiilor deprelucrare, adic participcaoperanzi nexpresii, se iniializeazprinatribuirisauoperaii deintrare, sestocheazpesupori, seafieazsause transmit ca parametri;- date care permit adresarea operanzilor i care au valori cuprinse ntre limite precizate, care prin calcule de adrese localizeaz corect fie operanzi, fie alte date de adresare, fie funcii de prelucrare;- date ce efectueaz prelucrarea,care apar ca succesiuni de instruciuni direct executabile dac fiierul careleaparineestencrcat nmemoriaunui calculator i secomandlansarean execuie a acestuia;d) Criteriul naturii datelor genereaz tipurile de date urmtoare:- date de tip ntreg, ale cror elemente aparin mulimii Z;- date de tip real, ale cror elemente aparin mulimii R;- datedetipcomplex, alecrorelementeaparinmulimiiC, iarcoeficieniicaredesemneaz partea real i partea imaginar aparin mulimii R;- date de tip boolean, ale cror elemente aparin mulimii{TRUE, FALSE} sau mulimii {0, 1};- datede tipcaracter, alecror elemente aparinmulimii caracterelor ce sunt definite prin combinaiede bii lanivelul unui bait; dincele 256decombinaiiunelesuntgrupate pentru litere, altele pentru cifre, altele pentru caractere speciale i pentru caractere de control; corespunztor, sunt definite date de tip alfabetic, de tip numeric, date de tip caractere de control etc.; aceste date au cte un singur element din mulimea ce-i definete tipul;- date de tip ir de caractere reprezint o compunere prin concatenare a datelor de tip caracter; dateleacesteaauundelimitatoral sfrituluideir, fieoconstantdetipntreglanceput, preciznd numrul de caractere care intr n alctuirea irului;e) Criteriul construirii tipurilor conduce la:- datedetipfundamental ceaparinunui tipimplementat nfiecarelimbaj deprogramare, precum tipurile ntreg, real, caracter, boolean, complex; programatorul are posibilitatea definirii constantelor simbolice i variabilelor proprii specificnd tipurile fundamentale i alege prelucrrile compatibile acestora;- date de tip derivat care se obin prin includerea n cadrul unor structuri a componentelor avnd unuldintipurilefundamentaleimplementatenlimbaj; rezultatul obinut esteuntipdedat derivatcaresepunencorespondencuunidentificatoricareestefolositdeprogramator pentru a defini variabilele n program avnd respectivul tip;f) Criteriul dispunerii n memoria intern, grupeaz datele n:- date dispuse n zone contigue care permit localizarea uneia dintre ele cunoscnd o adres i o deplasare; n cazul n care zonele de memorie ocupate au aceeai lungime, adresa fiecrei date se constituie ca termen al unei progresii aritmetice i este calculat cunoscnd adresa primei date i poziia n irul datelor contigue a elementului cutat;- date dispersate n memoria intern - se obin n cazul alocrii dinamice a memoriei necesare, ceea ce impune stocarea i conservarea adresei zonei de memorie asociat fiecrei date; dac datele dispuse n zone contigue, au realizat proiectarea alocrii n faza de compilare, datelor dispersate li se aloc memorie efectiv n faza de execuie i nu exist posibilitatea ca n mod direct s se construiasc modele de calcul a adreselor fizice pe care datele le ocup, mai ales dac alocarea memoriei este un proces ce depinde de testarea unor condiii din program;g) Criteriul cmpului de aciune, mparte datele n:- date cu caracter global care se definesc o singur dat, dar care sunt utilizate din orice punct al programului sau a funciilor i procedurilor care intr n componena lui; aceste date se definesc i li se aloc memorie o singur dat i au cmpul de aciune cel mai cuprinztor;- date cu caracter local sunt n fiecare procedur i li se aloc memorie dinamic, automat, la apelarea fiecrei proceduri sau funcii; odat cu revenirea n secvena apelat deci la ieirea din funcie sau din procedura, are loc eliberarea memoriei alocate (dealocarea memoriei); variabilele locale nu sunt folosite dect n procedura sau funcia unde au fost definite;- datedetipregistruaurolul deapuneladispoziieprogramatorului nlimbajeevoluate, accesul la registrele calculatorului; n cazul unei folosiri judicioase exist posibilitatea creterii vitezei de prelucrare, iar n cazul folosirii abuzive a registrelor se obine fenomenul invers;h) Criteriul definirii domeniului presupune:- date al cror domeniueste specificat prinlimita inferioar, limita superioar i forma de prezentare generic a elementelor;- date al cror domeniu este definit odat cu enumerare elementelor care i formeaz.i) Criteriul alocrii memoriei, grupeaz datele n:- date statistice calcule de alocare a memoriei se efectueaz n faza de compilare, iar nainte de execuie, alocarea este efectiv;- date dinamice a cror memorie este alocat i dealocat n timpul execuiei programului, prin funcii de bibliotec apelate.ntr-un program, o anumit dat este astfel definit nct se ncadreaz ntr-una din subgrupele fiecrui criteriu. Astfel, definirea:// PROGRAM definire:#include#include................................intk;main( ){}dintr-un program C/C++ se interpreteaz astfel:- k este o dat variabil (criteriul variabilitii);- k este o dat elementar (criteriul compunerii);- k este o dat de tip operand (criteriul semnificaiei);- k este o dat de tip ntreg (criteriul naturii datelor);- k este o dat de tip fundamental (criteriul construirii tipurilor);- k este o dat dispus ntr-o zon contigua (criteriul dispunerii n memoria intern);- k este o dat global (criteriul cmpului de aciune).Deci, k este un operand, variabila elementar, global, de tipul fundamental ntreg, dispus ntr-o zon contigu.1.3. MODELE DE PREZENTARE A DATELORntre forma de reprezentare natural sau extern a datelor i forma de reprezentare intern a acestora, exist mari diferene.Reprezentarea intern a datelor, se realizeaz utiliznd algoritmi de codificare, care pun n coresponden datele cu iruri de bii. Pentru fiecare tip de dat se definete lungimea zonei de memorie i algoritmul de codificare, precum i codurile operaiilor care utilizeaz operanzii n concordan cu caracteristicilede tip ale acestora.a) Modelul de verificare a concordanei tip-coninut-adresaModele de reprezentare a datelor au n componena lor: LSUPi, LIMFi valori ce precizeazlimitainferioarilimitasuperioaraintervaluluicreiai aparinedatadetipi specificat;Ai indicatorul algoritmului de realizare a reprezentrii interne pentrudatele de tip i;f() funcia de apartenen a datei la un anumit tip;M- mulimea funciilor de conversie;n- numrul de tipuri de date;k- cerine de aliniere a adresei de nceput a zonei de memoriek {1,2,4,8}Ti - natura i a datei;adr ( ) funcia de determinare a adresei unei zone de memorie pus n coresponden cu un identificator specificatadr: J -> Nunde: J este mulimea identificatorilor; N submulime a numerelor naturale cu care se localizeaz fiecare bait al zonei de memorie la dispoziia programatorului; N b a N ] , [~undea,bN, a TMulimea Tja naturii datelor fundamentale implementate nlimbajulde programare Lj , se definete prin:Tj = { T1, T2, ...,Tn }Dac j este C,TC = {int, bool, float, char, string}deci n=5, fr a fi luate n considerare variantele pentru datele ntregi, reale i posibilitatea de a specifica seturi de valori.Pentru datele de natur boolean, LSUP2 este 1 sau TRUE i LINF2 este 0 sau FALSE.Pentrudatele de natur real A3, corespunde modului de construire a mantisei i caracteristicii precum i dispunerea acestora pe cei 6 baii.Pentru datele ntregi H, mulimea funciilor de conversie are elementele:H = {f11, f12, f13, f14, f15}00 00 00 00 00 00 14 11cabbbb- cifra --- a sau b --[ ] - construcie opionalConstantele ntregi li seCC+---dddDintre acestea numai f11 i f14 sunt inversabile, deci tabloul funciilor:fij ( )i = 1,2,3,4,5j =1,2,3,4,5demonstreazc seefectueazconversii n toate direciilecu o anumit pierderea unor simboluri din descrierea iniial.Cerinele de aliniere sunt specifice particularitii hardware a sistemelor de calcul. n cazul n care la compilare nu este realizat optimizarea alocrii memoriei, apar zone neutilizabile cu efecte ce sunt interpretate mai dificil.Declararea: . . . . . . . . . . . . . . . . char a; float b; char c; char d;n absena optimizrii alocrii de memorie, conduce la rezervarea: n cazul optimizrii, secvenei de program i corespunde Este posibil optimizarea datorit comunicativitii dispunerii operanzilor ntr-o secven, atunci cnd acetia sunt elementari i nu apare problema redefinirii.Funcia de apartenena a datelor la un anumit tip se definete:f: U x Di-> { FALSE, TRUE}unde: U reprezint mulimea irurilor ce se genereaz cu simbolurile alfabetului construit pentru un limbaj.Di intervalul sau mulimea elementelor specifice tipului de date i'Di x daca TRUEDi x daca FALSEi x f ) , (De exemplu: f(13, int) =TRUE, pentru c 13 [-32768, 32767] ZDint fiind domeniul ntregilor, n timp ce f(-4, bool) = FALSE, pentru ca 4 nu aparine mulimii {FALSE, TRUE}.n secvena:. . . . . . . . . . . . . . . . . int x; . . . . . . . . . . . . . . . . .x = 20;. . . . . . . . . . . . . . . . .presupunnd c n compilare i editare de legturi, variabilei x i se asociaz zona de memorie:a b c d A : 8A+8 A+16 A+20b d a c

A :8

A+807AA000 00 00 00 00 00 14 11xcabbbb- cifra --- a sau b --[ ] - construcie opionalConstantele ntregi li seCC+---aaaccchhhjjjiiigggfffeeedddbbbddd111 777 10 11 ni1 nnadr(x) = 07AA0cont(x) = (00000014)16f(cont(x), int) = TRUEtip (x) = intDeci: f(cont(x), tip(x)) = TRUEFuncia de aliniere: K: adresa x tipi-> TRUE'iiik adresa daca FALSEk adresa daca TRUE) T K(adresa,Munde ki este factorul de aliniere cerut prin construcie pentru tipul de date Ti .K(07AA0, int) = TRUEpentru c 07AA04 K(adr(x), tip (x)) = TRUESe spune c variabila x este:- corect alocat- corect iniializatdac i numai dacf (cont(x), tip(x)) AND K(adr(x),tip(x)) = TRUEb) Modelul de generare a constantelor pentru un tip specificat de dateFolosind convenii i simboluri, se definesc reguli (mecanisme) de generare a constantelor.Astfel, se noteaz:Constantelor ntregi li se asociaz modelul de generare:Putem verifica dac irurile:0-125. 3+- 6044 sunt sau nu constante ntregi. Cu uurin ne dm seama c irurile . 3 +-60 i 44- nu ndeplinesc cerinele impuse de ablonul model.Pentru constantele de tip real se prezint modelul de generare:] [ ] ... [ [.] ] ... [ cc e c cc c ccE1]1

;'+1]1

;'1]1

;'+irurile:+1 . 2e-4- . 3 E22 . e-11e + 4sunt constante reale ntruct respect regulile de generare incluse n ablonc) Modele de descriere a datelor folosind grafuricabbbb- cifra --- a sau b --[ ] - construcie opionalConstantele ntregi li seCC+---ccccc. . . caaaccchhhjjjiiigggfffeeedddbbbddd111 777 10 11 ni1 nnntruct grafurile permit punerea n eviden a interdependenelor dintre elemente omogene sau neomogene, se consider utilizarea lor ca fiind sugestiv n cazul structurilor de date.Prin convenie, se stabilesc c nodurile care prezint numai arceincidentespreinteriorcorespunddatelorelementare, iar nodurilecareauarceincidentespreinterior i spreexterior corespund datelor de grup.Astfel, graful:este interpretat ca: data compus a are n alctuirea ei datele elementare b,ci d.Graful:0 - ->0 - ->0- ->0 ab c dcorespunde datelor interdependente, n care b urmeaz lui a, c urmeaz lui b i d urmeaz lui c. Nodurile a,b,c,d sunt fie date elementare, fie date compuse, iar pentru stabilirea relaiei de precedenta este necesar memorarea unor adrese.Pentrurealizarea ncadrul programelor a definirii structurilor complexe de date este necesar reprezentarea acestora folosind grafuri i dup aceea scrierea n program a unei forme liniarizate neambigue.De exemplu, pentrustructura de tiparborescent, seutilizeaz scrierea parantetica, ce presupune ca elementele de pe acelai nivel s fie separate prin virgul, iar pentru trecerea la nivel inferior, utilizarea unei paranteze rotunde deschise.Revenirea la nivelul precedent se marcheaz cu o parantez nchis. Astfel grafului:i corespunde liniarizarea:a(b(d,e,f,g), c(h(i,j)))d) Modele care permit implementarea recursivitii n descrierea datelorSe face deosebire ntre modelele recursive de descriere a datelor precum: : : = + -: : = 01 2 3 4 5 6 7 8 9 : : = : : = i modelele care implementeaz, recursivitatea n descrierea datelor.Astfel, construcia:bcaaaaccchhhjjjiiigggfffeeedddbbb111 777 10 11 ni1 nntip_de_data=( _ntreg,_)pune n eviden ca dat coninedoudateelementarei anume care are tipul ntreg i care are tipul .Aceste modele permit descrierea structurilor de date autoreferite liste, stive i arbori.e) Modele graficeSunt utilizate reprezentri grafice pentru locaiile de memorie asociate variabilelor i constantelor unui program. Prin arce se stabilesc legturile dintre locaii. Acest model de descriere a datelor este sugestiv i fr ambiguitate.Construcia:reprezint o list, fiecare component avnd dou elemente: primul reprezint informaia util avndvalorile1,7i 10, iaral doileaconineadrese. Arceleorientateindiclocaiaacrei adresa este memorat n componenta precedent.f) Modelul vectorialSe consider un vector avnd un numr dat de componente. Fiecare component are o semnificaie precizat, iar componentele luate n ansamblu lor descriu complet i corect structurile de date.Seobservcpentrudateleelementare, multedintrecomponentelevectorului sunt nule. Zerourile, arat lipsa dependenelor n aval i n amonte sau mrimea distanei dintre dou componente.Funcia distant se definete astfel:d(x,y)= adr (y) adr (x)Definim lg (x,Ti), funcia lungime a zonei de memorie asociat operandului x.De exemplu, pentru secvena de program:. . . . . . . . . . . . . . .x : extended;y :comp;z : shortint;w : word;. . . . . . . . . . . . . . .lg(x, extended) = 10lg (y, comp) = 8lg (z, shortint) = 1lg(w, word) = 4lg : IxT -> {1,2,4,6,8,10}Programul care pune n eviden lungimile tipurilor de date ale limbajului C/C++ este://program dimensiune_tip;#include #include main(){cout