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 poważnie pragnący 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.

W języku C++ i Python zostały opracowane specjalne biblioteki implementujące opisane tutaj struktury danych, jednakże nie będziemy z nich korzystać w tym artykule, aby zachować podobieństwo programów w wybranych językach programowania. Co więcej, wybrany przez znasz sposób uczy działania algorytmów operujących na strukturach danych, co później znakomicie ułatwia zrozumienie funkcji bibliotecznych.

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 (i dodatkowo Python) wybranych środowiskach programowania:

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

Wszystkie trzy są darmowe, pracują w środowiskach Windows i 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 aplikacji Geany lub Code Blocks), które są legalne i możliwe do pobrania 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.

Ponieważ opracowanie to zostało specjalnie przystosowane do smartfonów, programy napisano w sposób kompaktowy, aby można je było w miarę wygodnie przeglądać na małych ekranach. Nie wpływa to w żaden sposób na ich działanie.

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.

Jako dodatek w artykule umieściliśmy przykładowe programy w języku Python, ponieważ wszedł on w zakres nauczania informatyki w szkole średniej i pojawił się na maturze jako alternatywa dla języka C++. Programy te należy uruchamiać w aplikacjach IDLE, PyCharm lub podobnych.

Ponieważ programy napisano tak, aby w miarę wygodnie można je było przeglądać na małych ekranach smartfonów, to niektóre środowiska IDE mogą generować ostrzeżenia o braku spacji lub pustych wierszy. Nie są to błędy i nie powodują one złego działania programu.

W celu poprawy czytelności kodu w języku Python stosuje się zwykle kilka umów, np.:

• Nazwy zmiennych, atrybutów, funkcji tworzone małymi literami.
• Nazwy klas rozpoczynane dużą literą
• Nazwy stałych tworzone dużymi literami.
• Definicje rozdzielone dwoma pustymi wierszami.
• Po przecinku stosowana spacja.
• W komentarzach po znaku # stosowane dwie spacje (u nas używamy jednej spacji, aby zaoszczędzić miejsce na ekranie smartfona).

Również nazwy funkcji i argumentów staraliśmy się zachować podobne we wszystkich środowiskach programowania.

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 i Python 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  programem 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; programy Pythona można uruchamiać z konsoli: py nazwa_programu.py lub z Eksploratora plików jak każdy inny program), 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:

Pascal

:

readln;

C++

:

system("pause");

Basic

:

Sleep

Python

:

input("Naciśnij klawisz Enter")

Uwaga: Okno konsoli powinno mieć szerokość 80 znaków (standard). Jeśli szerokość ta jest inna, to niektóre programy mogą źle wyświetlać wyniki. Należy wtedy je odpowiednio skorygować, lub ustawić szerokość okna konsoli na 80 znaków-należy kliknąć prawym przyciskiem myszki pasek tytułowy okna konsoli i z menu wybrać opcję Właściwości:

Pojawi się wtedy okienko dialogowe, w którym można ustawiać różne parametry okna konsoli. Przejdź na zakładkę Układ i ustaw odpowiednią szerokość okienka:

Wszystkie algorytmy opisane w tym artykule są przedstawione w postaci listy kroków oraz implementacji w czterech środowiskach programowania: FreePascal, Code::Blocks, FreeBasic oraz  Python . 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:

zmienna ← wyrażenie

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

zmienna1 ←→ zmienna2

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

Jeśli warunek, 
to oparacja1, 
inaczej operacja2

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.

Dla zmienna = a, b, …, n:
wykonuj operacja

Dla zmienna = a, b, …, n:
wykonuj kroki Kxx…Kyy

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.

Dopóki warunek, 
wykonuj operacja

Dopóki warunek, 
wykonuj kroki Kxx…Kyy

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.

Idź do kroku Kxx

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

Następny obieg pętli Kxx

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

Pisz wyrażenie

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

Czytaj zmienna[, zmienna]

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.

Zakończ

Kończy działanie algorytmu

Zakończ z wynikiem x

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

Opis słowny

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