C_Algorytmy_i_struktury_danych_calstr.pdf

(856 KB) Pobierz
IDZ DO
PRZYK£ADOWY ROZDZIA£
SPIS TRE CI
KATALOG KSI¥¯EK
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
C++. Algorytmy
i struktury danych
Autor: Adam Drozdek
T³umaczenie: Piotr Rajca, Tomasz ¯mijewski
ISBN: 83-7361-385-4
Tytu³ orygina³u:
Data Structures and Algorithms
in C++, Second Edition
Format: B5, stron: 616
TWÓJ KOSZYK
DODAJ DO KOSZYKA
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWO CIACH
ZAMÓW CENNIK
Badanie struktur danych, elementarnych sk³adników wykorzystywanych w informatyce,
jest podstaw¹, w oparciu o któr¹ mo¿esz zdobywaæ cenne umiejêtno ci. Znajomo æ
struktur danych jest niezbêdna studentom, którzy chc¹ programowaæ czy te¿ testowaæ
oprogramowanie.
W niniejszej ksi¹¿ce zwrócono uwagê na trzy wa¿ne aspekty struktur danych: po
pierwsze, na zwi¹zek struktur danych z algorytmami, miêdzy innymi na z³o¿ono æ
obliczeniow¹ algorytmów. Po drugie, struktury te prezentowane s¹ w sposób zgodny
z zasadami projektowania obiektowego i obiektowym paradygmatem programowania.
Po trzecie, wa¿n¹ czê ci¹ ksi¹¿ki s¹ implementacje struktur danych w jêzyku C++.
Ksi¹¿ka prezentuje:
• Podstawy projektowania obiektowego w C++
• Analizê z³o¿ono ci
• Listy powi¹zane
• Stosy i kolejki
• Rekurencjê
• Drzewa binarne
• Sterty
• Drzewa wielokrotne
• Grafy
• Sortowanie i mieszanie
• Kompresja danych
• Zarz¹dzanie pamiêci¹
Ksi¹¿ka ta dostarcza studentom informatyki nie tylko niezbêdnej wiedzy na temat
algorytmów i struktur danych, ale prezentuje jednocze nie sposoby ich implementacji
w jêzyku C++, obecnie jednym z wiod¹cych jêzyków programowania. Dostarcza ona
wiêc nie tylko wiedzy teoretycznej, ale równie¿ pozwala rozwin¹æ praktyczne
umiejêtno ci przydatnych w przysz³ej pracy zawodowej.
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treści
Wstęp .....................................................................................................................11
1.
Programowanie obiektowe w C++ ........................................................................15
1.1.
1.2.
1.3.
1.4.
Abstrakcyjne typy danych ....................................................................................................................... 15
Enkapsulacja ............................................................................................................................................ 15
Dziedziczenie........................................................................................................................................... 19
Wskaźniki ................................................................................................................................................ 22
1.4.1. Wskaźniki a tablice ...................................................................................................................... 24
1.4.2. Wskaźniki a konstruktory kopiujące............................................................................................ 26
1.4.3. Wskaźniki i destruktory ............................................................................................................... 29
1.4.4. Wskaźniki a referencje................................................................................................................. 29
1.4.5. Wskaźniki na funkcje................................................................................................................... 32
Polimorfizm ............................................................................................................................................. 33
C++ a programowanie obiektowe............................................................................................................ 35
Standardowa biblioteka szablonów ......................................................................................................... 36
1.7.1. Kontenery..................................................................................................................................... 36
1.7.2. Iteratory........................................................................................................................................ 37
1.7.3. Algorytmy .................................................................................................................................... 37
1.7.4. Funktory....................................................................................................................................... 38
Wektory w standardowej bibliotece szablonów ...................................................................................... 40
Struktury danych a programowanie obiektowe ....................................................................................... 46
Przykład zastosowania: plik z dostępem swobodnym............................................................................. 47
Ćwiczenia ................................................................................................................................................ 56
Zadania programistyczne......................................................................................................................... 58
Bibliografia ............................................................................................................................................. 60
1.5.
1.6.
1.7.
1.8.
1.9.
1.10.
1.11.
1.12.
2.
Analiza zło oności .................................................................................................61
2.1. Zło oność obliczeniowa i asymptotyczna ............................................................................................... 61
2.2. O-notacja.................................................................................................................................................. 62
2.3. Właściwości O-notacji............................................................................................................................. 64
6
2.4.
2.5.
2.6.
2.7.
2.8.
2.9.
2.10.
SPIS TREŚCI
Notacje
Ω
i
Θ...........................................................................................................................................
66
Mo liwe problemy................................................................................................................................... 67
Przykłady zło oności ............................................................................................................................... 67
Określanie zło oności asymptotycznej. Przykłady.................................................................................. 68
Zło oność optymistyczna, średnia i pesymistyczna ................................................................................ 71
Zło oność zamortyzowana ...................................................................................................................... 73
Ćwiczenia ................................................................................................................................................ 77
Bibliografia ............................................................................................................................................. 80
3.
Listy .......................................................................................................................81
3.1. Listy jednokierunkowe ............................................................................................................................ 81
3.1.1. Wstawianie................................................................................................................................... 86
3.1.2. Usuwanie ..................................................................................................................................... 88
3.1.3. Wyszukiwanie.............................................................................................................................. 93
3.2. Listy dwukierunkowe .............................................................................................................................. 93
3.3. Listy cykliczne......................................................................................................................................... 97
3.4. Listy z przeskokami ................................................................................................................................. 99
3.5. Listy samoorganizujące się.................................................................................................................... 104
3.6. Tablice rzadkie....................................................................................................................................... 107
3.7. Listy w bibliotece STL .......................................................................................................................... 110
3.8. Kolejki dwustronne w bibliotece STL ................................................................................................... 113
3.9. Podsumowanie....................................................................................................................................... 117
3.10. Przykład zastosowania. Biblioteka ........................................................................................................ 118
3.11. Ćwiczenia .............................................................................................................................................. 126
3.12. Zadania programistyczne....................................................................................................................... 128
Bibliografia ........................................................................................................................................... 131
4.
Stosy i kolejki ......................................................................................................133
4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
4.7.
4.8.
4.9.
Stosy ...................................................................................................................................................... 133
Kolejki ................................................................................................................................................... 140
Kolejki priorytetowe .............................................................................................................................. 147
Stosy w bibliotece STL.......................................................................................................................... 148
Kolejki w bibliotece STL....................................................................................................................... 148
Kolejki priorytetowe w bibliotece STL ................................................................................................. 149
Przykład zastosowania. Szukanie wyjścia z labiryntu........................................................................... 152
Ćwiczenia .............................................................................................................................................. 156
Zadania programistyczne....................................................................................................................... 159
Bibliografia ........................................................................................................................................... 160
5.
Rekurencja ...........................................................................................................161
5.1.
5.2.
5.3.
5.4.
5.5.
Definicje rekurencyjne........................................................................................................................... 161
Wywołania funkcji a implementacja rekurencji .................................................................................... 164
Anatomia wywołania rekurencyjnego ................................................................................................... 165
Rekurencja ogonowa ............................................................................................................................. 169
Rekurencja inna ni ogonowa................................................................................................................ 170
SPIS TREŚCI
7
5.6.
5.7.
5.8.
5.9.
5.10.
5.11.
5.12.
5.13.
Rekurencja pośrednia............................................................................................................................. 174
Rekurencja zagnie d ona ...................................................................................................................... 176
Nadu ywanie rekurencji ........................................................................................................................ 177
Algorytmy z powrotami......................................................................................................................... 180
Wnioski końcowe .................................................................................................................................. 186
Przykład zastosowania. Rekurencyjny interpreter................................................................................. 187
Ćwiczenia .............................................................................................................................................. 194
Zadania programistyczne....................................................................................................................... 197
Bibliografia ........................................................................................................................................... 199
6.
Drzewa binarne ....................................................................................................201
6.1.
6.2.
6.3.
6.4.
Drzewa, drzewa binarne i binarne drzewa poszukiwania...................................................................... 201
Implementacja drzew binarnych............................................................................................................ 205
Wyszukiwanie w drzewie binarnym...................................................................................................... 207
Przechodzenie po drzewie ..................................................................................................................... 210
6.4.1. Przechodzenie wszerz ................................................................................................................ 210
6.4.2. Przechodzenie w głąb ................................................................................................................ 211
6.4.3. Przechodzenie po drzewie w głąb bez stosu .............................................................................. 217
Wstawianie ............................................................................................................................................ 223
Usuwanie ............................................................................................................................................... 225
6.6.1. Usuwanie przez złączanie .......................................................................................................... 226
6.6.2. Usuwanie przez kopiowanie ...................................................................................................... 229
Równowa enie drzewa .......................................................................................................................... 231
6.7.1. Algorytm DSW .......................................................................................................................... 234
6.7.2. Drzewa AVL.............................................................................................................................. 236
Drzewa samoorganizujące się................................................................................................................ 241
6.8.1. Drzewa samonaprawiające się ................................................................................................... 241
6.8.2. Ukosowanie ............................................................................................................................... 243
Sterty...................................................................................................................................................... 247
6.9.1. Sterty jako kolejki priorytetowe................................................................................................. 249
6.9.2. Organizowanie tablic w sterty ................................................................................................... 251
Notacja polska i drzewa wyra eń .......................................................................................................... 255
6.10.1. Operacje na drzewach wyra eń ................................................................................................. 256
Przykład zastosowania. Zliczanie częstości występowania słów .......................................................... 259
Ćwiczenia .............................................................................................................................................. 265
Zadania programistyczne....................................................................................................................... 268
Bibliografia ........................................................................................................................................... 272
6.5.
6.6.
6.7.
6.8.
6.9.
6.10.
6.11.
6.12.
6.13.
7.
Drzewa wielokierunkowe ....................................................................................275
7.1. Rodzina B-drzew ................................................................................................................................... 276
7.1.1. B-drzewa .................................................................................................................................... 277
7.1.2. B*-drzewa .................................................................................................................................. 286
7.1.3. B+-drzewa.................................................................................................................................. 288
7.1.4. B+-drzewa przedrostkowe ......................................................................................................... 289
7.1.5. Drzewa bitowe ........................................................................................................................... 291
7.1.6. R-drzewa .................................................................................................................................... 294
7.1.7. 2-4-drzewa ................................................................................................................................. 296
7.1.8. Zbiory i wielozbiory w bibliotece STL...................................................................................... 303
7.1.9. Mapy i multimapy w bibliotece STL ......................................................................................... 309
8
7.2.
7.3.
7.4.
7.5.
7.6.
SPIS TREŚCI
Drzewa słownikowe............................................................................................................................... 313
Uwagi końcowe ..................................................................................................................................... 321
Przykład zastosowania. Sprawdzanie pisowni ...................................................................................... 321
Ćwiczenia .............................................................................................................................................. 330
Zadania programistyczne....................................................................................................................... 331
Bibliografia ........................................................................................................................................... 334
8.
Grafy ....................................................................................................................337
8.1. Reprezentacje grafów ............................................................................................................................. 338
8.2. Przechodzenie po grafach....................................................................................................................... 340
8.3. Najkrótsza droga .................................................................................................................................... 344
8.3.1. Problem najkrótszych dróg typu „wszystkie-do-wszystkich” ................................................... 351
8.4. Wykrywanie cykli .................................................................................................................................. 353
8.4.1. Problem znajdowania sumy zbiorów rozłącznych..................................................................... 354
8.5. Drzewa rozpinające ................................................................................................................................ 356
8.5.1. Algorytm Borůvki...................................................................................................................... 357
8.5.2. Algorytm Kruskala .................................................................................................................... 358
8.5.3. Algorytm Jarníka-Prima ............................................................................................................ 360
8.5.4. Metoda Dijkstry ......................................................................................................................... 361
8.6. Spójność ................................................................................................................................................. 361
8.6.1. Spójność w grafach nieskierowanych........................................................................................ 361
8.6.2. Spójność w grafach skierowanych............................................................................................. 364
8.7. Sortowanie topologiczne ........................................................................................................................ 365
8.8. Sieci ........................................................................................................................................................ 368
8.8.1. Przepływy maksymalne ............................................................................................................. 368
8.8.2. Maksymalne przepływy o minimalnym koszcie........................................................................ 378
8.9. Kojarzenie .............................................................................................................................................. 383
8.9.1. Problem przypisania................................................................................................................... 387
8.9.2. Skojarzenia w grafach, które nie są dwudzielne........................................................................ 390
8.10. Grafy eulerowskie i hamiltonowskie...................................................................................................... 392
8.10.1. Grafy eulerowskie...................................................................................................................... 392
8.10.2. Grafy hamiltonowskie................................................................................................................ 393
8.11. Przykład zastosowania. Unikalni reprezentanci..................................................................................... 396
8.12. Ćwiczenia ............................................................................................................................................... 406
8.13. Zadania programistyczne ....................................................................................................................... 409
Bibliografia ........................................................................................................................................... 411
9.
Sortowanie ...........................................................................................................413
9.1. Podstawowe algorytmy sortowania ....................................................................................................... 414
9.1.1. Sortowanie przez wstawianie..................................................................................................... 414
9.1.2. Sortowanie przez wybieranie..................................................................................................... 417
9.1.3. Sortowanie bąbelkowe ............................................................................................................... 419
9.2. Drzewa decyzyjne.................................................................................................................................. 422
9.3. Efektywne algorytmy sortowania .......................................................................................................... 425
9.3.1. Sortowanie Shella ...................................................................................................................... 425
9.3.2. Sortowanie przez kopcowanie ................................................................................................... 429
9.3.3. Sortowanie szybkie (quicksort).................................................................................................. 433
9.3.4. Sortowanie poprzez scalanie...................................................................................................... 440
9.3.5. Sortowanie pozycyjne................................................................................................................ 443

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin