curs02.txt

来自「STRUCTURI DE DATE SI ALGORITMI」· 文本 代码 · 共 182 行

			       Curs 2

Structuri de date elementare

O structura de date presupune un mod de organizare a datelor (宯 tablouri,
structuri, etc), si definirea operatiilor acceptate. Deci, o structura de date
reprezinta o colectie organizata de date si un set de operatii definite.
Si notiunea de tip de date presupune:
		 |--- reprezentare
		 |--- operatii acceptate

De exemplu, pentru tipul int:
		 |--- reprezentare: pe doi octeti: cod complementar
		 |---operatii acceptate: +, -, *, /, &, |, etc.

Daca pentru un tip de date nu intereseaza reprezentarea, ci doar operatiile
acceptate,宯seamna ca tipul de date este abstract.

Structuri de date
  Tablouri
Tabloul este o colectie de date 宯 care fiecare element poate fi identificat
pe baza unui index, colectia asigur僴d timp de acces constant pentru fiecare
element. Prin reprezentarea tabloului se intelege plasarea elementelor 宯
locatii succesive de memorie:


Locatiile de memorie pot fi numerotate, put僴d accesa direct orice element.
Timpul de accesare al elementului numar, de exemplu, fiind acelasi cu timpul
de accesare al elementului n.

  Liste
O lista este o multime de obiecte, numite atomi, pentru care este definita o
ordine:

Operatiile principale care se pot se face 宯 cadrul listei:
  inserare: introducerea unui nou element 宯tr-o anumita pozitie;
  stergere: scoaterea unui element dintr-o anumita pozitie;
  consultare: accesul asupra fiecarui element din lista;
  parcurgere.
 Tipuri speciale de liste

   Stive
O stiva este o lista 宯 care operatiile de inserare, stergere si consultare se
efectueaza asupra unui capat al listei. Stiva se poate asemana cu un recipient
宯 care se pun si se pot scoate diferite obiecte. Operatia care pune obiectele
宯 stiva se numeste push, iar cea care scoate obiecte din stiva se numeste pop.
Capatul accesibil pentru stiva se numeste v價ful stivei:
 Asadar:
  push  insereaza un element 宯 v價ful stivei;
  pop  sterge un element din v價ful stivei;
  top  consulta (citeste) elementul din v價ful stivei;
  top(S)  citeste v價ful stivei.

 Cozi
O coada este o lista 宯 care inserarea se face la un capat (la sf價sit),
iar stergerea se face de la celalalt capat al cozii (de la 宯ceput). Partea
din fata a cozii (a primului element) se numeste front, iar partea din spate
(a ultimului element) se numeste end.
 Operatia de inserare 宯 coada  add (put)
 Operatia de stergere din coada  del (get)

 Implementari de liste
O lista poate fi realizata ca:  lista ordonata sau
                                lista 宯lantuita
Lista ordonata tine cont de o ordine a pozitiilor elementelor listei, nu de
continutul elementelor.
 Inserarea 宯tr-o lista de forma:

se face cu deplasare de o pozitie la st僴ga din punctul 宯 care dorim sa
inseram (pentru a face acest loc noului element).
Deplasarea se face 宯spre zona de memorie libera (cea hasurata)  presupunem
ca dorim sa inseram pe a 宯 pozitia i):

Presupun僴d acum hasurat corpul de elemente din lista si nehasurata zona de
memorie libera, inserarea s-ar putea figura astfel:

Stergerea: deplasarea cu o pozitie la st僴ga din acel punct.

  Liste 宯lantuite
Intr-o lista 宯lantuita, ordinea din memorie nu mai corespunde cu ordinea din
lista. Fiecare element al listei 宯lantuite va avea urmatoarea structura:
(a(i) , succesor(a(i)))
unde a(i) este atomul listei 宯lantuite, iar informatia succesor(a(i)) ne
permite sa identificam un nou element de lista 宯lantuita. Ordinea din memorie
a elementelor listei nu conteaza. Informatia care indica primul element al
listei se numeste "capul" listei. Informatiei succesor(a(i)) i se potriveste
notiunea de pointer (identificator), pointer-ul fiind o variabila care
pastreaza o adresa din memorie. El indica pozitia elementului urmator. C僴d
informatiile de 宯lantuire sunt pointeri, putem utiliza urmatoarea
reprezentare:


Capul de lista este un pointer separat care duce la primul element din lista,
iar 0 este pointer-ul nul (NULL) cu valoare zero. La implementarea listei
宯lantuite concentrarea se face la fluxul instructiunilor, nu la declaratiile
de variabile.

In programe vom utiliza urmatoarele notatii:
 x  adresa unui element din lista, deci un pointer;
 data(x)  atomul memorat 宯 elementul de lista indicat de x;
 link(x)  informatia de legatura memorata 宯 elementul de lista indicat de x,
          adica adresa elementului urmator;
 y = get_sp()  y (de acelasi tip cu x) primeste adresa unei zone de memorie
             宯 care se poate memora un element din lista (get space sau
             alocare de memorie c僴d este vorba de pointer);
 ret_sp(x)  elibereza memoria ocupata de elementul de lista indicat de x (din
             momentul respectiv	acolo se poate memora altceva).

Un element de lista va fi o astfel de structura:

 struct Element {
             Atom data;
             Element* link;
                };
Se va scrie:
 tipul lui x ---------------- Element* x
 data(x) ---------------- x  data
 link(x) ---------------- x  link
 y = get_sp() ---------------- y = new Element
 ret_sp() ---------------- delete x

Deoarece lucram cu conceptul de lista vom face declaratia :
 typedef Element* Lista;
Un pointer la un element de lista considerat aproximeaza lista ce porneste cu
elementul indicat.

Operatii primitive pentru liste 宯lantuite

1.Inserarea
Inserarea se face:  宯 fata, sau
宯 interior (la mijloc ori la sf價sit)
a) Inserarea 宯 fata

1 - Prima atribuire: link(x) = l
2 - A doua atribuire: l = x 

Observatie: daca lista este vida, l are valoarea 0 (capatul listei) iar 
atribuirile de mai sus ram僴 valabile:


b) Inserarea la mijloc

Analog pentru inserarea la sf價sit.
1 - Prima atribuire: link(x) = link(y)
2 - A doua atribuire: link(y) = x

2.a)Stergerea (stergerea din fata):

1 - Prima atribuire: p = l
2 - A doua atribuire: l = link(l)
3 - ret_sp(p)
Sau, stergerea din fata s-ar mai putea reprezenta astfel:
Situatia initiala:

Situatia finala:

(1) p = cap;
(2) cap = cap  link;
    delete p ;                // Elibereaza zona de memorie

Elementul care a fost izolat de lista trebuie sa fie procesat 宯 continuare,
cel putin pentru a fi eliberata zona de memorie pe care o ocupa, de aceea
adresa lui trebuie salvata (sa zicem 宯 variabila pointer p).
2.b)Stergerea de la mijloc sau de la sf價sit

Varibila q va indica elementul din fata celui care va fi sters.

Situatia initiala:

Situatia finala:

(1) p = q->link;
(2) q-> link = p->link;     // sau q->link = q->link->link;
    delete p;

Observatii:
Atunci c僴d q indica penultimul element dintr-o lista, atribuirile de mai sus
functioneaza corect si sterg ultimul element din lista.
Nu se poate face stergerea elementului indicat de q fara parcurgerea listei de
la capat.