c++.-struktury-danych-i-algorytmy cała książka.pdf

(35213 KB) Pobierz
Spis tre ci
O autorze
O recenzencie
Wst p
Rozdzia 1. Struktury danych i algorytmy w C++
Wymagania techniczne
Podstawy C++
Pierwszy kod w C++
Usprawnianie pracy nad kodem przy u yciu IDE
Definiowanie zmiennych przy u yciu podstawowych typów danych
Sterowanie przep ywem kodu
Wykorzystanie zmiennych za po rednictwem zaawansowanych typów danych
Tworzenie abstrakcyjnych typów danych
Wykorzystanie klas C++ przy tworzeniu ADT zdefiniowanych przez u ytkownika
Pos ugiwanie si szablonami
Analiza algorytmów
Analiza asymptotyczna
Najgorsze, rednie i najlepsze przypadki
Notacja , i
Metoda rekurencyjna
Analiza kosztu zamortyzowanego
Podsumowanie
Pytania
Dodatkowe materia y
9
10
11
15
15
16
16
17
19
20
28
33
33
39
44
44
47
48
49
49
50
50
50
Kup książkę
Poleć książkę
Spis tre ci
Rozdzia 2. Przechowywanie danych w listach i listach wi zanych
Wymagania techniczne
Tablice
Tworzenie ADT listy
Zwracanie elementu z listy
Wstawianie elementu do listy
Wyszukiwanie indeksu wybranego elementu w li cie
Usuwanie elementu z listy
Implementacja listy
Wprowadzenie do w z ów
Tworzenie ADT listy jednokierunkowej
Zwracanie elementu z listy wi zanej
Wstawianie elementu do listy wi zanej
Wyszukiwanie indeksu wybranego elementu w li cie wi zanej
Usuwanie elementu z listy wi zanej
Implementacja listy wi zanej
Tworzenie ADT listy dwukierunkowej
Refaktoryzacja typu danych Node<T>
Refaktoryzacja kilku operacji LinkedList
Implementacja ADT listy dwukierunkowej
Wykorzystanie typów List i LinkedList przy u yciu STL
std::vector
std::list
Podsumowanie
Pytania
Dodatkowe materia y
51
51
52
55
56
57
58
58
59
61
65
66
67
69
70
73
75
76
76
81
83
83
85
88
88
88
Rozdzia 3. Tworzenie stosów i kolejek
Wymagania techniczne
Tworzenie ADT stosu
Pobieranie warto ci elementu z ADT stosu
Umieszczanie elementów na ADT stosu
Usuwanie elementów z ADT stosu
Implementacja ADT stosu
Tworzenie ADT kolejki jednokierunkowej
Pobieranie warto ci elementu z ADT kolejki
Wstawianie elementu do ADT kolejki
Usuwanie elementu z ADT kolejki
Implementacja ADT kolejki
Tworzenie ADT kolejki dwukierunkowej
Pobieranie warto ci elementu z ADT kolejki dwukierunkowej
Dodawanie elementu do ADT kolejki dwukierunkowej
Usuwanie elementu z ADT kolejki dwukierunkowej
Implementacja ADT kolejki dwukierunkowej
Podsumowanie
Pytania
Dodatkowe materia y
91
91
92
93
93
94
95
99
100
100
101
102
103
104
104
106
107
108
109
109
4
Kup książkę
Poleć książkę
Spis tre ci
Rozdzia 4. Porz dkowanie elementów przy u yciu algorytmów sortowania
Wymagania techniczne
Sortowanie b belkowe
Sortowanie przez wybieranie
Sortowanie przez wstawianie
Sortowanie przez scalanie
Sortowanie szybkie
Sortowanie przez zliczanie
Sortowanie pozycyjne
Podsumowanie
Pytania
Dodatkowe materia y
111
111
112
114
118
122
128
133
136
140
140
141
Rozdzia 5. Wyszukiwanie elementów przy u yciu algorytmów wyszukiwania
Wymagania techniczne
Wyszukiwanie liniowe
Opracowanie algorytmu wyszukiwania liniowego
Implementacja algorytmu wyszukiwania liniowego
Wyszukiwanie binarne
Opracowanie algorytmu wyszukiwania binarnego
Implementacja algorytmu wyszukiwania binarnego
Wyszukiwanie ternarne
Opracowanie algorytmu wyszukiwania ternarnego
Zastosowanie algorytmu wyszukiwania ternarnego
Wyszukiwanie interpolacyjne
Opracowanie algorytmu wyszukiwania interpolacyjnego
Zastosowanie algorytmu wyszukiwania interpolacyjnego
Wyszukiwanie skokowe
Opracowanie algorytmu wyszukiwania skokowego
Zastosowanie algorytmu wyszukiwania skokowego
Wyszukiwanie wyk adnicze
Opracowanie algorytmu wyszukiwania wyk adniczego
Wywo anie funkcji ExponentialSearch()
Wyszukiwanie podlisty
Opracowanie algorytmu wyszukiwania podlisty
Wykorzystanie algorytmu wyszukiwania podlisty
Podsumowanie
Pytania
Dodatkowe materia y
143
144
144
144
145
146
146
147
148
149
150
151
151
153
154
154
155
156
156
157
158
159
160
162
162
163
Rozdzia 6. U ywanie znakowego typu danych
Wymagania techniczne
Ci g znakowy C++
Tworzenie ci gu znaków przy u yciu tablicy znaków
Dodatkowe funkcje std::string
Zabawa s owami
Tworzenie anagramów
Wykrywanie palindromów
165
165
166
166
166
167
167
169
5
Kup książkę
Poleć książkę
Spis tre ci
Tworzenie ci gu z cyfr binarnych
Konwertowanie liczb dziesi tnych na binarne
Konwertowanie ci gu binarnego na dziesi tny
Ci g podsekwencji
Generowanie podsekwencji z ci gu
Sprawdzanie, czy ci g jest podsekwencj innego ci gu
Wyszukiwanie wzorca
Podsumowanie
Pytania
Dodatkowe materia y
172
173
175
177
177
179
181
184
184
185
Rozdzia 7. Tworzenie hierarchicznej struktury drzewa
Wymagania techniczne
Tworzenie ADT drzewa binarnego
Tworzenie ADT binarnego drzewa poszukiwa
Wstawianie nowego klucza do BST
Przechodzenie po BST po kolei
Sprawdzanie obecno ci klucza w BST
Zwracanie minimalnych i maksymalnych warto ci kluczy
Wyszukiwanie nast pnika klucza w BST
Wyszukiwanie poprzednika klucza w BST
Usuwanie w z a wed ug podanego klucza
Implementacja ADT BST
Tworzenie ADT zrównowa onego BST (AVL)
Rotacja w z ów
Wstawianie nowego klucza
Usuwanie wskazanego klucza
Implementacja ADT AVL
Tworzenie ADT kopca binarnego
Sprawdzanie, czy kopiec jest pusty
Wstawianie nowego elementu do kopca
Pobieranie elementu o najwi kszej warto ci
Usuwanie elementu o najwi kszej warto ci
Implementacja stosu binarnego jako kolejki priorytetowej
Podsumowanie
Pytania
Dodatkowe materia y
187
187
188
190
192
193
193
194
195
197
199
201
204
205
207
208
210
212
213
214
214
215
216
217
218
218
Rozdzia 8. Zestawianie warto ci z kluczem w tablicy mieszaj cej
Wymagania techniczne
Wprowadzenie do tablic mieszaj cych
Du o danych w ma ych komórkach
Przechowywanie danych w tablicy mieszaj cej
Obs uga kolizji
Implementacja metody a cuchowej
Generowanie klucza mieszaj cego
Opracowanie operacji Insert()
Opracowanie operacji Search()
219
219
220
220
221
221
222
223
223
224
6
Kup książkę
Poleć książkę

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin