Inapoi la lista selectata

CUPRINS

CUPRINS

 

Prefaţă

V

1.  Complexitatea algoritmilor

1

1.1.  Aspecte generale

1

1.2.  Evaluarea complexităţii

2

1.3.  Clase de complexitate

7

2.  Structuri de date – Aspecte generale

9

2.1.  Caracteristici ale structurilor de date

9

2.2.  Structuri ordonate şi structuri înlănţuite

10

3.  Tablouri

11

3.1.  Aspecte generale

11

3.2.  Exerciţii

12

4.  Liste simple

15

4.1.  Aspecte generale

15

4.2.  Operaţii cu liste simple

16

5.  Liste liniare

17

5.1.  Aspecte generale

17

5.2.  Liste liniare ordonate

17

5.2.1.  Operaţii cu liste liniare ordonate

17

5.3.  Liste liniare simplu înlănţuite

20

5.3.1.  Operaţii cu liste liniare simplu înlănţuite

22

5.3.2.  Modalităţi de specificare a poziţiei elementului care urmează a fi procesat într-o listă liniară simplu înlănţuită

28

5.3.3.  Complexitatea operaţiilor de parcurgere, inserţie şi ştergere

31

5.3.4.  Exerciţii

31

5.4.  Liste liniare dublu înlănţuite

32

5.4.1.  Operaţii cu liste liniare dublu înlănţuite

33

5.4.2.  Moduri de definire a poziţiei elementului care urmează a fi procesat într-o listă liniară dublu înlănţuită

39

5.4.3.  Complexitatea operaţiilor de parcurgere, inserţie şi ştergere

41

5.4.4.  Exerciţii

42

6.  Liste circulare

43

6.1.  Aspecte generale

43

6.2.  Liste circulare simplu înlănţuite

43

6.2.1.  Operaţii cu liste circulare simplu înlănţuite

44

6.2.2.  Moduri de definire a adresei elementului care urmează a fi procesat într-o liste circulară simplu înlănţuită

47

6.2.3.  Complexitatea operaţiilor de parcurgere, inserţie şi ştergere

50

6.2.4.  Exerciţii

51

6.3.  Liste circulare dublu înlănţuite

52

6.3.1.  Operaţii cu liste circulare dublu înlănţuite

52

6.3.2.  Moduri de definire a  adresei elementului care urmează a fi procesat într-o listă circulară dublu înlănţuită

58

6.3.3.  Complexitatea operaţiilor de parcurgere, inserţie şi ştergere

60

6.3.4.  Exerciţii

61

7.  Stive şi cozi

63

7.1.  Stive

63

7.2.  Cozi

64

7.3.  Implementări de stive

65

7.3.1.  Stive ordonate

65

7.3.2.  Stive înlănţuite

67

7.4.  Exerciţii

68

7.5.  Implementări de cozi

70

7.5.1.  Cozi ordonate liniare

70

7.5.2.  Cozi ordonate circulare

72

7.5.3.  Cozi înlănţuite liniare

74

7.5.4.  Cozi înlănţuite circulare

76

7.5.4.  Complexitatea operaţiilor specifice stivelor şi cozilor

77

7.6.  Exerciţii

77

8.  Liste generalizate

79

8.1.  Aspecte generale

79

8.2.  Reprezentarea listelor generalizate

79

8.3.  Operaţii cu liste generalizate

81

8.3.1.  Traversarea listelor generalizate

82

8.4.  Exerciţii

83

9.  Arbori

85

9.1.  Aspecte generale

85

9.2.  Reprezentarea arborilor

87

9.2.1.  Reprezentarea  „tată-fii

87

9.2.2.  Reprezentarea prin liste generalizate

88

9.2.3.  Reprezentarea „fiu-tată

89

9.3.  Arbori binari oarecare

89

9.3.1.  Reprezentarea implicită a arborilor binari

91

9.3.2.  Relaţii între numărul de noduri şi structura unui arbore binar

92

9.3.3.  Operaţii asupra arborilor binari

93

9.4.  Arbori binari de căutare (BST)  

95

9.4.1.  Operaţii pe arbori binari de căutare

97

9.4.2.  Complexitatea operaţiilor pe arbori binari de căutare

101

9.4.3.  Complexitatea operaţiei de creare a unui arbore binar de căutare

101

9.5.  Arbori binari de căutare AVL - echilibraţi

104

9.5.1.  Conservarea proprietăţilor de arbore binar AVL - echilibrat

104

9.6.  Arbori binari de căutare optimali

110

9.7.  Arbori heap

115

9.7.1.  Operaţii pe arbori heap

116

9.7.2.  Aplicaţii ale arborilor  heap

119

9.8.  Exerciţii

124

10.  Grafuri

127

10.1.  Aspecte generale

127

10.2.  Reprezentări

129

10.3.  Explorarea sistemică a unui digraf

130

10.4.  Componente conexe

135

10.5.  Arbori de acoperire

137

10.6.  Exerciţii

137

11.  Teste grilă

139