Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00631 010273 11042499 na godz. na dobę w sumie
Struktury danych i techniki obiektowe na przykładzie Javy 5.0 - książka
Struktury danych i techniki obiektowe na przykładzie Javy 5.0 - książka
Autor: , Liczba stron: 936
Wydawca: Helion Język publikacji: polski
ISBN: 83-246-0089-2 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> java - programowanie
Porównaj ceny (książka, ebook, audiobook).

Przy tworzeniu systemów informatycznych najważniejsze zadania wykonuje się, zanim powstanie pierwszy fragment kodu źródłowego. Wymogi stawiane współczesnym aplikacjom powodują, że inżynieria oprogramowania staje się kwestią kluczową. Opracowanie odpowiedniego projektu oraz właściwy dobór technologii i metodologii zapewniają szybką i efektywną pracę nad systemem. Niezwykle ważne jest poznanie dostępnych w języku Java struktur danych i umiejętność ich wykorzystania. Prawidłowo dobrana struktura danych znacznie przyspiesza nie tylko implementację aplikacji, ale również działanie gotowego systemu.

Książka 'Struktury danych i techniki obiektowe na przykładzie Javy 5.0' przedstawia podstawowe struktury danych i sposoby ich wykorzystania podczas programowania obiektowego. Wszystkie wiadomości zostały zaprezentowane z uwzględnieniem reguł nowoczesnej inżynierii oprogramowania. Czytając kolejne rozdziały książki, poznasz najlepsze zastosowania różnych struktur danych oraz wady i zalety ich implementacji. Przede wszystkim jednak zrozumiesz potrzebę stosowania tak wielu struktur danych.

Po przeczytaniu tej książki zrozumiesz zasadę:
'Pomyśl, a dopiero potem pisz kod'.

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 Struktury danych i techniki obiektowe na przyk³adzie Javy 5.0 Autorzy: Elliot Koffman, Paul Wolfgang T³umaczenie: Rafa³ Joñca, Tomasz ¯mijewski ISBN: 83-246-0089-2 Tytu³ orygina³u: Objects, Abstraction, Data Structures and Design: Using Java version 5.0 Format: B5, stron: 936 Przy tworzeniu systemów informatycznych najwa¿niejsze zadania wykonuje siê, zanim powstanie pierwszy fragment kodu Ÿród³owego. Wymogi stawiane wspó³czesnym aplikacjom powoduj¹, ¿e in¿ynieria oprogramowania staje siê kwesti¹ kluczow¹. Opracowanie odpowiedniego projektu oraz w³aœciwy dobór technologii i metodologii zapewniaj¹ szybk¹ i efektywn¹ pracê nad systemem. Niezwykle wa¿ne jest poznanie dostêpnych w jêzyku Java struktur danych i umiejêtnoœæ ich wykorzystania. Prawid³owo dobrana struktura danych znacznie przyspiesza nie tylko implementacjê aplikacji, ale równie¿ dzia³anie gotowego systemu. Ksi¹¿ka „Struktury danych i techniki obiektowe na przyk³adzie Javy 5.0” przedstawia podstawowe struktury danych i sposoby ich wykorzystania podczas programowania obiektowego. Wszystkie wiadomoœci zosta³y zaprezentowane z uwzglêdnieniem regu³ nowoczesnej in¿ynierii oprogramowania. Czytaj¹c kolejne rozdzia³y ksi¹¿ki, poznasz najlepsze zastosowania ró¿nych struktur danych oraz wady i zalety ich implementacji. Przede wszystkim jednak zrozumiesz potrzebê stosowania tak wielu struktur danych. (cid:129) Cykl ¿ycia oprogramowania (cid:129) Zastosowanie jêzyka UML w projektowaniu systemów (cid:129) Obs³uga b³êdów i wyj¹tków (cid:129) Testowanie oprogramowania (cid:129) Dziedziczenie i hierarchia klas (cid:129) Listy jedno- i dwukierunkowe (cid:129) Interfejs Collection (cid:129) Stosy i kolejki (cid:129) Algorytmy rekurencyjne (cid:129) Sortowanie danych (cid:129) Drzewa wyszukiwania (cid:129) Grafy Po przeczytaniu tej ksi¹¿ki zrozumiesz zasadê: „Pomyœl, a dopiero potem pisz kod” Przedmowa ..................................................................................... 17 Rozdział 1. Wprowadzenie do projektowania oprogramowania ............................ 29 1.1. Cykl życia oprogramowania ..............................................................................30 Modele cyklu życia oprogramowania ...................................................................31 Działania związane z cyklem życia oprogramowania ..........................................33 Specyfikacja wymagań .........................................................................................34 Analiza ..................................................................................................................35 Projektowanie .......................................................................................................36 Ćwiczenia do podrozdziału 1.1 .............................................................................38 1.2. Abstrakcja pomaga zarządzać złożonością ......................................................39 Abstrakcja proceduralna .......................................................................................39 Abstrakcja danych .................................................................................................40 Ukrywanie informacji ...........................................................................................40 Ćwiczenia do podrozdziału 1.2 .............................................................................41 1.3. Abstrakcyjne typy danych, interfejsy, warunki wstępne i końcowe ..............42 Interfejsy ...............................................................................................................43 Klauzula implements ............................................................................................45 Deklaracja zmiennej będącej typem interfejsu .....................................................45 Interfejs dla klasy książki telefonicznej ................................................................46 Komentarze Javadoc .............................................................................................46 Kontrakty i interfejsy ............................................................................................47 Warunki początkowe i końcowe ...........................................................................47 Ćwiczenia do podrozdziału 1.3 .............................................................................48 1.4. Analiza wymagań, przypadki użycia i diagramy sekwencji ...........................49 ANALIZA PRZYPADKU — projektowanie programu książki telefonicznej ....50 Ćwiczenia do podrozdziału 1.4 .............................................................................55 1.5. Projektowanie książki telefonicznej bazującej na tablicy ...............................56 1.6. ANALIZA PRZYPADKU — projektowanie programu książki telefonicznej (kontynuacja) ......................................................................................................56 Ćwiczenia do podrozdziału 1.5 .............................................................................62 Implementacja i testowanie książki telefonicznej bazującej na tablicy .........62 ANALIZA PRZYPADKU — projektowanie programu książki telefonicznej (kontynuacja) ......................................................................................................62 Ćwiczenia do podrozdziału 1.6 .............................................................................69 D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc (06-03-06) — 3 — 4 Struktury danych i techniki obiektowe na przykładzie Javy 5.0 1.7. Dwie klasy implementujące interfejs PDUserInterface ...................................69 ANALIZA PRZYPADKU — projektowanie programu książki telefonicznej (kontynuacja) ......................................................................................................69 Ćwiczenia do podrozdziału 1.7 .............................................................................80 Podsumowanie rozdziału ...............................................................................................80 Rozdział 2. Poprawność i wydajność programów ............................................... 87 2.1. Defekty i błędy w programach ...........................................................................88 Błędy składniowe ..................................................................................................89 Błędy czasu wykonania i wyjątki .........................................................................90 Błędy logiczne ......................................................................................................94 Ćwiczenia do podrozdziału 2.1 .............................................................................95 2.2. Hierarchia klas wyjątków ..................................................................................95 Klasa Throwable ...................................................................................................96 Wyjątki weryfikowane i nieweryfikowane ...........................................................96 Ćwiczenia do podrozdziału 2.2 .............................................................................97 2.3. Wyłapywanie i obsługa wyjątków .....................................................................99 Wyjątki niewyłapane ............................................................................................99 Sekwencja try-catch-finally ..................................................................................99 Ćwiczenia do podrozdziału 2.3 ...........................................................................106 2.4. Zgłaszanie wyjątków .........................................................................................106 Klauzula throws ..................................................................................................106 Instrukcja throw ..................................................................................................108 Wyłapywanie wyjątków w programie książki telefonicznej ..............................111 Ćwiczenia do podrozdziału 2.4 ...........................................................................113 2.5. Testowanie programów ....................................................................................114 Strukturalne ścieżki przejścia .............................................................................115 Poziomy i rodzaje testów ....................................................................................115 Przygotowanie do testów ....................................................................................117 Wskazówki dotyczące testowania programów ...................................................118 Przygotowanie danych testowych .......................................................................119 Testowanie warunków granicznych ....................................................................119 Kto wykonuje testy? ...........................................................................................122 Namiastki ............................................................................................................123 Programy testujące ..............................................................................................124 Testowanie klasy .................................................................................................124 Wykorzystanie systemu testującego ...................................................................125 Testy regresyjne ..................................................................................................127 Testy integracyjne ...............................................................................................128 Ćwiczenia do podrozdziału 2.5 ...........................................................................128 2.6. Usuwanie błędów z programów .......................................................................129 Wykorzystanie programu uruchomieniowego ....................................................130 Ćwiczenia do podrozdziału 2.6 ...........................................................................134 2.7. Rozważania na temat programów: asercje i niezmienniki pętli ...................134 Asercje ................................................................................................................135 Niezmienniki pętli ...............................................................................................135 Rozszerzenie tematu — instrukcja assert języka Java ........................................137 Ćwiczenia do podrozdziału 2.7 ...........................................................................138 2.8. Wydajność algorytmów ....................................................................................138 Notacja dużego O ................................................................................................141 Porównanie wydajności ......................................................................................145 — 4 — (06-03-06) D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc Spis treści 5 Algorytmy o złożoności wykładniczej ................................................................146 Ćwiczenia do podrozdziału 2.8 ...........................................................................147 Podsumowanie rozdziału .............................................................................................148 Rozdział 3. Dziedziczenie i hierarchie klas ....................................................... 157 3.1. Wprowadzenie do dziedziczenia i hierarchii klas ..........................................158 Związki „jest” i „zawiera” ..................................................................................160 Klasa bazowa i podklasa .....................................................................................161 Wykorzystanie słowa kluczowego this ...............................................................162 Inicjalizacja pól danych podklasy .......................................................................163 Konstruktor bezparametrowy ..............................................................................164 Pola chronione klasy bazowej .............................................................................164 Ćwiczenia do podrozdziału 3.1 ...........................................................................165 3.2. Przeciążanie metod, przesłanianie metod i polimorfizm ...............................166 Przesłanianie metod ............................................................................................166 Przeciążanie metod .............................................................................................168 Polimorfizm ........................................................................................................169 Ćwiczenia do podrozdziału 3.2 ...........................................................................171 3.3. Klasy abstrakcyjne, przypisanie i rzutowanie w hierarchii klas ..................172 Referencje do obiektów rzeczywistych ..............................................................174 Klasy abstrakcyjne i interfejsy ............................................................................174 Klasa abstrakcyjna Number i klasy opakowujące typy podstawowe .................174 Podsumowanie cech klas konkretnych, klas abstrakcyjnych i interfejsów .........175 Ćwiczenia do podrozdziału 3.3 ...........................................................................175 3.4. Klasa Object, rzutowanie i klonowanie ..........................................................177 Metoda toString() ................................................................................................177 Dopuszczalne operacje określa typ zmiennej referencyjnej ...............................177 Rzutowanie w hierarchii klas ..............................................................................178 Metoda Object.equals() .......................................................................................182 Klonowanie .........................................................................................................183 Klonowanie struktury danych .............................................................................187 Ćwiczenia do podrozdziału 3.4 ...........................................................................188 3.5. Dziedziczenie wielobazowe, stosowanie wielu interfejsów i delegacja .........189 Wykorzystanie wielu interfejsów do emulacji dziedziczenia wielobazowego ...189 Implementacja wielokrotnego użycia dzięki delegacji .......................................191 Ćwiczenia do podrozdziału 3.5 ...........................................................................192 3.6. Pakiety i widoczność .........................................................................................193 Pakiety .................................................................................................................193 Środowisko bez deklaracji nazwy pakietu ..........................................................193 Widoczność w ramach pakietu ...........................................................................194 Widoczność pozwala wspomóc hermetyzację ....................................................194 Ćwiczenia do podrozdziału 3.6 ...........................................................................195 3.7. Hierarchia klas kształtu ...................................................................................196 ANALIZA PRZYPADKU — rysowanie figur geometrycznych .......................196 Ćwiczenia do podrozdziału 3.7 ...........................................................................212 3.8. Fabryki obiektów ..............................................................................................212 ANALIZA PRZYPADKU — obliczanie pól i obwodów figur geometrycznych ................................................................................................213 Ćwiczenia do podrozdziału 3.8 ...........................................................................215 D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc (06-03-06) — 5 — 6 Struktury danych i techniki obiektowe na przykładzie Javy 5.0 Podsumowanie rozdziału .............................................................................................215 4.1. 4.3. Rozdział 4. Listy i interfejs Collection ............................................................. 223 Interfejs List i klasa ArrayList ........................................................................224 Klasa ArrayList ...................................................................................................225 Kolekcje sparametryzowane ...............................................................................227 Specyfikacja klasy ArrayList ..............................................................................229 Ćwiczenia do podrozdziału 4.1 ...........................................................................230 4.2. Zastosowania ArrayList ...................................................................................230 Powrót do programu książki telefonicznej .........................................................231 Ćwiczenia do podrozdziału 4.2 ...........................................................................232 Implementacja klasy ArrayList .......................................................................233 Konstruktor klasy KWArrayList E ..................................................................234 Metoda add(E anEntry) .......................................................................................234 Metoda add(int index, E anEntry) .......................................................................235 Metody set() i get() .............................................................................................236 Metoda remove() .................................................................................................237 Metoda reallocate() .............................................................................................237 Implementacja KWArrayList jako klasy bez parametryzacji .............................238 Wydajność KWArrayList ...................................................................................238 Klasa Vector ........................................................................................................238 Ćwiczenia do podrozdziału 4.3 ...........................................................................239 4.4. Listy jednokierunkowe i dwukierunkowe ......................................................239 Węzeł listy ..........................................................................................................241 Łączenie węzłów .................................................................................................243 Klasa listy jednokierunkowej ..............................................................................243 Wstawienie węzła ...............................................................................................244 Usunięcie węzła ..................................................................................................244 Przejście przez listę .............................................................................................245 Listy dwukierunkowe ..........................................................................................246 Klasa listy dwukierunkowej ................................................................................248 Listy cykliczne ....................................................................................................249 Ćwiczenia do podrozdziału 4.4 ...........................................................................250 4.5. Klasa LinkedList oraz interfejsy Iterator, ListIterator i Iterable ................252 Klasa LinkedList .................................................................................................252 Iterator .................................................................................................................252 Interfejs Iterator ..................................................................................................253 Interfejs ListIterator ............................................................................................255 Porównanie Iterator i ListIterator ........................................................................258 Interfejs ListIterator i indeks ...............................................................................258 Rozszerzona pętla for ..........................................................................................258 Interfejs Iterable ..................................................................................................259 Ćwiczenia do podrozdziału 4.5 ...........................................................................259 Implementacja klasy listy dwukierunkowej ...................................................260 Implementacja metod klasy KWLinkedList .......................................................261 Klasa implementująca interfejs ListIterator ........................................................262 Klasy wewnętrzne — statyczne i niestatyczne ...................................................268 Ćwiczenia do podrozdziału 4.6 ...........................................................................269 4.7. Zastosowania klasy LinkedList .......................................................................269 ANALIZA PRZYPADKU — przechowywanie uporządkowanej listy .............270 Ćwiczenia do podrozdziału 4.7 ...........................................................................276 4.6. — 6 — (06-03-06) D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc Spis treści 7 4.8. Hierarchia szkieletu Java Collections .............................................................277 Cechy wspólne kolekcji ......................................................................................278 Klasy AbstractCollection, AbstractList i AbstractSequentialList ......................278 Ćwiczenia do podrozdziału 4.8 ...........................................................................279 Podsumowanie rozdziału .............................................................................................280 Rozdział 5. Stosy ........................................................................................... 287 5.1. Stos — abstrakcyjny typ danych .....................................................................288 Specyfikacja stosu jako abstrakcyjnego typu danych .........................................289 Ćwiczenia do podrozdziału 5.1 ...........................................................................290 5.2. Zastosowania stosów .........................................................................................291 ANALIZA PRZYPADKU — znajdowanie palindromów .................................291 ANALIZA PRZYPADKU — sprawdzanie wyrażeń pod kątem 5.3. zrównoważenia nawiasów ................................................................................294 Ćwiczenia do podrozdziału 5.2 ...........................................................................299 Implementacja stosu .........................................................................................299 Implementacja stosu jako rozszerzenia klasy Vector .........................................300 Implementacja stosu za pomocą komponentu List .............................................301 Implementacja stosu wykorzystująca tablicę ......................................................303 Implementacja stosu jako listy jednokierunkowej ..............................................305 Porównanie implementacji stosów .....................................................................307 Ćwiczenia do podrozdziału 5.3 ...........................................................................307 5.4. Kolejne zastosowania stosów ...........................................................................308 ANALIZA PRZYPADKU — obliczanie wyrażeń w odwrotnej notacji polskiej .............................................................................................................309 ANALIZA PRZYPADKU — konwersja z zapisu infiksowego na odwrotną notację polską ...................................................................................................314 ANALIZA PRZYPADKU — część 2., konwersja wyrażeń z nawiasami .........322 Wypróbowanie obu analiz przypadków w jednym programie ...........................324 Ćwiczenia do podrozdziału 5.4 ...........................................................................325 Podsumowanie rozdziału .............................................................................................325 Rozdział 6. Kolejki ......................................................................................... 333 6.1. Kolejka — abstrakcyjny typ danych ..............................................................334 Kolejka wydruku .................................................................................................334 Nieprzydatność „stosu wydruku” .......................................................................334 Kolejka klientów .................................................................................................335 Wykorzystanie kolejki do przejścia przez wielogałęziową strukturę danych ....335 Specyfikacja interfejsu Queue ............................................................................336 Klasa LinkedList implementuje interfejs Queue ................................................337 Ćwiczenia do podrozdziału 6.1 ...........................................................................338 6.2. Zarządzanie kolejką klientów ..........................................................................338 ANALIZA PRZYPADKU — zarządzanie kolejką ............................................339 Ćwiczenia do podrozdziału 6.2 ...........................................................................343 Implementacja interfejsu Queue .....................................................................344 Wykorzystanie listy dwukierunkowej do implementacji interfejsu Queue ........344 Wykorzystanie listy jednokierunkowej do implementacji interfejsu Queue ......345 Wykorzystanie tablicy cyklicznej do implementacji interfejsu Queue ...............348 Porównanie trzech implementacji .......................................................................355 Ćwiczenia do podrozdziału 6.3 ...........................................................................355 6.4. Symulacja średnich czasów obsługi za pomocą kolejki .................................356 ANALIZA PRZYPADKU — symulacja obsługi pasażerów linii lotniczych ....357 6.3. D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc (06-03-06) — 7 — 8 Struktury danych i techniki obiektowe na przykładzie Javy 5.0 Ćwiczenia do podrozdziału 6.4 ...........................................................................370 Podsumowanie rozdziału .............................................................................................371 Rozdział 7. Rekurencja ................................................................................... 379 7.1. Myśl w sposób rekurencyjny ...........................................................................380 Kroki związane z zaprojektowaniem algorytmu rekurencyjnego .......................382 Udowodnienie, iż metoda rekurencyjna jest poprawna ......................................385 Śledzenie wykonania metody rekurencyjnej ......................................................385 Stos wywołań i ramki aktywacji .........................................................................386 Ćwiczenia do podrozdziału 7.1 ...........................................................................388 7.2. Definicje rekurencyjne wybranych wzorów matematycznych .....................388 Rekurencja a iteracja ...........................................................................................392 Rekurencja prawostronna ....................................................................................392 Wydajność rekurencji .........................................................................................393 Ćwiczenia do podrozdziału 7.2 ...........................................................................396 7.3. Rekurencyjne przeszukiwanie tablicy .............................................................396 Zaprojektowanie rekurencyjnego liniowego algorytmu wyszukiwania .............397 Implementacja wyszukiwania liniowego ............................................................397 Zaprojektowanie algorytmu wyszukiwania binarnego .......................................398 Wydajność wyszukiwania binarnego ..................................................................400 Interfejs Comparable ...........................................................................................401 Implementacja wyszukiwania binarnego ............................................................401 Testowanie wyszukiwania binarnego .................................................................402 Metoda Arrays.binarySearch() ............................................................................403 Ćwiczenia do podrozdziału 7.3 ...........................................................................404 7.4. Rekurencyjne struktury danych ......................................................................404 Rekurencyjna definicja listy ...............................................................................404 Klasa LinkedListRec ...........................................................................................405 Usunięcie węzła z listy ........................................................................................408 Ćwiczenia do podrozdziału 7.4 ...........................................................................409 7.5. Rozwiązywanie problemów z wykorzystaniem rekurencji ...........................410 ANALIZA PRZYPADKU — wieże Hanoi ........................................................410 ANALIZA PRZYPADKU — zliczanie pikseli należących do plamy ...............414 Ćwiczenia do podrozdziału 7.5 ...........................................................................419 7.6. Nawroty ..............................................................................................................419 ANALIZA PRZYPADKU — znajdowanie ścieżki przez labirynt ....................420 Ćwiczenia do podrozdziału 7.6 ...........................................................................424 Podsumowanie rozdziału .............................................................................................425 Rozdział 8. Drzewa ......................................................................................... 431 8.1. Terminologia dotycząca drzew i ich zastosowania ........................................433 Terminologia .......................................................................................................433 Drzewa binarne ...................................................................................................434 Niektóre rodzaje drzew binarnych ......................................................................434 Pełność i zupełność .............................................................................................438 Drzewa bardziej ogólne ......................................................................................438 Ćwiczenia do podrozdziału 8.1 ...........................................................................440 8.2. Sposoby przejścia przez drzewo ......................................................................440 Wizualizacja przejścia przez drzewo ..................................................................441 Przejścia przez binarne drzewa przeszukiwania i drzewa wyrażeń ....................442 Ćwiczenia do podrozdziału 8.2 ...........................................................................443 — 8 — (06-03-06) D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc Spis treści 9 8.3. Implementacja klasy BinaryTree ....................................................................443 Klasa Node E ...................................................................................................443 Klasa BinaryTree E .........................................................................................445 Ćwiczenia do podrozdziału 8.3 ...........................................................................451 8.4. Binarne drzewa wyszukiwania ........................................................................452 Omówienie binarnych drzew wyszukiwania ......................................................452 Wydajność ...........................................................................................................454 Klasa TreeSet i interfejs SearchTree ...................................................................454 Klasa BinarySearchTree .....................................................................................454 Wstawianie elementu w drzewie BST ................................................................457 Usuwanie z drzewa BST .....................................................................................460 Testowanie binarnego drzewa przeszukiwania ...................................................466 ANALIZA PRZYPADKU — tworzenie skorowidza do wypracowania ...........466 Ćwiczenia do podrozdziału 8.4 ...........................................................................468 8.5. Sterty i kolejki priorytetowe ............................................................................469 Wstawianie elementu na stercie ..........................................................................470 Usunięcie elementu ze sterty ..............................................................................471 Implementacja sterty ...........................................................................................472 Kolejki priorytetowe ...........................................................................................476 Klasa PriorityQueue ............................................................................................477 Wykorzystanie sterty jako podstawy dla kolejki priorytetowej ..........................477 Pozostałe metody ................................................................................................480 Wykorzystanie interfejsu Comparator ................................................................480 Metoda compare() ...............................................................................................481 Ćwiczenia do podrozdziału 8.5 ...........................................................................483 8.6. Drzewa Huffmana .............................................................................................483 ANALIZA PRZYPADKU — wykonanie własnego drzewa Huffmana ............484 Ćwiczenia do podrozdziału 8.6 ...........................................................................491 Podsumowanie rozdziału .............................................................................................492 Rozdział 9. Zbiory i odwzorowania .................................................................. 499 9.1. Zbiory i interfejs Set .........................................................................................500 Abstrakcja zbioru — interfejs Set .......................................................................500 Interfejs Set i jego metody ..................................................................................502 Porównanie list i zbiorów ...................................................................................504 Ćwiczenia do podrozdziału 9.1 ...........................................................................504 9.2. Odwzorowania i interfejs Map ........................................................................505 Hierarchia Map ...................................................................................................507 Interfejs Map .......................................................................................................507 Ćwiczenia do podrozdziału 9.2 ...........................................................................509 9.3. Tablice mieszające ............................................................................................510 Funkcja mieszająca i wyliczanie indeksu ...........................................................510 Sposoby określania funkcji mieszających ..........................................................511 Adresacja otwarta ................................................................................................512 Zawinięcie tablicy i przerwanie poszukiwania ...................................................513 Przejście przez tablicę mieszającą ......................................................................515 Usunięcie elementu w adresacji otwartej ............................................................515 Zmniejszanie liczby kolizji przez zwiększenie pojemności tablicy ...................515 Redukcja kolizji za pomocą próbkowania kwadratowego ..................................516 Problemy próbkowania kwadratowego ...............................................................517 Mieszanie łańcuchowe ........................................................................................518 Wydajność tablic mieszających ..........................................................................519 Ćwiczenia do podrozdziału 9.3 ...........................................................................521 D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc (06-03-06) — 9 — 10 Struktury danych i techniki obiektowe na przykładzie Javy 5.0 9.4. Implementacja tablicy mieszającej .................................................................522 Interfejs KWHashMap ........................................................................................523 Klasa Entry ..........................................................................................................523 Klasa HashtableOpen ..........................................................................................524 Klasa HashtableChain .........................................................................................529 Testowanie implementacji tablic mieszających ..................................................533 Ćwiczenia do podrozdziału 9.4 ...........................................................................534 9.5. Zagadnienia związane z implementacją interfejsów Set i Map ....................534 Metody hashCode() i equals() .............................................................................534 Implementacja klasy HashSetOpen ....................................................................535 Wykonanie klasy HashSetOpen jako klasy adapterowej ....................................536 Implementacja interfejsów Map i Set Javy .........................................................537 Interfejs wewnętrzny Map.Entry ........................................................................537 Utworzenie widoku odwzorowania jako zbioru .................................................537 Metoda entrySet() i klasy EntrySet oraz SetIterator ...........................................538 Klasy TreeMap i TreeSet ....................................................................................539 Ćwiczenia do podrozdziału 9.5 ...........................................................................540 9.6. Dodatkowe zastosowania odwzorowań ...........................................................540 ANALIZA PRZYPADKU — implementacja książki telefonicznej przy użyciu odwzorowania .......................................................................................540 Analiza przypadku — dokończenie problemu kodowania Huffmana ................543 Ćwiczenia do podrozdziału 9.6 ...........................................................................547 Podsumowanie rozdziału .............................................................................................547 Rozdział 10. Sortowanie ................................................................................... 553 10.1. Użycie metod sortowania dostępnych w Javie ................................................554 Ćwiczenia do podrozdziału 10.1 .........................................................................558 10.2. Sortowanie przez wybór ...................................................................................559 Analiza sortowania przez wybór .........................................................................560 Kod sortowania przez wybór ..............................................................................560 Ćwiczenia do podrozdziału 10.2 .........................................................................561 10.3. Sortowanie bąbelkowe ......................................................................................562 Analiza sortowania bąbelkowego .......................................................................564 Kod sortowania bąbelkowego .............................................................................564 Ćwiczenia do podrozdziału 10.3 .........................................................................565 10.4. Sortowanie przez wstawianie ...........................................................................566 Analiza sortowania przez wstawianie .................................................................567 Kod sortowania przez wstawianie ......................................................................568 Ćwiczenia do podrozdziału 10.4 .........................................................................569 10.5. Porównanie metod sortowania działających w czasie kwadratowym ..........570 Porównania a podmiany ......................................................................................571 Ćwiczenia do podrozdziału 10.5 .........................................................................571 10.6. Sortowanie Shella — ulepszone sortowanie przez wstawianie .....................571 Analiza sortowania Shella ...................................................................................573 Kod sortownia Shella ..........................................................................................574 Ćwiczenia do podrozdziału 10.6 .........................................................................575 10.7. Sortowanie przez złączanie ..............................................................................576 Analiza złączania ................................................................................................576 Kod złączania ......................................................................................................577 Algorytm sortowania przez złączanie .................................................................578 Przykład zastosowania algorytmu sortowania przez złączanie ..........................579 Analiza sortowania przez złączanie ....................................................................579 — 10 — (06-03-06) D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc Spis treści 11 Kod sortowania przez złączanie ..........................................................................580 Ćwiczenia do podrozdziału 10.7 .........................................................................581 10.8. Sortowanie na stercie ........................................................................................581 Pierwsza wersja sortowania na stercie ................................................................582 Sortowanie na stercie — poprawka ....................................................................582 Algorytm tworzenia sterty ..................................................................................584 Analiza udoskonalonego algorytmu sortowania na stercie .................................584 Kod sortowania na stercie ...................................................................................585 Ćwiczenia do podrozdziału 10.8 .........................................................................586 10.9. Quicksort ...........................................................................................................587 Algorytm quicksort .............................................................................................588 Analiza algorytmu quicksort ...............................................................................588 Kod algorytmu quicksort ....................................................................................589 Algorytm podziału tablicy ..................................................................................590 Kod metody partition ..........................................................................................591 Udoskonalony algorytm podziału .......................................................................593 Kod udoskonalonej metody partition ..................................................................595 Ćwiczenia do podrozdziału 10.9 .........................................................................596 10.10. Testowanie algorytmów sortujących ...............................................................596 Ćwiczenia do podrozdziału 10.10 .......................................................................598 10.11. Problem flagi holenderskiej (temat opcjonalny) ............................................598 ANALIZA PRZYPADKU — problem flagi holenderskiej ................................599 Ćwiczenia do podrozdziału 10.11 .......................................................................602 Podsumowanie rozdziału .............................................................................................602 Rozdział 11. Samorównoważące się drzewa wyszukiwania ................................. 607 11.1. Zrównoważenie drzewa i rotacja .....................................................................608 Czemu równowaga jest tak ważna? ....................................................................608 Rotacja ................................................................................................................609 Algorytm rotacji ..................................................................................................610 Implementacja rotacji ..........................................................................................612 Ćwiczenia do podrozdziału 11.1 .........................................................................613 11.2. Drzewa AVL ......................................................................................................613 Równoważenie drzewa typu „lewa-lewa” ..........................................................614 Równoważenie drzewa typu „lewa-prawa” ........................................................615 Cztery rodzaje niezrównoważenia ......................................................................616 Implementacja drzew AVL .................................................................................619 Wstawianie wartości do drzewa AVL ................................................................621 Usuwanie z drzewa AVL ....................................................................................627 Wydajność drzew AVL .......................................................................................628 Ćwiczenia do podrozdziału 11.2 .........................................................................628 11.3. Drzewa czerwono-czarne ..................................................................................629 Wstawianie do drzewa czerwono-czarnego ........................................................629 Usuwanie elementów z czerwono-czarnych drzew ............................................642 Wydajność drzew czerwono-czarnych ...............................................................642 Klasy TreeMap i TreeSet ....................................................................................643 Ćwiczenia do podrozdziału 11.3 .........................................................................643 11.4. Drzewa 2-3 .........................................................................................................643 Przeszukiwanie drzewa 2-3 .................................................................................644 Wstawianie elementu do drzewa 2-3 ..................................................................645 Analiza drzew 2-3 i porównanie ich ze zrównoważonymi drzewami binarnymi .......................................................649 D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc (06-03-06) — 11 — 12 Struktury danych i techniki obiektowe na przykładzie Javy 5.0 Usuwanie danych z drzewa 2-3 ..........................................................................649 Ćwiczenia do podrozdziału 11.4 .........................................................................650 11.5. Drzewa 2-3-4 i B-drzewa ..................................................................................651 Drzewa 2-3-4 ......................................................................................................651 Implementacja klasy TwoThreeFourTree ...........................................................654 Drzewa 2-3-4 a drzewa czerwono-czarne ...........................................................659 B-drzewa .............................................................................................................660 Ćwiczenia do podrozdziału 11.5 .........................................................................662 Podsumowanie rozdziału .............................................................................................663 Rozdział 12. Grafy ............................................................................................ 673 12.1. Terminologia związana z grafami ......................................................................674 Wizualna reprezentacja grafów ...........................................................................674 Grafy skierowane i nieskierowane ......................................................................675 Drogi i cykle .......................................................................................................676 Związek między grafami a drzewami .................................................................678 Zastosowania grafów ..........................................................................................678 Ćwiczenia do podrozdziału 12.1 .........................................................................679 12.2. Graf jako abstrakcyjny typ danych, klasa Edge ............................................679 Ćwiczenia do podrozdziału 12.2 .........................................................................681 12.3. Implementacja grafów ......................................................................................682 Listy sąsiedztwa ..................................................................................................682 Macierz sąsiedztwa .............................................................................................682 Hierarchia klas ....................................................................................................684 Klasa AbstractGraph ...........................................................................................685 Klasa ListGraph ..................................................................................................688 Klasa MatrixGraph ..............................................................................................690 Porównanie obu implementacji ...........................................................................691 Ćwiczenia do podrozdziału 12.3 .........................................................................692 12.4. Metody przeglądania grafów ...........................................................................693 Przeszukiwanie wszerz .......................................................................................693 Przeszukiwanie w głąb ........................................................................................698 Ćwiczenia do podrozdziału 12.4 .........................................................................706 12.5. Zastosowania algorytmów przeglądania grafów ..............................................706 ANALIZA PRZYPADKU — najkrótsza droga przez labirynt ..........................706 ANALIZA PRZYPADKU — sortowanie topologiczne grafu ...........................710 Ćwiczenia do podrozdziału 12.5 .........................................................................713 12.6. Algorytmy wykorzystujące grafy ważone .......................................................713 Znajdowanie najkrótszej drogi z danego do wszystkich innych wierzchołków .....713 Minimalne drzewa rozpinające ...........................................................................718 Ćwiczenia do podrozdziału 12.6 .........................................................................722 Podsumowanie rozdziału .............................................................................................723 Dodatki Dodatek A Wprowadzenie do języka Java ........................................................ 735 A.1. Środowisko języka Java i klasy .......................................................................737 Wirtualna maszyna Javy .....................................................................................737 Kompilator Javy ..................................................................................................738 Klasy i obiekty ....................................................................................................738 API języka Java ...................................................................................................738 Instrukcja import .................................................................................................739 — 12 — (06-03-06) D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc Spis treści 13 A.3. Metoda main .......................................................................................................739 Wykonywanie programu języka Java .................................................................740 Ćwiczenia do podrozdziału A.1 ..........................................................................740 A.2. Elementarne typy danych i zmienne referencyjne .........................................741 Elementarne typy danych ....................................................................................741 Zmienne typów podstawowych ..........................................................................742 Stałe typów elementarnych .................................................................................743 Operatory ............................................................................................................743 Inkrementacja przyrostkowa i przedrostkowa ....................................................743 Zgodność typów i konwersja ..............................................................................745 Odwoływanie się do obiektów ............................................................................745 Tworzenie obiektów ............................................................................................746 Ćwiczenia do podrozdziału A.2 ..........................................................................747 Instrukcje sterujące języka Java .....................................................................747 Instrukcje sekwencji i instrukcje złożone ...........................................................747 Instrukcje wyboru i pętli .....................................................................................747 Zagnieżdżone instrukcje if ..................................................................................750 Instrukcja switch .................................................................................................751 Ćwiczenia do podrozdziału A.3 ..........................................................................752 A.4. Metody i klasa Math .........................................................................................752 Metody obiektu println i print .............................................................................752 Parametry przekazywane przez wartość .............................................................753 Klasa Math ..........................................................................................................754 Sekwencje sterujące ............................................................................................755 Ćwiczenia do podrozdziału A.4 ..........................................................................756 A.5. Klasy String, StringBuilder, StringBuffer oraz StringTokenizer ................756 Klasa String .........................................................................................................756 Łańcuchy są niezmienne .....................................................................................759 Odśmiecanie ........................................................................................................760 Porównywanie obiektów .....................................................................................760 Metoda String.format ..........................................................................................761 Klasa Formatter ...................................................................................................763 Klasy StringBuilder i StringBuffer .....................................................................763 Klasa StringTokenizer ........................................................................................765 Ćwiczenia do podrozdziału A.5 ..........................................................................766 A.6. Klasy opakowujące typy elementarne .............................................................767 Ćwiczenia do podrozdziału A.5 ..........................................................................769 A.7. Definiowanie własnych klas .............................................................................769 Prywatne pola danych, publiczne metody ..........................................................773 Konstruktory .......................................................................................................774 Konstruktor bezparametrowy ..............................................................................775 Metody modyfikatorów i akcesorowe ................................................................775 Użycie zapisu this. w metodach ..........................................................................775 Metoda toString ..................................................................................................776 Metoda equals .....................................................................................................776 Deklarowanie zmiennych lokalnych klasy Person .............................................777 Aplikacja korzystająca z klasy Person ................................................................778 Obiekty w roli parametrów .................................................................................779 Klasy jako składniki innych klas ........................................................................780 Dokumentowanie klas i metod w Javie ..............................................................781 Ćwiczenia do podrozdziału A.7 ..........................................................................781 D:SkładStruktury danych i techniki obiektowe na przykładzie Javy 5.0kalki!SPIS.doc (06-03-06) — 13 — 14 Struktury danych i techniki obiektowe na przykładzie Javy 5.0 A.8. Tablice ................................................................................................................783 Pole length ..........................................................................................................786 Metoda System.arraycopy ...................................................................................787 Tablicowe pola danych .......................................................................................788 Tablice jako wyniki i jako parametry .................................................................789 Tablice tablic .......................................................................................................790 Ćwiczenia do podrozdziału A.8 ..........................................................................793 A.9. Oprogramowanie wejścia i wyjścia przy użyciu klasy JOptionPane ...........794 Konwersja znakowego zapisu liczby na liczbę ...................................................795 Menu graficzne oparte na metodzie showOptionDialog ....................................796 Ćwiczenia do podrozdziału A.9 ..........................................................................796 A.10. Oprogramowanie wejścia i wyjścia przy użyciu strumieni ...........................797 Strumienie wejściowe .........................................................................................797 Wejście konsolowe .............................................................................................797 Strumienie wyjściowe .........................................................................................798 Przekazywanie parametrów metodzie main ........................................................798 Zamykanie strumieni ..........................................................................................798 Wyjątki ................................................................................................................799 Cała aplikacja przetwarzająca pliki ....................................................................799 Klasa Scanner ......................................................................................................801 Wczytywanie danych element po elemencie ......................................................803 Ćwiczenia do podrozdziału A.10 ........................................................................804 Podsumowanie rozdziału .............................................................................................804 Dodatek B Wprowadzenie do UML-a ............................................................... 811 B.1. Diagram klas ......................................................................................................812 Reprezentacja klas i interfejsów .........................................................................812 Generalizacja .......................................................................................................815 Klasy wewnętrzne, czyli zagnieżdżone .
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Struktury danych i techniki obiektowe na przykładzie Javy 5.0
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ą: