3-StructDate - C - Liste

7/24/2019 3-StructDate - C - Liste

http://slidepdf.com/reader/full/3-structdate-c-liste 1/61

Structuri de Date

Elementare



•avem de reprezentat multimi (fnite, de date omogene) –statice - componenta nu se schimba in

timp

–dinamice - componenta se schimba intimp

•multimi … pe care acem diverseoperatii•… in scopul rezolvarii unorprobleme



• Traversarea –operatia care acceseaza fecare element al

structurii, o singura data, in vederea procesarii(vizitarea elementului)

•autarea –se cauta un element cu cheie data in structura –cu sau fara succes –consta dintr-o traversare - eventual incompleta

a structurii, in care vizitarea revine la

comparatia cu elementul cautat –problema cheilor multiple - gasirea primei

aparitii, a tuturor aparitiilor

!peratii de baza



•"nserarea –adaugarea unui nou element structurii, cu

pastrarea tipului structurii

•Stergerea –e#tragerea unui element al structurii

(eventual in vederea unei procesari), cupastrarea tipului structurii pe elementeleramase

!peratii de baza (cont$)

"nserarea si Stergerea - reprezentarea multimilor cucaracter dinamic

costuri mici



!peratii (cont$)

•ombinare (merge) –din doua structuri de acelasi tip se

produce o alta structura, de acelasi tip,ce contine reuniunea elementelor

structurilor de intrare• e#% interclasarea a doua str$ liniare

ordonate

•Sortarea –ordonarea totala a elementelor

• sortarea multimilor statice• sortarea multimilor dinamice



•"nitializarea structurii cu structuravida•rearea - prin inserari repetate

• Test pt structura vida

!peratii &au#iliare'(cont$)

() iniţializarea structurii cu structura vid

(*) un ciclu repetitiv (de lungime variabil)

(a) se ia c+te un element dintr-un fier de intrare

(b) pentru fecare asemenea element se apeleaz o procedur ce

implementeaz opera.ia de inserare$



lase principale de structuri

•/ineare

•0elineare

• arborescente• grauri



Structuri /ineare

•"n alocare• statica - vectori

• dinamica - liste inlantuite

•!peratii de i1o (inserari1stergeri)

• ara restrictii i1o

• cu restrictii la i1o (stive si cozi)



Structuri lineare in alocarestatica

• Traversare

•"nserare

•Stergere

•autare



Traversarea(unei str$ liniare in alocare statica)

void Traversare(int A[], int n){ int k;

k = 1; // iniţializarea indicelui entru traversare!"ile (k #= n) // test entru nede$%irea structurii{

// viziteaz$ A[k];

k&&; //trece' la co'onenta ur'$toare



"nserarea (intr-o str$ liniara in alocare

statica) void nsert(int A[], int n, int k, int *le')

{ // insereaz$ +n structura liniar$ A[], e oziţia k, valoarea lui *le'int i;

// 'ut$ e rnd ele'entele de la A[n] la A[k] cte o locaţie la dreatai = n;!"ile (i -= k)

{ A[i&1] = A[i];i..;

// inserarea roriu.zis$ A[k] = *le';// cre%te di'ensiunea structuriin&&;



Stergerea (dintr-o str$ liniara in alocare statica)

void elete(int A[], int n, int k, int 0){ // etra2e +n 0 valoarea A[k] %i re3ace vectorul

int i;// etra2erea roriu.zis$

0 = A[k];// re3acerea structurii de vector 3or (i = k; i #= n.1; i&&)

A[i] = A[i&1];// scade di'ensiunea structurii

n..;



osturi - inserare

pi = ro4a4ilitatea eveni'entului de a insera o valoare nou$

e co'onenta i , i ∈ [1..n]. 5a inserarea e oziţia i tre4uie s$ 'ut$' n-i+1 c o'onente6

7u'$rul 'ediu de 'ut$ri la inserare M =Σ pi (n - i+1) .

ac$ p1 = …= pn = 1/n atunci

M = (1/n) ( n + ( n –1) + …. + 1 ) =(n+1)/2

"n unctie de mutari de componente



osturi - stergere

pi = ro4a4ilitatea eveni'entului de a ster2e co'onenta i ,

i ∈ [1..n]. 5a ster2erea lui A[i] tre4uie s$ 'ut$' n-i c o'onente6

7u'$rul 'ediu de 'ut$ri la ster2ere M =Σ pi (n - i) .

ac$ p1 = …= pn = 1/n atunci

M = (1/n) ( ( n –1) + …. + 1 ) =(n-1)/2

"n unctie de mutari de componente



autarea (unei valori date intr-o str$ lineara in

alocare statica)

void 8earc"5in (int A[], int n, int 9al, int 5oc){ / : caut$ liniar valoarea 9al +n A[166n] %i returneaz$5oc = dac$ nu o 2$se%te, %i o valoare 5oc ∈ [166n] dac$o 2$se%te e co'onenta A[5oc] :/ int i;

5oc = ; i = 1; !"ile ((i #= n) << (A[i] = 9al)) {

i&&; i3 (i #= n)

5oc = i;



autarea lineara - componenta marca2

void 8earc"5in1 (int A[], int n, int 9al, int 5oc){ // Căutare lineară de la stana la dreapta

A[n&1] = 9al; /! intr"duce# $al pe c"#p"nenta

#arca%& care 'a i la capatul din dreapta !/

5oc = 1;

!"ile (A[5oc] = 9al) {

5oc&&;

i3 (5oc == n&1)rint3(>?$utare 3$r$ succes>);else

rint3(>A' 2$sit e co'onenta @d,5oc);



omple#itate (costuri) - cautare lineara

pi = ro4a4ilitatea eveni'entului $al=A[i] (2asi'

valoarea c$utat$ e co'onenta i ), i ∈ [1..n]. = ro4a4ilitatea ca $al s$ nu se 2$seasc$ +n A[1..n].

Ave' Σ pi + = 1 .

Bentru 3iecare i ∈ [1..n+1]& entru a decide c$ ri'aaariţie a lui $al este e co'onenta A[i]& 3ace' i

co'araţii67u'$rul 'ediu de co'araţii va 3iC

C = Σ pi i + (n+1) .

"n unctie de componente accesate (comparatii)



Complexitate (costuri) - căutare lineară (cont.)

Ca*ul căutării cu succes:- $al se 2$se%te recis +n vector, i6e6 =

. se 2$se%te cu ro4a4ilitate e2al$ e oricare dinco'onente, i6e6 p1 = …= pn = 1/n

C = (1/n) ( 1 + 2 + ……. + n) = (n+1)/2 nu'$rul 'ediu de co'araţii +n cazul căutării cu

succes.

Ca*ul căutării fără succes:

- se traverseaz$ toata structura, se acceseaz$ n+1 co'6

C = n+1



Caz particular - vector ordonat crescător

- Structură lineară in alocare statica (secventiala)organizare suplimentara

A[1]≤ A[2]

≤ …

≤ A[n]

n3or'atie in lus – permite imbunatatirea cautarii lineare

Alta cautare - cautarea binara

– necesita modificarea algoritmilor de inserare



Cautarea lineara intr-un vector sortat

void 8earc"5inDrd (int A[], int n, int 9al, int 5oc)

{ int i;5oc = ;i = 1;!"ile ((i #= n) << (A[i] # 9al))

i&&;i3 (i #= n)

i3 (A[i] == 9al) // c$utare cu succes{

5oc = i;rint3(>ele'ent 2asit e ozitia @d >, 5oc);

else // A[i] - 9al

rint3(>c$utare 3$r$ succes>);else

rint3(>c$utare 3$r$ succes>);



Cautarea binara (intr-un vector sortat)

A[1..n] un vector cu A[1] ≤ A[2] ≤ … ≤ A[n]

Algoritmul de căutare binară:

(1) 8e +ncee cu se2'entul de3init de indicii ,et = 1 %i it = n

(E) Bentru 3iecare su4vector A[,et..it] se reet$C

(a) 8e calculeaz$ 'iFlocul se2'entului

Mid= (,et + it) / 2

(4) 8e co'ar$ $al cu A[Mid]

. dac$ $al = A[Mid] c$utarea se ter'in$ cu succes;

. dac$ $al 0 A[Mid] se reia asul (E) e [,et..Mid-1] ;

. dac$ $al [Mid] se reia asul (E) e [Mid+1..it] 6



void 8earc"Gin(int A[], int n, int 9al, int 5oc){ int 5e3t, Hi2"t, Iid;

5e3t = 1; Hi2"t = n;

Iid = (5e3t & Hi2"t)/E;5oc = ;!"ile ((5e3t #= Hi2"t) << (9al = A[Iid] )){ i3 (9al # A[Iid]) // se continu$ e su4intervalul din stn2a

Hi2"t = Iid.1; else // 9al - A[Iid] . se continu$ e su4intervalul dindreata

5e3t = Iid&1;Iid = (5e3t & Hi2"t)/E;

i3 (A[Iid] == 9al) //c$utare cu succes

{ 5oc = Iid; Brint3(>ele'ent 2asit e ozitia @d >, 5oc);

else5oc = ; //c$utare 3$r$ succes



Cautarea binara - complexitate

C(n) = nu'$rul de co'araţii e care +l necesit$ c$utarea4inar$ e un vector cu n co'onente6u$ 3iecare co'araţie di'ensiunea se2'entului e carec$ut$' se reduce la Fu'$tate6

ac$ du$ C(n) co'araţii a' +nc"eiat c$utarea, atunci2 C(n) n 2 C(n)-1

de undeC(n) = l" 2 n +1

co'leitatea c$ut$rii 4inare . (l" 2 n)

co'leitatea c$ut$rii lineare (secventiale) . (n)



Structuri lineare in alocaredinamica: liste(liste simplu inlantuite)



/iste simplu inlantuite - operatii

• Traversare•autarea unui element•"nserare nod nou

•Stergere (e#tragere) nod



Structuri lineare in alocare dinamica%liste (liste simplu inlantuite)

•elementele listei s$n$ noduri•fecare nod con.ine%

• () un c+mp, pe care se reprezint un element

al mul.imii (de obicei vom indentifcaelementul cu valoarea de pe un singur c+mp,numit c+mp cheie) 3n algoritmii careurmeaz putem presupune c elementulocup un singur c+mp, info

• (*) un pointer ctre nodul urmtor, next $



/iste simplu inlantuite

ino ne#t

…

Start

struct nod4 int ino nod 5ne#t

6



Lista

- Mod de acces la fecare element

Implementare lista inlantuita cu vectori: /istele simplu

3nln.uite se pot reprezenta i cu alocare static$ +mpurile info

ocup anumite loca.ii ale unui vector, iar c+mpurile next

asociate vor con.ine indicele elementului urmtor$ 7ceast

reprezentare se numete reprezentarea cu cursori a listei$

1 2 k n

Info Y … X … Z

Next n 2 0



Defniţie recursivă:

! list L de un anume tip de baz este%

(a) fe lista vid (L ! ∅ )

(b) fe este nevid, i atunci con.ine un nod numit capul

listei, urmat de o alt list de acelai tip de baz, unde

prin 8tip de baz9 ne reerim la tipul de date de pe

c+mpul info$



Liste simplu inlantuite - operatii

• Traversare

•autarea unui element

•"nserare nod nou




Observatii C C!!

•7locarea de memorie- in % malloc()

nod 5p : (nod 5) malloc (sizeo(nod))

- in ;;% ne"l nod 5p : ne< nod

•Eliberare de memorie

•- in % ree() ree (p)

•- in ;;% delete delete p




#raversare

$$$Start

ino ne#t

p

nod :; = 8tart; !"ile( = 7J55)

{ // relucrare K in3o = K net;




Cautare

$$$Start

ino ne#t

p

nod :;p : Start<hile (p =: 0>// ?? @al =: p A ino)

p : p A ne#ti (p :: 0>//) 11 cautare ara succes

else 11 gasit in p @al :: p A ino




%nserare

nod 5B : (nod 5) malloc(sizeo(nod)) 11 prelucrare B A inoB A ne#t : pi (oldp =: 0>//)

oldp A ne#t : Belse

Start : B

poldp

B



Ster&ere

nod 5temp : pi (oldp =: 0>//)

oldp A ne#t : p A ne#telse

Start : p A ne#t11 prelucrare temp sau temp A inoree(temp)


poldp p A ne#t



'lte tipuri de liste$ 'plicatii$



'lte tipuri de liste$ 'plicatii$

•cu nod marca2•circulare•dublu inlantuite

•alte inlantuiri – liste de liste – masive

Li t d



Liste cu nod marca

- Se modifca (simplifca) inserarile1stergerile



/iste cu nod marca2

#raversare

$$$Start

ino ne*t

p

nod :; = 8tart K net; !"ile( = 7J55)

{ // relucrare K in3o = K net;



/iste cu nod marca2

%nserare

nod 5B : (nod 5) malloc(sizeo(nod)) 11 prelucrare B A ino

B A ne#t : poldp A ne#t : B

poldp

B

Start$$$



Ster&ere

i (Start A ne#t :: 0>//)11 lista vida

else4

nod 5temp : poldp A ne#t : p A ne#t11 prelucrare temp sau temp A inoree(temp)

6

/iste cu nod marca2

Start$$$

poldp p A ne#t



Liste circulare

ig.!.".#. $istă circulară.

Start

. . .. . .

- util pentru aplica.iile 3n care este nevoie s acemparcurgeri repetate ale listei- testul de nedepire al structurii nu va mai f de tipul p ≠ N"LL



/iste circulare

#raversare

nod :; = 8tart;

// relucrare K in3o ri'ul ele'ent al listei

= K net; !"ile( = 8tart) { // relucrare K in3o = K net;


Start

. . .. . .

E#emplu C stergere duplicatelor dintr-o lista



/iste circulare

Cautare

nod :;p : Starti (p A ino :: @al) 11 cautare cu succes

else 4 p : p A ne#t

<hile (p =: Start ?? @al =: p A ino)p : p A ne#ti (p :: Start) 11 cautare ara succes

else 11 gasit in p @al :: p A ino


Start

. . .. . .



Liste circulare cu nod marca

ig.!.".%. $istă circulară cu nod marca&.

Start

. . .

ig.!.".'. $istă circulară vidă cu nod marca&.

Start

- cautare% Se introduce valoarea cutat #al pe c+mpul info alnodului marca2 cu $tart −> info ! #al$ Se 3ncepe cutarea 3n lista$tart −> next $Loc! pointerul returnat de opera.ia de cutare$ Dac Loc ≠ $tart cutarea este cu succes, iar dac Loc ! $tart cutarea este r

succes$



/iste circulare cu nod marca2

#raversare

nod :; = 8tart K net;

!"ile( = 8tart) { // relucrare K in3o = K net;


Start

. . .




Cautare

nod :5oc;8tart K in3o = 9al;/oc : Start A ne#t

<hile (/oc A ino =: @al)/oc : /oc A ne#ti (/oc :: Start) 11 cautare ara succes

else 11 gasit in /oc


Start

. . .




%nserare


Start

. . .

poldp

B

nod 5B : (nod 5) malloc(sizeo(nod)) 11 prelucrare B A ino

B A ne#t : poldp A ne#t : B




Ster&ere

Start$$$

poldp p A ne#t

i (Start A ne#t :: Start)11 lista vidaelse4

nod 5temp : p

oldp A ne#t : p A ne#t11 prelucrare temp sau temp A inoree(temp)

6



Liste dublu +nlănţuite$

next prev

ig.!.".(. )od *ntr-o listă dublu *nlăn+uită.

- inserari1stergeri% parcurgerea cu cautarea locului se

poate ace cu un singur pointer- parcurgeri in ambele sensuri

- cost % locatii in plus =

struct nod4 int ino nod 5prev, 5ne#t

6



Liste dublu inlantuite - operatii

• Traversare

•autarea unui element

•"nserare nod nou


i d bl i l i



/iste dublu inlantuite

#raversare

// Parcurgere Start – End

nod :; = 8tart;!"ile( = 7J55) { // relucrare K in3o = K net;

$$$

ne#t

pStart

End

ino

prev

ino

// Parcurgere End – Start

nod :; = *nd;!"ile( = 7J55) { // relucrare K in3o = K rev;

/i d bl i l i




Cautare

// Parcurgere End – Start

nod :;p : End

<hile (p =: 0>// ?? @al =: p A ino)p : p A prev

i (p :: 0>//) 11 cautare ara succeselse 11 gasit in p @al :: p A ino

$$$

ne#t

pStar

t

End

ino

prev

ino

/i t d bl i l t it




%nserare

nod 5B : (nod 5) malloc(sizeo(nod)) 11 prelucrare B A inoB A ne#t : pp A prev : BB A prev : oldp

i (oldp =: 0>//)oldp A ne#t : B

elseStart : B

poldp

B



Ster&ere

nod 5temp : p

i (oldp =: 0>//)4p A ne#t A prev : oldpoldp A ne#t : p A ne#t

6

else4 p A ne#t A prev : 0>//Start : p A ne#t6

11 prelucrare temp sau temp A ino

ree(temp)

p

oldp


p A ne#t



'plicatii

,eprezentarea vectorilor rari

- valorile nenule- indicele pe care apare resp$ val$ nenula



'plicatii (cont$)

,eprezentarea polinoamelor rare

Start, " '%!,

exp coef next

ig.!.".. eprezentarea polinoamelor rare.



'plicatii(cont$),eprezentarea matricilor rare

nlin lin

ai& i

ncol & col

ig.!."./. eprezentarea unui nod *ntr-o matrice rară.



'plicatii(cont$)

,eprezentarea numerelor mari.

% ( ' ! /

"ntregul *FG reprezentat ca lista (aritmetica cunumere 8mari9)



'plicatii(cont$)

Liste/ de liste,eprezentarea &raurilor (rare)

- lista de viruri- pt$ fecare vir/ lista sa de

adiacenta

3-StructDate - C - Liste

Documents

Transcript of 3-StructDate - C - Liste