Dane szczegółowe książki
Algorytmy-struktury_danych-programy / Wirth, Niklaus; Iglewski, Michał
Autorzy
Tytuł
Algorytmy-struktury_danych-programy
Tytuł oryginału
Algorithms + data structures = programs
Wydawnictwo
Warszawa: Wydawnictwa Naukowo-Techniczne, 2002
Numer wydania
6
ISBN
8320427401
Hasła przedmiotowe
Spis treści
pokaż spis treści
Przedmowa NANI 15
1 Podstawowe struktury danych 24
1.1. Wprowadzenie 24
1.2. Pojęcie typu danych 29
1.3. Proste typy danych 35
1.4. Standardowe typy proste 37
1.5. Typy okrojone 42
1.6. Tablice 44
1.7. Rekordy 52
1.8. Rekordy z wariantami 61
1.9. Zbiory 65
1.10. Reprezentacja tablic, rekordów i zbiorów 76
1.10.1. Reprezentacja tablic 78
1.10.2. Reprezentacja rekordów 82
1.10.3. Reprezentacja zbiorów 84
1.11. Plik sekwencyjny 87
1.11.1. Elementarne operatory plikowe 92
1.11.2. Pliki z podstrukturami 98
1.11.3. Teksty 102
1.11.4. Program redagowania pliku 118
2 Sortowanie 131
2.1. Wprowadzenie 131
2.2. Sortowanie tablic 136
2.2.1. Sortowanie przez proste wstawianie 138
2.2.2. Sortowanie przez proste wybieranie 144
2.2.3. Sortowanie przez prostą zamianę 148
2.2.4. Sortowanie za pomocą malejących przyrostów 155
2.2.5. Sortowanie drzewiaste 159
2.2.6. Sortowanie przez podział 170
2.2.7. Znajdowanie mediany 184
2.2.8. Porównanie metod sortowania tablic 188
2.3. Sortowanie plików sekwencyjnych 193
2.3.1. Łączenie proste 193
2.3.2. Łączenie naturalne 204
2.3.3. Wielokierunkowe łączenie wyważone 218
2.3.4. Sortowanie polifazowe 231
2.3.5. Rozdzielanie serii początkowych 254
3 Algorytmy rekurencyjne 272
3.1. Wprowadzenie 272
3.2. Kiedy nie stosować rekursji 276
3.3. Dwa przykłady programów rekurencyjnych 282
3.4. Algorytmy z powrotami 295
3.5. Problem ośmiu hetmanów 306
3.6. Problem trwałego małżeństwa 316
3.7. Problem optymalnego wyboru 330
4 Dynamiczne struktury informacyjne 345
4.1. Rekurencyjne typy danych 345
4.2. Wskaźniki lub odniesienia 350
4.3. Listy liniowe 362
4.3.1. Operacje podstawowe 362
4.4. Struktury drzewiaste 399
4.4.1. Pojęcia podstawowe i definicje 399
4.4.2. Podstawowe operacje na drzewach binarnych 416
4.4.3. Przeszukiwanie drzewa z wstawianiem 422
4.4.4. Usuwanie z drzewa 438
4.4.5. Analiza przeszukiwania drzewa z wstawianiem 442
4.4.6. Drzewa zrównoważone 448
4.4.7. Wstawianie w drzewach zrównoważonych 452
4.4.8. Usuwanie węzłów z drzew zrównoważonych 462
4.4.9. Optymalne drzewa poszukiwań 470
4.4.10. Drukowanie struktury drzewa 482
4.5. Drzewa wielokierunkowe 500
4.5.1. B-drzewa 504
4.5.2. Binarne B-drzewa 526
4.6. Transformacje kluczy (kodowanie mieszające) 537
4.6.1. Wybór funkcji transformującej 541
4.6.2. Usuwanie kolizji 541
4.6.3. Analiza transformacji kluczy 553
5 Struktury językowe i kompilatory 570
5.1. Definicja i struktura języka 570
5.2. Analiza zdań 575
5.3. Konstrukcja diagramu składni 585
5.4. Konstrukcja analizatora składniowego dla zadanej gramatyki 592
5.5. Konstrukcja programu analizatora sterowanego składnią 599
5.6. Translator z notacji BNF na struktury danych sterujące analizatorem 604
5.7. Język programowania PL/0 620
5.8. Analizator składniowy dla języka PL/0 627
5.9. Reagowanie na błędy składniowe 645
5.10. Maszyna PL/0 667
5.11. Generowanie kodu wynikowego 673
1 Podstawowe struktury danych 24
1.1. Wprowadzenie 24
1.2. Pojęcie typu danych 29
1.3. Proste typy danych 35
1.4. Standardowe typy proste 37
1.5. Typy okrojone 42
1.6. Tablice 44
1.7. Rekordy 52
1.8. Rekordy z wariantami 61
1.9. Zbiory 65
1.10. Reprezentacja tablic, rekordów i zbiorów 76
1.10.1. Reprezentacja tablic 78
1.10.2. Reprezentacja rekordów 82
1.10.3. Reprezentacja zbiorów 84
1.11. Plik sekwencyjny 87
1.11.1. Elementarne operatory plikowe 92
1.11.2. Pliki z podstrukturami 98
1.11.3. Teksty 102
1.11.4. Program redagowania pliku 118
2 Sortowanie 131
2.1. Wprowadzenie 131
2.2. Sortowanie tablic 136
2.2.1. Sortowanie przez proste wstawianie 138
2.2.2. Sortowanie przez proste wybieranie 144
2.2.3. Sortowanie przez prostą zamianę 148
2.2.4. Sortowanie za pomocą malejących przyrostów 155
2.2.5. Sortowanie drzewiaste 159
2.2.6. Sortowanie przez podział 170
2.2.7. Znajdowanie mediany 184
2.2.8. Porównanie metod sortowania tablic 188
2.3. Sortowanie plików sekwencyjnych 193
2.3.1. Łączenie proste 193
2.3.2. Łączenie naturalne 204
2.3.3. Wielokierunkowe łączenie wyważone 218
2.3.4. Sortowanie polifazowe 231
2.3.5. Rozdzielanie serii początkowych 254
3 Algorytmy rekurencyjne 272
3.1. Wprowadzenie 272
3.2. Kiedy nie stosować rekursji 276
3.3. Dwa przykłady programów rekurencyjnych 282
3.4. Algorytmy z powrotami 295
3.5. Problem ośmiu hetmanów 306
3.6. Problem trwałego małżeństwa 316
3.7. Problem optymalnego wyboru 330
4 Dynamiczne struktury informacyjne 345
4.1. Rekurencyjne typy danych 345
4.2. Wskaźniki lub odniesienia 350
4.3. Listy liniowe 362
4.3.1. Operacje podstawowe 362
4.4. Struktury drzewiaste 399
4.4.1. Pojęcia podstawowe i definicje 399
4.4.2. Podstawowe operacje na drzewach binarnych 416
4.4.3. Przeszukiwanie drzewa z wstawianiem 422
4.4.4. Usuwanie z drzewa 438
4.4.5. Analiza przeszukiwania drzewa z wstawianiem 442
4.4.6. Drzewa zrównoważone 448
4.4.7. Wstawianie w drzewach zrównoważonych 452
4.4.8. Usuwanie węzłów z drzew zrównoważonych 462
4.4.9. Optymalne drzewa poszukiwań 470
4.4.10. Drukowanie struktury drzewa 482
4.5. Drzewa wielokierunkowe 500
4.5.1. B-drzewa 504
4.5.2. Binarne B-drzewa 526
4.6. Transformacje kluczy (kodowanie mieszające) 537
4.6.1. Wybór funkcji transformującej 541
4.6.2. Usuwanie kolizji 541
4.6.3. Analiza transformacji kluczy 553
5 Struktury językowe i kompilatory 570
5.1. Definicja i struktura języka 570
5.2. Analiza zdań 575
5.3. Konstrukcja diagramu składni 585
5.4. Konstrukcja analizatora składniowego dla zadanej gramatyki 592
5.5. Konstrukcja programu analizatora sterowanego składnią 599
5.6. Translator z notacji BNF na struktury danych sterujące analizatorem 604
5.7. Język programowania PL/0 620
5.8. Analizator składniowy dla języka PL/0 627
5.9. Reagowanie na błędy składniowe 645
5.10. Maszyna PL/0 667
5.11. Generowanie kodu wynikowego 673