Wykład (30 godzin) + laboratorium (30 godzin)
Celem zajęć jest prezentacja technik programistycznych i struktur danych wykorzystywanych w programowaniu w małej i średniej skali.
Kiedy chcemy skorzystać z dodatkowej pamięci, nie wiedząc z góry ile nam jej będzie potrzeba i uzależniając jej ilość od danych, których wartości nie są znane, wygodnie jest używać mechanizmu dynamicznej alokacji pamięci. Podstawy alokacji dynamicznej pamięci zostały omówione w rozdziale Pamięć dynamiczna.
Bardzo wygodną strukturą danych są listy, czyli struktury, które umożliwiają tworzenie ciągów danych w taki sposób, że każda dana pamięta gdzie się znajduje kolejna.
Zanim zdefiniujemy listy, zastanówmy się, dlaczego trudno jest zrealizować następujący pomysł sortujący dane w tablicy. Ponieważ umiemy szybko wyszukiwać w posortowanym ciągu miejsce, w które należy wstawić daną wartość tak, aby nie popsuć posortowania, więc można sobie wyobrazić następujący szybki algorytm sortujący.
Dane: ciąg \(\alpha=\langle a_1,\ldots,a_n\rangle\) elementów z dziedziny A oraz relacja ≤ liniowo porządkująca dziedzinę A.
Cel: Posortować ciąg \(\alpha\), czyli tak poprzestawiać jego elementy, żeby następowały po sobie w kolejności niemalejącej.
Szukamy zatem takiego ciągu \(\beta=b_1,\ldots,b_n\), żeby był on permutacją ciągu \(\alpha\) oraz żeby \(\forall 1\le k <n: b_i\le b_{i+1}\).
Rozszerzmy ciąg \(\beta\) z lewej strony o element \(b_0=-\infty\), czyli załóżmy, że ciąg \(\beta\) zaczyna się od minus nieskończoności, pełniącej rolę strażnika.
Rozwiązanie:
Niech \(\beta_1=\langle -\infty,a_1 \rangle\) będzie dwuelementowym ciągiem złożonym ze strażnika oraz z pierwszego elementu ciągu a.
for i:=2 to n do {ciąg \(\beta_{i-1}\) składa się z posortowanych elementów \(b_0,a_1,...,a_{i-1}\)} begin znajdź taki indeks j, żeby \(1\le j<i\) oraz żeby \(b_{j-1}\le a_i \le b_j\) wstaw \(a_i\) między \(b_{j-1},\) a \(b_j\) end
Ten algorytm w pseudokodzie nie jest wcale tak łatwy do efektywnego zaimplementowania. Przyjrzyjmy się dziedzinie algorytmicznej, w której jest określony. Aby go zrealizować potrzebne są dwie operacje: znajdowania indeksu, pod który powinien trafić kolejny element ciągu a oraz wstawienia elementu we wskazane miejsce ciągu: "wepchnięcia" go między dwa istniejące elementy.
Spróbujmy przymierzyć się do zaimplementowania podanego algorytmu, przy założeniu, że właściwy ciąg \(a\) jest reprezentowany w tablicy A[1..n].
Pierwsza operacja – znajdowania stosownego indeksu – jest dość prosta: wystarczy zastosować algorytm wyszukiwania binarnego i jako efekt uboczny dostaniemy indeks j, po którym należy wstawić nasz element. Podany poniżej algorytm wyszukiwania binarnego znajduje indeks ostatniego wystąpienia elementu mniejszego lub równego A[i] – jest to miejsce, w którym element A[i] powinien się pojawić. Przedstawiony algorytm jest nieco zmodyfikowanym algorytmem wyszukiwania binarnego. Strażnik \(-\infty\) na pozycji 0 pełni swą rolę, gdy wstawiany element jest najmniejszy z dotychczasowych – zawsze wtedy wstawiamy nowy element za jakimś już istniejącym. Dzięki niemu nasz algorytm stanie się jednorodny: zawsze wstawiany element będzie znajdował swoje miejsce po jakimś już istniejącym. Tu rolę zmiennej n pełni i, ponieważ algorytm uruchamiamy wielokrotnie dla kolejnych wartości i:
A[0]:=-nieskonczonosc; l:=0; p:=i-1; {szukamy elementu PO którym chcemy wstawić A[i], zatem ostatniego, który jest mniejszy lub równy A[i]} while l < p do \(\{Sort(A[1..i-1) \land (1\le l\le p < i) \land (\forall p< k <i: A[k]> A[i]) \land (\forall 1\le k <i: A[k]\le A[i] \rightarrow k\le l)\}\) begin s:=(l+p+1) div 2; if A[i] >= A[s] then l:=s else p:=s+1 end;
Wychodzimy z pętli przy l=p, więc nasz niezmiennik gwarantuje to, że na prawo od p i na lewo od i (z wyłączeniem p oraz i) są elementy większe od A[i], zaś do l włącznie są mniejsze lub równe A[i]. Element A[i] należy zatem wstawić pomiędzy A[l] a A[l+1]. Tylko jak to zrobić? Tablica nie może tak nagle spuchnąć i zrobić sobie jedno dodatkowe miejsce gdzieś w środku na ten nowy element. To, co można zrobić, to tylko przesunąć mozolnie wszystkie elementy od j na prawo o jedną pozycję w prawo i dopiero wtedy, gdy zrobi się wolne miejsce na A[i], wstawić tam tę wartość.
Ćwiczenie:
Zaprogramuj tę część algorytmu.
Rozwiązanie:
v:=A[i]; for k:=i-1 downto p do A[k+1]:=A[k]; A[p]:=v
Tyle, że samo przesuwanie zajmie nam w średnim przypadku i/2 obrotów pętli, a cały algorytm będzie kwadratowy ze względu na n. Zatem to, co zarobiliśmy w pierwszej fazie, tracimy w drugiej, kiedy okazuje się, że operacja wciśnięcia nowego elementu do ciągu jest kosztowna. Na dobrą sprawę można powiedzieć, że niepotrzebnie robiliśmy pierwszą fazę; można było od razu zacząć od przesuwania elementów kończąc na pierwszym mniejszym lub równym A[i] i tam go wstawić. Taki algorytm nazywa się algorytmem sortowania przez proste wstawianie i jest całkiem dobrym algorytmem dla niewielkich danych, ale o złożoności kwadratowej – zarówno pesymistycznej, jak i średniej.
Widzimy więc, że w tablicach wyszukiwanie w ciągu posortowanym jest tanią operacją, natomiast wstawianie nowego elementu w środek ciągu – kosztowną. Poznamy teraz strukturę danych, reprezentującą ciągi, dla której będzie dokładnie na odwrót: wyszukiwanie będzie stosunkowo kosztowne, za to wstawianie tanie. Struktura ta będzie miała dodatkową cechę odróżniającą ją od tablic: długość reprezentowanego ciągu nie będzie musiała być z góry ustalona. Jest to niezwykle ważna cecha, gdyż w przypadku tablic musimy zazwyczaj przewidzieć zawczasu, jaka będzie długość ciągu i zadeklarować tablicę stosownego rozmiaru, być może godząc się na nieoszczędność pamięci, jeśli całej tablicy nie wykorzystamy.
Zbiór list \(L(A)\) nad pewnym zbiorem A definiujemy, jako najmniejszy zbiór spełniający następujące warunki:
Do reprezentacji list użyjemy zmiennych dynamicznych. Są one bardzo wygodne, gdyż można je alokować w czasie wykonywania programu i na tyle elastyczne, że umożliwiają łatwe dokonywanie wszystkich interesujących nas operacji. Zatem w składni Pascala można typ listowy zdefiniować następująco. Niech typA reprezentuje zbiór A.
type lista = ^elementlisty; elementlisty=record w: typA; nast: lista; end;
Przyjmijmy do końca tego wykładu, że typA=Integer. Będziemy więc mieli do czynienia z listami liczb całkowitych.
Powyższa definicja może nieco niepokoić. Definiujemy typ lista odwołując się do elementu listy, o którym za chwilę się dowiadujemy, że w jego definicji występuje z powrotem lista. Nastąpiło tu złamanie starej arystotelesowskiej zasady, że wolno definiować nowe pojęcia tylko za pomocą aksjomatów (czyli pojęć pierwotnych) lub pojęć już zdefiniowanych. Na szczęście wszystko jest w porządku, jeśli zdamy sobie sprawę z tego, że typ wskaźnikowy jest tak naprawdę adresem – adresem zaalokowanej zmiennej pokazującej na obiekt danego typu. Zatem typ lista jest adresem komórki o dwóch polach: pierwsze z nich zawiera wartość reprezentowaną przez typA, a drugie adres. Tak też tego rodzaju definicje traktuje kompilator Pascala i nie ma problemu z kompilacją takiego pseudozapętlenia definicji.
Lista jest zatem reprezentowana, jako wskaźnik do rekordu o dwóch polach: w pierwszym polu jest reprezentowany element danego typu, a w drugim wskaźnik do następnego elementu listy. Wyróżnioną wartością wskaźnika jest nil, który tu oznacza pustą listę. Przeważnie lista kończy się nilem. Inne możliwości, to
Ponadto warto zauważyć, że listy mogą się zbiegać i dla dwóch różnych początków mieć tę samą końcówkę.
Spróbujmy podać teraz parę rozwiązań podstawowych zadań związanych z przetwarzaniem list.
Zadanie 1.
Stwierdź, czy w liście znajduje się element o wartości x.
Rozwiązanie 1:
function jest_rek(l:lista; x:typA):Boolean; {przyjmuje wartość true wtedy i tylko wtedy, gdy w liście l znajduje się wartość x} begin if l=nil then jest_rek :=false else if l^.w = x then jest_rek := true else jest_rek := jest_rek(l^.nast,x) end;
Warto skomentować to rozwiązanie. Zauważmy, że na początku sprawdzamy, czy lista l aby nie jest pusta. Jest to konieczne, gdyż próba odwołania się do jakiegokolwiek pola listy pustej powoduje błąd i przerwanie programu – dla pustej listy wywołanie tej funkcji dałoby właśnie taki efekt. Początkowy test niepustości listy jest zalecany jako standardowy przy pracy z listami.
Reszta jest już w miarę prosta: jeśli lista jest niepusta, to szukana wartość jest albo w pierwszym elemencie, albo w ogonie listy; ten pierwszy przypadek badamy wprost, ten drugi – korzystając z rekurencji.
Od razu może ustalmy, że takie rekurencyjne rozwiązanie tego typu problemów nie jest zalecane. W ogóle w imperatywnych językach nadużywanie rekursji w przypadku prostych list jest niewskazane. Dodatkowe koszty organizacji rekurencji nie usprawiedliwiają zysku, jaki płynie z prostoty rozwiązania. Przedstawiamy zatem kolejną wersję – iteracyjną – rozwiązującą ten sam problem:
Rozwiązanie 2:
function jest_iter(l:lista; x:typA):Boolean; {podaje wartość true wtedy i tylko wtedy, gdy w liście l znajduje się wartość x} begin if l=nil then jest_iter :=false else begin while (l^.nast<>nil) and (l^.w <> x) do {aż do l wyłącznie nie ma x} l := l^.nast; jest_iter := l^.w = x end end;
Ćwiczenie. Udowodnij poprawność podanego kodu.
Ten kod wymaga znowu paru komentarzy.
Po pierwsze zauważmy, że kiedy przechodzimy wewnątrz funkcji ze wskaźnikiem l po liście, nie jesteśmy sie w stanie cofnąć. Niby nie mamy po co, ale czy nie tracimy dowiązania do początku listy? Otóż nie! Zawdzięczamy to wywołaniu parametru l przez wartość – działamy na jego kopii, zatem procedura wywołująca funkcję jest_iter po jej zakończeniu będzie miała oryginalną wartość l.
Po drugie, można by zapytać, po co tak się męczyć z następnikiem: czy nie wystarczy iść do przodu aż albo znajdziemy x, albo l stanie się równe nil? Innymi słowy chodziłoby tu o taką wersję naszej funkcji:
function jest_iter_leniwie (l:lista; x:typA):Boolean; {podaje wartość true wtedy i tylko wtedy, gdy w liście l znajduje się wartość x} begin while (l<>nil) and (l^.w <> x) do l := l^.nast; {aż do l wyłącznie nie ma x} jest_iter_leniwie := l <> nil {Zwróćmy uwagę na inny warunek ustalający wartość funkcji} end;
W wersji tej oszczędzamy sobie początkowego sprawdzenia nila – robi się to przy okazji testowania warunku wejścia do pętli – oraz być może dwukrotnego sprawdzenia czy wartość elementu listy równa się x (w poprzedniej wersji zawsze tak się działo, jeśli x wystąpił w liście!). Rozwiązanie to też jest poprawne, ale tym razem warunkowo – aby takie było, musi być włączona opcja tzw. leniwego sprawdzania złożonych warunków logicznych.
Przypomnijmy: leniwe wyliczanie polega na tym, że kompilator gdy tylko jest w stanie przewidzieć wynik formuły logicznej, przerywa jej dalsze obliczanie. Dzieje się tak w szczególności, gdy w koniunkcji jednym (i to nieostatnim) z czynników logicznych jest fałsz, lub – analogicznie – gdy w przypadku alternatywy jednym ze składników logicznych jest prawda. Musimy sobie zdać sprawę z tego, że logika wyrażeń logicznych w językach programowania jest trójwartościowa: poza prawdą lub fałszem mamy jeszcze wartość trzecią – nazwijmy ją niewiadomoco – gdy warunku nie udało się obliczyć, np. z powodu błędu. Jeżeli w logice wyrażeń komputerowych oznaczymy prawdę przez 1, fałsz przez 0, a niewiadomoco przez ?, to zakładamy, że działają tu następujące prawa dla alternatywy i koniunkcji:
\(1 \land ? = ?, ?\land 1 = ?, 0\land ? = 0, ? \land 0 = ?// 1 \lor ? = 1, ?\lor 1 = ?, 0\lor ? = ?, ? \lor 0 = ?\)
oraz prawo negacji
\(\neg ? = ?\)
Innymi słowy: jeśli zdąży się wyliczyć wartość ?, to niezależnie od reszty formuły wynikiem wyrażenia będzie ?. Jeśli natomiast w koniunkcji napotkamy 0 przed ? lub w alternatywie 1 przez ?, to formuła wyliczy się do klasycznej wartości logicznej – odpowiednio 0 lub 1. Zapamiętajmy:
Ani alternatywa, ani koniunkcja w leniwej logice trójwartościowej nie są przemienne!
Ćwiczenie
Czy błąd jest jedyną sytuacją, której warto przypisać wartość '?'.
Odpowiedź:
Nie, analogiczny efekt uzyskamy, gdy w czasie wyliczania warunku logicznego program się zapętli (np. wywołując funkcję logiczną). Proszę sprawdzić, że podane reguły logiczne dotyczące operatora ? są sensowne semantycznie w przypadku zapętlenia.
Leniwa logika pojawia się jako domniemana w pewnych językach programowania, np. w C, Javie. Jednak w Pascalu leniwego wyliczania nie ma w standardzie, więc musimy zachować szczególną ostrożność przy korzystaniu z tego narzędzia i mieć absolutną pewność, że opcja leniwego wyliczania wartości logicznych jest dostępna i włączona, gdy z niej korzystamy. Poprzednia wersja algorytmu, choć może nieco bardziej chropawa, była bezpieczna: w każdej realizacji Pascala zadziała. Jeżeli nie ma wyraźnych powodów, aby postępować inaczej, należy preferować rozwiązania zgodne ze standardem.
Zadanie 2
Wstaw do posortowanej listy l nowy element o wartości x, zachowując posortowanie l.
Rozwiązanie 1
Aby wstawić nową wartość do posortowanej listy, musimy znaleźć element ZA którym ją wstawimy (trzeba mu będzie zmienić pole nast). Pamiętajmy jednak, że po pierwsze o tym, że już pora wstawiać dowiadujemy się będąc już w jego następniku, bo dopiero następnik tego elementu bedzie większy lub równy wstawianej wartości. Po drugie nie zawsze tak element istnieje.
Ćwiczenie
Kiedy do posortowanej listy nie wstawiamy za jakimś elementem?
Rozwiązanie
Wtedy gdy wstawiany element jest najmniejszy z występujących na liście (w szczególności, gdy lista l jest pusta).
Napiszmy najpierw procedurę, z której często będziemy korzystali i która wstawia do listy element o wartości x za elementem wskazywany przez zmienną wsk. Zauważymy przy okazji wspomnianą na początku wykładu różnicę między wstawianiem do tablicy, a wstawianiem we wskazane miejsce wewnątrz listy. Zakładamy tu, że element wsk istnieje (czyli jest różny od nil).
procedure wstawZA(wsk:lista; x:typA); {wstawiamy wartość x do listy za element wskazywany przez wsk} var pom:lista; begin new(pom); pom^.nast:=wsk^.nast; pom^.w := x; wsk^.nat:=pom end;
Teraz zasadnicza procedura wstawiająca.
procedure wstaw_sort (var l:lista; x:typA); {do posortowanej listy l wstawia wartość x. Parametr l musi być przekazany przez zmienną, gdyż wartość l może się zmienić w przypadku wstawiania najmniejszej wartości do listy – lista będzie miała inny początek} var akt,next: lista; {akt – aktualny, next – następnik akt} begin if' l<>nil then begin {tu nietypowo akurat łatwiej jest napisać kod począwszy od ,,trudniejszego<i> przypadku, gdy lista jest niepusta}</i> akt := l; next := akt^.nast; if (next = nil) and (l^.w<x) then wstawZA(l,x) else begin while (next^.nast<>nil) and (next^.w<x) do begin akt:=next; next:=akt^.nast end; if x<=next^.w then wstawZA(akt,x) else {przerwaliśmy pętlę ze względu na koniec listy i nasza wartość powinna być wstawiona na koniec} wstawZA(next,x) end else {lista jest pusta lub pierwszy element listy jest większy lub równy x} begin akt:=l; {w szczególności może być nil} new(l); l^.w := x; l^.nast := akt end {Zauważmy, że ten sam kod dotyczy pustej listy, jak i przypadku, gdy naszą wartość wstawiamy na początku listy} else wstawZA(l,x) end;
Trzeba przyznać, że kod wyszedł dość obskurny – tutaj kłopot sprawiły nam dwie rzeczy: szczególne przypadki listy pustej i jednoelementowej oraz to, że trzeba było cały czas iść dwoma wskaźnikami, pilnując żeby ten z przodu nie stał się nilem, a zarazem badając jego wartość. Oczywiście użycie leniwego wyliczania tę część by uprościło, ale trzymajmy się na razie standardu.
Poznamy teraz technikę, za pomocą której przynajmniej pierwszy ze wspomnianych kłopotów zniknie.
Ponieważ pewne zamieszanie w jednorodności algorytmu wynikało z potencjalnej pustości listy, więc spróbujmy tak zadziałać, żeby ciąg pusty był reprezentowany przez niepustą listę. Wprowadzimy zatem dodatkowy element na początku listy, atrapę, której jedynym zadaniem będzie posiadanie pola nast – po to, aby było za czym wstawiać nowy element, nawet na początku listy. Tworzenie pustego ciągu wartości zamiast wyglądać tak:
l:= <b>nil</b>
będzie wyglądać tak:
new(l); l^.nast:=nil
Pole w atrapy nie ma znaczenia, więc go nawet nie inicjalizujemy.
Zobaczmy, jak uprości się teraz nasz kod wstawiania do posortowanej listy z atrapą.
procedure wstaw_sort_z_atrapa (l:lista; x:typA); {do posortowanej listy l, zaczynającej się od atrapy, wstawia wartość x. Parametr l nie musi tym razem być przekazany przez zmienną, gdyż wartość l, będąca dowiązaniem do atrapy nie może się zmienić: nawet w przypadku wstawiania najmniejszej wartości do listy – lista będzie miała tę samą atrapę, jako początek} var next: lista; {rolę zmiennej akt może pełnić parametr l} begin next:=l^.nast; if next=nil then {lista pusta} wstawza(l,x) else begin while (next^.w<x) and (next^.nast<>nil) do begin l:=next; next:=l^.nast <b>end</b>; if' x>next^.w then wstawza(next,x) else wstawZA(l,x) end end;
I już!
Co robić, jeśli ktoś nam daje listę bez atrapy? Cóż – zawsze możemy taką atrapę sobie dodać, a potem zlikwidować:
procedure wstaw_sort (var l:lista; x:typ); {robi to samo na normalnej liście, sama sobie dodając atrapę} var atrapa: lista; begin new(atrapa); atrapa^.nast:=l; wstaw_sort_z_atrapa(atrapa, x); l:=atrapa^.nast; dispose(atrapa) end;
Atrapy są na tyle wygodne, że często lepiej się umówić, że listy po prostu reprezentujemy z atrapami. Ale nie przesadzajmy: traktujmy atrapy jako jedną z technik naszego repertuaru i używajmy ich wtedy, gdy są rzeczywiście pożyteczne.
Przyjrzyjmy się korzyściom i stratom wynikającym ze stosowania atrap. Podstawowa korzyść polega na tym, że uzyskujemy często krótszy i klarowniejszy – bardziej jednorodny kod. Złożoność czasowa praktycznie jest taka sama. Pamięciowa – tu jest gorzej: gdy mamy wiele krótkich list, z którymi jednocześnie pracujemy, wówczas dodatkowy rekord może stanowić pewne obciążenie pamięciowe i to jest podstawowa strata, którą trzeba wziąć pod uwagę.
Drzewa stanowią podstawę wielu ważnych algorytmów. Te pożyteczne struktury danych pozwalają organizować informację w sposób umożliwiający zarówno szybkie do niej dotarcie (jak w przypadku tablic), jak i szybką modyfikację: usuwanie i dodawanie nowych danych (jak to ma miejsce w przypadku list). Nadają się one więc doskonale do reprezentowania zbiorów skończonych, które w zastosowaniach informatycznych powstają najczęściej przez dodawanie kolejnych elementów, usuwanie ich i sprawdzanie, czy dany element znajduje się w zbiorze (typowe operacje bazodanowe).
Drzewa są rozważane w teorii grafów jako niezorientowane grafy spójne bez cykli. Drzewa używane w informatyce będą miały jedną istotną różnicę: zawsze z drzewem będzie związany jeden wybrany wierzchołek, nazywany korzeniem. Typowy sposób reprezentowania drzew będzie polegał na ustaleniu dla każdego węzła dowiązania do jego sąsiadów znajdujących się dalej od korzenia. Korzeń drzewa jest punktem, przez który drzewo jest dostępne, a samą definicję drzewa podamy rekurencyjnie, tak aby w każdym węźle określić jego następników – tak jak w drzewie genealogicznym określa się dzieci każdego węzła. Zresztą terminologia drzewa genealogicznego przeniknęła do informatyki i mówimy o ojcach, synach, wnukach, stryjach, dziadkach, kuzynach, mając na myśli związki analogiczne do rodzinnych.
Jedyną istotną różnicą między listami a drzewami jest to, że każdy element listy ma co najwyżej jeden następnik, a węzeł drzewa (czyli odpowiednik elementu listy) może mieć ich kilka. Jeśli ma co najwyżej dwa, to takie drzewo nazwiemy binarnym i – jak się okaże umiejętność obsługi drzew binarnych łatwo przełoży się na drzewa ogólne.
Podobnie, jak z listami, zdefiniujemy drzewa o wartościach w zbiorze A rekurencyjnie, jako najmniejszy zbiór spełniający dwa warunki:
Zauważmy, że mówimy tu o ciągu drzew D – ważna jest dla nas kolejność. Czasami chcielibyśmy o tej kolejności zapomnieć i rozważać zbiór drzew zamiast ciągu – wtedy musimy odpowiednio zmodyfikować definicję.
Stopniem wierzchołka (węzła) nazwiemy liczbę jego synów. W szczególności, jeśli ciąg synów wierzchołka \(v\) jest pusty, to stopień \(v\) wynosi 0, a sam węzeł \(v\) nazwiemy liściem. Stopień drzewa, to maksimum ze stopni jego wierzchołków. Przyjmujemy, że stopień drzewa pustego, to \(-1\).
Ścieżką w drzewie nazwiemy ciąg \(v_0,\ldots,v_k\), gdzie dla każdego \(1\le j \le k\) węzeł \(v_j\) jest synem węzła \(v_{j-1}\). Długością takiej ścieżki jest \(k\). Ścieżka złożona z jednego węzła ma długość 0, ścieżka pusta ma długość \(-1\).
Poziom korzenia definiujemy, jako 0, zaś poziomem węzła nazwiemy długość ścieżki od korzenia do tego węzła. Wysokość drzewa, to poziom najgłębszego spośród węzłów (liści), czyli maksimum z poziomów wszystkich węzłów. Wysokość drzewa pustego, to \(-1\).
Drzewo binarne, to drzewo o stopniu nieprzekraczającym \(2\). Zacznijmy może od pokazania, jak można reprezentować takie drzewa.
type drzewo = ^węzeł; {drzewo binarne} węzeł=record w: typA; lsyn,psyn : drzewo; end;
Podobnie jak dla list, przyjmijmy do końca tego wykładu, że typA=Integer. Będziemy więc mieli do czynienia z drzewami liczb całkowitych.
Zauważmy, że od strony technicznej definicja drzewa (binarnego) różni się od definicji listy jedynie jednym polem więcej w rekordzie opisującym jego element, zwany tutaj węzłem – każdy węzeł ma 2 następniki, a nie jednego, jak to było w przypadku list. Zauważmy, że ponieważ znamy ograniczenie górne na liczbę synów, więc możemy statycznie zarezerwować dwa pola do reprezentowania wskaźników do nich. Zakładamy tu, że rozróżniamy prawego i lewego syna w tym sensie, że drzewo binarne może mieć obu synów, tylko prawego, tylko lewego i żadnego – wszystkie 4 przypadki dopuszczamy, jako możliwe.
Zacznijmy od funkcji, która sprawdza, czy w drzewie istnieje węzeł o wartości x.
function jest(d:drzewo; x:typA):Boolean; {przyjmuje wartość true wtedy i tylko wtedy, gdy w drzewie d znajduje się wartość x} begin if d=nil then jest :=false {puste drzewo nie zawiera żadnej wartości} else if d^.w = x then jest := true {a niepuste albo ma ją w korzeniu} else jest := jest (d^.lsyn,x) or jest (d^.psyn,x) {albo w lewym lub prawym synu} {do sprawnego wykonania ostatniego wiersza konieczne jest założenie o leniwym wyliczaniu} end;
Uwaga. W przedstawionej wersji jeśli nie ma leniwego wyliczania, to nawet w przypadku, gdy wartość x znajdziemy w lewym poddrzewie, będziemy dalej żmudnie szukali jej jeszcze w prawym, mimo że już i tak wynik funkcji jest wiadomy. Gdybyśmy nie mieli pewności co do leniwości, wtedy ostatni else powinno się skonstruować inaczej:
else if jest(d^.lsyn,x) then jest:= true else jest:=jest(d^.psyn,x)
Tym sposobem niejako wymuszamy leniwość wyliczania warunków logicznych.
Powyższa funkcja wyróżnia pewien porządek przejścia przez drzewo. Po upewnieniu się, że drzewo nie jest puste najpierw obsługujemy korzeń drzewa, potem jego lewe poddrzewo, a na końcu prawe. Nie jest to jedyna możliwa kolejność. Można sobie wyobrazić, że najpierw będziemy szukali x w lewym poddrzewie, potem dopiero w korzeniu, a potem w prawym. Albo wręcz najpierw w obu poddrzewach, a dopiero na końcu w korzeniu. Oczywiście każda z tych procedur ma swój odpowiednik w postaci procedury, która poddrzewa będzie badać w odwrotnej kolejności, czyli najpierw prawe, a potem lewe.
Wspomniane warianty przeszukiwania drzewa dotyczą trzech bardzo ważnych procedur, zwanych obiegami drzew. Sprawdźmy może, jak będzie wyglądać kolejność wypisywania węzłów następującego drzewa, w momencie, gdy zastosujemy zasygnalizowane wcześniej metody przechodzenia wszystkich elementów drzewa.
A
/ \
B C
/ \ / \
D E F G
/ \ \ \
H I J K
/ \ /
L M NOto wspomniane procedury:
Prefiksowa:
procedure wypiszPreLP(d:drzewo); begin if d<>nil then begin Write(d^.w); wypiszpreLP(d^.lsyn); wypiszpreLP(d^.psyn) end end;
Dla procedury wypiszPreLP porządek wypisywania węzłów naszego drzewa będzie następujący: ABDHILMECFJGKN
Infiksowa:
procedure> wypiszInfLP(d:drzewo); begin if d<>nil then begin wypiszInfLP(d^.lsyn); Write(d^.w); wypiszInfLP(d^.psyn) end end;
Dla procedury wypiszInfLP porządek wypisywania węzłów naszego drzewa będzie następujący: HDLIMBEAFJCGNK
Postfiksowa:
procedure wypiszPostLP(d:drzewo); begin if d<>nil then begin wypiszPostLP(d^.lsyn); wypiszPostLP(d^.psyn) Write(d^.w); end end;
Dla procedury wypiszPostLP porządek wypisywania węzłów naszego drzewa będzie następujący: HLMIDEBJFNKGCA
Dodajmy do tych trzech obiegów ich odpowiedniki wypiszPrePL, wypiszInfPL oraz wypiszPost różniące się od nich tylko tym, że najpierw wchodzą do prawego poddrzewa, a dopiero potem do lewego.
Zadanie: W jakiej kolejności wypiszą się węzły dla tych trzech procedur?
Rozwiązanie:
Czy widać jakieś związki z wynikami procedur LP? Ciąg powstały przez wywołanie wypiszInfPL jest po prostu odwróconym ciągiem powstałym przez wywołanie wypiszInfLP. Gdy przyjrzymy się dokładniej, zobaczymy że ciąg z wypiszPrePL jest odwróconym ciągiem z wypiszPostLP, a ciąg powstały z wywołania wypiszPostPL odwróconym ciągiem z wypiszPreLP.
Okazuje się, ze nie jest to przypadek. Dla ciągów powstałych z wywołania naszych procedur dla danego drzewa d wprowadźmy oznaczenia \(Pre_{LP}, Pre_{PL}, Inf_{LP}, Inf_{PL}, Post_{LP}\) i \(Post_{PL}\). Jeśli dodatkowo umówimy się, że dla słowa \(w\in A^*\) przez \(w^R\) oznaczamy jego odwrotność, czyli symbole czytane po kolei od tyłu, to zachodzi następujący lemat:
LEMAT
Dla każdych \(u,v\in A^*\) zachodzi \((uv)^R=v^Ru^R\).
DOWÓD
Oczywisty.
Możemy teraz sformułować następujące twierdzenie:
TWIERDZENIE O OBIEGACH
Dla każdego drzewa d, jeśli rozważane obiegi odwiedzają węzły w kolejności odpowiednio \(Pre_d{LP}, Pre_d{LP}, Inf_d{LP}, Inf_d{PL}, Post_d{LP} i Post_d{PL}\), to
DOWÓD
Indukcja ze względu na wielkość drzewa.
Baza: Jeśli drzewo jest puste, czyli d=nil, to wszystkie uzyskane słowa są puste, a więc równe sobie i swoim odwrotnościom.
Krok indukcyjny: Załóżmy, że d jest niepuste i ma n>0 węzłów. Wtedy ma na pewno korzeń \(r\) oraz dwa poddrzewa \(d_L\) i \(d_P\). Załóżmy, że dla wszystkich drzew o mniejszej niż n liczbie węzłów teza zachodzi. Pokażemy, że zachodzi również dla drzewa d.
Ponieważ drzewo d ma n węzłów, w tym korzeń, więc każde z jego poddrzew ma co najwyżej n-1 węzłów, zatem można do nich stosować założenie indukcyjne. Przeprowadźmy najpierw dowód tego, że \(Pre_d{LP}=Post_d{PL}^R\). Mamy zatem
\(Pre_d{LP}=r \cdot Pre_{d_L}{LP}\cdot Pre_{d_P}{LP}= r^R \cdot Post_{d_L}{PL}^R \cdot Post_{d_P}{PL}^R =\) \((Post_{d_P}{PL} \cdot Post_{d_L}{PL}\cdot r)^R = Post_d{PL}^R\).
Pierwsza z równości wynika z definicji obiegu prefiksowego LP, druga z równości wynika z założenia indukcyjnego, trzecia, to nasz lemat, a czwarta wynika z definicji obiegu postfiksowego PL.
Uzyskana równość kończy dowód pierwszego z podpunktów. Dowody pozostałych dwóch przebiegają analogicznie.
Zobaczmy teraz, jak można używać mechanizmu przekazywania parametrów procedury przy transferze informacji w drzewie. Rozwiążmy dwa zadania.
Zadanie 1. W każdym węźle v drzewa d zastąp wartość tego węzła przez sumę wartości wszystkich węzłów na ścieżce od d do v włącznie.
Rozwiązanie.
Jedyna trudność, to konieczność zadbania o to, żeby przy zmianie wartości węzłów uwzględniać to, że nie wolno tej samej wartości brać wiele razy pod uwagę. Narzuca się tu zatem porządek prefiksowy. Oto rozwiązanie:
procedure Nadsumuj(d:drzewo); procedure DodajGore(d:drzewo; k:Integer); {Dosumowuje wartość parametru k do węzła d i nową wartość przekazuje rekurencyjnie obu synom. Procedura wykonuje główna robotę; jedyną zmianą w stosunku do głównej procedury jest obecność dodatkowego parametru.} begin if' d<> nil then begin d^.w:=d^.w+k; DodajGore(d^.lsyn,d^.w); DodajGore(d^.psyn,d^.w); end; end; begin {Nadsumuj} DodajGore(d,0) end;
Zauważmy jedną bardzo ważną technikę. W naszym przypadku niezwykle uprościło całą procedurę wprowadzenie dodatkowego parametru informującego przetwarzany węzeł o tym, o ile zwiększyć się ma jego wartość. Często programiści niechlujnie programując dodają ten parametr do procedury zasadniczej, każąc użytkownikowi samemu zadbać o wywołanie jej z dodatkową wartością, zupełnie zbędną z punktu widzenia specyfikacji problemu – w naszym przypadku z zerem. Zapamiętajmy więc ważną zasadę:
Procedura powinna mieć tyle parametrów, ile jest to konieczne z punktu widzenia specyfikacji zadania. Wszelkie nadmiarowe parametry ułatwiające zaprogramowanie są wyrazem niechlujstwa. Również złą praktyką programistyczną jest nieumieszczanie istotnych parametrów w nagłówku i korzystanie ze zmiennych globalnych. Rekurencja i iteracja niezbyt się lubią nawzajem. Najczęściej dobrze jest zdecydować się na jedną z nich.
W Pascalu takie obudowanie zasadniczej procedury (w naszym przypadku DodajGore) właściwym interfejsem (w naszym przypadku Nadsumuj) jest naturalnie wpisane w koncepcję zagnieżdżania procedur. W językach rodziny C niestety procedur zagnieżdżać się nie da, co prowadzi do zmniejszenia czytelności kodu – ze struktury programu nie widać zależności funkcjonalnej między procedurami.
Wróćmy teraz do drugiego z naszych zadań.
Zadanie 2. W każdym węźle v drzewa d zastąp wartość tego węzła przez sumę wartości wszystkich węzłów w poddrzewie, którego v jest korzeniem.
Procedurę rozwiązującą zadania 2 nazwijmy Podsumuj.
procedure Podsumuj(d:drzewo); var dowol:Integer; {zaślepka – potrzebna tylko po to, żeby nie było błędu składniowego} procedure DodajDol(d:drzewo; var k:Integer); {Dosumowuje wszystkie wartości z poddrzewa pod znajdującego sie pod d do d^.w , a otrzymaną wartość przekazuje jako k węzłowi, który ja wywołał} var zdolu:Integer; begin if' d=nil then k:=0 {To przypisanie jest konieczne!} else begin DodajDol(d^.lsyn, zdolu); d^.w:=d^.w+zdolu; DodajDol(d^.psyn, zdolu); d^.w:=d^.w+zdolu; k:=d^.w end; end; begin {Podsumuj} DodajDol(d,dowol) {Można było uniknąć dowola wstawiając tu np. d^.w, ale to by zaciemniło kod} end;
Warto zapamiętać parę rad, które mogą nam ułatwić rozwiązywanie tego typu problemów.
W procedurach rekurencyjnych dotyczących drzew zawsze sprawdzamy na początku, czy argument nie jest nilem. Przy przekazywaniu informacji od korzenia w dół używamy najczęściej porządku prefiksowego, a informację przekazujmy przez wartość Przy przekazywaniu informacji z dołu drzewa do góry używamy najczęściej porządku postfiksowego i przekazujemy ją albo przez parametry wołane przez zmienną albo za pomocą funkcji.
Poznamy teraz technikę umożliwiającą rozwiązywanie całej klasy zadań i niezwykle wygodną. Nazwiemy ją techniką spaceru. Żeby zilustrować ją, a zarazem pokazać, czym się różni od standardowego przejścia rekurencyjnego, rozwiążmy jedno zadania na dwa sposoby. Zadanie polega na wyznaczeniu wysokości drzewa. Najpierw czysta rekurencja postfiksowa. Oczywiście postfiksowa, gdyż aby poznać wysokość drzewa, musimy w korzeniu znać wysokości jego synów, ci z kolei swoich – i tak dalej. Ewidentnie informacja wędruje z dołu.
function wysokość(d:drzewo):Integer; function max(a,b:Integer):Integer; begin if a<=b then max:=b else max:=a end {bez komentarza :-)} begin {wysokość} if d=nil then wysokość:=-1 else wysokość:=max(wysokość(d^.lsyn),wysokość(d^.psyn))+1 end;
I już! Wprost z definicji.
Teraz spacer. Technika spaceru polega na przejściu drzewa z stosownym porządku (tu akurat wybór porządku nie ma dużego znaczenia) i notowaniu na zmiennej globalnej zaobserwowanych informacji. U nas interesującą informacją będzie aktualna głębokość. Jeśli pobijemy rekord, to go zaktualizujemy.
function wysokośćSpacerowa(d:drzewo):Integer; var aktg,maxg:Integer; {aktualna i maksymalna głębokość} procedure spacer(d:drzewo); begin if d<>nil then begin {spacer} aktg:=aktg+1; {wywołano nas z poziomem o 1 za małym, więc ustawiamy go na naszą głębokość} if aktg>maxg then maxg:=aktg; spacer(d^.lsyn); spacer(d^.psyn); aktg:=aktg-1;{Nie wolno nam zapomnieć o tej instrukcji! Musimy ojcu odtworzyć jego głębokość.} end; {spacer} begin {WysokośćSpacerowa} aktg:=-1; maxg:=-1; spacer(d); WysokośćSpacerowa:=maxg <b>end</b>;
Tutaj sprawdzanie, czy rekord nie został pobity, mogliśmy przesunąć albo między wywołania dla synów (wtedy mielibyśmy coś w rodzaju obiegu infiksowego) albo po wywołaniu dla prawego syna (wtedy byłoby to postfiksowo) i ta wersja jest najefektywniejsza, ale zysk polega jedynie na tym, że rekordu nie ciułamy powiększając go o 1, tylko od razu – gdy będziemy w liściu aktualizujemy być może o kilka jednostek.
Zajmiemy się teraz drzewami ogólnymi. Zakładamy tu, że nic nie wiemy o stopniu poszczególnych węzłów. Najstosowniejszym pomysłem wydaje się więc zastosowanie list do implementacji synów węzłów. Gdy nie wiemy z góry, ilu synów ma który węzeł, listy wydają się być najlepszym rozwiązaniem. Każdy węzeł zatem będzie miał poza wartością dwa pola: wskaźnik do swojego skrajnie lewego syna oraz wskaźnik do prawego brata. Mamy więc następującą deklarację:
type DrzewoOgólne = ^WęzełOgólny; WęzełOgólny=record w: typA; lsyn,brat : drzewo; end;
Gdy przyjrzymy się tej definicji, zauważymy, że w zasadzie z punktu widzenia składni jest to identyczna definicja z definicją drzewa binarnego: jedyną różnicą jest inna nazwa drugiego pola wskaźnikowego, a co za tym idzie inna jego interpretacja. Zauważmy, że korzeń nie ma braci, zatem jego pole brat będzie zawsze wskazywało na nil. Przy okazji – często rozważa się inną strukturę danych – lasy, będące zbiorami drzew. Gdyby list zapoczątkowana przez pole brat korzenia była niepusta, uzyskalibyśmy naturalną metodę reprezentowania lasu.
Zobaczmy, jak zmieni się funkcja obliczająca wysokość drzewa ogólnego. Oto przykładowy kod:
function wysokosćOgólna(d:drzewo):Integer; function max(a,b:Integer):Integer; begin if a<=b then max:=a else max:=b end {bez komentarza :-)} begin {wysokość} if d= nil then wysokość:=-1 else wysokość:=max(wysokość(d^.lsyn)+1,wysokość(d^.brat)) end;
Różnica niewielka – dodawanie jedynki powinno dotyczyć tylko poziomów synów, a nie braci – stąd występuje ono tylko przy parametrze dotyczącym syna.
Dobrym ćwiczeniem jest zaprogramowanie zadań na drzewa binarne w wersji drzew ogólnych. Prawie wszystkie procedury wyglądają bardzo podobnie. Zauważmy, że o ile sensowne jest mówienie o porządku prefiksowym i postfiksowym (po prostu ojca przetwarzamy albo zanim przetworzymy synów, albo po nich), to porządek infiksowy nie jest taki oczywisty: nie wiadomo z góry po którym synu chcielibyśmy przetworzyć ojca.
Spośród wielu struktur danych używanych w informatyce dwie mają szczególne znaczenie. Charakteryzuje je prostota koncepcji, łatwość implementacji i przydatność w rozwiązywaniu rozmaitych problemów algorytmicznych. Są to stosy i kolejki. Ogólnie chodzi o niezwykle ważny w informatyce problem reprezentacji zbiorów skończonych. Bardzo często bowiem potrzebujemy przechowywać zbiory elementów pewnej przestrzeni, potencjalnie bardzo dużej (np. wszystkie możliwe rezerwacje lotnicze dla wszystkich ludzi na świecie) w taki sposób, żeby efektywnie móc wykonywać podstawowe trzy operacje:
Problem ten dokładnie jest opisany w kursie "Algorytmy i struktury danych", tu jednak chcemy zająć się jego wersją, związaną z pewną specyfiką, gdy zależy nam na wykonaniu jakiejś czynności dla każdego elementu zbioru i to w kolejności narzuconej przez nasze wymagania. O ile na wkładanie elementu do zbioru nie mamy wpływu - po prostu trzeba akceptować każde żądanie - o tyle w przypadku pobierania elementów ze zbioru mamy pewną dowolność. Podstawowe dwie strategie, które będziemy tu rozważać, to
Podstawowe operacje zatem, które będziemy rozważali będą następujące:
W zależności od tego, czy stosujemy strategię stosową, czy listową, zastosujemy różne implementacje. Zacznijmy od stosów.
Przedstawimy tu dwie najpopularniejsze implementacje stosów: tablicową i listową.
Stosy będziemy reprezentować jako parę (tablica T, indeks p pierwszego wolnego miejsca). Włożenie nowego elementu będzie polegać na wstawieniu go pod indeksem p i zwiększenie indeksu p o 1. Pobranie będzie polegało na zmniejszeniu indeksu p o 1 i odczytaniu znajdującej się tam wartości. Utworzenie pustego stosu będzie sprowadzało się do inicjalizacji wskaźnika na 1, a sprawdzenie, czy stos jest pusty na sprawdzeniu, czy indeks p jest równy 1. Oto komplet procedur stosowych:
type stos = record T : array[1..n] of typ; //Zakładamy, że wszystkiego elementy na stosie będą tego samego typu p : Integer //indeks pierwszego wolnego elementu end
procedure MakeEmpty(var s : stos); //Inicjalizacja stosu pustego begin s.p:=1 end;
function Empty(const s : stos) : Boolean; //Sprawdzenie pustości stosu begin Empty := s.p=1 end;
procedure Push(var s : stos; x:typ); //Włożenie na stos elementu o wartości x begin s.T[s.p]:=x; s.p:=s.p+1 end;
procedure Pop(var s : stos; var x:typ); //Zdjęcie ze stosu najświeższego elementu begin //i przypisanie jego wartości parametrowi x x:=s.T[s.p]; s.p:=s.p-1 end;
type stos = ^record w : typ; //Zakładamy, że wszystkie elementy na stosie będą tego samego typu nast : stos //wskaźnik do kolejnego elementu end
procedure MakeEmpty(var s : stos); //Inicjalizacja stosu pustego begin s := nil end;
function Empty(const s : stos) : Boolean; //Sprawdzenie pustości stosu begin Empty := s = nil end;
procedure Push(var s : stos; x:typ); //Włożenie na stos elementu o wartości x var pom: stos; begin new(pom); pom^.w:=x; if s= nil then pom^.nast:=nil else pom^.nast:=s; s:=pom end;
procedure Pop(var s : stos; var x:typ); //Zdjęcie ze stosu najświeższego elementu var pom:stos; begin //i przypisanie jego wartości parametrowi x x:=s^.w; pom := s; s := pom^.nast; dispose(pom) end;
Często procedury stosowe mają postać funkcji: wartością procedury Push jest nowy stos, wartością procedury Pop jest wartość zdjętego elementu x.
Dodatkowo czasami stosuje się procedury upraszczające korzystanie ze stosów. Do najważniejszych należą procedury, które podajemy w implementacji tablicowej:
function Full(const s : stos) : Boolean; //Sprawdzenie, czy na stosie jest miejsce na kolejny element begin Full := s.p>n end;
procedure Top(const s : stos; x:typ); //Pobranie wartości z wierzchołka stosu bez zdejmowania elementu begin x:=s.T[s.p]; end;
procedure Erase(var s : stos); //Wyczyszczenie stosu begin s.p:=1 end;
Zauważmy, że wszystkie te procedury można zaimplementować za pomocą procedur podstawowych. W szczególności wykonanie procedury Top(s,x) jest równoważne wywołaniu pary Pop(s,x); Push(s,x). Procedura Erase(s) jest równoważna pętli while not Empty(s) do Pop(s,x). Procedura Full wymagałaby użycia własnej zmiennej zliczającej liczbę elementów na stosie.
Z kolejkami sprawa jest o tyle trudniejsza, że musimy na nich operować z obu stron: z jednej wkładamy elementy, z drugiej wyjmujemy. Przedstawimy trzy implementacje kolejek: dwie pierwsze odpowiadają zaproponowanym implementacjom stosowym, trzecia jest oryginalna i wykorzystuje listę cykliczną. Dla rozróżnienia tych podobnych operacji będziemy w przypadku kolejek używać polskich nazw procedur.
Tym razem ponieważ będziemy pobierali z drugiego końca, niż wkładali, kolejka będzie się ,,przesuwać w tablicy. Gdy dojdzie do końca, zawiniemy ją tak, że kolejne elementy będą się pojawiać od początku. Z przyczyn technicznych
type kolejka = record T : array[0..n] of typ; //Zakładamy, że wszystkiego elementy w kolejce będą tego samego typu pocz,kon : Integer //pocz - indeks pierwszego elementu, kon - indeks pierwszego wolnego end
Tym razem tablica reprezentująca n-elementową kolejkę będzie miała n+1 elementów. Dlaczego? Wkrótce się wyjaśni.
procedure TwórzPustą (var k : kolejka); //Inicjalizacja pustej kolejki begin k.pocz:=0; k.kon:=0 end;
function Pusta(const k : kolejka) : Boolean; //Sprawdzenie pustości kolejki begin Empty := k.pocz=k.kon end;
procedure Wstaw(var k:kolejka; x:typ); //Włożenie do kolejki elementu o wartości x begin k.T[s.kon]:=x; k.kon:=k.kon+1; if k.kon>n then s.kon:=0 end;
procedure Pobierz(var k:kolejka; var x:typ); //Pobranie z kolejki najświeższego elementu begin //i przypisanie jego wartości parametrowi x x:=s.T[s.pocz]; k.pocz:=k.pocz+1; if k.pocz>n then k.pocz:=0 end;
type kolejka = ecord pocz,kon : lista //pocz - wskaźnik do pierwszego elementu, kon - do ostatniego end>
procedure TwórzPustą(var k : kolejka); //Inicjalizacja pustej kolejki begin k.pocz := nil end;
function Pusta(const k : kolejka) : Boolean; //Sprawdzenie pustości kolejki begin Empty := k.pocz = nil end;
procedure Wstaw(var k:kolejka; x:typ); //Włożenie do kolejki elementu o wartości x var pom: lista; begin new(pom); pom^.w:=x; if k.pocz = nil then k.pocz:=pom; else k.kon^.nast:=pom; //k.kon zawsze po wstawieniu pokazuje na ostatni element k.kon:=pom end;
procedure Pobierz(var k:kolejka; var x:typ); //Pobranie z kolejki najstarszego elementu var pom:lista; begin //i przypisanie jego wartości parametrowi x x:=k.pocz^.w; pom := k.pocz; if k.pocz=k.kon then k.pocz:=nil //Kolejka jednoelementowa else k.pocz := k.pocz^.nast; dispose(pom) end;
Podobnie, jak poprzednio, dodatkowe procedury, analogiczne do stosowych, można napisać tak:
Tym razem sprawdzenie w implementacji tablicowej, czy kolejka jest pełna nie jest tak proste. gdybyśmy sprawdzali, czy kolejka ma n+1 elementów, to naturalny warunek k.pocz=k.kon, który stwierdzałby pełność, dawałby odpowiedź true zarówno wtedy, gdy kolejka byłaby pełna, jak i wtedy, gdy byłaby pusta. Stąd umowa, że za pełną uznamy kolejkę, w której jeszcze jeden element jest niezapisany. Zatem musimy (cyklicznie) dodać jedynkę do k.pocz i sprawdzić, czy jest ona równa k.kon.
function Pełna(const k:kolejka) : Boolean; //Sprawdzenie, czy w kolejce jest miejsce na kolejny element var i:Integer; begin i:=k.kon+1; if i>n then i:=0; Full := k.pocz=i end;
procedure Pierwszy(const k.kolejka; var x:typ); //Pobranie wartości z początku kolejki bez pobierania elementu begin x:=k.T[k.pocz]; end;
procedure Usuń(var k : kolejka); //Wyczyszczenie kolejki begin k.pocz:=k.kon end;
Zauważmy, że tym razem byłyby kłopoty z implementacją procedury Pierwszy przez procedury podstawowe. Procedura Usuń(k) jest równoważna pętli while not Pusta(k) do Pobierz(k,x). Procedura Pełna też, tak jak w przypadku stosów, wymagałaby użycia własnej zmiennej zliczającej liczbę elementów w kolejce.
Oczywiście można wyobrazić sobie też inne procedury rozszerzające korzystanie z kolejek, na przykład wartość drugiego elementu, czy liczba elementów kolejki. Implementację takich funkcji pozostawiamy, jako ćwiczenie.
Ciekawym rozwiązaniem jest użycie listy cyklicznej. Koniec kolejki pamiętamy jako dowiązanie do ostatniego elementu listy. Jego następnikiem będzie pierwszy element kolejki, zatem wszystkie operacje kolejkowe można będzie zrobić w czasie stałym. Przy usuwaniu trzeba sprawdzać, czy kolejka nie jest jednoelementowa, przy dodawaniu elementu, czy nie jest pusta. W pozostałych przypadkach zawsze wstawiamy za ostatnim elementem (procedura wstawza z wykładu o listach), a pobieramy zza ostatniego elementu, usuwając element stojący za ostatnim. Zrealizowanie tej implementacji pozostawmy jako ćwiczenie.
Implementacja ta ma niewątpliwy walor estetyczny. Poszczególne operacje mogą być trochę kosztowniejsze - raptem jedno-dwa przypisania - ale nie powinno to stanowić powodu do odrzucenia tego pomysłu.
Rzecz jasna, porównując podane implementacje warto się zastanowić, która z nich jest najefektywniejsza. Implementacja tablicowa jest najszybsza. Wymaga jednak z góry zarezerwowanej pamięci. Jeśli mamy do czynienia z wieloma kolejkami o nieustalonej długości, to implementacja listowa daje elastyczność rezerwowania pamięci skrojonej na miarę problemu, co może być bardzo ważnym aspektem, szczególnie gdy liczba kolejek jest zależna od rozmiaru danych, a jednocześnie same kolejki są krótkie.