Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00555 008283 10456763 na godz. na dobę w sumie
Java. Algorytmy i struktury danych - książka
Java. Algorytmy i struktury danych - książka
Autor: Liczba stron: 704
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-123-1 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> java - programowanie
Porównaj ceny (książka, ebook, audiobook).

Książka 'Java. Algorytmy i struktury danych' jest łatwym do zrozumienia podręcznikiem poświęconym złożonym zagadnieniom gromadzenia i zarządzania danymi w taki sposób, aby uzyskać maksymalną efektywność działania programów komputerowych. Niezależnie od używanej platformy systemowej oraz języka programowania, opanowanie zagadnień przedstawionych w niniejszej książce poprawi jakość i efektywność tworzonego oprogramowania. Dzięki wykorzystaniu Javy do implementacji najważniejszych pojęć, uniknięto problemów związanych ze złożonością języków C oraz C++ i w pełni skoncentrowano się na prezentacji algorytmów i struktur danych.

Autor -- Robert Lafore -- prezentuje proste i zrozumiałe przykłady unikając niepotrzebnej matematyki i skomplikowanych dowodów, często pojawiających się w książkach o tej tematyce. W prezentowanym drugim wydaniu książki, autor udoskonalił i rozbudował przykłady, wykorzystując w nich najnowsze możliwości Javy. Na końcu każdego z rozdziałów zostały zamieszczone pytania i odpowiedzi, umożliwiające sprawdzenie stopnia zrozumienia i opanowania omawianych zagadnień.

W książce opisano:
Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREĎCI SPIS TREĎCI KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOĎCIACH O NOWOĎCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Java. Algorytmy i struktury danych Autor: Robert Lafore T³umaczenie: Przemys³aw Kowalczyk (rozdz. 1 – 5), Piotr Rajca (rozdz. 6 – 9), Pawe³ Koronkiewicz (rozdz. 9 – 15, dod. A – C) ISBN: 83-7361-123-1 Tytu³ orygina³u: Data Structures Algorithms in Java, 2nd Edition Format: B5, stron: 704 Ksi¹¿ka „Java. Algorytmy i struktury danych” jest ³atwym do zrozumienia podrêcznikiem poġwiêconym z³o¿onym zagadnieniom gromadzenia i zarz¹dzania danymi w taki sposób, aby uzyskaæ maksymaln¹ efektywnoġæ dzia³ania programów komputerowych. Niezale¿nie od u¿ywanej platformy systemowej oraz jêzyka programowania, opanowanie zagadnieñ przedstawionych w niniejszej ksi¹¿ce poprawi jakoġæ i efektywnoġæ tworzonego oprogramowania. Dziêki wykorzystaniu Javy do implementacji najwa¿niejszych pojêæ, unikniêto problemów zwi¹zanych ze z³o¿onoġci¹ jêzyków C oraz C++ i w pe³ni skoncentrowano siê na prezentacji algorytmów i struktur danych. Autor — Robert Lafore — prezentuje proste i zrozumia³e przyk³ady unikaj¹c niepotrzebnej matematyki i skomplikowanych dowodów, czêsto pojawiaj¹cych siê w ksi¹¿kach o tej tematyce. W prezentowanym drugim wydaniu ksi¹¿ki, autor udoskonali³ i rozbudowa³ przyk³ady, wykorzystuj¹c w nich najnowsze mo¿liwoġci Javy. Na koñcu ka¿dego z rozdzia³ów zosta³y zamieszczone pytania i odpowiedzi, umo¿liwiaj¹ce sprawdzenie stopnia zrozumienia i opanowania omawianych zagadnieñ. W ksi¹¿ce opisano: • Tablice • Proste i z³o¿one algorytmy sortowania • Stosy i kolejki • Listy • Zastosowania rekurencji • Ró¿ne rodzaje drzew i sposoby ich implementacji • Tablice rozproszone • Sterty • Grafy i grafy wa¿one • Dobór w³aġciwych algorytmów i struktur danych Robert Lafore pisze o programowaniu od 1982 roku. Do jego najbardziej poczytnych ksi¹¿ek nale¿¹: „Object-oriented Programming in C++”, która zosta³a sprzedana w ponad 200 tysi¹cach egzemplarzy na ca³ym ġwiecie, „Assembly Language Programming for the IBM PC”, „C Programming Using Turbo C++” oraz „C++ Interactive Course”. Lafore posiada tytu³y naukowe z matematyki i elektryki, a programowaniem zajmuje siê aktywnie od czasów, gdy królowa³y komputery PDP-5 i gdy 4 kB Spis treści O Autorze.................................................................................................................19 Drogi Czytelniku.....................................................................................................20 Wprowadzenie .........................................................................................................21 Co nowego w drugim wydaniu? ...................................................u.................................................................... 21 Dodatkowe tematy...................................................u...................................................u.......................... 21 Pytania końcowe...................................................u...................................................u............................. 22 Eksperymenty ...................................................u...................................................u................................. 22 Projekty programistyczne ...................................................u...................................................u............... 22 O czym jest ta książka? ...................................................u...................................................u............................... 22 Czym ta książka różni się od innych? ...................................................u............................................................ 23 Łatwa do zrozumienia ...................................................u...................................................u.................... 23 Warsztaty algorytmów...................................................u...................................................u.................... 24 Przykłady w Javie...................................................u...................................................u........................... 24 Komu może się przydać ta książka? ...................................................u.............................................................. 25 Co musimy wiedzieć, zanim zaczniemy ją czytać? ...................................................u....................................... 25 Potrzebne oprogramowanie...................................................u...................................................u......................... 25 Organizacja książki ...................................................u...................................................u..................................... 25 Dobrej zabawy! ...................................................u...................................................u........................................... 27 1. Przegląd ...................................................................................................................29 Do czego są przydatne struktury danych i algorytmy? ...................................................u.................................. 29 Przechowywanie danych ze świata zewnętrznego ...................................................u............................ 30 Narzędzia programisty...................................................u...................................................u.................... 31 Modelowanie danych ze świata zewnętrznego...................................................u.................................. 31 Przegląd struktur danych...................................................u...................................................u............................. 31 Przegląd algorytmów ...................................................u...................................................u.................................. 31 Kilka definicji...................................................u...................................................u.............................................. 32 Baza danych...................................................u...................................................u.................................... 32 Rekord ...................................................u...................................................u............................................ 33 6 SPIS TREŚCI Pole ...................................................u...................................................u..................... ............................ 33 Klucz...................................................u...................................................u............................................... 33 Programowanie obiektowe...................................................u...................................................u.......................... 34 Problemy z językami proceduralnymi...................................................u............................................... 34 Obiekty w telegraficznym skrócie...................................................u..................................................... 35 Działający program obiektowy...................................................u.......................................................... 37 Dziedziczenie i polimorfizm ...................................................u............................................................. 39 Inżynieria programowania............................u...................................................u.................................................. 40 Java dla programistów C++ ...................................................u...................................................u........................ 40 Brak wskaźników ...................................................u...................................................u........................... 41 Operatory przeciążone...................................................u...................................................u.................... 44 Typy proste ...................................................u...................................................u..................................... 44 Operacje wejścia-wyjścia ...................................................u...................................................u............... 44 Struktury danych w bibliotece Javy ...................................................u............................................................... 47 Podsumowanie ...................................................u...................................................u............................................ 47 Pytania...................................................u...................................................u.................. ....................................... 48 2. Tablice .....................................................................................................................49 Aplet demonstracyjny ...................................................u...................................................u................................. 49 Wstawianie ...................................................u...................................................u..................................... 51 Wyszukiwanie ...................................................u...................................................u................................ 51 Usuwanie ...................................................u...................................................u........................................ 52 Kwestia duplikatów ...................................................u...................................................u........................ 53 Niezbyt szybko ...................................................u...................................................u............................... 55 Tablice w Javie...................................................u...................................................u............................................ 55 Tworzenie tablicy ...................................................u...................................................u........................... 55 Dostęp do elementów tablicy ...................................................u............................................................ 56 Inicjalizacja...................................................u...................................................u..................................... 56 .................. 57 Przykład użycia tablic...................................................u...................................................u... Dzielenie programu na klasy...................................................u.......................................................................... 59 Klasy LowArray i LowArrayApp...................................................u...................................................... 61 Interfejsy klas ...................................................u...................................................u.............................................. 61 Niezbyt wygodnie...................................................u...................................................u........................... 62 Kto i za co odpowiada? ...................................................u...................................................u.................. 62 Program highArray.java ...................................................u...................................................u................. 63 … i życie użytkownika stało się prostsze...................................................u.......................................... 66 Abstrakcja...................................................u...................................................u....................................... 66 Aplet demonstrujący tablicę uporządkowaną ...................................................u................................................ 66 Wyszukiwanie liniowe ...................................................u...................................................u................... 66 Wyszukiwanie binarne ...................................................u...................................................u................... 67 Tablica uporządkowana w Javie ...................................................u.................................................................... 69 Wyszukiwanie binarne w metodzie find()...................................................u......................................... 70 Klasa OrdArray...................................................u...................................................u............................... 71 Korzyści wynikające z używania tablic uporządkowanych ...................................................u.............. 74 ................................... 74 Potęgowanie...................................................u...................................................u.................................... 75 Przeciwieństwo podnoszenia do potęgi...................................................u............................................. 76 Przechowywanie obiektów...................................................u...................................................u.......................... 76 Klasa Person ...................................................u...................................................u................................... 76 Program classDataArray.java ...................................................u............................................................ 77 Logarytmy ...................................................u...................................................u................ SPIS TREŚCI 7 Notacja O()...................................................u...................................................u.................................................. 81 Wstawianie do tablicy nieuporządkowanej: czas stały...................................................u...................... 81 Wyszukiwanie liniowe: czas proporcjonalny do N ...................................................u........................... 81 Wyszukiwanie binarne: czas proporcjonalny do log(N) ...................................................u................... 82 Stała niepotrzebna...................................................u...................................................u........................... 82 Czy tablice nadają się do wszystkiego? ...................................................u......................................................... 83 Podsumowanie ...................................................u...................................................u............................................ 84 Pytania...................................................u...................................................u.................. ....................................... 85 Eksperymenty...................................................u...................................................u.............................................. 86 Projekty programistyczne...................................................u...................................................u............................ 86 3. Proste algorytmy sortowania ..................................................................................87 W szeregu zbiórka!....................................u...................................................u..................................................... 88 Sortowanie bąbelkowe ...................................................u...................................................u................................ 89 Sortowanie bąbelkowe zawodników drużyny ...................................................u................................... 89 Aplet demonstracyjny sortowania bąbelkowego...................................................u............................... 91 Sortowanie bąbelkowe w Javie...................................................u.......................................................... 94 Niezmienniki ...................................................u...................................................u.................................. 97 Wydajność sortowania bąbelkowego ...................................................u................................................ 97 Sortowanie przez wybór...................................................u...................................................u.............................. 98 Sortowanie przez wybór drużyny baseballowej ...................................................u................................ 98 Aplet demonstracyjny sortowania przez wybór ...................................................u.............................. 100 Sortowanie przez wybór w Javie ...................................................u..................................................... 101 Niezmiennik...................................................u...................................................u.................................. 103 Wydajność sortowania przez wybór...................................................u................................................ 103 Sortowanie przez wstawianie ...................................................u....................................................................... 103 Sortowanie przez wstawianie drużyny baseballowej ...................................................u...................... 103 Aplet demonstracyjny sortowania przez wstawianie...................................................u....................... 104 Sortowanie przez wstawianie w Javie ...................................................u............................................. 107 Niezmiennik w sortowaniu przez wstawianie ...................................................u................................. 110 Wydajność sortowania przez wstawianie ...................................................u........................................ 110 Sortowanie obiektów...................................................u...................................................u................................. 111 Program sortujący tablicę obiektów ...................................................u................................................ 111 Porównania leksykograficzne...................................................u.......................................................... 114 Stabilność...................................................u...................................................u............... ....................... 115 Porównanie prostych algorytmów sortowania ...................................................u............................................. 115 Podsumowanie ...................................................u...................................................u.......................................... 115 Pytania...................................................u...................................................u.................. ..................................... 116 Eksperymenty...................................................u...................................................u............................................ 117 Projekty programistyczne...................................................u...................................................u.......................... 118 4. Stosy i kolejki ........................................................................................................121 Inny rodzaj struktur danych.........................u...................................................u................................................. 121 Narzędzia programisty...................................................u...................................................u.................. 121 Ograniczony dostęp ...................................................u...................................................u...................... 122 Bardziej abstrakcyjne ...................................................u...................................................u................... 122 ...................................... 122 Analogia pocztowa ...................................................u...................................................u....................... 123 Aplet demonstracyjny stosu...................................................u............................................................. 124 Stosy...................................................u...................................................u.................... 8 SPIS TREŚCI Kolejki...................................................u...................................................u.................. Stos w Javie ...................................................u...................................................u.................................. 126 Wykorzystanie stosu do odwracania słowa ...................................................u.....................................129 Wykorzystanie stosu do sprawdzania nawiasów...................................................u............................. 131 Wydajność stosów ...................................................u...................................................u........................ 136 ..................................... 136 Aplet demonstracyjny kolejki...................................................u.......................................................... 137 Kolejka cykliczna ...................................................u...................................................u......................... 140 Kolejka w Javie ...................................................u...................................................u............................ 141 Wydajność kolejek ...................................................u...................................................u....................... 146 Kolejki dwustronne...................................................u...................................................u....................... 146 Kolejki priorytetowe ...................................................u...................................................u................................. 146 Aplet demonstracyjny kolejki priorytetowej ...................................................u................................... 147 Kolejka priorytetowa w Javie ...................................................u.......................................................... 150 Wydajność kolejek priorytetowych ...................................................u................................................. 152 Analiza wyrażeń arytmetycznych ...................................................u................................................................ 152 Notacja przyrostkowa ...................................................u...................................................u................... 152 Zamiana notacji naturalnej na przyrostkową...................................................u................................... 153 Obliczanie wyrażeń w notacji przyrostkowej...................................................u..................................167 Podsumowanie ...................................................u...................................................u.......................................... 172 Pytania...................................................u...................................................u.................. ..................................... 172 Eksperymenty...................................................u...................................................u............................................ 174 Projekty programistyczne...................................................u...................................................u.......................... 174 5. Listy powiązane ....................................................................................................177 Połączenia.........................................u...................................................u............................................................ 178 Referencje i typy proste...................................................u...................................................u................ 179 Relacja, nie pozycja...................................................u...................................................u...................... 180 Aplet demonstracyjny listy powiązanej ...................................................u....................................................... 181 Przycisk Ins...................................................u...................................................u................................... 181 Przycisk Find ...................................................u...................................................u............ .................... 182 Przycisk Del...................................................u...................................................u.................................. 182 Prosta lista powiązana ...................................................u...................................................u............................... 183 Klasa Link...................................................u...................................................u..................................... 183 Klasa LinkList ...................................................u...................................................u........... ................... 184 Metoda insertFirst() ...................................................u...................................................u...................... 185 Metoda deleteFirst() ...................................................u...................................................u..................... 186 Metoda displayList()...................................................u...................................................u..................... 187 Program linkList.java ...................................................u...................................................u................... 187 Wyszukiwanie i usuwanie określonych elementów...................................................u..................................... 190 Metoda find()...................................................u...................................................u................................ 193 Metoda delete()...................................................u...................................................u............................. 193 Inne metody ...................................................u...................................................u.................................. 194 Listy dwustronne...................................................u...................................................u....................................... 194 Wydajność list powiązanych...................................................u........................................................................ 198 Abstrakcyjne typy danych...................................................u...................................................u......................... 199 Implementacja stosu przy użyciu listy powiązanej ...................................................u......................... 199 Implementacja kolejki przy użyciu listy powiązanej ...................................................u...................... 202 Typy danych i abstrakcja...................................................u...................................................u.............. 205 Listy abstrakcyjne...................................................u...................................................u......................... 206 Abstrakcyjne typy danych jako narzędzia projektowe ...................................................u.................... 206 SPIS TREŚCI 9 Listy uporządkowane ...................................................u...................................................u................................ 207 Wstawianie do listy uporządkowanej w Javie...................................................u................................. 209 Program sortedList.java...................................................u...................................................u................ 210 Wydajność list uporządkowanych ...................................................u................................................... 212 Sortowanie przez wstawianie do listy ...................................................u............................................. 212 Listy dwukierunkowe...................................................u...................................................u................................ 214 Przeglądanie...................................................u...................................................u.................................. 216 Wstawianie ...................................................u...................................................u................................... 216 Usuwanie ...................................................u...................................................u...................................... 218 Program doublyLinked.java ...................................................u...................................................u......... 219 Listy dwukierunkowe jako podstawa kolejek dwustronnych...................................................u.......... 223 Iteratory ...................................................u...................................................u..................................................... 223 Referencja w liście?...................................................u...................................................u...................... 224 Klasa iteratora...................................................u...................................................u............................... 224 Dodatkowe możliwości iteratorów...................................................u.................................................. 225 Metody klasy iteratorowej ...................................................u...................................................u............ 226 Program interIterator.java...................................................u................................................................ 227 Na co wskazuje iterator?...................................................u...................................................u............... 232 Metoda atEnd() ...................................................u...................................................u............................. 233 Operacje iteracyjne ...................................................u...................................................u....................... 233 Inne metody ...................................................u...................................................u.................................. 234 Podsumowanie ...................................................u...................................................u.......................................... 235 Pytania...................................................u...................................................u.................. ..................................... 236 Eksperymenty...................................................u...................................................u............................................ 237 Projekty programistyczne...................................................u...................................................u.......................... 237 6. Rekurencja .............................................................................................................239 Liczby trójkątne.....................................u...................................................u....................................................... 239 Określanie wartości n-tego elementu przy użyciu pętli...................................................u................... 240 Określanie wartości n-tego elementu przy użyciu rekurencji ...................................................u......... 241 Program triangle.java...................................................u...................................................u.................... 243 Co się tak naprawdę dzieje? ...................................................u............................................................ 244 Charakterystyczne cechy metod rekurencyjnych ...................................................u............................ 245 Czy rekurencja jest efektywna?...................................................u....................................................... 246 Indukcja matematyczna ...................................................u...................................................u................ 247 Silnia ...................................................u...................................................u................... ...................................... 247 Anagramy...................................................u...................................................u.................................................. 248 Rekurencyjne wyszukiwanie binarne...................................................u........................................................... 254 Zastąpienie pętli rozwiązaniem rekurencyjnym ...................................................u.............................. 255 Algorytmy „dziel i zwyciężaj” ...................................................u........................................................ 258 Wieże Hanoi...................................................u...................................................u.............................................. 259 Aplet Towers Workshop...................................................u...................................................u............... 260 Przesuwanie poddrzew ...................................................u...................................................u................. 261 Algorytm rekurencyjny...................................................u...................................................u................. 262 Program towers.java ...................................................u...................................................u..................... 262 Sortowanie przez scalanie ...................................................u...................................................u......................... 265 Scalanie dwóch posortowanych tablic...................................................u............................................. 265 Sortowanie przez scalanie ...................................................u...................................................u............ 268 Applet MergeSort Workshop...................................................u...................................................u........ 271 Program mergeSort.java ...................................................u...................................................u............... 272 Efektywność działania algorytmu sortowania przez scalanie ...................................................u......... 276 10 SPIS TREŚCI Eliminacja rekurencji ...................................................u...................................................u................................ 278 Rekurencja i stosy...................................................u...................................................u......................... 279 Symulowanie metod rekurencyjnych ...................................................u.............................................. 279 Czego to dowodzi? ...................................................u...................................................u....................... 284 Niektóre interesujące zastosowania rekurencji ...................................................u............................................ 286 Podnoszenie liczby do potęgi ...................................................u.......................................................... 287 Problem plecakowy ...................................................u...................................................u...................... 288 Kombinacje: Wybieranie zespołu...................................................u.................................................... 290 Podsumowanie ...................................................u...................................................u.......................................... 292 Pytania...................................................u...................................................u.................. ..................................... 293 Eksperymenty...................................................u...................................................u............................................ 294 Projekty programów...................................................u...................................................u.................................. 294 7. Zaawansowane algorytmy sortowania..................................................................297 Sortowanie Shella...................................................u...................................................u...................................... 297 Sortowanie przez wstawianie: zbyt wiele operacji kopiowania ...................................................u...... 298 N-sortowanie ...................................................u...................................................u................................ 298 Usuwanie odstępów...................................................u...................................................u...................... 300 Aplet Shellsort Workshop ...................................................u...................................................u. ........... 301 Kod algorytmu Shella napisany w Javie...................................................u.......................................... 303 Inne sekwencje dostępów ...................................................u...................................................u............. 306 Efektywność działania algorytmu Shella ...................................................u........................................ 306 Podział danych ...................................................u...................................................u.......................................... 307 Aplet demonstracyjny Partitioning...................................................u.................................................. 307 Program Partition.java ...................................................u...................................................u.................. 309 Algorytm podziału danych ...................................................u...................................................u........... 311 Efektywność działania algorytmu podziału...................................................u..................................... 314 Quicksort ...................................................u...................................................u................................................... 314 Algorytm quicksort...................................................u...................................................u....... ................ 315 Wybór wartości osiowej ...................................................u...................................................u............... 316 Aplet demonstracyjny QuickSort1 ...................................................u.................................................. 321 Obniżenie efektywności do rzędu O(N2)...................................................u......................................... 325 Wybór mediany trzech elementów ...................................................u.................................................. 326 Obsługa dzielenia niewielkich grup danych...................................................u.................................... 331 Usuwanie rekurencji ...................................................u...................................................u..................... 335 Efektywność działania algorytmu quicksort...................................................u.................................... 335 Sortowanie pozycyjne ...................................................u...................................................u............................... 338 Algorytm sortowania pozycyjnego...................................................u.................................................. 338 Projekt programu ...................................................u...................................................u.......................... 339 Efektywność sortowania pozycyjnego ...................................................u............................................ 339 Podsumowanie ...................................................u...................................................u.......................................... 340 Pytania...................................................u...................................................u.................. ..................................... 341 Eksperymenty...................................................u...................................................u............................................ 343 Projekty programów...................................................u...................................................u.................................. 343 8. Drzewa binarne .....................................................................................................345 Dlaczego warto używać drzew binarnych?...................................................u.................................................. 345 Wolne wstawianie elementów do tablicy uporządkowanych...................................................u.......... 346 Wolne wyszukiwanie w listach powiązanych ...................................................u................................. 346 SPIS TREŚCI 11 Rozwiązaniem są drzewa...................................................u...................................................u.............. 347 Czym jest drzewo?...................................................u...................................................u........................ 347 Terminologia związana z drzewami...................................................u............................................................. 348 Ścieżka...................................................u...................................................u.......................................... 348 Korzeń ...................................................u...................................................u.......................................... 348 Rodzic...................................................u...................................................u........................................... 349 Potomek ...................................................u...................................................u.................. ...................... 349 Liście ...................................................u...................................................u............................................ 349 Poddrzewo ...................................................u...................................................u.................................... 350 Odwiedzanie ...................................................u...................................................u................................. 350 Trawersowanie...................................................u...................................................u.............................. 350 Poziomy ...................................................u...................................................u.................. ...................... 350 Klucze...................................................u...................................................u........................................... 350 Drzewa binarne...................................................u...................................................u............................. 350 Analogia ...................................................u...................................................u.................................................... 351 Jak działają drzewa binarne?...................................................u........................................................................ 352 Aplet demonstracyjny Binary Tree...................................................u.................................................. 352 Reprezentacja drzew w języku Java ...................................................u................................................ 354 Wyszukiwanie węzła...................................................u...................................................u................................. 357 Wyszukiwanie węzłów w aplecie demonstracyjnym Binary Tree...................................................u.. 357 Kod metody wyszukującej węzeł ...................................................u.................................................... 358 Efektywność operacji na drzewach binarnych ...................................................u................................ 359 Wstawianie węzła...................................................u...................................................u...................................... 359 Wstawianie węzłów w aplecie demonstracyjnym Binary Tree...................................................u....... 359 Kod metody wstawiającej węzeł ...................................................u..................................................... 360 Trawersowanie drzewa...................................................u...................................................u.............................. 362 Trawersowanie drzew w porządku inorder ...................................................u..................................... 362 Kod metody trawersującej drzewo ...................................................u.................................................. 362 Trawersowanie drzew zawierających trzy węzły ...................................................u............................ 363 Trawersowanie drzewa w aplecie demonstracyjnym Binary Tree...................................................u.. 364 Trawersowanie drzew w porządkach preorder oraz postorder...................................................u........ 366 Znajdowanie wartości maksymalnej i minimalnej...................................................u....................................... 368 Usuwanie węzła ...................................................u...................................................u........................................ 369 Przypadek 1. Usuwany węzeł nie ma potomków ...................................................u............................ 370 Przypadek 2. Usuwany węzeł ma jednego potomka ...................................................u....................... 372 Przypadek 3. Usuwany węzeł na dwa potomki ...................................................u............................... 373 Efektywność operacji na drzewach binarnych ...................................................u............................................. 381 Przedstawianie drzew w formie tablicy ...................................................u....................................................... 383 Powtarzające się klucze...................................................u...................................................u............................. 384 Program tree.java ...................................................u...................................................u...................................... 385 Kod Huffmana...................................................u...................................................u........................................... 393 Kody znaków...................................................u...................................................u................................ 393 Dekodowanie przy wykorzystaniu drzewa Huffmana...................................................u..................... 395 Tworzenie drzewa Huffmana ...................................................u...................................................u....... 396 Kodowanie tekstu wiadomości...................................................u........................................................ 397 Tworzenie kodów Huffmana ...................................................u...................................................u........ 398 Podsumowanie ...................................................u...................................................u.......................................... 399 Pytania...................................................u...................................................u.................. ..................................... 401 Eksperymenty...................................................u...................................................u............................................ 402 Projekty programów...................................................u...................................................u.................................. 402 12 9. SPIS TREŚCI Drzewa czerwono-czarne......................................................................................405 Sposób omówienia struktury...................................................u........................................................................ 406 Zasada działania ...................................................u...................................................u........................... 406 Wstawianie zstępujące...................................................u...................................................u.................. 406 Drzewa zrównoważone i drzewa niezrównoważone ...................................................u................................... 406 Degeneracja do O(N)...................................................u...................................................u.................... 407 Równoważenie drzewa ...................................................u...................................................u................. 408 Cechy drzewa czerwono-czarnego ...................................................u.................................................. 408 Korygowanie struktury ...................................................u...................................................u................. 410 Aplet demonstracyjny RBTree...................................................u..................................................................... 410 Kliknięcie obrazka węzła...................................................u...................................................u.............. 411 Przycisk Start...................................................u...................................................u................................ 411 Przycisk Ins...................................................u...................................................u................................... 411 Przycisk Del...................................................u...................................................u.................................. 411 ..................... 411 Przycisk Flip ...................................................u...................................................u............ ................... 412 Przycisk RoL ...................................................u...................................................u............. ................... 412 Przycisk RoR ...................................................u...................................................u............. Przycisk R/B ...................................................u...................................................u............. .................... 412 Komunikaty tekstowe ...................................................u...................................................u................... 412 Gdzie jest przycisk Find? ...................................................u...................................................u............. 412 Ćwiczenia z apletem demonstracyjnym...................................................u....................................................... 413 Ćwiczenie 2. — obroty...................................................u...................................................u................. 414 Ćwiczenie 3. — odwracanie kolorów...................................................u.............................................. 414 Ćwiczenie 4. — drzewo niezrównoważone ...................................................u.................................... 415 Dalsze ćwiczenia ...................................................u...................................................u.......................... 416 Reguły RB i drzewa zrównoważone ...................................................u............................................... 416 Potomek pusty ...................................................u...................................................u............ .................. 416 Obroty ...................................................u...................................................u....................................................... 417 Proste operacje obrotu ...................................................u...................................................u.................. 417 Tajemniczy węzeł krzyżowy ...................................................u...................................................u........ 418 Obracanie gałęzi drzewa...................................................u...................................................u............... 418 Ludzie przeciw komputerom ...................................................u...................................................u........ 420 Wstawianie nowego węzła ...................................................u...................................................u........................ 421 Przebieg procedury wstawiania ...................................................u....................................................... 421 Odwrócenia kolorów w trakcie przeszukiwania...................................................u.............................. 422 Obroty po wstawieniu węzła ...................................................u........................................................... 423 Obroty w trakcie przeszukiwania ...................................................u.................................................... 429 Usuwanie...................................................u...................................................u................................................... 432 Wydajność drzew czerwono-czarnych...................................................u......................................................... 432 Implementacja drzewa czerwono-czarnego ...................................................u................................................. 433 Inne drzewa zrównoważone...................................................u...................................................u...................... 433 Podsumowanie ...................................................u...................................................u.......................................... 434 Pytania...................................................u...................................................u.................. ..................................... 434 Ćwiczenia...................................................u...................................................u.................................................. 436 10. Drzewa 2-3-4 i pamięć zewnętrzna.......................................................................437 Wprowadzenie...................................................u...................................................u........................................... 437 Skąd nazwa? ...................................................u...................................................u................................. 438 Organizacja drzewa 2-3-4...................................................u...................................................u............. 439 SPIS TREŚCI 13 Przeszukiwanie drzewa 2-3-4...................................................u.......................................................... 440 Wstawianie danych...................................................u...................................................u....................... 440 Podziały węzłów...................................................u...................................................u........................... 441 Podział korzenia ...................................................u...................................................u........................... 442 Zstępujące dzielenie węzłów ...................................................u........................................................... 442 Aplet demonstracyjny Tree234 ...................................................u.................................................................... 443 ...................... 443 Przycisk Fill...................................................u...................................................u............ Przycisk Find ...................................................u...................................................u............ .................... 444 Przycisk Ins...................................................u...................................................u................................... 445 Przycisk Zoom...................................................u...................................................u.............................. 445 Przeglądanie węzłów ...................................................u...................................................u.................... 446 Ćwiczenia ...................................................u...................................................u..................................... 447 Kod drzewa 2-3-4 w języku Java ...................................................u................................................................. 448 Klasa DataItem ...................................................u...................................................u............................. 449 Klasa Node ...................................................u...................................................u................................... 449 Klasa Tree234...................................................u...................................................u............................... 449 Klasa Tree234App...................................................u...................................................u........................ 450 Pełny kod programu tree234.java...................................................u.................................................... 451 Drzewa 2-3-4 a drzewa czerwono-czarne ...................................................u.................................................... 458 Transformacja drzewa 2-3-4 do drzewa czerwono-czarnego...................................................u.......... 458 Równoważność operacji ...................................................u...................................................u............... 460 Wydajność drzew 2-3-4 ...................................................u...................................................u............................ 461 Szybkość...................................................u...................................................u....................................... 461 Wymagania pamięciowe...................................................u...................................................u............... 463 Drzewa 2-3 ...................................................u...................................................u................................................ 463 Podziały węzłów...................................................u...................................................u........................... 464 Implementacja ...................................................u...................................................u.............................. 466 Pamięć zewnętrzna...................................................u...................................................u.................................... 466 Dostęp do danych zewnętrznych ...................................................u..................................................... 467 Sekwencyjne porządkowanie danych...................................................u.............................................. 470 B-drzewa...................................................u...................................................u....................................... 471 Indeksowanie ...................................................u...................................................u................................ 476 Złożone kryteria wyszukiwania...................................................u....................................................... 479 Sortowanie plików zewnętrznych...................................................u.................................................... 479 Podsumowanie ...................................................u...................................................u.......................................... 481 Pytania...................................................u...................................................u.................. ..................................... 483 Ćwiczenia...................................................u...................................................u.................................................. 484 Propozycje programów ...................................................u...................................................u............................. 485 11. Tablice rozproszone ..............................................................................................487 Algorytmy rozpraszania — wprowadzenie...................................................u.................................................. 488 Numery pracowników jako klucze danych ...................................................u..................................... 488 Słownik...................................................u...................................................u.................. ....................... 489 Rozpraszanie...................................................u...................................................u................................. 492 Kolizje ...................................................u...................................................u.......................................... 494 Adresowanie otwarte...................................................u...................................................u................................. 495 Aplet demonstracyjny Hash...................................................u...................................................u.......... 496 Kod tablicy rozproszonej z sondowaniem liniowym ...................................................u...................... 500 Sondowanie kwadratowe...................................................u...................................................u.............. 507 Podwójne rozpraszanie ...................................................u...................................................u................. 510 14 SPIS TREŚCI Łączenie ni
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Java. Algorytmy i struktury danych
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: