Tehnici de Implementare a Problemelor cu Volum Variabil de Date

CUPRINS:

INTRODUCERE…………………………………………………………………………………………………………3

REZOLVAREA PROBLEMELOR CU AJUTORUL TABLOURILOR…………………………….3

REZOLVAREA PROBLEMELOR CU AJUTORUL POINTERILOR………………………………7

LEGĂTURA DINTRE OINTERI ȘI TABLOURI…………………………………………………..7

ALOCAREA DINAMICĂ A MEMORIEI……………………………………………………………..8

REZOLVAREA PROBLEMELOR CU AJUTORUL LISTELOR……………………………………10

IMPLEMENTAREA LISTELOR CU JUTORUL TABLOURILOR………………………..10

IMPLEMENTAREA LISTELOR FOLOSIND STRUCTURI CU AUTODEFINIRE..11

STRUCTURI ARBORESCENTE………………………………………………………………………………..35

ELEMENTE GENERALE………………………………………………………………………………….35

TRAVERSAREA ARBORILOR…………………………………………………………………………36

REPREZENTAREA STRUCTURILOR ARBORESCENTE………………………………….36

EXPERIMENT DEMONSTRATIV……………………………………………………………………………..38

BIBLIOGRAFIE:

INTRODUCERE

În diverse domenii ale științei apare necesitatea folosirii seturilor de date cu volum variabil. De exemplu, în fizică este necesară prelucrarea seturilor de măsurători, numărul înregistrărilor fiind multe ori necunoscut în momentul începerii măsurătorilor. Un factor esențial în abordarea acestor tipuri de probleme îl constituie momentul când se cunoaște volumul setului de date. Se pot astfel delimita trei cazuri de bază.

O primă clasă de probleme cuprinde cazurile când volumul setului de date este cunoscut la momentul proiectării. Aceste probleme pot fi rezolvate prin tehnici caracteristice operațiilor cu tablouri. Un tablou consta din componente de același tip, fiind astfel o structură omogenă. Pentru a preciza o componentă individuală, numelui întregii structuri i se adaugă un indice care selectează acea componentă. În cazul în care se utilizează un singur indice pentru a ne referi la elementele tabloului, tabloului spunem că tabloul este unidimensional, iar în cazul în care se folosesc n indici, tabloul este n-dimensional.

În cazul în care volumul setului de date se cunoaște abia în momentul execuției, se utilizează variabilele de tip pointer. Un pointer desemnează mulțimea de variabile care pot lua ca valori adrese de memorie la care este alocat spațiul pentru un conținut de un anume tip, numit tip de bază. Pointerii oferă posibilitatea de a acționa în cadrul programului asupra conținutului zonelor de memorie alocate utilizând adrese simbolice pentru referirea lor, fără ca programul să cunoască valorile interne ale acestor adrese. Acest mod de localizare poartă numele de adresare indirectă a conținutului unei zone de memorie. Prin această procedură se permite alocarea dinamică a zonelor de memorie.

Un al treilea tip de probleme cuprinde cazurile cand volumul setului de date se cunoaște de-abia după obținerea ultimului element din set. În aceste cazuri structurile de date pot fi organizate în liste liniare sau arborescente. O listă este o secvență de zero sau mai multe elemente numite noduri, de un anumit tip numit tip de bază. Numărul n al nodurilor se numește lungimea listei. Dacă n este zero avem de-a face cu o listă vidă. O proprietate importantă a unei liste este aceea că nodurile sale pot fi ordonate liniar în funcție de poziția lor în cadrul listei.

REZOLVAREA PROBLEMELOR CU AJUTORUL TABLOURILOR

Tablourile se memorează în locații succesive de memorie, începând cu o anumită adresă. Această adresăeste desemnată prin numele tabloului. Prin compilare se alocă, la întâlnirea unei declarații de tablou, o zonî contigua de memorie necesară pentru a păstra valorile tuturor elementelor sale. Pentru fiecare element al tabloului se repartizează o zonă de memorie necesară în conformitate cu tipul tabloului respectiv. Numele unui tablou este un simbol care ca valoare chiar adresa primului element al tabloului respectiv. Operațiile de bază care se efectuează asupra unei structuri de date de tip tablou sunt creearea, listarea, sortarea, căutarea unui anumit element.

În continuare se prezintă anumite probleme car epot fi rezolvate în mod natural folosind tablourile.

Memorarea matricilor rare

Matricele rare își găsesc aplicabilitatea în modelarea unor procese de natură industrială, economică, tehnică, socială etc. Capitolul de față își propune să trateze modalitățile de reprezentare în structuri de date a matricelor rare, precum și principalele operații matriceale implementate într-un limbaj orientat pe obiecte. În final este prezentată o aplicație concretă – estimarea parametrilor unei regresii statistice. În rezolvarea multor probleme de natură economică, tehnică, socială, a diverselor probleme de optimizare, precum și în modelarea unor procese industriale și tehnologice este necesar să se determine modelul matematic care descrie funcționarea procesului respectiv. Descrierea acestor sisteme fizice conduce la obținerea unor modele matematice care fie în mod direct, prin modelare, fie prin metoda de rezolvare implică sisteme de ecuații algebrice liniare sau probleme de programare liniară a căror matrice a coeficienților este rară (sparse), în sensul că ponderea elementelor nenule în totalul elementelor matricei este mică. Din punct de vedere practic trebuie remarcat faptul că analiza sistemelor mai sus amintite conduce la obținerea unor modele matematice de mari dimensiuni care implică sisteme de ecuații algebrice liniare de mii de ecuații, pentru a căror rezolvare sunt necesare resurse mari de memorie și timp de calcul. În multe cazuri practice, cum sunt sistemele în timp real, timpul de calcul este o resursă critică, nefiind permis să depășească o valoare limită. Modelele matematice ale proceselor reale implică un număr foarte mare de variabile și restricții care prezintă fenomenul de raritate ,sparsity, adică o slabă interconectare a elementelor sale. Luarea în considerație a fenomenului de raritate furnizează un nou mod de abordare foarte eficient, ce implică în dezvoltarea aplicațiilor informatice folosirea unor structuri de date speciale, care să conducă la reducerea resurselor de memorie și a timpului de calcul. În general, o matrice – dimensională este rară atunci când conține un număr mic de elemente nenule nn ),( , adică . Cantitativ, matricele rare sunt caracterizate de ponderea numărului de elemente nenule în totalul de elemente, pondere ce definește gradul de umplere al matricei. În aplicațiile curente se întâlnesc matrice rare cu grade de umplere între 0,15% și 3%.

Schema 1. Când o matrice este de dimensiuni mari și conține unu număr mare de elemente nule (marice rară) se poate folosi o schemă de memorare care reține numai elemente nule, salvându-se astfel memorie și tip de calcul. Este necesar, deoarece zona de memorare a matricii nu va fi identică cu matricea inițială, ca tehnica de memorare să cuprindă – pe lângă elementele nule – și mijloacele de identificare a pozițiilor acestor elemente în matrice.

Memorarea compactă aleatoare constă în utilizarea unei zone primare ELEM, care conține numai elemente nule ale matricii, precum și a două zone secundare continuând indicii de linie LIN și de coloană COL a elementelor nule. Deoarece fiecare element nenul este identificat în mod univoc prin memorarea indicelui de linie și de coloană corespunzător, este posibil ca matricea sa fie memorată în ordine aleatoare. Astfel matricea:

0 a12 0 a14 0

A = 0 0 a23 0 a25

a31 a32 0 0 a35

poate fi memorată astfel:

Un avantaj important al memorării compact aleatoare constă în faptul ca elemtele nenule adiționale ale matricei pot fi adăugate la sfârșitul zonelor de memorare fară a perturba înregistrarea anterioară a celorlalte elemente. De asemenea, această schemă de memorare permite o manevrabilitate rapidă a datelor. Metoda este foarte potrivită și pentru elementele nenule de deasupra diagonalei utilizând zonele ELEM, LIN, COL și elementele diagonale într-o secundară DIAG.

Numărul total de cuvinte necesar memorării matricei A(m,n) nesimetrică, prin intermediul celor trei zone ELEM, LIN, COL este 3.m.n.r, unde r este raportul de memorare, definit ca raportul dintre numărul de elemente nenule și numărul total de elemente. Raportul dintre cerințele de memorie ale acestei scheme și a celei standard este c=3 r.

Se observă ca această schemă este eficientă pentru memorarea matricilor rare cu o densitate a elementelor nenule de maximum 33,3%.

Schema 2. În schema 1 pentru identificarea elementelor nenule ale unei matrici rare au fost utilizate două zone secundare LIN și COL. În schema 2 se va utiliza o singură zonă secundară POZ, de dimensiune egală cu numărul de elemente nenule ale matricei, conținând simultan informații asupra indicilor de linie și de coloană.

Astfel, fiecărui element ELEM[k] memorat în zona primară ELEM l se atașază un număr întreg POZ[k] din care se pot determina indicia de linie și coloană. Dacă elemental A[i,j]=0 este memorat în locația k a zonei primare, atunci POZ[k]=i+(j-l) m, unde m este numărul de linii ale matricei.

Valoarea POZ[k] identifică în mod univoc poziția elementului în matrice. Utilizând această schemă matricea de mai sus poate fi memorată estfel:

Pentru a determina indicele de linie și de coloană al elementului memorat în locația k va fi utilizatăurmaătoarea tehnică de calcul:

– coloana j este obținută ca: j cel mai mic întreg mai mare sau egal cu valoarea POZ[k]/m;

– linia I este determinată astfel: i=POZ[k]-(j-l) m

Această schemă de memorare necesită mai puțină memorie decât schema precedentă, dar în schimb este mai puțin rapidă în manevrarea datelor.

Numărul total de cuvinte necesare memorării matricei este 2mnr. Raportul dintre cerințele de memorie ale acestei scheme și cea standard este c=2 r.

Se observă că această schemă de memorare este eficientă pentru matricile rare a căror densitate a elementelor nenule este de maximum 50%.

Transformarea din baza 10 în 2

Transformarea unui număr întreg n din baza 10 în baza 2 se face reținând cifrele într-un vector. Deoarece cifrele se obțin în ordinea inversă, vectorul se va afișa de la dreapta la stânga.

#include<iostream.h>

#include<conio.h>

#define MAX 32

int m,x[MAX], semn;

long n;

void afisare_sir(void);

void calcul(long);

void main()

{

clrscer();

cout<<”n=”;cin>>n;

if(n<0)

{semn=-1;n=-n;}

else semn=1;

calcul(n);

afisare_sir();

}

void afisare_sir(void)

{

int i;

cout<<semn*n<<”10=”;

if(semn<0)cout<<”-“;

for (i=m-l;i>0;i–)//m=nr de cifre din baza 2

cout<<x[i];

cout<<”2”;

}

void calcul(long n)

{

int rest;

if(n)

{ m=0;

while(n!=0)

{

rest=(int)n%2;

x[m]=rest;

m++;

n=n/2;

}

}

else {x[0]=0; m=1;}

REZOLVAREA PROBLEMELOR CU AJUTORUL POINTERILOR

LEGĂTURA DINTRE POINTERI ȘI TABLOURI

Un tablou cu o singură dimensiune este o succesiune de variabile având toate de același tip (tipul de bază al tabloului), care ocupă o zonă contiguă de memorie.

Un tablou are:

dimensiune (egală cu numărul de elemente al tabloului)

un nume (care identifică global tabloul)

o clasă de alocare

un tip comun tuturor elementelor tabloului

Dimensiunea tabloului precizează numărul de elemente printr-o constantă întreagă sau printr-o expresie constantă.

La declararea unui tablou se specifică: numele, tipul de bază, clasa de alocare și dimensiunea.

tip nume[dimensiune];

sau

clasă tip nume[dimensiune];

Un pointer este o variabilă care are ca valori adrese ale altor variabile, sau mai general adrese de memorie.

Un pointer este asociat unui tip de variabile, deci avem pointeri către int, char, float, etc.

În general o variabilă pointer p către tipul T se declară:

T *p;

Se știe că adresa primului element dintr-un tablou reprezintă tocmai valoarea pointerului ce dă numele respectivului tablou însă există totuși o diferență între numele unui tablou și o variabilăde tip pointer. Această diferență consta în faptul că unei variabile de tip pointer I se atribuie valori la execuție în timp ce numele unui tablou are tot timpul ca valoare adresa primului său element. Astfel, numele unui tablou este un pointer constant.

Programul din exemplul următor citește și afișează elementele a două tablouri. Accesul la primul tablou se face indexat, iar la al doilea tablou se realizează prin pointeri:

#include<studio.h>

#include<conio.h>

#define n,10

int tab1[n], tab2[n];

void citire1()

{

int i;

puts(“Introduceti elementele lui tab1:”);

for(i=0;i<n;i++)

{

putchar(‘:’)

scanf(“%d”,&tab1[i]);

}

}

void tiparire 1()

{

int i;

puts(“Elementele lui tab1:”);

for(i=0;i<N;i++)

printf(“%d”,tab1[i];

}

void citire2()

{

int*pi;

puts(“Introduceti elementele lui tab2:”);

for(pi=tab2;pi<tab2N;pi++)

{

putchar(‘:’); scanf(“%d”,pi);

}

}

void tiparire2()

{

int*pi;

puts(“Introduceti elementele lui tab2:”);

for(pi=tab2 ;pi<tab2+N ;pi++)

printf(“%d”, *pi);

putchar(‘\n’);

}

void main()

{

citire1();

tiparire1();

citire2();

tiparire2();

}

ALOCAREA DINAMICĂ A MEMORIEI

Operația prin care se caută și se atribuie spațiu de memorie în HEAP, necesar unei date, în timpul executării instrucțiunilor programului, poartă numele unei date, în timpul executării instrucțiunilor programului, poartă numele de alocare dinamică a datei. Principiul stivei este cel care guvernează memorarea în zona dinamică de memorare. Astfel, în timpul execuției programului, sistemul de operare folosește pentru variabile noi spațiul de memorie din zona adreselor libere (HEAP), și nu segmentul de date al cărui conținut a fost fixat odată cu compilarea programului.

Funcțiile de bază pentru alocare în zona liberă sunt conținute în biblioteca alloc.h. pentru alocarea unei zone de memorie în HEAP se folosește funcția malloc, care are prototipul:

void* malloc (unsigned n) ;

efectul acestei funcții este alocarea unei zone de memorie contigue de n octeți și returnarea adresei de început a zonei de alocare. Această adresă este un pointer de tip void (void*). O dată de un anumit tip se păstrează într-o zonă de memorie în HEAP cu scopul de a păstra n valori de tip int, se declară u pointer spre tipul int și apoi se apelează funcția malloc

int*p ;

p=(int*)malloc(n*sizeof(int))

Cu ajutorul funcției free pot fi eliberate zonele prin funcția malloc, pentru a fi eventual realocate.

În exemplul de mai jos, programul aloca spațiul pentru o variabilă întreagă dinamică, iar după citire și tipărire spațiul este eliberat.

#include<studio.h>

#include<alloc.h>

#include<conio.h>

int *pi;//pi este veriabilă statică

void main ()

{

pi=(int *) malloc(sizeof(int));

if(pi=NULL)

{

puts(“Memorie insuficientă !”);

return;//revenire din main

}

printf(“valoare:”); scanf(“%d”,pi);

*pi*=2; //dublarea

printf(“val=%d,pi (adresa pe HEAP)=%p, adr_pi(var static)=%p\n,*pi,&pi”);

printf(“%d %d %d\n”, sizeof(*pi), sizeof(pi), sizeof(&pi));

free(pi); //eliberare spatiu

printf(“pi(dupa eliberare):%p\n”,pi);

}

REZOLVAREA PROBLEMELOR CU AJUTORUL LISTELOR

În timp ce pentru structurile de date fundamentale există construcții de limbaj care le reprezintă și care au un anumit corespondentîn particularitățile hardware ale sistemelor care le implementează, pentru structurile de date avansate acest lucru nu mai este valabil. Reprezentarea acestor structuri de date avansate, caracterizate printr-un nivel mai înalt de abstracție, se realizaează cu ajutorul structurilor de date fundamentale și structuri de tip listă.

IMPLEMENTAREA LISTELOR CU AJUTORUL TABLOURILOR

Implementarea optimă a listelor se realizează folosind alocarea înlănțuită, însă listele pot fi implementate și cu ajutorul tipului tablou. Astfel, o listă se asimilează cu un tablou, iar nodurile sunt stocate într-o zonă contiguă de memorie, în locații succesiv. Tipul listă este definit ca o structură cu două câmpuri. Primul câmp reprezintă un tablou cu elemente de tipnod, lungimea aleasă de programator este astfel încât să fie auficientă pentru a păstra cea mai mare dimensiune de listă ce poate apărea în aplicația respectivă. Câmpul al doilea este un ăntreg ultim care indică în tablou poziția ultimului nod al listei. În ipoteza că elementele listei sunt considerate ca un întreg, structura de tip listă se va defini în modul următor:

#define lungime_maxima 100

typedef int nod;

typedef struct {

nod element[lungime_maxima];

int ultim;

} lista;

Acest mod de reprezentare a listelor se prezintă graphic în Figura 4.1.

ultim

Figura 4.1. Reprezentarea listei cu ajutorul tipului tablou.

Traversarea listei se realizează ușor în această reprezentare, iar noile noduri se adaugă șa sfârșitul listei. Pentru a insera un nod la mijlocul listei, toate nodurile următoare vor fi deplasate cu o poziție spre sfârșitul listei, penru a face loc noului nod. Tot astfel, sprimarea unui nod cu excepția ultimului, presupune deplasarea celorlalte pentru a elimina spațiul creat.

IMPLEMENTAREA LISTELOR FOLOSIND STRUCTURI CU AUTODEFINIRE

Lista liniară simplu înlănțuită

O lista este o colectie de elemente intre care este specificata cel putin o relatie de ordine.

O lista liniara simplu inlantuita este caracterizata prin faptul ca relatia de ordine definita pe multimea elementelor este unica si totala. Ordinea elementelor pentru o astfel de lista este specificata explicit printr-un cimp de informatie care este parte componenta a fiecarui element si indica elementul urmator, conform cu relatia de ordine definita pe multimea elementelor listei.

O listă liniară poate fi păstrată în locații succesive de memorie, însă se folosește o schemă mult mai flexibilă, în care fiecare nod este legat de următorul nod al listei prin câmpulnext, iar primul nod al listei este indicat prinr-o variabilă pointer p. Acest tip de implementare se numește listă liniară simplu înlănțuită și este prezentat schematic în Figura 4.2.

Prim el1 el2 eln

Figura 4.2 schema de implementare a unei liste liniare simplu înlănțuite.

Dacă se folosește o variabilă de tip nod, iar câmpul next indică primul nod efectiv allistei, celelalte câmpuri care conțin informația propriu-zisă rămân neasignate, atunci pointerul prim indică nodul fictive cap de listă. Prelucrarea listelor înlănțuite este simplificată în anumite situații prin utilizarea acestui nod de început. În continuare se folosește pointerul prim de început.

Dacă cheia este de tip întreg și informația este un șir de cel mult 10 caractere, se poate defini lista ca o structură recursivă de tipul:

Strzct nod {

char info[10];

struct nod *next;

}

typedef struct nod Tnod;

se defineste și tipul ref ca fiind tipul pointer la nodurile listei:

Typedef Tnod *ref;

Ref p;/*retine adresa primului nod al listei*/

Operațiile uzuale cu liste sunt inserarea unui nod în fața listei (la începutul listei), inserarea la sfârșitul listei (în spatele listei), traversarea listei, inserarea unui nod după un nod anume al listei, inserarea înaintea unui anumit nod, suprimarea unui nod al listei.

Inserarea unui element nou în listă se poate realiza înainte sau după un nod care menține o valoare dată. Evident s-ar putea realiza și insera pe o poziție data astfel încât toate elementele începând de la acea poziție se vor deplasa mai la dreapta.

În cazul în care inserarea se realizează „după”, se continuă cu un nod intermediar c în lista până la nodul după care se va face inserarea după care se crează un nou nod (nodul a) apoi se generează legăturile: mai întâi de la a la c->next apoi de la c la a. Există posibilitatea ca ultimul nod să mențină valoarea după care se execută inserarea caz în care se modifică ultimul.

În cazul în care inserarea se execută „înainte” se avansează cu un nod intermediar c în listă până la un nod situat înaintea celui căutat, se formează un nounod (nodul a) apoi se produc legăturile: mai întâi de la a la c->next apoi de la c la a. Există posibilitatea ca primul nod să mențină valoarea înainte de care se realizează inserarea caz în care se modifică primul.

În cazul în care se produce ștergerea, se dezvoltă cu un nod intermediar c în listă până la un nod situat înaintea celui căutat (nodul de șters), se produc noi legături între precedentul și următorul nod de șters, se eliberează spațiul de memorie.

Iată o soluție pentru implementarea funcțiilor anterioare:

#include<conio.h>

#include<fstream.h>

struct Nod

{int info;

Nod *next;

};

Nod *prim, *ultim;

Funcțiile de creare și adăugare se pot restrânge într-o singură funcție care poate testa dacă există un prim nod și în funcție de rezultatul testului va executa alocarea primului nod sau se va completa cu un nod la sfârșit

void creare_adăugare()

{if(prim=NULL)

{prim=new Nod;

cout<<”introduceți valoarea menținută în primul nod:”;

cin>>prim->info;

prim->next=0//la crearea listei va exista un singur nod, primul // și prin urmare adresa următoare lui este 0

ultim=prim;//evident, având un singur element acesta va fi primul // și ultimul

}

else

{Nod*c;

c=new Nod;

count<<”valoarea de adăugat în listă”;

cin>>c->info;

ultim->next=c;//se “agață” noul nod c, după ultimul din listă

ultim=c;//evident noul nod e ultimul…

ultim->next=0;//….după ultimul nu e nimic, deci nici o adresă

}

}

void listare ()

{Nod*c;

c=prim;

while(c!=0//cat timp mai sunt în listă

{cout<<c->info<<” ”;

c=c->next;//avansez în listă trecând la următoarea adresă

}

cout<<endl;

}

funcția inserare_după() va insera după o valoare val transmisă din main()

void inserare_dupa(int val)

{Nod *c,*a;

//Nod *a reține adresa nodului ce se va insera în listă

//cu *c se face avansarea în listă până la nodul ce conține valoarea după

//care se face inserarea; evident se pornește de pe primul;

c=prim;

while(c->info!=val &&c)

c=c->next;

a=new Nod;

cout<<”valoarea de inserat”;

cin>>a->info;

a->next=c->next;

c->next=a;

if(c=ultim) ultim=a;//pentru că există și posibilitatea ca valoarea //după care se face inserarea să fie reținută de ultimul element

}

funcția inserare_înainte() va insera înainte de o valoare val transmisă din main()

void inserare_înainte(int val)

{Nod *c,*a;

//Nod *a reține adresa nodului ce se va insera în listă

//cu *c se face avansarea în listă până la nosul ce conține valoarea //înainte

//care se face inserarea; evident se pornește de la primul;

c=prim;

//pentru că există și posibilitatea ca valoarea înainte de care se face //inserarea

//să fie menținută de primul nod se va face un test și în caz afisrmativ se va

//stabili un nou prim element

if(prim->info=val)

{c=new Nod;

cout<<”valoare de inserat”;

cin>>c->info;

c->next=prim;

prim=c;}

else

{while(c->next->info!=val &&c) //c se așează înainte de elementul //căutat

c=c->next;

a=new Nod;

cout<<”valoarea de inserat ”;

cin>>a->info;

a->next=c->next;

c->next=a;}

}

funcția produce ștergerea unui element după conținutul transmis ca parametru

void șterge(int val)

{Nod *c,*a //a se șterge, c este precedentul sau se va genera o nouă //legătură între c și a->next

c=prim;

if(prim->info=val) //dacă primul nod reține val se șterge primul

{a=prim; //se reține în a

prim=prim->next; //primul va devein urm[torul element

delete a;} //se eliberează memoria

else

{while(c->next->info!=val &&c)// se poziționează pe elementul ce urmează a // fi șters

c=c->next;

a=c->next;

c->next=a->next;

if(a==ultim) ultimo=c;

delete a;}// se eliberează memoria

}

void main()

{int i,n,val_info;

cout<<”n=”;cin>>n;

for(i=l;i<=n;i++)

creare_adăugare();

listare();

cout<<”după ce valoare din listă se produce inserarea”;

cin>>val_info;

inserare_după(val_info);

listare();

creare_adăugare();

listare();

cout<<”valoare înainte de care se face inserarea”;

cin>>val_info;

inserare_înainte(val_info);

listare();

cout<<endl<<”valoare ce urmează a fi șterasă:”;

cin>>val_info;

ștergere(val_info);

listare();

}

Concluzii privind utilitatea modurilor de implementare a listelor simplu înlănțuite

În ceea ce privește listele implementate cu ajutorul tipului tablou, putem fi mulțumiți de acest tip de implementare pentru cazurile în care se cere tot timpul accesul la elementele aflate în interiorul listei, iar ștergerile și inserările sunt destul de rare. În acest caz este recomandat să utilizăm o listă implementată cu tipul tablou și nu una implementată prin tipul pointer deoarece dimensiunea listei nu va avea o variație mare în timp și de asemenea accesul la elementele unui tablou se va face direct, spre deosebire de accesele la elementele unei liste implementată prin pointeri, la nodurile căreia, accesul va fi secvențial.

Optam pentru o listă implementată prin pointeri în cazul în care sunt frecvente inserările de elemente, ștergerile, nu putem aprecia foarte bine dimensiunea pe care o va putea avea lista în timp. Listele implementate prin pointeri nu necesită deplasări ale elementelor spre începutul sau sfârșitul său, în cazul ștergerii respectiv inserării de elemente, așa cum o necesită implementarea prin tablou de elemente.

În concluzie, trebuie să optați pentru liste implementate prin tablou daca sunt necesare multe accesări ale informațiilor și puține inserări și ștergeri, iar dimensiunea listei e aproape constantă pe tot timpul execuției, și va recomand implementarea prin tipul pointer a listelor în caz contrar.

Lista dublu înlănțuită

Câteodată este necesară deplasarea rapidă în cadrul listei, în ambele direcții. Pentru a avea această posibilitate de mutare rapidă este util a se memora referințe atât spre nodul ce succede nodului curent, cât și spre predecesorul nodului curent. O astfel de abordare duce la o nouă structură de date, este vorba despre lista liniară dublu înlănțuită. Această structură alături de stive și cozi, este o structură derivată din structura de tip listă, diferența e că, în timp ce stiva și coada sunt cazuri particulare ale listei simplu înlănțuite, lista dublu înlănțuită produce beneficii pe care nu le are o listă simplu înlănțuită, deci putem considera lista simplu înlănțuită ca o simplificare (un caz particular) al listei dublu înlănțuite.

Structura ce reține o listă liniară dublu înlănțuită este de arătată mai jos:

struct nod

{

char element[20];

nod *urm, *ant;

};

Ștergerea unui element necesită, în cazul în care elementul nu este nici primul, nici ultimul, găsirea nodului R, care va fi șters, pointerul R va indica acest nod, se va modifica apoi referința ant a succesorului lui R, astfel ca aceasta să indice predecesorul lui R, și referința urm a predecesorului lui R, astfel ca aceasta să indice succesorul lui R. Astfel efectuăm o ștergere fizică a nodului R. Urmează apoi o ștergere logică a lui R, folosind funcția free.

Dacă nodul de șters e primul nod al listei, pointerul p va înainta cu o poziție, pentru a nu pierde primul element al listei.

void stergere(void)

{

nod *succ, *pred;

if(r==p) p=p->urm;

succ=r->urm;

pred=r->ant;

if(r->ant!=NULL) pred->urm=r->urm;

if(r->urm!=NULL) succ->ant=r->ant;

free(r);

}

Introducerea primului nod al listei dublu înlănțuite presupune formarea spațiului de memorie necesar, setarea valorii elementului, și de asemenea setarea pointerilor pentru urm și ant, pe NULL. Pointerul p va indica acest nod.

void insp(void)

{

if((s=(nod*)malloc(sizeof(nod)))==NULL)

{

printf("\nesuare alocare de memorie");

printf("\ntastati enter pentru iesire");

getch();

exit(1);

}

printf("\nIntroduceti elementul continut de nod: ");

scanf("%s",&(s->element));

s->urm=NULL;

s->ant=NULL;

p=s;

}

Introducerea unui nod la dreapta unui nod indicat de un pointer r, necesită alocarea de spațiu pentru noul nod, inserarea informației ce o va reține noul nod, vom face ca referința urm a noului nod să indice spre succesorul lui r, iar referința ant a noului nod să indice spre nodul r. Referința urm a nodului r va indica noul nod, iar referința ant a succesorului lui r va arăta de asemenea noul nod.

Dacă succesorul lui R va fi NULL(r era ultimul element al listei), nu vom modifica referința ant a succesorului pentru că prin diferențierea succesorului se va realiza o eroare.

void insdd(void)

{ nod *succ;

succ=r->urm;

if((s=(nod*)malloc(sizeof(nod)))==NULL)(1)

{

printf("\nesuare alocare de memorie");

printf("\ntastati enter pentru iesire");

getch();

exit(1);

}

printf("\nAdăugați elementul continut de nod: ");

scanf("%s",&(s->element));(2)

s->ant=r;(3)

s->urm=succ;(4)

r->urm=s;(5)

if(succ!=NULL) succ->ant=s;(6)

}

Pentru introducerea unui nod în stânga nodului indicat de pointerul r, vom aloca spațiu pentru noul nod, vom introduce informația corespunzătoare noului nod, pointerul ant a noului nod va arăta predecesorul lui R, iar pointerul urm va indica nodul R. Totodată va fi modificat pointerul urm al predecesorului lui R astfel ca să indice spre noul nod, și pointerul ant al nodului R, astfel ca să indice noul nod.

Ca și în cazul inserării la dreapta, poate apărea o eroare dacă încercăm diferențierea predecesorului lui R pentru a-i modifica referința urm, dacă acesta nu există, adică dacă R e primul nod al listei și predecesorul său e NULL. Dacă predecesorul este NULL, atunci alocarea se va face la stânga lui R, deci pe prima poziție, în consecință pointerul p va trebui modificat corespunzător.

void insds(void)

{

nod *pred;

pred=r->ant;

if((s=(nod*)malloc(sizeof(nod)))==NULL)(1)

{

printf("\nesuare alocare de memorie");

printf("\ntastati enter pentru iesire");

getch();

exit(1);

}

printf("\nIntroduceti elementul continut de nod: ");

scanf("%s",&(s->element));(2)

s->ant=r->ant;(3)

if(pred!=NULL) pred->urm=s;(4)

else p=s;

s->urm=r;(5)

r->ant=s;(6)

}

Ca un avantaj al folosirii listelor liniare dublu înlănțuite este faptul că această implementare oferă o deplasare rapidă atât înainte cât și înapoi, spre deosebire de lista liniară simplu înlănțuită, la care parcurgerea este rapidă numai într-o parte, de la începutul listei spre sfârșit. Nu trebuie uitat însă faptul că nodurile listei dublu înlănțuite rețin pe lângă pointerul spre nodul următor și o referință spre nodul anterior. Această referință va ocupa un spațiu egal cu spațiul necesar reprezentării unei adrese în sistemul de operare respectiv(de obicei acesta este de 2 sau 4 octeți). Dacă avem un număr mare de noduri puteți remarca o oarecare risipă de memorie.

Pentru aplicațiile care necesită traversarea listelor înainte și înapoi se definește structura de listă înlănțuită. Astfel, pentru cazul în care, fiind dar un element oarecare al listei trebuie determinat cu rapiditate succesorul și predecesorul său, se memorează în fiecare nod al listei referințele înainte și înapoi.

Acest tip de structură este prezentat schematic în Fig. 4.3.

0

Figura 4.3. Structura unei liste dublu înlănțuite.

Presupunând informația un șir de cel mult 10 caractere, putem descrie o astfel de structură în limbajul C astfel:

Typedef struct nod

{

char info[10];

struct nod *urm, *prec;

} Tnod;

typedef Tnod *ref;

ref p; /*primul nod al listei */

Avantajul oferit de o listă dublu înlănțuită este faptul că inserarea unui nod fie la dreapta fie la stânga unui nod dat, se realizează ușor. Celelalte operații de bază se efectuează ca și în cazul în care am considera lista ca o listă simplu înlănțuită după câmpul urm.

În situațiile practice de programare, nodul de început al listei dublu înlănțuite este transformat într-un nod fictive care practic „închide cercul”. Astfel, câmpul precedent al acestui nod indică ultimul nod al listei, iar câmpul următor al ultimului nod al listei indică acest nod fictiv. Se definește astfel lista circulară în cazul căreia ultimul nod al listei se înlănțuie cu primul(și primul nod cu ultimul în cazul alocării dublu înlănțuite).

Operatii cu liste duble

Parcurgere si afisare lista

Lista este parcursa pornind de la pointerul spre primul element si avansand folosind pointerii din structura pana la sfarsitul listei (pointer NULL).

// Parcurgere si afisare lista dubla

void Afisare(Element* cap)

{

//cat timp mai avem elemente

//in lista

while (cap != NULL)

{

//afiseaza elementul curentcout << cap->valoare << endl;

//avanseaza la elementul urmatorcap = cap->urmator;

}

}

Pentru parcurgerea inversa a listei se va porni cu un pointer catre ultimul element al listei, iar avansarea se va face folosind secventa cap = cap->anterior; .

Inserare element

Inserarea unui element se poate realiza la inceputul sau la sfarsitul listei.

a) Inserare la inceput

Acesta este cazul cel mai simplu: trebuie doar introdus elementul, legat de primul element din lista si reașezarea capului listei:

//Introducere element la inceputul unei

//liste dublu inlantuite

void InserareInceput(Element* &cap, Date val)

{

//Alocare nod si initializare valoare

Element *elem = new Element;

elem->valoare = val;

elem->anterior = NULL;

//legare nod in lista

elem->urmator = cap;

if (cap != NULL)

cap->anterior = elem;

// mutarea capului listei

cap = elem;

}

b) Inserare la sfarsitul listei

In acest caz trebuie prima dată parcursa lista si dupa aceea adaugat elementul si apoi legat de restul listei. De asemenea, trebuie avut in vedere cazul in care lista este vida.

//Introducere element la sfarsitul unei

//liste dublu inlantuite

void InserareSfarsit(Element* &cap, Date val)

{

//Alocare si initializare

nodElement *elem = new Element;

elem->valoare = val;

elem->urmator = NULL;

elem->anterior = NULL;

daca avem lista vida

if (cap == NULL)

// doar modificam capul listei

cap = elem;

else

{

//parcurgem lista pana la ultimul nod

Element *nod = cap;

while (nod->urmator != NULL)

nod = nod->urmator;

//adaugam elementul nou in lista

nod->urmator = elem;

elem->anterior = nod;

}

}

c) introducerea dupa un element dat

void InserareInterior(Element* &cap, Element* p, Date val)

{

Alocare si initializare nod

Element *elem = new Element;

elem->valoare = val;

elem->urmator = NULL;

elem->anterior = NULL;

// lista vida

if (cap == NULL)

{

cap = elem;

return;

}

//inserare la inceputul listei

if (cap == p)

{

elem->urmator = cap;

cap->anterior = elem;

cap = elem;

return;

}

//inserare in interior

elem->urmator = p->urmator;

elem->anterior = p;

p->urmator->anterior = elem;

p->urmator = elem;

}

Cautare element

Cautarea unui element dintr-o lista, presupune parcurgerea listei pentru gasirea nodului in functie de un criteriu. Cele mai frecvente criterii sunt cele legate de pozitia in cadrul listei si de informatiile utile continute de nod. Rezultatul operatiei este adresa primului element gasit sau NULL.

a) Cautarea dupa pozitie

Se înaintează pointerul cu numarul de pozitii specificat:

// Cautare element dupa pozitie

Element* CautarePozitie(Element* cap, int pozitie)

{

int i = 0; // pozitia curenta

//parcurge lista pana la

//pozitia ceruta sau pana la

//sfarsitul listei

while (cap != NULL && i < pozitie)

{

cap = cap->urmator;

i++;

}

// daca lista contine elementul

if (i == pozitie)

return cap;

else

return NULL;

}

b) Cautarea dupa valoare

Se parcurge lista pana la terminarea acesteia sau descoperirea elementului:

// Cautare element dupa valoare

Element* CautareValoare(Element* cap, Date val)

{

//parcurge lista pana la gasirea

//elementului sau epuizarea listei

while (cap != NULL && cap->valoare !

= val) cap = cap->urmator;

return cap;

}

Stergere element

a) Stergerea unui element din interiorul listei (diferit de capul listei)

//sterge un element din interiorul listei

//primind ca parametru adresa elementului

void StergereElementInterior(Element* elem)

{

//scurcircuitam elementul

elem->anterior->urmator = elem->urmator;

elem->urmator->anterior = elem->anterior;

// si il stergem

delete elem;

}

b) Stergerea unui element de pe o anumita pozitie

Daca elementul este primul din lista, atunci se modifica capul listei, altfel se cauta elementul si se sterge folosind functia stabilită anterior:

void StergerePozitie(Element* &cap, int pozitie)

{

//daca lista e vida nu facem nimic

if (cap == NULL)

return;

//daca este primul element, atunci

//il stergem si mutam capul

if (pozitie == 0)

{

Element* deSters = cap;

cap = cap->urmator;

cap->anterior = NULL;

delete deSters; return;

}

//daca este in interor, atunci folosim

//functia de stergere

Element* elem = CautarePozitie(cap, pozitie);

StergereElementInterior(elem);

}

c) stergerea dupa o valoare

Se cauta elementul si se foloseste functia de stergere element:

void StergereValoare(Element* &cap, Date val)

{

//daca lista e vida nu facem nimic

if (cap == NULL)

return;

//daca este primul element, atunci

//il stergem si mutam capul

if (cap->valoare == val)

{

Element* deSters = cap;

cap = cap->urmator;

cap->anterior = NULL;

delete deSters;

return;

}

// cautam elementul

Element* elem = CautareValoare(cap, val);

// daca a fost gasit, atunci il stergem

if (elem->urmator != NULL)

StergereElementInterior(elem);

}

Stiva

O stivă este un tip special de listă în care toate inserările, suprimările și orice alt acces se execută la un singur capăt, care se numește vârful stivei. Stivele se mai numesc liste de tipul LIFO(last in first out), adică ultimul element introdus este primul suprimat.

Pentru implementarea stivelor nu este indicată utilizarea tipului tablou deoarece operația de inserare și ștergere necesită mutarea întregii liste în jos, respectiv în sus, această activitate consumând un timp promoțional cu numărul de elemente ale stivei.

O utilizare mai eficientă a tipului tablou ține cont de faptul că inserțiile și suprimările se fac numai în vârf. Astfel, se poate considera drept bază a stivei sfârșitul tabloului, stiva crescând în sensul descreșterii indexului în tablou. Un cursor numit vârf indică poziția curentă a primului element al stivei. Acest mod de implementare este prezentat schematic în Figura 4.4.

Figura 4.4 implementarea stivelor prin tipul tablou

Structura de dată abstractă care se definește pentru această implementarea va fi următoarea:

#define lungime_max 10

typdef int tipelem

typedef struct

{

int vârf;

tipelem elemente[lungime_max];

} Stiva;

Având în vedere faptul că avem de a face cu un caz particular de listă, implementările pentru listă sunt valabile și pentru stivă cu unele restricții la inserare și ștergere.

Pentru stiva implementată prin tablou, o introducere ar presupune mutarea tuturor elementelor cu o poziție spre spatele tabloului, pentru a elibera poziția primă în tablou, care va fi utilizată pentru inserarea noului element. O ștergere ar însemna mutarea tuturor elementelor începând cu poziția 2 , și continuând până la ultimul element, cu o poziție în față. Această implementare nu este însă foarte bună datorită mutărilor de elemente ce apar în număr mare în cadrul operațiilor de inserare și ștergere de elemente.

Pentru a rezolva această problemă, ne vom gândi că stiva este vidă dacă pointerul de stivă indică poziția de dincolo de dimensiunea maximă a tabloului ce conține elementele stivei. O inserare va presupune decrementarea poziției indicate de acest pointer, și inserarea noului nod pe poziția în care a ajuns pointerul, iar o ștergere ar presupune înaintarea pointerului de stivă cu o poziție.

O astfel de abordare duce la o eficiență sporită a lucrului cu stiva implementată prin tablou.

Pentru reprezentarea în memoria sistemului de calcul a unei stive implementate prin intermediul tipului tablou vom folosi o structură ce forma următoare:

struct stiva

{

int varf;

tipelement elemente[lungmax];

};

unde varf este o variabilă ce tine mereu poziția celui mai recent element introdus în listă.

Inițializarea stivei presupune, așa cum am mai spus, așezarea indicatorului de vârf al stivei pe poziția lungmax, unde lungmax e dimensiunea tabloului ce reține stiva. Pozițiile tabloului fiind numerotate de la 0 la lungmax-1, rezultă ca poziția lungmax va fi prima aflată înafara tabloului, deci o putem folosi pentru a ne sugera o stivă vidă.

void init(struct stiva &s)

{

s.varf=lungmax;

}

Testul de stivă vidă se va face prin compararea poziției ce ne indică vârful stivei, cu prima poziție aflată înafara stivei, adică, cu poziția lungmax.

int stvid(struct stiva s)

{

if(s.varf>=lungmax)

return 1;

else

return 0;

}

Vom avea totodata nevoie de o funcție ce returneze valoarea elementului din vârful stivei, pentru a nu fi obligați ca de fiecare dată când dorim aflarea acestei valori să fim nevoiți să extragem elementul din vârful stivei pentru a-i vedea valoarea și apoi să-l reinserăm. Din punct de vedere al implementării ne atrage atenția folosirea unui parametru suplimentar de eroare, parametru ce va fi transmis prin referință la apel, și care va fi setat pe 1 dacă avem o stivă vidă, deci nu avem un prim element, sau pe 0 în caz contrar.

tipelement varfst(struct stiva s, int &err)

{

err=0;

if(stvid(s))

{

err=1;

printf("\nstiva vida");

return -1;

}

else

return s.elemente[s.varf];

}

Pentru scoaterea unui element din stivă vom introduce o funcție ca cea de mai jos. Valoarea elementului scos poate fi întoarsă ca valoare de retur a funcției, sau poate fi menținută într-o variabilă transmisă ca parametru funcției, prin referință. Mai jos am optat pentru a doua variantă în scopul familiarizării cu transmiterea parametrilor funcțiilor C. Pentru eliminarea unui element, va fi setată variabila ce reține elementul extras pe valoarea elementului din vârful stivei, și va fi incrementat indicatorul de vîrf al stivei. Parametrul de eroare ne va indica dacă funcția s-a executat cu succes sau a eșuat din cauză ca stiva era deja vidă înaintea extragerii.

void extrage(struct stiva &s, tipelement &x, int &err)

{

err=0;

if(stvid(s))

{

err=1;

printf("\nstiva vida");

}

else

{

x=s.elemente[s.varf];

s.varf++;

}

}

Introducerea unui element în stivă presupune decrementarea indicatorului de vârf al stivei pentru a crea o poziție nouă în stivă, și introducerea noului element pe poziția nou creată. Eroarea va putea apărea de această dată dacă stiva e plină și nu mai e loc pentru elementul ce dorim sa-l inserăm, situație ce va fi indicată prin setarea corespunzătoare a parametrului err.

void introduce(struct stiva &s, tipelement x, int &err)

{

err=0;

if(s.varf==0)

{

err=1;

printf("stiva plina");

}

else

{

s.varf–;

s.elemente[s.varf]=x;

}

}

Cum implementăm o stivă?

Stiva este o structură de date abstractă, ce poate fi implementată în diferite moduri. De exemplu, putem implementa o stivă ca un vector în care reținem elementele stivei. Pentru ca acest vector să funcționeze ca o stivă, singurele operații permise sunt operațiile caracteristice stivei.

Pentru exemplificare, să prezentăm declarațiile necesare pentru implementarea unei stive cu elemente de tip int:

#define DimMax 100 //numarul maxim de elemente din stivatypedef int Stiva[DimMax];

//tipul Stiva implementat ca vector

Crearea unei stive vide

Pentru a crea o stivă vidă inițializăm vârful stivei cu -1 (vârful stivei indică întotdeauna poziția ultimului element introdus în stivă; elementele sunt memorate în vector începând cu poziția 0):

 vf=-1;

Inserarea unui element în stivă

Pentru a insera un element x în stiva S trebuie să verificăm în primul rând dacă „avem loc”, deci dacă stiva nu este plină. Dacă stiva este plină, inserarea nu se poate face, altfel vom mări vârful stivei i vom plasa la vârf noul element.

De exemplu, dacă dorim să inserăm elementul x = 3 în stiva din figura

Coada

COADA este o structură de date abstractă, pentru care operația de adăugare a unui element se execută la un capăt, în timp ce operația de extragere a unui element se realizează la celălalt capăt.

Singurul element din coadă la care avem acces direct este cel de la început.

Operații caracteristice

Singurele operații ce pot fi realizate cu o coadă sunt:

crearea unei cozi vide;

inserarea unui element în coadă;

extragerea unui element din coadă;

accesarea unui element.

Realizarea acestor operații asupra unei cozi presupune cunoașterea începutului cozii (să-l notăm Inc) și a sfârșitului acesteia (să-l notăm Sf).

Modul de funcționare a unei cozi este foarte ușor de intuit: toată lumea a „stat la coadă”, măcar o dată. Orice situație în care sunt mai multe cereri de acces la o resursă unică (de exemplu, mai mulți clienți și o singură vânzătoare; o singură pompă de benzină și mai multe mașini, un singur pod și mai multe capre, etc) necesită formarea unei „linii de așteptare”. Dacă nu apar alte priorități, cererile sunt satisfăcute în ordinea sosirii.

Datorită faptului că întotdeauna este extras („servit”) primul element din coadă, iar adăugarea oricărui nou element se face la sfârșit („la coadă”), coada este definită ca o structură de date care funcționează după principiul FIFO(First In First Out – Primul Intrat Primul Ieșit).

Terminologia diferă puțin față de cea pe care o utilizăm în cazul tipului stivă, de această dată nu vom mai avea noțiunea de vârf ci vom numi capătul unde se vor face inserări de elemente spatele cozii, iar capătul unde se fac ștergeri de elemente îl vom numi fața cozii.

Implementarea cozilor cu ajutorul tipului pointer

Orice implementare pentru liste este valabilă și în cazul cozilor. Pornind de la observația ca inserările se fac doar în spatele cozii, iar suprimările doar în fața cozii, introducerea de noduri va trebui să o optimizăm cumva, pentru a nu fi nevoie ca de fiecare dată când inserăm un nod să parcurgem întreaga coadă pentru a găsi sfârșitul cozii. Putem face o astfel de optimizare prin folosirea unui pointer care va memora mereu adresa la care se află ultimul element din coadă, acesta fiind utilizat alături de pointerul ce reține adresa primului element din coadă.

Structura de date corespunzătoare unui nod din coadă va fi de genul celei de mai jos, unde element este de un tip particular. Tipul folosit pentru membrul element poate fi orice tip standard sau implementat de utilizator.

struct nod

{

char element[30];

nod *urm;

};

Așa cum am mai menționat, pentru implementarea tipului coadă, vom avea nevoie de un pointer spre primul element al listei și de unul spre ultimul element al listei. Vom folosi în implementare o tehnică pe care nu am mai folosit-o până acum, este vorba de folosirea unui nod fictiv. Acesta este un nod al cărui câmp pentru informație nu mai este completat, el nu va fi luat în calcul ca și nod al cozii în executarea operațiilor de listare a informației nodurilor, de inserare, de suprimare, etc. Acest nod este folosit numai pentru ușurarea manipulării structurii de date de tip coadă.

Care este utilitatea unei cozi?

Utilitatea structurii de tip coadă reiese din modul său de funcționare – este necesară folosirea unei cozi atunci când informațiile trebuie prelucrate exact în ordinea în care „au sosit” și ele sunt reținute în coadă până când pot fi prelucrate. În informatică, cozile sunt utilizate frecvent.

De exemplu, să considerăm că avem o rețea de calculatoare și o singură imprimantă. Când utilizatorii rețelei vor da comenzi de tipărire, imprimanta nu poate răspunde tuturor comenzilor în același timp (imaginați-vă ce ar ieși!).

Prin urmare comenzile de tipărire primite sunt înregistrate într-o coadă (Print Queue – Coadă de Tipărire). Imprimanta va tipări documentele pe rând, în ordinea în care au fost înregistrate în coadă. Un alt exemplu: pentru a mări viteza de execuție, microprocesoarele Intel utilizează o coadă de instrucțiuni în care sunt memorate instrucțiunile care urmează a fi executate.

O altă categorie specială de liste în care elementele sunt inserate la un capăt ( spate) și sunt suprimate la celălalt capăt (față) sunt cozile. Acestea se mai numesc liste de tipul FIFO(first in first out), adică liste de tip primul venit primul servit. Operațiile care se execută asupra cozii sunt analoage cu cele executate asupra stivei, cu diferența că inserțiile se fac în spatele cozii și nu la începutul ei.

Ca și în cazul stivelor, orice implementare a listelor este valabilă și pentru cozi. Cozile pot fi implementate cu ajutorul tablourilor circulare.

În cazul implementării cu pointeri, pentru adăugarea unui element se va păstra un pointer la ultimul element. De asemenea, ca și la toate tipurile de liste, se va păstra și pointerul la primul element. În implementare se poate utiliza și un nod fictiv ca prim elemant al cozii, caz în care pointerul de început va ridica acest nod.

Tipurile de date care se utilizează în acest scop, presupunând elementele cozii de tip întreg vor fi:

typedef struct nod;

{

tipelem element;

struct nod *urm;

} Tnod;

Se poate astfel define o structură de tip coadă pentru care există doi pointeri indicând fața, respectiv spatele unei liste înălțate. Primul nod al cozii este unul fictiv în care câmpul element este ignorat, această convenție permițând manipularea mai simplă a cozii vide. În consecință, tipul coadă poate fi definit în modul următor:

typedef struct;

{

Tnod *fata, *spate;

} coada;

Pentru cozi, nu este foarte eficient reprezentarea cu ajutorul tablourilor folosită în cazul listelor. Pointerul la ultimul element al listei permite implementarea simplă, intr-un număr finit de pași a operației de adăugare. Execuția operației de ștergere presupune însă mutarea întregii cozi cu o poziție în tablou.

Pentru a depăși acest dezavantaj se poate folosi o structură de tablouri circulare (listă circulară) în care se pot aranja n=;ung_max noduri, x[0] …x[n-1] implicit într-un cerc, în care x[0] urmează după x[n-1].

Structura de acest tip este reprezentată schematic în Figura 4.5.

Figura 4.5. Implementarea cozilor cu ajutorul tablourilor circulare

Structura de tip coadă se definește în modul următor:

#define Lung_max 10

typedef int tipel;

typedef struct

{

tipel elemente[Lung_max];

int față, spate;

} coada;

Elementele cozii se găsesc în poziții consecutive, spatele cozii fiind undeva înaintea feței la parcurgerea cercului în sensul acelor de ceasornic. Înlănțuirea unui element în coadă presupune mișcarea cursorului c.spate cu o poziție în sensul acelor de ceasornic și introducerea elementului în această poziție, iar scoaterea presupune simpla mutare a cursorului c.față cu o poziție în sensul rotirii acelor de ceasornic.

În continuare se prezintă ca exemplu un program care calculează aria unui poligon folosind lista circulară dublu înlănțuită, conform Ref.[4] din bibliografie indicată. Coordonatele poligonului convex sunt conținute în ordine în fișierultext”poligon.in”. Pe prima linie a fișierului se află numărul n de vârfuri șipe următoarele n linii se află coordonatele poligonului. Lista dublu înlănțuită va conține poligonul în triunghiuri care au un vârf comun.

#include<iostream.h>

#include<conio.h>

#include<math.h>

#include<studio.h>

FILE *f;

struct nod

{

int x,y;

nod *urm, *prec;

}

nod *prim, *ultime;

void adaugare_sf(nod *&prim, nod*&ultimo, int xx, int yy)

{

nod *p, *q;

q=new nod;

if (q)

{

q->x=xx;

q->y=yy;

q->prec=ultim;

q->urm=NULL;

if (ultim)

ultim->urm=q;

else

prim=q;

ultim=q;

}

else

cout<<”spatiu insufficient”;

}

void creare(nod *&prim, nod *ultim)

{

int n,xx,yy;

f=fopen(“polygon.in”,”r”);

fscanf(f, “%d”, &n); //nr. de varfuri

for(int i=l;i<=n;i++)

{

(fscanf(f, “%d%d”, &xx, &yy));//citesc coordonatele varfurilor

adaugare_sf(prim,ultimo,xx,yy);//adaug coordinate varfurilor într-un nod din listă

}

prim->prec=ultim;

ultim->urm=prim;//transform lista in listă circulară

}

//funcția distanță calculează dintre două puncte (coordonatele acestor puncte sunt memorate în nodurile de adresă p,q)

float distanța (nod *p, nod *q)

{

float pp=(p->x-q->x)*(p->x-q>x)+(p->y-q->y)*(p->y-q->y);

return sqrt(pp);

}

//funcția arie calculează aria triunghiului cu un vârf memorat în nodul de adresă prim, altul în nodul de adresă p și al treilea în nodul de adresă p->urm

float arie(nod *p)

{

float a,b,c,sp;

a=distant (prim, p)

b=distanta(p, p->urm);

c=distanta(prim, p->urm);

sp=(a+b+c)/2;

return sqrt(sp*(sp-a)*(sp-b)*(sp-c));

}

void calcul(nod *prim)

{

float s=0;

nod *p=prim->urm;

while(p->urm!=prim)

{

s+=arie(p);

p=p->urm;

}

count<<”aria poligonului este”<<s<<endl;

}

void main()

{

clrscr();

creare(prim, ultim);

calcul(prim);

}

STRUCTURI ARBORESCENTE

ELEMENTE GENERALE

Structurile arborescente presupun relații de ratificare între noduri, asemănător configurației arborilor din natură.

Un arbore este o multime finită de n≥0 elemente denumite noduri sau vârfuri, de același fel, care, dacă nu este vidă a) un nod cu destinație specială numit rădăcina arborelui și b) celelalte noduri care sunt repartizate în m≥0 seturi disjuncte A1, A2,…., Am fiecare set A1 constituind la rândul lui un arbore. Astfel, recursivitatea reprezintă o caracterictică naturală a structurilor arborescente. Reprezentarea grafică schematică a unei structuri arborescent este dată în Figura 5.1.

Figura 5.1. reprezentarea grafică a structurii arborescente.

Nodul rădăcină (A în figura 5.1.) se consideră ca fiind de nivelul zero, nodurile B,C,D din figura vor fi de nivelul 1, s.a.m.d. Dacă numărul nivelurilor este finit atunci și arborele este finit, ăn caz contrar arboreal este infinit.

Astfel, arboreal este o structură ierarhică, fiecare nod fiind direct subordonat unui singur nod, excepție fiind rădăcina. Dacă un nod nu are nici un nod subordonat se numește frunză sau nod terminal. Dacă există un drum de la nodul x la nodul y, atunci nodul x se numește strămoș al lui y, iar nodul y se numește descendent al lui x. Numărul fiilor unui nod reprezintă gradul unui nod, un nod terminal având astfel gradul zero. Gradul maxim al nodurilor unui arbore se numește gradul arborelui. Nivelul maxim al nodurilor unui arbore se numește înălțimea arborelui. Astfel, arboreal din Figura 5.1. are înălțimea 2 și gradul 3.

Dacă ordinea relativă a subarborilor are imporanță, arboreal se numește arbore ordonat. De o importanță particulară sunt arborii ordonați de gradul 2, aceștia numindu-se arbori binari.

Exemple familiale de arbori sunt arborii genealogici (genealogia cu tatăl și mama unei persoane ca descendenți) sau o expresie aritmetică cu operatori binari (fiecare operator denotând un nod de ramificare, cu cei doi operatori ca subarbori).

TRAVERSAREA ARBORILOR

Una din activitățile fundamentale care se execută asupra unei structuri de arbore este traversarea acestuia. Ca și în cazul listelor liniare, traversarea arborelui înseamnă execuția unei anumite operații asupra tuturor nodurilor arborelui. În timpul traversării nodurilor sunt vizitate într-o anumită ordine, astfel încât ele pot fi considerate ca și când ar fi integrate într-o listă liniară (liniarizarea structurii de arbore).

Există trei moduri de liniarizare mai importante, numite „preordine”, „inordine” și „postordine”. Aceste moduri se definesc recursive după cum urmează:

– dacă arborele este Arb este vid, atunci ordonarea arborelui în preordine, inordine și postordine se reduce la lista vidă;

– dacă arborele este Arb este format dintr-un singur nod, atunci nodul însuși reprezintă traversarea arborelui în orice din cele trei noduri;

– pentru restul cazurilor putem considera ca exemplu arborele din Figura 5.1.

Traversarea în preordine presupune traversarea rădăcinii A urmată de traversarea în preordine a subarborelui B, apoi de traversarea în preordine a subarborelui C urmată de traversarea în preordine a subarborelui D. Secvența de parcurgere a arborelui din figura 5.1. va fi în acest caz A B C D E F G H I J K L M.

Traversarea în inordine presupune traversarea în inordine a subarborelui B, urmată de rădăcina A, urmată de parcurgerile în inordine a subarborilor C și D pentru exemplul considerat secvența de parcurgere va fi E B F G A H C I J K D L M.

Traversarea în postordine a arborelui exemplu constă în traversarea în postordine a subarborilor B, C, D, urmată de traversarea rădăcinii A. Astfel, secvența de parcurgere va fi acest caz E F G B H I J C K L M D A.

REPREZENTAREA STRUCTURILOR ARBORESCENTE

Pentru reprezentarea pe suport a structurilor arboreștene se folosește alocarea înlănțuită.

O metodă de reprezentare este reprezentarea prin pointeri multipli. Fiecare nod conține pe lângă informația propriu-zisă, n+1 câmpuri l0, l1,…ln, unde n este gradul nodului, l0 conține gradul nodului, iar l1 (1≤i≤n) conțin adresele succesorilor imediați ai nodului. Dacă unul din subarborii unui nod lipsește, deci dacă subarborele respective este vid, pointerul corespunzător va conține referința nulă (NULL).

Datorită faptului că în fiecare nod trebuie să rezolvăm loc pentru maxim de referințe către fii (care poate să nu fie cunoscut dinainte), risipa de memorie este uneori prea mare. Aceste neajunsuri pot fi înlăturate, de exemplu păstrând lista referințelor către fii unui nod nu într-un vector ci într-o listă înlănțuită.

Structura unui nod se va descrie în limbajul C astfel (max este o constantă care reprezintă gradul arborelui)

typedef struct nod

{

int nr_fii;

struct nod *ref_fii[max];

} Tnod;

typedef Tnod*ref;

ref rădăcina;

În cazul arborilor binari, întrucât gradul arborilor este 2, se vor reprezenta pentru fiecare nod lângă informația propriu-zisă numai referințele la cei doi subarbori(st=referința la subarborele stâng, respectiv dr=referința la subarborele drept). Astfel, structura unui arbore binar se va descrie astfel:

typedef struct nod

{

struct nod *st, *dr;

} Tnod;

typedef Tnod *ref;

ref rădăcina;

EXPERIMENT DEMONSTRATIV

În această secțiune se prezintă situații experimentale ipotetice (experimente imaginare) în care se evidențiază prelucrerea datelor folosind tablouri, pointeri și structuri cu autoreferire.

Experimentele se referă la prelucrarea datelor experimentale rezultate din măsurători asupra celulelor solare. Celulele solare sunt dispozitive experimentale care transformă energia luminoasă în energie electrică. Astfel, la iluminarea unei celule solare are loc producerea unui anumit curent electric (sau tensiune electrică) care este măsurat, înregistrat și prelucrat. În funcție de tipul experimentului și a măsurătorii, se propune prelucrarea datelor înregistrate folosind diferite structuri de date. Astfel, dacă numărul datelor înregistrate cunoaște la ănceputul proiectării programului de prelucrare a datelor, se vor folosi tablouri. Dacă numărul datelor înregistrate se cunoaște la începutul execușiei programului de prelucrare, se va face uz de variabile pointer, iar dacă numărul măsurătorilor este cunoscut abia după efectuarea ultimei observații se vor folosi structuri cu auto-referire(liste).

Situația experimentală ipotetică pentru evidențierea utilității prelucrărilor de date folosind tablouri este prezentată schematic în Figura 6.1. celula solară CS este iluminată de sursa de lumină L diapozitivul T reglează temperatura efectuăriiexperimentului la valoarea dorită. Prin iluminare celula solară va furniza tensiunea electrică V. Se urmărește măsurarea, înregistrarea și reprezentarea grafică a tensiunii electrice furnizată de celula solară de diferite valori ale temperaturii, precum și determinarea coeficientului de variație a tensiunii V în funcție de temperatura T presupunând o dependență liniară. Măsurătorile se efectuează la temperaturi care variază de la 10 la 1000C, modificând temperatura din grad în grad.

Figura 6.1. Experiment imaginar demonstrativ pentru evidențierea utilității

prelucrărilor de date folosind tablouri

în fișierul de măsurători se înregistrează valorile tensiunii electrice de celulă solară, împreună cu temperatura la care s-a obținut fiecare valoare a tensiunii. Se poate remarca faptul că numărul de măsurători (100) pentru acest tip de experiment este fixat înainte de îneperea efectuării experimentului, punându-se astfel folosi tablouri. Programul va analiza datele din fișierul text de măsurători și va furniza rezultatele, conform diagramei schematice din Figura 6.1.

Programul va avea următoarea structură, ilustrată mai jos în versiune schematică.

int i;

double coef;

double T[100], V[100]

fp=fopen(“fisier_masuratori.txt”, “r”);

for(i=l; i<=100; i++)

fscanf(fp, “%f, %f”, T[i], V[i]);

/* se citesc valorile T[i], V[i] masurate*/

Reprezintă grafic V ca funcție de T;

determină coef=sum{(T[i]-Tm)x(V[i]-Vm)}/Sum{T[i]-Tm) 2};

Programul de analiză a datelor va memora valorile temperaturii și ale tensiunii în câte un vector unidimensional de dimensiune 100. După reprezentarea grafică, se va calcula coeficienzul de variație a tensiunii cu temperatura ca fiind panta dreptei obținute prin regresie liniară a datelor. Se va folosi expresia:

coef=∑[(T-Tm)(V-Vm)]/∑[(T-Tm)2], unde Tm și Vm sunt valori medii ale vectorilor T și V, iar ∑[x] desemnează suma tuturor valorilor vectorului [x].

Al doilea experiment imaginar are la bază aceeasi situație din Figura 6.1. În acest caz însă, numărul de măsurători este precizat abia la începutul execuției programului, algoritmul trebuind săpermită determinarea coeficientului de variație pentru un număr N neapreciat de perechi (T,V). Numărul N va fi menționat la începutul fișierului text de măsurători. În acest caz, prelucrarea datelor va fi realizată folosind alocarea dimanică de memorie, algoritmul fiind ilustrat mai jos în versiune schematică.

int N,i;

double coef;

double *T, *V;

fp=fopen(“fisier_masuratori.txt”, “r”);

fscanf(fp, ”%d”, N); /*se citeste numarul N */

T=(double *)malloc (N*sizeof(double));

V=(double *)malloc (N*sizeof(double));

fscanf(fp, ”%f, %f”, &T[i], &V[i]);

/* se citesc valorile T[i], V[i] masurate */

reprezinta grafic V ca functie de T;

determina coef=sum{(T[i]-Tm)x(V[i]-Vm)}/Sum{T[i]-Tm) 2};

Al treilea experiment imaginar este reprezentat în Figura 6.2. în acestă situație se va evidenția necesitatea folosirii structurilor cu autoreferire în cazul prelucrărilor de date experimentale.

Figura 6.2. Experiment imaginar demonstrativ pentru evidențierea necesității

prelucrărilor de date folosind structuri cu autoreferire

În experimentuldin Figura 6.2. celula solară considerată este expusă radiației solare. Temperatura se consideră de această dată constantă pe tot parcursul desfășurării experimentului. Radiația solară va avea o intensitate variabilă în timpul zilei calendaristice sau în timpul unui an calendaristic (iluminar diferită în anotimpuri diferite). Ca urmare, tensiunea electrică furnizată de celula solară va depinde de timp, în funcție de momentul din zi sau de momentul de timp din cadrul anului calendaristic. Cu ajutorul unui cronometru (care poate fi operat manual sau în mod automat) se poate înregistra momentul de timp în care are loc măsurarea tensiunii. În cadrul experimentului se urmărește monitorizarea tensiunii în funcție de timp la momente de timp oarecare și pe durată nedeterminată, precum și calcularea tensiunii medii furnizate de celula de la începerea monitorizării.

Se observă că în cazul de față nu sunt cunoscute numărul de observații atunci când este efectuată prelucrarea valorilor numerice. Aceasta deoarece momentele de timp în care se înregistrează valori nu neapărat periodice, precum și din cauza faptului că durata monitorizării este nedeterminată. Astfel un experiment poate dura o zi calendaristicăsau un an calendaristic și poate conține de exemplu 25 sau 10000 de înregistrări. În acest caz potrivit ca programul să opereze pe baza structurilor cu autoreferire (de exemplu liste liniare simplu înlănțuite în cazul de față).

Structura programului este ilustrată mai jos în versiune pseudocod.

declară structura de nod al listei;

/* câmpul info va conține variabilele reale timp, V*/

definește pointer la nodurile listei;

reține adresa primului nod al listei;

while<experiment în derulare>

if<inregistrare noua>

inserează măsurarea în listă;

reprezintă grafic V în funcție de timp;

calculează valoarea medie Vm;

end if;

end while;

BIBLIOGRAFIE:

Paraschiva Popovici – Structuri de date liniare și arborescente în C,

Editura Eurostampa, Timișoara, 2006

Daniela Oprescu, Liana Bejan Ienulescu, Viorica Pătrașcu,

Informatică, Manual pentru clasa a XI-a, editura Niculescu, București, 2002

Victoria Iordan – Algoritmi și programare în C,

Editura Eurostampa, Timișoara, 2006

Dorin Mânz, Ioana Stan, Sanda Junea, Adriana Simulescu, Felicia Neacșu, Maria Scripca, Ovidiu Roșu, Cristina Bărbieru, Alina Mihail, Cristina Carnat

Informatică. Culegere de probleme rezolvate și propuse, Editura Mirton, Timișoara 2003