Structuri Dinamice de Date [PDF]

Zitiervorschau

Tema 1: Structuri dinamice de date. Variabile dinamice. Tipul referinta. Structuri de date. Liste unidirectionale. Variabilele se impart in 2 categorii: statice si dinamice. Variabilele statice sunt cele cu care am lucrat pina in present, structura, tipul si adresa de memorie nu se pot modifica in timpul executiei. Aceste variabile sunt referite prin numele lor, fiecarui nume asociindu-i-se o adresa fizica de memorie. Unei variabile statice I se poate modifica doar valoarea , nu si adresa din memoria interna. Variabilele care sunt create si distruse in timpul executiei programului se numesc variabile dinamice. Pentru variabileledinamice poate fi modificat volumul de memorie rezervat. Accesul la variabilele dinamice nu se face directci prin intermediul unui tip mediator numit- tip referinta. De obicei tipul referinta se declara in mod urmator: I type nume_nou=^tip_data;

sau II var nume_var: ^tip_data;

var nume:nume_nou; unde tip_data- este tip de data simplu sau structurat. adresa.

^- se citeste

Ex. 1) Var x:^ integer; {x-var ce contine o adresa catre o zona in care se va memora un intreg} 2) var a: ^char; {^char,^integer- tip de referinta anonim} b:^integer; c:^char; d:^real; 3) type AdresaReal=^real; {tip de date referinta AdresaReal} Var i:AdresaReal; Multimea de valori a unui tip de date referinta este formata din adrese. Fiecare adresa identifica o variabila dinamica ce apartine tipului de baza. Aceasta multime de adrese contine o valoare speciala notate nil(zero) care nu identifica nici o variabila. Fie ca avem declaratiile: Type AdresaInteger= ^integer; AdresaChar= ^char; Var i:AdresaInteger; r: ^real; c:AdresaChar; Variabilele I,r,c sunt variabile de tip referinta. Asupra valorilor tipului de date referinta pot fi effectuate operatiile: =, < >. Valorile de tip referinta nu pot fi citite de la tastaturasi afisate pe ecran. Pentru a putea lucre cu variabilele dinamice acestea trebuie create print-un apel de forma: New(p) unde p- variabila de tip referinta Aceasta procedura(new) rezerva memorie pentru variailele nou create si intoarce adresa zonei respective prin variabila p. Apoi variabila dinamica va fi accesata prin dereperare(numele variabilei de tip referinta p este urmat de semnul ^)

Ex. New(i); i^:=1; - se creaza var dinamica de tip integer,var i:=valoarea1. New(c); c^:=’*’; - se creaza var dinamica de tip char, var C:=semnul *. Distrugerea unei variabile dinamice si eliberarea zonei de memorie se realizeaza cu procedura predefinita dispose, printr-un apel de forma: dispose(p); p – var de tip referinta Ex. dispose(i); dispose(c); Asupra variabilelor dinamice se pot efectua toate operatiile admise de tipul de baza. Ex.1 Folosind alocarea dinamica a memorie, elaborate un program Pascal care va afisa suma a 2 nr. Program Pdinamic; type adresa=^integer; var a,b,c:adresa; begin new(a); new(b);new(c); readln(a^); readln(b^); c^:=a^+b^; writeln(c^); dispose(a); dispose(b); dispose(c); readln; end. Ex2. Comentati programul: Program P119; var r,s:^real; begin r^:=1; s^:=2; writeln(r^=',r^, ' s^=', s^); readln; end. Ex.3 Elaborati un program in care se creaza doua variabile dinamicede tipul sir de caractere. Atribuiti valori variabilelor create si afisati la ecran rezultatul concatenarii sirurilor respective.

Structuri de date

O structura de date este formata din date propriu zise si relatiile dintre ele. In functie de cum e organizata o structura de date poate fi implicita sau explicita. Structurile implicite sunt structurile standarte oferite de Pascal: tablouri,siruri de caractere ,articolele,fisierele si multimile. Relatiile dintre componentele acestor structuri sunt predefinite si nu pot fi modificate. Acestea reprezinta structure statice de date. Acest tip de structure pot fi folosite pentru a rezolva un sir limitat de probleme. Sunt anumite cazuri cind relatiile dintre componente pot devein destul de complexe. Ex. Sirul de asteptare la o casa de bilete. Relatiile dintre personae se modifica: cineva pleaca cu bilet, cineva se alipeste la rind , cineva pleaca fara sa procure bilet. Aici apare necesitatea ca relatiile dintre componentele structurii sa fie specificate explicit. Acest effect se poate obtine atasind fiecarei componente informative ce caracterizeaza relatiile acesteia fata de alte componente a structurii. Aceasta informative e numita informative de atructura si este reprezentata prin variabila tip referinta. Structurile de date componentele carora sunt create si apoi distruse se numesc structure dinamice de date. Cele mai frecvent utilizate structure dinamice de date sunt: a) Liste unidirectionale b) Liste bidirectionale c) Stive d) Cozi e) Arbori f) Etc

Liste unidirectionale Listele unidirectionale sunt structure dinamice explicite de date formate din cellule. O celula reprezinta o variabila dinamica de tip record ce contine o variabila dinamica de tip record ce contine 2 cimpuri principale: cimpul date si cimpul de legatura. Cimpul de date contine informatia de prelucrat a celulei. Cimpul de legatura ofera indicatorul de adresa corespunzator celulei la care se poate ajunge din celula curenta.