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 - 2014Structuri de date (n baza C++): Suport de curs

S.Pereteatcu, A.Pereteatcu

Recomandat de ctre Comisia tiinifico-Metodic a Unstitutului de Formare Continu, Process+verbal nr.1 din 14 iunie 2012

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

2

Structuri de date (n baza C++): Suport de curs

S.Pereteatcu, A.Pereteatcu

CUPRINS

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

1.1.Noiuni generale .............................................................................................................4

1.2.Clase de baz..................................................................................................................52.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).................................................................293. 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....................................................724. 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............................................................................................................................1185.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...............................................................................................................1536.ACTIVITI........................................................................................................................161

I Declararea claselor de baz....................................................................................161

II Lucrul cu tabele....................................................................................................162

III Sortri.................................................................................................................162

IV Structuri dinamice de date...................................................................................163

V Matrice ................................................................................................................165BIBLIOGRAFIE........................................................................................................................166

3Structuri de date (n baza C++): Suport de curs

S.Pereteatcu, A.Pereteatcu

Program = Algoritm + Structuri de date

Niklaus Wirth, 1976

INTRODUCERE N STRUCTURI DE DATE

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:

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.

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.

4Structuri de date (n baza C++): Suport de curs

S.Pereteatcu, A.Pereteatcu

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;

}

5Structuri de date (n baza C++): Suport de curs

S.Pereteatcu, A.Pereteatcu

int operator < (elem& e2)

{

return cmp(e2)