Sd Modul Ifc Rom

MINISTERUL EDUCAIEI

INSTITUTUL DE FORMARE CONTINU

CATEDRA TEHNOLOGII INFORMAIONALE

Structuri de date

(n baza C++)

SUPORT DE CURS

Ediia 2

Elaborat i adaptat

Sergiu Pereteatcu, conf., dr.

Alexandru Pereteatcu, mag. n inf.

Chiinu - 2014

Structuri de date (n baza C++): Suport de curs S.Pereteatcu, A.Pereteatcu

2

R ec o ma n da t d e c t r e C o mi s ia t i i n i f i c o -M et o d i c a Uns t i t u t u lu i d e F or ma r e C o nt i nu , P r oc es s + v e r b a l nr . 1 d i n 1 4 iu n i e 2 0 1 2

Sergiu Pereteatcu, confereniar unuversitar, doctor

Alexandru Pereteatcu, magistru n informatic

Redactor coordonator

Ion Spinei - confereniar unuversitar, doc

Tehnoredactare computerizat

Ion Stngu

Descrierea CIP a Camerei Naionale a Crii

Pereteatcu, Sergiu Structuri de date (n baza C++): Suport de curs / Sergiu Pereteatcu, Alexandru Pereteatcu;

Inst. de Formare Continu, Catedra Tehnologii Informaionale. Ch.: Inst. de Formare Continu, 2012. 135 p.

Bibliogr.: p. 134 (15 tit.). ISBN 978-9975-4404-3-1.

004.6:519.1/6(075.8)

P52


3

CUPRINS

1. INTRODUCERE N STRUCTURI DE DATE ..................................................................4

1.1. Noiuni generale .............................................................................................................4 1.2. Clase de baz..................................................................................................................5

2. TABELE ................................................................................................................................10 2.1. Noiune de tabel............................................................................................................10 2.2. Tabele neordonate ........................................................................................................12 2.3. Tabele neordonate structurate arborescent.....................................................................17 2.4. Tabele ordonate ............................................................................................................24 2.5. Tabele cu adresare direct.............................................................................................29 2.6. Tabele de repartizare (repartizarea aleatorie).................................................................29

3. TEHNICI DE SORTARE ...................................................................................................40 3.1. Noiuni generale ...........................................................................................................40 3.2. Clase pentru exemple de sortare....................................................................................41 3.3. Sortarea prin interschimbare .........................................................................................44 3.4. Sortarea rapid..............................................................................................................45 3.5. Sortarea prin inserie.....................................................................................................59 3.6. Sortarea prin selecie.....................................................................................................66 3.7. Sortarea arborescent (piramidal, heapsort).................................................................66 3.8. Comparaii practice ai diferiilor algoritmi de sortare ....................................................72

4. STRUCTURI DINAMICE DE DATE................................................................................73 4.1. Noiune de structura dinamic de date...........................................................................73 4.2. Arbori binari.................................................................................................................74 4.3. Liste .............................................................................................................................85 4.4. Stive .............................................................................................................................95 4.5. Cozi............................................................................................................................118

5. MATRICE ...........................................................................................................................129 5.1. Noiune de matrice......................................................................................................129 5.2. Structura intern de memorie vector.........................................................................130 5.3. Reprezentarea matricelor n memoria operativ ..........................................................130 5.4. Reprezentarea matricelor pe linii .............................................................................131 5.5. Reprezentarea matricelor pe coloane .......................................................................140 5.6. Vectori definitori ........................................................................................................147 5.7. Vectori Iliffe...............................................................................................................153

6. ACTIVITI ........................................................................................................................161 I Declararea claselor de baz....................................................................................161 II Lucrul cu tabele....................................................................................................162 III Sortri.................................................................................................................162 IV Structuri dinamice de date...................................................................................163 V Matrice ................................................................................................................165

BIBLIOGRAFIE........................................................................................................................166


4

Program = Algoritm + Structuri de date

Niklaus Wirth, 1976

1. INTRODUCERE N STRUCTURI DE DATE

1.1. Noiuni generale Definiia:

Prin structura de date abstract (SDA), sau pur i simplu structura de date

(SD), vom nelege o totalitate de reguli i restricii ce reflect legturile existente ntre prile separate de date i prin care prile acestea se unesc

ntr-un singur tot.

Cuvntul abstract n definiia structurii de date subliniaz c structura de date se examineaz fr cercetarea modului de reprezentare a ei n memoria calculatorului.

Structura nimic nu ne spune despre prile separate de date (mai corect despre coninutul lor). Coninutul poate fi format n procesul de lucru. Drept vorbind, structura poate s cear ca aceste prile componente s fie n concordan cu structura. Totui orice informaii ce se conin n elementele de date nici cum nu depind de nsi structura.

Termenul utilizat element nseamn o parte de structur de date abstract. Elementul poate fi o valoare de un tip simplu. El poate fi i o alt structur de date, sau o referin la alte structuri de date, astfel s creeaz structuri de date ierarhice sau secvene de structuri de date.

Vom diviza structuri de date n statice i dinamice. Definiia:

Exemplu: Matrice cu dimensiunile fixe, Tabeel cu numrul de nregistrri tabelare fix, Vectori cu numrul de elemente fix. Definiia:

Prin structura de date dinamic vom nelege aa SD, la care n procesul de

lucru se schimb att informaii ce se conin n elemente de date, ct i numrul de elemente (componena cantitativ).

Exemplu: Liste nlnuite de diferite tipuri, stive, cozi, arbori binari.

Prin structura de date static vom nelege aa SD, la care n procesul de lucru se schimb numai informaiile ce se conin n elemente de date i nu se schimb

cantitatea acestor elemente.


5

1.2. Clase de baz

La demonstrarea metodelor de organizare a structurilor de date vom utiliza clase generice. Orice astfel de metod va fi realizat printr-o clas generic parametrizat cu o alt clas-parametru ce reprezint un element al structurii de date respective. n calitate de argumentul la instaniera unei clase generice vom folosi o clas concret derivat de la clasa abstract elem.

Clasa abstract elem nu va putea fi instaniat. Ea doar descrie cele funcii virtuale pure care neaprat trebuie redefinite n orice clasa derivat concret, care va fi folosit ulterior pentru reprezentarea elementelor la construirea structurilor de date. Clasa abstract mai conine suprancrcrile operatorilor de comparaie bzndu-le pe funcia virtual pur cmp().

Declararea clasei abstracte elem va arta astfel: #include

#include

#include

#include

#include

#include

//

// a b s t r a c t c l a s s "e l e m"

//

class elem

{

public:

virtual int fscanf_el(FILE *f)=0;

virtual void show(const char* opening=NULL,

const char* ending=NULL)=0;

virtual int free() = 0;

virtual int cmp(elem& e2) = 0;

int operator > (elem& e2)

{

return cmp(e2)>0;

}

int operator >= (elem& e2)

{

return cmp(e2)>=0;

}


6

int operator < (elem& e2)

{

return cmp(e2)


7

double salary;

public:

usual_elem()

{

name[0]='\0';

year=0;

salary=0.0;

}

usual_elem(char* init_name, int init_year, double init_salary)

{

strcpy(name, init_name);

year=init_year;

salary=init_salary;

}

virtual int fscanf_el(FILE *f)

{

return fscanf(f, "%s %d %lf", name, &year, &salary);

}


const char* ending=NULL)

{

if(!opening)

opening="";

if(!ending)

ending="\n";

cout


8

return strcmp(this->name, ((usual_elem&)e2).name);

}

};

Crem un fiier text cu numele, de exemplu, stud.txt, din care mai departe vom introduce informaii pentru ncrcarea diferitelor structuri de date. Coninutul fiierului stud.txt va arta astfel: Green 1987 350.00

Red 1980 450.00

Blue 1981 500.00

Gray 1968 900.00

Orange 1984 550.00

White 1980 600.00

Cyan 1975 800.00

Yellow 1988 300.00

Magenta 1983 600.00

Black 1981 500.00

In fine, declarm clasa abstract SD, care va servi n viitor ca clasa de baz pentru declararea diferitelor claselor de reprezentare a structurilor de date. //

// a b s t r a c t c l a s s "S D"

//

class SD

{

protected:

FILE* pf;

long ncomp;

public:

SD()

{

pf=NULL;

ncomp=0;

}

SD(char* file_name)

{

if(!(pf=fopen(file_name, "rt")))

{

char *mes = new char[5+strlen(file_name)+12+1];

error(strcat(strcat(strcpy(mes,"File "),file_name),

" not found!\n"));


9

}

ncomp=0;

}

~SD()

{

if(pf)

fclose(pf);

}


const char* ending=NULL)=0;

long get_ncomp()

{

return ncomp;

}

void reset_ncomp()

{

ncomp=0;

}

protected:

void error(char* message)

{

cerr


10

2. TABELE

2.1. Noiune de tabel

Tabel este un set de elemente, fiecare din care are un indicator special numit

cheie cu proprietatea c elementele se adaug n tabel i se caut n tabel dup cheie. Pe lng cheie, elementul din tabel (se mai numete nc nregistrare

tabelar) de obicei conine date, purttoare de careva informaii.

Exemplul 1.

Tabelul ptratelor numerelor naturale Cheia

(valoarea

argumentului)

Datele

(valoarea

funciei)

0 0

1 1

2 4

3 9

4 16

5 25

6 36

Cheia n acest tabel este valoarea argumentului, dar valoarea funciei reprezint informaii.

Exemplul 2.

Tabelul de trecere din baza 10 n bazele 2, 8 i 16 Datele Cheia

(valoarea

numrului

n baza 10)

Valoarea

numrului

n baza 2

Valoarea

numrului

n baza 8

Valoarea

numrului

n baza 16

0 0000 00 0

1 0001 01 1

2 0010 02 2

3 0011 03 3

4 0100 04 4

5 0101 05 5

6 0110 06 6

7 0111 07 7

8 1000 10 8

9 1001 11 9


11

10 1010 12 A

11 1011 13 B

12 1100 14 C

13 1101 15 D

14 1110 16 E

15 1111 17 F

Cheia n acest tabel este valoarea numrului n baza 10, iar datele poart informaii despre valoarea numrului n bazele 2, 8 i 16.

Exemplul 3:

Tabelul de nume simbolice Datele Cheia

Symbol name Type Value

!!DATE Text 09/15/12

??FILENAME Text sumvectr

??TIME Text 11:28:21

A10 Near COD:004E

B10 Near COD:00AD

BINSTR Near COD:01A0

C10 Near COD:0105

N Word DATE:0067

NOMBIN Word DATE:02CF

S10 Near COD:0181

Z Byte DATE:0061

ZMAX Byte DATE:005F

ZT Word DATE01F9

Compilatoare i interpretatoare folosesc tabele de nume. Cheia n astfel de tabel este identificatorul, dar datele poart informaii despre tipul variabilei, adresa de alocare n memoria calculatorului, etc.

n memoria calculatorului tabele de obicei sunt prezentate sub form de vectori de nregistrri, dar uneori se folosesc i liste, sau combinri dintre vectori i liste.

Referitor la tabele o problem cea mai important este problema de cutare.

Problema cutrii const n aflarea dup cheia dat adresei (locului) de pstrare

a nregistrrii tabelare cu aa cheie, sau ajungerea la concluzie c o aa

nregistrare nu este n tabel.

Aceast problem se rezolv diferit, n dependen de metoda organizrii a tabelului.

Caracteristica principal a metodei de organizare a tabelului este timpul mediu de cutare a unei nregistrri tabelare. Acest timp este proporional lungimii medii de cutare.


12

Lungimea medie de cutare este numrul mediu de nregistrri parcurse pentru

cutarea nregistrrii necesare.

2.2. Tabele neordonate

n tabele neordonate nregistrrile sunt aranjate una dup alta (pe msura venirii) fr lipsuri. Astfel de tabele uor se alctuiesc. O nou nregistrare pur i simplu se adaug la sfritul tabelului dup nregistrarea precedent.

Pentru cutare n aa tabele se aplic parcurgerea secvenial, prin care nregistrrile se parcurg la rnd una dup alta, ncepnd cu prima.

Lungimea medie de cutare prin parcurgerea secvenial a tabelului cu n nregistrri tabelare se calculeaz prin formula:

n

iiipD

1

(2.1)

unde i - este numrul de ordine a nregistrrii, iar pi probabilitatea c nregistrarea necesar are numr i.

Dac nregistrarea cutat se afl n orice loc al tabelului cu probabilitatea egal, atunci n

pi1

, i

lungimea medie de cutare va fi egal:

22

11

11

nnnnn

iD

n

i

(2.2)

Tabelele neordonate nu sunt economice dup timpul de cutare, de aceea ele nu se folosesc n calitate de tabele constante n translatoare (compilatoare sau interpretatoare). ns adugarea unei nregistrri noi n aa tabele necesit timpul minim, deaceea tabelele neordonate uneori se folosesc n translatoare ca tabele temporare, ncrcndu-se n timpul translaiei. La nceputul vectorului de reprezentare a acestui tabel, deseori se pstreaz numrul maximal posibil de nregistrri i numrul primei linii libere din tabel.

Pentru a demonstra lucrul cu tabele neordonate declarm clasa table, ca o clas generic ce depinde de un tip parametrizat reprezentnd o nregistrare tabelar. //

// c l a s s "t a b l e"

//

const NMAX=200;

//

template class table : public SD {

protected:

int n; // numrul de nregistrri tabelare


13

el t[NMAX]; // vector de nregistrri tabelare

public:

table()

{

n=0;

}

table(char* file_name) :

SD(file_name)

{

int repeated;

n=0;

while(!feof(pf))

if(t[n].fscanf_el(pf)>0)

{

if ( (repeated=search(t[n]))>=0 )

{

char message[60];

char repeated_str[10];

message[0]='\0';

strcat(message,

"Key coincides with the key in the position: ");

strcat(message, itoa(repeated+1, repeated_str, 10));

strcat(message, "!\n");

error(message);

}

n++;

}

fclose(pf) , pf=NULL; }

virtual void show(const char* opening =NULL, const char* ending=NULL)

{

clrscr();

cout


14

{

if(i>0 && i%20==0)

{

cout


15

cin >> surname;

usual_elem e(surname, 2000, 0.0);

gr.reset_ncomp();

int pos=gr.search(e);

if(pos


16

n urmtorul exemplu al funciei main() se calculeaz lungimea medie de cutare pentru un tabel simplu neordonat creat n baza fiierului stud.txt. void main()

{

clrscr();

table gr("Stud.txt");

gr.show("Group:\n","");

usual_elem sample;

long NCOMP=0;

FILE* pf=fopen("Stud.txt", "rt");

while(!feof(pf))

if(sample.fscanf_el(pf)>0)

{

gr.reset_ncomp();

if(gr.search(sample)>=0)

NCOMP+=gr.get_ncomp();

}

fclose(pf);

cout


17

2.3. Tabele neordonate structurate arborescent

Cteodat n calitate de tabele temporare se aplic tabele neordonate structurate arborescent, organizate n form de arbore binar. La fiecare nregistrare tabelar n aa tabele se adaug cte doi pointeri: un pointer spre nregistrarea tabelar cu valoarea mai mic a cheii, iar al doilea pointer spre nregistrrea tabelar cu valoarea mai mare a cheii.

O nou nregistrare se adaug n tabel la rnd, ca i n tabele neordonate simple. Dup adugarea n tabel a noii nregistrri valoarea cheii se compar cu valoarea cheii a primei nregistrri a tabelului. Dup rezultatul comparrii cu ajutorul pointerilor se afl adresa pstrrii urmtoarei nregistrri, cu cheia crei trebuie de comparat valoarea cheii nregistrrii noi. Acest proces are loc pn atunci, pn cnd nu va fi gsit nregistrarea tabelar cu pointerul vid n direcia necesar de cutare. n acest pointer se nscrie adresa pstrrii noii nregistrri tabelare.

De exemplu, n figura 2.1 este artat tabelul neordonat structurat arborescent creat pe baza fiierului Stud.txt.

Pentru a demonstra lucrul cu tabele neordonate structurate arborescent mai nti de toate crem n baza clasei usual_elem clasa tree_like la care mai adaugm dou cmpuri cu caracter de pointeri. //

// c l a s s "t r e e l i k e" e l e m e n t s

//

class tree_like: public usual_elem

{

protected:

int less;

int greater;

public:

tree_like()

{

less=greater=-1;

}

tree_like(char* init_name, int init_year, double init_salary):

usual_elem(init_name, init_year, init_salary)

{

less=greater=-1;

}

int get_less()

{

return less;

}


18

int set_less(int new_less)

{

return less=new_less;

}

int get_greater()

Fig. 2.1 Tabelul neordonat structurat arborescent

00

01 Red 1980, 450

4 5

02 Blue 1981, 500

9 3

03

04 Orange

05

1984, 550

8 -1

White 1980, 600

-1 7

06 Cyan 1975, 800

-1 -1

07 Yellow 1988, 300

-1 -1

08

09

Magenta 1983, 600

-1 -1

Black 1981, 500

-1 -1

Gray 1968, 900

6 -1

Green 1987, 350

2 1


19

{

return greater;

}

int set_greater(int new_greater)

{

return greater=new_greater;

}

virtual void tree_show(const char* opening =NULL, const char* ending=NULL)

{

if(!opening)

opening="";

if(!ending)

ending="\n";

cout


20

for(int i=1; i


21

}

int search(el e)

{

int position = -1;

int forward=1;

int i=0;

int cmp_result;

while(forward)

if( ncomp++, (cmp_result=e.cmp(t[i]))==0 )

position=i, forward=0;

else

{

if(cmp_result


22

char ch='n';

char surname[21];

while(ch!='y')

{

cout > surname;

tree_like e(surname, 2000, 0.0);

tree_gr.reset_ncomp();

int pos=tree_gr.search(e);

if(pos


23

5. Orange, 1984, 550 [8, -1]

6. White, 1980, 600 [-1, 7]

7. Cyan, 1975, 800 [-1, -1]

8. Yellow, 1988, 300 [-1, -1]

9. Magenta, 1983, 600 [-1, -1]

10. Black, 1981, 500 [-1, -1]

End of Table. Press any key ...

Enter a name to search: White

There are in the position 6. The number of comparisons: 3

Done ? (y/n)

Enter a name to search: Green


Done ? (y/n)

Enter a name to search: Black


Done ? (y/n)

Enter a name to search: Purple

No table! The number of comparisons: 3

Done ? (y/n)

Dac vrem s calculm lungimea medie de cutare pentru acest tabel, scriem funcia main() astfel: void main()

{

clrscr();

tree_table gr("stud.txt");

gr.tree_show("Group:\n","");

tree_like sample;

long NCOMP=0;

FILE* pf=fopen("stud.txt", "rt");

while(!feof(pf))


{

gr.reset_ncomp();



}

fclose(pf);

cout


24

}

Afiarea va arta: Group:

1. Green, 1987, 350 [2, 1]

2. Red, 1980, 450 [4, 5]

3. Blue, 1981, 500 [9, 3]

4. Gray, 1968, 900 [6, -1]

5. Orange, 1984, 550 [8, -1]

6. White, 1980, 600 [-1, 7]

7. Cyan, 1975, 800 [-1, -1]

8. Yellow, 1988, 300 [-1, -1]

9. Magenta, 1983, 600 [-1, -1]

10. Black, 1981, 500 [-1, -1]


N=10, NCOMP=29, ALS=2.9, MAX=5, MIN=5.32193

Analiza rezultatelor rmne ca exerciiu.

Neajunsul tabelelor neordonate structurate arborescent cheltuieli mai mari de memorie (pentru pstrarea pointerilor) i algoritmii de ncrcare tabelului i cutare nregistrrilor puin mai complicai n comparaie cu cei pentru tabelele neordonate simple.

2.4. Tabele ordonate

Tabele pot fi ordonate cresctor dup codul numeric al cheii, sau dup frecvena apelurilor la nregistrri. n primul caz pentru cutarea nregistrrii de obicei se folosete cutarea binar, dar n al doilea parcurgerea secvenial.

Cutarea binar const n mprirea tabelului n dou pri aproape egale i constatarea n care din cele dou pri se gsete valoarea cheii cutat. Partea ce conine cheia se supune de fiecare dat mpririi secveniale. Fiindc tabelul este aranjat cresctor dup cheie, pentru a gsi n care parte se afl valoarea cheii cutate, valoarea cheii n punctul mpririi se compar cu valoarea cheii cutate. //

// c l a s s "s o r t e d t a b l e"

//

template class sorted_table: public table

{

public:

sorted_table()

{

}


25

sorted_table(char* file_name)

{

el tmp;

pf=fopen(file_name, "rt");

n=0;

while(!feof(pf))

if(tmp.fscanf_el(pf)>0)

{

int i;

for(i=n-1; i>=0 && (tmp0 && i>=0 && tmp==t[i])

{

char message[60];


message[0]='\0';

strcat(message,


strcat(message, itoa(i+1, repeated_str, 10));


error(message);

}

t[i+1]=tmp, n++;

}

fclose(pf) , pf=NULL; }

int search(el e)

{

int a=0, b=n-1;

int result;

while(a0)

a=i+1;

else

if(result


26

}

return (ncomp++, e==t[a])? a : -1;

}

};

n funcia main() demonstrm utilizarea tabelelor sortate dup cheie. void main()

{

clrscr();

sorted_table sorted_gr("stud.txt");

sorted_gr.show("Group:\n","");

char ch='n';

char surname[21];

while(ch!='y')

{

cout > surname;

usual_elem e(surname, 2000, 0.0);

int pos=sorted_gr.search(e);

int pos=sorted_gr.search(e);

if(pos


27

7. Orange, 1984, 550

8. Red, 1980, 450

9. White, 1980, 600

10. Yellow, 1988, 300


Enter a name to search: White


Done ? (y/n)

Enter a name to search: Green


Done ? (y/n)

Enter a name to search: Black


Done ? (y/n)

Enter a name to search: Purple

No table! The number of comparisons: 4

Done ? (y/n)

Lungimea cutrii binare se obine dup formula

2log 22 nD (2.3),

ce pentru n destul de mare aproape c este egal cu limita de jos teoretic pentru metode de cutare, bazate numai pe compararea cheilor. Teoretic limita de jos este egal cu log2(n+1). Cutarea binar mult mai efectiv dect parcurgerea secvenial. Pentru n=1000, D1=500, iar D2=11.

Pentru a calcula lungimea medie practic de cutare n tabelul ordonat creat n baza fiierului "stud.txt" modificm funcia main(). void main()

{

clrscr();

sorted_table gr("stud.txt");

gr.show("Group:\n","");

usual_elem sample;

long NCOMP=0;

FILE* pf=fopen("Stud.txt", "rt");

while(!feof(pf))


{

gr.reset_ncomp();



}


28

fclose(pf);

cout


29

2.5. Tabele cu adresare direct

Fie n tabel de m nregistrri, toate nregistrrile au diferite valori ale cheilor k0, k1, k2,..., km-1, i tabelul este reflectat n vectorul T[0], T[1], , T[n-1], unde mn. Dac este definit funcia f(k), astfel, ca pentru orice ki, i=0, ..., m-1, f(ki) are o valoare ntreag ntre 0 i n-1, unde f(ki)f(kj), ij atunci nregistrarea tabelar cu cheia K se reflect bireciproc n elementul T[f(K)].

Funcia f(K) se numete funcie de repartizare (dispersare sau Hash funcie). Aceast funcie asigur calcularea pentru fiecare nregistrare tabelar a numrului corespunztor al elementului vectorului T. Accesul la nregistrare dup cheia K se efectueaz n acest caz nemijlocit prin calcularea valorii f(K). Tabelele, pentru care exist i este cunoscut (descris) funcia de repartizare, se numesc tabele cu adresare direct. Lungimea medie de cutare n astfel de tabele este minimal i egal D3=1.

Alegerea funciei de repartizare, care asigur transformarea bireciproc a cheii nregistrrii n adresa de pstrare, n caz general este o problem destul de complicat. Practic ea poate fi rezolvat numai pentru tabelele constante cu setul de valori pentru cheii tiut dinainte. De exemplu: tabelul de recodificare, tabelul de simboluri ale limbajului de intrare al translatorului.

2.6. Tabele de repartizare (repartizarea aleatorie)

Noiuni generale

Deoarece, practic transformarea bireciproc a cheii n adresa pstrrii nregistrrii, n mod general, nu poate fi ndeplinit, atunci suntem nevoii s ne refuzm de cerin de reflectare birereciproc. Aceasta aduce la suprapunerea nregistrrilor sau, altfel zis, la coliziuni. Ca astfel de coliziuni s fie ct mai puine, funcia de repartizare se alege din condiia de reprezentare aleatorie i cu ct se poate mai uniform de reflectarea cheilor n adresa de pstrare. Tabele construite dup acest principiu sunt numite tabele de repartizare.

Repartizarea nu exclude pe deplin posibilitatea de suprapunere a nregistrrilor (coliziuni). De acea se aplic diferite metode pentru nlturarea coliziunilor. Diferena variantelor de tabele de repartizare este definit prin metoda folosit de nlturare a coliziunilor.

Tabele de repartizare cu examinarea liniar (adresare deschis)

n metoda de repartizare cu examinarea liniar la reprezentarea tabelelor n vector de lungime n se folosete urmtorul algoritm al inserrii nregistrrii cu cheia dat K:

1. Calculm i=f(K). Trecem la punctul 2. 2. Dac poziia i este liber, atunci nscriem n aceasta poziie nregistrarea noua. n caz contrar

trecem la punctul 3.

3. Punem i=(i+1) mod n, i trecem la punctul 2:

nidaca

nidacaii

1,0

1,1

La includerea unei noi nregistrri algoritmul rmne determinat pn atunci, cnd vectorul, n care se reflect tabelul, conine mcar o poziie liber.


30

Dac aceast condiie nu se ndeplinete este posibil ciclarea, mpotriva creia trebuie de luat msuri speciale. De exemplu, se poate introduce un contor de poziii verificate, dac acest numr a devenit mai mare ca n, atunci algoritmul trebuie s fie oprit.

La cutarea nregistrrii cu cheia dat K se folosete urmtorul algoritm:

1. Calculm i=f(K). Trecem la punctul 2

2. Dac poziia i este liber atunci n tabelul dat nu exist nregistrarea cu cheia K. Dac poziia este ocupat i cheia coincide cu cheia K, atunci cutarea este reuit, n caz contrar trecem la punctul 3.

3. Punem i=(i+1) mod n, i trecem la punctul 2:

nidaca

nidacaii

1,0

1,1

La cutare algoritmul este determinat dac tabelul conine nregistrarea tabelar cu cheia K, sau vectorul conine poziii libere. n cazul nendeplinirii acestor condiii trebuie de luat msuri speciale. De exemplu, se poate introduce un contor de poziii verificate, dac acest numr a devenit mai mare ca n, atunci algoritmul trebuie s fie oprit.

Declarm n baza clasei usual_elem clasa hashing_elem care va fi dotat cu o funcie de repartizare. //

// c l a s s "h a s h i n g _ e l e m"

//

class hashing_elem : public usual_elem

{

public:

hashing_elem()

{

}

hashing_elem(char* init_name, int init_year, double init_salary):


{

}

int hf(int n) // hashing function

{

return (name[0]-'A')%n;

}

};

n exemplul acesta valoarea funciei de dispersare este egal cu numrul de ordine al primei litere a numelui n alfabet. Numrul de ordin se moduleaz dup mrimea vectorului de reprezentare.


31

n baza clasei generice table declarm clasa hashing_table tot generic, care asigur lucrul cu tabele de repartizare cu examinarea linear. //

// c l a s s "h a s h i n g t a b l e"

//

template class hashing_table: public table

{

protected:

int m;

public:

hashing_table(char* file_name, int n_init)

{

n=n_init, m=0;

el tmp;

int repeated;


m=0;

while(!feof(pf))

if(tmp.fscanf_el(pf)>0)

{

int i=tmp.hf(n);

repeated=-1;

while((repeated==-1) && !t[i].free())

{

if ( tmp==t[i] )

repeated=i;

else

i=(i+1)%n;

}

if ( repeated!=-1 )

{

char message[60];


message[0]='\0';

strcat(message,


strcat(message, itoa(repeated+1, repeated_str, 10));


error(message);

}

t[i]=tmp;


32

m++;

}

fclose(pf), pf=NULL;

}

int search(el e)

{

int position=-1;

int i=e.hf(n);

while((position==-1) && !t[i].free())

if(ncomp++, e==t[i])

position=i;

else

i=(i+1)%n;

return position;

}

int get_m()

{

return m;

}

};

n funcia main()crem un tabel de repartizare cu examinarea linear, ncrcnd acest tabel din fiierul text Stud.txt. Apoi afim acest tabel i cutm careva nregistrri dup cheie. void main()

{

clrscr();

hashing_table hashing_gr("stud.txt", 15);

hashing_gr.show("Group:\n","");

char ch='n';

char surname[21];

while(ch!='y')

{

cout > surname;

hashing_elem e(surname, 2000, 0.0);

hashing_gr.reset_ncomp();

int pos=hashing_gr.search(e);

if(pos


33

else

cout


34

Pentru exemplul nostru tabelul va arta astfel:

Dup cum se vede poziiile 0, 5, 10, 11, 13 au rmas libere. Pe parcursul completrii tabelului n poziiile 1, 2, 6, 7 au avut loc coliziuni. Drept vorbind, coliziunea n poziia 7 pentru nregistrarea tabelar cu cheia White este secundar.

Cercetrile teoretice i experimente pentru cutarea la metoda de repartizare cu examinarea liniar au artat, c pentru repartizarea aleatorie i uniform a nregistrrilor prin funcia de repartizare n intervalul [0, n-1], lungimea medie de cutare nu depinde de lungimea tabelului, dar depinde numai

de factorul de ncrcare nm

, unde m - lungimea tabelului, iar n lungimea vectorului de

reprezentare.

Aceast proprietate este foarte important, mai ales pentru tabele mari. Tabele deterministe, att aranjate ct i cele nearanjate nu posed aceast proprietate. n tabele deterministe lungimea medie de cutare crete cu creterea lungimii tabelului.

Formula aproximativ

22

2)(

D , pentru lungimea medie de cutare la metoda de repartizare

cu examinarea liniar ofer coinciden suficient cu experimentul pentru 0,85.

Formula este obinut n presupunerea repartizrii aleatorie i uniform a nregistrrilor pe poziiile vectorului de reprezentare.

Urmtorul tabel demonstreaz dependena lungimii medie de cutare de factorul de ncrcare .

0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

D() 1.06 1.13 1.21 1.33 1.50 1.75 2.17 3.00 5.5

02 Red, 1980, 450

03 Cyan, 1975, 800

04 Black, 1981, 500

05

07 Gray, 1968, 900

08 White, 1980, 600

09 Yellow, 1988, 300

10

11

13

14 Orange, 1984, 550

00

06 Green, 1987, 350

12 Magenta,1983, 600

01 Blue, 1981, 500

Green

Red

Blue

Gray

Orange

White

Cyan Yellow

Magenta

Black


35

Experimentele arat, c pentru =1 lungimea medie de cutare nu ntrece 20.

Dac distribuirea nregistrrilor pe poziiile vectorului de reflectare nu este uniform, atunci numerele din tabel cresc n mediu cu 1.5 2 ori. Chiar i cu astfel de corecii repartizarea cu examinarea linear are lungimea medie de cutare mai mic, ca alte metode. De exemplu, pentru tabelul din 400 nregistrri i lungimea vectorului de reflectare 512, lungimea medie de cutare pentru tabelul de repartizare cu examinarea liniar, lund n consideraie distribuirea neuniform a nregistrrilor, nu depete 4.5 6. n aceleai condiii lungimea medie la cutarea binar este egal cu 10, iar lungimea medie a parcurgerii secveniale 200.

Neajunsurile: la repartizarea cu examinarea liniar aproape 20% de memorie, rezervat pentru tabel, nu se folosete.

Pentru a calcula lungimea medie de cutare pentru tabelul cu repartizare linear din exemplul nostru, cercetm urmtoarea funcia main(): void main()

{

clrscr();

hashing_table hashing_gr("stud.txt", 15);

hashing_gr.show("Group:\n","");

hashing_elem sample;

long NCOMP=0;

FILE* pf=fopen("stud.txt", "rt");

while(!feof(pf))


{

hashing_gr.reset_ncomp();

if(hashing_gr.search(sample)>=0)

NCOMP+=hashing_gr.get_ncomp();

}

fclose(pf);

cout


36

2. Blue, 1981, 500

3. Red, 1980, 450

4. Cyan, 1975, 800

5. Black, 1981, 500

6.

7. Green, 1987, 350

8. Gray, 1968, 900

9. White, 1980, 600

10. Yellow, 1988, 300

11.

12.

13. Magenta, 1983, 600

14.

15. Orange, 1984, 550


M=10, NCOMP=16, ALS=1.6, m/n=0.666667, D(m/n)=2


Tabele de repartizare cu nlnuirea extern (repartizarea deschis, nlnuirea separat)

n metoda examinrii liniare nregistrrile ce produc coliziuni se includ n poziiile libere aceluiai vector de reflectare. ns pentru aceste nregistrri se poate crea un tabel aparte. n tabelul adugtor nregistrrile se poate lega n lan, ca n liste, pentru uurarea cutrii.

n tabele de repartizare cu nlnuirea extern lungimea medie de cutare pentru distribuirea

uniform i aleatorie a nregistrrilor se definete dup formula:

n

mnmD

21

1,

, n lungimea vectorului de reflectare, m lungimea tabelului.


37

Tabele de repartizare cu nlnuirea intern

ncrcarea poziiilor vectorului de reflectare const din dou etape:

prima etap se aseamn cu repartizarea cu nlnuirea extern;

a doua etap se ndeplinete dup terminarea crerii tabelului primar i celui secundar. Ea const n mutarea lanurilor din tabelul secundarr n poziiile libere ale tabelului primar.

Astfel tabelele din exemplul precedent vor fi transformate n urmtorul tabel:

Prioritatea acestei metode n comparaie cu precedenta economie de memorie, dar neajunsul flexibilitatea mic i algoritmul de ncrcare a tabelului este mai complicat.

Lungimea medie de cutare aici se definete dup aceiai formula: n

mnmD

21

1),(

, aceast

metod se folosete pentru tabele permanente, i pentru tabele temporare, care se ncrc la prima etap, dar se folosesc la alta.

03

04

05

08

10

11

13

00

03 04 05

07 08 09 10 11

13 14

00|Gray, 1968,900

06

12

Primary Table

Secondary Table

Gray 06Green, 1987,35000

Green

14Orange,1984,550

Orange 07White, 1980,600

White

Cyan

02Red, 1980,45001

Red

09Yellow,1988,300 Yellow

12Magenta,1983,600

Magenta

01Cyan, 1975,800 02Black, 1981,500|

Black

01Blue, 1981,50002

Blue


38

Pentru tabele constante nregistrrile cel mai des folosite se nscriu primele, atunci accesrile

lanurilor interioare sunt rare, ce micoreaz lungimea medie de cutare. Este caracter, c la folosirea lanurilor interioare toate poziiile ale vectorului de reflectare pot fi ncrcate (adic m=n), dar lungimea medie de cutare pentru repartizarea uniform i aleatorie a nregistrrilor nu ntrece 1.5.

Tabelele de repartizare aleatorie se ncarc destul de simplu, nu necesit ordonarea nregistrrilor i asigur o cutare rapid. Deaceea aceste tabele deseori se folosesc n practic.

Funcii de repartizare

Timpul calculrii funciei de repartizare f(k) intr n timpul mediu de cutare, deaceiea trebuie de inut cont la alegerea algoritmului, realiznd funcia de repartizare.

O funcie bun de repartizare trebuie s asigure repartizarea uniform a nregistrrilor pe poziiile vectorului de reflectare, fiindc distribuirea neuniform mrete timpul mediu de cutare. ns dac calcularea valorii funciei de repartizare necesit ndeplinirea unui numr mare de operaii, aceasta poate distruge toat economia n timpul cutrii. Deci, algoritmul calculrii funciei de repartizare nu trebuie s fie complicat. S privim cteva metode de calculare a funciei de repartizare:

1. Una din metodele simple se bazeaz pe evidenierea unei pri din codul numeric al cheii. De exemplu, fie dimensiunea maxim ateptat a tabelului de nume simbolice nu ntrece 256. Atunci funcia de repartizare poate avea n calitate de valoare 8 bii, fiindc 256=28. Se poate pur i simplu de a evidenia primii 8 bii din codul binar al identificatorului sau de a lua careva 8 bii din mijlocul codului. Trebuie doar s asigurm cu ct este posibil o distribuire uniform a nregistrrilor prin funcia f(k) n intervalul [0, 255].

05

08

10

11

13

04Gray, 1968,900

Gray 06Green, 1987,35004

Green

14Orange,1984,550

Orange 07White, 1980,600

White

09Yellow,1988,300 Yellow

12Magenta,1983,600

Magenta

00Black, 1981,500

Black

01Blue, 1981,50000

Blue

03Cyan, 1975,800

Cyan

02Red, 1980,45003

Red


39

2. Pentru asigurarea distribuirii uniforme se folosete sumarea codului identificatorului: prima jumtate a codului se sumeaz cu a doua i din rezultat se evideniaz 8 bii. Se poate de asemenea de mprit codul cheii n buci cte 8 bii, de sumat bucile i de pus suma pe modulul 28. Ultima modificare are careva probabilitate teoretic: la presupunerea a statisticei independente de sumare a bucilor se primete repartizarea aproape de uniform.

3. O alt metod de calculare a funciei de repartizare este mprirea. Pentru vectorul de reflectare de lungimea n, cheia se privete ca un numr ntreg i se mparte la mrimea n. Experimentele arat, c restul de la mprire este repartizat aproape uniform n intervalul [0, n-1] i poate fi folosit ca valoarea funciei de repartizare.

Verificarea experimental a metodelor descrise pentru tabelele de repartizare cu examinarea linear a artat c evidenierea simpl a bucii din codul identificatorului mrete lungimea medie de

cutare n comparaie cu cea teoretic, definit dup formula:

22

2)(

D , n 4-5 sau i mai

multe ori. Lungimea medie de cutare pentru metoda de sumare a bucilor dup modulul 2k aproape de dou ori mai mare ca teoretic, dar pentru mprirea, lungimea medie de cutare practic coincide cu teoretic pentru 8.85.


40

3. TEHNICI DE SORTARE

3.1. Noiuni generale

Sortarea este operaia de aranjare a elementelor unui vector dup valoarea

cheilor, pentru care este definit relaia de ordine.

Tradiional difer sortarea intern de sortarea extern. Sortarea intern prelucreaz datele pstrate n memoria operativ a calculatorului, dar sortarea extern, opereaz cu datele care sunt pstrate n fiiere.

n cazul sortrii interne se tinde la minimizarea numrului de comparaii i permutri ale elementelor.

n cazul sortrii externe factorul hotrtor este numrul de operaii de intrare i ieire. n acest caz numrul de comparaii trece pe planul doi, totui i el se i-a n consideraie.

Cazul sortrii interne

Presupunem, c datele supuse sortrii se pstreaz n memoria operativ ntr-un vector t. Fiecare element t[i] al acetui vector este obiect al clasei parametrizate el n care sunt suprancrcai operatorii de comparaie. Deci, sunt admise expresii:

t[i]


41

Definiia 4. Algoritmul sortrii se numete stabil, dac el niciodat nu schimb

ordinea relativ n vector la oricare 2 elemente cu cheile egale. Adic pentru orice pereche i, j: ii', j>j' => i'


42

{

protected:

int n; // numrul de elemente ale vectorului

el t[NMAX]; // elemente ale vectorului

long ncomp; // contorul comparaiilor

public:

vector()

{

n=0, ncomp=0;;

}

vector(char* file_name)

{

FILE* pf;


n=0, ncomp=0;

while(!feof(pf))

if(t[n].fscanf_el(pf)>0)

n++;

fclose(pf);

}

virtual void show(const char* opening, const char* ending)

{

clrscr();

cout


43

int search(el e)

{

int position = -1;

for(int i=0; (position==-1) && it[i])

position=i;

return position;

}

int get_n()

{

return n;

}

long get_ncomp()

{

return ncomp;

}

void reset_ncomp()

{

ncomp=0;

}

protected:

void error(char* message)

{

cerr


44

3.3. Sortarea prin interschimbare

Metoda de sortare prin interschimbare (engl. Exchange sort) const n parcurgerea elementelor ale vectorului, n aa mod ca fiecare parcurgere micoreaz numrul de inversii, pn atunci cnd nu rmne nici o inversie. Problema const n cutarea urmtoarei inversiei (i, j).

Schematic: while (este_inversie (i, j))

swap(i, j);

Sortarea prin interschimbare const n modificri succesive de tip t[i]t[j], pn cnd elementele vectorului nu vor deveni n ordine cresctoare.

Din aceast categorie fac parte metoda bulelor (bubblesort) unul din cei mai slabi algoritmi de sortare i sortarea rapid (quicksort) unul din cei mai buni algoritmi de sortare.

Sortarea prin metoda bulelor

Metoda bulelor const n compararea t[i] cu t[i+1], dac ordinea este bun se compar t[i+1] cu t[i+2], dac ordinea nu este bun se interschimb t[i] cu t[i+1] i apoi se compar t[i+1] cu t[i+2]. Dup prima parcurgere a vectorului, pe ultima poziie ajunge elementul avnd valoarea cea mai mare, dup a doua parcurgere ajunge urmtorul element pe penultima poziie, etc.

Algoritmul are complexitatea O(n2).

void bubble_sort()

{

BOOLEAN inversion;

do

{

inversion = FALSE;

for(int i=0; it[i+1])

{

swap(i,i+1);

inversion = TRUE;

}

}

while (inversion);

}

Complexitatea minim este O(n). Dac vectorul iniial este deja sortat, variabila inversion niciodat nu va primi valoarea TRUE.

Complexitatea maxim este O((n-1)2)=O(n2). Dac elementul minimal are indicele iniial n-1, atunci va fi nevoie de n-1 executri a ciclului exterior, ca s-i dm indicele 0.

Pentru fiecare executare a ciclului exterior cu n-1 comparaii: (n-1)*(n-1)=(n-1)2 comparaii.


45

Complexitatea medie de asemenea este egal cu O(n2), dac elementul minimal cutat se afl aleator printre indicii 0, 1,, n-1.

Exerciiu: Este posibil mbuntirea acestui algoritm, ce nu schimb totui esenial complexitatea. mbuntii algoritmul de mai sus, prescurtnd cu un element parcurgerea de rnd fa de precedent.

Metoda bulelor este unul din cei mai ri algoritmi de sortare. Neajunsul const n aceea c la fiecare pas elementul urmtor se compar numai cu vecinul su urmtor.

3.4. Sortarea rapid

Sortarea rapid (quicksort) a fost propus de C.A.R. Hoare i folosete principiile Divide Et Impera i Echilibru.

Ideea metodei este urmtoarea: se selecteaz un element arbitrar din vector numit principal (sau pivot) i se rearanjeaz vectorul n doi subvectori, astfel nct cel din stnga are toate elementele mai mici sau egale dect pivotul, iar cel din dreapta mai mari sau egale ca pivotul. Procedeul se reia n subvectorul din stnga i apoi n cel din dreapta, etc. Procedeul se termin cnd se ajunge la subvectori dintr-un singur element.

n baza clasei generice vector declarm clasa derivat vector_quicksort, dotat cu algoritmul de sortare rapid. //

// c l a s s " v e c t o r q u i c k s o r t"

//

template class vector_quicksort: public vector

{

public:

vector_quicksort(char* file_name):

vector(file_name)

{

}

void quicksort(int i=0, int j=-1)

{

if(j>=n || j==-1)

j=n-1;

if(ij)

i=0;

quicksort_intern(i, j);

}

protected:

void quicksort_intern(int i, int j);

int divide(int i, int j);


46

};

Presupunem c exist funcia numit divide(), care ntr-un anumit fel alege elementul principal cu cheia K i rearanjeaz vectorul astfel, ca elementul principal primete un indice imain, iar toate elementele cu cheile K se aranjeaz de la stnga (adic au indicii < imain), dar toate elementele cu cheile K se aranjeaz de la dreapta (adic au indicii >imain):

Avem aici un caz tipic recursiv:

parametrizarea: se precaut pentru subvectorul t[i]t[j]; pentru vectorul iniial i=0, j=n-1;

cazul trivial: i=j (nu avem ce sorta);

trecerea de la cazul general la un caz mai simplu, care are loc datorit funciei divide().

Dac exist o astfel de funcie, atunci sortarea rapid imediat se obine n form recursiv: template

void vector_quicksort::quicksort_intern(int i, int j)

{

if (j>i)

{

int imain=divide(i,j);

quicksort_intern(i,imain-1);

quicksort_intern(imain+1,j);

}

}

Algoritmul are loc pentru ambele ordine de apeluri recursive.

Schema metodei de divizare n timpul O(n):12 3 15 10 2 20 4

principal

elementul

Prelucrm vectorul din stnga i din dreapta pn atunci, pn cnd din stnga nu va fi gsit elementul cu cheia, ce ntrece cheia elementului principal, dar din dreapta elementul cu cheia mai mic ca cheia elementului principal. Dup aceasta se poate de schimbat cu locurile aceste dou elemente, lichidnd prin asta inversia. Apoi astfel de prelucrare dubl, din stnga i din dreapta, continu cu poziiile deja gsite. Vectorul se socoate mprit, cnd poziiile din stnga i din dreapta se ntlnesc. Valoarea comun a lor notm prin imain.

imain 0 n-1

imain-1

elementul principal t[imain]

elemente t[imain] elemente t[imain]

imain+1


47

Evident, c complexitatea divizrii nu ntrece O(n), sau mai bine spus O(j-i) cnd divizarea se aplic la subvectorul t[i]t[j].

Sfaturi practice la alegerea elementului principal

Alegerea elementului principal trebuie s fie n aa fel ca s se micoreze probabilitatea cazului cnd dup divizarea subvectorii (segmentele) s difere mult dup lungime.

Prima strategie: la fiecare divizare alegerea aleatorie (folosind funcia-generator de numere aleatoare) a valorii indicelui elementului principal dintre i, i+1, , j. Neajunsul acestei metode - cheltuieli suplimentare de timp necesare pentru aceast operaie.

A dou strategie: n calitate de elementul principal se alege elementul cu valoarea medie dintr-un set nu mare de elemente. Cel mai simplu i mai uor de examinat setul ce conine trei elemente cu indicii respectiv i, j i (i+j)/2.

Ambele metode micoreaz probabilitatea cazului catastrofal O(n2), doar totui aa situaie nu este exclus. Sortarea rapid ntotdeauna poate s se degenereze. Paradoxal, c sortarea rapid este unul din cei mai buni algoritmi de sortare intern, dar suntem nevoii s ne refuzm de ea n probleme unde limitele superioare de timp (de tip knlog2n) necesare pentru sortarea, sunt critice.

Algoritmul divizrii

Exist mai multe variante ale algoritmului de divizare. Toate din ele urmresc cel puin dou scopuri:

a accelera ciclurile interioare;

a prevedea caracterul aleator a vectorului. Adic de a exclude introducerea ntmpltoare a ordinei n segmentele de divizare din punct de vedere al productivitii generale a algoritmului. Adic trebuie s ne refuzm de orice ncercare de a sorta n procesul de divizare.

Sedgewick R. E. a propus urmtoarea metod de divizare:

a) punem elementul principal n poziia i (l schimbm dac este necesar cu elementul t[i]).

b) divizm subvectorul t[i+1], t[i+2], t[j], cu ajutorul valoarei elementului principal t[i] lsnd pe t[i] la locul su. Se primete divizarea cu poziia intermediar imain, de exemplu:

i j i+1

i j imain

imain+1 imain-1

elemente t[i] elemente t[i]


48

c) schimbm cu locurile elementul t[i] cu elementul t[imain] i dm valoarea imain ca

rezultatul ntors de ctre funcia divide.

template int vector_quicksort::divide(int i, int j)

{

int imain, jmain, imed;

imed =(i+j)/2;

imain = (ncomp++, t[i] < t[imed]) ?

((ncomp++, t[imed] < t[j]) ?

imed

:

(ncomp++, t[i] < t[j]) ? j : i)

:

((ncomp++, t[imed] > t[j]) ?

imed

:

(ncomp++, t[i] > t[j]) ? j : i);

if(imain > i)

swap(i, imain);

imain = i+1, jmain = j;

while(imain < jmain)

{

while((imain < jmain)&&(ncomp++, t[imain] imain)&&(ncomp++, t[jmain] >= t[i]))

jmain--;

if(imain < jmain)

swap(imain, jmain);

}

if(ncomp++, t[imain] > t[i])

imain--;

if(imain > i)

swap(i, imain);

i j imain

imain+1 imain-1

elemente t[imain] elemente t[imain] elementul principal


49

return imain;

}

Este clar c funcia divide() are complexitatea O(n). Ciclul exterior while(imain < jmain)

{

}

verific fiecare element al vectorului t[0], t[i], t[n-1] cel mai mult de dou ori, dar restul operaiilor cere un timp fix.

n funcia main() crem un vector si-il sortatm prin metoda quicksort: void main()

{

clrscr();

vector_quicksort gr("Stud.txt");

gr.show("Unsorted group:\n","");

gr.quicksort();

gr.show("Group sorted by name:\n","");

cout


50

4. Gray, 1968, 900

5. Green, 1987, 350

6. Magenta, 1983, 600

7. Orange, 1984, 550

8. Red, 1980, 450

9. White, 1980, 600

10. Yellow, 1988, 300

End of vector. Press any key ...

n=10, ncomp=39, n*log2(n)=33.2193, n*n=100


Dac vrem s sortm dup anul de natere, atunci declarm n baza clasei usual_elem clasa year_elem la care suprascriem funcia cmp(). //

// c l a s s "y e a r _ e l e m"

//

class year_elem : public usual_elem

{

public:

year_elem()

{

}

year_elem(char* init_name, int init_year, double init_salary):


{

}

virtual int cmp(elem& e2)

{

int result;

if(this->year < ((year_elem&)e2).year)

result=-1;

else

if(this->year > ((year_elem&)e2).year)

result=1;

else

result=0;

return result;

}

};

n funcia main() instaniem clasa generic vector_quicksort cu clasa-argument year_elem.


51

void main()

{

clrscr();



gr.quicksort();

gr.show("Group sorted by year:\n","");

cout


52

n sfrit declarm n baza clasei usual_elem clasa derivat salary_elem care compar obiecte dup salariu. //

// c l a s s "s a l a r y _ e l e m"

//

class salary_elem : public usual_elem

{

public:

salary_elem()

{

}

salary_elem(char* init_name, int init_year, double init_salary):


{

}

virtual int cmp(elem& e2)

{

int result;

if(this->salary < ((salary_elem&)e2).salary)

result=-1;

else

if(this->salary > ((salary_elem&)e2).salary)

result=1;

else

result=0;

return result;

}

};

n funcia main() instaniem clasa generic vector_quicksort cu clasa-argument salary_elem. void main()

{

clrscr();



gr.quicksort();

gr.show("Group sorted by salary:\n","");

cout


53


54

numrul maxim P(n) de elemente nscrise simultan n stiv, care este i adncimea maxim a apelurilor recursive, satisface relaiei

2

1)(n

PnP , adic )0(1...111)(2log

PnPn

Lund n consideraie, c P(0)=0, obinem c P(n)i)

{


if(imain-i > j-imain)

{//ncepem cu intervalul stng



}

else

{//ncepem cu intervalul drept



}

}

}

Deoarece modificarea introdus nu va schimba afirile obinute prin exemplele de sortare precedente, nu le mai repetm.

Complexitatea spaial se reduce n aa fel la mrimea P(n) ).(log2 nO Apreciem complexitatea

temporal T(n). Fiindc divizarea are complexitatea O(n), avem:

)1()0()()( imainnTimainTnOnT . Deci, totul depinde de imain, adic cum vectorul va

fi divizat de ctre funcia divide().

O situaie ideal care ar putea fi obinut prin aplicarea principiului de echilibru, const n

segmentarea vectorului aproximativ n dou pari egale, aa ca 2n

imain . Atunci

),log()(...)()(...8

24

22

2)(

42

22)(

22)()(

2 nnOnOnOnOn

Tn

On

OnO

nT

nOnO

nTnOnT


55

fiindc T(0)=0. Deci, T(n)=O(nlog2n), precum coeficientul la nlog2n este acelai ca i coeficientul pe lng n la complexitatea mpririi.

Aadar, metoda obine O(nlog2n) ce este limita de jos pentru complexitatea algoritmilor de sortare bazai pe compararea cheilor.

Dac divizarea sistematic se obine lng primul sau lng ultimul elemente ale subvectorilor cercetai (adic permanent imain=i, sau imain=j), atunci fiecare dat rmne de sortat o parte a subvectorului, n care numrul de elemente este cu o unitate mai mic dect subvectorul precedent, i rezult c complexitatea va fi )()1(...)1()()1()1()()( 2nOOnOnOnTOnOnT .

n acest caz sortarea rapid are complexitatea teoretic asemntoare cu complexitatea celor mai ri algoritmi de sortare, de exemplu sortarea prin metoda bulelor. Dar complexitatea practic probabil va fi i mai mare, din cauza timpului necesar pentru realizarea recursiei dirijate de stiv. Pentru sortarea rapid este artat teoretic c complexitatea medie apreciat pentru probabilitile egale a tuturor permutrilor este egal cu O(nlog2n) cu aproximativ 2nlog2n comparaii a cheilor, de asemenea este artat c probabilitatea celui mai nefavorabil caz cu complexitatea O(n2) este destul de mic.

Posibilitatea celui mai nefavorabil caz nu este exclus cnd datele sunt deja sortate sau parial sortate (poate fi i n ordine invers).

Paradoxul sortrii rapide n contrastul cu sortarea prin inserie sau chiar prin metoda bulelor, const n aceea c sortarea rapid i pierde calitatea la vectori parial ordonai. Faptul acesta este incomod, fiindc necesitatea de a sorta datele aproape sortate destul de des se ntlnete n practic.

mbuntirea sortrii rapide

Ca sortarea rapid s devin real un algoritm efectiv, ea mai cere nc o mbuntire. Este evident, c n versiunile precedente recursia i alegerea elementului principal devin destul de grele pentru subvectori mici. Sortarea rapid nu poate fi aplicat la vectori mici. De aceea recursia trebuie oprit cnd dimensiunea subvectorului devine mai mic dect careva constant, numit prag. Dup aceasta se folosete metoda, eficacitatea creia poate s se mbunteasc la datele parial sortate, de exemplu sortarea prin inserie simpl.

D. Knuth a obinut c valoarea optimal teoretic a pragului este egal cu 9.

n practic rezultatele bune ne dau valorile pragului de la 8 pn la 20, iar valoarea optim se conine ntre 14 i 16. //

// c l a s s " v e c t o r o p t i m q u i c k s o r t "

//

template class vector_optim_quicksort:

public vector_quicksort

{

public:

vector_optim_quicksort(char* file_name, int threshold_init=15):


56

vector_quicksort(file_name)

{

threshold=threshold_init;

if(threshold=n || j==-1)

j=n-1;

if(ij)

i=0;

quicksort_intern(i, j);

}

protected:

int threshold;

void quicksort_intern(int i, int j);

void insertsort(int i, int j);

};

template

void vector_optim_quicksort::quicksort_intern(int i, int j)

{

if(j-i+1>threshold)

{


if(imain-i > j-imain)

{



}

else

{



}

}

else

insertsort(i, j);

}


57

template

void vector_optim_quicksort::insertsort(int i, int j)

{

for(int k = i+1; ki)&&(ncomp++, t[l]


58

2. Red, 1980, 450

3. Blue, 1981, 500

4. Gray, 1968, 900

5. Orange, 1984, 550

6. White, 1980, 600

7. Cyan, 1975, 800

8. Yellow, 1988, 300

9. Magenta, 1983, 600

10. Black, 1981, 500


Group sorted by year:

1. Gray, 1968, 900

2. Cyan, 1975, 800

3. Red, 1980, 450

4. White, 1980, 600

5. Blue, 1981, 500

6. Black, 1981, 500

7. Magenta, 1983, 600

8. Orange, 1984, 550

9. Green, 1987, 350

10. Yellow, 1988, 300


n=10, ncomp=37, n*log2(n)=33.2193, n*n=100

Pentru vectorul concretizat cu clasa salary_elem Unsorted group:

1. Green, 1987, 350

2. Red, 1980, 450

3. Blue, 1981, 500

4. Gray, 1968, 900

5. Orange, 1984, 550

6. White, 1980, 600

7. Cyan, 1975, 800

8. Yellow, 1988, 300

9. Magenta, 1983, 600

10. Black, 1981, 500


Group sorted by salary:

1. Yellow, 1988, 300

2. Green, 1987, 350

3. Red, 1980, 450

4. Blue, 1981, 500

5. Black, 1981, 500


59

6. Orange, 1984, 550

7. White, 1980, 600

8. Magenta, 1983, 600

9. Cyan, 1975, 800

10. Gray, 1968, 900


n=10, ncomp=33, n*log2(n)=33.2193, n*n=100

n urmtorul tabel este prezentat numrul de comparri efectuate la sortarea obiectelor vector_optim_quicksort create pe baza fiierului stud.txt pentru diferite valori ale pragului i clase de concretizare.

Cmpul de sortare Prag

name year salary

0 39 42 43 1 39 42 43 2 37 37 41 3 35 37 38 4 32 37 33 5 29 34 28 6 29 34 28 7 29 34 28 8 29 34 28 9 29 34 28

10 30 28 25 11 30 28 25

Analiza rezultatelor prezentate n acest tabel rmne ca exerciiu.

3.5. Sortarea prin inserie

Inserie simpl

Ideea principal a sortrii prin inserie (engl. Insert sort) este simpl: alegem careva element, sortm celelalte elemente, inserm elementul ales (adic l includem) la locul potrivit printre altele deja sortate. void recursivinsertsort(int i, int j)

{

if(j>i)

{

recursivinsertsort(i, j-1);

for(int l=j; (l>i)&&(ncomp++, t[l]


60

n forma nerecursiv sortarea prin inserie se scrie astfel: void insertsort(int i, int j)

{

int k;

for(k=i+1; ki)&&(ncomp++,t[l]


61

Dac vectorul iniial este total sortat, atunci complexitatea este egal O(n). n cazul general algoritmul folosete orice ordine parial, ce se conine n vector. Dac mai lum n consideraie i simplitatea algoritmului, ajungem la concluzie c acest algoritm este cel mai bun pentru finisarea lucrului a metodelor mai pretenioase, cum de exemplu este sortarea rapid. Adic pentru finisarea lucrului algoritmilor, care destul de repede mpart vectorul n mai multe pri aproape sortate, dar cer destul de mult timp i se nduesc la sortarea final a subvectorilor mici.

Metoda lui Shell

Neajunsul esenial al sortrii prin inserie simpl const n aceia, c la fiecare pas de mutare elementul care se mut, se deplaseaz doar cu o poziie. Fiecare din aceste mutri elimin exact o inversie. n rezultat numrul total de mutri a datelor este egal cu numrul iniial de inversii, care n

probabilitatea medie este: 4

)1(2*2

)1(2

2

nnnncn .

Donald L. Shell n anul 1959 a propus n loc de inseria sistematic a elementului cu indicele i n sub vectorul elementelor precedente (modul care contrazice principiului de echilibru), de a include acest element n sublist, coninnd elemente cu indicii i-h, i-2h, i-3h, , unde h o constant pozitiv (pas).

Astfel se formeaz vectorul, n care hseria elementelor (elemente care se afl la distana h unul de la altul) se sorteaz deoparte.

Dup ce au fost sortate deoparte neintersectatele hserii, procesul ncepe cu valori noi h'


62

Crem n baza clasei generice vector clasa generic vector_Shellsort dotat cu algoritmul de sortare prin metoda lui Shell: //

// c l a s s "v e c t o r _ S h e l l s o r t "

//

template class vector_Shellsort: public vector

{

public:

vector_Shellsort(char* file_name): vector(file_name)

{

}

void Shellsort();

};

template

void vector_Shellsort::Shellsort()

{

int h;

int i, j, k;

el tmp;

//definirea pasului iniial

h=1;

while(h


63

}

}

//micorarea incrementului

h=h/3;

} while(h>0);

}

Observaii: 1. n locul recalculrii pailor secveniali h se poate de obinut pe ei din calcularea preventiv i

stocarea ntr-un vector adugtor:

2. Se poate de unit buclele dup k i dup i, nlocuind schimburi cu semischimburi;

3. Sortarea prin metoda lui Shell este instabil, i problema aceasta nu poate fi rezolvat uor.

n funcia main() instaniem clasa vector_Shellsort concretizat cu clasa usual_elem, afim vectorul iniial, l sortm prin metoda lui Shell, afim vectorul sortat i informaii legate de aprecierea complexitii: void main()

{

clrscr();

vector_Shellsort gr("Stud.txt");


gr.Shellsort();


cout


64

8. Yellow, 1988, 300

9. Magenta, 1983, 600

10. Black, 1981, 500


Group sorted by name:

1. Black, 1981, 500

2. Blue, 1981, 500

3. Cyan, 1975, 800

4. Gray, 1968, 900

5. Green, 1987, 350

6. Magenta, 1983, 600

7. Orange, 1984, 550

8. Red, 1980, 450

9. White, 1980, 600

10. Yellow, 1988, 300


n=10, ncomp=30, n*log2(n)=33.2193, n*n=100

Dup cum se vede numrul de comparri a coincis cu numrul de comparri la inserie simpl.

nlocuim n funcia main() clasa usual_elem cu clasa year_elem, atunci vom obine: Unsorted group:

1. Green, 1987, 350

2. Red, 1980, 450

3. Blue, 1981, 500

4. Gray, 1968, 900

5. Orange, 1984, 550

6. White, 1980, 600

7. Cyan, 1975, 800

8. Yellow, 1988, 300

9. Magenta, 1983, 600

10. Black, 1981, 500


Group sorted by year:

1. Gray, 1968, 900

2. Cyan, 1975, 800

3. Red, 1980, 450

4. White, 1980, 600

5. Blue, 1981, 500

6. Black, 1981, 500

7. Magenta, 1983, 600

8. Orange, 1984, 550

9. Green, 1987, 350

10. Yellow, 1988, 300


65


n=10, ncomp=28, n*log2(n)=33.2193, n*n=100


Dac vom nlocui n funcia main() clasa year_elem cu clasa salary_elem, vom obine: Unsorted group:

1. Green, 1987, 350

2. Red, 1980, 450

3. Blue, 1981, 500

4. Gray, 1968, 900

5. Orange, 1984, 550

6. White, 1980, 600

7. Cyan, 1975, 800

8. Yellow, 1988, 300

9. Magenta, 1983, 600

10. Black, 1981, 500


Group sorted by salary:

1. Yellow, 1988, 300

2. Green, 1987, 350

3. Red, 1980, 450

4. Blue, 1981, 500

5. Black, 1981, 500

6. Orange, 1984, 550

7. White, 1980, 600

8. Magenta, 1983, 600

9. Cyan, 1975, 800

10. Gray, 1968, 900


n=10, ncomp=25, n*log2(n)=33.2193, n*n=100


Metoda lui Shell esenial ntrece inseria simpl pentru n mai mari de 100. Numrul necesar de comparri n mediu are ordinul 1.66n1.25 pentru un n destul de mare. Analiznd tabelul urmtor:

n 1.66n1.25 nlog2n

10 29,5 33.2193

100 525 664

1000 9335 9966

10000 166000 132877

105 2,95*106 1,66*106

106 5,25*107 1,99*107


66

vedem c metoda lui Shell rezist competiia cu metodele O(nlog2n) pn la n=105.

Sortarea Shell ru se adapteaz la sistemele cu memorie virtual (adic care acoper vectorul cu intervale largi).

3.6. Sortarea prin selecie

Selecie simpl

Ideea acestei metode de sortare (engl. Selection sort) este foarte simpl: se selecteaz elementul maxim din tablou i i se schimb locul cu ultimul element; n continuare se caut elementul maxim pn la ultimul i i se schimb cu penultimul elementul. La fiecare parcurgere se examineaz toate elementele ale vectorului care au rmas neordonate, elementul maxim din care va fi alturat la cele ordonate.

n form nerecursiv selecie simpl const din n-1 etape. La etapa k se caut elementul cu cheia maxim dintre elementele care nu sunt ordonate pn la capt i-l leag la poziia n-k.

Exemplu: void selectsort()

{

int imax, i, j;

for(i=n-1; i>0; i--)

{

imax=i;

for(j=0; jt[imax])

imax=j;

swap(i,imax);

// aici sub vectorul ]1[][ ntit este sortat(invarianta buclei)

}

}

Acest algoritm are complexitatea O(n2) n toate cazurile. Numrul de ndepliniri a ciclului interior

este egal 2

)1( nn.

3.7. Sortarea arborescent (piramidal, heapsort)

Sortarea arborescent provine de la selecia simpl. Neajunsul principal al sortrii prin selecie simpl const n aceea c comparaiile fcute la fiecare etap dau mult mai multe informaii dect cele care se folosesc efectiv pentru a pune elementul curent la locul potrivit. Pentru a obine o mbuntire esenial, trebuie de folosit o structur de date mai dezvoltat, permindu-i pe ct se poate, s pstreze informaia, obinut secvenial la verificare. De exemplu, dac t[i]>=t[k], iar t[k]>=t[j], atunci t[i]>=t[j].


67

Sortarea arborescent folosete un arbore binar concret, din care este uor de extras elemente cu chei maxime. Acest arbore se numete arbore de maximizare, el posed proprietatea c elementul n fiecare vrf are cheia mai mare sau egal dect cheile ale fiilor dac aceti fii exist. La aplicarea arborilor de maximizare apare problema de reorganizare cnd doi subarbori ai rdcinii sunt de maximizare, iar arborele ntreg nu este de maximizare.

n acest caz pentru reorganizarea arborelui, adic pentru l preface n arbore de maximizare, trebuie s facem civa pai. ncepnd de la rdcin ne deplasm n direcia maximal interschimbnd elementele.

Arborele binar plin, adic, la care pn la orice nivel exist toate nodurile cu posibila excepie pentru cele mai drepte noduri ale ultimului nivel. Astfel de arbore poate fi reprezentat sub form de vector.

Nodului cu indice i i corespunde nodurile cu indicii 2*i+1 (fiul stng, dac 2*i+1


68

{

}

void heapsort();

protected:

void reorganization(int i, int j);

void planting();

void maxtreesort();

};

Descriem funcia de reorganizare pentru subarbori.

Fie: i, j o pereche de indici astfel c 0


69

aa fel complexitatea reorganizrii este O(log2(j-i+1)), mai concret ea se ndeplinete cu 2(log2(j-i+1)) comparaii i log2(j-i+2) interschimbri.

Algoritmul de sortare arborescent const din dou etape fiecare din care folosete reorganizarea:

Plantare (planting) transform vectorul iniial n vectorul cu arbore de maximizare;

Sortarea arborelui de maximizare (maxtreesort) face sortarea lund n consideraie arborii de maximizare.

template void vector_heapsort::heapsort()

{

planting();

maxtreesort();

}

La plantare reorganizarea se aplic la aa indicii i subarborii la care, dac exist, sunt arbori de maximizare. ncepem de la elementul t[(n-1)/2], fiindc elementul cu indice mai mare nu are subarbori. template void vector_heapsort::planting()

{

for(int i=(n-1)/2; i>=0; i--)

reorganization(i, n-1);

}

Complexitatea plantrii poate fi dedus din complexitatea reorganizrii, adic din subvectorii cercetai, corespunztori vrfurilor arborelui:

1. adncimea sub vectorului h=[log2n]+1 vectorul t[0]t[n-1];

2. adncimea sub vectorului h-1 vectorii t[1]t[n-1], t[2]t[n-1];

3. adncimea sub vectorului h-2 vectorii t[3]t[n-1], t[4]t[n-1], t[5]t[n-1],

t[6]t[n-1];

4.

n aa fel complexitatea poate fi scris n forma: O(1*h*2*(h-1)+...+2h-2*2)=O(2h-1)=O(n).

Dup plantare t[0] a devenit elementul maximal, el trebuie sa fie interschimbat cu elementul t[n-1], dup ce rmne de sortat sub vectorul t[0]t[n-2], dar acest sub vector va fi arbore de maximizare cu unic excepie posibil, privind elementul t[0] (precedentul t[n-1]), de aceea la acest subvector aplicm reorganizarea, pentru a obine maximul subvectorului n t[0], pe care interschimbm cu t[n-2], etc. template void vector_heapsort::maxtreesort()

{

for (int i=(n-1);i>=1;i--)

{

swap (0, i);

reorganization(0, i-1);

}


70

}

Complexitatea acestei proceduri este )()(1

1,0

n

iihOnT , unde h0,i - adncimea corespunztoarea

subarborelui t[0]t[i], adic 1log 2,0 ih i . Deci, obinem c T(n)=O(nlog2n). n aa fel complexitatea algoritmului de sortare arborescenta este O(n+nlog2n)=O(nlog2n).

Aceasta este complexitatea att maximal ct i cea medie fiindc nimic n-am presupus despre repartizarea iniial a elementelor. Sortarea arborescent este cel mai sigur algoritm de sortare .

void main()

{

clrscr();

vector_heapsort gr("Stud.txt");


gr.heapsort();


cout


71

6. Magenta, 1983, 600

7. Orange, 1984, 550

8. Red, 1980, 450

9. White, 1980, 600

10. Yellow, 1988, 300


n=10, ncomp=41, n*log2(n)=33.2193, n*n=100

nlocuim n funcia main() clasa usual_elem cu clasa year_elem, atunci vom obine: Group sorted by year:

1. Gray, 1968, 900

2. Cyan, 1975, 800

3. White, 1980, 600

4. Red, 1980, 450

5. Blue, 1981, 500

6. Black, 1981, 500

7. Magenta, 1983, 600

8. Orange, 1984, 550

9. Green, 1987, 350

10. Yellow, 1988, 300


n=10, ncomp=38, n*log2(n)=33.2193, n*n=100

nlocuim n funcia main() clasa year_elem cu clasa salary_elem, atunci vom obine: Group sorted by salary:

1. Yellow, 1988, 300

2. Green, 1987, 350

3. Red, 1980, 450

4. Black, 1981, 500

5. Blue, 1981, 500

6. Orange, 1984, 550

7. White, 1980, 600

8. Magenta, 1983, 600

9. Cyan, 1975, 800

10. Gray, 1968, 900


n=10, ncomp=40, n*log2(n)=33.2193, n*n=100



72

3.8. Comparaii practice ai diferiilor algoritmi de sortare

S-au folosit diferite principii de sortare i poate prea greu de ales algoritmul potrivit. El depinde de muli factori. Dar fiecare din aceti algoritmi se poate uor i repede de reprogramat. De aceea adresarea la Bubblesort din cauza c este uor de scris, nu poate fi justificat nicicum.

La alegerea algoritmului de sortare pot fi date urmtoarele recomandri: - pentru n mici (100) i poate mai mari, dac nu ncercm s ctigm cteva microsecunde,

sortarea prin inserie simpl ne d un rezultat destul de bun, n special dac datele sunt deja

parial sortate;

- pentru n de la cteva sute pn la cteva mii, metoda Shell ne d un rezultat excelent. n

sistemele cu memorie virtual ea nu trebuie folosit, dac vectorul se aranjeaz pe un numr

mare de pagini;

- pentru n >100 (de exemplu) quicksort este probabil, cel mai bun algoritm n caz general; dar

el poate s creasc pn la O(n2) cu probabilitatea ne nul (probabilitatea totui este destul

de mic, dac este bine scris divizarea);

- pentru n>100 sortarea Heapsort cere aproape de dou ori mai mult timp n mediu, fa de

sortare rapid, dar este garantat comportarea ei cu O(nlogn).

n comparaiile experimentale ale diferitor metode de sortare, a fost folosit un vector real, n care fiecare element era cheia lui proprie. Vectorul a fost alctuit din elemente aleatorie, ceia ce puin a favorizat sortarea rapid.

Observaie: Concluziile pot fi diferite n dependen de preul de comparare a cheilor ce se compar, de modul de interschimbare a elementelor, i de alte operaii:

N

metoda

10 100 1000 10000 25000 50000

Bublesort 0,16 20 2400

Extractsort 0,12 7,3 680

Insertsort 0,12 6,7 610

Shellsort 0,07 2 37 600 1800 4200

Heapsort 0,2 3,5 50 660 1830 3960

Quicksort 0,07 2 28 365 1000 2140


73

4. STRUCTURI DINAMICE DE DATE

4.1. Noiune de structura dinamic de date

Definiie:

Structura dinamic de date (SDD) este o aa structur de date numrul de elemente la care se schimb n procesul de utilizare a ei.

Se adaug elemente noi, se elimin careva elemente din cele existente, precum adugrile i eliminrile se efectueaz n mod independent unele de altele.

Pentru structuri dinamice de date este de caracter amplasarea elementelor mprtiat prin memorie n dependen de alocarea locurilor pentru ele n timpul de adugare a lor.

Tipuri de structuri dinamice de date se difer ntre ele prin organizarea legturilor ntre elementele care ntr n componena SDD, prin ordine de adugare (nscriere) a elementelor noi, prin ordine de accesare a elementelor, prin ordine de nlturare (tergere) a elementelor existente,

Date post:	15-Oct-2015
Category:	Documents
Upload:	victorsoltan
View:	104 times
Download:	3 times

Sd Modul Ifc Rom

Documents