Structuri de date fundamentale

Introducere

Sistemele de calcul moderne sunt dispozitive care au fost concepute cu scopul de a facilita si accelera calcule complicate, mari consumatoare de timp.

o      Din acest motiv, viteza, frecventa de lucru si capacitatea lor de a memora si de a avea acces la cantitati mari de informatii au un rol hotarator si sunt considerate caracteristici primordiale ale calculatoarelor

o      Abilitatea de calcul, in cele mai multe cazuri este irelevanta in maniera directa.

Cantitatea mare de informatii pe care o prelucreaza un sistem de calcul reprezinta de regula, o abstractizare a lumii inconjuratoare, respectiv a unei parti a lumii reale.

o      Informatia furnizata sistemului de calcul consta dintr-o multime de date selectate referitoare la lumea reala,

o      Datele selectate se refera la multimea de date care este considerata cea mai reprezentativa pentru problema tratata si despre care se presupune ca din ea pot fi obtinute (deduse) rezultatele dorite.

In acest context, datele reprezinta o abstractizare a realitatii

o      In procesul de abstractizare anumite proprietati si caracteristici ale obiectelor reale, pe care acestea le reprezinta, sunt ignorate intrucat pot fi considerate nerelevante pentru problema particulara tratata.

o      Abstractizarea este de fapt o simplificare a faptelor.

o      In rezolvarea unei probleme cu ajutorul unui sistem de calcul un rol esential revine alegerii unei abstractizari convenabile a realitatii

Alegerea abstractizarii se poate realiza in doi pasi:

o      (1) Definirea unui set reprezentativ de date care modeleaza (reprezinta) situatia reala.

o      (2) Stabilirea reprezentarii abstractizarii.

Alegerea abstractizarii datelor este determinata:

o      De natura problemei de rezolvat.

o      De uneltele care vor fi utilizate in rezolvarea problemei, spre exemplu de facilitatile oferite de un anume sistem de calcul.

Alegerea reprezentarii este de multe ori o activitate deosebit de dificila intrucat nu este determinata in mod unic de facilitatile disponibile.

o      De regula, alegerea reprezentarii datelor se poate realiza la diferite niveluri de abstractizare, functie de obiectivul urmarit si de limbajul de programare utilizat.

In acest context, un limbaj de programare reprezinta:

o      Un calculator abstract capabil sa inteleaga fraze construite cu ajutorul termenilor definiti in cadrul acestui limbaj de programare

o      Termeni definiti in cadrul limbajului de programare, pot sa incorporeze un anumit nivel de abstractizare al entitatilor efectiv utilizate (definite) de catre masina reala.

o      Utilizand un astfel de limbaj, programatorul va fi eliberat spre exemplu de chestiuni legate de reprezentarea numerelor daca acestea constituie entitati elementare in descrierea limbajului.

Utilizarea unui limbaj de programare care ofera un set fundamental de abstractizari, se reflecta in special in domeniul de reliabilitate al programelor care rezulta.

o      Este mult mai usor sa se conceapa un program bazat pe obiecte familiare (numere, multimi, secvente) decat unul bazat pe structuri de biti, cuvinte si salturi.

o      Desigur, oricare sistem de calcul reprezinta in ultima instanta datele ca si un masiv de informatii binare.

Acest fapt este insa transparent pentru programator

Programatorul poate opera cu notiuni abstracte, mai usor de manipulat intrucat dispune de compilatoare specializate care preiau sarcina transformarii notiunilor abstracte in termeni specifici sistemului de calcul tinta.

Cu cat nivelul de abstractizare este mai strans legat de un anumit sistem de calcul

o      Cu atat este mai simplu pentru dezvoltatorul de aplicatii sa aleaga o reprezentare mai eficienta a datelor,

o      Cu atat mai redusa este posibilitatea ca reprezentarea aleasa sa satisfaca o clasa mai larga de aplicatii convenabile.

Aceste elemente precizeaza limitele nivelului de abstractizare abordat pentru un sistem de calcul real respectiv pentru un limbaj de programare.

Limbajul de programare avut in vedere este limbajul C

Acest limbaj acopera in mod fericit o plaja larga situata intre

o      (1) Limbajele orientate spre masina sau limbaje dependente de masina care lasa deschise problemele reprezentarilor si

o      (2) Limbajele cu un inalt nivel de abstractizare bazate pe obiecte care rezolva automat problemele de reprezentare.

In acest mod utilizatorul poate aborda nivelul de abstractizare convenabil din punctul de vedere al realizarii unei anumite aplicatii.

2. Tipuri de date. Tipuri de date abstracte

2. Conceptul de tip de date

In procesul de prelucrare a datelor se face o distinctie clara intre:

(1) Numerele reale

(2) Numerele complexe

(3) Valori logice

(4) Variabilele care reprezinta valori individuale, multimi de valori, multimi de multimi sau functii, multimi de functii, etc.

In acest sens se statueaza principiul conform caruia fiecare constanta, variabila, expresie sau functie este de un anumit tip.

Un tip este in mod esential caracterizat prin:

(1) Multimea valorilor careia ii apartine o constanta a tipului in cauza, respectiv multimea valorilor pe care le poate asuma o variabila, o expresie sau care pot fi generate de o functie incadrata in acel tip

(2) Un anumit grad de structurare (organizare) a informatiei;

(3) Un set de operatori specifici.

In practica curenta, tipul asociat unei variabile este precizat printr-o declaratie explicita de constanta, variabila sau functie, declaratie care precede textual utilizarea respectivei constante, variabile sau functii.

Caracteristicile conceptului de tip sunt urmatoarele:

(1) Un tip de date determina multimea valorilor careia ii apartine o constanta, sau pe care le poate asuma o variabila sau o expresie, sau care pot fi generate de un operator sau o functie.

(2) Tipul unei valori precizate de o constanta, variabila sau expresie poate fi dedus din forma sau din declaratia sa, fara a fi necesara executia unor procese de calcul.

(3) Fiecare operator sau functie accepta argumente de un tip precizat si conduce la un rezultat de un tip precizat.

(4) Un tip presupune un anumit nivel de structurare (organizare) a informatiei.

Drept urmare, respectand aceste reguli, un compilator poate verifica compatibilitatea si legalitatea anumitor constructii de limbaj, in faza de compilare, fara a fi necesara executia efectiva a programului.

• Din punctul de vedere al sistemului de calcul, memoria este o masa omogena de biti fara vreo structura aparenta.
• Ori tocmai structurile abstracte de date sunt acelea care permit recunoasterea, interpretarea si prelucrarea configuratiilor de cifre binare prezente in memoria sistemului de calcul

2.2. Tipuri de date abstracte

Definirea notiunii de tip de date abstract (TDA):

o      Un TDA se defineste ca un model matematic caruia i se asociaza o colectie de operatori specifici.

Vom realiza o paralela cu conceptul de functie.

(1) Functia generalizeaza notiunea de operator.

In loc de a fi limitat la utilizarea exclusiva a operatorilor definiti in cadrul limbajului de programare ('built-in' operators), folosind functiile, programatorul este liber sa-si defineasca proprii sai operatori, pe care ulterior sa-i aplice asupra unor operanzi care nu e necesar sa apartina tipurilor de baza (primitive) ale limbajului utilizat.

Un exemplu de procedura utilizata in aceasta maniera este spre exemplu, functia de inmultire a doua matrici.

(2) Functiile incapsuleaza anumite parti ale unui algoritm prin 'localizare'

Aceasta inseamna plasarea intr-o singura sectiune a programului a tuturor instructiunilor relevante.

Intr-o maniera similara

(1) Un TDA generalizeaza tipurile de date primitive (intreg, real, etc.), dupa cum functiile sunt generalizari ale operatiilor primitive (+, -, etc.).

(2) Un TDA incapsuleaza conceptual un tip de date in sensul ca din punct de vedere logic si fizic, definirea tipului si toate operatiile referitoare la el sunt localizate intr-o singura sectiune a programului.

(3) Daca apare necesitatea modificarii implementarii TDA-ului

(3.1) Programatorul stie cu certitudine locul in care trebuiesc efectuate modificarile

(3.2) Poate fi sigur ca modificarea sectiunii respective nu produce modificari nedorite in restul codului programului, daca nu se modifica formatul operatorilor TDA-ului respectiv

(4) In plus, in afara sectiunii in care sunt definiti operatorii, TDA-ul in cauza poate fi tratat ca un tip primitiv.

Dezavantajul major al folosirii TDA-urilor rezida in necesitatea respectarii riguroase a disciplinei de utilizare.

Cu alte cuvinte toate referirile la datele incapsulate intr-un TDA trebuiesc realizate prin operatorii specifici.

Aceasta cerinta nu este verificabila la nivelul compilatorului si trebuie acceptata ca si o constrangere a disciplinei de programare.

Exemplul 2.2

Se considera un tip de date abstract Lista.

Nodurile listei apartin unui tip precizat TipNod.

Fie:

L o instanta a TDA-ului (L: Lista),

v o variabila nod (v: TipNod)

c o referinta la un nod al listei (c: TipReferintaNodLista).

Un set posibil de operatori pentru TDA Lista este urmatorul:

ListaVida(L:Lista);- operator care initializeaza pe L ca lista vida;

2. c:= Primul(L:Lista); - operator care returneaza valoarea indicatorului la primul nod al listei, sau indicatorul vid in cazul unei liste goale;

3. c:= Urmator(L:Lista); - operator care returneaza valoarea indicatorului urmatorului nod al listei, respectiv indicatorul vid daca un astfel de nod nu exista;

4. Insereaza(v:TipNod, L:Lista); - operator care insereaza nodul v in lista L dupa nodul curent.

5. Furnizeaza(v:TipNod, L:Lista); - operator care furnizeaza continutul nodului curent al listei.

Observatii referitoare la avantajele definirii unui astfel de TDA.

1) Odata definit si implementat TDA Lista, toate prelucrarile de liste se pot realiza in termenii operatorilor definiti asupra acestuia, declarand un numar corespunzator de instante ale TDA-ului

2) Indiferent de maniera concreta de implementare a TDA Lista (tablouri, pointeri, cursori), din punctul de vedere al utilizatorului, forma operatorilor ramane cea definita initial.

3) Nu exista nici o limitare referitoare la numarul de operatii care pot fi aplicate instantelor unui model matematic precizat.

4) Eficienta, siguranta si corectitudinea utilizarii TDA-ului Lista este garantata numai in situatia in care utilizatorul realizeaza accesele la listele definite numai prin operatorii asociati tipului respectiv.

2.2. Definirea unui tip de date abstract (TDA)

Dupa cum s-a precizat, un tip de date abstract (TDA) este conceput ca si un model matematic caruia i se asociaza o colectie de operatori definiti pe acest model.

In consecinta, definirea unui tip de date presupune:

(1) Precizarea modelului matematic

(2) Definirea operatorilor asociati.

Limbajele de programare includ mai multe metode de definire a tipurilor de date.

In toate situatiile se porneste de la un set de tipuri denumite Tipuri primitive

Tipurile primitive joaca rolul de caramizi ale dezvoltarii.

In cadrul acestor tipuri primitive se disting:

(1) Tipurile standard sau predefinite

(2) Tipurile primitive dezvoltate de utilizator

(1) Tipurile standard sau predefinite includ de regula numerele si valorile logice.

Ele se bazeaza pe modele matematice consacrate (multimile de numere intregi, reale, logice, etc.) si implementeaza operatiile specifice definite pe aceste categorii de numere.

Daca intre valorile individuale ale tipului exista o relatie de ordonare, atunci tipul se numeste ordonat sau scalar.

(2) Tipuri primitive definite de utilizator.

O metoda larg utilizata de constructie a unor astfel de tipuri este aceea a enumerarii valorilor constitutive ale tipului.

Spre exemplu, intr-un program care prelucreaza figuri geometrice, poate fi introdus un tip primitiv numit tip_figura ale carui valori pot fi precizate de identificatorii dreptunghi, patrat, elipsa, cerc.

In multe cazuri, noile tipuri se definesc in termenii unor tipuri anterior definite.

Valorile unor astfel de tipuri, sunt de obicei conglomerate de valori componente ale unuia sau mai multor tipuri constitutive definite anterior motiv pentru care se numesc tipuri structurate.

Tipuri structurate. Sunt conglomerate de valori de componente. Daca exista un singur tip constitutiv, acesta se numeste tip de baza.

Poate fi construita o intreaga ierarhie de astfel de structuri,

Pentru definirea tipurilor structurate, se utilizeaza metode de structurare. Metodele de structurare pot fi:

Statice: tabloul, articolul, multimea si secventa (fisierul).

Dinamice: listele, arborii, grafurile

Standard (predefinite): intreg, real,

boolean,.

Tipuri primitive

(nestructurate)

Definite de utilizator: enumerare

TIPURI

DE

DATE Statice: tablou, articol, multime

Tipuri structurate

Dinamice: liste, arbori, grafuri

Pentru a utiliza un tip de date definit, trebuiesc declarate variabile incadrate in tipul in cauza, proces care se numeste instantiere

Prelucrarea acestor variabile se realizeaza cu ajutorul operatorilor asociati tipului.

In concluzie:

(1) Un tip este de fapt o maniera de structurare a informatiei.

(2) Pentru tipurile nestructurate este mai relevanta multimea constantelor tipului si mai putin gradul de structurare.

(3) Pe masura ce tipul devine mai complex, gradul de structurare devine tot mai relevant.

2.2.2. Implementarea unui TDA

Implementarea unui TDA este de fapt o translatare, adica o exprimare a sa in termenii unui limbaj de programare concret.

Implementarea unui TDA presupune:

(1) Precizarea structurii propriu-zise (modelul matematic) in termenii unui limbaj de programare

(2) Definirea functiilor care implementeaza operatorii specifici.

Activitatea de implementare a unui tip se realizeaza numai in cazul tipurilor de date definite de utilizator, in restul cazurilor elementele specifice de implementare fiind de regula incluse in limbajul de programare utilizat.

Un tip structurat se implementeaza pornind de la tipurile de date de baza care sunt definite in cadrul limbajului, utilizand facilitatile de structurare disponibile.

In continuare definirea functiilor care implementeaza operatorii este intim legata de maniera de implementare aleasa pentru materializarea TDA-ului.

Exista posibilitatea abordarii ierarhice a implementarii TDA-urilor, respectiv implementarea unui TDA in termenii altor TDA-uri deja existente, spre exemplu apartinand unor biblioteci

2.3. Tip de date abstract. Tip de date. Structura de date

Se pune intrebarea: Care este semnificatia termenilor de mai jos, care sunt adesea confundati?

(1) Tip de date abstract (TDA),

(2) Tip de date (TD) sau simplu tip

(3) Structura de date (SD)

4) Data elementara (DE)

(1) Dupa cum s-a precizat, un tip de date abstract este un model matematic, impreuna cu totalitatea operatiilor definite pe acest model.

La nivel conceptual, algoritmii pot fi proiectati in termenii unor tipuri de date abstracte (TDA)

Pentru a implementa insa un astfel de algoritm intr-un anumit limbaj de programare, este absolut necesar sa se realizeze o reprezentare a acestor TDA-uri in termenii tipurilor de date si ai operatorilor definiti in limbajul de programare respectiv.

(2) Un tip de date este o implementare a unui TDA intr-un limbaj de programare.

Un tip de date (TD) nu poate fi utilizat ca atare.

In consecinta in cadrul programului se declara variabile incadrate in tipul respectiv, variabile care pot fi efectiv prelucrate si care iau valori in multimea valorilor tipului.

Acest proces se numeste instantiere si el de fapt conduce in cazul tipurilor nestructurate la generarea unei date elementare (DE) iar in cazul tipurilor structurate la generarea unei structuri de date (SD).

(3) O data elementara este o instanta a unui tip de date nestructurat

(4) O structura de date este o instanta a unui tip de date structurat.

Ca atare legatura dintre aceste notiuni este materializata de urmatoarea formula:

DE (Data elementara)

TDA (implementare) TD (instantiere)

SD (Structura de date)

Se face precizarea ca formula de mai sus este valabila pentru tipurile primitive definite de utilizator si pentru cele structurate.

Prin implementare se intelege definirea tipului iar prin instantiere, declararea unei variabile asociate tipului.

In cazul tipurilor predefinite faza de implementare lipseste ea fiind inclusa intrinsec in limbajul de programare ca atare pentru aceste tipuri este valabila formula:

TD (instantiere) DE

3. Tipuri nestructurate

3. Tipul enumerare

In marea majoritate a programelor se utilizeaza numerele intregi, chiar atunci cand nu sunt implicate valori numerice si cand intregii reprezinta de fapt abstractizari ale unor entitati reale.

Pentru a evita aceasta situatie limbajele de programare introduc un nou tip de date primitiv nestructurat precizat prin enumerarea tuturor valorilor sale posibile

Un astfel de tip se numeste Tip enumerare si el este definit prin enumerarea tuturor valorilor sale posibile: c₁,c₂,.,c_n .

// Definirea tipului enumerare

enum TipEnumerare variabila;

typedef enum nume_tip; [3.b]

Tipul enumerare este un tip ordonat, valorile sale considerandu-se ordonate crescator in ordinea in care au fost definite in baza conventiei:

(c_i < c_j) (i < j)

Tipul enumerare este un tip nestructurat definit de utilizator

o      In consecinta utilizarea sa presupune atat faza de implementare (declarare a tipului) cat si faza de instantiere (declarare de variabile apartinatoare tipului).

/*Exemplu de implementare a tipului enumerare*/ /*3.c*/

typedef enum TipFigura;

typedef enum TipCuloare;

typedef enum TipBoolean;

typedef enum TipZiSaptamina;

typedef enum TipGrad;

La definirea unui astfel de tip se introduce nu numai un nou identificator de tip, dar se definesc si identificatorii care precizeaza valorile noului tip (de fapt domeniul valorilor tipului)

Acesti identificatori pot fi utilizati ca si constante in cadrul programului, sporind in acest fel considerabil gradul de intelegere al textului sursa.

/*Exemplu de instantiere a tipului enumerare*/ /*3.e */

TipCuloare c;

TipZiSaptamina z;

TipGrad g;

TipBoolean b;

c = alb;  /*c:= 0;*/

z = miercuri;  /*z:= 2;*/

g = capitan;  /*g:= 5;*/

b = fals;  /*b:= 1;*/

Astfel, referitor la secventa [3.c] se pot introduce spre exemplu variabilele c,z,g,b [3.e].

In mod evident, aceasta reprezentare la nivel de program este mult mai intuitiva decat spre exemplu:

c = 0; z= 2; g = 5 ; b = 1

3.2. Tipuri standard predefinite

Tipurile standard predefinite sunt acele tipuri care sunt disponibile in marea majoritate a sistemelor de calcul ca si caracteristici hardware

Tipurile standard predefinite includ numerele intregi, valorile logice, caracterele si numerele fractionare adica: INTEGER, BOOLEAN, CHAR, REAL.

(1) Tipul intreg implementeaza o submultime a numerelor intregi,

Dimensiunea intregilor (numarul maxim de cifre) variaza de la un sistem de calcul la altul si depinde de caracteristicile hardware ale sistemului.

Se presupune insa ca toate operatiile efectuate asupra acestui tip conduc la valori exacte si se conformeaza regulilor obisnuite ale aritmeticii.

Procesul de calcul se intrerupe in cazul obtinerii unui rezultat in afara setului reprezentabil (depasirea capacitatii registrelor - DCR) de exemplu impartirea cu zero.

Pe multimea numerelor intregi in afara operatorilor clasici de comparare si atribuire, se definesc si operatori standard:

Operatori standard definiti pe multimea intregilor: adunare (+), scadere (-), inmultire (*), impartire intreaga (/) si modulo (%)

m - n < (m / n)* n <= m

(m / n)* n + (m % n) = m

(2) Tipul real implementeaza o submultime reprezentabila a numerelor reale.

In timp ce aritmetica numerelor intregi conduce la rezultate exacte, aritmetica valorilor de tip real este aproximativa in limitele erorilor de rotunjire cauzate de efectuarea calculelor cu un numar finit de cifre zecimale.

Din acest motiv tipurile intreg respectiv real in marea majoritate a limbajelor de programare se trateaza separat.

Operatiile se noteaza cu simbolurile consacrate cu exceptia impartirii numerelor reale care se noteaza cu (/).

Operatiile care conduc la valori care depasesc domeniul de reprezentabilitate al implementarii conduc la erori (DCR) - de exemplu impartirea cu zero.

Implementarile curente ale limbajelor de programare contin mai multe categorii de tipuri intregi (simplu, fara semn, scurt, lung, etc.) respectiv mai multe tipuri reale (normal, dublu, lung) care difera de regula prin numarul de cifre binare utilizate in reprezentare.

(3) Tipul Boolean are doua valori care sunt precizate de catre identificatorii TRUE (adevarat) si FALSE (fals).

In limbajul C aceste valori lipsesc fiind substituite de valori intregi: 1 sau <> 0 semnifica adevarat, respectiv 0 semnifica fals.

Operatorii specifici definiti pentru acest tip sunt operatorii logici: conjunctie, reuniune si negatie

Tabelul 3.2.a. Operatori logici

(4) Tipul standard caracter cuprinde o multime de caractere afisabile.

o      Codificarea ASCII (American Standard Code for Information Interchage)

Litere mari A B C X Y Z

hexazecimal: x^'41^' x^'42^' x^'43^' x^'58^' x^'59^' x^'5A^'

zecimal: 65 66 67 88 89 90

Cifre: 0 1 2 9

hexazecimal: x^'30^' x^'31^' x^'32^' x^'39^'

zecimal: 48 49 50 57

Litere mici: a b c z

hexazecimal: x'61' x'62' x'63' x'7A'

zecimal: 97 98 99 122

Caracterul blanc: hexazecimal: x'20' zecimal: 32

In limbajul C tipurile char si int sunt echivalente.

Stabilirea naturii unui caracter:

('A' <= x) AND (x <= 'Z') - x este litera mare;

('a' <= x) AND (x <= 'z') - x este litera mica;

('0' <= x) AND (x <= '9') - x este o cifra.

Transformarea caracter-intreg se realizeaza in baza urmatoarelor relatii [3.2.c]

// Corespondenta intreg-caracter

char c; int n;

n=c-'0 // transformare caracter-intreg [3.2.c]

c=n+'0'; // transformare intreg-caracter

4. Tipuri structurate

4. Structura tablou. Tipul de date abstract tablou

Un tablou este o structura omogena el constand dintr-o multime de componente de acelasi tip numit tip de baza.

Tabloul este o structura de date cu acces direct (random-acces), deoarece oricare dintre elementele sale sunt direct si in mod egal accesibile.

Pentru a preciza o componenta individuala, numelui intregii structuri i se asociaza un indice care selecteaza pozitional componenta dorita.

La definirea unui tablou se precizeaza:

(1) Metoda de structurare, care este implementata direct de limbaj 

(2) Numele tabloului de date rezultat

(3) Tipul de baza al tabloului

(4) Tipul indice al tabloului

(5) Dimensiunea sau dimensiunile tabloului

// Definirea unei structuri tablou -

//tip_element nume_tablou[nr_elemente];

float tablou[10]; [4.b]

char sir[10];

Metoda de structurare tablou este indicata de prezenta perechii de paranteze drepte []

nume_tablou precizeaza numele tabloului care se defineste

tip_element precizeaza numele tipului de baza, adica tipul elementelor tabloului

o      tip_element nu este supus nici unei restrictii, adica el poate fi oricare alt tip (inclusiv un tip structurat)

Tipul indice este in mod implicit tipul intreg (int). Indicele ia valori in domeniul [0, nr_elemente-1]

Intre parantezele dreapte se precizeaza in mod efectiv numarul de elemente ale tabloului (nr_elemente) adica dimensiunea acestuia

Tabloul este o structura de date statica pentru care rezervarea de memorie se realizeaza in faza de compilare a programului.

O structura tablou poate fi initializata printr-un constructor de tablou si o operatie de atribuire:

tip­_element nume_tablou[nr_elemente]=;

// Constructia unui tablou

int vect[5]=;

int mat[2][3]=,};

char str[9]='Turbo C++';

Operatorul invers al unui constructor este selectorul. Acesta selecteaza o componenta individuala a unui tablou.

Fiind data o variabila tablou vector , un selector de tablou se precizeaza adaugand numelui tabloului, indexul i al componentei selectate: vector[i].

In locul unui indice constant poate fi utilizata o expresie index (de indice).

Evaluarea acestei expresii in timpul executiei programului, conduce la determinarea componentei selectate.

Tablourile definite sunt tablouri de o singura dimensiune sau tablouri liniare.

Accesul la oricare element al unui astfel de tablou se realizeaza utilizand un singur indice in mecanismul de selectie.

tip_element precizat la definirea unui tip de date tablou poate fi la randul sau un tip tablou.

Prin acest mecanism se pot defini tablourile de mai multe dimensiuni.

Astfel de tablouri se numesc de obicei matrice

Accesul la un element al matricei se realizeaza utilizand un numar de indici egal cu numarul de dimensiuni ale matricei

mat[i,j,k,. ,m,n]

// Definirea unei structuri tablou multidimensional

tip_element nume_tablou[nr_elemente1][nr_elemente2]

[nr_elementeN];

Formal, TDA Tablou poate fi precizat cam si in [4.e] iar o implementare a sa in limbajul C ca si in [4.f]

TDA Tablou

Model matematic: Secventa de elemente de acelasi tip. Indicele asociat apartine unui tip ordinal finit. Exista o corespondenta biunivoca intre indici si elementele tabloului.

Notatii:

TipElement -tipul elementelor tabloului;

a - tablou unidimensional;

i - index; [4.e]

e - obiect de tip TipElement.

Operatii

DepuneInTablou(a,i,e) - procedura care depune valoarea lui e in cel de-al i-lea element al tablolui a;

e:= FurnizeazaDinTablou(a,i) - functie care returneaza valoarea celui de-al i-lea element al tabloului a.

/*Exemplu de implementare - Varianta C */ /*4.f*/

#define NumarMaxElem valoareIntreaga

typedef tip_element tip_tablou[NumarMaxElem];

int i;

tip_tablou a;

tip_element e;

a[i]=e; /*DepuneInTablou(a,i,e)*/

e=a[i]; /*FurnizeazaDinTablou(a,i)*/

4.2. Tehnici de cautare in tablouri

Formularea problemei: se presupune ca este data o colectie de date, in care se cere sa se localizeze (fixeze) prin cautare un anumit element.

Se considera ca multimea celor n elemente este organizata in forma unui un tablou liniar a:

tip_element a[n];

De regula tip_element poate fi o structura struct cu un camp specific pe post de cheie.

Sarcina procesului de cautare este aceea de a gasi un element al tabloul a, a carui cheie este identica cu o cheie data x .

Indexul i care rezulta din procesul de cautare satisface relatia a[i].cheie=x si el permite accesul si la alte campuri ale elementului localizat

Se presupune in continuare ca tip_element consta numai din campul 'cheie', adica el este chiar cheia.

Cu alte cuvinte se va opera de fapt cu un tablou de chei.

4.2. Cautarea liniara

Atunci cand nu exista nici un fel de informatii referitoare la colectia de date in care se face cautarea, tehnica evidenta este aceea de a parcurge in mod secvential colectia prin incrementarea indexului de cautare pas cu pas.

Aceasta metoda se numeste cautare liniara

In secventele urmatoare sunt prezentate trei variante de cautare liniara

/*cautare liniara - varianta while */ /*4.2.a*/ 

tip_element a[nr_elemente];

tip_element x;

int i=0;

while ((i<n-1) && (a[i]!=x))

i++;

if (a[i]!=x )

else

Exista doua conditii care finalizeaza cautarea:

Elementul a fost gasit adica a[i] = x ;

Elementul nu a fost gasit dupa parcurgerea integrala a tabloului.

/*cautare liniara - varianta do */ /*4.2.b*/

tip_element a[nr_elemente];

tip_element x;

int i=-1;

dowhile ((i<n-1) && (a[i]!=x))

if (a[i]!=x )

else

In legatura cu aceste variante de algoritm se precizeaza urmatoarele:

La parasirea buclei mai trebuie realizata o comparatie a lui a[i] cu x in vederea stabilirii existentei sau nonexistentei elementului cautat (daca i=n)

Daca elementul este gasit, el este elementul cu cel mai mic indice (daca exista mai multe elemente identice).

/*cautare liniara - varianta for */ /*4.2.e*/

/*returneaza n pentru negasit, respectiv i<n pentru gasit*/

/* pe pozitia i*/

int cautare _liniara(int x,int a[],int n

Dupa cum se observa fiecare pas al algoritmului necesita evaluarea expresiei booleene (care este formata din doi factori) si incrementarea indexului.

o      Acest proces poate fi simplificat si in consecinta cautarea poate fi accelerata, prin simplificarea expresiei booleene.

Solutie de a simplifica expresia este aceea de a gasi un singur factor care sa-i implice pe cei doi existenti.

o      Acest lucru este posibil daca se garanteaza faptul ca va fi gasita cel putin o potrivire.

o      In acest scop tabloul a se completeaza cu un element aditional a[n+1] caruia i se atribuie initial valoarea lui x (elementul cautat). Tabloul devine: tip_element a[n+1];

Elementul x pozitionat pe ultima pozitie a tabloului se numeste fanion, iar tehnica de cautare, tehnica fanionului.

o      Evident, daca la parasirea buclei de cautare i = n , rezulta ca elementul cautat nu se afla in tablou

Algoritmul de cautare astfel modificat apare in [4.2.c, d si e].

/*cautare liniara tehnica fanionului (while)*/ /*4.2.c*/ 

tip_element a[nr_elemente+1];

tip_element x;

int i=0;

a[nr_elemente]=x;

while (a[i]!=x)

i++;

if (i == nr_elemente)

else

In secventa [4.2.d] apare acelasi algoritm implementat cu ajutorul ciclului (do).

/*cautare liniara tehnica fanionului (do) */ /*4.2.d*/ 

tip_element a[nr_elemente+1];

tip_element x;

int i=-1;

a[nr_elemente]=x;

dowhile (a[i]!=x)

if (i == NumarMaxElem)

else

Performanta cautarii liniare este O(n/2), cu alte cuvinte, in medie un element este gasit dupa parcurgerea a jumatate din elementele tabloului.

In secventa urmatoare apare un alt exemplu de implementare in limbajul C a tehnicii de cautare discutate.

//cautare liniara tehnica fanionului

//returneaza n pentru negasit, respectiv i<n pentru gasit // pe pozitia i

int cautare_fanion(int x,int a[],int n)

4.2.2. Cautarea binara

Procesul de cautare poate fi mult accelerat daca se dispune de informatii suplimentare referitoare la datele cautate.

Este bine cunoscut faptul ca o cautare se realizeaza mult mai rapid intr-un masiv de date ordonate (spre exemplu intr-o carte de telefoane sau intr-un dictionar).

In continuare se prezinta un algoritm de cautare intr-o structura de date ordonata, adica care satisface conditia:

tip_element a[n];

A_k:0<k<=n-1:a[k-1]<= a[k] [4.2.2.a]

Ideea de baza a cautarii binare:

Se inspecteaza un element aleator a[m] si se compara cu elementul cautat x.

(1) Daca este egal cu x cautarea se termina;

(2) Daca este mai mic decat x , se restrange intervalul de cautare la elementele care au indici mai mari ca m;

(3) Daca este mai mare decat x , se restrange intervalul la elementele care au indicii mai mici ca m.

In consecinta rezulta algoritmul denumit cautare binara.

Variabilele s si d sunt de tip indice si ele precizeaza limitele stanga respectiv dreapta ale intervalului in care elementul ar mai putea fi gasit:

/*cautare binara */ /*4.2.2.b*/

tip_element a[n];

tip_element x;

int s,d,m;

int gasit;

s=0; d=n-1; gasit=0;

while((s<=d)&&(!gasit))

if(gasit) /*avem o coincidenta la indicele m*/

Solutia optima in acest sens este alegerea elementului din mijlocul intervalului, intrucat ea elimina la fiecare pas jumatate din intervalul in care se face cautarea.

In consecinta rezulta ca numarul maxim de pasi de cautare va fi O(log ₂ n),

Aceasta performanta reprezinta o imbunatatire remarcabila fata de cautarea liniara unde numarul mediu de cautari este n / 2 .

Eficienta cautarii binare poate fi imbunatatita daca se interschimba instructiunile IF intre ele.

O imbunatatire a eficientei se poate obtine - ca si in cazul cautarii liniare - prin simplificarea conditiei de terminare.

Acest lucru se poate realiza daca se renunta la ideea de a termina algoritmul de indata ce s-a stabilit coincidenta.

La prima vedere acest lucru nu pare prea intelept, insa la o examinare mai atenta, se poate observa ca castigul in eficienta la fiecare pas este mai substantial decat pierderea provocata de cateva comparatii suplimentare de elemente.

Se reaminteste faptul ca numarul de pasi este log ₂ n .

Cu alte cuvinte, procesul de cautare continua pana cand intervalul de cautare ajunge de dimensiune banala (0 sau 1 element). Aceasta tehnica este ilustrata in [4.2.2.c].

/*cautare binara ameliorata */ /*4.2.2.c*/

tip_element a[n];

tip_element x;

int s,d,m;

s=0; d=n;

while(s<d)

if(d>n) /*nu exista elementul cautat*/;

if(d<=n)

if(a[d]==x)

/*elementul exista pe pozitia d*/;

else

/*elementul nu exista*/;

Ciclul se termina cand s = d .

Cu toate acestea egalitatea s = d nu indica automat gasirea elementului cautat.

Daca d > n nu exista nici o coincidenta. S-a cautat un element mai mare decat orice element al tabloului

Daca  d<=n  se observa ca elementul a[d] corespunzator ultimului indice d nu a fost comparat cu cheia,

In consecinta este necesara efectuarea in afara ciclului a unui test  a[d]=x  care de fapt stabileste existenta coincidentei.

Acest algoritm asemenea cautarii liniare, gaseste elementul cu cel mai mic indice, lucru care nu este valabil pentru cautarea binara normala.

Alte variante de implementare a celor doua cautari binare in limbajul C apar in secventa [4.2.2.d].

/*cautari binare - varianta C */ /*4.2.2.d*/

int cautare_binara(int x,int a[],int n)while(a[m]-x && s<=d);

return(a[m]-x)?n:m;

int cautare_binara_ameliorata(int x,int a[],int n)while(s<d);

return

((d>=n)||(d<n && a[d]-x))?n:d;

4.3. Structura articol. Tipul de date abstract articol

Metoda cea mai generala de a obtine a tipuri structurate este aceea de a reuni elemente ale mai multor tipuri, unele dintre ele fiind la randul lor structurate, intr-un tip compus.

Exemple in acest sens sunt:

Numerele complexe din matematica care sunt compuse din doua numere reale

Punctele de coordonate compuse din doua sau mai multe numere reale in functie de numarul de dimensiuni ale spatiului la care se refera.

In matematica un astfel de tip compus se numeste produsul cartezian al tipurilor constitutive.

Setul de valori al tipului compus consta din toate combinatiile posibile ale valorilor tipurilor componente, selectand cate o singura valoare din fiecare.

O astfel de combinatie se numeste n-uplu;

Termenul care descrie o data compusa de aceasta natura este cuvantul struct

In secventele [4.3.a.] si [4.3.b.] se prezinta modul generic de definire a unuei structuri struct

//Definire structura

struct nume_structura lista_var_structura;

Identificatorii nume_camp₁ , nume_camp₂ ,. nume_camp_n introdusi la definirea structrii, sunt nume conferite componentelor individuale ale acesteia.

Ei sunt utilizati in selectorii de articol care permit accesul la campurile unei variabile structurate de tip articol.

Pentru o variabila struct nume_structura x , cel de-al i-lea camp poate fi precizat prin notatia 'dot' sau 'punct':

x.nume_camp_i

O atribuire a respectivei componente poate fi precizata prin constructia sintactica:

x.nume_camp_i= x_i

unde x_i este o valoare (expresie) de tip_i .

Cateva exemple de definire a unor structuri articol.

/*Exemplu 1 de definire a unor structuri articol*/

struct data data_nasterii, data_inscrierii

struct data_nasterii, data_inscrierii

struct data

struct data data_nasterii, data_inscrierii

typedef struct data data_calendar

data_calendar data_nasterii, data_inscrierii

/*Exemplu 2 de definire a unor structuri articol*/

struct punct

struct dreptunghi   [4.3.g]

struct punct p1; double dist;

struct dreptunghi fereastra;

//Exemplu de utilizare

dist=sqrt((double)(px*px)+(double)(py*py));

fereastra.varfx=188; 

4.4. Structura secventa. Tipul de date abstract secventa

Caracteristica comuna a structurilor de date prezentate pana in prezent (tablouri, articole, multimi) este aceea ca toate au cardinalitatea finita, respectiv cardinalitatea tipurilor lor componente este finita.

Din acest motiv, implementarea lor nu ridica probleme deosebite.

Cele mai multe dintre asa numitele structuri avansate: secventele, listele, arborii, grafurile, etc, sunt caracterizate prin cardinalitate infinita.

Aceasta diferenta fata de structurile clasice este de profunda importanta avand consecinte practice semnificative.

Spre exemplu structura secventa avand tipul de baza T₀ se defineste dupa cum urmeaza:

S₀=< > (secventa vida)

S_i=<S_i-1,s_i> unde 0 < i si s_iI T₀

Cu alte cuvinte, o secventa cu tipul de baza T₀ , este:

o      Fie o secventa vida

o      Fie o concatenare a unei secvente (cu tipul de baza T₀) cu o valoare (s_i) a tipului T₀ .

Definirea recursiva a unui tip secventa conduce la o cardinalitate infinita.

o      Fiecare valoare a tipului secventa contine in realitate un numar finit de componente de tip T₀ ,

o      Acest numar este nemarginit deoarece, pornind de la orice secventa se poate construi o secventa mai lunga.

O consecinta importanta a acestui fapt este:

Volumul de memorie necesar reprezentarii unei structuri avansate, nu poate fi cunoscut in momentul compilarii,

Ca atare, este necesara aplicarea unor scheme de alocare dinamica a memoriei, in care memoria este alocata structurilor care 'cresc' si este eliberata de catre structurile care 'descresc'.

Pentru a implementa aceasta cerinta, este necesar ca limbajul superior utilizat in implementare sa fie prevazut cu acces la functii sistem care permit:

Alocarea / eliberarea dinamica a memoriei

Legarea / referirea dinamica a componentelor

In aceste conditii cu ajutorul instructiilor limbajului pot fi descrise si utilizate structuri avansate de date.

Tehnicile de generare si de manipulare a unor astfel de structuri avansate sunt prezentate in capitolele urmatoare ale cursului

Structura secventa este din acest punct de vedere o structura intermediara;

(1) Ea este o structura avansata din punctul de vedere al cardinalitatii care este infinita

(2) Este insa atat de curent utilizata incat includerea sa in multimea structurilor fundamentale este consacrata.

(3) Aceasta situatie este influentata si de faptul ca alegerea unui set potrivit de operatori referitori la structura secventa, permite implementatorilor sa adopte reprezentari potrivite si eficiente ale acestei structuri.

(4) Drept consecinta, mecanismele alocarii dinamice a memoriei devin suficient de simple pentru a permite o implementare eficienta, neafectata de detalii, la nivel de limbaj superior.

4.4. Tipul de date abstract secventa

Includerea structurii secventa in randul structurilor fundamentale, presupune constrangerea setului de operatori de o asemenea maniera incat se permite numai accesul secvential la componentele structurii.

Aceasta structura este cunoscuta si sub denumirea de fisier secvential sau pe scurt fisier.

Structura secventa este supusa unicei restrictii de a avea componente de acelasi tip, cu alte cuvinte este o structura omogena.

Numarul componentelor, denumit si lungime a secventei, se presupune a fi necunoscut atat in faza de compilare, cat si in faza de executie a codului.

Mai mult chiar, acest numar nu se presupune constant el putandu-se modifica in timpul executiei.

Cardinalitatea tipului secventa este in consecinta infinita.

In dependenta de maniera de implementare a structurilor de tip secventa, acestea se inregistreaza de regula pe suporturi de memorie externa reutilizabile cum ar fi benzile magnetice sau discurile in alocare secventiala.

Acest lucru face posibila tratarea relativ simpla a structurilor de tip secventa si permite incadrarea lor in randul structurilor fundamentale, desi de drept ele apartin structurilor dinamice.

Secventa este o structura ordonata.

Ordonarea elementelor structurii este stabilita de ordinea in timp a crearii componentelor individuale.

Datorita mecanismului de acces secvential preconizat, selectarea prin indici a componentelor individuale devine improprie.

In consecinta la definirea unui tip de secventa se precizeaza numai tipul de baza.

TYPE TipSecventa = FILE OF TipDeBaza;

In cadrul unei secvente definite ca mai sus in orice moment este accesibila o singura componenta, denumita componenta curenta, care este precizata printr-un pointer (indicator) asociat secventei.

Acest indicator avanseaza secvential, practic dupa executia oricarei operatii asupra secventei.

In plus oricarei secvente i se asociaza un operator boolean standard sfarsit de fisier notat cu Eof(f:TipSecventa) care permite sesizarea sfarsitului secventei.

Modul concret de acces la componente, precum si posibilitatile de prelucrare efectiva, rezulta din semantica operatorilor definiti pentru tipul de date abstract secventa este prezentat sintetic in [4.5.a] .

Implementarile recente ale limbajelor Pascal si C introduc in setul de instructiuni accesibile programatorului si operatori pentru prelucrarea secventelor implementate ca si fisiere secventiale.

In secventa [4.5.b] apare o astfel de implementare definita in limbajul Pascal. Variante asemanatoare stau la dispozitie si in limbajul C.

TDA Secventa

Modelul matematic: secventa de elemente de acelasi tip. Un indicator la secventa indica elementul urmator la care se poate realiza accesul. Accesul la elemente este strict secvential.

Notatii:

TipElement - tipul unui element al secventei. Nu poate

fi de tip secventa;

f - variabila secventa;

e - variabila de TipElement; [4.5.a]

b - valoare booleana;

numeFisierDisc - sir de caractere.

Operatori:

Atribuie(f,numeFisierDisc) - atribuie variabilei secventa f numele unui fisier disc precizat;

Rescrie(f) - procedura care muta indicatorul secventei la inceputul lui f si deschide fisierul f in regim de scriere. Daca fisierul f nu exista el este creat. Daca f exista, vechea sa varianta se pierde si se creeaza un nou fisier f vid;

ResetSecventa(f) - procedura care muta indicatorul la inceputul secventei f si deschide secventa in regim de consultare. Daca f nu exista se semnaleaza eroare de executie;

DeschideSecventa(f) - procedura care in anumite implementari joaca rol de rescrie sau reset de secventa;

b:= Eof(f) - functie care returneaza valoarea true daca indicatorul secventei indica marcherul de sfarsit de fisier al lui f;

FurnizeazaSecventa(f,e) - procedura care actioneaza in regim de consultare. Atata vreme cat Eof(f) este fals, furnizeaza in e urmatorul element al secventei f si avanseaza indicatorul acesteia;

DepuneSecventa(f,e) - pentru secventa f deschisa in regim de scriere, procedura copiaza valoarea lui e in elementul urmator al secventei f si avanseaza indicatorul acesteia;

Adauga(f) - procedura care deschide secventa f in regim de scriere, pozitionand indicatorul la sfarsitul acesteia, cu posibilitatea de a adauga elemente noi numai la sfarsitul secventei.

InchideSecventa(f) - inchide secventa.

TYPE TipElement = ;

TipSecventa = TEXT;

VAR f: TipSecventa; [4.5.b]

e: TipElement;

numeFisierDisc: string;

assign(f,numeFisierDisc)

rewrite(f)

write(f,e) ; writeln()

reset(f)

eof(f)

read(f,e); readln()

append(f)

close(f)

5 Rezumat

Pentru utilizarea sistemelor de calcul se folosesc datele. Datele sunt o abstractizare a lumii reale. Drept suport al abstractizarii se folosesc limbajele de programare.

Datele se incadreaza in tipuri de date care precizeaza domeniul valorilor, operatiile si nivelul de structurare al entitatilor care sunt incadrate in tipul respectiv.

Un tip de date abstract (TDA) este conceput ca un model matematic caruia i se asociaza un set de operatori specifici. Pentru a fi utilizat un TDA trebuie definit, apoi implementat intr-un limbaj de programare si instantiat in cadrul aplicatiei

Tipurile de date se clasifica in

Tipuri de date primitive (nestructurate) care includ tipurile standard sau predefinite si tipurile primitive de date definite de utilizator

Tipuri de date structurate care includ tipurile de date statice (tablou, articol, secventa) si tipurile de date dinamice (lista, arbore, graf)

Tipurile structurate se construiesc din cele nestructurate utilizind metode de structurare definite in limbajele de programare.

Un TDA definit, prin implementare devine tip de date (TD) care prin instantiere devine data elementara DE (daca este nestructurat) respectiv o structura de date SD (daca este un tip structurat)

Tipurile de date primitive includ tipurile: enumerare, intreg, real, boolean, caracter

Tipurile structurate statice includ tipurile: tablou, articol si secventa

Una dintre operatiile cel mai frecvente aplicate asupra structurii tablou este cautarea.

Pentru tablourile obisnite se utilizeaza cautarea liniara respectiv varianta de cautare numita tehnica fanionului

Pentru tablourile ordonate se foloseste o metoda mult mai performanta: cautarea binara.

6 Exercitii

Definiti conceptele de data, abstractizare si limbaj de programare. Evidentiati legatura dintre ele.

Ce este un tip de date? Prin ce se caracterizeaza un tip de date? Care sunt caracteristicile unui tip de date?

Definiti conceptul de tip de date abstract (TDA). Care sunt avantajele utilizarii TDA-urilor?

Cum se defineste un TDA? Cum se implementeaza un TDA?

Cum se clasifica tipurile de date?

Care este diferenta intre urmatoarele entitati: tip de date abstract, tip de date, structuraa de date si data elementara?

Descrieti tipurile de date nestructurate (enumerare, intreg, real, caracter). Ce au in comun aceste tipuri?

Ce este un tablou? Cum se defineste structura tablou? Dati exemple de definire a unor tablouri liniare si a unor tablouri de mai multe dimensiuni

Se cere sa se redacteze doua functii: una care implementeaza cautarea liniara, celalta cautarea cu tehnica fanionului intr-un tablou liniar.

Se cere sa se redacteze doua functii: una care implementeaza cautarea binara, celalta cautarea binara ameliorata intr-un tablou liniar ordonat.

Se cere sa se redacteze un program C care:

a)     defineste un tablou de numere intregi

b)     citeste elementele tabloului de la tastatura

c)     citeste o cheie x

d)     cauta cheia x in tablou prin diferite tehnici de cautare, utilizand functiile din aplicatiile anterioare

e)     afiseaza rezultatul cautarii

Ce este o structura? Cum se defineste o structura? Cum se acceseaza componentele unei structuri? Dati exemple de structuri.

Se cere sa redacteze un program C care implementeaza operatiile matematice cu numere complexe: adunarea, scaderea si modulul. La definirea numerelor complexe se va utiliza un tip structurat. Se va defini de asemenea o functie pentru citirea si o functie pentru afisarea unui numar complex. Programul principal va exemplifica operatiile implementate.

Ce este si cum se defineste structura secventa? Care sunt principalele caracteristici ale structurii secventa?