Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00447 006619 19984358 na godz. na dobę w sumie
Struktury danych i algorytmy w języku Java. Przewodnik dla początkujących - książka
Struktury danych i algorytmy w języku Java. Przewodnik dla początkujących - książka
Autor: Liczba stron: 168
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-283-5329-9 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> java - programowanie
Porównaj ceny (książka, ebook (-35%), audiobook).

Aby aplikacje mogły spełniać oczekiwania dotyczące wydajności i szybkości działania, programista musi orientować się w typowych problemach z wykonywaniem kodu i wiedzieć, które techniki sprawdzą się w danej sytuacji. W tym celu powinien biegle posługiwać się algorytmami i strukturami danych. Wiedza ta umożliwia rozpoznawanie typowych zagrożeń i wybór najlepszych rozwiązań. Warto pamiętać, że w przypadku większości codziennych problemów z kodem istnieją już wypróbowane rozwiązania. Znajomość tych zagadnień jest niezwykle ważna dla każdego inżyniera oprogramowania.

To książka przeznaczona dla programistów, którzy chcą w praktyczny sposób posługiwać się popularnymi algorytmami i strukturami danych, zrozumieć ich działanie i skuteczniej poprawiać wydajność swojego kodu w Javie. Przedstawiono tu narzędzia przydatne w pracy z algorytmami i w tworzeniu efektywnych aplikacji. Opisano praktyczne aspekty złożoności algorytmów. Omówiono algorytmy sortowania oraz inne popularne wzorce programowania, a także takie struktury danych jak drzewa binarne, tablice z haszowaniem i grafy. Następnie zaprezentowano koncepcje bardziej zaawansowane, wśród nich paradygmaty projektowania algorytmów i teorię grafów.

W tej książce między innymi:

Algorytm i struktura danych: tak działa optymalny kod!

Znajdź podobne książki Ostatnio czytane w tej kategorii

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)

Gdzie kupić całą publikację:

Struktury danych i algorytmy w języku Java. Przewodnik dla początkujących
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ą: