Darmowy fragment publikacji:
Tytuł oryginału: Beginning Java Data Structures and Algorithms
Tłumaczenie: Krzysztof Bąbol
ISBN: 978-83-283-5329-9
Copyright © Packt Publishing 2018. First published in the English language under the title ‘Beginning Java
Data Structures and Algorithms – (9781789537178)’.
Polish edition copyright © 2019 by Helion SA
All rights reserved.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means,
electronic or mechanical, including photocopying, recording or by any information storage retrieval system,
without permission from the Publisher.
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej
publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną,
fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje
naruszenie praw autorskich niniejszej publikacji.
Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich
właścicieli.
Autor oraz Helion SA dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne
i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym
ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Helion SA nie ponoszą również
żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce.
Helion SA
ul. Kościuszki 1c, 44-100 Gliwice
tel. 32 231 22 19, 32 230 98 63
e-mail: helion@helion.pl
WWW: http://helion.pl (księgarnia internetowa, katalog książek)
Pliki z przykładami omawianymi w książce można znaleźć pod adresem:
ftp://ftp.helion.pl/przyklady/sdalgj.zip
Drogi Czytelniku!
Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres
http://helion.pl/user/opinie/sdalgj
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
Printed in Poland.
• Kup książkę
• Poleć książkę
• Oceń książkę
• Księgarnia internetowa
• Lubię to! » Nasza społeczność
Spis tre(cid:258)ci
O autorze
Wst(cid:218)p
Rozdzia(cid:239) 1. Algorytmy i ich z(cid:239)o(cid:285)ono(cid:258)(cid:202)
Tworzymy nasz pierwszy algorytm
Algorytm konwersji liczb dwójkowych na dziesi(cid:218)tne
Mierzenie z(cid:239)o(cid:285)ono(cid:258)ci algorytmów za pomoc(cid:200) notacji du(cid:285)ego O
Przyk(cid:239)ad na z(cid:239)o(cid:285)ono(cid:258)(cid:202)
Zrozumienie z(cid:239)o(cid:285)ono(cid:258)ci
Notacja z(cid:239)o(cid:285)ono(cid:258)ci
Identyfikacja algorytmów o ró(cid:285)nej z(cid:239)o(cid:285)ono(cid:258)ci
Z(cid:239)o(cid:285)ono(cid:258)(cid:202) liniowa
Z(cid:239)o(cid:285)ono(cid:258)(cid:202) kwadratowa
Z(cid:239)o(cid:285)ono(cid:258)(cid:202) logarytmiczna
Z(cid:239)o(cid:285)ono(cid:258)(cid:202) wyk(cid:239)adnicza
Z(cid:239)o(cid:285)ono(cid:258)(cid:202) sta(cid:239)a
Podsumowanie
Rozdzia(cid:239) 2. Algorytmy sortowania i podstawowe struktury danych
Wprowadzenie do sortowania b(cid:200)belkowego
Zrozumienie sortowania b(cid:200)belkowego
Udoskonalanie sortowania b(cid:200)belkowego
Zrozumienie sortowania szybkiego
Zrozumienie rekurencji
Podzia(cid:239) w wyszukiwaniu szybkim
Jak to wszystko posk(cid:239)ada(cid:202) razem
Korzystanie z sortowania przez scalanie
Dzielenie problemu
Scalanie problemu
7
9
13
14
14
16
16
19
22
26
27
28
29
30
32
34
35
35
36
37
40
40
42
44
46
47
48
Poleć książkęKup książkę Spis tre(cid:286)ci
Rozpocz(cid:218)cie pracy z podstawowymi strukturami danych
Wprowadzenie do struktur danych
Struktura list powi(cid:200)zanych
Operacje na listach powi(cid:200)zanych
Kolejki
Stosy
Modelowanie stosów i kolejek przy u(cid:285)yciu tablic
Podsumowanie
Rozdzia(cid:239) 3. Tablice z haszowaniem i binarne drzewa poszukiwa(cid:241)
Wprowadzenie do tablic z haszowaniem
Zrozumienie tablic z haszowaniem
Rozwi(cid:200)zywanie kolizji przez (cid:239)a(cid:241)cuchowanie
Rozwi(cid:200)zywanie kolizji przez adresowanie otwarte
Haszowanie uniwersalne
Rozpocz(cid:218)cie pracy z binarnymi drzewami poszukiwa(cid:241)
Struktura drzewa binarnego
Operacje na binarnych drzewach poszukiwa(cid:241)
Przechodzenie przez binarne drzewo poszukiwa(cid:241)
Zrównowa(cid:285)one binarne drzewa poszukiwa(cid:241)
Podsumowanie
Rozdzia(cid:239) 4. Paradygmaty projektowania algorytmów
Wprowadzenie do algorytmów zach(cid:239)annych
Problem wyboru zaj(cid:218)(cid:202)
Rozwi(cid:200)zanie problemu wyboru zaj(cid:218)(cid:202)
Sk(cid:239)adniki algorytmu zach(cid:239)annego
Kodowanie Huffmana
(cid:109)wiczenie: Implementacja algorytmu zach(cid:239)annego
do obliczania u(cid:239)amków egipskich
Wprowadzenie do algorytmów typu „dziel i zwyci(cid:218)(cid:285)aj”
Podej(cid:258)cie „dziel i zwyci(cid:218)(cid:285)aj”
Metoda rekurencji uniwersalnej
Problem najbli(cid:285)szej pary punktów
(cid:109)wiczenie: Rozwi(cid:200)zywanie problemu podtablicy o najwi(cid:218)kszej sumie
Zrozumienie programowania dynamicznego
Elementy problematyki programowania dynamicznego
Dyskretny problem plecakowy
Najd(cid:239)u(cid:285)szy wspólny podci(cid:200)g
(cid:109)wiczenie: Problem wydawania reszty
Podsumowanie
Rozdzia(cid:239) 5. Algorytmy wyszukiwania wzorca w tek(cid:258)cie
Algorytm wyszukiwania naiwnego
Implementacja wyszukiwania naiwnego
Usprawnienie algorytmu wyszukiwania naiwnego
4
50
51
51
53
57
58
60
64
65
65
66
68
71
76
78
78
80
84
86
91
93
94
94
96
96
99
102
103
103
104
106
109
110
110
111
114
116
117
119
119
120
121
Poleć książkęKup książkę Spis tre(cid:286)ci
Pierwsze kroki z algorytmem wyszukiwania wzorca Boyera-Moore’a
Zasada niezgodno(cid:258)ci
Zasada dobrego sufiksu
Zastosowanie algorytmu Boyera-Moore’a
Prezentacja innych algorytmów wyszukiwania wzorca w tek(cid:258)cie
Algorytm Rabina-Karpa
Algorytm Knutha-Morrisa-Pratta
Algorytm Aho-Corasick
Podsumowanie
Rozdzia(cid:239) 6. Grafy, liczby pierwsze i klasy z(cid:239)o(cid:285)ono(cid:258)ci
Reprezentacja grafów
Listy s(cid:200)siedztwa
Macierz s(cid:200)siedztwa
Przechodzenie przez graf
Przeszukiwanie wszerz
Przeszukiwanie w g(cid:239)(cid:200)b
Wykrywanie cykli
Obliczanie najkrótszych (cid:258)cie(cid:285)ek
Najkrótsza (cid:258)cie(cid:285)ka z pojedynczego (cid:283)ród(cid:239)a: algorytm Dijkstry
Najkrótsze (cid:258)cie(cid:285)ki dla wszystkich par wierzcho(cid:239)ków: algorytm Floyda-Warshalla
Liczby pierwsze w algorytmach
Sito Eratostenesa
Rozk(cid:239)ad na czynniki pierwsze
Inne koncepcje zwi(cid:200)zane z grafami
Minimalne drzewa rozpinaj(cid:200)ce
Algorytm A*
Problem maksymalnego przep(cid:239)ywu
Zrozumienie klas z(cid:239)o(cid:285)ono(cid:258)ci problemów
Podsumowanie
Skorowidz
122
123
125
129
130
130
132
132
133
135
136
137
139
142
142
144
147
149
150
154
158
158
158
159
159
160
161
161
162
163
5
Poleć książkęKup książkę Spis tre(cid:286)ci
6
Poleć książkęKup książkę 2
Algorytmy sortowania
i podstawowe
struktury danych
W poprzednim rozdziale pokaza(cid:239)em, jak ulepszy(cid:202) rozwi(cid:200)zanie problemu znajdowania cz(cid:218)(cid:258)ci
wspólnej, korzystaj(cid:200)c z algorytmu sortowania. To cz(cid:218)sty przypadek. Je(cid:285)eli bowiem dane s(cid:200) upo-
rz(cid:200)dkowane, mo(cid:285)na opracowa(cid:202) efektywniejszy algorytm. Ten rozdzia(cid:239) rozpoczniemy od zbadania
trzech technik sortowania: b(cid:200)belkowego, szybkiego i przez scalanie. Pó(cid:283)niej poznasz ró(cid:285)ne spo-
soby organizowania danych w podstawowe struktury.
Z tego rozdzia(cid:239)u dowiesz si(cid:218), jak:
(cid:81) opisa(cid:202) sposób dzia(cid:239)ania sortowania b(cid:200)belkowego;
(cid:81) zaimplementowa(cid:202) lepsze rozwi(cid:200)zanie — sortowanie szybkie;
(cid:81) scharakteryzowa(cid:202) sortowanie przez scalanie;
(cid:81) stworzy(cid:202) struktur(cid:218) danych — list(cid:218) wi(cid:200)zan(cid:200);
(cid:81) zaimplementowa(cid:202) kolejki;
(cid:81) opisa(cid:202) struktur(cid:218) danych stosu.
Wprowadzenie
do sortowania b(cid:200)belkowego
Sortowanie b(cid:200)belkowe jest najprostszym algorytmem sortowania. Wi(cid:200)(cid:285)e si(cid:218) z wielokrotnym
przej(cid:258)ciem przez tablic(cid:218) wej(cid:258)ciow(cid:200) i zamian(cid:200) miejscami s(cid:200)siaduj(cid:200)cych nieuporz(cid:200)dkowanych
elementów. Technika ta nazywa si(cid:218) sortowaniem b(cid:200)belkowym, poniewa(cid:285) posortowane fragmenty
jak b(cid:200)belki przemieszczaj(cid:200) si(cid:218) z ko(cid:241)ca listy.
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
Zrozumienie sortowania b(cid:200)belkowego
Ka(cid:285)dy algorytm sortowania przyjmuje list(cid:218) elementów i zwraca je uporz(cid:200)dkowane. G(cid:239)ówn(cid:200) ró(cid:285)-
nic(cid:200) mi(cid:218)dzy algorytmami jest sposób, w jaki dokonuj(cid:200) sortowania. Sortowanie b(cid:200)belkowe dzia(cid:239)a
na zasadzie zamiany miejscami s(cid:200)siaduj(cid:200)cych elementów. Tak posortowane elementy s(cid:200) spychane
na koniec listy.
Na listingu 2.1 zosta(cid:239) pokazany pseudokod sortowania b(cid:200)belkowego. Algorytm wykonuje trzy
proste zadania: wielokrotnie przechodzi przez list(cid:218) do sortowania, porównuje s(cid:200)siaduj(cid:200)ce ele-
menty i zamienia je miejscami, je(cid:258)li pierwszy element jest wi(cid:218)kszy od drugiego.
Listing 2.1. Pseudokod sortowania b(cid:200)belkowego
bubbleSort(array)
n = length(array)
for (k = 1 until n)
for (j = 0 until -1)
if(array[j] array[j + 1])
swap(array, j, j + 1)
Ile przej(cid:258)(cid:202) nale(cid:285)y wykona(cid:202), by tablica by(cid:239)a posortowana? Jak si(cid:218) okazuje, potrzeba do tego n–1
iteracji, gdzie n jest wielko(cid:258)ci(cid:200) tablicy. W nast(cid:218)pnym punkcie poka(cid:285)(cid:218), dlaczego konieczne jest
tyle przej(cid:258)(cid:202), ale sortowanie b(cid:200)belkowe ma z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasow(cid:200) O(n(cid:21)) w(cid:239)a(cid:258)nie dlatego, (cid:285)e przetwa-
rzamy n elementów n–1 razy.
Funkcja swap z listingu 2.1 przy u(cid:285)yciu zmiennej tymczasowej zamienia warto(cid:258)ci w miejscach tablicy o in-
deksach j oraz j+1.
Implementacja sortowania b(cid:200)belkowego
Aby zaimplementowa(cid:202) sortowanie b(cid:200)belkowe w Javie, wykonaj nast(cid:218)puj(cid:200)ce kroki:
1. Prze(cid:239)ó(cid:285) pseudokod pokazany na listingu 2.1 na j(cid:218)zyk Java. Utwórz klas(cid:218) i metod(cid:218)
przyjmuj(cid:200)c(cid:200) do sortowania tablic(cid:218) w nast(cid:218)puj(cid:200)cy sposób:
public void sort(int[] numbers)
2. Trudno(cid:258)(cid:202) w tym algorytmie mo(cid:285)e sprawi(cid:202) zamiana elementów miejscami. W tym
celu jeden z zamienianych elementów przypisuje si(cid:218) do zmiennej tymczasowej,
tak jak na listingu 2.2.
Listing 2.2. Metoda sortowania b(cid:200)belkowego. Nazwa klasy (cid:283)ród(cid:239)owej: BubbleSort
public void sort(int[] numbers) {
for (int i = 1; i numbers.length; i++) {
for (int j = 0; j numbers.length - 1; j++) {
if (numbers[j] numbers[j + 1]) {
int temp = numbers[j];
36
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
}
}
}
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
Chocia(cid:285) sortowanie b(cid:200)belkowe bardzo (cid:239)atwo zaimplementowa(cid:202), jest te(cid:285) jedn(cid:200) z najwolniejszych
metod sortowania. W nast(cid:218)pnej sekcji przyjrzymy si(cid:218), jak poprawi(cid:202) nieco wydajno(cid:258)(cid:202) tego
algorytmu.
Udoskonalanie sortowania b(cid:200)belkowego
Aby poprawi(cid:202) wydajno(cid:258)(cid:202) sortowania b(cid:200)belkowego, mo(cid:285)na zastosowa(cid:202) dwie g(cid:239)ówne techniki.
Trzeba zdawa(cid:202) sobie spraw(cid:218), (cid:285)e chocia(cid:285) w przeci(cid:218)tnym przypadku obie te strategie poprawiaj(cid:200)
ogóln(cid:200) wydajno(cid:258)(cid:202) sortowania b(cid:200)belkowego, to w najgorszym przypadku algorytm nadal ma
t(cid:218) sam(cid:200) s(cid:239)ab(cid:200) z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasow(cid:200) O(n(cid:21)).
Pierwszym drobnym ulepszeniem, jakie mo(cid:285)na wprowadzi(cid:202) do pierwotnego sortowania b(cid:200)bel-
kowego, jest wykorzystanie faktu, (cid:285)e uporz(cid:200)dkowany „b(cid:200)belek” tworzy si(cid:218) na ko(cid:241)cu listy.
Podczas ka(cid:285)dego przej(cid:258)cia do „b(cid:200)belka” do(cid:239)(cid:200)czany jest kolejny element. Dlatego w(cid:239)a(cid:258)nie
wymagane jest (n–1) przej(cid:258)(cid:202).
Przedstawia to równie(cid:285) rysunek 2.1, gdzie elementy w kropkowanym kole s(cid:200) ju(cid:285) posortowane
i we w(cid:239)a(cid:258)ciwym miejscu.
Rysunek 2.1. Tworzenie „b(cid:200)belków” na ko(cid:241)cu listy
37
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
Mo(cid:285)na wykorzysta(cid:202) ten fakt, by nie sortowa(cid:202) elementów wewn(cid:200)trz „b(cid:200)belka”. W tym celu
nale(cid:285)y nieznacznie zmodyfikowa(cid:202) kod w Javie w sposób pokazany na listingu 2.3. W wewn(cid:218)trz-
nej p(cid:218)tli, zamiast przetwarza(cid:202) list(cid:218) do ko(cid:241)ca, mo(cid:285)emy zatrzyma(cid:202) si(cid:218) tu(cid:285) przed posortowanym
„b(cid:200)belkiem”, na pozycji numbers.length - i. Dla zwi(cid:218)z(cid:239)o(cid:258)ci w listingu 2.3 zamiast kodu doko-
nuj(cid:200)cego zamiany elementów miejscami wprowadzi(cid:239)em wywo(cid:239)anie metody w inny sposób.
Listing 2.3. Ulepszone sortowanie b(cid:200)belkowe 1. Nazwa klasy (cid:283)ród(cid:239)owej: BubbleSort
public void sortImprovement1(int[] numbers) {
for (int i = 1; i numbers.length; i++) {
for (int j = 0; j numbers.length - i; j++) {
if (numbers[j] numbers[j + 1]) {
swap(numbers, j, j + 1);
}
}
}
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
Je(cid:258)li do algorytmu sortowania b(cid:200)belkowego przeka(cid:285)emy posortowan(cid:200) list(cid:218), to mimo braku
zmian nadal b(cid:218)dziemy wykonywa(cid:202) wiele przej(cid:258)(cid:202). Mo(cid:285)emy wi(cid:218)c poprawi(cid:202) algorytm, tak by
wychodzi(cid:239) z p(cid:218)tli zewn(cid:218)trznej, je(cid:285)eli lista wewn(cid:200)trz tablicy jest w pe(cid:239)ni posortowana. W tym celu
nale(cid:285)y sprawdzi(cid:202), czy podczas ostatniego przej(cid:258)cia dokonano jakichkolwiek zamian. Je(cid:258)li wi(cid:218)c
przeka(cid:285)emy do metody ju(cid:285) posortowan(cid:200) list(cid:218), wystarczy przej(cid:258)(cid:202) jeden raz przez tablic(cid:218) i pozo-
stawi(cid:202) j(cid:200) bez zmian. Oznacza to, (cid:285)e przypadek optymistyczny ma teraz z(cid:239)o(cid:285)ono(cid:258)(cid:202) O (n), chocia(cid:285)
z(cid:239)o(cid:285)ono(cid:258)(cid:202) pesymistyczna pozosta(cid:239)a taka sama.
Implementacja poprawionego sortowania b(cid:200)belkowego
Ulepszymy algorytm sortowania b(cid:200)belkowego, zmniejszaj(cid:200)c liczb(cid:218) przebiegów.
W tym celu trzeba wykona(cid:202) nast(cid:218)puj(cid:200)ce kroki:
1. Zmie(cid:241) metod(cid:218) sortowania b(cid:200)belkowego, aby przesta(cid:239)a sortowa(cid:202), je(cid:258)li po przej(cid:258)ciu
przez wewn(cid:218)trzn(cid:200) p(cid:218)tl(cid:218) tablica nie uleg(cid:239)a zmianom.
2. Rozwi(cid:200)zanie to naj(cid:239)atwiej opracowa(cid:202), zamieniaj(cid:200)c zewn(cid:218)trzn(cid:200) p(cid:218)tl(cid:218) for na p(cid:218)tl(cid:218)
while oraz wprowadzaj(cid:200)c flag(cid:218) wskazuj(cid:200)c(cid:200), czy podczas przechodzenia przez
tablic(cid:218) zosta(cid:239)y zamienione jakie(cid:258) elementy. Pokazuje to listing 2.4.
Listing 2.4. Ulepszone sortowanie b(cid:200)belkowe 2. Nazwa klasy (cid:283)ród(cid:239)owej: BubbleSort
public void sortImprovement2(int[] numbers) {
int i = 0;
boolean swapOccured = true;
while (swapOccured) {
38
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
swapOccured = false;
i++;
for (int j = 0; j numbers.length - i; j++) {
if (numbers[j] numbers[j + 1]) {
swap(numbers, j, j + 1);
swapOccured = true;
}
}
}
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
W tym punkcie pokaza(cid:239)em kilka prostych sztuczek poprawiaj(cid:200)cych algorytm sortowania b(cid:200)bel-
kowego. W kolejnych podrozdzia(cid:239)ach przyjrzymy si(cid:218) innym technikom sortowania, które dzia(cid:239)aj(cid:200)
znacznie szybciej ni(cid:285) sortowanie b(cid:200)belkowe.
(cid:109)wiczenie: Implementacja sortowania przez wybieranie w j(cid:218)zyku Java
Scenariusz
Sortowanie przez wybieranie naj(cid:239)atwiej zrozumie(cid:202) na podstawie dwóch list, A i B. Na pocz(cid:200)tku
lista A zawiera wszystkie nieposortowane elementy, lista B jest za(cid:258) pusta. Pomys(cid:239) polega na
zapisywaniu posortowanych elementów w li(cid:258)cie B. Dzia(cid:239)anie algorytmu polega na znajdowaniu
najmniejszego elementu listy A i przesuwaniu go na koniec listy B. Robimy to, dopóki lista A
nie jest pusta, a B nie jest pe(cid:239)na.
Zamiast dwóch oddzielnych list mo(cid:285)emy po prostu u(cid:285)y(cid:202) tej samej tablicy wej(cid:258)ciowej, utrzymuj(cid:200)c
wska(cid:283)nik dziel(cid:200)cy tablic(cid:218) na dwie cz(cid:218)(cid:258)ci.
Mo(cid:285)na to wyja(cid:258)ni(cid:202) na przyk(cid:239)adzie z (cid:285)ycia. Wyobra(cid:283) sobie sortowanie talii kart. Po potasowaniu
talii przegl(cid:200)dasz karty jedna po drugiej, a(cid:285) znajdziesz najni(cid:285)sz(cid:200). Odk(cid:239)adasz j(cid:200) na bok na nowy,
drugi stos. Potem szukasz nast(cid:218)pnej najni(cid:285)szej karty i po znalezieniu k(cid:239)adziesz j(cid:200) na spód dru-
giego stosu. Powtarzasz te czynno(cid:258)ci, dopóki pierwszy stos nie jest pusty.
Jednym ze sposobów doj(cid:258)cia do rozwi(cid:200)zania jest napisanie najpierw pseudokodu, korzystaj(cid:200)-
cego z dwóch tablic (opisanych wcze(cid:258)niej jako A i B). Nast(cid:218)pnie nale(cid:285)y dostosowa(cid:202) pseudokod
tak, by zapisywa(cid:239) posortowan(cid:200) list(cid:218) (tablic(cid:218) B) w tej samej tablicy, w której s(cid:200) dane wej(cid:258)ciowe.
Cel
Implementacja sortowania przez wybieranie w j(cid:218)zyku Java.
39
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
Warunki wst(cid:218)pne
(cid:81) Zaimplementuj metod(cid:218) sort, znajduj(cid:200)c(cid:200) si(cid:218) w klasie dost(cid:218)pnej w kodzie do(cid:239)(cid:200)czonym
do tej ksi(cid:200)(cid:285)ki pod adresem src/main/java/com/packt/datastructuresandalg/
lesson2/activity/selectionsort/SelectionSort.java
(cid:81) Metoda sort powinna przyj(cid:200)(cid:202) tablic(cid:218) liczb ca(cid:239)kowitych i j(cid:200) posortowa(cid:202).
Je(cid:258)li skonfigurowa(cid:239)e(cid:258) projekt, testy jednostkowe do tego (cid:202)wiczenia uruchomisz nast(cid:218)puj(cid:200)cym poleceniem:
gradlew test --tests com.packt.datastructuresandalg.lesson2.activity.selectionsort*
Kroki do wykonania
1. Podziel tablic(cid:218) wej(cid:258)ciow(cid:200) na dwie za pomoc(cid:200) wska(cid:283)nika indeksu tablicy.
2. Metoda sort powinna przyj(cid:200)(cid:202) tablic(cid:218) liczb ca(cid:239)kowitych i j(cid:200) posortowa(cid:202).
3. Przejd(cid:283) przez nieposortowan(cid:200) cz(cid:218)(cid:258)(cid:202) tablicy, aby znale(cid:283)(cid:202) w niej warto(cid:258)(cid:202) minimaln(cid:200).
4. Zamie(cid:241) znaleziony element miejscami, przenosz(cid:200)c go na koniec cz(cid:218)(cid:258)ci posortowanej.
Zrozumienie sortowania szybkiego
Sortowanie szybkie stanowi du(cid:285)y post(cid:218)p w porównaniu z sortowaniem b(cid:200)belkowym. Technika
sortowania szybkiego zosta(cid:239)a opracowana przez brytyjskiego informatyka Tony’ego Hoare’a.
Algorytm wykonuje trzy g(cid:239)ówne kroki:
1. Wybiera element osiowy.
2. Dzieli list(cid:218) tak, by elementy po lewej stronie elementu osiowego by(cid:239)y mniejsze ni(cid:285)
warto(cid:258)(cid:202) tego elementu, a te po prawej wi(cid:218)ksze.
3. Powtarza kroki 1. i 2. osobno dla lewej i prawej cz(cid:218)(cid:258)ci.
Poniewa(cid:285) sortowanie szybkie wymaga u(cid:285)ycia rekurencji, ten podrozdzia(cid:239) zaczniemy od zapre-
zentowania jej przyk(cid:239)adu. Potem przyjrzymy si(cid:218) dokonywaniu podzia(cid:239)u w algorytmie sortowania
szybkiego, a w ko(cid:241)cowej cz(cid:218)(cid:258)ci zastosujemy techniki rekurencyjne.
Zrozumienie rekurencji
Rekurencja to naprawd(cid:218) przydatne narz(cid:218)dzie dla twórców algorytmów. Pozwala pokonywa(cid:202)
du(cid:285)e problemy, rozwi(cid:200)zuj(cid:200)c te same problemy w mniejszej skali. Funkcje rekurencyjne maj(cid:200)
zwykle podobn(cid:200) struktur(cid:218) i zawieraj(cid:200) nast(cid:218)puj(cid:200)ce sk(cid:239)adniki:
(cid:81) Co najmniej jeden warunek zatrzymania: w pewnych warunkach powstrzymuj(cid:200) one
funkcj(cid:218) przed ponownym wywo(cid:239)aniem siebie samej.
(cid:81) Co najmniej jedno wywo(cid:239)anie rekurencyjne: maj(cid:200) one miejsce wtedy, gdy funkcja
(lub metoda) wywo(cid:239)uje sam(cid:200) siebie.
40
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
W nast(cid:218)pnym przyk(cid:239)adzie we(cid:283)miemy na warsztat problem wyszukiwania binarnego z poprzed-
niego rozdzia(cid:239)u i zmienimy algorytm tak, by dzia(cid:239)a(cid:239) rekurencyjnie. Przeanalizujmy problem
wyszukiwania binarnego omówiony w rozdziale 1., „Algorytmy i i ich z(cid:239)o(cid:285)ono(cid:258)(cid:202)”, pokazany
na listingu 1.7. Implementacja ta jest iteracyjna, to znaczy dzia(cid:239)a w p(cid:218)tli, a(cid:285) element zostanie
znaleziony albo parametr end b(cid:218)dzie równy lub wi(cid:218)kszy od zmiennej start. Listing 2.5 zawiera
pseudokod pokazuj(cid:200)cy, jak mo(cid:285)emy zamieni(cid:202) t(cid:218) metod(cid:218) na funkcj(cid:218) rekurencyjn(cid:200).
Listing 2.5. Rekurencyjny pseudokod wyszukiwania binarnego
binarySearch(x, array, start, end)
if(start = end)
mid = (end - start) / 2 + start
if (array[mid] == x) return true
if (array[mid] x) return binarySearch(x, array, start, mid - 1)
return binarySearch(x, array, mid + 1, end)
return false
W rekurencyjnym wyszukiwaniu binarnym tak naprawd(cid:218) istniej(cid:200) dwa warunki zatrzymania. Funkcja
zatrzymuje (cid:239)a(cid:241)cuch rekurencji, je(cid:258)li po drodze znajdzie wyszukiwany element albo je(cid:258)li wska(cid:283)nik pocz(cid:200)tkowy
do tablicy b(cid:218)dzie wi(cid:218)kszy od ko(cid:241)cowego, co oznacza, (cid:285)e element nie zosta(cid:239) znaleziony. Warunek zatrzyma-
nia mo(cid:285)na (cid:239)atwo znale(cid:283)(cid:202), sprawdzaj(cid:200)c wszystkie drogi wyj(cid:258)cia, które nie wymagaj(cid:200) dalszych wywo(cid:239)a(cid:241)
rekurencyjnych.
Implementacja rekurencyjnego wyszukiwania binarnego
Aby zaimplementowa(cid:202) rekurencyjne wyszukiwanie binarne w j(cid:218)zyku Java, wykonaj nast(cid:218)-
puj(cid:200)ce kroki:
1. U(cid:285)ywaj(cid:200)c pseudokodu pokazanego na listingu 2.5, zaimplementuj funkcj(cid:218) wykonuj(cid:200)c(cid:200)
rekurencyjnie wyszukiwanie binarne.
2. Dodaj kolejn(cid:200) metod(cid:218), której sygnatura b(cid:218)dzie zawiera(cid:202) tylko szukany element
i posortowan(cid:200) tablic(cid:218) jako dane wej(cid:258)ciowe. Ta metoda wywo(cid:239)a funkcj(cid:218) rekurencyjn(cid:200)
z odpowiednimi warto(cid:258)ciami w nast(cid:218)puj(cid:200)cy sposób:
public boolean binarySearch(int x, int[] sortedNumbers)
Wynik
Ta dodatkowa metoda wywo(cid:239)uje wst(cid:218)pnie funkcj(cid:218) rekurencyjn(cid:200), pokazan(cid:200) na listingu 2.6.
Listing 2.6. Rekurencyjne wyszukiwanie binarne. Nazwa klasy (cid:283)ród(cid:239)owej: BinarySearchRecursive
public boolean binarySearch(int x, int[] sortedNumbers, int start,
int end) {
if (start = end) {
int mid = (end - start) / 2 + start;
if (sortedNumbers[mid] == x) return true;
if (sortedNumbers[mid] x)
41
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
return binarySearch(x, sortedNumbers, start, mid - 1);
return binarySearch(x, sortedNumbers, mid + 1, end);
}
return false;}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
Rekurencja jest niezb(cid:218)dnym narz(cid:218)dziem ka(cid:285)dego programisty i b(cid:218)dziemy z niej korzysta(cid:202) w tej
ksi(cid:200)(cid:285)ce wielokrotnie. W tym punkcie zaimplementowali(cid:258)my przyk(cid:239)ad wyszukiwania binarnego.
W nast(cid:218)pnym przyjrzymy si(cid:218) dokonywaniu podzia(cid:239)u w algorytmie wyszukiwania szybkiego.
Podzia(cid:239) w wyszukiwaniu szybkim
Podzia(cid:239) jest procesem, w którym zmieniamy kolejno(cid:258)(cid:202) elementów tablicy tak, by elementy
o warto(cid:258)ci mniejszej ni(cid:285) element osiowy przenie(cid:258)(cid:202) na jego lew(cid:200) stron(cid:218), a elementy o warto(cid:258)ci
wi(cid:218)kszej przesun(cid:200)(cid:202) na prawo (rysunek 2.2). Mo(cid:285)na to zrobi(cid:202) na wiele sposobów. Tutaj opisz(cid:218)
(cid:239)atwy do zrozumienia schemat znany jako podzia(cid:239) Lomuto.
Rysunek 2.2. Przed podzia(cid:239)em tablicy i po podziale tablicy
Istnieje wiele innych schematów. Schemat Lomuto ma t(cid:218) wad(cid:218), (cid:285)e nie jest zbyt wydajny, gdy u(cid:285)ywa
si(cid:218) go na ju(cid:285) posortowanych listach. Oryginalny schemat podzia(cid:239)u Hoare’a ma lepsz(cid:200) wydajno(cid:258)(cid:202) i przetwarza
tablic(cid:218) z obu ko(cid:241)ców. Dzia(cid:239)a lepiej, poniewa(cid:285) dokonuje mniej zamian elementów, cho(cid:202) te(cid:285) jest ma(cid:239)o
efektywny, je(cid:258)li dane wej(cid:258)ciowe s(cid:200) posortowane. Zarówno schemat Lomuto, jak i Hoare’a powoduj(cid:200),
(cid:285)e sortowanie odbywa si(cid:218) w sposób niestabilny. Stabilno(cid:258)(cid:202) sortowania oznacza, (cid:285)e je(cid:285)eli co najmniej dwa
elementy maj(cid:200) t(cid:218) sam(cid:200) kluczow(cid:200) warto(cid:258)(cid:202), to pojawi(cid:200) si(cid:218) na wyj(cid:258)ciu w tej samej kolejno(cid:258)ci, w której
pojawi(cid:239)y si(cid:218) na wej(cid:258)ciu. Istniej(cid:200) inne schematy, sprawiaj(cid:200)ce, (cid:285)e sortowanie szybkie jest stabilne, ale wyko-
rzystuj(cid:200) one wi(cid:218)cej pami(cid:218)ci.
42
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
Aby dobrze zrozumie(cid:202) ten schemat podzia(cid:239)u, najlepiej upro(cid:258)ci(cid:202) dzia(cid:239)anie algorytm do pi(cid:218)ciu
prostych kroków:
1. Obierz skrajny prawy element tablicy za element osiowy.
2. Zacznij od lewej strony i znajd(cid:283) element wi(cid:218)kszy od elementu osiowego.
3. Zamie(cid:241) ten element miejscami z nast(cid:218)pnym, który jest mniejszy ni(cid:285) element osiowy.
4. Powtarzaj kroki 2. i 3., dopóki zamiana jest mo(cid:285)liwa.
5. Pierwszy element, którego warto(cid:258)(cid:202) jest wi(cid:218)ksza od elementu osiowego, zamie(cid:241)
miejscami z elementem osiowym.
Aby podzia(cid:239) za pomoc(cid:200) tych kroków by(cid:239) efektywny, skorzystamy z dwóch wska(cid:283)ników, z których
jeden b(cid:218)dzie wskazywa(cid:239) pierwszy element wi(cid:218)kszy ni(cid:285) element osiowy, a drugi pos(cid:239)u(cid:285)y do szu-
kania warto(cid:258)ci mniejszej ni(cid:285) warto(cid:258)(cid:202) elementu osiowego.
W kodzie z listingu 2.7 te wska(cid:283)niki do liczb ca(cid:239)kowitych nosz(cid:200) nazwy, odpowiednio, x oraz i.
Na pocz(cid:200)tku algorytm wybiera jako element osiowy ostatni element tablicy wej(cid:258)ciowej. Nast(cid:218)p-
nie za pomoc(cid:200) zmiennej i w pojedynczym przebiegu przetwarza tablic(cid:218) od lewej do prawej.
Je(cid:258)li element wskazywany obecnie przez i jest mniejszy ni(cid:285) element osiowy, to nast(cid:218)puje
inkrementacja zmiennej x oraz zamiana jej miejscami z i. Po zastosowaniu tej techniki zmienna x
wskazuje element wi(cid:218)kszy ni(cid:285) element osiowy albo ma t(cid:218) sam(cid:200) warto(cid:258)(cid:202) co zmienna i, a w tym
przypadku zamiana elementów nie zmodyfikuje tablicy. Po zako(cid:241)czeniu p(cid:218)tli wykonujemy
ostatni krok, zamieniaj(cid:200)c miejscami pierwszy element wi(cid:218)kszy od elementu osiowego z samym
elementem osiowym.
Listing 2.7. Podzia(cid:239) w sortowaniu szybkim. Nazwa klasy (cid:283)ród(cid:239)owej: QuickSort
private int partition(int[] numbers, int start, int end) {
int pivot = numbers[end];
int x = start - 1;
for (int i = start; i end; i++) {
if (numbers[i] pivot) {
x++;
swap(numbers, x, i);
}
}
swap(numbers, x + 1, end);
return x + 1;
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
43
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
(cid:109)wiczenie: Zrozumienie metody dziel(cid:200)cej
Scenariusz
Aby lepiej zrozumie(cid:202) metod(cid:218) dziel(cid:200)c(cid:200) zastosowan(cid:200) w listingu 2.7, przeanalizuj j(cid:200) krok po
kroku, korzystaj(cid:200)c z przyk(cid:239)adowych danych.
Cel
Zrozumienie, jak przebiega podzia(cid:239) Lomuto.
Kroki do wykonania
1. Uruchom w wyobra(cid:283)ni kod z listingu 2.7 dla ka(cid:285)dego elementu tablicy, zwi(cid:218)kszaj(cid:200)c
warto(cid:258)ci zmiennych x oraz i.
2. Wype(cid:239)nij tabel(cid:218) 2.1, przyjmuj(cid:200)c, (cid:285)e element osiowy jest ostatni na li(cid:258)cie,
czyli ma warto(cid:258)(cid:202) 16.
Tabela 2.1. Kroki procesu podzia(cid:239)u
i
-
0
1
2
3
4
5
6
tablica
[4, 5, 33, 17, 3, 21, 1, 16]
[4, 5, 33, 17, 3, 21, 1, 16]
[4, 5, 33, 17, 3, 21 1, 16]
[4, 5, 3, 17, 33, 21, 1, 16]
7
na koniec
[4, 5, 3, 1, 16, 21, 17, 33]
x
-1
0
1
2
3
Teraz na pewno rozumiesz, jak przebiega podzia(cid:239) w sortowaniu szybkim. W nast(cid:218)pnym punkcie
w(cid:239)(cid:200)czymy metod(cid:218) dziel(cid:200)c(cid:200) do ca(cid:239)ego algorytmu sortowania szybkiego.
Jak to wszystko posk(cid:239)ada(cid:202) razem
Sortowanie szybkie pochodzi z algorytmów typu „dziel i zwyci(cid:218)(cid:285)aj”. W tej ksi(cid:200)(cid:285)ce zobaczysz
wiele innych przyk(cid:239)adów algorytmów tej klasy, a metod(cid:200) „dziel i zwyci(cid:218)(cid:285)aj” zajmiemy si(cid:218) szcze-
gó(cid:239)owo w rozdziale 4., „Paradygmaty projektowania algorytmów”. Na razie wa(cid:285)ne jest, by pa-
mi(cid:218)ta(cid:202), (cid:285)e algorytmy typu „dziel i zwyci(cid:218)(cid:285)aj” dziel(cid:200) problem na coraz mniejsze cz(cid:218)(cid:258)ci, a(cid:285)
ich rozwi(cid:200)zanie stanie si(cid:218) banalne. Takie dzielenie mo(cid:285)na (cid:239)atwo zaimplementowa(cid:202) za pomoc(cid:200)
rekurencji.
44
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
W przypadku sortowania szybkiego dzielimy rekurencyjnie tablic(cid:218), dopóki problem nie stanie
si(cid:218) na tyle ma(cid:239)y, (cid:285)e b(cid:218)dzie si(cid:218) da(cid:239)o go (cid:239)atwo rozwi(cid:200)za(cid:202). Gdy tablica ma tylko jeden element,
rozwi(cid:200)zanie jest proste: tablica pozostaje niezmieniona, poniewa(cid:285) nie ma w niej nic do sortowa-
nia. Jest to warunek zatrzymania algorytmu rekurencyjnego. Je(cid:258)li tablica ma wi(cid:218)cej ni(cid:285) jeden
element, to nadal j(cid:200) dzielimy, korzystaj(cid:200)c z metody opracowanej w poprzednim punkcie.
Istnieje równie(cid:285) nierekurencyjny algorytm sortowania szybkiego, korzystaj(cid:200)cy ze struktury danych stosu, ale
jego napisanie jest nieco bardziej skomplikowane. Stosy i listy omówi(cid:218) w dalszej cz(cid:218)(cid:258)ci tego rozdzia(cid:239)u.
Listing 2.8 zawiera kompletny pseudokod sortowania szybkiego. Podobnie jak w wi(cid:218)kszo(cid:258)ci
funkcji rekurencyjnych, kod ten rozpoczyna si(cid:218) od sprawdzenia warunku zatrzymania. W tym
przypadku sprawdzamy, czy tablica ma co najmniej dwa elementy, upewniaj(cid:200)c si(cid:218), (cid:285)e pocz(cid:200)tkowy
wska(cid:283)nik tablicy jest mniejszy od ko(cid:241)cowego.
Listing 2.8. Pseudokod rekurencyjnego sortowania szybkiego
quickSort(array, start, end)
if(start end)
p = partition(array, start, end)
quickSort(array, start, p - 1)
quickSort(array, p + 1, end)
Je(cid:258)li tablica zawiera co najmniej dwa elementy, wywo(cid:239)ujemy metod(cid:218) dziel(cid:200)c(cid:200). Nast(cid:218)pnie,
u(cid:285)ywaj(cid:200)c ostatniej pozycji elementu osiowego (zwróconej przez metod(cid:218) dziel(cid:200)c(cid:200)), przy u(cid:285)yciu
sortowania szybkiego sortujemy rekurencyjnie lew(cid:200) cz(cid:218)(cid:258)(cid:202), a potem praw(cid:200).
W tym celu wywo(cid:239)ujemy ten sam kod sortowania szybkiego, korzystaj(cid:200)c ze wska(cid:283)ników
(start, p – 1) i (p + 1, end), bez uwzgl(cid:218)dnienia p, czyli pozycji elementu osiowego.
Aby zrozumie(cid:202) dzia(cid:239)anie sortowania szybkiego, warto u(cid:258)wiadomi(cid:202) sobie, (cid:285)e po wywo(cid:239)aniu
metody dziel(cid:200)cej nie trzeba ju(cid:285) przenosi(cid:202) elementu znajduj(cid:200)cego si(cid:218) na zwróconej pozycji
(elementu osiowego). Dzieje si(cid:218) tak dlatego, (cid:285)e wszystkie elementy po prawej stronie s(cid:200) wi(cid:218)ksze,
a po lewej mniejsze, wi(cid:218)c element osiowy znajduje si(cid:218) w prawid(cid:239)owej pozycji ko(cid:241)cowej.
Implementacja sortowania szybkiego
Aby zaimplementowa(cid:202) sortowanie szybkie w Javie, wykonaj nast(cid:218)puj(cid:200)ce kroki:
1. Zaimplementuj w Javie pseudokod z listingu 2.8, wywo(cid:239)uj(cid:200)c metod(cid:218) dziel(cid:200)c(cid:200)
pokazan(cid:200) na listingu 2.7.
2. Rekurencyjna implementacja w Javie korzystaj(cid:200)ca z opracowanej w poprzednim
punkcie metody dziel(cid:200)cej pokazana jest na listingu 2.9.
45
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
Listing 2.9. Sposób implementacji sortowania szybkiego. Nazwa klasy (cid:283)ród(cid:239)owej: QuickSort
private void sort(int[] numbers, int start, int end) {
if (start end) {
int p = partition(numbers, start, end);
sort(numbers, start, p - 1);
sort(numbers, p + 1, end);
}
}
W tym punkcie opisa(cid:239)em algorytm sortowania szybkiego, znacznie wydajniejszy ni(cid:285) algorytm
sortowania b(cid:200)belkowego, który pokaza(cid:239)em wcze(cid:258)niej. Przeci(cid:218)tnie algorytm ten wykonuje si(cid:218)
w czasie O(n log n), co stanowi ogromn(cid:200) popraw(cid:218) w stosunku do sortowania b(cid:200)belkowego, którego
z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasowa wynosi O(n(cid:21)). Jednak w przypadku pesymistycznym algorytm sortowania
szybkiego nadal dzia(cid:239)a w czasie O(n(cid:21)). O tym, jakie dane wej(cid:258)ciowe s(cid:200) najgorsze, decyduje zasto-
sowany schemat podzia(cid:239)u. W omówionym w tym podrozdziale schemacie Lomuto przypadek
pesymistyczny zachodzi wtedy, gdy dane wej(cid:258)ciowe s(cid:200) ju(cid:285) posortowane. W nast(cid:218)pnym podroz-
dziale przeanalizujemy inny algorytm sortowania, którego czas wykonania w przypadku pesymi-
stycznym wynosi O(n log n).
Korzystanie z sortowania przez scalanie
Chocia(cid:285) sortowanie szybkie w przypadku oczekiwanym jest do(cid:258)(cid:202) wydajne, wci(cid:200)(cid:285) ma teore-
tyczn(cid:200) pesymistyczn(cid:200) z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasow(cid:200) O (n(cid:21)). W tym podrozdziale poddamy analizie inny
algorytm sortowania, zwany sortowaniem przez scalanie, którego pesymistyczna z(cid:239)o(cid:285)ono(cid:258)(cid:202)
czasowa wynosi O(n log n). Podobnie jak sortowanie szybkie, sortowanie przez scalanie nale(cid:285)y do
algorytmów typu „dziel i zwyci(cid:218)(cid:285)aj”.
Sortowanie przez scalanie mo(cid:285)na stre(cid:258)ci(cid:202) w trzech prostych krokach:
1. podziel tablic(cid:218) na (cid:258)rodku;
2. rekurencyjnie sortuj ka(cid:285)d(cid:200) cz(cid:218)(cid:258)(cid:202) osobno;
3. po(cid:239)(cid:200)cz dwie posortowane cz(cid:218)(cid:258)ci.
W nast(cid:218)pnym punkcie b(cid:218)dziemy stopniowo opracowywa(cid:202) powy(cid:285)sze kroki, by coraz lepiej zro-
zumie(cid:202) dzia(cid:239)anie sortowania przez scalanie.
Chocia(cid:285) sortowanie przez scalanie jest teoretycznie wydajniejsze ni(cid:285) sortowanie szybkie, w praktyce
niektóre implementacje sortowania szybkiego s(cid:200) bardziej efektywne. Poza tym sortowanie przez scalanie ma
z(cid:239)o(cid:285)ono(cid:258)(cid:202) pami(cid:218)ciow(cid:200) O(n), w przeciwie(cid:241)stwie do sortowania szybkiego, którego z(cid:239)o(cid:285)ono(cid:258)(cid:202) pami(cid:218)ciowa
wynosi O(log n).
46
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
Dzielenie problemu
W poprzedniej sekcji pokaza(cid:239)em, jak u(cid:285)y(cid:202) techniki rekurencyjnej, by podzieli(cid:202) problem na wiele
mniejszych, a(cid:285) stan(cid:200) si(cid:218) (cid:239)atwe do rozwi(cid:200)zania. W sortowaniu przez scalanie korzysta si(cid:218) z tego
samego podej(cid:258)cia. Przypadek bazowy naszej rekurencji jest taki sam jak w sortowaniu szybkim.
Zachodzi wówczas, gdy tablica ma tylko jeden element, bo wtedy jest ju(cid:285) posortowana.
Na rysunku 2.3 zosta(cid:239) pokazany podzia(cid:239) tablicy w sortowaniu przez scalanie. W ka(cid:285)dym kroku
znajdujemy punkt (cid:258)rodkowy tablicy i dzielimy j(cid:200) na dwie cz(cid:218)(cid:258)ci. Nast(cid:218)pnie rekurencyjnie
sortujemy osobno lew(cid:200) i praw(cid:200) cz(cid:218)(cid:258)(cid:202) rozdzielonej tablicy. Wywo(cid:239)anie rekurencyjne zatrzy-
mujemy, gdy suma elementów do posortowania b(cid:218)dzie równa warto(cid:258)ci pokazanej na rysunku.
Rysunek 2.3. Etapy podzia(cid:239)u w algorytmie sortowania przez scalanie
Implementacja sortowania przez scalanie
Uzupe(cid:239)nijmy pseudokod algorytmu sortowania przez scalanie.
Maj(cid:200)c na uwadze, (cid:285)e rekurencyjna cz(cid:218)(cid:258)(cid:202) sortowania przez scalanie jest bardzo podobna do algo-
rytmu sortowania szybkiego z poprzedniego podrozdzia(cid:239)u, uzupe(cid:239)nij pseudokod pokazany na
listingu 2.10.
Listing 2.10. (cid:109)wiczenie w uzupe(cid:239)nianiu pseudokodu rekurencyjnego sortowania przez scalanie
mergeSort(array, start, end)
if(_____________)
midPoint = _________
mergeSort(array, _____, _____)
mergeSort(array, _____, _____)
merge(array, start, midPoint, end)
Pseudokod sortowania przez scalanie mo(cid:285)na uzupe(cid:239)ni(cid:202) w sposób pokazany na listingu 2.11.
Listing 2.11. Sposób uzupe(cid:239)nienia pseudokodu sortowania przez scalanie
mergeSort(array, start, end)
if(start end)
47
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
midPoint = (end - start) / 2 + start
mergeSort(array, start, midPoint)
mergeSort(array, midPoint + 1, start)
merge(array, start, midPoint, end)
Algorytm sortowania przez scalanie nale(cid:285)y do tej samej klasy algorytmów co sortowanie szybkie,
jednak jego z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasowa i pami(cid:218)ciowa jest inna. Zamiast dzieli(cid:202) tablic(cid:218) wzgl(cid:218)dem ele-
mentu osiowego, sortowanie przez scalanie zawsze dzieli tablic(cid:218) w punkcie (cid:258)rodkowym. Jest to
proces podobny do wyszukiwania binarnego, a jego wynikiem jest log2n podzia(cid:239)ów tablic. W na-
st(cid:218)pnym punkcie przedstawi(cid:218) cz(cid:218)(cid:258)(cid:202) scalaj(cid:200)c(cid:200) tego algorytmu, (cid:239)(cid:200)cz(cid:200)c(cid:200) dwa ró(cid:285)ne fragmenty
podzielonej tablicy w jeden posortowany.
Scalanie problemu
Jak scali(cid:202) dwie posortowane listy w jedn(cid:200)? Dokonuje tego funkcja merge(), znajduj(cid:200)ca si(cid:218) na
ko(cid:241)cu pseudokodu pokazanego w poprzednim punkcie. Proces ten pokaza(cid:239)em na rysunku 2.4.
Scalenie dwóch posortowanych list jest (cid:239)atwiejsze ni(cid:285) sortowanie od podstaw.
Rysunek 2.4. Przed scaleniem i po scaleniu dwóch posortowanych tablic
Podobnie by(cid:239)o w przypadku problemu znajdowania cz(cid:218)(cid:258)ci wspólnej zbiorów, przedstawionego
w rozdziale 1., „Algorytmy i ich z(cid:239)o(cid:285)ono(cid:258)(cid:202)”.
Scalanie mo(cid:285)emy wykona(cid:202) w czasie liniowym, wykorzystuj(cid:200)c tylko dwa wska(cid:283)niki i pust(cid:200)
tablic(cid:218), co zosta(cid:239)o pokazane na rysunku 2.4.
Poniewa(cid:285) oba fragmenty podzielonej tablicy s(cid:200) posortowane, (cid:239)atwo jest je scali(cid:202). Szukaj(cid:200)c analogii,
warto przypomnie(cid:202) sobie, (cid:285)e problem znajdowania cz(cid:218)(cid:258)ci wspólnej zbiorów przedstawiony w rozdziale 1.,
„Algorytmy i ich z(cid:239)o(cid:285)ono(cid:258)(cid:202)”, sta(cid:239) si(cid:218) du(cid:285)o (cid:239)atwiejszy, gdy obie tablice wej(cid:258)ciowe zosta(cid:239)y posortowane.
Podobny algorytm stosuje si(cid:218) tak(cid:285)e tutaj.
Pseudokod scalania jest pokazany na listingu 2.12. W kodzie tym funkcja copyArray() pobiera
tablic(cid:218) (cid:283)ród(cid:239)ow(cid:200) b(cid:218)d(cid:200)c(cid:200) pierwszym argumentem i kopiuje j(cid:200) do tablicy docelowej, czyli do
drugiego argumentu. Zmienna start wskazuje, w którym miejscu tablicy docelowej umie(cid:258)ci(cid:202)
pierwszy element tablicy (cid:283)ród(cid:239)owej.
48
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
Listing 2.12. Pseudokod scalania w sortowaniu przez scalanie
merge(array, start, middle, end)
i = start
j = middle + 1
arrayTemp = initArrayOfSize(end - start + 1)
for (k = 0 until end-start)
if (i = middle (j end || array[i] = array[j]))
arrayTemp[k] = array[i]
i++
else
arrayTemp[k] = array[j]
j++
copyArray(arrayTemp, array, start)
W cz(cid:218)(cid:258)ci scalaj(cid:200)cej sortowania przez scalanie tworzymy tymczasow(cid:200) tablic(cid:218) o wielko(cid:258)ci równej
(cid:239)(cid:200)cznemu rozmiarowi dwóch fragmentów tablicy pocz(cid:200)tkowej. Nast(cid:218)pnie wykonujemy pojedyn-
cze przej(cid:258)cie po tej tablicy, wype(cid:239)niaj(cid:200)c ka(cid:285)dy kolejny element kolejn(cid:200) najmniejsz(cid:200) warto(cid:258)ci(cid:200)
z dwóch list wej(cid:258)ciowych (reprezentowanych przez wska(cid:283)niki start, middle i end). Po wybraniu
elementu z jednej z list przesuwamy wska(cid:283)nik tej listy i powtarzamy to dzia(cid:239)anie a(cid:285) do zako(cid:241)-
czenia scalania.
W j(cid:218)zyku Java istnieje wiele narz(cid:218)dzi, których mo(cid:285)na u(cid:285)y(cid:202) do zaimplementowania funkcji copyArray()
pokazanej na ko(cid:241)cu listingu 2.12. Mo(cid:285)emy samodzielnie zaimplementowa(cid:202) funkcj(cid:218) copy(), korzystaj(cid:200)c
z p(cid:218)tli for. Mo(cid:285)na te(cid:285) u(cid:285)y(cid:202) strumieni Javy i zapisa(cid:202) kopi(cid:218) tablicy w jednym wierszu kodu. Bodaj najprost-
szym sposobem jest skorzystanie z funkcji System.arrayCopy().
Sortowanie przez scalanie to teoretycznie jeden z najszybszych algorytmów sortowania. Nie-
stety zu(cid:285)ywa ono przez to nieco wi(cid:218)cej pami(cid:218)ci, chocia(cid:285) istniej(cid:200) implementacje, które w celu
zaoszcz(cid:218)dzenia pami(cid:218)ci dokonuj(cid:200) scalania w miejscu.
Dla porównania w tabeli 2.2 przedstawiam kilka technik sortowania oraz ich z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasow(cid:200)
i pami(cid:218)ciow(cid:200).
Tabela 2.2. Algorytmy sortowania
Algorytm
sortowania
b(cid:200)belkowe
przez wybieranie
przez wstawianie
szybkie
przez scalanie
przez kopcowanie
Przypadek
przeci(cid:218)tny
O(n (cid:21))
O(n (cid:21))
O(n (cid:21))
O(n log n)
O(n log n)
O(n log n)
Przypadek
pesymistyczny
Pami(cid:218)(cid:202)
Stabilno(cid:258)(cid:202)
O(n (cid:21))
O(n (cid:21))
O(n (cid:21))
O(n (cid:21))
O(n log n)
O(n log n)
O(1)
O(1)
O(1)
O(1)
O(n)
O(1)
stabilne
niestabilne
stabilne
niestabilne
stabilne
niestabilne
49
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
(cid:109)wiczenie: Implementacja sortowania przez scalanie w j(cid:218)zyku Java
Scenariusz
Sortowanie przez scalanie jest jedn(cid:200) z najszybszych technik sortowania. Korzysta z niego
wiele do(cid:239)(cid:200)czanych bibliotek i interfejsów API. W tym (cid:202)wiczeniu napiszemy w Javie algorytm
sortuj(cid:200)cy w ten sposób tablic(cid:218).
Cel
Wykorzystanie pseudokodu pokazanego w tym punkcie do implementacji pe(cid:239)nego algorytmu
sortowania przez scalanie w j(cid:218)zyku Java.
Warunki wst(cid:218)pne
Aby wykona(cid:202) to (cid:202)wiczenie, zaimplementuj metody znajduj(cid:200)ce si(cid:218) w klasie dost(cid:218)pnej w repozy-
torium do(cid:239)(cid:200)czonym do tej ksi(cid:200)(cid:285)ki pod adresem src/main/java/com/packt/datastructuresandalg/
lesson2/activity/mergesort/MergeSort.java
Je(cid:258)li skonfigurowa(cid:239)e(cid:258) projekt, testy jednostkowe do tego (cid:202)wiczenia uruchomisz nast(cid:218)puj(cid:200)cym poleceniem:
gradlew test --tests com.packt.datastructuresandalg.lesson2.activity.mergesort*
Kroki do wykonania
1. Rozpocznij od implementacji metody mergeSort, która dzieli tablic(cid:218) na dwie
cz(cid:218)(cid:258)ci, sortuje je obie rekurencyjnie i scala wyniki.
2. Nast(cid:218)pnie zaimplementuj metod(cid:218) merge, scalaj(cid:200)c(cid:200) oba fragmenty podzielonej
tablicy w innym miejscu.
3. Po zako(cid:241)czeniu scalania skopiuj now(cid:200) tablic(cid:218) z powrotem do tablicy wej(cid:258)ciowej.
Rozpocz(cid:218)cie pracy z podstawowymi
strukturami danych
Struktury danych pozwalaj(cid:200) uporz(cid:200)dkowa(cid:202) dane w taki sposób, by by(cid:239)y efektywnie dost(cid:218)pne
podczas rozwi(cid:200)zywania problemu. Wybór odpowiedniej struktury danych zale(cid:285)y od typu pro-
blemu do rozwi(cid:200)zania (który okre(cid:258)la sposób dost(cid:218)pu do danych), ilo(cid:258)ci danych, które nale(cid:285)y
uporz(cid:200)dkowa(cid:202), oraz no(cid:258)nika u(cid:285)ywanego do przechowywania danych (pami(cid:218)(cid:202), dysk i tak dalej).
Mia(cid:239)e(cid:258) ju(cid:285) okazj(cid:218) zobaczy(cid:202) jedn(cid:200) ze struktur danych i jej u(cid:285)ywa(cid:202). W poprzednich podrozdzia-
(cid:239)ach cz(cid:218)sto korzystali(cid:258)my z tablic. S(cid:200) one najprostszymi strukturami. Zapewniaj(cid:200) dost(cid:218)p do danych
za pomoc(cid:200) indeksu i maj(cid:200) ustalony rozmiar (bywaj(cid:200) nazywane równie(cid:285) strukturami statycznymi).
Stanowi(cid:200) przeciwie(cid:241)stwo innych, dynamicznych struktur danych, które mo(cid:285)na powi(cid:218)ksza(cid:202),
zapewniaj(cid:200)c wi(cid:218)cej miejsca na dane, kiedy tylko zajdzie taka potrzeba.
50
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
Wprowadzenie do struktur danych
Formalnie rzecz bior(cid:200)c, struktura danych to organizacja elementów danych — zbiór funkcji, które
mo(cid:285)na zastosowa(cid:202) do tych danych (takich jak dodawanie, usuwanie i wyszukiwanie), oraz wszel-
kie powi(cid:200)zania mi(cid:218)dzy ró(cid:285)nymi elementami. Tabela 2.3 przedstawia typowe operacje wyko-
nywane na strukturach danych.
Tabela 2.3. Niektóre typowe operacje na strukturach danych
Operacja
Typ
Opis
search(klucz)
niemodyfikuj(cid:200)ca
size()
niemodyfikuj(cid:200)ca
add(warto(cid:258)(cid:202))
update(klucz,
warto(cid:258)(cid:202))
delete(warto(cid:258)(cid:202))
minimum()
modyfikuj(cid:200)ca
modyfikuj(cid:200)ca
modyfikuj(cid:200)ca
niemodyfikuj(cid:200)ca
maximum()
niemodyfikuj(cid:200)ca
Operacja, która po podaniu klucza do okre(cid:258)lonej
warto(cid:258)ci zwraca t(cid:218) warto(cid:258)(cid:202), je(cid:258)li mo(cid:285)na j(cid:200) znale(cid:283)(cid:202)
w strukturze
Ca(cid:239)kowita liczba warto(cid:258)ci przechowywanych
w strukturze danych
Wstawia warto(cid:258)(cid:202) do struktury danych
Aktualizuje istniej(cid:200)c(cid:200) pozycj(cid:218), korzystaj(cid:200)c
z podanego klucza i warto(cid:258)ci
Usuwa element ze struktury danych
Operacja obs(cid:239)ugiwana tylko przez uporz(cid:200)dkowane
struktury danych, zwracaj(cid:200)ca warto(cid:258)(cid:202) najmniejszego
klucza
Operacja obs(cid:239)ugiwana tylko przez uporz(cid:200)dkowane
struktury danych, zwracaj(cid:200)ca warto(cid:258)(cid:202) najwi(cid:218)kszego
klucza
W tym podrozdziale zobaczysz ró(cid:285)nego typu dynamiczne struktury danych. Zaczniemy od list
powi(cid:200)zanych, które s(cid:200) zoptymalizowane pod k(cid:200)tem dynamicznego zwi(cid:218)kszania wielko(cid:258)ci, ale
wyszukiwanie w nich jest powolne. Potem na bazie list zaimplementujemy inne struktury
danych, takie jak kolejki i stosy.
Struktura list powi(cid:200)zanych
Lista powi(cid:200)zana to lista elementów, z których ka(cid:285)dy zawiera jedynie informacje o nast(cid:218)pnym
elemencie listy, je(cid:258)li taki istnieje. Rysunek 2.5 pokazuje przyk(cid:239)ad takiej listy. Ka(cid:285)de pole na ry-
sunku reprezentuje pojemnik na element danych, który mamy przechowywa(cid:202). Ten pojemnik,
zwany w(cid:218)z(cid:239)em, zawiera warto(cid:258)ci naszych danych i wska(cid:283)nik do nast(cid:218)pnego w(cid:218)z(cid:239)a listy. Jak wida(cid:202)
na rysunku, w(cid:218)ze(cid:239) z pocz(cid:200)tku listy jest nazywany g(cid:239)ow(cid:200) (ang. head), a ostatni element listy
— ogonem (ang. tail).
Dla u(cid:239)atwienia dost(cid:218)pu do tych w(cid:218)z(cid:239)ów struktura danych przechowuje do nich oddzielne
wska(cid:283)niki.
51
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
Rysunek 2.5. Przyk(cid:239)ad listy powi(cid:200)zanej
Zalet(cid:200) korzystania z listy powi(cid:200)zanej, w przeciwie(cid:241)stwie do tablicy, jest mo(cid:285)liwo(cid:258)(cid:202) dynamicznego
zwi(cid:218)kszania wielko(cid:258)ci. Przy korzystaniu z tablicy miejsce alokuje si(cid:218) na pocz(cid:200)tku i pozostaje
ono sta(cid:239)e. Przydzielenie na ni(cid:200) zbyt du(cid:285)o miejsca, które pozostanie niewykorzystane, to marno-
trawstwo zasobów. Z drugiej strony, je(cid:258)li tablica jest zbyt ma(cid:239)a, dane mog(cid:200) si(cid:218) w niej nie zmie-
(cid:258)ci(cid:202). Natomiast w przypadku listy powi(cid:200)zanej miejsce nie jest ustalone. Struktura ta powi(cid:218)ksza
si(cid:218) dynamicznie w miar(cid:218) dodawania danych i zmniejsza si(cid:218) podczas ich usuwania, zwalniaj(cid:200)c
miejsce w pami(cid:218)ci.
U(cid:285)ywaj(cid:200)c j(cid:218)zyka obiektowego, takiego jak Java, stwórzmy model listy powi(cid:200)zanej z wykorzysta-
niem oddzielnych, po(cid:239)(cid:200)czonych ze sob(cid:200) instancji w(cid:218)z(cid:239)ów. Listing 2.13 przedstawia, jak odwzo-
rowa(cid:202) w(cid:218)ze(cid:239) listy w klasie Javy.
Listing 2.13. Klasa w(cid:218)z(cid:239)a listy powi(cid:200)zanej (dla zwi(cid:218)z(cid:239)o(cid:258)ci pomini(cid:218)to akcesory i mutatory).
Nazwa klasy (cid:283)ród(cid:239)owej: Linkedlistnode
public class LinkedListNode V {
private V value;
private LinkedListNode V next;
public LinkedListNode(V value, LinkedListNode V next) {
this.value = value;
this.next = next;
}
public Optional LinkedListNode V getNext() {
return Optional.ofNullable(next);
}
}
Klasa ta zawiera samoreferencj(cid:218), co pozwala po(cid:239)(cid:200)czy(cid:202) wiele w(cid:218)z(cid:239)ów w list(cid:218), jak pokaza(cid:239)em
w rysunku 2.5.
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
Zwró(cid:202) uwag(cid:218) na to, (cid:285)e do wskazania nast(cid:218)pnego w(cid:218)z(cid:239)a u(cid:285)ywamy obiektów klasy Optional
j(cid:218)zyka Java, co pozwala unikn(cid:200)(cid:202) zwracania pustych wska(cid:283)ników. W w(cid:218)(cid:283)le ko(cid:241)cowym listy
powi(cid:200)zanej obiekt taki jest zawsze pusty. Do modelowania przechowywanych danych wykorzy-
stujemy z kolei typy generyczne. W ten sposób zachowujemy struktur(cid:218) tak ogóln(cid:200), jak to tylko
mo(cid:285)liwe, przechowuj(cid:200)c(cid:200) dane dowolnego typu.
52
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
Klasa Optional, wprowadzona w 8. wersji j(cid:218)zyka Java do reprezentacji warto(cid:258)ci opcjonalnych, pozwala
unikn(cid:200)(cid:202) u(cid:285)ywania warto(cid:258)ci null.
Przekszta(cid:239)cenie listy powi(cid:200)zanej na list(cid:218) powi(cid:200)zan(cid:200) dwukierunkowo
W j(cid:218)zyku Java zmodyfikujemy klas(cid:218) w(cid:218)z(cid:239)a w celu obs(cid:239)ugi listy dwukierunkowej.
Lista dwukierunkowa to lista, w której ka(cid:285)dy w(cid:218)ze(cid:239) zawiera odniesienia do nast(cid:218)pnego i poprzed-
niego w(cid:218)z(cid:239)a. Spróbuj zmodyfikowa(cid:202) kod z listingu 2.13 tak, by obs(cid:239)ugiwa(cid:239) list(cid:218) dwukierunkow(cid:200).
Rozwi(cid:200)zanie przedstawia listing 2.14.
Listing 2.14. Klasa w(cid:218)z(cid:239)a listy dwukierunkowej (dla zwi(cid:218)z(cid:239)o(cid:258)ci pomini(cid:218)to akcesory i mutatory).
Nazwa klasy (cid:283)ród(cid:239)owej: Dbllinkedlistnode
public class DblLinkedListNode V {
private V value;
private DblLinkedListNode V next;
private DblLinkedListNode V previous;
public DblLinkedListNode(V value,
DblLinkedListNode V next,
DblLinkedListNode V previous) {
this.value = value;
this.next = next;
this.previous = previous;
}
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip. W li(cid:258)cie dwukierunkowej w(cid:218)ze(cid:239) pocz(cid:200)tkowy ma pusty wska(cid:283)nik do poprzednika, a w(cid:218)ze(cid:239) ko(cid:241)-
cowy ma pusty wska(cid:283)nik do nast(cid:218)pnika.
W tym podpunkcie pokaza(cid:239)em, jak modelowa(cid:202) w(cid:218)ze(cid:239) listy powi(cid:200)zanej za pomoc(cid:200) klas, typów ge-
nerycznych i obiektów Optional. W nast(cid:218)pnym podpunkcie zobaczysz, jak zaimplementowa(cid:202)
operacje na li(cid:258)cie.
Operacje na listach powi(cid:200)zanych
Zanim b(cid:218)dziesz móg(cid:239) dokonywa(cid:202) operacji na li(cid:258)cie powi(cid:200)zanej, musisz zainicjalizowa(cid:202) t(cid:218) struk-
tur(cid:218) danych i oznaczy(cid:202) j(cid:200) jako pust(cid:200). Koncepcyjnie jest to sytuacja, gdy wska(cid:283)nik do pocz(cid:200)tku
listy nic nie wskazuje. Dodamy t(cid:218) logik(cid:218) do konstruktora w j(cid:218)zyku Java.
Pokazuje to listing 2.15. Zauwa(cid:285), (cid:285)e po raz kolejny w celu przechowania w li(cid:258)cie elementów do-
wolnego typu korzystamy z typów generycznych:
53
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
Listing 2.15. Inicjalizowanie listy powi(cid:200)zanej za pomoc(cid:200) konstruktora. Nazwa klasy (cid:283)ród(cid:239)owej: Linkedlist
public class LinkedList V {
private LinkedListNode V head;
public LinkedList() {
head = null;
}
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
Jak dodawa(cid:202) elementy na pocz(cid:200)tku listy i usuwa(cid:202) je stamt(cid:200)d? Dodanie w(cid:218)z(cid:239)a do listy powi(cid:200)za-
nej wymaga ponownego przypisania dwóch wska(cid:283)ników. W nowym w(cid:218)(cid:283)le wska(cid:283)nikowi do
nast(cid:218)pnika przypisuje si(cid:218) t(cid:218) sam(cid:200) warto(cid:258)(cid:202), któr(cid:200) ma wska(cid:283)nik do g(cid:239)owy. Potem wska(cid:283)nik do g(cid:239)owy
nale(cid:285)y ustawi(cid:202) tak, by wskazywa(cid:239) nowo utworzony w(cid:218)ze(cid:239). Proces ten zosta(cid:239) pokazany na ry-
sunku 2.6. Usuni(cid:218)cie elementu z pocz(cid:200)tku listy to proces odwrotny. Wska(cid:283)nik do g(cid:239)owy nale(cid:285)y
ustawi(cid:202) na nast(cid:218)pnik dotychczasowego w(cid:218)z(cid:239)a pocz(cid:200)tkowego. Dla porz(cid:200)dku w w(cid:218)(cid:283)le pocz(cid:200)tko-
wym wska(cid:283)nikowi do nast(cid:218)pnika mo(cid:285)na nada(cid:202) warto(cid:258)(cid:202) pust(cid:200).
Rysunek 2.6. Dodawanie w(cid:218)z(cid:239)a na pocz(cid:200)tku listy
Aby zlokalizowa(cid:202) element na li(cid:258)cie, przechodzimy przez ni(cid:200), dopóki nie znajdziemy poszukiwa-
nego elementu lub nie dojdziemy do jej ko(cid:241)ca. Mo(cid:285)emy tego dokona(cid:202) w prosty sposób, zaczy-
naj(cid:200)c od pocz(cid:200)tku listy i pod(cid:200)(cid:285)aj(cid:200)c ci(cid:200)gle za wska(cid:283)nikiem do nast(cid:218)pnego w(cid:218)z(cid:239)a, a(cid:285) znajdziemy
w(cid:218)ze(cid:239) z poszukiwan(cid:200) warto(cid:258)ci(cid:200), albo ich zabraknie, czyli wska(cid:283)nik do nast(cid:218)pnego w(cid:218)z(cid:239)a
b(cid:218)dzie pusty.
Na listingu 2.16 pokaza(cid:239)em operacje dodawania w(cid:218)z(cid:239)a na pocz(cid:200)tku listy powi(cid:200)zanej [ addFront()]
i usuwania w(cid:218)z(cid:239)a z pocz(cid:200)tku listy [deleteFront()]. W przypadku metody addFront() tworzymy
nowy w(cid:218)ze(cid:239), a jego wska(cid:283)nikowi do nast(cid:218)pnika przypisujemy bie(cid:285)(cid:200)c(cid:200) warto(cid:258)(cid:202) wska(cid:283)nika do
g(cid:239)owy. Nast(cid:218)pnie ustawiamy nowy w(cid:218)ze(cid:239) jako g(cid:239)ow(cid:218). Zwró(cid:202) uwag(cid:218), (cid:285)e w metodzie usuwaj(cid:200)cej
korzystamy z obiektów Optional j(cid:218)zyka Java. Je(cid:258)li wska(cid:283)nik do g(cid:239)owy ma warto(cid:258)(cid:202) null, takim
pozostaje i nic nie zmieniamy. W przeciwnym razie przekszta(cid:239)camy go na pierwszy wska(cid:283)nik
do nast(cid:218)pnika. Wreszcie w w(cid:218)(cid:283)le pocz(cid:200)tkowym wska(cid:283)nikowi do nast(cid:218)pnika nadajemy warto(cid:258)(cid:202)
null. Ten ostatni krok nie jest konieczny, poniewa(cid:285) osierocony w(cid:218)ze(cid:239) zostanie zebrany podczas
od(cid:258)miecania, jednak uwzgl(cid:218)dnimy go w celu zachowania kompletno(cid:258)ci.
54
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
Listing 2.16. Dodawanie i usuwanie na pocz(cid:200)tku listy powi(cid:200)zanej. Nazwa klasy (cid:283)ród(cid:239)owej: Linkedlist
public void addFront(V item) {
this.head = new LinkedListNode (item, head);
}
public void deleteFront() {
Optional LinkedListNode V firstNode = Optional.
ofNullable(this.head);
this.head = firstNode.flatMap(LinkedListNode::getNext).
orElse(null);
firstNode.ifPresent(n - n.setNext(null));
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
Na listingu 2.17 pokaza(cid:239)em jeden ze sposobów implementacji metody wyszukuj(cid:200)cej. Tu znów
mo(cid:285)na zaobserwowa(cid:202), jak korzysta(cid:202) w Javie z metod klasy Optional. P(cid:218)tl(cid:218) while rozpoczynamy
od wska(cid:283)nika do g(cid:239)owy i je(cid:258)li bie(cid:285)(cid:200)cy w(cid:218)ze(cid:239) nie zawiera poszukiwanego elementu, przechodzimy
dalej do nast(cid:218)pnego w(cid:218)z(cid:239)a, o ile taki istnieje. Nast(cid:218)pnie zwracamy ostatni wska(cid:283)nik, w którym
mo(cid:285)e by(cid:202) pusty obiekt klasy Optional albo w(cid:218)ze(cid:239) zawieraj(cid:200)cy dopasowanie.
Listing 2.17. Dodawanie i usuwanie na pocz(cid:200)tku listy powi(cid:200)zanej. Nazwa klasy (cid:283)ród(cid:239)owej: Linkedlist
public Optional LinkedListNode V find(V item) {
Optional LinkedListNode V node = Optional.ofNullable(this.head);
while (node.filter(n - n.getValue() != item).isPresent()) {
node = node.flatMap(LinkedListNode::getNext);
}
return node;
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip. Metoda find() na li(cid:258)cie powi(cid:200)zanej ma pesymistyczn(cid:200) z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasow(cid:200) rz(cid:218)du O(n).
Dzieje si(cid:218) tak, gdy pasuj(cid:200)cy element jest na ko(cid:241)cu listy lub nie ma go w niej w ogóle.
W poprzednim przyk(cid:239)adzie pokaza(cid:239)em, jak doda(cid:202) element na pocz(cid:200)tku listy powi(cid:200)zanej. A jak
wstawi(cid:202) go do listy w dowolnie wybranym punkcie? Rysunek 2.7 przedstawia, jak to zrobi(cid:202)
w dwóch krokach.
Jak to zrobi(cid:202), pokazuje listing 2.18. Jest to metoda Javy o nazwie addAfter(), pobieraj(cid:200)ca w(cid:218)ze(cid:239)
i element do wstawienia. Metoda ta dodaje w(cid:218)ze(cid:239) zawieraj(cid:200)cy element po w(cid:218)(cid:283)le podanym
w argumencie aNode. Implementacja przebiega zgodnie z krokami pokazanymi na rysunku 2.7.
55
Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku Java
Rysunek 2.7. Dodawanie w(cid:218)z(cid:239)a na dowolnej pozycji listy
Listing 2.18. Przyk(cid:239)adowa metoda addAfter. Nazwa klasy (cid:283)ród(cid:239)owej: Linkedlist
public void addAfter(LinkedListNode V aNode, V item) {
aNode.setNext(new LinkedListNode (item, aNode.getNext().orElse(null)));
}
Kod tego przyk(cid:239)adu znajdziesz w archiwum, które mo(cid:285)esz pobra(cid:202) pod adresem ftp://ftp.helion.pl/przyklady/
sdalgj.zip.
(cid:109)wiczenie: Przechodzenie przez list(cid:218) powi(cid:200)zan(cid:200)
Scenariusz
Maj(cid:200)c list(cid:218) powi(cid:200)zan(cid:200), która zawiera kilka elementów, mamy zbudowa(cid:202) (cid:239)a(cid:241)cuch o postaci
[3,6,4,2,4]. Je(cid:258)li lista jest pusta, nale(cid:285)y wypisa(cid:202) [].
Cel
Napisa(cid:202) w Javie kod przechodz(cid:200)cy przez list(cid:218) powi(cid:200)zan(cid:200).
Kroki do wykonania
1. Do klasy LinkedList dopisz metod(cid:218) toString():
public String toString() {
}
2. W p(cid:218)tli while przejd(cid:283) przez list(cid:218) powi(cid:200)zan(cid:200).
W tym punkcie pokaza(cid:239)em, jak zaimplementowa(cid:202) ró(cid:285)ne operacje na li(cid:258)cie powi(cid:200)zanej. Ta struk-
tura danych b(cid:218)dzie podstaw(cid:200), któr(cid:200) wykorzystamy do modelowania kolejek i stosów. Listy
powi(cid:200)zane b(cid:218)d(cid:200) te(cid:285) cz(cid:218)sto stosowane w bardziej zaawansowanych algorytmach w dalszej
cz(cid:218)(cid:258)ci ksi(cid:200)(cid:285)ki.
56
Poleć książkęKup książkę Rozdzia(cid:225) 2. • Algorytmy sortowania i podstawowe struktury danych
Kolejki
Kolejki s(cid:200) abstrakcyjnymi strukturami danych maj(cid:200)cymi na(cid:258)ladowa(cid:202) dzia(cid:239)anie prawdziwych
kolejek. Maj(cid:200) ró(cid:285)norodne zastosowania, mi(cid:218)dzy innymi przydzielanie zasobów, planowanie,
sortowanie i wiele innych Zazwyczaj implementuje si(cid:218) je przy u(cid:285)yciu listy dwukierunkowej,
chocia(cid:285) istniej(cid:200) inne sposoby. Kolejka umo(cid:285)liwia zwykle dwie operacje: operacj(cid:218) ustawiania
(ang. enqueue), czyli dodawania elementów na ko(cid:241)cu kolejki, oraz przeciwstawn(cid:200) operacj(cid:218)
od(cid:239)(cid:200)czania (ang. dequeue), w której elementy s(cid:200) usuwane z pocz(cid:200)tku kolejki. Na tych dwóch
operacjach opiera si(cid:218) zasada dzia(cid:239)ania tej struktury danych, okre(cid:258)lana po angielsku jako First
In First Out (FIFO — z ang. pierwszy na wej(cid:258)ciu, pierwszy na wyj(cid:258)ciu).
Kolejk(cid:218) mo(cid:285)na efektywnie zaimplementowa(cid:202) przy u(cid:285)yciu listy dwukierunkowej. Implementacja
od(cid:239)(cid:200)czania z kolejki polega wtedy na usuni(cid:218)ciu elementu z pocz(cid:200)tku listy powi(cid:200)zanej. Usta-
wienie w kolejce to dodanie elementu na koniec listy. Rysunek 2.8 pokazuje, jak wykona(cid:202) te
dwie operacje.
Rysunek 2.8. Ustawianie w kolejce i od(cid:239)(cid:200)czanie z niej przy u(cid:285)yciu listy dwukierunkowej
Aby od(cid:239)(cid:200)czy(cid:202) element z kolejki opartej na li(cid:258)cie dwukierunkowej, wystarczy przenie(cid:258)(cid:202) jej g(cid:239)ow(cid:218)
do nast(cid:218)pnego elementu na li(cid:258)cie i od(cid:239)(cid:200)czy(cid:202) dotychczasowy element pocz(cid:200)tkowy, nadaj(cid:200)c jego
wska(cid:283)nikowi d
Pobierz darmowy fragment (pdf)
