Java Algorytmy i struktury danych.pdf

(2455 KB) Pobierz
C:\Andrzej\PDF\ABC nagrywania p³yt CD\1 strona.cdr
IDZ DO
PRZYK£ADOW Y ROZDZIA£
Java. Algorytmy
SPIS TRECI
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
in Java, 2nd Edition
Format: B5, stron: 704
KATALOG KSI¥¯EK
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
DODAJ DO KOSZYKA
Ksi¹¿ka „Java. Algorytmy i struktury danych” jest ³atwym do zrozumienia
podrêcznikiem powiê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¿onoci¹ 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¿liwoci 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³aciwych 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
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWOCIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
11676249.002.png 11676249.003.png 11676249.004.png
Spis treci
O Autorze...............................................................................................................19
Drogi Czytelniku....................................................................................................20
Wprowadzenie .......................................................................................................21
Co nowego w drugim wydaniu? ....................................................................................................................... 21
Dodatkowe tematy................................................................................................................................ 21
Pytania kocowe................................................................................................................................... 22
Eksperymenty ....................................................................................................................................... 22
Projekty programistyczne..................................................................................................................... 22
O czym jest ta ksi ka?..................................................................................................................................... 22
Czym ta ksi ka ró ni si" od innych?............................................................................................................... 23
Łatwa do zrozumienia .......................................................................................................................... 23
Warsztaty algorytmów.......................................................................................................................... 24
Przykłady w Javie................................................................................................................................. 24
Komu mo e si" przyda- ta ksi ka? ................................................................................................................. 25
Co musimy wiedzie-, zanim zaczniemy j czyta-? .......................................................................................... 25
Potrzebne oprogramowanie............................................................................................................................... 25
Organizacja ksi ki ........................................................................................................................................... 25
Dobrej zabawy! ................................................................................................................................................. 27
1.
Przegld .................................................................................................................29
Do czego s przydatne struktury danych i algorytmy? ..................................................................................... 29
Przechowywanie danych ze 4wiata zewn"trznego ............................................................................... 30
Narz"dzia programisty.......................................................................................................................... 31
Modelowanie danych ze 4wiata zewn"trznego..................................................................................... 31
Przegld struktur danych................................................................................................................................... 31
Przegld algorytmów ........................................................................................................................................ 31
Kilka definicji.................................................................................................................................................... 32
Baza danych.......................................................................................................................................... 32
Rekord .................................................................................................................................................. 33
11676249.005.png
6
SPIS TRECI
Pole ....................................................................................................................................................... 33
Klucz..................................................................................................................................................... 33
Programowanie obiektowe................................................................................................................................ 34
Problemy z j"zykami proceduralnymi.................................................................................................. 34
Obiekty w telegraficznym skrócie........................................................................................................ 35
Działajcy program obiektowy............................................................................................................. 37
Dziedziczenie i polimorfizm ................................................................................................................ 39
In ynieria programowania................................................................................................................................. 40
Java dla programistów C++ .............................................................................................................................. 40
Brak wska=ników ................................................................................................................................. 41
Operatory przeci one.......................................................................................................................... 44
Typy proste........................................................................................................................................... 44
Operacje wej4cia-wyj4cia ..................................................................................................................... 44
Struktury danych w bibliotece Javy .................................................................................................................. 47
Podsumowanie .................................................................................................................................................. 47
Pytania............................................................................................................................................................... 48
2.
Tablice ...................................................................................................................49
Aplet demonstracyjny ....................................................................................................................................... 49
Wstawianie ........................................................................................................................................... 51
Wyszukiwanie ...................................................................................................................................... 51
Usuwanie .............................................................................................................................................. 52
Kwestia duplikatów .............................................................................................................................. 53
Niezbyt szybko ..................................................................................................................................... 55
Tablice w Javie.................................................................................................................................................. 55
Tworzenie tablicy ................................................................................................................................. 55
Dost"p do elementów tablicy ............................................................................................................... 56
Inicjalizacja........................................................................................................................................... 56
Przykład u ycia tablic........................................................................................................................... 57
Dzielenie programu na klasy............................................................................................................................. 59
Klasy LowArray i LowArrayApp......................................................................................................... 61
Interfejsy klas.................................................................................................................................................... 61
Niezbyt wygodnie................................................................................................................................. 62
Kto i za co odpowiada? ........................................................................................................................ 62
Program highArray.java ....................................................................................................................... 63
… i ycie u ytkownika stało si" prostsze............................................................................................. 66
Abstrakcja............................................................................................................................................. 66
Aplet demonstrujcy tablic" uporzdkowan ................................................................................................... 66
Wyszukiwanie liniowe ......................................................................................................................... 66
Wyszukiwanie binarne ......................................................................................................................... 67
Tablica uporzdkowana w Javie ....................................................................................................................... 69
Wyszukiwanie binarne w metodzie find()............................................................................................ 70
Klasa OrdArray..................................................................................................................................... 71
Korzy4ci wynikajce z u ywania tablic uporzdkowanych ................................................................. 74
Logarytmy......................................................................................................................................................... 74
Pot"gowanie.......................................................................................................................................... 75
Przeciwiestwo podnoszenia do pot"gi................................................................................................ 76
Przechowywanie obiektów................................................................................................................................ 76
Klasa Person ......................................................................................................................................... 76
Program classDataArray.java ............................................................................................................... 77
SPIS TRECI
7
Notacja O()........................................................................................................................................................ 81
Wstawianie do tablicy nieuporzdkowanej: czas stały......................................................................... 81
Wyszukiwanie liniowe: czas proporcjonalny do N .............................................................................. 81
Wyszukiwanie binarne: czas proporcjonalny do log(N) ...................................................................... 82
Stała niepotrzebna................................................................................................................................. 82
Czy tablice nadaj si" do wszystkiego? ............................................................................................................ 83
Podsumowanie .................................................................................................................................................. 84
Pytania............................................................................................................................................................... 85
Eksperymenty.................................................................................................................................................... 86
Projekty programistyczne.................................................................................................................................. 86
3.
Proste algorytmy sortowania .................................................................................87
W szeregu zbiórka!............................................................................................................................................ 88
Sortowanie bbelkowe ...................................................................................................................................... 89
Sortowanie bbelkowe zawodników dru yny ...................................................................................... 89
Aplet demonstracyjny sortowania bbelkowego.................................................................................. 91
Sortowanie bbelkowe w Javie............................................................................................................. 94
Niezmienniki ........................................................................................................................................ 97
Wydajno4- sortowania bbelkowego ................................................................................................... 97
Sortowanie przez wybór.................................................................................................................................... 98
Sortowanie przez wybór dru yny baseballowej ................................................................................... 98
Aplet demonstracyjny sortowania przez wybór ................................................................................. 100
Sortowanie przez wybór w Javie........................................................................................................ 101
Niezmiennik........................................................................................................................................ 103
Wydajno4- sortowania przez wybór................................................................................................... 103
Sortowanie przez wstawianie.......................................................................................................................... 103
Sortowanie przez wstawianie dru yny baseballowej ......................................................................... 103
Aplet demonstracyjny sortowania przez wstawianie.......................................................................... 104
Sortowanie przez wstawianie w Javie ................................................................................................ 107
Niezmiennik w sortowaniu przez wstawianie .................................................................................... 110
Wydajno4- sortowania przez wstawianie........................................................................................... 110
Sortowanie obiektów....................................................................................................................................... 111
Program sortujcy tablic" obiektów ................................................................................................... 111
Porównania leksykograficzne............................................................................................................. 114
Stabilno4-............................................................................................................................................ 115
Porównanie prostych algorytmów sortowania................................................................................................ 115
Podsumowanie ................................................................................................................................................ 115
Pytania............................................................................................................................................................. 116
Eksperymenty.................................................................................................................................................. 117
Projekty programistyczne................................................................................................................................ 118
4.
Stosy i kolejki ......................................................................................................121
Inny rodzaj struktur danych............................................................................................................................. 121
Narz"dzia programisty........................................................................................................................ 121
Ograniczony dost"p ............................................................................................................................ 122
Bardziej abstrakcyjne ......................................................................................................................... 122
Stosy................................................................................................................................................................ 122
Analogia pocztowa ............................................................................................................................. 123
Aplet demonstracyjny stosu................................................................................................................ 124
11676249.001.png
8
SPIS TRECI
Stos w Javie ........................................................................................................................................ 126
Wykorzystanie stosu do odwracania słowa........................................................................................ 129
Wykorzystanie stosu do sprawdzania nawiasów................................................................................ 131
Wydajno4- stosów .............................................................................................................................. 136
Kolejki............................................................................................................................................................. 136
Aplet demonstracyjny kolejki............................................................................................................. 137
Kolejka cykliczna ............................................................................................................................... 140
Kolejka w Javie .................................................................................................................................. 141
Wydajno4- kolejek ............................................................................................................................. 146
Kolejki dwustronne............................................................................................................................. 146
Kolejki priorytetowe ....................................................................................................................................... 146
Aplet demonstracyjny kolejki priorytetowej ...................................................................................... 147
Kolejka priorytetowa w Javie............................................................................................................. 150
Wydajno4- kolejek priorytetowych.................................................................................................... 152
Analiza wyra e arytmetycznych ................................................................................................................... 152
Notacja przyrostkowa......................................................................................................................... 152
Zamiana notacji naturalnej na przyrostkow...................................................................................... 153
Obliczanie wyra e w notacji przyrostkowej..................................................................................... 167
Podsumowanie ................................................................................................................................................ 172
Pytania............................................................................................................................................................. 172
Eksperymenty.................................................................................................................................................. 174
Projekty programistyczne................................................................................................................................ 174
5.
Listy powizane ...................................................................................................177
Połczenia........................................................................................................................................................ 178
Referencje i typy proste...................................................................................................................... 179
Relacja, nie pozycja............................................................................................................................ 180
Aplet demonstracyjny listy powizanej .......................................................................................................... 181
Przycisk Ins......................................................................................................................................... 181
Przycisk Find ...................................................................................................................................... 182
Przycisk Del........................................................................................................................................ 182
Prosta lista powizana..................................................................................................................................... 183
Klasa Link........................................................................................................................................... 183
Klasa LinkList .................................................................................................................................... 184
Metoda insertFirst() ............................................................................................................................ 185
Metoda deleteFirst() ........................................................................................................................... 186
Metoda displayList()........................................................................................................................... 187
Program linkList.java ......................................................................................................................... 187
Wyszukiwanie i usuwanie okre4lonych elementów........................................................................................ 190
Metoda find()...................................................................................................................................... 193
Metoda delete()................................................................................................................................... 193
Inne metody ........................................................................................................................................ 194
Listy dwustronne............................................................................................................................................. 194
Wydajno4- list powizanych........................................................................................................................... 198
Abstrakcyjne typy danych............................................................................................................................... 199
Implementacja stosu przy u yciu listy powizanej ............................................................................ 199
Implementacja kolejki przy u yciu listy powizanej ......................................................................... 202
Typy danych i abstrakcja.................................................................................................................... 205
Listy abstrakcyjne............................................................................................................................... 206
Abstrakcyjne typy danych jako narz"dzia projektowe....................................................................... 206

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin