Dane szczegółowe książki
STRUKTURY DANYCH W JĘZYKU C / Drozdek, Adam; Simon, Donald L.
Autorzy
Tytuł
STRUKTURY DANYCH W JĘZYKU C
Wydawnictwo
Warszawa: Wydawnictwa Naukowo-Techniczne, 1996
ISBN
83-204-1981-6
Spis treści
pokaż spis treści
Przedmowa do polskiego wydania 11
Przedmowa 13
1. Projektowanie programu w języku C 17
1.1. Projektowanie zstępujące 17
1.2. Projektowanie wstępujące: maszyny wirtualne 19
1.3. Projektowanie do wielokrotnego użytku: oddzielna kompilacja 20
1.4. Abstrakcyjne typy danych 22
1.5. Ćwiczenia 33
2. Projektowanie algorytmu 35
2.1. Algorytmy zachłanne 35
2.2. Algorytmy oparte na strategii „dziel i zwyciężaj" 36
2.3. Algorytmy oparte na programowaniu dynamicznym 38
2.4. Algorytmy z powrotami 41
2.5. Ćwiczenia 45
3. Poprawność programu 47
3.1. Wprowadzenie 47
3.2. Warunki wstępne i końcowe 47
3.3. Niezmienniki pętli 50
3.3.1. Dowodzenie niezmienników 52
3.3.2. Najczęstsze niezmienniki pętli 55
3.3.3. Przetwarzanie tablic 58
3.4. Problem stopu 59
3.5. Przykład: wyszukiwanie binarne 60
3.6. Uwagi końcowe 63
#6
4. Analiza złożoności 66
4.1. Złożoność obliczeniowa i asymptotyczna 66
4.2. Notacja „wielkie O" 67
4.3. Własności notacji „wielkie O" 70
4.4. Notacje Q i 0 71
4.5. Możliwe problemy 72
4.6. Przykłady rzędów złożoności 73
4.7. Znajdowanie złożoności asymptotycznej: przykłady 75
4.8. Ćwiczenia 77
5. Dynamiczne przydzielanie pamięci 79
5.1. Listy 79
5.1.1. Listy dwukierunkowe 86
5.1.2. Listy cykliczne 87
5.2. Tablice rzadkie 89
5.3. Przykład: zarządzanie biblioteką 93
5.4. Ćwiczenia 101
5.5. Zadania programistyczne 101
6. Stosy i kolejki 103
6.1. Stosy 103
6.2. Kolejki 110
6.3. Kolejki priorytetowe 115
6.4. Przykład: płatek śniegu von Kocha 116
6.5. Ćwiczenia 121
6.6. Zadania programistyczne 122
7. Rekursja 125
7.1. Definicje rekurencyjne 125
7.2. Wywołania funkcji i realizacja rekursji 128
7.3. „Anatomia" wywołania rekurencyjnego 130
7.4. Rekursja końcowa 134
7.5. Rekursja niekońcowa 136
7.6. Rekursja pośrednia 140
7.7. Rekursja zagnieżdżona 143
7.8. Nadużywanie rekursji 143
7.9. Metoda powrotów 147
7.10. Uwagi końcowe 154
7.11. Przykład: interpretator 155
7.12. Ćwiczenia 163
7.13. Zadania programistyczne 165
#7
8. Drzewa binarne 168
8.1. Drzewa, drzewa binarne i drzewa poszukiwań binarnych 168
8.2. Realizacja drzew binarnych 168
8.3. Wyszukiwanie w drzewie poszukiwań binarnych 173
8.4. Przechodzenie drzewa 177
8.4.1. Przechodzenie wszerz 178
8.4.2. Przechodzenie w głąb 178
8.4.3. Przechodzenie w głąb bez użycia stosu 186
8.5. Wstawianie 192
8.6. Usuwanie 198
8.6.1. Pierwsze rozwiązanie 199
8.6.2. Drugie rozwiązanie 202
8.7. Równoważenie drzewa 204
8.7.1. Algorytm DSW 208
8.7.2. Drzewa A VL 211
8.8. Samokorygujące się drzewa 216
8.8.1. Samoorganizujące się drzewa 217
8.8.2. Rozchylanie 218
8.9. Kopce 221
8.10. Notacja polska i drzewa wyrażeń 226
8.10.1. Operacje na drzewach wyrażeń 228
8.11. Przykład: obliczanie częstości występowania słów 231
8.12. Ćwiczenia 236
8.13. Zadania programistyczne 239
9. Drzewa wyższych rzędów 245
9.1. Rodzina B-drzew 246
9.1.1. B-drzewa 247
9.1.2. B^*-drzewa 258
9.1.3. B^+-drzewa 260
9.1.4. Prefiksowe B^+-drzewa 262
9.1.5. Drzewa bitowe 264
9.1.6. R-drzewa 267
9.1.7. 2-4 drzewa 270
9.2. Drzewa trie 279
9.3. Uwagi końcowe 288
9.4. Przykład: sprawdzanie pisowni 289
9.5. Ćwiczenia 297
9.6. Zadania programistyczne 299
10. Grafy 304
10.1. Reprezentacja grafów 305
10.2. Przechodzenie grafu 306
#8
10.3. Spójność/dwuspójność 310
10.4. Grafy z wagami 315
10.4.1. Najkrótsze ścieżki 316
10.4.2. Minimalne drzewo rozpinające 319
10.5. Grafy skierowane 326
10.5.1. Przechodzenie grafu skierowanego 328
10.5.2. Najkrótsze ścieżki 333
10.6. Przykład: układanie harmonogramu zajęć 334
10.7. Ćwiczenia 346
10.8. Zadania programistyczne 347
11. Sortowanie 349
11.1. Elementarne algorytmy sortowania 351
11.1.1. Sortowanie przez wstawianie 351
11.1.2. Sortowanie przez wybieranie 356
11.1.3. Sortowanie bąbelkowe 358
11.2. Drzewa decyzyjne 364
11.3. Efektywne algorytmy sortowania 367
11.3.1. Sortowanie metodą Shella 367
11.3.2. Sortowanie przez kopcowanie 372
11.3.3. Sortowanie szybkie 379
11.3.4. Sortowanie przez scalanie 388
11.3.5. Sortowanie pozycyjne 391
11.4. Uwagi końcowe 397
11.5. Przykład: dodawanie wielomianów 399
11.6. Ćwiczenia 406
11.7. Zadania programistyczne 408
12. Mieszanie 412
12.1. Funkcje mieszające 413
12.1.1. Dzielenie 413
12.1.2. Składanie 414
12.1.3. Funkcja „środek kwadratu" 414
12.1.4. Wycinanie 415
12.1.5. Zamiana podstawy 415
12.2. Rozwiązywanie problemu kolizji 415
12.2.1. Adresowanie otwarte 416
12.2.2. Metoda łańcuchowa 422
12.2.3. Adresowanie kubełkowe 425
12.3. Usuwanie 426
12.4. Doskonałe funkcje mieszające 427
12.4.1. Metoda Cichelliego 428
12.4.2. Algorytm FHCD 431
#9
12.5. Funkcje mieszające dla plików rozszerzalnych 434
12.5.1. Mieszanie przedłużalne 434
12.5.2. Mieszanie liniowe 437
12.6. Przykład: mieszanie z użyciem kubełków 440
12.7. Ćwiczenia 447
12.8. Zadania programistyczne 448
13. Kompresja danych 451
13.1. Wymagania dotyczące kompresji danych 451
13.2. Metoda Huffmana 453
13.2.1. Adaptacyjne kody Huffmana 463
13.3. Metoda Shannona-Fano 467
13.4. Kodowanie długości serii 469
13.5. Metoda Ziva-Lempela 471
13.6. Przykład: metoda Huffmana z kodowaniem długości serii 474
13.7. Ćwiczenia 483
13.8. Zadania programistyczne 485
14. Zarządzanie pamięcią 487
14.1. Metody dopasowywania sekwencyjnego 488
14.2. Metody niesekwencyjne 490
14.2.1. Systemy par 492
14.3. Odśmiecanie 500
14.3.1. Metoda „zaznacz-i-usuń" 501
14.3.2. Metody kopiowania 509
14.3.3. Odśmiecanie krokowe 510
14.4. Uwagi końcowe 519
14.5. Przykład: odśmiecanie „w miejscu" 520
14.6. Ćwiczenia 525
14.7. Zadania programistyczne 527
DODATEK A. Obliczenia przybliżone 532
A.1. Szereg harmoniczny 532
A.2. Oszacowanie funkcji lg(n!) 532
A.3. Średnia złożoność algorytmu auicksort 535
A.4. Średnia długość ścieżki w losowym drzewie binarnym 536
Skorowidz 538
Przedmowa 13
1. Projektowanie programu w języku C 17
1.1. Projektowanie zstępujące 17
1.2. Projektowanie wstępujące: maszyny wirtualne 19
1.3. Projektowanie do wielokrotnego użytku: oddzielna kompilacja 20
1.4. Abstrakcyjne typy danych 22
1.5. Ćwiczenia 33
2. Projektowanie algorytmu 35
2.1. Algorytmy zachłanne 35
2.2. Algorytmy oparte na strategii „dziel i zwyciężaj" 36
2.3. Algorytmy oparte na programowaniu dynamicznym 38
2.4. Algorytmy z powrotami 41
2.5. Ćwiczenia 45
3. Poprawność programu 47
3.1. Wprowadzenie 47
3.2. Warunki wstępne i końcowe 47
3.3. Niezmienniki pętli 50
3.3.1. Dowodzenie niezmienników 52
3.3.2. Najczęstsze niezmienniki pętli 55
3.3.3. Przetwarzanie tablic 58
3.4. Problem stopu 59
3.5. Przykład: wyszukiwanie binarne 60
3.6. Uwagi końcowe 63
#6
4. Analiza złożoności 66
4.1. Złożoność obliczeniowa i asymptotyczna 66
4.2. Notacja „wielkie O" 67
4.3. Własności notacji „wielkie O" 70
4.4. Notacje Q i 0 71
4.5. Możliwe problemy 72
4.6. Przykłady rzędów złożoności 73
4.7. Znajdowanie złożoności asymptotycznej: przykłady 75
4.8. Ćwiczenia 77
5. Dynamiczne przydzielanie pamięci 79
5.1. Listy 79
5.1.1. Listy dwukierunkowe 86
5.1.2. Listy cykliczne 87
5.2. Tablice rzadkie 89
5.3. Przykład: zarządzanie biblioteką 93
5.4. Ćwiczenia 101
5.5. Zadania programistyczne 101
6. Stosy i kolejki 103
6.1. Stosy 103
6.2. Kolejki 110
6.3. Kolejki priorytetowe 115
6.4. Przykład: płatek śniegu von Kocha 116
6.5. Ćwiczenia 121
6.6. Zadania programistyczne 122
7. Rekursja 125
7.1. Definicje rekurencyjne 125
7.2. Wywołania funkcji i realizacja rekursji 128
7.3. „Anatomia" wywołania rekurencyjnego 130
7.4. Rekursja końcowa 134
7.5. Rekursja niekońcowa 136
7.6. Rekursja pośrednia 140
7.7. Rekursja zagnieżdżona 143
7.8. Nadużywanie rekursji 143
7.9. Metoda powrotów 147
7.10. Uwagi końcowe 154
7.11. Przykład: interpretator 155
7.12. Ćwiczenia 163
7.13. Zadania programistyczne 165
#7
8. Drzewa binarne 168
8.1. Drzewa, drzewa binarne i drzewa poszukiwań binarnych 168
8.2. Realizacja drzew binarnych 168
8.3. Wyszukiwanie w drzewie poszukiwań binarnych 173
8.4. Przechodzenie drzewa 177
8.4.1. Przechodzenie wszerz 178
8.4.2. Przechodzenie w głąb 178
8.4.3. Przechodzenie w głąb bez użycia stosu 186
8.5. Wstawianie 192
8.6. Usuwanie 198
8.6.1. Pierwsze rozwiązanie 199
8.6.2. Drugie rozwiązanie 202
8.7. Równoważenie drzewa 204
8.7.1. Algorytm DSW 208
8.7.2. Drzewa A VL 211
8.8. Samokorygujące się drzewa 216
8.8.1. Samoorganizujące się drzewa 217
8.8.2. Rozchylanie 218
8.9. Kopce 221
8.10. Notacja polska i drzewa wyrażeń 226
8.10.1. Operacje na drzewach wyrażeń 228
8.11. Przykład: obliczanie częstości występowania słów 231
8.12. Ćwiczenia 236
8.13. Zadania programistyczne 239
9. Drzewa wyższych rzędów 245
9.1. Rodzina B-drzew 246
9.1.1. B-drzewa 247
9.1.2. B^*-drzewa 258
9.1.3. B^+-drzewa 260
9.1.4. Prefiksowe B^+-drzewa 262
9.1.5. Drzewa bitowe 264
9.1.6. R-drzewa 267
9.1.7. 2-4 drzewa 270
9.2. Drzewa trie 279
9.3. Uwagi końcowe 288
9.4. Przykład: sprawdzanie pisowni 289
9.5. Ćwiczenia 297
9.6. Zadania programistyczne 299
10. Grafy 304
10.1. Reprezentacja grafów 305
10.2. Przechodzenie grafu 306
#8
10.3. Spójność/dwuspójność 310
10.4. Grafy z wagami 315
10.4.1. Najkrótsze ścieżki 316
10.4.2. Minimalne drzewo rozpinające 319
10.5. Grafy skierowane 326
10.5.1. Przechodzenie grafu skierowanego 328
10.5.2. Najkrótsze ścieżki 333
10.6. Przykład: układanie harmonogramu zajęć 334
10.7. Ćwiczenia 346
10.8. Zadania programistyczne 347
11. Sortowanie 349
11.1. Elementarne algorytmy sortowania 351
11.1.1. Sortowanie przez wstawianie 351
11.1.2. Sortowanie przez wybieranie 356
11.1.3. Sortowanie bąbelkowe 358
11.2. Drzewa decyzyjne 364
11.3. Efektywne algorytmy sortowania 367
11.3.1. Sortowanie metodą Shella 367
11.3.2. Sortowanie przez kopcowanie 372
11.3.3. Sortowanie szybkie 379
11.3.4. Sortowanie przez scalanie 388
11.3.5. Sortowanie pozycyjne 391
11.4. Uwagi końcowe 397
11.5. Przykład: dodawanie wielomianów 399
11.6. Ćwiczenia 406
11.7. Zadania programistyczne 408
12. Mieszanie 412
12.1. Funkcje mieszające 413
12.1.1. Dzielenie 413
12.1.2. Składanie 414
12.1.3. Funkcja „środek kwadratu" 414
12.1.4. Wycinanie 415
12.1.5. Zamiana podstawy 415
12.2. Rozwiązywanie problemu kolizji 415
12.2.1. Adresowanie otwarte 416
12.2.2. Metoda łańcuchowa 422
12.2.3. Adresowanie kubełkowe 425
12.3. Usuwanie 426
12.4. Doskonałe funkcje mieszające 427
12.4.1. Metoda Cichelliego 428
12.4.2. Algorytm FHCD 431
#9
12.5. Funkcje mieszające dla plików rozszerzalnych 434
12.5.1. Mieszanie przedłużalne 434
12.5.2. Mieszanie liniowe 437
12.6. Przykład: mieszanie z użyciem kubełków 440
12.7. Ćwiczenia 447
12.8. Zadania programistyczne 448
13. Kompresja danych 451
13.1. Wymagania dotyczące kompresji danych 451
13.2. Metoda Huffmana 453
13.2.1. Adaptacyjne kody Huffmana 463
13.3. Metoda Shannona-Fano 467
13.4. Kodowanie długości serii 469
13.5. Metoda Ziva-Lempela 471
13.6. Przykład: metoda Huffmana z kodowaniem długości serii 474
13.7. Ćwiczenia 483
13.8. Zadania programistyczne 485
14. Zarządzanie pamięcią 487
14.1. Metody dopasowywania sekwencyjnego 488
14.2. Metody niesekwencyjne 490
14.2.1. Systemy par 492
14.3. Odśmiecanie 500
14.3.1. Metoda „zaznacz-i-usuń" 501
14.3.2. Metody kopiowania 509
14.3.3. Odśmiecanie krokowe 510
14.4. Uwagi końcowe 519
14.5. Przykład: odśmiecanie „w miejscu" 520
14.6. Ćwiczenia 525
14.7. Zadania programistyczne 527
DODATEK A. Obliczenia przybliżone 532
A.1. Szereg harmoniczny 532
A.2. Oszacowanie funkcji lg(n!) 532
A.3. Średnia złożoność algorytmu auicksort 535
A.4. Średnia długość ścieżki w losowym drzewie binarnym 536
Skorowidz 538