Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Structuri liniare

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Conversii definite de programator
Functii pentru prelucrarea sirurilor (fisierul antet string
Tipul int
Initializarea modului grafic
Elemente de baza ale limbajului C/C++
Nume de variabile
Verificarea existentei elementelor sortate crescator din lista
METODE DE ELABORARE A ALGORITMILOR. BACKTRACKING.
Instructiunea while
Stergerea unei ferestre

TERMENI importanti pentru acest document

Structuri liniare




Definitia 3.4

Se numeste lista o secventa finita L = (l1, l2, , ln) de elemente numite componente, secventa care satisface proprietatile:

componentele pot fi date elementare sau structuri de date;

componentele pot fi de tipuri diferite.

Listele au fost introduse din necesitatea realizarii unor structuri de date dinamice, adica structura lor se poate modifica in cursul procesului de calcul.

Definitia 3.5

Se numeste lista liniara o lista L = (l1, l2, , ln) care satisface proprietatile:

exista    o relatie de ordine intre elementele listei L, astfel incat orice element li are predecesor pe li-1, i = 2, , n si succesor pe li , i = 1, , n-1;

elementul l1 nu are predecesor si este numit element initial al listei;

elementul ln nu are succesor si este numit element terminal al listei.

Pentru a indica predecesorul sau succesorul unui element al listei liniare se foloseste un indicator numit pointer (care reprezinta o adresa).

Definitia 3.6

Se numeste lista liniara simpla o lista liniara L = (l1, l2, , ln) in care fiecare element li este dublet ordonat de forma (di, pi) , unde di este o data elementara sau o structura de date, iar pi este un pointer care indica succesorul elementului li din lista.

Observatia 3.1

In cazul elementului terminal ln al listei L = (l1, l2, , ln), pointerul pn     are o valoare speciala.

Parcurgerea unei liste liniare simple L = (l1, l2, , ln) se poate face intr-un singur sens de la elementul initial l1 catre elementul terminal ln. De aceea o astfel de lista se mai numeste lista liniara asimetrica.

Pentru reprezentarea grafica a unei liste liniare simple L = ((d1, p1), , (dn, pn)) se poate folosi un digraf (graf orientat) G = (N, A), N = , A = , pi = (di, di

Exemplul 3.2

Lista L = ((d1, p1), (d2, p2), (d3, p3), (d4, p4), (d5, p5)) este reprezentata grafic prin digraful din figura 3.1

Figura 3.1

Definitia 3.7

Se numeste lista liniara dublu inlantuita o lista L = (l1, l2, , ln) in care fiecare element li este un triplet ordonat de forma (di, pi , pi) unde di este o data elementara sau o structura de date, pi este un pointer spre predecesor si pi este un pointer spre succesor.

Observatia 3.2

In cazul elementului initial l1 si al elementului terminal ln ale listei liniare dublu inlantuite L = (l1, l2, , ln) pointerul p1 si respectiv pointerul pn au valori speciale;

Parcurgerea unei liste liniare dublu inlantuita se poate face in ambele sensuri. De aceea o astfel de lista se mai numeste lista liniara simetrica.

Pentru reprezentarea grafica a unei liste liniare dublu inlantuita L = ((d1, p1 , p1), , (dn, pn , pn)) se poate folosi un digraf (graf orientat) G = (N, A), N = , A = , pi = (di, di-1), pi = (di, di

Exemplul 3.3

Lista L = ((d1, p1 , p1), , (d5, p5 , p5)) este reprezentata grafic prin digraful din figura 3.2.

Figura 3.2

Definitia 3.8

Se numeste lista liniara circulara o lista liniara L = (l1, l2, , ln) in care elementul initial l1 este succesorul elementului terminal ln.

Observatia 3.3

O lista liniara circulara poate fi simpla sau dublu inlantuita dupa cum elementele listei sunt dublete sau triplete, adica contin un pointer sau doi pointeri.

Memorarea listelor liniare se poate face in mai multe moduri, in continuare prezentandu-se doua dintre ele:

alocarea secventiala;

alocarea inlantuita.

Alocarea secventiala consta in a memora elementele listei in locatii succesive de memorie, conform ordinii acestor elemente in lista; in acelasi timp se memoreaza adresa de baza (adresa primului element al listei). Pointerii nu se reprezinta, iar ordinea logica a elementelor in lista este identica cu ordinea fizica pe suport. In acest caz, in general, elementele listei sunt memorate intr-un vector, adresa de baza fiind adresa primului element al vectorului.

Alocarea inlantuita consta in a memora fiecare element al listei intr-o locatie de memorie. Fiecare locatie are doua sau trei campuri, un camp pentru data si unul sau doua campuri pentru pointeri dupa cum lista este simplu sau dublu inlantuita. Trebuie memorata si adresa de baza. Deci, in acest caz pointerii se reprezinta efectiv, ei fiind adresele locatiilor unde se afla predecesorii sau succesorii elementelor. Astfel se asigura o independenta a ordinii logice a elementelor in lista in raport cu ordinea fizica pe suport si, de aceea elementele listei se pot memora in diverse zone de memorie.

Alocarea inlantuita cere mai multa memorie decat alocarea secventiala, dar are avantajul ca elimina necesitatea deplasarii de elemente pentru operatiile de introducere si de extragere din lista.

Asupra unei liste de date se pot efectua o multime de operatii care se refera la datele elementelor sau la structura. Aceste operatii sunt:

- creare(L) care consta in memorarea listei L in forma initiala;



- card(L) care consta in determinarea numarului elementelor listei L;

- sortare(L) care consta in ordonarea elementelor listei L dupa un criteriu;

- suprimare(L) care consta in stergerea listei L de pe suport;

- introducere(L, l) care consta in adaugarea la lista L a elementului l;

- consultare(L, l) care consta in accesul in lista L la elementul l;

- extragere(L, l) care consta in stergerea din lista L a elementului l;

- actualizare(L, l) care consta in actualizarea in lista L a valorii elementului l;

- inserare(L, l) care consta in adaugarea la lista L a elementului l intr-un anumit loc din lista;

- descompunere(L; L1, , Lm) care consta in descompunerea listei L in listele L1, , Lm;

- concatenare(L1, , Lm; L) care consta in obtinerea listei L din concatenarea listelor L1, , Lm;

- salvare(L1, L2) care consta in copierea listei L1 in lista L2, in general, pe un alt suport.

In cazul in care se impun anumite restrictii asupra operatiilor de introducere si extragere a elementelor unei liste liniare, se obtin cateva tipuri particulare de liste folosite frecvent in practica.

Definitia 3.9

Se numeste stiva o lista liniara cu proprietatea ca operatiile de introducere si stergere din lista se fac la un singur capat al listei numit varful stivei.

Observatia 3.4

O stiva mai poarta numele de stack, pila, lista LIFO (Last-In, First-Out) sau lista push-down.

Definitie 3.10

Se numeste coada o lista liniara cu proprietatea ca operatia de introducere se efectueaza la un capat al listei numit baza cozii si operatia de extragere se efectueaza la celalalt capat al listei numit varful cozii.

Observatia 3.5

O coada mai poarta si numele de queue, sir de asteptare sau lista FIFO (First-In, First-Out).

In reprezentarea secventiala, elementele stivei vor fi memorate intr-un vector s cu n componente, n fiind capacitatea maxima a stivei. O stiva fara nici un element se numeste stiva vida. O stiva cu n elemente se numeste stiva plina.

Fie k numarul efectiv de elemente din stiva; ca urmare elementul sk apare in varful stivei. Operatia de introducere in stiva se realizeaza asa cum se arata in procedura SIN:

PROCEDURE SIN(s, n, k, x);

ARRAY s(n);

IF k ≥ n THEN

WRITE ’STIVA PLINA’;

STOP;

ENDIF

k := k + 1;

s(k) := x;

RETURN

END.

Operatia de extragere din stiva se realizeaza asa cum se arata in procedura SOUT:

PROCEDURE SOUT(s,n,k,x);

ARRAY s(n);

IF k ≤ 0 THEN

WRITE ’STIVA VIDA’;

STOP;

ENDIF

x := s(k);

k := k – 1;

RETURN

END.

In reprezentarea inlantuita, adresa de baza va fi adresa varfului stivei, legaturile mergand de la ultimul spre primul element al stivei.

In alocarea secventiala vom folosi pentru o coada un vector c cu n componente in care, daca elementele cozii sunt memorate in ci+1, ci+2, , ck (unde ci+1 este varful cozii, iar ck este baza cozii), atunci p = i si u = k. Introducerea variabilelor p si u este necesara pentru a putea testa daca o coada este vida, caz in care p = u. Scoaterea, respectiv introducerea unui element in coada conduce la marirea lui p, respectiv u cu o unitate. Dar operatiile de introducere si extragere din coada produc o deplasare spre dreapta a elementelor. Astfel se poate ajunge la situatia p = u = n, cand coada esta vida, dar nu putem introduce nici un element in coada. Pentru a elimina acest neajuns se va considera ca lista coada este o lista circulara, adica dupa cn urmeaza c1. In acest caz relatia p = u este valabila atat pentru o coada vida cat si pentru una plina. Pentru a deosebi cele coua cazuri se poate folosi una din metodele:

introducerea unei variabile b care sa ia valoarea 0 in cazul unei cozi vide si 1 in rest;

utilizarea a n–1 componente ale vectorului c; in aceasta situatie coada vida este identificata prin p = u, iar coada plina prin u + 1 = p (mod n).

Convenim ca la initializarea cozii punem p := n, u := n.

Operatia de introducere in coada se realizeaza asa cum se arata in procedura CIN:

PROCEDURE CIN(c, n, p, u, x);

ARRAY c(n);

u := u + 1;

IF u > n THEN

u := 1;

ENDIF

IF p = u THEN

WRITE ’COADA PLINA’;

STOP;

ENDIF

c(u) := x;

RETURN

END.

Operatia de extragere din coada se realizeaza asa cum se arata in procedura COUT:

PROCEDURE COUT(c, n, p, u, x);

ARRAY c(n);

IF p = u THEN

WRITE ’COADA VIDA’;

STOP;

ENDIF;

IF p = n THEN

p := 0;

ENDIF

p := p + 1;

x := c(p);

RETURN

END.

Reprezentarea inlantuita a cozilor se realizeaza analog ca pentru stive, cu deosebirea ca se memoreaza doua adrese p si u pentru varful, respectiv baza cozii.






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 775
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2021 . All rights reserved

Distribuie URL

Adauga cod HTML in site