Informacja jest przechowywana przez komputer w różnych strukturach danych. Niniejszy artykuł opisuje podstawowe algorytmy operujące na różnych strukturach danych, z którymi najczęściej spotyka się programista we współczesnej informatyce. Lista algorytmów i struktur danych w żadnym wypadku nie jest kompletna (jest to technicznie i czasowo niemożliwe do zrealizowania z uwagi na obszerność problemu ), starałem się jedynie wybrać dla każdej z opisywanych tutaj struktur danych typowe algorytmy wykorzystujące daną strukturę. Dobór właściwej struktury danych dla określonego algorytmu jest jedną z podstawowych umiejętności, które musi opanować każdy informatyk, który poważnie pragnie zajmować się swoją dziedziną. Od tego doboru zależy wiele rzeczy, np. efektywność algorytmu, a zatem czas jego wykonania na określonym komputerze, wymagania pamięciowe, złożoność operacji itp.

Mam nadzieję, że podane tutaj informacje pomogą w takim doborze.

Omawiane w artykule algorytmy są zawsze przedstawione w postaci listy kroków wraz ze specyfikacją danych wejściowych i wyjściowych. Przykładowe implementacje algorytmów zrealizowaliśmy w trzech wybranych środowiskach programowania:

• Pascal ( Lazarus )
• C++ ( Code::Blocks )
• Basic ( Free Basic )

Wszystkie trzy są darmowe, pracują w środowisku Windows/Linux (w Linuxie instaluje się tylko same kompilatory Free Pascala oraz Free Basica ( kompilator C++ jest zawsze dostępny w Linuxie )  a jako IDE używać można Geany lub Code Blocks) i można je legalnie pobrać w sieci z witryny producenta, co polecamy niezwłocznie uczynić. Przykłady programów w tych językach nie są celem tego opracowania (jak sądzą niektórzy czytelnicy ). Są nim algorytmy i na nich głównie skupiamy uwagę. Znając działanie algorytmu można go zaimplementować w dowolnym języku programowania. Dlatego nie żądajcie od nas przesyłania przykładów w dialektach powyższych języków, czy też w innych językach programowania – tym nie zajmujemy się z braku czasu oraz wszechwiedzy.

Niekiedy dodaliśmy również przykład w języku skryptowym JavaScript, który pozwala czytelnikowi interaktywnie sprawdzić omawiane zagadnienia. Jednakże w przypadku JavaScript nie bawimy się w prezentację kodu w artykule. Dostęp do kodu JavaScript można w prosty sposób uzyskać przeglądając źródło strony WWW, co potrafi wykonać praktycznie każda współczesna przeglądarka.

Wszystkie przykłady programów będą uruchomione w trybie konsoli. Cechą charakterystyczną tego trybu jest okno tekstowe (w Linuxie jest to okno terminala ), które służy zarówno do wprowadzania jak i do wyprowadzania danych. Zaletą jest prostota komunikacji z użytkownikiem. W języku Pascal wykorzystuje się polecenia writeln i write do zapisu oraz readln i read do odczytu danych. W języku C++ można w tym charakterze wykorzystywać obiekty biblioteki STL cout oraz cin. W języku Basic stosowane są polecenia print i input.

Dane wprowadzane do programu pracującego w trybie konsoli mogą pochodzić z kilku źródeł. Pierwszym z nich jest oczywiście klawiatura. Jednakże wpisywanie długich ciągów liczb, szczególnie gdy muszą się one powtarzać przy testowaniu działania programu, jest niewygodne. W takiej sytuacji mamy dwa wyjścia:

1. Dane wklejamy do okna konsoli poprzez schowek Windows. W notatniku przygotowujemy sobie odpowiednie liczby do wprowadzenia do programu, następnie kopiujemy je do schowka Windows i wklejamy do okna konsoli. W tym celu klikamy w okienko konsoli prawym przyciskiem myszki i z menu kontekstowego wybieramy polecenie Wklej. Wybierając polecenie Oznacz, a następnie zaznaczając myszką obszar w oknie konsoli i wciskając na koniec klawisz Enter, można skopiować do schowka treść okna konsoli. Poniższy tekst pochodzi z takiej właśnie operacji:

   C:\>date Bieżąca data: 2008-03-05 Wprowadź nową datę: (rr-mm-dd) C:\>time Bieżąca godzina: 22:10:08, 84 Wprowadź nową godzinę: C:\>

2. Przy uruchamianiu programu przekierowujemy jego standardowe wejście lub wyjście do pliku zamiast na konsolę. W tym celu wystarczy wydać polecenie:
   

   nazwa_programu < plik_wejścia > plik_wyjścia

   Załóżmy na przykład, iż napisaliśmy program o nazwie szukaj.exe. Jeśli dane wejściowe dla programu przygotowaliśmy w pliku d_we.txt, a dane wyjściowe chcemy otrzymać w pliku d_wy.txt, to wydajemy następujące polecenie:
   

   szukaj < d_we.txt > d_wy.txt

   Program uruchamiamy w opisany powyżej sposób z okna konsoli. W tym celu należy kliknąć przycisk Start i w opcji uruchom wpisać polecenie cmd. Polecenie to otwiera okno konsoli i umożliwia użytkownikowi wprowadzanie z klawiatury różnych rozkazów systemu operacyjnego. Przy pomocy polecenia cd przechodzimy do katalogu z projektem i wydajemy wyżej opisane polecenia. Program, który ma być uruchamiany w takim trybie nie powinien przy zakończeniu czekać na reakcję użytkownika – po prostu czyta dane, przetwarza je, wyprowadza wyniki i kończy działanie. Tak właśnie pracują nasze przykłady.

Jeśli często wykorzystujesz uruchamianie z przekierowaniem standardowego wejścia/wyjścia do tych samych plików z danymi, to rozważ stworzenie prostego pliku batch – pliku skryptowego z rozszerzeniem bat lub cmd, w którym po prostu umieszcza się kolejne polecenia do wykonania. Plik batch zapisuje się następnie w katalogu projektu pod jakąś krótką nazwą – ja stosuję !.cmd i w konsoli wystarczy wpisać !, aby uruchomić kolejne polecenia zawarte w pliku !.cmd. Proste i wygodne. Przykładowy plik batch !.cmd może wyglądać tak:

@echo off
cls
echo Test aplikacji SZUKAJ.EXE
echo Odczyt danych, przetwarzanie i zapis wynikow, prosze czekac...
echo.
szukaj < s_we.txt > d_wy.txt
echo Koniec przetwarzania.
type d_wy.txt
echo.

Prezentowane w artykule programy są maksymalnie uproszczone – odczytują wymagane dane wejściowe, przetwarzają je i wypisują wyniki beż żadnych dodatkowych upiększeń. Mogą one być materiałem do dopracowania na lekcji lub kole informatycznym – np. uczniowie dopisują do nich odpowiedni interfejs komunikacji z użytkownikiem. Wszystko zależy zatem od nauczyciela. Aplikacje te należy uruchamiać z poziomu okna konsoli (Start → Uruchom → cmd ), ponieważ nie będą czekały na reakcję użytkownika przy zakończeniu działania – uruchomienie ich z poziomu Windows spowoduje zamknięcie okienka konsoli przy zakończeniu programu, zatem zapewne nie zdążysz nic przeczytać. W takiej postaci programy tworzy się zwykle na wszelkiego rodzaju konkursach, w tym na olimpiadzie informatycznej. Dlatego i my wybieramy ten sposób.

Jeśli jednak chciałbyś pracować w środowisku Windows, to możesz dodać na końcu programu następujące polecenia wstrzymujące zamknięcie okna konsoli, aż do naciśnięcia klawisza Enter:

Wszystkie algorytmy opisane w tym artykule są przedstawione w postaci listy kroków oraz implementacji w trzech językach programowania: FreePascal, Code::Blocks oraz FreeBasic. Lista kroków zawsze jest poprzedzona specyfikacją algorytmu zbudowaną z następujących trzech sekcji:

• Dane wejściowe – określa dane, które algorytm będzie przetwarzał. W opisie algorytmu pomijamy odczyt tych danych – po prostu zakładamy, iż będą one w jakiś sposób dostępne.
• Dane wyjściowe – określa wynik pracy algorytmu, czyli co algorytm wyprodukuje podczas swojej pracy.
• Dane pomocnicze: – jeśli algorytm wymaga dodatkowych zmiennych lub funkcji, to tutaj zostają one opisane. Są to wewnętrzne zmienne algorytmu.

Na liście kroków używamy następujących konstrukcji algorytmicznych:

Operacja przypisania. Wartość wyrażenia zostaje umieszczona w zmiennej.

Zamiana zawartości. Po operacji zmienna₁  będzie zawierała to co zmienna₂, a zmienna₂  to co zmienna₁.

Jest to typowa instrukcja warunkowa. Jeśli warunek będzie spełniony, to zostanie wykonana operacja₁ (operacja₂ nie będzie wykonana ). Jeśli warunek nie będzie spełniony, to zostanie wykonana operacja₂ (teraz operacja₁ nie będzie wykonana ). Jeśli brak członu inaczej, to algorytm przechodzi do następnego kroku. Konstrukcja ta umożliwia tworzenie rozgałęzień w algorytmie. Czasami zamiast pojedynczej operacji podajemy ich ciąg rozdzielony przecinkami.

Jest to konstrukcja pętli iteracyjnej. Dla kolejnych wartości zmiennej  równych a, b..., c wykonywana jest wskazana operacja lub wykonywane są kroki w zakresie od Kxx do Kyy. Kroki wykonywane są kolejno od góry do dołu. Gdy pętla się zakończy wykonywany jest krok Kyy + 1 – znajdujący się za ostatnią z powtarzanych instrukcji. Dodatkowo w obrębie pętli stosujemy wcięcia, aby poprawić czytelność tej konstrukcji.

Jest to konstrukcja pętli warunkowej. Jeśli warunek jest prawdziwy, to wykonywana jest operacja lub kolejne kroki od Kxx do Kyy. Kroki wykonywane są kolejno od góry do dołu. Po ostatnim kroku Kyy warunek jest ponownie testowany i w przypadku jego spełnienia, kroki Kxx ... Kyy są wykonywane ponownie. Gdy pętla się zakończy wykonywany jest krok Kyy+1 – za ostatnią z powtarzanych instrukcji. W przypadku, gdy warunek jest nieprawdziwy przed wejściem do pętli, nie zostanie wykonany żaden krok od Kxx do Kyy – algorytm przejdzie do kroku Kyy+1.

Następnym krokiem wykonywanym przez algorytm będzie krok Kxx.

Algorytm przejdzie do wykonania kolejnego obiegu pętli zdefiniowanej w kroku Kxx. Przed rozpoczęciem obiegu sprawdzane są odpowiednie warunki kontynuacji pętli:

– dla pętli warunkowej warunek kontynuacji musi być prawdziwy
– dla pętli iteracyjnej zmienna sterująca otrzymuje kolejną wartość i, jeśli mieści się ona w zakresie, to pętla wykonuje kolejny obieg.

Algorytm wyprowadza na wyjście wartość wyrażenia.

Algorytm odczytuje z wejścia dane dla podanej zmiennej. Tam, gdzie dane wejściowe są oczywiste i opisane w specyfikacji, pomijamy ich odczyt w algorytmie.

Kończy działanie algorytmu

Kończy działanie algorytmu z wynikiem x – ta postać zakończenia jest używana w algorytmach funkcji.

Niektóre operacje algorytmu muszą być opisane słownie, ponieważ ich wykonanie zależy od specyfiki używanego języka programowania lub też wymaga wielu operacji prostych.

W wyrażeniach stosujemy następujące operatory:

+ - × :	podstawowe operacje arytmetyczne
sqr ( w )	pierwiastek kwadratowy z w
mod	reszta z dzielenia całkowitoliczbowego
div	dzielenie całkowite
	operacja logiczna alternatywy
	operacja logiczna koniunkcji
	operacja logiczna sumy symetrycznej
¬	operacja logiczna negacji
and	bitowa operacja koniunkcji
or	bitowa operacja alternatywy
not	bitowa operacja negacji
xor	bitowa operacja sumy modulo 2
shr	przesunięcie bitowe w prawo
shl	przesunięcie bitowe w lewo
[ w ]	część całkowita z w
floor ( w )	zaokrąglenie w dół do najbliższej liczby całkowitej
ceil ( w )	zaokrąglenie w górę do najbliższej liczby całkowitej
< ≤ = ≠ ≥ >	operatory porównań
→	wskazanie pola struktury
.	odwołanie do pola struktury

Zapraszam do lektury
mgr Jerzy Wałaszek