calstr-1

[ Pobierz całość w formacie PDF ]
IDZ DO
PRZYK£ADOW
C++. Algorytmy
SPIS TRECI
i struktury danych
KATALOG KSI¥¯EK
Autor: Adam Drozdek
T³umaczenie: Piotr Rajca, Tomasz ¯mijewski
ISBN: 83-7361-385-4
Tytu³ orygina³u
in C++, Second Edition
Format: B5, stron: 616
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
DODAJ DO KOSZYKA
Badanie struktur danych, elementarnych sk³adników wykorzystywanych w informatyce,
jest podstaw¹, w oparciu o któr¹ mo¿esz zdobywaæ cenne umiejêtnoci. 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¿onoci
• 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 jednoczenie 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êtnoci przydatnych w przysz³ej pracy zawodowej.
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Spis treci
Wstp.....................................................................................................................11
1.
Programowanie obiektowe w C++ ........................................................................15
1.1. Abstrakcyjne typy danych ....................................................................................................................... 15
1.2. Enkapsulacja............................................................................................................................................ 15
1.3. Dziedziczenie........................................................................................................................................... 19
1.4. Wskaniki ................................................................................................................................................ 22
1.4.1. Wskaniki a tablice...................................................................................................................... 24
1.4.2. Wskaniki a konstruktory kopiuj!ce............................................................................................ 26
1.4.3. Wskaniki i destruktory............................................................................................................... 29
1.4.4. Wskaniki a referencje................................................................................................................. 29
1.4.5. Wskaniki na funkcje................................................................................................................... 32
1.5. Polimorfizm............................................................................................................................................. 33
1.6. C++ a programowanie obiektowe............................................................................................................ 35
1.7. 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
1.8. Wektory w standardowej bibliotece szablonów ...................................................................................... 40
1.9. Struktury danych a programowanie obiektowe....................................................................................... 46
1.10. Przykład zastosowania: plik z dost4pem swobodnym............................................................................. 47
1.11. 5wiczenia ................................................................................................................................................ 56
1.12. Zadania programistyczne......................................................................................................................... 58
Bibliografia ............................................................................................................................................. 60
2
Analiza złoonoci.................................................................................................61
2.1. Zło8ono9: obliczeniowa i asymptotyczna ............................................................................................... 61
2.2. O-notacja.................................................................................................................................................. 62
2.3. Wła9ciwo9ci O-notacji............................................................................................................................. 64
 6
SPIS TRECI
2.4. Notacje i ........................................................................................................................................... 66
2.5. Mo8liwe problemy................................................................................................................................... 67
2.6. Przykłady zło8ono9ci............................................................................................................................... 67
2.7. Okre9lanie zło8ono9ci asymptotycznej. Przykłady.................................................................................. 68
2.8. Zło8ono9: optymistyczna, 9rednia i pesymistyczna................................................................................ 71
2.9. Zło8ono9: zamortyzowana ...................................................................................................................... 73
2.10. 5wiczenia ................................................................................................................................................ 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 si4.................................................................................................................... 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. 5wiczenia .............................................................................................................................................. 126
3.12. Zadania programistyczne....................................................................................................................... 128
Bibliografia ........................................................................................................................................... 131
4.
Stosy i kolejki ......................................................................................................133
4.1. Stosy ...................................................................................................................................................... 133
4.2. Kolejki ................................................................................................................................................... 140
4.3. Kolejki priorytetowe.............................................................................................................................. 147
4.4. Stosy w bibliotece STL.......................................................................................................................... 148
4.5. Kolejki w bibliotece STL....................................................................................................................... 148
4.6. Kolejki priorytetowe w bibliotece STL................................................................................................. 149
4.7. Przykład zastosowania. Szukanie wyj9cia z labiryntu........................................................................... 152
4.8. 5wiczenia .............................................................................................................................................. 156
4.9. Zadania programistyczne....................................................................................................................... 159
Bibliografia ........................................................................................................................................... 160
5
Rekurencja...........................................................................................................161
5.1. Definicje rekurencyjne........................................................................................................................... 161
5.2. Wywołania funkcji a implementacja rekurencji.................................................................................... 164
5.3. Anatomia wywołania rekurencyjnego................................................................................................... 165
5.4. Rekurencja ogonowa ............................................................................................................................. 169
5.5. Rekurencja inna ni8 ogonowa................................................................................................................ 170
SPIS TRECI
7
5.6. Rekurencja po9rednia............................................................................................................................. 174
5.7. Rekurencja zagnie8d8ona ...................................................................................................................... 176
5.8. Nadu8ywanie rekurencji........................................................................................................................ 177
5.9. Algorytmy z powrotami......................................................................................................................... 180
5.10. Wnioski koDcowe .................................................................................................................................. 186
5.11. Przykład zastosowania. Rekurencyjny interpreter................................................................................. 187
5.12. 5wiczenia .............................................................................................................................................. 194
5.13. Zadania programistyczne....................................................................................................................... 197
Bibliografia ........................................................................................................................................... 199
6
Drzewa binarne....................................................................................................201
6.1. Drzewa, drzewa binarne i binarne drzewa poszukiwania...................................................................... 201
6.2. Implementacja drzew binarnych............................................................................................................ 205
6.3. Wyszukiwanie w drzewie binarnym...................................................................................................... 207
6.4. 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
6.5. Wstawianie ............................................................................................................................................ 223
6.6. Usuwanie ............................................................................................................................................... 225
6.6.1. Usuwanie przez zł!czanie.......................................................................................................... 226
6.6.2. Usuwanie przez kopiowanie...................................................................................................... 229
6.7. Równowa8enie drzewa.......................................................................................................................... 231
6.7.1. Algorytm DSW.......................................................................................................................... 234
6.7.2. Drzewa AVL.............................................................................................................................. 236
6.8. Drzewa samoorganizuj!ce si4................................................................................................................ 241
6.8.1. Drzewa samonaprawiaj!ce si4................................................................................................... 241
6.8.2. Ukosowanie ............................................................................................................................... 243
6.9. Sterty...................................................................................................................................................... 247
6.9.1. Sterty jako kolejki priorytetowe................................................................................................. 249
6.9.2. Organizowanie tablic w sterty ................................................................................................... 251
6.10. Notacja polska i drzewa wyra8eD .......................................................................................................... 255
6.10.1. Operacje na drzewach wyra8eD ................................................................................................. 256
6.11. Przykład zastosowania. Zliczanie cz4sto9ci wyst4powania słów.......................................................... 259
6.12. 5wiczenia .............................................................................................................................................. 265
6.13. Zadania programistyczne....................................................................................................................... 268
Bibliografia ........................................................................................................................................... 272
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
SPIS TRECI
7.2. Drzewa słownikowe............................................................................................................................... 313
7.3. Uwagi koDcowe ..................................................................................................................................... 321
7.4. Przykład zastosowania. Sprawdzanie pisowni ...................................................................................... 321
7.5. 5wiczenia .............................................................................................................................................. 330
7.6. 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 BorIvki...................................................................................................................... 357
8.5.2. Algorytm Kruskala .................................................................................................................... 358
8.5.3. Algorytm Jarníka-Prima ............................................................................................................ 360
8.5.4. Metoda Dijkstry......................................................................................................................... 361
8.6. Spójno9: ................................................................................................................................................. 361
8.6.1. Spójno9: w grafach nieskierowanych........................................................................................ 361
8.6.2. Spójno9: 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. 5wiczenia............................................................................................................................................... 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
[ Pobierz całość w formacie PDF ]