Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00072 006137 19007370 na godz. na dobę w sumie
Struktury danych i algorytmy w języku C#. Projektowanie efektywnych aplikacji - książka
Struktury danych i algorytmy w języku C#. Projektowanie efektywnych aplikacji - książka
Autor: Liczba stron: 232
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-283-5047-2 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> algorytmy - programowanie
Porównaj ceny (książka, ebook (-35%), audiobook).

C# jest nowoczesnym i elastycznym językiem programowania. Aby w pełni skorzystać z jego zalet, trzeba płynnie posługiwać się dostępnymi w nim strukturami danych i algorytmami, pozwalają one bowiem na efektywnie organizowanie danych i mają znaczący wpływ na wydajność aplikacji. Z punktu widzenia programisty kluczowe jest ich właściwe zaimplementowanie: wybór właściwej struktury danych i związanego z nią algorytmu stanowi o jakości tworzonego kodu. Na przykład w celu wykonywania wysokowydajnych operacji na zbiorach warto użyć zbioru haszowanego. Inne konstrukcje umożliwiają rozwiązywanie kolejnych problemów.

Dzięki tej książce nauczysz się używania struktur danych i implementacji najważniejszych algorytmów w języku C#. Najpierw zapoznasz się z najprostszymi strukturami danych o swobodnym dostępie - z tablicami oraz listami. Wyjaśniono tu również działanie struktur danych o dostępie sekwencyjnym, opartych na stosach i kolejkach. Przedstawiono zastosowanie słowników, dzięki którym można mapować klucze na wartości i prowadzić szybkie wyszukiwanie. Przystępnie opisano korzystanie z najbardziej zaawansowanych konstrukcji, takich jak drzewo binarne, binarne drzewo poszukiwań, drzewo samorównoważące się i kopiec. W końcowej części książki znajdziesz ciekawą analizę stosowania grafów i związanych z nimi algorytmów, takich jak przeszukiwanie grafu, minimalne drzewo rozpinające, kolorowanie węzłów oraz znajdowanie najkrótszej ścieżki.

Najciekawsze zagadnienia ujęte w książce:

C#. Liczy się algorytm i odpowiednia struktura danych!

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

Darmowy fragment publikacji:

Tytuł oryginału: C# Data Structures and Algorithms Tłumaczenie: Krzysztof Bąbol ISBN: 978-83-283-5047-2 Copyright © Packt Publishing 2018. First published in the English language under the title ‘C# Data Structures and Algorithms (9781788833738)’ 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/strdan.zip Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie/strdan 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 7 8 9 13 14 15 16 17 22 23 25 26 27 30 32 33 34 34 36 41 45 45 48 50 52 O autorze O recenzencie Wst(cid:218)p Rozdzia(cid:239) 1. Wprowadzenie J(cid:218)zyk programowania Typy danych Typy warto(cid:258)ciowe Typy referencyjne Instalacja i konfiguracja (cid:258)rodowiska IDE Tworzenie projektu Wej(cid:258)cie i wyj(cid:258)cie Odczytywanie z wej(cid:258)cia Zapisywanie do wyj(cid:258)cia Uruchamianie i debugowanie Podsumowanie Rozdzia(cid:239) 2. Tablice i listy Tablice Tablice jednowymiarowe Tablice wielowymiarowe Tablice nieregularne Algorytmy sortowania Sortowanie przez wybieranie Sortowanie przez wstawianie Sortowanie b(cid:200)belkowe Sortowanie szybkie Poleć książkęKup książkę Spis tre(cid:286)ci Proste listy Lista tablicowa Lista generyczna Przyk(cid:239)ad — (cid:258)rednia warto(cid:258)(cid:202) Przyk(cid:239)ad — lista osób Listy uporz(cid:200)dkowane Przyk(cid:239)ad — ksi(cid:200)(cid:285)ka adresowa Listy wi(cid:200)zane Przyk(cid:239)ad — czytnik ksi(cid:200)(cid:285)ki Listy cykliczne Implementacja Przyk(cid:239)ad — zakr(cid:218)(cid:202) ko(cid:239)em Podsumowanie Rozdzia(cid:239) 3. Stosy i kolejki Stosy Przyk(cid:239)ad — odwracanie wyrazów Przyk(cid:239)ad — Wie(cid:285)e Hanoi Kolejki Przyk(cid:239)ad — telefoniczne biuro obs(cid:239)ugi klienta z jednym konsultantem Przyk(cid:239)ad — telefoniczne biuro obs(cid:239)ugi klienta z wieloma konsultantami Przyk(cid:239)ad — biuro telefonicznej obs(cid:239)ugi klienta ze wsparciem priorytetowym Kolejki priorytetowe Podsumowanie Rozdzia(cid:239) 4. S(cid:239)owniki i zbiory Tablice z haszowaniem Przyk(cid:239)ad — ksi(cid:200)(cid:285)ka telefoniczna S(cid:239)owniki Przyk(cid:239)ad — wyszukiwanie produktu Przyk(cid:239)ad — dane u(cid:285)ytkownika S(cid:239)owniki uporz(cid:200)dkowane Przyk(cid:239)ad — definicje Zbiory haszowane Przyk(cid:239)ad — kupony Przyk(cid:239)ad — baseny Zbiory „uporz(cid:200)dkowane” Przyk(cid:239)ad — usuwanie duplikatów Podsumowanie Rozdzia(cid:239) 5. Warianty drzew Zwyk(cid:239)e drzewa Implementacja Przyk(cid:239)ad — hierarchia identyfikatorów Przyk(cid:239)ad — struktura przedsi(cid:218)biorstwa Drzewa binarne Implementacja Przyk(cid:239)ad — prosty quiz 4 55 55 57 58 59 60 61 62 63 66 67 69 71 73 73 75 75 82 84 88 92 94 97 99 99 101 104 105 107 109 110 113 115 117 120 121 122 123 124 124 126 127 129 132 136 Poleć książkęKup książkę Binarne drzewa poszukiwa(cid:241) Implementacja Przyk(cid:239)ad — wizualizacja drzewa BST Drzewa AVL Implementacja Przyk(cid:239)ad — utrzymuj zrównowa(cid:285)enie drzewa Drzewa czerwono-czarne Implementacja Przyk(cid:239)ad — funkcje drzew RBT Kopce binarne Implementacja Przyk(cid:239)ad — sortowanie przez kopcowanie Kopce dwumianowe Kopce Fibonacciego Podsumowanie Rozdzia(cid:239) 6. Odkrywanie grafów Koncepcja grafów Zastosowania Reprezentacja Lista s(cid:200)siedztwa Macierz s(cid:200)siedztwa Implementacja W(cid:218)ze(cid:239) Kraw(cid:218)d(cid:283) Graf Przyk(cid:239)ad — kraw(cid:218)dzie nieskierowane i niewa(cid:285)one Przyk(cid:239)ad — kraw(cid:218)dzie skierowane i wa(cid:285)one Przeszukiwanie Przeszukiwanie w g(cid:239)(cid:200)b Przeszukiwanie wszerz Minimalne drzewo rozpinaj(cid:200)ce Algorytm Kruskala Algorytm Prima Przyk(cid:239)ad — kabel telekomunikacyjny Kolorowanie Przyk(cid:239)ad — mapa województw Najkrótsza (cid:258)cie(cid:285)ka Przyk(cid:239)ad — mapa gry Podsumowanie Spis tre(cid:286)ci 139 142 149 156 157 158 159 160 160 162 163 164 165 166 168 169 170 172 173 174 175 178 178 179 180 184 185 186 186 189 192 193 196 200 203 205 207 210 213 5 Poleć książkęKup książkę Spis tre(cid:286)ci Rozdzia(cid:239) 7. Podsumowanie Klasyfikacja struktur danych Ró(cid:285)norodno(cid:258)(cid:202) zastosowa(cid:241) struktur danych Tablice Listy Stosy Kolejki S(cid:239)owniki Zbiory Drzewa Kopce Grafy S(cid:239)owo ko(cid:241)cowe Skorowidz 215 215 217 217 218 219 219 220 221 221 222 223 224 227 6 Poleć książkęKup książkę 33 2 Tablice i listy Jako programista z pewno(cid:258)ci(cid:200) przechowywa(cid:239)e(cid:258) w swoich aplikacjach ró(cid:285)ne kolekcje, takie jak dane u(cid:285)ytkownika, ksi(cid:200)(cid:285)ki albo logi. Jednym z naturalnych sposobów przechowywania takich danych jest u(cid:285)ycie tablic i list. Czy jednak my(cid:258)la(cid:239)e(cid:258) kiedykolwiek o ich wariantach? Czy s(cid:239)ysza(cid:239)e(cid:258) o tablicach nieregularnych albo o listach cyklicznych? W tym rozdziale zobaczysz dzia(cid:239)anie takich struktur danych wraz z przyk(cid:239)adami i dok(cid:239)adnym opisem. To nie wszystko, poniewa(cid:285) od- niesiemy si(cid:218) do wielu zagadnie(cid:241) zwi(cid:200)zanych z tablicami i listami, odpowiednich dla programi- stów o ró(cid:285)nym poziomie umiej(cid:218)tno(cid:258)ci. Na pocz(cid:200)tku przedstawione zostan(cid:200) tablice oraz ich podzia(cid:239) na jednowymiarowe, wielowymia- rowe i nieregularne. Poznasz cztery algorytmy sortowania, a mianowicie sortowanie przez selek- cj(cid:218), wstawianie, b(cid:200)belkowe oraz szybkie. W ka(cid:285)dym przypadku zostanie zaprezentowany przy- k(cid:239)ad opatrzony rysunkiem, kod implementacji oraz wyja(cid:258)nienie krok po kroku. Tablice maj(cid:200) wiele zastosowa(cid:241), ale jeszcze wi(cid:218)ksze mo(cid:285)liwo(cid:258)ci daj(cid:200) dost(cid:218)pne w j(cid:218)zyku C# listy generyczne. W pozosta(cid:239)ej cz(cid:218)(cid:258)ci rozdzia(cid:239)u zobaczysz, jak korzysta(cid:202) z kilku wariantów list: prostych, uporz(cid:200)dkowanych, dwukierunkowych i cyklicznych. Dla ka(cid:285)dej odmiany zostanie przedstawiony kod w j(cid:218)zyku C# z dok(cid:239)adnym opisem. Rozdzia(cid:239) ten omawia: (cid:81) tablice, (cid:81) algorytmy sortowania, (cid:81) listy proste, (cid:81) listy uporz(cid:200)dkowane, (cid:81) listy wi(cid:200)zane, (cid:81) listy cykliczne. Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# Tablice Zacznijmy od tablicowej struktury danych. U(cid:285)ywa si(cid:218) jej do przechowywania wielu zmiennych tego samego typu, jak int, string albo zdefiniowana przez u(cid:285)ytkownika klasa. Jak wspomnia(cid:239)em we wst(cid:218)pie, podczas opracowywania aplikacji w j(cid:218)zyku C# mo(cid:285)na korzysta(cid:202) z kilku wariantów tablic, przedstawionych na poni(cid:285)szym rysunku. Dost(cid:218)pne s(cid:200) nie tylko tablice jednowymiarowe (oznaczone liter(cid:200) a), ale tak(cid:285)e wielowymiarowe (b) i nieregularne (c). Przyk(cid:239)ad ka(cid:285)dej z nich jest pokazany poni(cid:285)ej: Co istotne, po zainicjowaniu tablicy nie da si(cid:218) zmieni(cid:202) liczby jej elementów. Z tego powodu nie mo(cid:285)na w prosty sposób doda(cid:202) na ko(cid:241)cu tablicy nowego elementu ani wstawi(cid:202) go na okre(cid:258)lonej pozycji. Je(cid:258)li potrzebujesz takich funkcji, mo(cid:285)esz u(cid:285)y(cid:202) innych struktur danych opisanych w tym rozdziale — list generycznych. Wi(cid:218)cej informacji o tablicach znajdziesz pod adresem https://docs.microsoft.com/pl-pl/dotnet/csharp/ programming-guide/arrays/. Po tym krótkim opisie jeste(cid:258) gotowy, aby dowiedzie(cid:202) si(cid:218) wi(cid:218)cej o poszczególnych wariantach tablic i przyjrze(cid:202) si(cid:218) kodowi w j(cid:218)zyku C#. Przejd(cid:283)my wi(cid:218)c do najprostszej odmiany tablic, czyli tablic jednowymiarowych. Tablice jednowymiarowe Tablica jednowymiarowa przechowuje kolekcj(cid:218) elementów tego samego typu, dost(cid:218)pnych za pomoc(cid:200) indeksu. Wa(cid:285)ne, by pami(cid:218)ta(cid:202), (cid:285)e indeksy tablic w j(cid:218)zyku C# zaczynaj(cid:200) si(cid:218) od zera, to znaczy pierwszy element ma indeks równy 0, ostatni — rozmiar tablicy minus jeden. 34 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Przyk(cid:239)adowa tablica jednowymiarowa jest pokazana na poprzednim rysunku (po jego lewej stronie, oznaczona liter(cid:200) a). Zawiera pi(cid:218)(cid:202) elementów o warto(cid:258)ciach 9, –11, 6, –12 i 1. Pierwszy element ma indeks równy 0, ostatni — 4. Aby korzysta(cid:202) z tablicy jednowymiarowej, nale(cid:285)y j(cid:200) zadeklarowa(cid:202) i zainicjowa(cid:202). Deklaracja jest bardzo prosta, bo wystarczy poda(cid:202) typ elementów i nazw(cid:218) w nast(cid:218)puj(cid:200)cy sposób: typ[] nazwa; Deklaracja tablicy o warto(cid:258)ciach ca(cid:239)kowitych wygl(cid:200)da nast(cid:218)puj(cid:200)co: int[] numbers; Wiesz ju(cid:285), jak zadeklarowa(cid:202) tablic(cid:218), ale co z inicjowaniem? Aby zainicjowa(cid:202) elementy tablicy domy(cid:258)lnymi warto(cid:258)ciami, u(cid:285)ywa si(cid:218) operatora new, tak jak poni(cid:285)ej: numbers = new int[5]; Deklaracj(cid:218) i inicjowanie mo(cid:285)na oczywi(cid:258)cie po(cid:239)(cid:200)czy(cid:202) w jednej linii w nast(cid:218)puj(cid:200)cy sposób: int[] numbers = new int[5]; Niestety wszystkie elementy maj(cid:200) teraz domy(cid:258)lne warto(cid:258)ci, to znaczy, w przypadku warto(cid:258)ci ca(cid:239)- kowitych, zero. Nale(cid:285)y wi(cid:218)c nada(cid:202) warto(cid:258)ci poszczególnym elementom za pomoc(cid:200) operatora [] i indeksu elementu, co pokazuje listing: numbers[0] = 9; numbers[1] = -11; (...) numbers[4] = 1; Mo(cid:285)na ponadto po(cid:239)(cid:200)czy(cid:202) deklaracj(cid:218) i inicjowanie elementów tablicy okre(cid:258)lonymi warto(cid:258)ciami przy u(cid:285)yciu jednego z poni(cid:285)szych wariantów kodu: int[] numbers = new int[] { 9, -11, 6, -12, 1 }; int[] numbers = { 9, -11, 6, -12, 1 }; Je(cid:258)li elementy tablicy maj(cid:200) odpowiednie warto(cid:258)ci, pobiera si(cid:218) je za pomoc(cid:200) operatora [] oraz in- deksu, jak to zosta(cid:239)o pokazane w poni(cid:285)szym wierszu: int middle = numbers[2]; Warto(cid:258)(cid:202) trzeciego elementu (o indeksie równym 2) tablicy o nazwie numbers jest tutaj pobierana i zapisywana w zmiennej middle. Wi(cid:218)cej informacji o tablicach jednowymiarowych mo(cid:285)na uzyska(cid:202) na stronie https://docs.microsoft. com/pl-pl/dotnet/csharp/programming-guide/arrays/single-dimensional-arrays. 35 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# Przyk(cid:239)ad — nazwy miesi(cid:218)cy Aby podsumowa(cid:202) informacje o tablicach jednowymiarowych, rzu(cid:202)my okiem na prosty przyk(cid:239)ad, w którym tablica s(cid:239)u(cid:285)y do przechowywania nazw miesi(cid:218)cy. Nazwy tego typu powinny by(cid:202) pozy- skiwane automatycznie, a nie wpisywane bezpo(cid:258)rednio do kodu (cid:283)ród(cid:239)owego. Oto implementacja: string[] months = new string[12]; for (int month = 1; month = 12; month++) { DateTime firstDay = new DateTime(DateTime.Now.Year, month, 1); string name = firstDay.ToString( MMMM , CultureInfo.CreateSpecificCulture( pl )); months[month - 1] = name; } foreach (string month in months) { Console.WriteLine($ - {month} ); } Na pocz(cid:200)tku tworzy si(cid:218) tablic(cid:218) jednowymiarow(cid:200) i inicjuje si(cid:218) j(cid:200) domy(cid:258)lnymi warto(cid:258)ciami. Zawiera ona 12 elementów przeznaczonych do przechowywania nazw miesi(cid:218)cy. Nast(cid:218)pnie p(cid:218)tla for przechodzi po numerach miesi(cid:218)cy od 1 do 12. Tworzone s(cid:200) wyst(cid:200)pienia klasy DateTime repre- zentuj(cid:200)ce pierwszy dzie(cid:241) ka(cid:285)dego miesi(cid:200)ca. Nazwa miesi(cid:200)ca jest pozyskiwana dzi(cid:218)ki wywo(cid:239)aniu w wyst(cid:200)pieniu klasy DateTime metody ToString z odpowiednim formatem daty (MMMM) oraz okre(cid:258)lon(cid:200) kultur(cid:200) (w tym przypadku pl). Nast(cid:218)pnie nazwa miesi(cid:200)ca jest zachowywana w tablicy za pomoc(cid:200) operatora [] z indeksem elementu. Warto odnotowa(cid:202), (cid:285)e indeks jest równy bie(cid:285)(cid:200)cej warto(cid:258)ci zmiennej month minus jeden. Odj(cid:218)cie jedynki jest niezb(cid:218)dne, bo pierwszy element tablicy ma warto(cid:258)(cid:202) zero, a nie jeden. Kolejnym interesuj(cid:200)cym fragmentem kodu jest p(cid:218)tla foreach przechodz(cid:200)ca po wszystkich ele- mentach tablicy. W przypadku ka(cid:285)dego z nich w konsoli wy(cid:258)wietlana jest jedna linia, to znaczy nazwa miesi(cid:200)ca poprzedzona symbolem - . Wynik wygl(cid:200)da nast(cid:218)puj(cid:200)co: - January - February (...) - November - December Jak wcze(cid:258)niej wspomnia(cid:239)em, tablice jednowymiarowe nie s(cid:200) jedynym dost(cid:218)pnym wariantem tablic. W kolejnym punkcie dowiesz si(cid:218) wi(cid:218)cej o tablicach wielowymiarowych. Tablice wielowymiarowe Tablice w j(cid:218)zyku C# nie musz(cid:200) ogranicza(cid:202) si(cid:218) tylko do jednego wymiaru. Istnieje równie(cid:285) mo(cid:285)- liwo(cid:258)(cid:202) tworzenia tablic o dwóch, a nawet trzech wymiarach. Rozpocznijmy od przyjrzenia si(cid:218) deklaracji i inicjowaniu tablicy dwuwymiarowej o 5 rz(cid:218)dach i 2 kolumnach: int[,] numbers = new int[5, 2]; 36 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Aby utworzy(cid:202) tablic(cid:218) trójwymiarow(cid:200), u(cid:285)ywa si(cid:218) nast(cid:218)puj(cid:200)cego kodu: int[, ,] numbers = new int[5, 4, 3]; Mo(cid:285)na oczywi(cid:258)cie po(cid:239)(cid:200)czy(cid:202) deklaracj(cid:218) z inicjowaniem, tak jak w poni(cid:285)szym przyk(cid:239)adzie: int[,] numbers = new int[,] = { { 9, 5, -9 }, { -11, 4, 0 }, { 6, 115, 3 }, { -12, -9, 71 }, { 1, -6, -1 } }; Przyda(cid:239)oby si(cid:218) drobne wyja(cid:258)nienie, w jaki sposób uzyska(cid:202) dost(cid:218)p do poszczególnych elementów tablicy dwuwymiarowej. Spójrzmy na poni(cid:285)szy przyk(cid:239)ad: int number = numbers[2][1]; numbers[1][0] = 11; W pierwszym wierszu kodu odczytywana jest warto(cid:258)(cid:202) z trzeciego wiersza (indeks równy 2) i dru- giej kolumny (indeks 1) tabeli (warto(cid:258)(cid:202) ta wynosi 115), która jest przypisywana zmiennej number. Drugi wiersz kodu zmienia warto(cid:258)(cid:202) w drugim wierszu i pierwszej kolumnie tabeli z -11 na 11. Wi(cid:218)cej informacji o tablicach wielowymiarowych mo(cid:285)na uzyska(cid:202) na stronie https://docs.microsoft. com/pl-pl/dotnet/csharp/programming-guide/arrays/multidimensional-arrays. Przyk(cid:239)ad — tabliczka mno(cid:285)enia Pierwszy przyk(cid:239)ad ilustruje podstawowe operacje na tablicy dwuwymiarowej, prezentuj(cid:200)c ta- bliczk(cid:218) mno(cid:285)enia. Zapisane zosta(cid:239)y wyniki mno(cid:285)enia wszystkich liczb ca(cid:239)kowitych od 1 do 10, co pokazuj(cid:200) poni(cid:285)sze dane wyj(cid:258)ciowe: 1 2 3 4 5 6 7 8 9 10 2 4 6 8 10 12 14 16 18 20 3 6 9 12 15 18 21 24 27 30 4 8 12 16 20 24 28 32 36 40 5 10 15 20 25 30 35 40 45 50 6 12 18 24 30 36 42 48 54 60 7 14 21 28 35 42 49 56 63 70 8 16 24 32 40 48 56 64 72 80 9 18 27 36 45 54 63 72 81 90 10 20 30 40 50 60 70 80 90 100 Przyjrzyjmy si(cid:218) sposobowi deklaracji i inicjowania tablicy: int[,] results = new int[10, 10]; Tworzona jest tutaj tablica dwuwymiarowa o 10 wierszach i 10 kolumnach, a jej elementy s(cid:200) ini- cjowane warto(cid:258)ciami domy(cid:258)lnymi, to znaczy zerami. 37 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# Tablica jest gotowa, nale(cid:285)y wi(cid:218)c wype(cid:239)ni(cid:202) j(cid:200) wynikami mno(cid:285)enia. Mo(cid:285)na tego dokona(cid:202) za pomoc(cid:200) dwóch p(cid:218)tli for: for (int i = 0; i results.GetLength(0); i++) { for (int j = 0; j results.GetLength(1); j++) { results[i, j] = (i + 1) * (j + 1); } } Na powy(cid:285)szym listingu na obiekcie tablicy wywo(cid:239)uje si(cid:218) metod(cid:218) GetLength. Metoda ta zwraca liczb(cid:218) elementów konkretnego wymiaru, to znaczy pierwszego (gdy parametrem jest 0) i drugiego (gdy parametrem jest 1). W obu przypadkach zwracana jest warto(cid:258)(cid:202) 10, odpowiadaj(cid:200)ca warto- (cid:258)ciom podanym w czasie inicjowania tablicy. Inn(cid:200) wa(cid:285)n(cid:200) kwesti(cid:200) jest sposób nadawania warto(cid:258)ci elementom tablicy dwuwymiarowej. Aby tego dokona(cid:202), nale(cid:285)y poda(cid:202) dwa indeksy: results[i, j]. Na koniec wystarczy przedstawi(cid:202) wyniki. Mo(cid:285)na to zrobi(cid:202) za pomoc(cid:200) dwóch p(cid:218)tli for, tak jak w przypadku wype(cid:239)niania tablicy. Ten fragment kodu przedstawia si(cid:218) nast(cid:218)puj(cid:200)co: for (int i = 0; i results.GetLength(0); i++) { for (int j = 0; j results.GetLength(1); j++) { Console.Write( {0,4} , results[i, j]); } Console.WriteLine(); } Wyniki mno(cid:285)enia po zamianie na warto(cid:258)ci typu string maj(cid:200) ró(cid:285)n(cid:200) d(cid:239)ugo(cid:258)(cid:202), od jednego znaku (w przypadku 4 jako wyniku dzia(cid:239)ania 2 * 2) do trzech (100 z mno(cid:285)enia 10 * 10). Dla lepszej prezentacji wyniku nale(cid:285)y go zawsze wypisywa(cid:202) za pomoc(cid:200) 4 znaków. Je(cid:258)li zatem warto(cid:258)(cid:202) ca(cid:239)- kowita zajmuje mniej miejsca, trzeba doda(cid:202) na pocz(cid:200)tku spacje. Na przyk(cid:239)ad wynik 1 b(cid:218)dzie poprzedzony trzema spacjami (___1, gdzie _ oznacza spacj(cid:218)), a 100 tylko jedn(cid:200) (_100). Aby osi(cid:200)- gn(cid:200)(cid:202) ten cel, przy wywo(cid:239)aniu metody Write z klasy Console mo(cid:285)na u(cid:285)y(cid:202) odpowiedniego z(cid:239)o(cid:285)o- nego ci(cid:200)gu formatuj(cid:200)cego (to znaczy {0,4}). Przyk(cid:239)ad — mapa gry Innym przyk(cid:239)adem zastosowania tablicy dwuwymiarowej jest program przedstawiaj(cid:200)cy map(cid:218) gry. Mapa jest prostok(cid:200)tem o 11 wierszach i 10 kolumnach. Ka(cid:285)dy element tablicy okre(cid:258)la typ terenu, taki jak trawa, piasek woda albo mur. Ka(cid:285)de miejsce mapy powinno by(cid:202) wy(cid:258)wietlone w okre(cid:258)lonym kolorze (na przyk(cid:239)ad zielonym w przypadku trawy) za pomoc(cid:200) znaku obrazuj(cid:200)cego typ terenu (na przyk(cid:239)ad (cid:3611) w przypadku wody), co pokazuje rysunek: 38 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Na pocz(cid:200)tku zadeklarujmy warto(cid:258)(cid:202) wyliczenia o nazwie TerrainEnum z czterema sta(cid:239)ymi, mianowicie GRASS, SAND, WATER i WALL w nast(cid:218)puj(cid:200)cy sposób: public enum TerrainEnum { GRASS, SAND, WATER, WALL } Dla lepszej czytelno(cid:258)ci ca(cid:239)ego projektu zaleca si(cid:218) zadeklarowanie typu TerrainEnum w oddzielnym pliku o nazwie TerrainEnum.cs. Nale(cid:285)y stosowa(cid:202) t(cid:218) zasad(cid:218) do wszystkich typów zdefiniowanych przez u(cid:285)ytkownika, w(cid:239)(cid:200)cznie z klasami. Nast(cid:218)pnie tworzone s(cid:200) dwie metody rozszerze(cid:241), umo(cid:285)liwiaj(cid:200)ce pobranie odpowiedniego koloru i znaku w zale(cid:285)no(cid:258)ci od typu terenu (odpowiednio GetColor i GetChar). Te metody rozszerze(cid:241) s(cid:200) zadeklarowane w klasie TerrainEnumExtensions w sposób przedstawiony poni(cid:285)ej: public static class TerrainEnumExtensions { public static ConsoleColor GetColor(this TerrainEnum terrain) { switch (terrain) { case TerrainEnum.GRASS: return ConsoleColor.Green; case TerrainEnum.SAND: return ConsoleColor.Yellow; case TerrainEnum.WATER: return ConsoleColor.Blue; default: return ConsoleColor.DarkGray; } } public static char GetChar(this TerrainEnum terrain) { switch (terrain) { case TerrainEnum.GRASS: return \u201c ; case TerrainEnum.SAND: return \u25cb ; case TerrainEnum.WATER: return \u2248 ; 39 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# default: return \u25cf ; } } } Warto wspomnie(cid:202), (cid:285)e metoda GetChar zwraca w(cid:239)a(cid:258)ciwy znak Unicode w oparciu o warto(cid:258)(cid:202) TerrainEnum. Na przyk(cid:239)ad w przypadku sta(cid:239)ej WATER zwracana jest warto(cid:258)(cid:202) \u2248 b(cid:218)d(cid:200)ca re- prezentacj(cid:200) znaku (cid:3611). Czy s(cid:239)ysza(cid:239)e(cid:258) o metodach rozszerze(cid:241) (ang. extension methods)? Je(cid:258)li nie, pomy(cid:258)l o nich jako o metodach „dodanych” do jakiego(cid:258) istniej(cid:200)cego typu (zarówno wbudowanego, jak i zdefiniowanego przez u(cid:285)ytkownika), które wywo(cid:239)uje si(cid:218) tak, jakby by(cid:239)y zdefiniowane bezpo(cid:258)rednio w jego wyst(cid:200)pieniu. Deklaruj(cid:200)c metod(cid:218) rozszerzenia, nale(cid:285)y zdefiniowa(cid:202) j(cid:200) w klasie statycznej jako metod(cid:218) statyczn(cid:200) z pierwszym parametrem wskazuj(cid:200)cym typ, do którego ma by(cid:202) „dodana”, poprzedzony s(cid:239)owem kluczowym this. Wi(cid:218)cej informacji mo(cid:285)na znale(cid:283)(cid:202) na stronie https://docs.microsoft.com/pl-pl/dotnet/csharp/programming-guide/classes-and- -structs/extension-methods. Przyjrzyjmy si(cid:218) tre(cid:258)ci metody Main w klasie Program. Konfiguruje ona map(cid:218) i prezentuje j(cid:200) w konsoli za pomoc(cid:200) nast(cid:218)puj(cid:200)cego kodu: TerrainEnum[,] map = { { TerrainEnum.SAND, TerrainEnum.SAND, TerrainEnum.SAND, TerrainEnum.SAND, TerrainEnum.GRASS, TerrainEnum.GRASS, TerrainEnum.GRASS, TerrainEnum.GRASS, TerrainEnum.GRASS, TerrainEnum.GRASS }, (...) { TerrainEnum.WATER, TerrainEnum.WATER, TerrainEnum.WATER, TerrainEnum.WATER, TerrainEnum.WATER, TerrainEnum.WATER, TerrainEnum.WATER, TerrainEnum.WALL, TerrainEnum.WATER, TerrainEnum.WATER } }; Console.OutputEncoding = UTF8Encoding.UTF8; for (int row = 0; row map.GetLength(0); row++) { for (int column = 0; column map.GetLength(1); column++) { Console.ForegroundColor = map[row, column].GetColor(); Console.Write(map[row, column].GetChar() + ); } Console.WriteLine(); } Console.ForegroundColor = ConsoleColor.Gray; Przyda si(cid:218) par(cid:218) s(cid:239)ów komentarza na temat sposobu pobierania koloru i pozyskiwania znaku dla konkretnego miejsca mapy. Obie operacje s(cid:200) wykonywane przez metody rozszerze(cid:241) dodane do zdefiniowanego przez u(cid:285)ytkownika typu TerrainEnum. Z tego powodu najpierw pozyskiwana jest warto(cid:258)(cid:202) wyliczenia TerrainEnum dla konkretnego miejsca mapy (za pomoc(cid:200) operatora [] i dwóch indeksów), a potem wywo(cid:239)ywana odpowiednia metoda rozszerzenia, GetChar albo GetColor. Do tej pory pozna(cid:239)e(cid:258) zarówno tablice jedno-, jak i wielowymiarowe, ale do przedstawienia w ksi(cid:200)(cid:285)ce pozosta(cid:239) jeszcze jeden wariant. Kontynuuj lektur(cid:218), aby dowiedzie(cid:202) si(cid:218) o nim wi(cid:218)cej. 40 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Tablice nieregularne Ostatnim wariantem tablic opisanym w tej ksi(cid:200)(cid:285)ce jest tablica nieregularna, zwana tak(cid:285)e tablic(cid:200) tablic. Brzmi to skomplikowanie, ale na szcz(cid:218)(cid:258)cie jest bardzo proste. Tablic(cid:218) nieregularn(cid:200) mo(cid:285)na wyobrazi(cid:202) sobie jako tablic(cid:218) jednowymiarow(cid:200), której ka(cid:285)dy element jest kolejn(cid:200) tablic(cid:200). Te we- wn(cid:218)trzne tablice mog(cid:200) mie(cid:202) oczywi(cid:258)cie ró(cid:285)n(cid:200) d(cid:239)ugo(cid:258)(cid:202), a nawet mog(cid:200) nie by(cid:202) zainicjowane. Spójrz na poni(cid:285)szy rysunek, na którym zobaczysz przyk(cid:239)adow(cid:200) tablic(cid:218) nieregularn(cid:200) o czterech elementach. Pierwszy z nich jest tablic(cid:200) z trzema elementami (9, 5, -9), drugi to tablica pi(cid:218)cio- elementowa (0, -3, 12, 51, -3), trzeci nie jest zainicjowany (ma warto(cid:258)(cid:202) NULL), a ostatni jest tablic(cid:200) maj(cid:200)c(cid:200) tylko jeden element (54): Zanim przejdziemy do przyk(cid:239)adu, warto jeszcze wspomnie(cid:202) o sposobie deklarowania i inicjo- wania tablicy nieregularnej, poniewa(cid:285) jest on nieco inny ni(cid:285) w opisanych wcze(cid:258)niej tablicach. Spójrz na poni(cid:285)szy listing: int[][] numbers = new int[4][]; numbers[0] = new int[] { 9, 5, -9 }; numbers[1] = new int[] { 0, -3, 12, 51, -3 }; numbers[3] = new int[] { 54 }; W pierwszym wierszu wida(cid:202) deklaracj(cid:218) tablicy jednowymiarowej o czterech elementach. Ka(cid:285)dy element jest nast(cid:218)pn(cid:200) tablic(cid:200) jednowymiarow(cid:200) warto(cid:258)ci ca(cid:239)kowitych. Po wykonaniu pierwszego wiersza kodu tablica numbers jest inicjowana warto(cid:258)ciami domy(cid:258)lnymi, to znaczy NULL. Z tego powodu nale(cid:285)y r(cid:218)cznie zainicjowa(cid:202) poszczególne elementy, co wida(cid:202) w kolejnych trzech wier- szach kodu. Warto zauwa(cid:285)y(cid:202), (cid:285)e trzeci element nie jest zainicjowany. Powy(cid:285)szy kod mo(cid:285)na te(cid:285) zapisa(cid:202) inaczej: int[][] numbers = { new int[] { 9, 5, -9 }, 41 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# new int[] { 0, -3, 12, 51, -3 }, NULL, new int[] { 54 } }; Wypada równie(cid:285) pokrótce skomentowa(cid:202) sposób dost(cid:218)pu do konkretnego elementu tablicy nie- regularnej. Wygl(cid:200)da on nast(cid:218)puj(cid:200)co: int number = numbers[1][2]; number[1][3] = 50; Pierwszy wiersz kodu nadaje zmiennej number warto(cid:258)(cid:202) 12, czyli warto(cid:258)(cid:202) trzeciego elementu (o indeksie 2) tablicy, która jest drugim elementem tablicy nieregularnej. Drugi wiersz zmienia warto(cid:258)(cid:202) czwartego elementu tablicy b(cid:218)d(cid:200)cej drugim elementem tablicy nieregularnej z 51 na 50. Wi(cid:218)cej informacji o tablicach nieregularnych mo(cid:285)na uzyska(cid:202) na stronie https://docs.microsoft.com/pl-pl/ dotnet/csharp/programming-guide/arrays/jagged-arrays. Przyk(cid:239)ad — roczny plan transportu Po wprowadzeniu do tablic nieregularnych przejd(cid:283)my do przyk(cid:239)adu. Zobaczysz, jak opracowa(cid:202) program tworz(cid:200)cy plan transportu na ca(cid:239)y rok. Dla ka(cid:285)dego dnia ka(cid:285)dego miesi(cid:200)ca aplikacja rysuje jeden dost(cid:218)pny (cid:258)rodek transportu. Na koniec program przedstawia wygenerowany plan, taki jak na poni(cid:285)szym rysunku: Na pocz(cid:200)tek zadeklarujmy typ wyliczeniowy ze sta(cid:239)ymi reprezentuj(cid:200)cymi dost(cid:218)pne typy trans- portu, a mianowicie samochód, autobus, metro, rower i piesz(cid:200) przechadzk(cid:218): public enum TransportEnum { CAR, BUS, SUBWAY, BIKE, WALK } 42 Poleć książkęKup książkę W kolejnym kroku s(cid:200) tworzone dwie metody rozszerze(cid:241), które zwracaj(cid:200) znak i kolor reprezen- tuj(cid:200)ce dany (cid:258)rodek transportu w konsoli. Oto ich kod: Rozdzia(cid:225) 2. • Tablice i listy public static class TransportEnumExtensions { public static char GetChar(this TransportEnum transport) { switch (transport) { case TransportEnum.BIKE: return R ; case TransportEnum.BUS: return A ; case TransportEnum.CAR: return S ; case TransportEnum.SUBWAY: return M ; case TransportEnum.WALK: return P ; default: throw new Exception( Nieznany (cid:258)rodek transportu ); } } public static ConsoleColor GetColor( this TransportEnum transport) { switch (transport) { case TransportEnum.BIKE: return ConsoleColor.Blue; case TransportEnum.BUS: return ConsoleColor.DarkGreen; case TransportEnum.CAR: return ConsoleColor.Red; case TransportEnum.SUBWAY: return ConsoleColor.DarkMagenta; case TransportEnum.WALK: return ConsoleColor.DarkYellow; default: throw new Exception( Nieznany (cid:258)rodek transportu ); } } } Powy(cid:285)szy kod nie wymaga dodatkowych wyja(cid:258)nie(cid:241), poniewa(cid:285) jest bardzo podobny do przed- stawionego wcze(cid:258)niej. Przejd(cid:283)my teraz do metody Main klasy Program, która zostanie pokazana i opisana we fragmentach. W pierwszej cz(cid:218)(cid:258)ci tworzy si(cid:218) tablic(cid:218) nieregularn(cid:200) i wype(cid:239)nia si(cid:218) j(cid:200) odpowiednimi warto(cid:258)ciami. Zak(cid:239)adamy, (cid:285)e tablica nieregularna ma 12 elementów reprezentuj(cid:200)cych miesi(cid:200)ce bie(cid:285)(cid:200)cego roku. Ka(cid:285)dy element jest jednowymiarow(cid:200) tablic(cid:200) warto(cid:258)ci typu TransportEnum. D(cid:239)ugo(cid:258)(cid:202) takiej we- wn(cid:218)trznej tablicy zale(cid:285)y od liczby dni w danym miesi(cid:200)cu, wynosi na przyk(cid:239)ad 31 elementów dla stycznia i 30 elementów dla kwietnia. Oto pierwsza cz(cid:218)(cid:258)(cid:202) kodu: Random random = new Random(); int transportTypesCount = Enum.GetNames(typeof(TransportEnum)).Length; TransportEnum[][] transport = new TransportEnum[12][]; for (int month = 1; month = 12; month++) { int daysCount = DateTime.DaysInMonth( DateTime.Now.Year, month); transport[month - 1] = new TransportEnum[daysCount]; 43 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# for (int day = 1; day = daysCount; day++) { int randomType = random.Next(transportTypesCount); transport[month - 1][day - 1] = (TransportEnum)randomType; } } Przeanalizujmy powy(cid:285)szy kod. Na pocz(cid:200)tku jest tworzone nowe wyst(cid:200)pienie klasy Random, które pos(cid:239)u(cid:285)y potem do wylosowania jednego z dost(cid:218)pnych (cid:258)rodków transportu. W nast(cid:218)pnym kroku z typu wyliczeniowego TransportEnum pobiera si(cid:218) sta(cid:239)(cid:200) numeryczn(cid:200) b(cid:218)d(cid:200)c(cid:200) liczb(cid:200) dost(cid:218)pnych typów transportu. W dalszej kolejno(cid:258)ci jest tworzona tablica nieregularna, a p(cid:218)tla for przechodzi po wszystkich miesi(cid:200)cach roku. W ka(cid:285)dej iteracji pozyskuje si(cid:218) liczb(cid:218) dni (za pomoc(cid:200) metody statycznej DaysInMonth klasy DateTime), a tablica (b(cid:218)d(cid:200)ca elementem tablicy nieregularnej) jest inicjowana zerami. W kolejnym wierszu wida(cid:202) nast(cid:218)pn(cid:200) p(cid:218)tl(cid:218) for s(cid:239)u(cid:285)(cid:200)c(cid:200) do przechodzenia po wszystkich dniach miesi(cid:200)ca. Wewn(cid:200)trz tej p(cid:218)tli odbywa si(cid:218) losowanie typu transportu i zapisy- wanie go w odpowiednim elemencie tablicy, która jest elementem tablicy nieregularnej. Nast(cid:218)pny fragment kodu jest zwi(cid:200)zany z pokazaniem planu w konsoli: string[] monthNames = GetMonthNames(); int monthNamesPart = monthNames.Max(n = n.Length) + 2; for (int month = 1; month = transport.Length; month++) { Console.Write( $ {monthNames[month - 1]}: .PadRight(monthNamesPart)); for (int day = 1; day = transport[month - 1].Length; day++) { Console.ForegroundColor = ConsoleColor.White; Console.BackgroundColor = transport[month - 1][day - 1].GetColor(); Console.Write(transport[month - 1][day - 1].GetChar()); Console.BackgroundColor = ConsoleColor.Black; Console.ForegroundColor = ConsoleColor.Gray; Console.Write( ); } Console.WriteLine(); } Na pocz(cid:200)tku za pomoc(cid:200) metody GetMonthNames, która b(cid:218)dzie opisana pó(cid:283)niej, tworzona jest jednowymiarowa tablica z nazwami miesi(cid:218)cy. Nast(cid:218)pnie zmiennej monthNamesPart przypisuje si(cid:218) maksymaln(cid:200) d(cid:239)ugo(cid:258)(cid:202) tekstu potrzebnego do przechowania nazwy miesi(cid:200)ca. Aby odnale(cid:283)(cid:202) t(cid:218) d(cid:239)ugo(cid:258)(cid:202), w kolekcji nazw miesi(cid:218)cy korzysta si(cid:218) z wyra(cid:285)enia LINQ. Pozyskany wynik jest zwi(cid:218)k- szany o 2, by zarezerwowa(cid:202) miejsce na przecinek i spacj(cid:218). Jedn(cid:200) ze (cid:258)wietnych funkcji j(cid:218)zyka C# jest mechanizm LINQ. Umo(cid:285)liwia on pobieranie danych w spójny sposób nie tylko z rozmaitych kolekcji, ale równie(cid:285) z baz danych korzystaj(cid:200)cych z j(cid:218)zyka Structured Query Language (SQL) i dokumentów w j(cid:218)zyku Extensible Markup Language (XML). Wi(cid:218)cej informacji mo(cid:285)na uzyska(cid:202) na stronie https://docs.microsoft.com/pl-pl/dotnet/csharp/linq/index. 44 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Nast(cid:218)pnie u(cid:285)ywa si(cid:218) p(cid:218)tli for do przej(cid:258)cia po wszystkich elementach tablicy nieregularnej, czyli miesi(cid:200)cach. W ka(cid:285)dej iteracji w konsoli pokazywana jest nazwa miesi(cid:200)ca. Potem kolejna p(cid:218)tla for przechodzi po wszystkich elementach bie(cid:285)(cid:200)cego elementu tablicy niere- gularnej, czyli dniach miesi(cid:200)ca. Dla ka(cid:285)dego z nich ustawiane s(cid:200) w(cid:239)a(cid:258)ciwe kolory (znaku i t(cid:239)a) oraz pokazywany jest odpowiedni znak. Na koniec przyjrzyjmy si(cid:218) implementacji metody GetMonthNames: private static string[] GetMonthNames() { string[] names = new string[12]; for (int month = 1; month = 12; month++) { DateTime firstDay = new DateTime( DateTime.Now.Year, month, 1); string name = firstDay.ToString( MMMM , CultureInfo.CreateSpecificCulture( pl )); names[month - 1] = name; } return names; } Ten kod nie wymaga dodatkowych wyja(cid:258)nie(cid:241), poniewa(cid:285) bazuje na przyk(cid:239)adzie dla tablic jednowymiarowych. Algorytmy sortowania Istnieje wiele algorytmów dokonuj(cid:200)cych rozmaitych operacji na tablicach, ale jednym z najcz(cid:218)st- szych zada(cid:241) jest sortowanie elementów tablicy w porz(cid:200)dku rosn(cid:200)cym lub malej(cid:200)cym. Zagadnie- nie algorytmów sortowania obejmuje wiele metod, w tym sortowanie przez wybieranie, przez wstawianie, b(cid:200)belkowe oraz szybkie, które zostan(cid:200) szczegó(cid:239)owo wyja(cid:258)nione w tym podrozdziale. Sortowanie przez wybieranie Rozpocznijmy od sortowania przez wybieranie, b(cid:218)d(cid:200)cego jednym z najprostszych algorytmów. Ten algorytm dzieli tablic(cid:218) na dwie cz(cid:218)(cid:258)ci, to znaczy posortowan(cid:200) i nieposortowan(cid:200). Podczas kolejnych iteracji algorytm znajduje najmniejszy element cz(cid:218)(cid:258)ci nieposortowanej i zamienia go miejscami z pierwszym elementem tej cz(cid:218)(cid:258)ci. Brzmi to bardzo prosto, prawda? Aby lepiej zrozumie(cid:202) ten algorytm, spójrz na kolejne iteracje w przypadku tablicy dziewi(cid:218)cio- elementowej (–11, 12, –42, 0, 1, 90, 68, 6, –9), które przedstawia poni(cid:285)szy rysunek: 45 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# Dla u(cid:239)atwienia analizy grub(cid:200) lini(cid:200) zosta(cid:239)a zaznaczona granica pomi(cid:218)dzy posortowan(cid:200) i nieposor- towan(cid:200) cz(cid:218)(cid:258)ci(cid:200) tablicy. Na pocz(cid:200)tku (krok 1.) granica jest zlokalizowana na samym szczycie tablicy, co oznacza, (cid:285)e posortowana cz(cid:218)(cid:258)(cid:202) jest pusta. Algorytm znajduje zatem najmniejsz(cid:200) warto(cid:258)(cid:202) w cz(cid:218)(cid:258)ci nieposortowanej (–42) i zamienia j(cid:200) z pierwszym elementem tej cz(cid:218)(cid:258)ci (–11). Wynik zosta(cid:239) przedstawiony w kroku 2., w którym cz(cid:218)(cid:258)(cid:202) posortowana zawiera jeden element (–42), a cz(cid:218)(cid:258)(cid:202) nieposortowana sk(cid:239)ada si(cid:218) z o(cid:258)miu elementów. Wspomniane kroki s(cid:200) wykonywane dot(cid:200)d, a(cid:285) w cz(cid:218)(cid:258)ci nieposortowanej zostanie tyko jeden element. Ostateczny wynik zosta(cid:239) zapre- zentowany w kroku 9. Pozna(cid:239)e(cid:258) dzia(cid:239)anie algorytmu sortowania przez wybieranie, ale czy wiesz, jaka jest rola wska(cid:283)ni- ków i oraz m pokazanych po lewej stronie kolejnych kroków na powy(cid:285)szym rysunku? Odnosz(cid:200) si(cid:218) one do zmiennych u(cid:285)ytych w implementacji tego algorytmu. Nadszed(cid:239) zatem czas, aby zoba- czy(cid:202) kod w j(cid:218)zyku C#. Algorytm zosta(cid:239) zaimplementowany w postaci statycznej klasy SelectionSort z generyczn(cid:200) me- tod(cid:200) statyczn(cid:200) Sort pokazan(cid:200) na poni(cid:285)szym listingu: public static class SelectionSort { public static void Sort T (T[] array) where T : IComparable { for (int i = 0; i array.Length - 1; i++) { int minIndex = i; T minValue = array[i]; for (int j = i + 1; j array.Length; j++) { if (array[j].CompareTo(minValue) 0) { minIndex = j; minValue = array[j]; } } Swap(array, i, minIndex); } } (...) } 46 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Metoda Sort przyjmuje jeden parametr, mianowicie tablic(cid:218) do posortowania (array). Wewn(cid:200)trz tej metody p(cid:218)tla for przechodzi po elementach tablicy do momentu, gdy w cz(cid:218)(cid:258)ci nieposortowa- nej zostanie tylko jeden element. Tak wi(cid:218)c liczba powtórze(cid:241) p(cid:218)tli jest równa d(cid:239)ugo(cid:258)ci tablicy minus jeden (array.Length - 1). W ramach ka(cid:285)dej iteracji u(cid:285)ywa si(cid:218) kolejnej p(cid:218)tli for do znale- zienia najmniejszej warto(cid:258)ci w cz(cid:218)(cid:258)ci nieposortowanej (minValue, od indeksu i + 1 a(cid:285) do ko(cid:241)ca tablicy) oraz do zachowania indeksu najmniejszej warto(cid:258)ci (minIndex, na powy(cid:285)szym rysunku oznaczony jako wska(cid:283)nik m). Nast(cid:218)pnie zamienia si(cid:218) miejscami najmniejszy element cz(cid:218)(cid:258)ci nie- posortowanej (o indeksie równym minIndex) z pierwszym elementem tej cz(cid:218)(cid:258)ci (o indeksie rów- nym i) za pomoc(cid:200) dodatkowej metody Swap, której implementacja wygl(cid:200)da tak jak poni(cid:285)ej: private static void Swap T (T[] array, int first, int second) { T temp = array[first]; array[first] = array[second]; array[second] = temp; } Je(cid:258)li chcesz przetestowa(cid:202) implementacj(cid:218) algorytmu sortowania przez wybieranie, umie(cid:258)(cid:202) poni(cid:285)- szy kod w metodzie Main klasy Program: int[] integerValues = { -11, 12, -42, 0, 1, 90, 68, 6, -9 }; SelectionSort.Sort(integerValues); Console.WriteLine(string.Join( | , integerValues)); Powy(cid:285)szy kod deklaruje i inicjuje now(cid:200) tablic(cid:218). Nast(cid:218)pnie wywo(cid:239)uje statyczn(cid:200) metod(cid:218) Sort z tablic(cid:200) jako parametrem. Na koniec przez po(cid:239)(cid:200)czenie elementów tablicy (rozdzielonych zna- kiem |) tworzona i pokazywana w konsoli jest warto(cid:258)(cid:202) typu string: -42 | -11 | -9 | 0 | 1 | 6 | 12 | 68 | 90 Dzi(cid:218)ki wykorzystaniu metody generycznej mo(cid:285)na z (cid:239)atwo(cid:258)ci(cid:200) u(cid:285)y(cid:202) tej klasy do sortowania ró(cid:285)- nych tablic, zawieraj(cid:200)cych na przyk(cid:239)ad liczby zmiennoprzecinkowe albo ci(cid:200)gi. Oto przyk(cid:239)ado- wy kod: string[] stringValues = { Maria , Marcin , Anna , Jakub , Jerzy , Nikola }; SelectionSort.Sort(stringValues); Console.WriteLine(string.Join( | , stringValues)); Na wyj(cid:258)ciu pojawi(cid:200) si(cid:218) poni(cid:285)sze dane: Anna | Jakub | Jerzy | Marcin | Maria | Nikola Przy omawianiu rozmaitych algorytmów jednym z najwa(cid:285)niejszych zagadnie(cid:241) jest z(cid:239)o(cid:285)ono(cid:258)(cid:202) obliczeniowa (ang. computational complexity), zw(cid:239)aszcza z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasowa (ang. time com- plexity). Ma ona kilka wariantów, na przyk(cid:239)ad dla najgorszego albo (cid:258)redniego przypadku. Z(cid:239)o(cid:285)ono(cid:258)(cid:202) mo(cid:285)na interpretowa(cid:202) jako liczb(cid:218) podstawowych operacji, które musi wykona(cid:202) algo- rytm w zale(cid:285)no(cid:258)ci od rozmiaru danych wej(cid:258)ciowych (n). Wyra(cid:285)a si(cid:218) j(cid:200) za pomoc(cid:200) notacji „du(cid:285)e O” (ang. Big O notation), na przyk(cid:239)ad jako O(n), O(n2) albo O(n log(n)). Co to znaczy? Notacja O(n) wskazuje, (cid:285)e liczba operacji wzrasta liniowo wraz z rozmiarem danych wej(cid:258)ciowych (n). Rz(cid:200)d z(cid:239)o(cid:285)ono(cid:258)ci O(n2) jest nazywany kwadratowym (ang. quadratic), a O(n log(n)) linio- wo-logarytmicznym (ang. linearithmic). Istniej(cid:200) tak(cid:285)e inne rz(cid:218)dy z(cid:239)o(cid:285)ono(cid:258)ci, na przyk(cid:239)ad O(1), czyli sta(cid:239)y. 47 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# W przypadku sortowania przez wybieranie zarówno pesymistyczna, jak i (cid:258)rednia z(cid:239)o(cid:285)ono(cid:258)(cid:202) cza- sowa wynosi O(n2). Dlaczego? Aby odpowiedzie(cid:202) na to pytanie, przyjrzyjmy si(cid:218) kodowi. S(cid:200) tam dwie p(cid:218)tle (jedna wewn(cid:200)trz drugiej), a ka(cid:285)da z nich przechodzi przez wiele elementów tablicy. Z tego powodu z(cid:239)o(cid:285)ono(cid:258)(cid:202) jest wykazywana jako O(n2). Wi(cid:218)cej informacji na temat sortowania przez wybieranie i jego implementacji mo(cid:285)na znale(cid:283)(cid:202) na stronach: (cid:81) https://pl.wikipedia.org/wiki/Sortowanie_przez_wybieranie. (cid:81) http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Selection_sort. W(cid:239)a(cid:258)nie nauczy(cid:239)e(cid:258) si(cid:218) pierwszego algorytmu sortowania! Je(cid:258)li jeste(cid:258) zainteresowany poznaniem kolejnej metody, przejd(cid:283) do nast(cid:218)pnego punktu, przedstawiaj(cid:200)cego sortowanie przez wstawianie. Sortowanie przez wstawianie Sortowanie przez wstawianie (ang. insertion sort) jest kolejnym algorytmem pozwalaj(cid:200)cym w prosty sposób uporz(cid:200)dkowa(cid:202) tablic(cid:218) jednowymiarow(cid:200), co wida(cid:202) na poni(cid:285)szym rysunku. Podobnie jak w przypadku sortowania przez wybieranie, tablica jest dzielona na dwie cz(cid:218)(cid:258)ci, to znaczy posortowan(cid:200) i nieposortowan(cid:200), na pocz(cid:200)tku pierwszy element zalicza si(cid:218) jednak do cz(cid:218)(cid:258)ci posortowanej. W ka(cid:285)dej iteracji algorytm bierze pierwszy element z cz(cid:218)(cid:258)ci nieposortowa- nej i umieszcza go w odpowiednim miejscu cz(cid:218)(cid:258)ci posortowanej, zostawiaj(cid:200)c j(cid:200) we w(cid:239)a(cid:258)ciwym porz(cid:200)dku. Te operacje s(cid:200) powtarzane tak d(cid:239)ugo, a(cid:285) cz(cid:218)(cid:258)(cid:202) nieposortowana b(cid:218)dzie pusta. Przyjrzyjmy si(cid:218) przyk(cid:239)adowi sortowania tablicy dziewi(cid:218)cioelementowej (–11, 12, –42, 0, 1, 90, 68, 6, –9) za pomoc(cid:200) sortowania przez wstawianie, przedstawionemu na rysunku na nast(cid:218)p- nej stronie. Na pocz(cid:200)tku w cz(cid:218)(cid:258)ci posortowanej znajduje si(cid:218) tylko jeden element (–11 — krok 1.). Potem jest znajdowany najmniejszy element cz(cid:218)(cid:258)ci nieposortowanej (–42) i w serii zamian jest on prze- noszony na w(cid:239)a(cid:258)ciwe miejsce w cz(cid:218)(cid:258)ci posortowanej, czyli na pocz(cid:200)tek tablicy (kroki 2. i 3.). W ten sposób cz(cid:218)(cid:258)(cid:202) posortowana zwi(cid:218)kszy(cid:239)a si(cid:218) do dwóch elementów, czyli –42 i –11. Te opera- cje s(cid:200) powtarzane dot(cid:200)d, a(cid:285) cz(cid:218)(cid:258)(cid:202) nieposortowana b(cid:218)dzie pusta (krok 22.). Kod implementuj(cid:200)cy sortowanie przez wstawianie jest bardzo prosty: public static class InsertionSort { public static void Sort T (T[] array) where T : IComparable { for (int i = 1; i array.Length; i++) { int j = i; while (j 0 array[j].CompareTo(array[j - 1]) 0) { 48 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Swap(array, j, j - 1); j--; } } } (...) } Podobnie jak w przypadku sortowania przez wybieranie, implementacj(cid:218) zawarto w nowej klasie o nazwie InsertionSort. Generyczna metoda statyczna Sort dokonuje operacji sortowania, przyjmuj(cid:200)c jako parametr tablic(cid:218). Wewn(cid:200)trz tej metody p(cid:218)tla for przechodzi przez wszystkie elementy w cz(cid:218)(cid:258)ci nieposortowanej. Na pocz(cid:200)tku zmienna i przyjmuje warto(cid:258)(cid:202) nie 0, ale 1. W ka(cid:285)dym powtórzeniu p(cid:218)tli for uruchamiana jest p(cid:218)tla while przenosz(cid:200)ca pierwszy element w nieposortowanej cz(cid:218)(cid:258)ci tablicy (o indeksie równym warto(cid:258)ci zmiennej i) na w(cid:239)a(cid:258)ciwe miejsce w cz(cid:218)(cid:258)ci posortowanej przy u(cid:285)yciu pomocniczej metody Swap, zaimplementowanej tak samo jak w przypadku sortowania przez wybieranie. Sposób testowania sortowania przez wybieranie jest równie(cid:285) bardzo podobny, ale nale(cid:285)y u(cid:285)y(cid:202) innej nazwy klasy, czyli InsertionSort zamiast SelectionSort. Wi(cid:218)cej informacji na temat sortowania przez wstawianie i jego implementacji mo(cid:285)na znale(cid:283)(cid:202) na stronach: (cid:81) https://pl.wikipedia.org/wiki/Sortowanie_przez_wstawianie. (cid:81) https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Insertion_sort. 49 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# Na koniec warto wspomnie(cid:202) o z(cid:239)o(cid:285)ono(cid:258)ci czasowej sortowania przez wstawianie. Podobnie jak w przypadku sortowania przez wybieranie, zarówno pesymistyczna, jak i (cid:258)rednia z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasowa wynosi O(n2). Gdy przyjrzysz si(cid:218) kodowi, równie(cid:285) zobaczysz dwie p(cid:218)tle (for i while), umieszczone jedna w drugiej, których wykonanie mo(cid:285)e si(cid:218) powtarza(cid:202) wiele razy w zale(cid:285)no(cid:258)ci od rozmiaru danych wej(cid:258)ciowych. Sortowanie b(cid:200)belkowe Trzecim algorytmem sortowania przedstawionym w ksi(cid:200)(cid:285)ce b(cid:218)dzie sortowanie b(cid:200)belkowe (ang. bubble sort). Jego sposób dzia(cid:239)ania jest bardzo prosty, poniewa(cid:285) algorytm zwyczajnie przechodzi przez tablic(cid:218) i porównuje s(cid:200)siednie elementy. Je(cid:258)li s(cid:200) umieszczone w niew(cid:239)a(cid:258)ciwej kolejno(cid:258)ci, to s(cid:200) zamieniane miejscami. Brzmi to bardzo prosto, ale algorytm nie jest zbyt efektywny, a jego u(cid:285)ycie z du(cid:285)ymi kolekcjami mo(cid:285)e spowodowa(cid:202) problemy z wydajno(cid:258)ci(cid:200). Aby lepiej zrozumie(cid:202), jak dzia(cid:239)a opisany algorytm, przyjrzyj si(cid:218) poni(cid:285)szemu rysunkowi przedstawiaj(cid:200)cemu operacj(cid:218) sortowania jednowymiarowej tablicy o dziewi(cid:218)ciu elementach (–11, 12, –42, 0, 1, 90, 68, 6, –9): 50 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Jak wida(cid:202), w ka(cid:285)dym kroku algorytm porównuje dwa s(cid:200)siednie elementy tablicy i zamienia je miejscami, je(cid:258)li to niezb(cid:218)dne. Na przyk(cid:239)ad w kroku 1. porównywane s(cid:200) warto(cid:258)ci –11 i 12, ale s(cid:200) one umieszczone we w(cid:239)a(cid:258)ciwym porz(cid:200)dku, nie trzeba ich wi(cid:218)c zamienia(cid:202). W kroku 2. porów- nywane s(cid:200) kolejne s(cid:200)siednie elementy (to znaczy 12 i –42). Tym razem te elementy nie s(cid:200) umiesz- czone we w(cid:239)a(cid:258)ciwym porz(cid:200)dku, s(cid:200) wi(cid:218)c zamieniane miejscami. Wspomniane operacje s(cid:200) wyko- nywane wiele razy. Na ko(cid:241)cu, w kroku 72., tablica b(cid:218)dzie posortowana. Algorytm wydaje si(cid:218) bardzo prosty, a jak wygl(cid:200)da jego implementacja? Czy jest równie(cid:285) tak prosta? Na szcz(cid:218)(cid:258)cie tak! Wystarczy u(cid:285)y(cid:202) dwóch p(cid:218)tli, porówna(cid:202) s(cid:200)siednie elementy i w razie konieczno(cid:258)ci zamieni(cid:202) je miejscami. To wszystko! Przyjrzyj si(cid:218) poni(cid:285)szemu listingowi: public static class BubbleSort { public static void Sort T (T[] array) where T : IComparable { for (int i = 0; i array.Length; i++) { for (int j = 0; j array.Length - 1; j++) { if (array[j].CompareTo(array[j + 1]) 0) { Swap(array, j, j + 1); } } } } (...) } Implementacj(cid:218) algorytmu sortowania b(cid:200)belkowego zawiera generyczna metoda statyczna Sort, zadeklarowana w klasie BubbleSort. Jak ju(cid:285) wspomnia(cid:239)em, u(cid:285)yto w niej dwóch p(cid:218)tli for z po- równaniem i wywo(cid:239)aniem metody Swap (zaimplementowanej tak samo jak w przypadku wcze- (cid:258)niej opisanych algorytmów sortowania). Poza tym do przetestowania implementacji mo(cid:285)na wy- korzysta(cid:202) podobny kod, ale trzeba pami(cid:218)ta(cid:202) o zmianie nazwy klasy na BubbleSort. Algorytm sortowania b(cid:200)belkowego daje si(cid:218) zoptymalizowa(cid:202) dzi(cid:218)ki prostej modyfikacji. Opiera si(cid:218) ona na za(cid:239)o(cid:285)eniu, (cid:285)e je(cid:258)li w ci(cid:200)gu jednego przej(cid:258)cia przez tablic(cid:218) nie wykryto (cid:285)adnych zmian, to porównania nale(cid:285)y zatrzyma(cid:202). Oto zmodyfikowany kod: public static T[] Sort T (T[] array) where T : IComparable { for (int i = 0; i array.Length; i++) { bool isAnyChange = false; for (int j = 0; j array.Length - 1; j++) { if (array[j].CompareTo(array[j + 1]) 0) { isAnyChange = true; Swap(array, j, j + 1); } } if (!isAnyChange) { 51 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# break; } } return array; } Dzi(cid:218)ki tej prostej modyfikacji liczb(cid:218) porówna(cid:241) mo(cid:285)na znacznie ograniczy(cid:202). W powy(cid:285)szym przy- k(cid:239)adzie zmniejszy(cid:239)a si(cid:218) ona z 72 do 56. Wi(cid:218)cej informacji na temat sortowania b(cid:200)belkowego oraz jego implementacji mo(cid:285)na znale(cid:283)(cid:202) na stronach: (cid:81) https://pl.wikipedia.org/wiki/Sortowanie_b(cid:200)belkowe. (cid:81) https://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Bubble_sort. Przed przej(cid:258)ciem do omówienia nast(cid:218)pnego algorytmu warto wspomnie(cid:202) o z(cid:239)o(cid:285)ono(cid:258)ci czasowej sortowania b(cid:200)belkowego. Jak ju(cid:285) zapewne zgad(cid:239)e(cid:258), zarówno w najgorszym, jak i (cid:258)rednim przy- padku jest ona taka sama jak w sortowaniu przez wybieranie i wstawianie, czyli O(n2). Sortowanie szybkie Ostatni algorytm sortowania opisany w tej ksi(cid:200)(cid:285)ce nosi nazw(cid:218) sortowania szybkiego (ang. quick- sort). Jest to jeden z popularnych algorytmów „dziel i rz(cid:200)d(cid:283)” (ang. divide and conquer), który dzieli wi(cid:218)kszy problem na zestaw mniejszych. W dodatku oferuje on programistom wydajny sposób sortowania. Czy to znaczy, (cid:285)e jego koncepcja i implementacja s(cid:200) bardzo skomplikowane? Na szcz(cid:218)(cid:258)cie nie! W tym punkcie dowiesz si(cid:218), jak dzia(cid:239)a ten algorytm i jak mo(cid:285)e wygl(cid:200)da(cid:202) jego implementacja. Zaczynajmy! Jak dzia(cid:239)a algorytm? Na pocz(cid:200)tku wybiera pewn(cid:200) warto(cid:258)(cid:202) (na przyk(cid:239)ad z pierwszego lub (cid:258)rodko- wego elementu tablicy) jako element osiowy (ang. pivot). Potem przestawia tablic(cid:218) w taki sposób, aby warto(cid:258)ci mniejsze lub równe elementowi osiowemu by(cid:239)y umieszczone przed nim (tworz(cid:200)c pocz(cid:200)tkow(cid:200) podtablic(cid:218)), a warto(cid:258)ci wi(cid:218)ksze od elementu osiowego po nim (w ko(cid:241)co- wej podtablicy). Ten proces to podzia(cid:239) na partycje (ang. partitioning). W tej ksi(cid:200)(cid:285)ce u(cid:285)ywany jest podzia(cid:239) Hoare’a. Nast(cid:218)pnie algorytm rekursywnie sortuje ka(cid:285)d(cid:200) z wcze(cid:258)niej wymienionych podtablic. Oczywi(cid:258)cie ka(cid:285)da podtablica jest w dalszym ci(cid:200)gu dzielona na nast(cid:218)pne dwie i tak dalej. Rekursywne wywo(cid:239)ania ko(cid:241)cz(cid:200) si(cid:218), je(cid:258)li podtablica ma zero elementów, poniewa(cid:285) wtedy nie ma nic do sortowania. Powy(cid:285)szy opis mo(cid:285)e wydawa(cid:202) si(cid:218) nieco skomplikowany, spójrzmy wi(cid:218)c na przyk(cid:239)ad (zobacz rysunek na nast(cid:218)pnej stronie). Przyk(cid:239)ad ten pokazuje, jak algorytm sortowania szybkiego porz(cid:200)dkuje jednowymiarow(cid:200) tablic(cid:218) o dziewi(cid:218)ciu elementach (–11, 12, –42, 0, 1, 90, 68, 6, –9). W tym przypadku jako warto(cid:258)(cid:202) osiow(cid:200) przyj(cid:218)to warto(cid:258)(cid:202) pierwszego elementu aktualnie sortowanej podtablicy. W kroku 1. jako warto(cid:258)(cid:202) osiow(cid:200) wybrano –11. Konieczne jest przestawienie tablicy po to, by w pocz(cid:200)tkowej 52 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy podtablicy pozosta(cid:239)y tylko warto(cid:258)ci mniejsze albo równe elementowi rozdzielaj(cid:200)cemu (–42, –11), a w ko(cid:241)cowej tylko warto(cid:258)ci od niego wi(cid:218)ksze (12, 0, 1, 90, 68, 6, –9), dlatego –11 jest zamieniane miejscami z –42, a 12 z –11. Potem algorytm jest wywo(cid:239)ywany rekursywnie dla obu podtablic, to znaczy (–42, 11) i (12, 0, 1, 90, 68, 6, –9), te podtablice s(cid:200) wi(cid:218)c poddawane tej samej analizie co tablica wej(cid:258)ciowa. Na przyk(cid:239)ad w kroku 5. jako warto(cid:258)(cid:202) osiow(cid:200) wybrano 12. Podtablica jest dzielona na dwie, to znaczy (–9, 0, 1, 6, 12) i (68, 90). W obu podtablicach wybiera si(cid:218) elementy osiowe, czyli –9 i 68. Po wykonaniu takich operacji we wszystkich pozosta(cid:239)ych fragmentach tablicy uzyskuje si(cid:218) wynik ko(cid:241)cowy, pokazany z prawej strony rysunku (krok 15.). Warto wspomnie(cid:202), (cid:285)e w innych implementacjach tego algorytmu rozmaicie dobiera si(cid:218) element osiowy. Spójrzmy na przyk(cid:239)ad, jak zmieni(cid:200) si(cid:218) kolejne kroki, je(cid:258)li wybierzemy warto(cid:258)(cid:202) (cid:258)rodko- wego elementu: Je(cid:258)li zrozumia(cid:239)e(cid:258) dzia(cid:239)anie algorytmu, zapoznaj si(cid:218) z implementacj(cid:200). Jest ona bardziej skompli- kowana ni(cid:285) w podanych wcze(cid:258)niej przyk(cid:239)adach i przy wywo(cid:239)ywaniu metody sortuj(cid:200)cej podta- blice korzysta z rekurencji (ang. recursion). Kod zosta(cid:239) umieszczony w klasie QuickSort: public static class QuickSort { public static void Sort T (T[] array) where T : IComparable { Sort(array, 0, array.Length - 1); } (...) } 53 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# Klasa QuickSort zawiera dwie odmiany metody Sort. Pierwsza przyjmuje tylko jeden parametr, to znaczy tablic(cid:218) do posortowania, i jest pokazana na powy(cid:285)szym listingu. Jedyne, co robi, to wywo(cid:239)uje drugi wariant metody Sort, pozwalaj(cid:200)cy okre(cid:258)li(cid:202) indeks pocz(cid:200)tkowy i ko(cid:241)cowy frag- mentu tablicy do posortowania. Oto druga wersja metody Sort: private static T[] Sort T (T[] array, int lower, int upper) where T : IComparable { if (lower upper) { int p = Partition(array, lower, upper); Sort(array, lower, p); Sort(array, p + 1, upper); } return array; } Metoda Sort sprawdza, czy tablica (lub podtablica) ma co najmniej dwa elementy, porównuj(cid:200)c warto(cid:258)ci zmiennych lower i upper. Je(cid:258)li tak, wywo(cid:239)uje ona metod(cid:218) Partition, odpowiedzialn(cid:200) za podzia(cid:239) na partycje, a potem rekursywnie wywo(cid:239)uje metod(cid:218) Sort dla obu podtablic, to znaczy pocz(cid:200)tkowej (o indeksach od lower do p) i ko(cid:241)cowej (od p + 1 do upper). Oto kod dziel(cid:200)cy tablic(cid:218) na partycje: private static int Partition T (T[] array, int lower, int upper) where T : IComparable { int i = lower; int j = upper; T pivot = array[lower]; // albo: T pivot = array[(lower + upper) / 2]; do { while (array[i].CompareTo(pivot) 0) { i++; } while (array[j].CompareTo(pivot) 0) { j--; } if (i = j) { break; } Swap(array, i, j); } while (i = j); return j; } Na pocz(cid:200)tku warto(cid:258)(cid:202) osiowa jest wybierana i zapisywana w zmiennej pivot. Jak ju(cid:285) wiesz, mo(cid:285)na j(cid:200) wybra(cid:202) rozmaicie, na przyk(cid:239)ad bior(cid:200)c warto(cid:258)(cid:202) pierwszego elementu (co pokazuje powy(cid:285)szy listing), warto(cid:258)(cid:202) (cid:258)rodkowego elementu (co pokazuje komentarz w powy(cid:285)szym kodzie), a nawet warto(cid:258)(cid:202) losow(cid:200). Nast(cid:218)pnie w p(cid:218)tli do-while tablica jest przekszta(cid:239)cana zgodnie ze sche- matem Hoare’a za pomoc(cid:200) porówna(cid:241) i zamiany elementów. Na koniec jest zwracana aktualna warto(cid:258)(cid:202) zmiennej j. Jak wygl(cid:200)da z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasowa sortowania szybkiego? Czy s(cid:200)dzisz, (cid:285)e jest inna ni(cid:285) w sortowaniu przez wybieranie, wstawianie oraz b(cid:200)belkowym? Je(cid:258)li tak, masz racj(cid:218)! Sortowanie szybkie ma przeci(cid:218)tn(cid:200) z(cid:239)o(cid:285)ono(cid:258)(cid:202) czasow(cid:200) O(n log(n)), cho(cid:202) w najgorszym przypadku wynosi ona O(n2). 54 Poleć książkęKup książkę Rozdzia(cid:225) 2. • Tablice i listy Zaprezentowana implementacja jest oparta na schemacie podzia(cid:239)u na partycje Hoare’a, którego pseudokod i obja(cid:258)nienie przedstawia strona https://en.wikipedia.org/wiki/Quicksort. Istniej(cid:200) ró(cid:285)ne sposoby implementacji sortowania szybkiego. Wi(cid:218)cej informacji mo(cid:285)na znale(cid:283)(cid:202) na stronie https://en.wikibooks.org/wiki/ Algorithm_Implementation/Sorting/Quicksort. Proste listy Tablice s(cid:200) naprawd(cid:218) u(cid:285)ytecznymi strukturami danych i wykorzystuje si(cid:218) je w wielu algorytmach. Niemniej jednak w niektórych przypadkach ich zastosowanie jest skomplikowane, poniewa(cid:285) nie mo(cid:285)na zwi(cid:218)ksza(cid:202) ani zmniejsza(cid:202) wielko(cid:258)ci ju(cid:285) utworzonej tablicy. Co zrobi(cid:202), je(cid:258)li ca(cid:239)kowita liczba elementów do przechowania w kolekcji jest nieznana? Czy utworzy(cid:202) bardzo du(cid:285)(cid:200) tablic(cid:218) i po prostu nie u(cid:285)ywa(cid:202) zb(cid:218)dnych elementów? To rozwi(cid:200)zanie nie wygl(cid:200)da dobrze, prawda? Znacznie lepszym podej(cid:258)ciem jest wykorzystanie struktury danych pozwalaj(cid:200)cej w miar(cid:218) potrzeb dynamicznie zwi(cid:218)ksza(cid:202) rozmiar kolekcji. Lista tablicowa Pierwsz(cid:200) struktur(cid:200) danych, która spe(cid:239)nia to wymaganie, jest lista tablicowa (ang. array list), re- prezentowana przez klas(cid:218) ArrayList z przestrzeni nazw System.Collections. Klasa ta s(cid:239)u(cid:285)y do przechowywania du(cid:285)ych kolekcji danych, do których w razie potrzeby mo(cid:285)na z (cid:239)atwo(cid:258)ci(cid:200) doda(cid:202) nowy element. Oczywi(cid:258)cie da si(cid:218) te(cid:285) usuwa(cid:202) elementy, liczy(cid:202) je oraz znajdowa(cid:202) indeks konkret- nej warto(cid:258)ci zapisanej w li(cid:258)cie tablicowej. W jaki sposób si(cid:218) to robi? Spójrzmy na poni(cid:285)szy kod: ArrayList tablicaList = nowy ArrayList(); tablicaList.Add(5); tablicaList.AddRange(new int[] { 6, -7, 8 }); tablicaList.AddRange(new object[] { Marcin , Maria }); tablicaList.Insert(5, 7.8); W pierwszym wierszu tworzone jest nowe wyst(cid:200)pienie klasy ArrayList. Nast(cid:218)pnie w celu doda- nia nowych elementów do listy tablicowej u(cid:285)ywa si(cid:218) metod Add, AddRange i Insert. Pierwsza z nich (czyli Add) pozwala doda(cid:202) nowy element na ko(cid:241)cu listy. Metoda AddRange dodaje na ko(cid:241)cu listy tablicowej kolekcj(cid:218) elementów, Insert za(cid:258) umieszcza element w podanym miejscu. Po wy- konaniu powy(cid:285)szego kodu lista tablicowa b(cid:218)dzie zawiera(cid:202) nast(cid:218)puj(cid:200)ce elementy: 5, 6, -7, 8, Marcin , 7.8 i Maria . Jak wida(cid:202), wszystkie przechowywane w niej elementy s(cid:200) typu object. Mo(cid:285)na zatem jednocze(cid:258)nie umieszcza(cid:202) w tej samej kolekcji dane ró(cid:285)nych typów. Je(cid:258)li chcesz okre(cid:258)li(cid:202) typ ka(cid:285)dego elementu przechowywanego w li(cid:258)cie, mo(cid:285)esz skorzysta(cid:202) z generycz- nej klasy List, która jest opisana zaraz po ArrayList. 55 Poleć książkęKup książkę Struktury danych i algorytmy w j(cid:266)zyku C# Warto wspomnie(cid:202), (cid:285)e mo(cid:285)na (cid:239)atwo uzyska(cid:202) dost(cid:218)p do konkretnego elementu listy tablicowej, u(cid:285)ywaj(cid:200)c po prostu indeksu, co pokazuj(cid:200) poni(cid:285)sze dwa wiersze kodu: object first = arrayList[0]; int third = (int)arrayList[2]; Przyjrzyjmy si(cid:218) rzutowaniu do typu int w drugim wierszu. Takie rzutowanie jest konieczne, poniewa(cid:285) lista tablicowa przechowuje warto(cid:258)ci typu object. W celu uzyskania dost(cid:218)pu do kon- kretnych elementów kolekcji tak samo jak w przypadku tablic u(cid:285)ywa si(cid:218) indeksów zaczynaj(cid:200)cych si(cid:218) od zera. Do przej(cid:258)cia przez wszystkie elementy mo(cid:285)na oczywi(cid:258)cie skorzysta(cid:202) z p(cid:218)tli foreach: foreach (object element in arrayList) { Console.WriteLine(element); } To nie wszystko! Klasa ArrayList ma zestaw w(cid:239)a(cid:258)ciwo(cid:258)ci i metod, których mo(cid:285)na u(cid:285)y(cid:202), opraco- wuj(cid:200)c aplikacje korzystaj(cid:200)ce z tej struktury danych. Na pocz(cid:200)tek przyjrzyjmy si(cid:218) w(cid:239)a(cid:258)ciwo(cid:258)ciom Count i Capacity: int count = arrayList.Count; int capacity = arrayList.Capacity; Pierwsza z nich (Count) zwraca liczb(cid:218) elementów listy tablicowej, a druga (Cap
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Struktury danych i algorytmy w języku C#. Projektowanie efektywnych aplikacji
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ą: