Algorytmy_i_struktury_danych_alstrd.pdf

(928 KB) Pobierz
IDZ DO
PRZYK£ADOWY ROZDZIA£
SPIS TRE CI
KATALOG KSI¥¯EK
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
Algorytmy i struktury
danych
Autorzy: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
T³umaczenie: Andrzej Gra¿yñski
ISBN: 83-7361-177-0
Tytu³ orygina³u:
Data Structures and Algorithms
Format: B5, stron: 442
W niniejszej ksi¹¿ce przedstawiono struktury danych i algorytmy stanowi¹ce podstawê
wspó³czesnego programowania komputerów. Algorytmy s¹ niczym przepis na
rozwi¹zanie postawionego przed programistê problemu. S¹ one nierozerwalnie
zwi¹zane ze strukturami danych — listami, rekordami, tablicami, kolejkami, drzewami…
podstawowymi elementami wiedzy ka¿dego programisty.
Ksi¹¿ka obejmuje szeroki zakres materia³u, a do jej lektury wystarczy znajomo æ
dowolnego jêzyka programowania strukturalnego (np. Pascala). Opis klasycznych
algorytmów uzupe³niono o algorytmy zwi¹zane z zarz¹dzaniem pamiêci¹ operacyjn¹
i pamiêciami zewnêtrznymi.
Ksi¹¿ka przedstawia algorytmy i struktury danych w kontek cie rozwi¹zywania
problemów za pomoc¹ komputera. Z tematyk¹ rozwi¹zywania problemów powi¹zano
zagadnienie zliczania kroków oraz z³o¿ono ci czasowej — wynika to z g³êbokiego
przekonania autorów tej ksi¹¿ki, i¿ wraz z pojawianiem siê coraz szybszych
komputerów, pojawiaæ siê bêd¹ tak¿e coraz bardziej z³o¿one problemy
do rozwi¹zywania i — paradoksalnie — z³o¿ono æ obliczeniowa u¿ywanych
algorytmów zyskiwaæ bêdzie na znaczeniu.
W ksi¹¿ce omówiono m.in.:
• Tradycyjne struktury danych: listy, kolejki, stosy
• Drzewa i operacje na strukturach drzew
• Typy danych oparte na zbiorach, s³owniki i kolejki priorytetowe wraz
ze sposobami ich implementacji
• Grafy zorientowane i niezorientowane
• Algorytmy sortowania i poszukiwania mediany
• Asymptotyczne zachowanie siê procedur rekurencyjnych
• Techniki projektowania algorytmów: „dziel i rz¹d ”, wyszukiwanie lokalne
i programowanie dynamiczne
• Zarz¹dzanie pamiêci¹, B-drzewa i struktury indeksowe
Ka¿demu rozdzia³owi towarzyszy zestaw æwiczeñ, o zró¿nicowanym stopniu trudno ci,
pomagaj¹cych sprawdziæ swoj¹ wiedzê. „Algorytmy i struktury danych” to doskona³y
podrêcznik dla studentów informatyki i pokrewnych kierunków, a tak¿e dla wszystkich
zainteresowanych t¹ tematyk¹.
TWÓJ KOSZYK
DODAJ DO KOSZYKA
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWO CIACH
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 treści
Od tłumacza .............................................................................................................7
Wstęp .....................................................................................................................11
1
Projektowanie i analiza algorytmów......................................................................15
1.1. Od problemu do programu ......................................................................................................................... 15
1.2. Abstrakcyjne typy danych.......................................................................................................................... 23
1.3. Typy danych, struktury danych i ADT ...................................................................................................... 25
1.4. Czas wykonywania programu .................................................................................................................... 28
1.5. Obliczanie czasu wykonywania programu................................................................................................. 33
1.6. Dobre praktyki programowania ................................................................................................................. 39
1.7. Super Pascal ............................................................................................................................................... 41
Ćwiczenia .......................................................................................................................................................... 44
Uwagi bibliograficzne ....................................................................................................................................... 48
2
Podstawowe abstrakcyjne typy danych .................................................................49
2.1. Lista jako abstrakcyjny typ danych............................................................................................................ 49
2.2. Implementacje list ...................................................................................................................................... 52
2.3. Stosy ........................................................................................................................................................... 64
2.4. Kolejki........................................................................................................................................................ 68
2.5. Mapowania ................................................................................................................................................. 73
2.6. Stosy a procedury rekurencyjne ................................................................................................................. 75
Ćwiczenia .......................................................................................................................................................... 80
Uwagi bibliograficzne ....................................................................................................................................... 84
3
Drzewa ...................................................................................................................85
3.1. Podstawowa terminologia .......................................................................................................................... 85
3.2. Drzewa jako abstrakcyjne obiekty danych................................................................................................. 92
4
SPIS TREŚCI
3.3. Implementacje drzew ................................................................................................................................. 95
3.4. Drzewa binarne ........................................................................................................................................ 102
Ćwiczenia ........................................................................................................................................................ 113
Uwagi bibliograficzne ..................................................................................................................................... 116
4
Podstawowe operacje na zbiorach .......................................................................117
4.1. Wprowadzenie do zbiorów....................................................................................................................... 117
4.2. Słowniki ................................................................................................................................................... 129
4.3. Tablice haszowane ................................................................................................................................... 132
4.4. Implementacja abstrakcyjnego typu danych MAPPING ......................................................................... 146
4.5. Kolejki priorytetowe ................................................................................................................................ 148
4.6. Przykłady zło onych struktur zbiorowych............................................................................................... 156
Ćwiczenia ........................................................................................................................................................ 163
Uwagi bibliograficzne ..................................................................................................................................... 165
5
Zaawansowane metody reprezentowania zbiorów ..............................................167
5.1. Binarne drzewa wyszukiwawcze ............................................................................................................. 167
5.2. Analiza zło oności operacji wykonywanych na binarnym drzewie wyszukiwawczym.......................... 171
5.3. Drzewa trie ............................................................................................................................................... 175
5.4. Implementacja zbiorów w postaci drzew wywa onych — 2-3-drzewa................................................... 181
5.5. Operacje MERGE i FIND ........................................................................................................................ 193
5.6. Abstrakcyjny typ danych z operacjami MERGE i SPLIT ....................................................................... 202
Ćwiczenia ........................................................................................................................................................ 207
Uwagi bibliograficzne ..................................................................................................................................... 209
6
Grafy skierowane .................................................................................................211
6.1. Podstawowe pojęcia ................................................................................................................................. 211
6.2. Reprezentacje grafów skierowanych........................................................................................................ 213
6.3. Graf skierowany jako abstrakcyjny typ danych ....................................................................................... 215
6.4. Znajdowanie najkrótszych ście ek o wspólnym początku....................................................................... 217
6.5. Znajdowanie najkrótszych ście ek między ka dą parą wierzchołków .................................................... 221
6.6. Przechodzenie przez grafy skierowane — przeszukiwanie zstępujące.................................................... 229
6.7. Silna spójność i silnie spójne składowe digrafu....................................................................................... 237
Ćwiczenia ........................................................................................................................................................ 240
Uwagi bibliograficzne ..................................................................................................................................... 242
7
Grafy nieskierowane ............................................................................................243
7.1. Definicje ................................................................................................................................................... 243
7.2. Metody reprezentowania grafów.............................................................................................................. 245
7.3. Drzewa rozpinające o najmniejszym koszcie........................................................................................... 246
7.4. Przechodzenie przez graf ......................................................................................................................... 253
7.5. Wierzchołki rozdzielające i składowe dwuspójne grafu .......................................................................... 256
SPIS TREŚCI
5
7.6. Reprezentowanie skojarzeń przez grafy................................................................................................... 259
Ćwiczenia ........................................................................................................................................................ 262
Uwagi bibliograficzne ..................................................................................................................................... 264
8
Sortowanie ...........................................................................................................265
8.1. Model sortowania wewnętrznego............................................................................................................. 265
8.2. Proste algorytmy sortowania wewnętrznego............................................................................................ 266
8.3. Sortowanie szybkie (quicksort)................................................................................................................ 273
8.4. Sortowanie stogowe ................................................................................................................................. 283
8.5. Sortowanie rozrzutowe............................................................................................................................. 287
8.6. Dolne ograniczenie dla sortowania za pomocą porównań ....................................................................... 294
8.7. Szukanie k-tej wartości (statystyki pozycyjne)........................................................................................ 298
Ćwiczenia ........................................................................................................................................................ 302
Uwagi bibliograficzne ..................................................................................................................................... 304
9
Techniki analizy algorytmów ..............................................................................305
9.1. Efektywność algorytmów......................................................................................................................... 305
9.2. Analiza programów zawierających wywołania rekurencyjne.................................................................. 306
9.3. Rozwiązywanie równań rekurencyjnych ................................................................................................. 308
9.4. Rozwiązanie ogólne dla pewnej klasy rekurencji .................................................................................... 311
Ćwiczenia ........................................................................................................................................................ 316
Uwagi bibliograficzne ..................................................................................................................................... 319
10
Techniki projektowania algorytmów ...................................................................321
10.1. Zasada „dziel i zwycię aj” ..................................................................................................................... 321
10.2. Programowanie dynamiczne .................................................................................................................. 327
10.3. Algorytmy zachłanne ............................................................................................................................. 335
10.4. Algorytmy z nawrotami ......................................................................................................................... 339
10.5. Przeszukiwanie lokalne .......................................................................................................................... 349
Ćwiczenia ........................................................................................................................................................ 355
Uwagi bibliograficzne ..................................................................................................................................... 358
11
Struktury danych i algorytmy obróbki danych zewnętrznych .............................359
11.1. Model danych zewnętrznych.................................................................................................................. 359
11.2. Sortowanie zewnętrzne .......................................................................................................................... 362
11.3. Przechowywanie informacji w plikach pamięci zewnętrznych ............................................................. 373
11.4. Zewnętrzne drzewa wyszukiwawcze ..................................................................................................... 381
Ćwiczenia ........................................................................................................................................................ 387
Uwagi bibliograficzne ..................................................................................................................................... 390
6
SPIS TREŚCI
12
Zarządzanie pamięcią ..........................................................................................391
12.1. Podstawowe aspekty zarządzania pamięcią ........................................................................................... 391
12.2. Zarządzanie blokami o ustalonej wielkości ........................................................................................... 395
12.3. Algorytm odśmiecania dla bloków o ustalonej wielkości...................................................................... 397
12.4. Przydział pamięci dla obiektów o zró nicowanych rozmiarach ............................................................ 405
12.5. Systemy partnerskie ............................................................................................................................... 412
12.6. Upakowywanie pamięci ......................................................................................................................... 416
Ćwiczenia ........................................................................................................................................................ 419
Uwagi bibliograficzne ..................................................................................................................................... 421
Bibliografia ..........................................................................................................423
Skorowidz ............................................................................................................429

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin