O Copyright by Anna Struzińska-Walczak, Krzysztof Walczak Warszawa 1994 "Nauka programowania dla już nie całkiem początkujących" Autorzy: Anna Struzińska-Walczak, Krzysztof Walczak Książka zawiera wykład nauki programowania na poziomie nieco wyższym niż podstawowy. Jest ona kontunuacją pracy "Nauka programowania dla początkujących". W książce są wyjaśnione wszystkie techniki programowania możliwe do wykorzystania w języku Pascal łącznie z obszernym omówieniem prngramowania obiektowego. Wykład został poprowadzony w sposób jak najbardziej czytelny i przejrzysty, zamieszczone programy są bogato skomentowane i opisane, a trudniejsze algorytmy są zapisane w pseudokodzie. Książka jest przeznaczona dla wszystkich osób interesujących się programowaniem. Może być także wykorzystywana przez studentńw wyższych uczelni jako podręcznik do nauki programowania. Uwaga: W wydawnictwie można zakupić dyskietkę zawierąjącą kody źródłowe programów zawartych w książce. Wydawca Wydawnictwo W & W Adres korespondencyjny ul. lbłstoja 1/13 Ol-910 Warszawa tel. 85 90 24 ISBN 83-900519-4-X SPIS TRESCI 1.Wstęp......................................... 5 2.Prostetypydanych.. .... ............8 3.Tablice (uzupełnienie ).......... # 3.1.Tablice trzywymiarowe. ...11 3.2.Zadania.. ...16 4.Moduły .. .........17 5. Pliki tekstowe i operacje na tekstach . . . . . . 22 5.1. Pliki input i output. . . 22 5.2. Pliki tekstowe. . . . 23 5.3. Wyprowadzanie danych na drukarkg . . 38 5.4. Operacje na tekstach. . . . 39 5.5. Zadania. . . . 43 6. Pliki elementowe. . . . . . . . . . 7.Zbiory .. .......... 51 7.1. Wprowadzenie. . . 51 7.2. Operacje na zbiorach. . . . 53 7.3. Podstawowe algorytmy. . . 55 7.4. Zadania. . . . . 67 8. Rekordy 8.1. Wprowadzenie. 8.2. Instrukcja with 8.3. Tablice rekordów 8.4. Zadania. . #q . . 69 . . 74 . . 77 . . 95 Nauka programowania... 9. Rekurencja. . . 9.1. Wprowadzenie 9.2. Algorytmy z powrotami . . 101 9.3. Algorytmy sortowania 116 9.4. Zadania 128 10. Wskaźniki. . . . 130 10.1. Wprowadzenie. 130 10.2. Operacje na wskaźnikach i zmiennych dynamicznych 133 10.3. Tablice wskaźników 134 10.4. Zadania. 140 11. Podstawy programowania obiektowego 14 11.1. Wprowadzenie . 141 11.2. Dziedziczenie 147 11.3. Metody wirtualne. 155 11.4. Rozszerzalność obiektów. . . 159 11.5. Klasa do tworzenia menu programu. . 161 12. Pro#ramowanie dynamicznych struktur danych z wykorzystaniem programowania obiektowego 173 12.1. Listy 173 12.2. Stosy 241 12.3. Kolejki 249 12.4: Drzewa binarne. . 255 12.5. Zadania 276 1#. Podsumowanie . . . 279 LITERATURA UZUPEŁNIAJĄGA. 280 SKOftOWIDZ 282 -4- Rozdział WST#P Niniejsza książka jest drugą z kolei w serii poświęconej nauce programowania. Pierwsza to "Nauka programowania dla początkujących" [20). Zapoznanie sig z tą książką lub inną zawierającą podobny materiał oraz rozwiązanie pewnej liczby przykładów jest niezbędne do rozpoczgcia studiowania niniejszej pozycji. Praca ta może być również wykorzystywana przez bardziej zaawansowanego Czytelnika, który chce poznać techniki programowania obiektowego. Jak wskazuje sam tytuł, książka ta jest poświęcona nauce programowania na poziomie nieco wyższym niż podstawowy. Zakładamy, że Czytelnik posiada już podstawową umiejgtność programowania i potrafi wykorzystać instrukcje sterujące, tablice oraz podprogramy. Obecnie postaramy sig nauczyć Czytelnika programować z wykorzystaniem wszystkich mechanizmów dostępnych w języku Pascal łączni# z programowaniem obiektowym. Podobnie jak w pracy [20] jako język do nauki programowania wybraliśmy jgzyk lhrbo Pascal w wersji 6.0 (możliwość programowania obiektowego jest dostgpna od wersji 5.5 języka). Drogi Czytelniku, numer wersji danego języka przy nauce programowania naprawdg nie jest istotny. Ważne jest jedynie, aby dana wersja posiadała wszystkie wykładane mechanizmy. Ucząc sig programować, nie należy zatem przejmować się tym, że ukazała sig już nowsza wersja języka. Należy podkreślić, że książka nie zawiera pełnego opisu języka ltzrbo Pascal (nie zostały omowione mniej istotne w nauce programowania szcze -5- Nauka programowania... góły jgzyka). Jest to książka do nauki programowania, a nie praca poświęcona samemu językowi. Pełny opis języka 'Itzrbo Pascal można znaleźć w pracach [6,13,14]. Materiał przedstawiony w książce można podzielić na kilka części. Pierwsza jest poświęcona uzupełnieniu podstawowych wiadomości dotyczących typów danych, wykorzystania tablic trzywymiarowych oraz projektowaniu modułów (rozdz. 2,3,4). Część druga omawia algorytmy stosowane przy przetwarzaniu plików i techniki stosowane w operacjach na zbiorach oraz rekordach (rozdz. 5-8). Następna część jest poświgcona projektowaniu algorytmów rekurencyjnych (rozdz. 9). Kolejna część podąje techniki programowania z wykorzystaniem wskaźników (rozdz. 10). Część piąta zawiera wprowadzenie do programowania obiektowego (rozdz. 11). Ostatnia bardzo obszerna część książki to omówienie technik stosowanych przy przetwarzaniu list, stosów, kolejek i drzew binarnych z jednoczesnym wykorzystaniem programowania obiektowego (rozdz.12). W książce znajduje się wiele progi'amów wraz z zaprojektowanymi algorytmami. Podobnie jak w pracy [20) algorytmy są zapisywane nąjpierw w pseudo-kodzie. Zamieszczone przykłady są już o wiele trudniejsze niż podane w [20], większość z nich bazuje na klasycznych algorytmach wykorzystywanych w nauce programowanie i mających jednocześnie duże zastosowanie praktyczne. Można tu wymienić zwłaszcza algorytmy sortowania szybkiego i przez scalanie, programy wykorzystujące algorytm nawrotu oraz algorytmy stosowane przy przetwarzaniu list oraz drzew binarnych. Projektowanie algorytmów powinno przebiegać w oparciu o systematyczne techniki ich projektowania. Do podstawowych technik należą projektowanie wstępujące i zstępujące. Projektowanie wstępujące polega na rozpoczęciu projektowania od wyodrębnienia w danym algorytmie niepodzielnych części, które następnie łąc#y się w większe jednostki tak długo, aż otrzymamy rozwiązanie danego problemu. Można je określić jako projektowanie od szczegółu do ogółu. Natomiast projektowanie zstępujące polega na zaprojektowaniu algorytmu w pierwszym etapie bez rozpatrywania szczegółów. Częściami składowymi algorytmu są bloki funkcjonalne realizujące ściśle określone operacje, które następnie w dalszej fazie projektowania uściśla się tak długo, aż dojdzie się do operacji możliwych do zaprojektowania bezpośrednio. Określamy je jako projektowanie od ogółu do szczegółu. W niniejszej książce będziemy wykorzystywać obie wymienione techniki projektowania algorytmów. Mamy nadzieję, że Czytelnik bez trudu zorientuje się, która technika została wykorzystana w konkretnym przypadku. -6- 1. Wstęp Cały podany materiał został wyłożony w sposób jak nąjbardziej czytelny i przejrzysty, zamieszczone programy są bogato skomentowane i opisane, a wszystkie trudniejsze algorytmy są zapisane w pseudo-kodzie. Po każdym rozdziale są podane przykładowe zadania utrwaląjące wyłożony materiał. Książka jest przeznaczona dla wszystkich osób interesujących sig programowaniem. Może być także wykorzystywana jako podrgcznik do nauki programowania przez studentów wyższych uczelni. -7- Rozdział PROSTE TYPY D##NYCH W poprzedniej książce [20] pierwszej w eyklu poświęconym nauce programowania wprowadziliśmy następujące typy danych: całkowity, rzeczywisty, znakowy, łańcuchowy oraz logiczny. Obecnie omówimy typy danych, które mogą zostać zdefiniowane przez programistę. Należy do nich typ wyliczeniowy oraz typ okrojony. Z#p wyliczeniowy jest definiowany następująco: type nazwa = (sl,...,s#) gdzie nazwa jest nazwą typu, a s; są identyfikatorami stałych, których wartości rrioże przyjmować zmienna danego typu. Przykład type mebl e = C stol, krzesl o, szafa, wersal ka ) ; var ml,m2: meble; W przykładzie zdefiniowano typ wyliczeniowy meble oraz zmienne ml oraz m2 typu meble. Wartości typu wyliczeniowego nie można wczytywae ani drukować w normalny sposób. Można je natomiast wykorzystywać w relacjach, funkcjach i instrukcjach przypisania. Przykłady programów, w których wyko 2. Proste typy danych rzystano typ wyliczeniowy są podane w rozdziale 7. 1#p okrojony jest to podzbiór wartości typu całkowitego, znakowego, logicznego lub wyliczeniowego.1#p ten defniujemy następująco: type nazwa = min..max gdzie nazwa jest nazwą typu, min jest dolnym a max górnym ograniczeniem wartości, jakie może przyjmować zmienna typu okrojonego. Przykład type litera = 'a'..'z'; tydzien = C poniedzialek, wtorek, sroda, czwartek, piatek sobota niedziela ); robocze = poniedzialek..piatek; zakres =10. .20; var 11,12:litera; dni: robocze; zl,z2: zakres Zmienne 11,12, dni, zl, z2 są typu okrojonego i mogą przyjmować następujące wartości: zmienne 11 i 12 - litery 'a ', 'b ',..., 'z ' zmienna dni - poniedzialek, wtorek, sroda, czwartek, piatek zmienne zl, z2 - liczby z przedziału <10,20> l#py integer, char, Boolean oraz wprowadzony wyżej typ wyliczeniowy i okrojony są tak zwanymi typami porządkowymi. Charakteryzują się one tym, że móżna je uporządkować i dla danej wartości podać wartość poprzed= nią i następną. Dla typńw porządkowych można wykorzystywać szereg użytecznych funkcji standardowych. Funkcja succ(arg) podaje wartość następną w danym typie po wartości argumentu. Funkcja pred(arg) podaje wartość poprzednią w danym typie przed wartością argumentu. Funkcja ord(arg) podaje numer, jaki wartość argumentu zajmuje w danym typie. Przykład type tydzien = C poniedzialek, wtorek, sroda, czwartek, pi atek, sobota, ni edzi el a ) ; var -9- Nauka programowania... d: tydzien; x:integer; Przy powyższej deklaracji funkcja succ(sroda) podąje wartość czwartek, a funkcja succ(11) wartość 12. Wartością funkcji pred(wtorek) jest poniedzialek, a funkcji pred(15) wartość 14. Funkcja ord(piatek) podaje wartość 5, a funkcja ord(13) wartość 13 (podawany numer jest taki jak dana wartość całkowita). ' lO ' Rozdział TABLICE (UZUPE#NIENIE) 3.1. Tablice trzywymiarowe W pracy [20] podano szereg przykładów ilustrujących wykorzystanie tablic, ale tylko tablic jedno i dwuwymiarowych. W jgzyku Pascal tablice mogą mieć wigcej wymiarów. W zaprezentowanym obecnie przykładzie wykorzystamy tablicg o trzech wymiarach. # Przykład Napisać program obliczania sumy elementów leżących na dowolnej przekątnej w tablicy trzywymiarovvej kwadrat#wej. Tablicę trzywymiarową oraz jedną przekątną główną i jedną boczną ilustruje rys. 3.1. Zastanówmy się teraz nad algorytmem obliczania sumy elementów leżących na dowolnej przekątnej w tablicy trzywymiarowej. Najważniejsze jest oczywiście wyznaczenie współrzędnych poszczególnych elementów. Wyobraźmy sobie najpierw tablicg trzywymiarową jako n tablic dwuwymiarowych położonych jedna nad drugą. Rozważmy na początek przekątną położoną w pierwszej tablicy dwuwymiarowej. Umówmy sig jeszcze, że element tablica[i,j,k] oznacza element leżący w i-tej tablicy dwuwymiarowej Nauka programowania... ftys. 3.1. Przykładowa tablica trzywymiarowa na przecigciu j-tego wiersza i k-tej kolumny. Na rys. 3.2 przedstawiono indeksy pierwszej tablicy dwuwymiarowej. lll 112 113 121 122123 131 132133 Rys. 3.2. Indeksy pierwszej tablicy dwuwymiarowej Przy pomocy pogrubienia zaznaczono indeksy jednej z dwóch przekątnych. Jeden z końców przekątnej ma indeksy 111, a drugi koniec indeksy 133. Wykorzystany algorytm polega na znalezieniu liczby elementów prze- ů kątnej oraz trzech wartości oznaczanych w programie przy pomocy dx,dy,dz podających, o ile muszą sig zmienić indeksy tablicy. Wartość dx podaje zmianę dla zmiennej i, dy określa zmianę dla zmiennej j, a dz wyznacza zmiang-dla zmiennej k. W analizowanym przypadku dx ma wartość 0, dy wartość 1 oraz dz wartość 1. Wartości te wyznacza się przy pomocy poniższej konstrukcji, ktorą dla przykładu podamy dla zmiennej x (wyrażenie to ma sens, wtedy gdy x2 - xl jest różne od zera): dx := Cx2 - xl) div absCx2 - xl); gdzie operator div wykonuje dzielenie całkowite. Jak łatwo można zauważyć, wartość ta może być równa albo +1 albo -1. Liczbę kroków wyznaczamy przy pomocy konstrukcji: kroki := abs Cx2 - xl ) + 1; oczywiście tylko wtedy, gdy x2 - xl jest różne od zera. Ponieważ tablice dwuwymiarowe są kwadratowe, to nie ma znaczenia, z obliczenia której zmiennej wyznaczymy wartość kroku. Obliczenie sumy elementów leżących na dowolnej przekątnej odbywa się już w bardzo prosty -12 - 3. Tablice (uzupełnienie) sposób poprzez wykonanie w pętli następujących instrukcji: suma := suma + tCi,j,k] ; C ustawienie wspólrzgdnych nastgpnego elementu przek#tnej ) k:=k+dz; j:=j+dy; i := i +dx; A oto kompletny program realizujący omawiane zadanie. Program 3.1 program Trzywymiary; f Program obliczania sumy elementów leż#cych na dowolnej przekątnej) constn=3: type tablica = array Cl..n,l..n,l..n] ofinteger; var t : tabl i ca ; f anal i zowana tabl i ca ) xl,yl,zl, ( wspdlrzgdnejednego końca przekątnej ) x2,y2,z2: f wspblrzgdne drugiego końca przekątnej ) integer; procedure Czytaj Cvart: tablica); ( Procedura wczytywania elementów tablicy trzywymiarowej ) var i, j, k : i nteger ; { zmi enne kontro I ne pgt I i ) begin for i :=1 to n do for j :=1 to n do fork:=ltondo . begin write C'C',i:2,',',j#2,',',k:2,') = '); readln Ct Ci,j,k]) end end; procedure Drukuj Ct: tablica); ( Procedura drukowania elementów tablicy trzywymiarowej ) var i, j, k : i nteger ; ( zmi enne kontrol ne pgtl i ) begin fori:=ltondo Nauka programowania... begin for j :=1 to n do begin fork:=ltondo write Ct Ci,j,k]:4); wri tel n end; writeln end end; function Przekatna Ct: tablica; xl,yl,zl,x2,y2,z2:integer):integer; ( Funkcja obl i czani a sumy el ementów 1 eżdcych na przekdtnej owspółrzgdnych jednego końća xl,yl,zl i współrzędnych drugi ego końca x2,y2, z2 ) var i, j, k : i nteger ; ( zmi enne wyznaczaj #ce kol ejne el ementy na przek#tnej ) dx, ( zmi ana w ki erunku x ) dy, ( zmi ana w ki erun ku y ) dz : ( zmi ana w ki erunku z ) integer; suma : integew; ( suma el ementów na przek#tnej ) kroki, 11 i czba el ementów na przekątnej ) ster : f zmi enna steruj dca obl i czani em sumy el ementów ) integer; begin, dx := 0; dy := 0; dz := 0; kroki :=1; if x2 - xl C# 0 then # begin dx := (x2 - xl) div absCx2 - xl); kroki := absCx2 - xl ) + 1 end; if y2 - yl C# 0 then begin dy := Cy2 - yl ) di v abs Cy2 - yl ) ; kroki := absCy2 - yl ) + 1 end; -14 - 3. Tablice (uzupełnienie) if z2 - zl C> 0 then begin dz := Cz2 - zl) div absCz2 - zl); kroki := absCz2 - zl ) + 1 end; suma :=0; i := xl ; j := yl ; k := zl ; for ster :=1 to kroki do begin suma := suma + tCi,j,k] ; C ustawienie wspólrzgdnych następnego elementu przekatnej ) k := k + dz ; j:=j+dy; i := i + dx end; przekatna := suma end; begin writeln C'Wczytanie tablicy trzywymiarowej:'); Czytaj Ct); writeln C'Wczytane wartości:'); Drukuj Ct); wri tel n ; writeln C'Wspólrzgdne punktu poczatkowego'); readlnCicl,yl,z1); writeln C'Wspdlrzgd_ne#-unktu koń Gswego'); readln Cx2,y2,z2); fsprawdzenie czy wczytane współrzędne nie wyprowadzaj# poza tabl i cę ) if Cxl in [1. .n]) and Cyl in [1. .n]) and Czl in [1. .n]) and Cx2 in [1. .n]) and Cy2 in [1. .n)) and Cz2 in [1. .n]) then writeln C'Przekatna C',xl,',',yl, '.',zl,') - C'.x2,',',y2, ,',z2,') = ',Przekatna Ct,xl,yl,zl,x2,y2,z2)) el se -15 - Nauka programowania... end. writeln('Bład danych') 3.2. Zadania 1. Napisać program znajdowania minimalnego i maksymalnego elementu w tablicy trójwymiarowej oraz jego położenia. 2. Napisać program tworzenia wektora zawierającego sumy elementów tablic dwuwymiarowych odpowiadająeych pierwszemu indeksowi tablicy trzywymiarowej. 3. Napisać program wyznaczania iloczynu oraz sumy elementów tablicy trzywymiarowej różnych od zera. 4. Napisać program wyznaczania sumy tych elementów tablicy trzywymiarowej, których wszystkie indeksy są liczbami parzystymi. -16 - Rozdział MODU#Y Jak już wspomniano w książce [20], w systemie ltzrbo Pascal procedury i funkcje standardowe są umieszczane w tak zwanych modułach. Modułem podstawowym jest moduł System, który jest automatycznie dołączany do każdego programu. Ponadto istnieją jeszcze moduły Dos, Crt, Graph, Printer i Overlay. Przypomnijmy jeszcze, że jeśli chcemy wykorzystać procedury i funkcje zawarte w tych modułach, to należy w czgści głównej programu bezpośrednio po instrukcji prngram użyć instrukcjg uses. Obecnie wyjaśnimy metodg tworzenia własnych modułów, w których można umieścić zaprojektowane procedury i funkcje. Modul tworzy sig w nastgpujący sposób. Piszemy najpierw słowo kluczowe unit, po którym podajemy nazwę modułu. Nazwa pliku, w którym znajduje sig moduł, powinna być taka sama jak nazwa modułu. W treści modułu możemy wyróżnić trzy części: opisową, implementacyjną#oraz iz#icjującą. Część inicjująca musi kończyć sig kropką. Utworzone moduły powinny być przechowywane w plikach o rozszerzeniu.pas. Plik ten należy skompilować w analogiczny sposób jak program, a tekst wynikowy zostanie zapisany w pliku o rozszerzeniu.tpu. Aby wykorzystać skompilowany moduł w programie, należy podać jego nazwę w instrukcji uaes. Wówczas wszystkie procedury i funkcje zdefniowane w module będą dostępne w danym programie. -17 - Nauka programowania... deklaracje modułów Cześć opisowa definicje typów i stałych definic#e zmiennych lista nagłówków procedur i funkcji im I#m#nt#li0n de#nicje procedur i funkcji, który#h nagłbwki podano CzBść implementacyjna w cześci interface definicje typów, stałych i zmienny#ch dostępnych wytącznie wewn#tn modułu Cześć inicjujaca { instrukcja złożona lub słovr# kluczowe #nd ftys. 4.1. Struktura modułu Przykład Moduł podany w przykładzie zawiera dwie procedury Czytąj oraz Drukuj, kt,ńre zostały zaprojekt,owane w poprzednim rozdziale. Procedura Czytąj służy do wprowadzania danych do tablicy trzywymiarowej, a procedura Drukuj umożliwia wyprowadzanie danych. Procedury te mogą być wykorzystywane również w innych programach, dlat.ego jest celowe umieszczenie ich w module. Treść modułu zamieszczono poniżej. unit Wprowadz; interface con5t n=3; type tabl,ica = array C1. .n,l. .n,l. .n] of integer; procedure Czytaj Cvar t: tablica); procedure Drukuj Ct:tablica); implementation procedure Czytaj Cvar t: tablica); { Procedura wczytywania elementów tablicy trzywymiarowej) vari,j,k:integer; begin fori:=ltondo for j :=1 to n do fork:=Itondo -18 - 4. Moduły begin write C'C',i:2,',',j:2 k:2,')= '); readln Ct Ci][j][k]) end end; procedure Drukuj Ct:tablica); ( Procedura drukowania elementów tablicy trzywymiarowej ) var i,j,k: integer; begin for i :=1 to n do begin for j :=1 to n do begin for k :=1 to n do write Ct Ci][j][k]:4); wri tel n end; writeln end end; end. Obecnie pokażemy na przykładzie programu obliczania sumy elementów na dowolnej przekątnej tablicy trzywymiarowej wykorzystanie zaprojektowanego wyżej modułu Wprowadz. W celu użycia zamieszczonych tam procedur Czytaj oraz Drukuj wystarczy (po skompilowaniu modułu) podać w programie instrukcję: uses Wprowadz; a treści tych #rocedur nie potrzeba już zamieszczać. Gdyby procedura Przekatna- miała być t#ykorzystywana w innych programach, to również można ją umieścić w module. W przedstawionym niżej programie procedura ta jest podana bezpośrednio w treści programu. Program 4.1 program Trzywymiary; fProgram obliczania sumy elementów leżących na dowolnej przek#tnej) uses Wprowadz; var t : tabl i ca ; C anal i zowana tabl i ca ) -19 - Nauka programowania... xl,yl,zl, t wspólrzędnejednego końca przekątnej ) x2,y2,z2: C wspólrzgdne drugiego końca przekatnej ) integer; function Przekatna Ct: tablica; xl,yl,zl,x2,y2,z2: integer):integer; ( Funkcja obliczania sumy elementów leżących na przekątnej o wspólrzgdnychjednego końca xl,yl,zl i wspólrzgdnych drugi ego końca x2,y2, z2 ) var i,j,k:integer; ( zmienne wyznaczające kolejne elementy na przekątnej ) dx, f zmi ana w ki erunku x ; dy, Ć zmi ana w ki erunku y ) dz : ( zmi ana w ki erunku z ) integer; suma: integer; ( suma elementów na przekątnej ) kroki, ( 1 i czba el ementów na przek#tnej ) ster : ( zmi enna steruj ąca obl i czani em sumy el ementów ) integer; begin dx := 0; dy := 0; dz := 0; kroki :=1; if x2 - xl C# 0 then begin dx := Cx2 - xl) div absCx2 - xl); kroki := absCx2 - xl ) + 1 end; ify2 - yl C# 0 then beg;in dy := Cy2 - yl ) di v abs Cy2 - yl ) ; kroki := abs(y2 - yl) + 1 end; if z2 - zl C# 0 then begin dz := Cz2 - zl) div absCz2 - zl); kroki := abs(z2 - zl) + 1 end; -20- 4. Moduły suma :=0; i := xl ; j := yl ; k := zl ; for ster :=1 to kroki do begin suma := suma + tCi,j,k]; f ustawienie wspblrzędnychnastgpnego elementu przekdtnej ) k:=k+dz; j:=j+dy: i := i + dx end; przekatna := suma end; begin writeln C'Wczytanie tablicy trzywymiarowej:'); Czytaj Ct); writelnf'Wczytane wartości:'); Drukujft); wri tel n ; writelnf'Współrzgdne punktu poczatkowego'); readlnfxl,yl,zl); writelnf'Wspó#rzgdne punktu końcowego'); readlnfx2,y2,z2); if fxl in [1. .n]) and fyl in [1. .n]) and Czl in [1. .n]) and fx2 in [1. .n]) and Cy2 in [1. .n]) and fz2 in [1. .n]) then writelnf'Przekatna f',xl,',',yl, ',',zl,') -f',x2,', ,y2, ',',z2,') = ',Przekatna Ct,-xl,yl,zl;x2,y2,z2)) el se writelnf'Bl#d danych') end - 21- Rozdział PLIKI TEKSTOWE I OPER#AC#E NA TEKSTACH W niniejszym rozdziale omówimy pliki tekstowe tzn. takie, w których dane są przedstawiane w postaci ciągu znaków. W następnym rozdziale omówimy pliki elementowe, w których dane są przedstawiane w postaci zakodowanej, niemożliwej do odczytania przez edytor. 5.1. Pliki input i output Pliki input i output są standardowymi plikami tekstowymi zawierąjącymi dane do programu i wyniki wykonania programu. Plik input może być wczytywany tylko jeden raz, natomiast inne pliki tekstowe mogą być wczytywane wielokrotnie. Do wprowadzania danych i wyprowadzania wyników służą instrukcje read, readln, write, writeln, które zostały omówione w książce [20) pierwszej w cyklu poświęconym nauce programowania. Przy wprowadzaniu i wyprowadzaniu danych można wykorzystywać funkcjg eofi) stwierdzającą, czy osiągnęliśmy koniec pliku oraz funkcję eoln() stwierdząjącą czy osiągngliśmy koniec linii. Wykorzystanie tych funkcji -22- 5. Pliki tekstowe i operacje na tekstach zostanie omówione w następnym punkcie poświgconym plikom tekstowym. 5.2. Pliki tekstowe Pliki tekstowe są to pliki zawieraj#ce informację niezakodowaną, czytelną w bezpośredni sposób. Plik tekstowy deklarujemy w sposób nastgpujący: var nazwa#pliku: text; gdzie nazwa plikujest nazwą tak zwanej zmiennej plikowej. Przed wykonaniem jakichkolwiek operacji na tekście przechowywanym w pliku na dysku powinniśmy najpierw przyporządkować nazwg pliku dyskowego do konkretnej zmiennej plikowej wykorzystywanej w programie. Do tego celu służy procedura standardowa assign. Jej wywołanie jest postaci: assign(nazwa#pliku, nazwa dysk); gdzie nazwa pliku jest nazwą zmiennej plikowej w programie, a nazwa dysk jest nazwą pliku na dysku. Następnie należy otworzyć plik przy pomocy jednej ze standardowych procedur rewrite, reset lub append. Dokonuje sig tego w sposób następujący: rewrite(nazwa pliku); lub reset(nazwa pliku); lub append(nazwa pliku); Między procedurami reset oraz rewrite istnieje drobna ale istotna różnica. Otóż procedura reset.otwiera tylko już istniejący plik (w przypadku próby otwarcia nie istniejącego pliku zostanie zasygnalizowany błąd). Natomiast procedura rewrite otwiera dany plik nawet wtedy, gdy nie istniał on poprzednio na dysku. Jednak przy zastosowaniu tej procedury jest wymagana szczególna ostrożność. Jeśli plik istniał na dysku, to użycie procedury rewrite spowoduje nadanie mu zerowej długości. Procedura append powoduje otwarcie pliku wyłącznie do zapisu (dane będą dopisywane na koniec pliku). Po wykonaniu żądanych operacji na pliku należy go koniecznie zamknąć przy pomocy procedury close o postaci: close(nazwa pliku); -23- Nauka programowania... Zapisywanie i odczytywanie danych z plików tekstowych dokonujemy przy pomocy instrukcji read, readln, write oraz writeln, które zostały omówione w [20]. Obecnie instrukcje te wzbogacimy o podanie nazwy pliku. Po tym uzupełnieniu postać tych instrukcji jest następująca: read(nazwa pliku,lista argumentów); write(nazwa pliku,lisfa argumenfów); Poniższe przykłady zilustrują wykonywanie operacji na plikach tekstowych. Przykład W przykładzie podarny program realizujący zapisywanie i odczytywanie danych z plików tekstowyeh. Po uruchomieniu programu można obejrzeć zawartości utworzonych plików tekstowych. Będziemy wykorzystywać trzy pliki, wszystkie tekstowe, z których jeden przechowuje liczby całkowite, drugi liczby rzeczywiste, a trzeci znaki. Program 5.1 program Tekst 0 ; ( Program i 1 u5truj#ey zapi sywani e i odczytywani e danych z pl i ków tekstowych ) const n=10; var pl i kcal k,( pl i k z 1 i czbami cal kowi tymi ) pl i krzecz,[ pl i k z 1 i czbami rzeczywi stymi ) pl i k#l ow : ( pl i k ze znakami ) text; i, [ zmi enna kontrol na pętl i ) m: i nteger ; ( zmi enna pomocni cza ) `x, y: real ; ( zmienne pomocnicze ) slowo: string[10]; f zmienna pomocnicza ) begin assi gn Cpl i kcal k, 'tl ' ) ; ( przyporz#dkowani e nazwy do pl i ku ) rewri te C pl i kcal k ) ; ( otworzeni e pl i ku ) assign Cplikrzecz,'t2'); rewrite Cplikrzecz); assign Cplikslow,'t3'); rewrite Cplikslow); -24- 5. Pliki tekstowe i operacje na tekstach for i :=1 to n do write Cplikcalk,i:4); fori:=ltondo begin x:=0.345*i; writeCplikrzecz, x:8:3 ) end; fori:=ltondo write Cplikslow,'a'); reset C pl i kcal k ) ; f otworzeni e pl i ku ) whi 1 e not eof C pl i kca 1 k ) do begin read Cplikcalk,m); write Cm:8) end; writeln; reset Cplikrzecz); whi 1 e not eof C pl i krzecz) do begin read Cplikrzecz,y); write Cy:10:3) end; wri tel n; reset Cplikslow): while not eof Cplikslow) do begin read Cplikslow,slowo); writeCslowo, '' ) end end. Przykład 1#-eścią przykładu jest procedura urnożliwiająca kopiowanie zawartości pliku tekstowego linia po linii. W podanym programie warto zwrócić uwagę na -25- Nauka programow#nia.. wykorzystanie funkcji eofi), ktńra podaje wartość true, jeżeli napotkamy koniec pliku. Program 5.2 program Tekst#l; f Kopi owani e pl i ku tekstowego 1 i ni ami ) var pi erwszy, f pl i k pi erwszy ) drugi : f pl i k drugi ) text; 1i ni a : stri ng[80] ; f jedna 1i ni a tekstu ) nazwa 1, f nazwa pl i ku pi erwszego ) nazwa#2: f nazwa pl i ku drugi ego l string C20]; procedure Kopiuj Cnazwa#l,nazwa#2: string); f Procedura kopi owani a pl i ków ) begin assignCpierwszy,nazwa#l); f przyporz#dkowanie nazwy do pliku ) reset C pi erwszy ) ; f otworzeni e pl i ku ) assign Cdrugi,nazwa 2); rewri te Cdrugi ) ; f otworzeni e pl i ku ) whi 1 e not eof C pi erwszy ) do begin f odczytanie jednej linii tekstu ) ' readln Cpierwszy,linia); f zapi sani e jednej 1 ini i tekstu ) writelnfdrugi,linia) end; cl ose C pi erwszy ) ; f zamkni ęci e pl i ku ) close Cdrugi); wri tel n C ' Skopi owano pl i k ', nazwa#l, ' do pl i ku ',nazwa#2 ) end; begin writeln C'Podaj nazwę pliku wejściowego:'); readln Cnazwa#l); -26- 5. Pliki tekstowe i operacje na tekstach writeln('Podaj nazwg pliku wyjściowego:'); readln Cnazwa 2); Kopi uj Cnazwa#l,nazwa 2 ) f skopi owani e pl i ku o nazwi e nazwa#l ) end. Przyhład W odróżnieniu od poprzedniego przykładu obecnie podamy procedurg kopiowania pliku tekstowego znak po znaku. Procedura ta zostanie wykorzystana w programie l#ekst 2. Warto zwrócić uwagg na funkcjg eoln(), która umożliwia przetwarzanie znaków umieszczonych w jednej linii. Funkcja ta podaje wartość true, gdy napotkano koniec pliku. Program 5.3 program Tekst 2 ; f Kopi owani e pl i ku tekstowego znak po znaku ) var pi erwszy, f pl i k pi erwszy ) drugi : f pli k drugi ) text; znak: char; f jeden znak tekstu ) nazwa#l, f nazwa pl i ku pi erwszego ) nazwa#2: f nazwa pl i ku drugi ego ) string[20]; procedure Kopiuj Cnazwa#l,nazwa#2: string); f Procedura kopi owani a pl i kdw ) begin assign(pierwszy,nazwa#l); f przypisanie nazwy ) reset C pi erwszy ) ; f otworzeni e pl i ku ) assign Cdrugi,nazwa 2);# rewrite Cdrugi); whi 1 e not eof( pi erwszy ) do begin f skopi owani e do końca 1 ini i ) while not eoln Cpierwszy) do begin read Cpierwszy,znak); write Cdrugi,znak) -27- Nauka programowania... end; readlnCpierwszy); f odczytanie znaku końca linii ) wri tel n Cdrugi ) f zapi sani e znaku końca 1 i ni i ) end; cl ose C pi erwszy ) ; f zamkni ęci e pl i ku ) close Cdrugi); writeln C'Skopiowano plik end; ', nazwa#l, ' do pl i ku ',nazwa#2) begin writeln C'Podaj nazwg pliku wejściowego:'); readln Cnazwa 1); writeln C'Podaj nazwg pliku wyjściowego:'); readln Cnazwa 2); Kopi uj Cnazwa#l, nazwa 2 ) f skopi owani e pl i ku o nazwi e nazwa#l ) end. Przykład W przykładzie podamy procedurg umożliwiającą podanie liczby znaków zawartych w pliku tekstowym. Wykorzystany algorytm polega na przejrzeniu wszystkich znaków w tekście i zliczeniu ich liczby. Przeglądanie odbywa sig linia po linii z wykorzystaniem funkcji eoln(). Progra#z 5.4 program Tekst 3 ; f Program zliczania znaków ) var - pl i k : t"ext ; f pl i k, w którym zostan# zl i czone znaki ) n : i nteger ; f 1 i czba znaków w pl i ku ; nazwa: string[12]; f nazwa pliku ) procedure Znaki Cnazwa: string; varliczba:integer); f Procedura zl i czani a znaków w pl i ku, nazwa - nazwa pl i ku, 1 i czba - 1 i czba znaków w pl i ku ) var znak: char; f jeden znak tekstu ) -28- 5. Pliki tekstowe i operacje na tekstach begin assign Cplik,nazwa); reset Cplik); 1 i czba := 0 ; whi 1 e not eof C pl i k ) do begin ( przetwarzaniejednej linii tekstu ) while not eoln Cpl i k) do begin read Cplik,znak); 1 i czba :=1 i czba + 1 end; readlnCplik) f wczytanie znaku końca linii ) end; close Cplik) end; begin writeln C'Podaj nazwę pliku'); readln Cnazwa); Znaki Cnazwa.n); writelnC 'Liczba znaków w pli ku ',nazwa, ' wynosi ',n:5) end. Przyklad W odróżnieniu od poprzednie;gn przykładu tematem którego było podanie liczby znaków tekstu, obećnie zaprojektujemy procedurg, która umożliwia wyznaczenie liczby wierszy tekstu. Podobnie jak w poprzednim przykładzie są przeglądane wszystkie znaki te#stu, a obliczanie liczby wierszy odbywa się dopiero w momencie zakończenia przeglądania danego wiersza tekstu. Program 5.6 program Tekst 4; C Program obl i czani a 1 i czby wi erszy w pl i ku tekstowym ; var pl i k : text ; i pl i k, w ktbrym zostan# zl i czone wi ersze ) -29- Nauka programowania... n : i nteger ; { 1 i czba wi erszy w pl i ku ) nazwa : string[12] ; { nazwa pl i ku ) procedure Wiersze Cnazwa: string; varliczba:integer); { Procedura obl i czani a 1 i czby wi erszy ) var znak : char ; { j eden znak w pl i ku ) begin assign Cplik,nazwa); reset Cplik); liczba := 0; whi 1 e not eof C pl i k ) do begin { przetwarzani e jednego wi ersza tekstu ) while not eoln Cpl i k) do read Cplik,znak); readln Cplik); 1 i czba :=1 i czba + 1 { zwi ększeni e 1 i czby wi erszy ) end; close Cplik) end; begin writeln C'Podaj nazwg pliku'); readln Cnazwa); Wiers#e Cnazwa,n); writelnC 'Liczba wierszy w pliku ',nazwa, ' wynosi ',n:5) end. Przykład Przykład jest poświgcony obliczeniu liczby słów w pliku tekstowym. Zakładamy, że poszczególne słowa są oddzielone znakiem spacji, tabulacji lub końcem linii. Ponadto zakładamy, że między słowami może być tylko jeden znak spacji. Obliczenie liczby słów realizuje procedura Slowa, której algorytm jest podany poniżej. Algorytm 5.1. podczas gdy nie napotkano symbolu końca pliku wykonuj '3O' II 5. Pliki tekstowe i operacje na tekstach wczytaj znak jeśli znak jest symbolem końca słowa to zapamiętaj, że nowe słowo w przeciwnym przypadku jeśli nowe słowo to zwiększ licznik słów zapamiętaj, że nie nowe słowo A oto program t#stujący procedurg Slowa. Program 5.? program Tekst#5: ( Program obl i czani a 1 i czby sl6w w pl i ku tekstowym ) Con St TABU LACJA = 9 ; var pl i k : text ; f pl i k, w którym zostand zl i czone slowa ) n : i nteger ; ( 1 i czba sł 6w w pl i ku ) nazwa : stri ng[12) ; ( nazwa pl i ku ) procedure Slowa Cnazwa: string; varliczba:integer); ( Procedura obl i czani a 1 i czby sl6w w pl i ku ) var znak: char; ( jeden znak z pl"iku ) noweslowo: boolean; begin . assign Cplik,nazwa); reset Cplik); liczba :=0; whi 1 e not eof C pl i k ) do begin read Cplik,znak); if Cznak= '') oreolnCplik) or Cord Cznak) = TABULACJA) then noweslowo := true el se i f nowesl owo then Nauka programowania... begin 1 i czba :=1 i czba + 1; noweslowo := false end end; close Cplik) end; begin writeln C'Podaj nazwę pliku'); readln Cnazwa); Slowa Cnazwa,n); writelnC'Liczba słówwpliku ',nazwa,' wynosi ',n:5) end. Przykład Przykład zawiera funkcję porównywania zawartości dwóch plików tekstowych. Wykorzystany algorytm polega na sprawdzaniu równości znaków do końca krótszego pliku, a następnie w przypadku pozytywnego wyniku na sprawdzeniu długośoi plików. Pro#ram 5.8 program Tekst 6 ; ( Program porównywani a dwóch pl i ków tekstowych ) var # pierwszy, drugi: text; nazwa 1; nazwa 2: string[12]; f pl i k pi erwszy ) ( pl i k drugi ) f nazwa pl i ku pi erwszego ) f nazwa pl i ku drugi ego ) function Porownaj Cnazwa#l,nazwa#2: string):boolean; f Funkcja porównywani a dwóch pl i ków tekstowych ) var znakl, C odczytany znak z pliku pierwszego ) znak2 : f odczytany znak z pl i ku drugi ego ) char; -32- 5. Plihi tehstowe i operacje na tehstach bl ad : bool ean ; Czmi enna i nformujaca o rbwności pl i kbw) begin assignfpierwszy,nazwa#l); reset Cpierwszy); assign Cdrugi,nazwa 2); reset Cdrugi); bl ad := true ; ( pl i ki sa jednakowe ) f sprawdzeni e znaków do końca krbtszego pl i ku ) while blad and not eoffpierwszy) and not eofCdrugi ) do begin read Cpierwszy,znakl); readCdrugi,znak2); if znakl C# znak2 then bl ad := fal sef pl i ki s# rbżne ) end; f jeśl i różna długość pl i k6w ) if not C eof C pi erwszy ) = eof C drugi ) ) then blad := false; close Cpierwszy); close Cdrugi); Porownaj : = bl ad end; begin writeln C'Podaj nazwę pliku wejściowego#'); readln Cnazwa#l); writeln('Podaj nazwę pliku wyjściowego:'); readln Cnazwa 2); if Porownaj Cnazwa#l,nazwa#2) then wri teln C ' Pl i ki s# identyczne ' ) el se writelnC' Pliki nie s# identyczne') Ostatni przykład jest poświgcony nieco trudniejszemu problemowi, a nowicie wyświetlaniu na ekranie zawartości pliku tekstowego. W trakcie -33- Nauka programawania... wyświetlania można wykorzystywać pewne klawisze umożliwiające sterowanie przesuwaniem tekstu. Przykład W przykładzie zaprojektujemy program umożliwiający wyświetlanie na ekranie zawartości pliku tekstowego. Podczas wyświetlania tekstu powinniśmy mieć możliwość jego przewijania o jedną linig w górę lub w dół oraz o jedną stronę w górg lub w dół. Dostępne powinny być zatem następujące klawisze: strzałka w górę, strzałka w dół oraz PgDn i PgUp. Ponadto naciśnięcie klawisza Esc powinno zakończyć wyświetlanie tekstu. Sterowanie pracą programu odbywa się przy pomocy funkcji Menu(), która podaje odpowiednią wartość w zależności od naciśniętego klawisza. W przypadku naciśnigcia klawisza strzałka w górg jest wywoływana procedura Poprzedni, natomiast naciśnięciu klawisza strzałka w dół powoduje wywołanie procedury Nastepny, a po naciśnigciu klawiszy PgDn i PgUp są odpowiednio wywoływane procedury Strona dol i Strona#gora. W programie jest ponadto wykorzystywana procedura Wyswietl umożliwiająca wyświetlenie tekstu poczynając od wskazanej linii. Kompletną treść programu zamieszczono poniżej. W programie użyto następujących funkcji i procedur zawartych w module Crt: CIrScr, GotoXY, InsLine, TextBackground, TextColor, Window. Ich działanie jest wyjaśnione w komentarzach zamieszczonych w programie. Program 5.9 Program Pokaz; ( Program wyświ etl ani a zawartości pl i ku tekstowego } uses crt#; const ..max#line=80; C maksymalna liczba znakóww linii } max#row = 500 ; C maksymal na 1 i czba 1 i ni i w pl i ku } var pl i k : text ; C anal i zowany pl i k tekstowy ; nazwa : string[12] ; ( nazwa pl i ku } tablica: array Cl..max#row] ofstring[max#line); max: integer; C maksymalna liczba zajgtych wierszy tablicy} linia: integer;f aktualna linia tekstu } koniec: boolean; ( sterowanie zakończeniem pracy programu ) procedure Wyswietl Ca:integer); -34- 5. Pliki tekstowe i operacje ha tekstach ( Wyświetlenie tekstu na ekranie poczynaj#c od linii o numerze a ) var j:integer; begin C1 rScr ; C wyczyszczeni e ekranu ) j := a; C podczas gdy ni e wyjdzi emy poza ekran 1 ub poza koni ec tekstu ) while Cj C a + 23) and fj C max) do begin writeln; f wydruk j -tej 1 ini i tek5tu ) write Ctablica Cj]); j;=j+1 end; end procedure Nastepny; ( Wyświ etl eni e nastgpnej 1 i ni i tekstu ) begin if 1 i ni a + 25 C max then f jeśl i ni e wyjdzi emy poza koni ec tekstu ) begin f ustawi eni e kursora w 231 i ni i i w 80 kol umni e ) gotoxy C80,23); linia := linia + 1; writeln; fwyświ etl eni e nowej 1 i ni i tekstu na dol e ekranu ) writeCtablicaClinia + 24]) # end end; procedure Poprzedni ; - # - ( Wyświ etl ani e poprzedni ej 1 i ni i tekstu ) begin if 1 inia # 1 then f jeśli nie wyjdziemy poza poczatek tekstu ) begin linia := linia - 1; gotoxy Cl,l); InsLine; f wstawienie linii ) Cwyświ etl eni e nowej 1 i ni i tekstu na gdrze ekranu) -35- Nauka programowania... end end; write Ctablica Clinia)) procedure Strona#gora; ( Przesunigcie tekstu jedn# stronę w gdrg ) begin if linia # 1 then begin linia := linia - 23; if linia C 1 then linia :-1; Wyswietl Clinia) end end; procedure Strona Dol; C Przesunigcie tekstu jedna stronę w d61 ) begin if linia C max - 23 then begin linia := linia + 23: if linia # max - 23 then linia :=max - 23; Wyswietl Clinia) end end; functiott Menu : integer; C Sterowanie prac# programu ) var znak: char; begin # i sprawdzenie ostatnio naciśnigtego klawisza, kody używanych kl awi szy : 27 - Esc, 72 - strzalka w górę 73 - PgUp 80 - strzałka w dól 81 - PgDn ) repeat -36- 5. Pliki tekstowe i operacje na tekstach znak := ReadKey; l wczytanie znaku ) until znak in Cchr CBO),chr C72),chr C73),chr C81),chrf27)]; if ordfznak) = 27 then menu := 0 ( klawisz Esc ) else if ordCznak) = 80 then menu :=1 ( klawisz strzalka w d61 ) else if ordCznak) = 72 then menu := 2 t klawisz strzałka w gbrę ) else if ordCznak) = 81 then menu := 3 ( kl awi sz PgDn ) else if ordCznak) = 73 then menu := 4 f klawisz PgUp ) end; begin C1 rScr ; Goto XYC1,24); writeln C' 'l: wri te C ' Podaj nazwg pl i ku : ' ) ; readln Cnazwa); Assign Cplik,nazwa); reset Cplik); ( wpi sywani e wi erszy tekstu do tabl i cy ) max :=1; while not eofCpl i k) do begin readln Cplik,tablica Cmax]); max := max + 1 end; TextBackgroundCWhite); C Kolor tla: bialy ) TextColorCBlack); ( Kolor tekstu: czarny ) Goto X Y Cl,l); C1 r Eol ; f wyczyszczeni e do końca 1 i ni i ) -37- Nauka programowania... writeC ' W & W Obejrzyj ', 'Liczba lini i : :60,max-1); Goto XYC1,25); ClrEo1; writef' Plik: ', nazwa, '@K. Walczak ':65); Text Background C Black); f Kolor tla: czarny ) TextColorCWhite);f Kolor tekstu: biały ) window Cl,2,80,24); ( ustawienie okna do wyprowadzania tekstu ) ; linia:=1; wyswietl Clinia); koni ec := fal se; repeat case Menu of 1: Nastepny ; f przesuni gci e o j edn# 1 i ni ę w d61 ) 2 : Poprzedni ; ( przesuni ęci e o j edn# 1 i ni ę w gbrg ) 3 : Strona dol ; f przesuni ęci e o strong w dól ; 4: Strona#gora; ( przesunięcie o stronę w górę ) 0 : begin windowCl,1,80,25); C okno na caly ekran ; Cl rScr ; koni ec := true ( koni ec pracy programu ; end end unti 1 koni ec end. 5:#. Wyprowadzanie danych na drukarkg Wyprowadzanie danych na drukarkę zilustrujemy przykładem. Przykład W przykładzie podamy dwa programy umożliwiające skierowanie wydruku na drukarkę. Program 5.10 program Wydruk#l; 5. Pliki tekstowe i operacje na tekstach var plik: text; begin assign Cplik,'lptl'); rewrite Cplik); writeln Cplik,'Pewien tekst'); closeCplik) end. Powyższy program można skrócić wykorzystując dostępny w języku ltzrbo Pascal moduł Printer. Po przyłączeniu modułu należy następnie użyć standardową zmienną lst, która oznacza kierowanie wydruku na drukarkę. Program 5.11 program Wydruk#2; uses Printer; begin writeln Clst,'Pewien tekst') end. 5.4. Operacje na tekstach W tym punkcie zilustrujemy dwoma przykładami wykonywanie operacji na tekstach przechowywanych w plikach tekstowych. Najpierw jednak wspomnimy o kilku podstawowych funkcjach #działających na zmiennych typu łańcuchowego. Dokładny opis tych funkcji można znaleźć w pracy [14]. Concat(x,y), sklejenie, takie samo działanie jak x + y I.enght(x) podaje długo#ć zmiennej"x Pos(x,znak)podaje pozycję pierwszego wystąpienia znaku znak w zmiennej x Delete(x,n,k) usuwa k znaków ze zmiennej x zaczynąjąc od pozycji n Zmienne typu łańcuchowego można ze sobą porównywać przy pomocy operatorów <, >, <>. Istnieje rownież możliwość wstawienia odpowiedniego znaku na daną pozycję. Dokonuje się tego w sposób następujący: x[n] :=znak gdzie x tak jak i poprzednio jest zmienną typu łańcuchowego, znak zmienną typu znakowego. -39- Na#a pr#gramowania... Przyhład W przykładzie zaprojektujemy program centrowania tekstu w każdej linii pliku tekstowego. Centrowanie polegać bgdzie na umieszczeniu każdej linii tekstu na środku wydruku. W programie jest wykorzystana procedura Usun#spacje, która pozwala na usunigcie spacji umieszczonych na początku i na końcu tekstu. Po usunięciu tych spacji wyznaczamy długość "czystego" tekstu, co umożliwia wyznaczenie liczby spacji, ktńre powinny zostać umieszczone na początku linu po to, by tekst znalazł sig na środku. Program 5.12 program Centruj; f Programcentrowania tekstuw każdej linii pliku } const max#l i ne = 80 ; type jedna#linia = string[max#line]; var plikl, f plikwejściowy } pl i k2 : f pl i k wyj śCi owy } text; linia: jedna#linia; f linia tekstu ) nazwa#l, f nazwa pl i ku wej ści owego } nazwa#2: f nazwa pli ku wyjściowego } string[12); spacje:integer; function Usun#spacje Clinia:jedna#linia):jedna#linia; f Usunięcie poczatkowych i końcowych spacji z jednej linii tekstu } var n, f dlugość linii } i. f zmienna pomocnicza startuj#ca od pocz#tku linii j: f zmienna pomocnicza startujdca od końca linii } integer; wynik:jedna#linia; begin n := Length Clinia); i :=1; j :=n; wynik := ', -40- 5. Pliki tekstowe i operacje na tekstach C wyznaczeni e 1 i czby spacj i od poczatku 1 i ni i ) while Ci C= n) and CliniaCi]='' ) do i := i + 1; f wyznaczenie liczby spacji od końca linii ) while Cj C=n) and fliniaCj] = '') doj :=j - 1; f przepi sani e tekstu bez pocz#tkowyeh i końcowych spacj i ) whi 1 e i C= j do begin wynik:=wynik+liniaCi]; i:#i+1 end; Usun spacje := wyni k end; begin writeln C'Podaj nazwg pliku wejściowego:'); readln Cnazwa#l); writeln C'Podaj na2wg pliku wyjściowego:'); readln Cnazwa 2); assign Cplikl,nazwa#l); reset Cplikl); assignCplik2,nazwa 2); rewrite Cplik2); while not eofCplikl) do begin re,adlnCplikl,linia); f wyznaczeni e 1 i czby spacj i na pocz#tku drukowanej 1 inůi i jspacje := Cmax#line - Length C Usun#spacje Clinia))) div2; writeln Cplik2,' :spacje, Usun#spacje Clinia)); end; close Cplikl); close Cplik2); end - 41- Nauka programowania... Przykład Poniżej zamieszczono program testujący procedurg Usun, która umożliwia usunigcie z tekstu zdefiniowanego fragmentu. Usuwane są wszystkie wystąpienia tego fragmentu tekstu. Przy usuwaniu jest wykorzystywana standardowa procedura Delet#, a przy wyznaczaniu położenia danego fragmentu standardowa procedura Pos. Program 5.13 program Usuwanie; f Program usuwani a z tekstu zdefi ni owanego fragmentu ) var x, C tekst podstawowy ) y: ( fragment tekstu do usunigcia ) string; procedure UsunCvar tekst, zam: string) ; C Usuwanie tekstu zam z tekstu tekst ) var nr: integer; ( numer pozycji wyst#pienia tekstu ) begin repeat C wyznaczenie kolejnej pozycji wyst#pienia tekstu zam ) nr :=PosCzam,x); ifnrC#Othen ( usunigcie fragmentu tekstu o dlugości Length Czam) poczynaj#c od pozycji nr ) # Delete Cx,nr,Length Czam)); unti 1 nr = 0 end; beg i n # x := 'Ala ma ma kota ma '. y := 'ma ' Usun Cx,y); writeln Cx) end. W wyniku wykonania programu otrzymamy wydruk: Ala kota -42- 5. Pliki tekstowe i operacje na tekstach 5.5. Zadania 1. Napisać program kopiowania jednego pliku tekstowego do drugiego zastępując jednocześnie każdy ciąg spacji jedną spacją (ciąg spacji na początku wiersza ma pozostać bez zmiany). 2. Napisać program wczytywania słowa i obliczania ile razy to słowo wystąpiło w danym tekście. 8. Napisać program zastępowania wyróżnionego słowa w tekście innym słowem. 4. Napisać program usuwania zdefiniowanej linii w tekście. 5. Napisać program wstawiania podanego tekstu po określonej linii tekstu. 6. Napisać program znajdowania najdłuższego słowa w tekście. 7. Napisać program drukowania pliku tekstowego na drukarce wraz z numerami linii. 8.Zmodyfikować program Pokaz tak, by możliwe było przewijanie plików tekstowych o dowolnej długości. 8.Napisać program drukowania tekstu dowolnego programu zapisanego w języku Pascal w ten sposób, by słowa kluczowe były pogrubione. -43- Rozdział PLIKI ELEMENTOWE Pliki elementowe są to pliki, w których przechowywana informacja jest przedstawiona w postaci zakodowanej niemożliwej do bezpośredniego odczytania. Deklaracja zmiennej plikowej dla pliku elementowego jest postaci: nazwa pliku: flle of typ składowy gdzie nazwa pliku jest nazwą zmiennej plikowej, a typ#składowy jest typem prostym lub strukturalnym (typ#składowy nie może być typem plikowym lub wskaźnikowym). PodObnie jak dla plików tekstowych przyporządkowanie nazwy pliku dyskowego do konkretnej zmiennej plikowej dokonujemy przy pomocy procedury assign. Otwieranie plików wykonujemy przy pomocy procedur re#rite i reset (ale bez procedury append), a zamykanie przy pomocy procedury close. Wykorzystanie plików elementowych zilustrujemy kilkoma przykładami. Przykład W przykładzie podamy program, który umożliwia wykonywanie dwóch podstawowych operacji tzn. wczytywania i wyprowadzania danych z pliku elementowego. Operacje te wykonamy dla dwóch plików: jednego przechowującego liczby całkowite i drugiego przechowującego liczby rzeczywiste. -44- 6. Pliki elementowe Program 6.1 Program Pliki#l; ( Programilustrujacy wykorzystanie plików elementowych } const n#100; var pl i kcal k : fi 1 e of i nteger ; pl i krzecz : fi 1 e of real ; i,m:integer; x,y: real ; begi n assign Cplikcalk,'pl'); rewrite Cplikcalk); assign Cplikrzecz,'p2'); rewrite Cplikrzecz); ( pl i k z 1 i czbami cał kowi tymi } ( pl i k z 1 i czbami rzeczywi stymi } ( przyporządkowani e nazwy do pl i ku } # otworzeni e pl i ku } C zapi s do pl i k6w } for i :=1 to n do writeCplikcalk,i); for i : =1 to n do begin x:=0.345*i; wri te t pl i krzecz, x ) end; C odczytywani e z pl i k6w } reset Cpl i kcal k) ; ( otworzeni e pl i ku } while nQt eofCpli kcal k) do begin read C pl i kca-1 k,m) ;write Cm:4) end; reset C pl i krzecz ) ; ( o.tworzeni e pl i ku } while not eofCpl i krzecz) do begin read Cplikrzecz,y); write Cy:8:3) end -45- Nauka programowania... end. Przykład Z#'eścią przykładu jest program umożliwiający kopiowanie pliku elementowego przechowującego liczby całkowite. Program 6.2 program P1 i ki#2 ; f Program kopi owani a pl i ku el ementowego } type pli k = file of integer; var pierwszy, ( plik, z którego kopiujemy } drugi : ( pl i k, do którego kopi ujemy } plik; nazwa#l, ( nazwa pl i ku pi erwszego } nazwa 2 : ( nazwa pl i ku drugi ego } string[20]; procedure Kopiuj Cvar pierwszy,drugi: plik); [ Kopi owani e pl i ku pi erwszy do pl i ku drugi } var el ement : i nteger ; ( el ement pl i ku } begin while not eofCpierwszy) do begin read Cpierwszy,element); write Cdrugi,element) end '-end ;. begin writeln C'Podaj nazwę pliku wejściowego:'); readln Cnazwa#l); writeln C'Podaj nazwg pliku wyjściowego:'); readln Cnazwa#2); assign Cpierwszy,nazwa#l); reset Cpierwszy); assign Cdrugi,nazwa#2); -46- 6. Pliki elementowe rewrite Cdrugi); Kopiuj Cpierwszy,drugi); close Cpierwszy); close Cdrugi) end. Przykład Zamieszczony niżej program pozwala na utworzenie pliku elementowego przechowującego całe tablice. Program 6.8 program P1 i ki#3 ; ( Tworzeni e pl i ku el ementowego zawi erajdcego tabl i ce ) const n =10; type wyniki = arrayCl. .n] of integer; var tab: wyniki ; plik:fileofwyniki; nazwa : stri.ng[12] ; i:integer; begin wri tel n C ' Podaj nazwg pl i ku ' ) ; readln Cnazwa): assign Cplik,nazwa); rewrite Cplik); f zapi s tabl i c do pl i ku, tabl i ca o zerowym pi erwszym elemencie kończy operację ) repeat writeln C'Podaj tablicg'); fori :=1 to n do read Ctab[i]); write Cplik,tab); until tabCl] =0; -47- Nauka programowania.. f odczytani e tabl i c z pl i ku ) reset Cpl i k) ; f otworzeni e pl i ku ) whi le not eof Cpl i k) do begi n read C pl i k, tab ) ; f odezytani e tabl i cy ) f kontrolne wydrukowanie zawartości tablicy ) for i : =1 to n do write Ctab Ci]:2); wri tel n end; closeCplik) end. Przykład 15"eścią przykładu jest program umożliwiąjący porównanie dwóch plików elementowych przechowujących całe tablice. Wykorzystany algorytm polega na kolejnym porównywaniu zawartości odczytanych tablic aż do końca krótszego pliku i nastgpnie w przypadku uzyskania pozytywnej odpowiedzi na sprawdzeniu długości obu plików Program 6.4 program P1 i ki#4; f Porównywanie dwóch plików elementowych przechowuj#cych tabl i cg ) const n =10; type wyniki = arrayCl. .n] of integer; va#' . pi erwszy, f pl i k pi erwszy ) drugi : f pl i k drugi ) fi le of wyni ki ; tabl, tab2 : wyni ki ; f przeehowywane tabl i ce ) nazwa#l, f nazwa pi erwszego pl i ku ) nazwa 2 : f nazwa drugi ego pl i ku ) string[12]; function Porownaj Cnazwa#l,nazwa#2: string):boolean; -48- 6. Pliki elementowe ( Porównywani e pl i ku nazwa#l z pl i ki em nazwa 2 ) var blad: boolean; i:integer; begin assign Cpierwszy,nazwa#l); reset Cpierwszy); assign Cdrugi,nazwa#2); resetfdrugi); blad :=true; while bl ad and not eof C pi erwszy ) and not eof C drugi ) do begin ( odczytani e tabl i cy z pi erwszego pl i ku ) read Cpierwszy,tabl); C odczytani e tabl i cy z drugi ego pl i ku ) read Cdrugi,tab2); for i :=1 to n do if tabl[i ] C# tab2[i ] then bl ad := fal se f tabl i ce s# różne ) end; C sprawdzenie równości dlugości plików ) if not CeofCpierwszy) = eofCdrugi )) then blad := false; close Cpierwszy); close Cdrugi); Porownaj := blad end; begin writeln C'Podaj nazwę pliku pierwszego:'); readln Cnazwa#l); writeln C'Podaj nazwg pliku drugiego:'); readln Cnazwa#2); if Porownaj Cnazwa#l,nazwa#2) then wri tel n C ' Pl i ki są i dentyczne ' ) else -49- Nauka programowania... end. wri tel n C ' Pl i ki ni e s# i dentyczne ' ) Przykłady dotyczące wykorzystania plików elementowych znajdują się również w rozdziale 8 poświęconym zastosowaniu rekordów. W rozdziale tym są też zamieszczone zadania utrwalające wprowadzony materiał. -50- Rozdział ZBIORY 7.1. Wprowadzenie Jgzyk Pascal umożliwia wykorzystywanie w programach zbiorów teoriomnogościowych, których elementy muszą należeć do pewnego określonego typu. 1#p zbiorowy definiujemy w sposób nastgpujący: type nazwa = set of nazwa typu ; gdzie nazwa jest nazwą typu zbiorowego, a nazwa typu jest nazwą tzw. typu podstawowego, który stanowi elementy #bioru (może to być typ integer, char, boolean, wyliczeniowy lub okrojony). Wartościami zmiennych typu zbiorowego są zatem wszystkie zbiory, które można utworzyć z wartości typu podstawowego oraz zbiór pusty (pusty nie zawiera żadnego elementu). Wartości zmiennym typu zbiorowego nad#emy przy pomocy tzw. konstruktora zbioru, którym jest para nawiasów prostokątnych [], wewnątrz których wpisujemy wartości typu podstawowego. Przykład type abc='a'..'c'; trzyl i tery = set of abc ; var x: trzylitery; - 51- Nauka programowania... Utworzono typ zbiorowy o nazwie trzylitery (typem podstawowym są litery 'a ', 'b ', 'c ') oraz zadeklarowano zmienną x typu trzylitery Wartościami zmiennej x mogą być wszystkie podzbiory zbioru { 'a ', 'b ', 'c ' } oraz zbiór pusty. Poniżej wypisano wszystkie możliwe przypisania wartości zmiennej x przy pomocy konstruktora zbioru []. x :=[]; x:=['a']; x:=C'b']; x:=['c'); x:=['a','b']; x:=['a','c']; x := [ 'b', 'c') ; x := C'a','b','c'); Zauważmy jeszcze, że definicję typu zbiorowego można zawrzeć bezpośrednio w deklaracji zmiennej x: var x: set of 'a'. . 'c' ; Przykład type podstawa =1. .10 ; zbiorl iczb = set of podstawa; var pelny, x, pusty : zbiorliczb; Zadeklarowano zmienne pelny, x, pusty typu zbiorowego, których wartościami mogą być dowolne#podzbiory zbioru {1,...,10}. Wartości tym zmiennym przypiszemy w sposób następujący: pel n# := [1. .10] ; x-:=C3.5,7',9); pusty := [); Wartością zmiennej pelny jest zbiór liczb {1,...,10}, wartością zmiennej x jest zbiór liczb {3,5,7,9}, a zmiennej pusty jest zbiór pusty, który nie zawiera żadnego elementu. Powyższy przykład ilustruje migdzy innymi defnicję tak zwanego zbioru pełnego, czyli takiego, który zawiera wszystkie elementy ze zdefiniowanego typu podstawowego. Warto zwrócić uwagg, że zarówno zbiór pełny jak i -52- 7. Zbiory zbiór pusty są szeroko wykorzystywane w wielu programach, w których operuje sig na zbiorach. 7.2. Operacje na zbiorach Język Pascal umożliwia wykonywanie nastgpujących operacji na zbiorach: Operator Znaczenie t suma zbiorów różnica zbiorów * część wspólna zbiorów Należy również zwrócić uwagg na operator in, który umożliwia stwierdzenie, czy dany element należy do zbioru. Można też wykorzystywać operatory relacyjne: Operator Znaczenie równość zbiorów <> nierówność zbiorów <= oraz => zawieranie się zbiorów Obecnie dla przypomnienia podamy definicjg sumy, różnicy i iloczynu zbiorów. Sumą zbiorów A oraz B jest zbiór, którego elementy należą do zbioru A lub do zbioru B. Iloczynen# zbiorów A oraz B jest zbiór, którego elementy należą do zbioru A i c1ó zbioru B.# Natomiast różnicą zbiorów A oraz B jest zbiór, którego elementy należą do zbioru A, ale nie należą do zbioru B. Wszystkie zdefniowane operacje na zbiorach ilustruje poniższy przykład. Przykład Rozważmy nastgpujący zbiór artykułów sportowych: { narty, kijki, buty nar, łyżwy, sanki, rakiety, piłki, płetwy, okulary#,pływ, rowery, motocykle} -53- Nauka programowania... Następnie przypuśćmy, że sklep A sprzedaje następujące artykuły: { narty, kijki,buty#nar,rakiety,piłki } a sklep B sprzedaje poniżej wymienione artykuły: { rakiety,piłki,płetwy,okulary#,pływ } Powyższe dane możemy w programie zapamiętać przy pomocy struktury danych postaci: type artyk = (narty.kijki,buty#narc.lyzwy,sanki,rakiety, pilki,pletwy,okul#plyw,rowery,motocykle); zbiorartyk = set of artyk; var sklep#A, f artykuly sprzedawane przez sklep A ; sklep#B, f artykuly sprzedawane przez sklep B ; wszystkie, { wszystkie artykuły ; x ( zmienna roboCza wykorzystywana do przechowywaniainformacji o obu sklepach ; : zbiorartyk; Zmiennym wszystkie, sklep-A, sklep-B powinny być nadane następujące wartości: wszystkie := [narty..motocykle]; sklep A := [narty. .pilki]; sklep# B := [rakiety..okul#plyw]; Przy pomocy tych zmiennych oraz poszczególnych operatorów możemy otrzymywać informacje o artykułach sportowych, co ilustruje poniższa tabela: , wyrażenie 1) x := sklep-A + sklep-B 2) x ů- sklep-A * sklep#B 3) # x := sklep#A - sklep-B 4) x := sklep-B - sklep-A 5) x := wszystkie - sklep#A 6) x := wszystkie - sklep-B 7) x := wszystkie - sklep-A - sklep-B wartość zmiennej x [narty..okul-plyw] [rakiety,pilki] [narty.. sanki] [pletwy,okul#plyw] [pletwy..motocykle] [narty. . sanki,rowery,motocykle] [rowery,motocykle] Znaczenie wartości poszczególnych wyrażeń jest następujące: 1) artykuły dostępne w jednym lub drugim sklepie 2) artykuły dostępne w obu sklepach 3) artykuły dostępne w sklepie A i niedostępne w sklepie B -54- 7. Zbiory 4) artykuły dostgpne w sklepie B i niedostępne w sklepie A 5) artykuły niedostgpne w sklepie A 6) artykuły niedostgpne w sklepie B 7) artykuły niedostępne w żadnym sklepie Program ilustrujący przetwarzanie informacji o artykułach sprzedawanych w dwóch sklepach sportowych zostanie zamieszczony w nastgpnym podrozdziale. 7.3. Podstawowe algorytmy W niniejszym podrozdziale podamy podstawowe algorytmy, które umożliwiają wykonywanie operacji na zbiorach. Przede wszystkim zilustrujemy podstawowe operacje, a mianowicie wprowadzanie i wyprowadzanie danych ze zmiennych typu zbiorowego. Jeżeli typem podstawowym nie jest typ wyliczeniowy, to wczytanie i wydruk wartości zmiennej typu zbiorowego odbywa sig wzglgdnie prosto. Zilustrujemy to na przykładzie zmiennych o poniższej deklaracji: type zbi orl i czb = set of 1. .100 ; var x,y: zbiorliczb; Przypomnijmy, że przy takiej deklaracji wartościami zmiennych x i y mogą być wszystkie podzbiory zbioru ( 1,...,100# łącznie ze zbiorem pustym. Procedura CzytąjZbior pozwala na wczytanie dowolnej wartości zmiennej typu zbiorliczb. Algorytm wykorzystany w tej procedurze jest nastgpujący: Algorytm 7.1. przypisz zmiennej a typu zbiorowego zbiór pusty podczas gdy wczytana liczba jest różna od zera to jeśli wczytana liczba mieści się w zakresie typu podstawowego to dodaj do zmiennej a zbiór złożony z wczytanej liczby czytaj liczbę A oto treść procedury: -55- Nauka programowania... procedure Czytaj Zbior Cvar a:zbiorliczb;ograniczeniel, ograniczenie2:integer); ( Procedura wczytywania wartości zmiennej typu zbiorowego ) var k: integer; begin wri tel n C ' Podaj wartość zmi ennej zbi orowej C 0 kończy ) ' ) ; read Ck); a := C]; whilekC>Odo begin if kin C ograniczeniel..ograniczenie2] then a := a + Ck] ; read Ck) end end; Wydruk wartości zmiennej typu zbiorliczb umożliwia procedura DrukujZbior. Zanim podamy jej treść przedstawimy algorytm wykorzystany w tej procedurze. Algorytm 7.2. dla i przebiegajqcej przez wszystkie warfości typu podstawowego wykonuj jeśli i należy do warfości zmiennej a to drukuj i procedure Qrukuj Zbior Ca:zbiorliczb;ograniczeniel, ograniczenie2: integer); C Procedura drukowania wartości zmiennej typu zbiorowego) var i`integer; begin writeln('Wartość zmiennej zbiorowej'); for i := ograni czeni el to ograni czeni e2 do if i in a then writelnCi ) end; Zamieszczony poniżej program testuje wykonanie procedur CzytąjZbior i Drukuj Zbior. -56- 7. Zbiory Program 7.1 program Test; type zbiorliczb = set of 1. .100; var x,y: zbiorliczb; procedure Czytaj Zbior Cvar a:zbiorliczb;ograniczeniel, ograniczenie2:integer); (Procedura wczytywania wartości zmiennej typu zbiorowego} begin ( Treść procedury zami eszczono wcześni ej } end; procedure Drukuj Zbior Ca:zbiorliczb;ograniczeniel, ograniczenie2: integer); ( Procedura drukowani a wartości zmi ennej typu zbi orowego } begin ( Treść procedury zamieszczono wcześniej } end; begin Czytaj Zbior Cx,1,100); Czytaj Zbior Cy,1,100); Drukuj Zbior Cx,1,100); Drukuj Zbior Cy,1,100) end. Jeśli wczytamy następujące ciągi liczb: 3434490 55675555880 -" to wartością zmiennej x będzie [3,4,9], a wartością zmiennej y [55,67,88]. Warto podkreślić, że podane wyżej procedury mąją charakter ogólny, mogą być wykorzystywane dla wszystkich typów zbiorowych, w których typem podstawowym są liczby Dla innych typów podstawowych należy dokonać drobnej modyfikacji tych procedur. Sytuacja znacznie się komplikuje, jeśli typem podstawowym, z którego tworzy się elementy zbioru, jest typ wyliczeniowy. W poprzednim podrozdziale rozważaliśmy przykład, w którym były wyznaczane informacje doty -57- Nauka programowania... czące artykułów sprzedawanych w dwóch sklepach. Przypomnijmy, że typem podstawowym, z którego tworzyliśmy wartości zmiennych typu zbiorowego był następujący typ wyliczeniowy: artyk = C narty, ki j ki, buty narc,1 yzwy, sanki, raki ety, pi 1 ki, pl etwy, okul#plyw, rowery, motocykle ); a typem zbiorowym typ: zbiorartyk = set of artyk; W tym przypadku do wczytywania i wyprowadzania wartości zmiennych typu zbiorowego należy zaprojektować prncedury ukierunkowane na ten konkretny typ wyliczeniowy (dla innego typu wyliczeniowego procedury te będą miały inną postać). Algorytm wykorzystany w procedurze drukowania i treść t#j procedury są przedstawione poniżej: Algorytm 7.3. dlai przebiegaj5lcej wszystkie wartości typu wyliczeniowego wykonuj jeśli i zawiera się w a to wyprowadź odpowiedni tekst w zależności od i procedure Drukuj Wylicz Ca:zbiorartyk); ( Procedura drukowania wartości zmiennej typu zbiorowego, którego typ podstawowy jest typem wyl i czeni owym ) var i : artyk; begin for i := narty to motocykl e do if i in a then case i of narty: writelnf'narty'); kijki : writelnf 'kijki '); buty#narc: writeln C'buty#narc'); ly2wy: writeln C'lyzwy'); sanki : writelnC 'sanki ' ) ; rakiety:writeln C'rakiety'); pilki : writelnC'pilki '); pletwy: writeln C'pletwy'); okul#plyw: writeln C'okul#plyw'); rowery: writeln C'rowery'); motocykle: writeln C'motocykle') -58- 7. Zbiory end end; Algorytm wykorzystany w proeedurze czytania i treść procedury są podane poniżej. Algorytm 7.4. przypisz zmiennej a typu zbiorowego zbiór pusty podczas gdy wczytana liczba jest różna od zera to jeśli wczytana liczba mieści się w liczbie elementów typu wyliczeniowego to dodaj do zmiennej a element złożony z odpowiedniej wartości typu wyliczeniowego poprzez przyporzQdkowanie liczbie wartości czytaj liczbę procedure Czytaj Wylicz Cvara:zbiorartyk; liczbaelemen:integer); (Procedura wczytywania wartości zmiennej typu zbiorowego, którego typ podstawowy jest typem wyl i czeni owym } var k:integer; begin writeln C'Podaj liczby odpowiadaj#ce wartościom', ' typu wyliczeniowego'); read Ck); a:=[]; whilekC>Odo begin if C 1 C= k ) and C k C= liczbaelemen ) then case k of 1: a : = a + j na-r t y ] ; . , 2: a :=a+ [kijki]; 3: a := a + [buty#narc] ; 4: a := a + [lyzwy] ; 5: a := a + [sanki ] ; 6: a := a + [rakiety]; 7: a := a + [pilki]; 8: a := a + [pletwy] ; 9: a := a + [okul#plyw]; 10 : a := a + [rowery] ; -59- end end; Algorytm wykorzystany w procedurze czytania i treść procedury są podane poniżej. Algorytm 7.4. przypisz zmiennej a typu zbiorowego zbiór pusty podczas gdy wczytana liczba jest różna od zera to jeśli wczytana liczba mieści się w liczbie elementów typu wyliczeniowego to dodaj do zmiennej a element złożony z odpowiedniej warfości typu wyliczeniowego poprzez przyporz#dkowanie liczbie warfości czytaj liczbę procedure Czytaj Wylicz Cvara:zbiorartyk;liczbaelemen: integer); (Procedura wczytywania wartości zmiennej typu zbiorowego, ktbrego typ podstawowy jest typemwyliczeniowym ) var k:integer; begin writeln('Podaj liczby odpowiadaj#ce wartościom'; ' typu wyl i czeni owego ' ) ; read Ck); a := C]; whi 1 e k C# 0 do begin if C 1 C= k ) and C k C= liczbaelerńen ) then case k of 1: a :=-#-# [narty_] ;~ , 2: a := a + Ckijki]; 3: a := a + [buty narc]; 4: a := a + [lyzwy] ; 5 : a := a + [sanki ] ; 6: a := a + Crakiety]; 7: a :=a+Cpilki]; 8: a := a + Cpletwy] ; 9: a := a + Cokul#plyw] ; 10 : a := a + [rowery] ; -59- Nauka programowania... 11: a := a + Cmotocykl e] end; read Ck) end end; Programilustrujący wykorzystanie procedury CzytajWylicz i DrukujWylicz jest przedstawiony poniżej. Program 7.2 program Testowy; f Programilustrujdcy wykorzystanie procedur Czytaj Wylicz i DrukujWylicz } type artyk = (narty,kijki,buty#narc,lyzwy,sanki,rakiety, pilki,pletwy,okul#plyw,rowery,motocykle); zbiorartyk = set of artyk; var x ( zmienna do wprowadzania i wyprowadzania wartości } : zbiorartyk; procedure Czytaj Wylicz Cvar a:zbiorartyk; liczbaelemen: integer); ( Procedura wczytywańia wartości zmiennej typu zbiorowego, którego typ podstawowy jest typem wyl i czeni owym } begin C Treść procedury zamieszczono wcześniej } end ; . procedure Drukuj Wylicz Ca:zbiorartyk); [ Procedura drukowania wartości zmiennej typu zbiorowego, ktbrego typ#podstawowy jest typem wyliczeniowym } begin C Treść procedury zami eszczono wcześni ej } end; begin Czytaj Wylicz(x,ll); Drukuj Wyliez Cx) end. Jeżeli wprowadzimy nastgpujące dane: -60- 7. Zbiory 1 5 1 4 6 4 1 0 to uzyskamy wydruk postaci: narty lyzwy sanki rakiety Posiadając umiejgtność wczytywania i wyprowadzania wartości, możemy przystąpić do wykorzystania informacji zawartych w zmiennych typu zbiorowego. Obecnie zaprojektujemy program, który umożliwia po wprowadzeniu wykazu artykułów sportowych uzyskanie nastgpujących informacji: 1) wykaz artykułów (spośród wprowadzonych), których nie można zakupić w żadnym sklepie 2) wykaz artykułów, ktńre musimy zakupić w sklepie A 8) wykaz artykułów, które musimy zakupić w sklepie B Zmienną, w której bgdziemy przechowywali wprowadzony wykaz artykułów, nazwiemy wykaz. Podobnie jak w poprzednim podrozdziale do wyznaczenia żądanych danych wykorzystamy wyrażenia logiczne. Informacjg pierwszą możemy wyznaczyć poprzez wyrażenie postaci ( wszystkie - sklep#A - sklep B ) * wykaz Informacjg drugą wyznaczamy obliczając nastgpujące wyrażenie: ( sklep#A - sklep#B ) * wykaz A informacjg trzecią wyznaczamy przy pomocy wyrażenia: ( sklep#B - sklep#A ) * wykaz gdzie wartością zmiennej wszystkie jest zbiór"pełny, wartością zmiennej eklep A zbiór artykułów sprzedawanych w sklepie A oraz wartością zmiennej sklep#B zbiór artykułów sprzedawanych w sklepie B. Wartości wymienionym zmiennym należy nadąć na począt,ku programu. Unikniemy w ten sposób wypisywania w pr#gramie odpo#viednich śkładowych poprzez zastąpienie ich nazwą zmiennej i tak np. zamiast zapisu [narty.motocykle) użyjemy zmiennej wszystkie. Przypisanie tych wartości może sig odbywać przy pomocy poniższej procedury o nazwie Stale: procedure Stale Cvar wszystkie,sklep A,sklep B: zbiorartyk); { nadanie zmiennym stalych wartości } begi n wszystkie := [narty..motocykle]; sklep# A := Cnarty..sanki]; sklep#B := [rakiety. .okul#plyw] - 61- Nauka programowania... var end; Program realizujący wyprowadzenie żądanej informacji jest podany poniżej: Program 7.3 program Sportowy; type artyk= Cnarty,kijki,buty narc,lyzwy,sanki,rakiety, pilki,pletwy,okul#plyw,rowery,motocykle); zbiorartyk = set of artyk; sklep#A,( wykaz artykułów dostgpnych w sklepie A ) sklep#B,C wykaz artyku#ów dostgpnych w sklepie B ) wszystkie, f wykaz wszystkich artykulów ) wykaz, ( wprowadzony wykaz artykulbw ) wyni k ( wartość wyni kowa ) : zbiorartyk; procedure Stale Cvarwszystkie,sklep A,sklep B: zbiorartyk); ( nadanie zmiennym stalych wartości ) begin C Treść procedury zami eszczono wcześni ej l end; procedure Czytaj Wylicz Cvar a:zbiorartyk;liczbaelemen: integer); f Procedura wczytywania wartości zmiennej typu zbiorowego, którego typ podstawowy jest typem wyl i czeni owym ) begin ' C Treść procedury zami eszczono wcześni ej ) end; procedure Drukuj Wylicz Ca:zbiorartyk); ( Procedura drukowania wartości zmiennej typu zbiorowego, którego typ podstawowy jest typem wyl i czeni owym ) begin ( Treść procedury zami eszczono wcześni ej ) end; begin Stale Cwszystkie,sklep A,sklep# B); Czytaj Wylicz Cwykaz,ll); -62- 7. Zbiory writeln C'Artykuly z wczytanego wykazu'); Drukuj Wylicz Cwykaz); writelnC 'Artykuły z wykazu, których nie ma w żadnym sklepie' ) ; wynik := ( wszystkie - sklep A - sklep B ) *wykaz; Drukuj Wylicz Cwynik); wri tel nf 'Artykuły z wykazu, które można kupi ć tyl ko w skl epi e A ' ) ; wyni k := C skl ep A - skl ep B ) * wykaz ; Drukuj Wylicz(wynik); wri tel n C 'Artykuly z wykazu, które można kupi ć tyl ko w skl epi e B ' ) ; wyni k := f s kl ep#B - skl ep A ) * wykaz ; Drukuj Wylicz Cwynik) end. Przedstawione wyżej procedury wprowadzania i wyprowadzania wartości zmiennych typu zbiorowego wykorzystywały następujące dwa ogólne algorytmy : #gOrytm 7,$, dla wszystkich wartości typu podstawowego wykonuj jeśli wartość ta zawiera się w pewnym zbiorze to przetwarzaj tę wartość Algorytm 7.6. przypisz zmiennej x warfość zbioru pustego podczas gdy istniejq wartości do przetworzenia wykonuj czytaj warfość a jeśli a zawiera się w zbiorze pełnym to x:=x+ (a) ů # Algorytm 7.5 był wykorzystywany przy wyprowadzaniu wartości zmiennej typu zbiorowego, a algorytm 7.6 przy wprowadzaniu tej wartości. Równie często jest stosowany następujący algorytm: Algorytm 7.7. przypisz zmiennej x warfość zbioru pełnego podczas gdy istniejq wartości do przetworzenia wykonuj -63- Nauka programowania... czytaj warfość a jeśli zawiera się w zbiorze pelnym to x := x - (a) Algorytm 7.7 jest stosowany do eliminacji pewnych wartości ze zbioru pełnego. Wykorzystanie wszystkich trzech podanych algorytmów ilustruje kolejny przykład. Przykład W przykładzie rozważymy następujący problem. W tekście umieszczonym w pliku tekstowym należy znaleźć znaki nieobecne w tym tekście i jednocześnie występujące w pierwszym zbiorze znaków oraz znaki obecne w tym tekście i jednocześnie występujące w drugim zbiorze znaków. Pierwszy zbiór znaków bgdziemy przechowywać w zmiennej typu zbiorowego o nazwie nieobecne, a drugi zbiór znaków w zmiennej o nazwie obecne. Do wczytania i drukowania wartości tych zmiennych wykorzystamy dwie procedury o nazwach CzytajZbior oraz DrukujZbior. Procedury te są zaprojektowane analogicznie jak procedury o tych samych nazwach podane w poprzednim podrozdziale. Różnią się tylko typem parametrów i zmiennych wewnętrznych. Zbiór znaków obecnych w tekście i jednocześnie występujących w zmiennej obecne będziemy przechowywać w zmiennej t obecne, natomiast zbiór znaków nieobecnych w tekście i jednocześnie występujących w zmiennej nieobecne bgdziemy przechowywać w zmiennej t nieobecne. Wartość początkowa zmiennej t obecne powinna być równa [], a wartość początkowa zmiennej t nieobecne powinna być równa wartości zmiennej nieobecne. Dla wartości zmiennej obecne: [X,Y,P] i wa#tości zmiennej nieobecne: [a,b,c,d,e] oraz tekstu "Program = algorytm + struktura danych" wartość zmiennej t obecne powinna wynosić: [P] a wartość zmiennej t nieobecne powinna być równa: [b,e] Możemy teraz przystąpić do zaprojektowania procedury wyznaczającej -64- 7. Zbiory wartości zmiennych t obecne oraz t nieobecne. Algorytm przetwarzania tQkstu wykorzystuje algorytmy 7.6 oraz 7.7 i jest następujący: AlgOrytm 7.8 otwórz żĄdany plik podczas gdy w pliku występujĄ jeszcze symbole wykonuj czytaj znak z pliku jeśli znak zawiera się w warfości zmiennej obecne to dodaj do wartości zmiennej t obecne zbiór złożony ze znaku jeśli znak zawiera się w wartości zmiennej nieobecne to odejmij od warfości zmiennej t nieobecne zbiór złożony ze znaku 'I#kst procedury jest podany poniżej: procedure Przetwarzaj Cobecne,nieobecne:znaki; vart obecne:znaki; var t nieobecne:znaki; var plik:text); ( Procedura przetwarzania znakbw z tekstu ) var znak: char; begin assign Cplik,'ala'); reset Cplik); whi1 e not eof C pl i k ) do begin read Cplik,znak); if znak in obecne then t obecne := t obecne + Cznak] ; i f zna k i n ni eobecne then t nieobecne :=t nieobeene - Cznak] end ů end; Możemy już t#raz podać tekst programu sprawdzającego przynależność znaków. Zrobimy to przy założeniu, że wzorcowe zbiory znaków (zmienne obecne oraz nieobecne) mogą składać się z dużych i małych liter. Ograniczenia typu podstawowego przy wywołaniu procedur CzytajZbior i DrukujZbior są zatem następujące: 'A' ograniczenie dolne i 'z' ograniczenie górne. Przy innym typie podstawowym należałoby zmienić te ograniczenia. Program 7.4 program Tekst; -65- Nauha programowania... ( Program sprawdzania przynależności znaków z tekstu ) type znaki = set of char; var obecne, ni eobecne, C wzorcowe zbi ory znaków ) t#obecne, t nieobecne: C wyznaczane zbiory znaków ) znaki ; pl i k : text ; ( pl i k zawi erajacy sprawdzany tekst ) procedure Czytaj Zbior Cvar a:znaki; ograniczeniel,ograniczenie2,koniec: char); ( Procedura wczytywani a zbi oru znaków ) var k: char; begin writeln('Podaj wartość zmiennej zbiorowej: '); read(k); a := C]; while k C# koniec do begin if (ograniczeniel C= k) and ( k C= ograni czeni e2 ) then a := a + Ck] ; read Ck) end end; procedure Drukuj Zbior(a:znaki; ograniczeniel,ograniczenie2: char); ( Procedura drukowania zbioru znaków ) var i : char; begin writeln('Wartość zmiennej zbiorowej'); for i := ograniczeniel to ograniczenie2 do if i in a then writeln(i ) end; procedure Przetwarzaj(obecne,nieobecne: znaki; var t#obecne, t ni eobecne : znaki ; var pl i k : text ) ; ( Procedura przetwarzania znaków z tekstu ) -66- 7. Zbiory begin end; begin writelnC 'Podaj pierwszy wykaz znakbw ' ); Czytaj Zbiorfobecne,'A','z','?'); writelnC 'Wykaz znaków, których szukamy znaków' 'obecnych w tekście: '); Drukuj Zbior Cobecne,'A','z'); writeln C'Podaj drugi wykaz znaków '); Czytaj Zbior Cnieobecne,'A','z','?'); writeln C'Wykaz znaków, których szukamy znaków', ' ni eobecnych w tekści e : ' ) ; Drukuj Zbior Cnieobecne,'A','z'); t#obecne : = ( ] ; t#nieobecne := nieobecne; Przetwarzaj Cobecne,nieobecne,t obecne,t nieobecne, plik); writeln C'Znaki obecne we wczytanym tekście'); Drukuj Zbior Ct#obecne,'A','z'); writeln C'Znaki nieobecne we wczytanym tekście'); Drukuj Zbior Ct#nieobecne,'A','z') end. Na zakończenie zauważmy, że procedury wczytywania i drukowania wzorcowych zbiorów znaków zostały tak zaprojektowane, aby wczytywany był każdy znak należący do, zbioru. Oczyv#ście możliwe jest takie zaprojektowanie tych procedur, aby wczytywane było tylko ograniczenie dolne i górne znaków należących do zbioru. Wykonanie tego zadania pozostawiamy jako ćwiczenie Czytelnikowi. 7.4. Zadania l.Zaprojektować tak procedury wczytywania i drukowania wzorcowych zbiorów znaków, aby wczytywane było tylko ograniczenie dolne i górne -67- Nauka programowania... znaków należących do zbioru. 2.Wczytać wartości zmiennych x,y typu zbiorowego o typie składowym bgdącym typem wyliczeniowym (poniedzialek, wtorek, sroda, czwartek, piatek, sobota, niedziela) i wydrukować wartości wyrażeń x + y, x - y, x *yorazy-x. 8.Podać liczbę elementów zbioru reprezentowanego przez zmienną x z poprzedniego zadania. 4.Napisać procedurę kontrolującą poprawność wprowadzania danych. Zakładamy, że mogą być wprowadzane wyłącznie litery A, B, C oraz cyfry. 5.Napisać funkcję podającą wartość true, gdy dany tekst zawiera tylko litery i spacje. 6.Napisać procedurę usuwania w podanym tekście wszystkich znaków różnych od liter i spacji. -68- Rozdział REKORDY W niniejszym rozdziale omówimy strukturę danych, która umożliwia przechowywanie elementńw różnego typu. Strukturę taką nazywamy rekordem. Elementami rekordu są pola, a każde z nich posiada swoją nazwę. 8.1. Wprowadzenie Deklaracja typu rekordowego ma postać: nazwa = record " nazwa 1: typ 1; nazwa 2: typ 2; end; gdzie nazwa jest nazwą typu rekordowego, a nazwa i oraz typ i są odpowiednio nazwą oraz typem i-tego pola. Poniżej została podana przykładowa deklaracja typu rekordowego. Przykład type data = record mi esi ac, dzien, -69- Nauka prog#ramowania... rok: integer end; Po zdefiniowaniu typu rekordowego należy określić zmienną rekordową przy pomocy deklaracji var. Przykład var dl,d2: data; Wykorzystując deklarację typu rekordowego z poprzedniego przykładu zostały zdefiniowane dwie zmienne dl oraz d2 typu rekordowego data. Zmienne rekordowe (rekordy) dl, d2 zawierąją te same pola: miesiac, dzien, rok typu integer. Warto zwrócić uwagę na fakt, że poszczególne pola danego rekordu same mogą być również rekordami. Ilustruje to poniższy przykład. Przykład type ident = record imiepier, imiedrug, nazwisko: string[20] end; data = r#cord dzien, miesiac, ,.rok: integer; miejsce: string[20] end; adresprac = record kod:integer; miejscowosc, ulica: string[30]; numer, mieszkanie, - 70 - 8. R,ekordy tel efon : i nteger end; jezyki = record angi el ski, rosyjski, n i emi ec ki, francuski : stri ng[3] end; poziomprac = record wyksztalcenie, stanowisko: string[30]; obce:jezyki end; pracowni k = record nazw:ident; urodz: data; adres: adresprac; poziom: poziomprac end; var prac : pracowni k; Rekord prac zawiera nastgpujące pola: nazw typu rekordowego ident, urodz typu rekordowego data, adres typu rekdrdowego adresprac oraz poziom typu rekordowego poziomprac. Pole poziom zawiera również pole obce typu rekordowego jgzyki. Strukturg tego rekordu nąjłatwiej można przedstawić na rysunku (rys.8.l). Warto zaznaczyć, że żadeklarnwa#ie na przykład pola nazw jako typu rekordowego umożliwia identyfkację pierwszego i drugiego imienia oraz nazwiska. Natomiast deklaracja zmiennej nazw jako typu string[40) powoduje, że nazwisko i imiona są traktowane łącznie. -71- Nauka programowania... miejscov#osc ulica numer mieszkanie Każde pole rekordu może zostać wybrane do dalszego przetwarzania przy pomocy wskazania przez tak zwany deskryptor pola. Deskryptor pola ma postać: nazwa rekordu.nazwa pola Przykład Dlarekordu zdefiniowanego w poprzednim przykładzie deskryptor prac.urodz.rok wskazuje pole rok rekordu urodz, który jest polem rekordu prac. Po wskazaniu poszczególne pola rekordu mogą być wykorzystywane w instrukcjach. Ilustruje to poniższy przykład. Przykład wr.i te# n C ' Rok urodzeni a : ', prac. urodz. rok : 6 ) ; Zostanie wyprowadzóna wartość pola rok w rekordzie urodz, który jest polem rekordu prac. Wprowadzanie danych do pól rekordu ilustruje kolejny przykład. Przykład Zakładamy definicjg rekordu prac taką jak w poprzednich przykładach. Poniższy fragment programu powoduje wprowadzenie wartości do pól rekor -#2- R,ys. 8.1. Struktura rekordu prac 8. R#ekordy urodz bgdącego polem rekordu prac. Przy wprowadzaniu danych jest onywane jednocześnie sprawdzenie ich poprawności. Do tego celu służy kcja Poprawne(), która sprawdza poprawność wprowadzenia danych do dzien (zakres [1..31)), miesiac ( zakres [1..12)) oraz rok (zakres [0..93)). ction Poprawne Crek:data): boolean; in poprawne := Crek.dzien in [1..31]) and Crek.miesiac in [1..12]) and Crek.rok in [0. .93]) end; repeat writeln C'Podaj datę i miejsce urodzenia Cdzień,', ' miesiąc, rok)'); readln Cprac.urodz.dzien,prac.urodz.miesiac, prac.urodz.rok,prac.urodz.miejsce); until Poprawne Cprac.urodz); Czgsto zachodzi konieczność sprawdzenia, czy zawartości tych samych pól w dwóch rekordach są identyczne. W jgzyku #arbo Pascal nie można dokonać tego porównania przy pomocy operatora porównania =. Musimy do tego celu wykorzystać specjalnie zaprojektowaną funkcję; która porównuje kolejno wszystkie pola rekordów. Ilustruje to poniższy przykład. Przykład W przykładzie jest podana funkcja sprawdza,j#ca identyczność dwóch rekordów przechowujących datę w postaci miesiąca, dnia i roku. Program 8.1 program Porownaj; ( Program ilustruj#cy wykorzystanie funkcji Rowne C) testującej identyczność dwóch rekordów ) type data = record miesiac, dzien, rok:integer; miejsce: string[20] end ; Nauka programowania... var datal,data2: data; function Rowne Cdl,d2:data):boolean; f Funkcja sprawdzania identyczności zawartości dwóch rekordów o taki ch samych pol ach ) begin rowne := Cdl.miesiac=d2.miesiac) and Cdl.dzien= d2.dzien)and Cdl.rok=d2.rok) end; begin C wpisanie zawartości dwbch rekordów datal oraz data2 ) datal.miesiac :=10; datal.dzien := 26; datal.rok := 1992; data2.miesiac :=10; data2.dzien := 26; data2.rok := 1992; if Rowne Cdatal,data2) then writelnC'Daty są takie same') el se end. writelnC'Daty sa różne') Zawartości poszczególnych rekordów mogą być kopiowane jeden do drugiego pod warunkiem, że zawierąją te same pola identycznego typu. Dla rekordów z poprzedniego przykładu można wykonać następującą instrukcjg . #datal := data2 Instrukcja ta spowoduje przepisanie zawartości rekordu data2 do rekordu datal. 8.2. Instrukcja with W celu wybrania odpowiedniego pola rekordu należy wskazać to pole przy pomocy deskryptora. W przypadku jeśli tych pól jest dużo, może to być - 74 - 8. R,ekordy bardzo uciążliwe. Wykonanie tego zadania ułatwia istniejąca w jgzyku Pascal instrukcja wiążąca with umożliwiająca wskazanie całej grupy pól danego rekordu. Instrukcja with ma postać: with nazwa rekordu do instrukcja Instrukcjajest nąjczęściej instrukcją złożoną. Jeżeli w instrukcji tej wystgpują nazwy pól, odnoszą sig one do rekordu wyszczególnionego w instrukcji #th. Przykład Niech rekord nazw bgdzie zdefniowany nastgpująco: type ident = record imiepier, imiedrug. nazwisko: string[20] end; var nazw:ident: Zamiast napisać writeln Cnazw.imiepier); writeln Cnazw.imiedrug); write Cnazw.nazwisko): możemy napisać: with nazw do b291n writelnCimiepier); writeln Cimiedrug): wri te Cnazwi sko) end; Identyfkatory imiepier, imiedrug oraz nazwisko traktowane bgdą jako pola rekordu nazw. Instrukcja with może być zagnieżdżona tzn. wewnątrz jednej instrukcji with może wystgpować druga instrukcja with. Wykorzystanie zagnieżdżonej instrukcji with ilustruje kolejny przykład. -75- Nauka programowania... Przykład Rozważmy rekord prac zdefniowany na początku tego rozdziału. Jeżeli chcemy wyprowadzić wartości pól: dzien, miesiac, rok umieszczonych w rekordzie urodz, który jest polem rekordu prac, to można napisać: with prac do with urodz do begin writeln Cdzien); writeln Cmiesiac); writeln Crok) end; lub też nieco krócej: with prac, urodz do begin writeln Cdzien); writeln Cmiesiac); writeln Crok) end; Obie powyższe konstrukcje są równoważne i nazwy pól umieszczone wewnątrz instrukcji begin... end odnoszą sig do pól rekordu nazw, który jest polem rekordu prac. Gdy chcemy uzyskać dostęp do wszystkich pól danego rekordu łącznie ze wszystkimi polami umieszczonymi w rekordach, które są polami danego rekordu, n#leży w instrukcji with wymienić wszystkie nazwy rekordów, ale w odpowiedniej kolejności. Kolejność powinna wynikać ze struktury rekordu, rekordy umieszczone wyżej w strukturze powinny być wymienione wcześniej. Przykład with prac,nazw,urodz,adres,poziom,obce do begin end; Powyższa instrukcja umożliwia dostgp do wszystkich pól rekordu prac. -76- 8. Rekordy #. Na zakończenie zwróćmy uwagg, że w przypadku gdy nazwa pola jest #aka sama jak nazwa zmiennej występującej w programie, to identyflkator występujący wewnątrz instrukcji with odnosi sig zawsze do pola rekordu. 8.3. Tablice rekordów Użyteczność rekordów bardzo wzrasta, gdy są wykorzystywane jako elementy tablic. Można bowiem wtedy tworzyć bazy danyeh złożone z tablic, których poszczególne elementy są rekordami pozwalającymi przechowywać bardziej złożoną informację. Zawartość tablicy można zapamiętać na dysku w odpowiednim pliku, co umożliwia późniejsze odczytanie podanej informacji. Wykorzystanie tablicy rekordów ilustruje poniższy przykład. Przykład W przykładzie skonstruujemy prostą bazę danych pozwalającą na przechowywanie informacji o pracownikach zakładu. Na wstgpie należy zaprojektować strukturg rekordu, w którym bgdzie umieszczona informacja o jednym pracowniku. Pojedynczy rekord umieścimy w tablicy, co pozwoli na zapamigtanie informacji o wigkszej liczbie pracowników. Struktura rekordu bgdzie analogiczna do wykorzystywanych w przykładach zamieszczonych w tym rozdziale. Umożliwia ona zapamigtanie podstawowej informacji o pracowniku. Zwróćmy uwagg, że plik baza jest złożony z rekordów typu pracownik. Należy obecnie zaprojektować program, który pozwoli wykorzystać informacjg zapamiętaną w bazie danych. Program taki powinien na wstgpie odczytać bazg z pliku do tablicy, po zakończeniu przetwarzania powinien zapisywać zawartość tablicy do pliku, musi również umożliwiać wczytywanie informacji dla nowego pracownika oraz wyświetlanie informacji o wszystkich pracownikach. ~ Są to podstawowe operacje, które powinien wykonywać program zarządzający bazą danych. Opróez tego można zaprojektować inne funkcje w zależności od konkretnych potrzeb. W naszym przykładzie zaprojektujemy jeszcze trzy dodatkowe operacje, a mianowicie znajdowanie wszystkich pracowników urodzonych po roku 1958, zamieszkałych na danej ulicy oraz posiadających wykształcenie wyższe. Należy podkreślić, że są to tylko wybrane przykładowe zapytania, rzeczywisty system kadrowy przechowujący informacjg o pracownikach jest o wiele bardziej skomplikowany. -77- Nauka programowania... Podsumujmy teraz operacje wykonywane przez program (każdą operacjg bgdzie realizować oddzielna procedura): l. Odczytanie danych z pliku do tablicy - procedura Odczytaj 2. Zapis danych z tablicy do pliku - procedura Zapisz 3. Wczytanie informacji dla nowego pracownika - procedura Czytąj 4. Wyświetlenie informacji o wszystkich pracownikach - procedura Wszyscy 5. Znalezienie pracowników urodzonych po roku 1958 - procedura Wiek 6. Znalezienie pracowników zamieszkałych na danej ulicy - procedura Zamieszk 7. Znalezienie pracowników posiadąjących wykształcenie wyższe - procedura Wyzsze Sternwanie wykonaniem odpowiedniej operacji odbywać sig bgdzie przy pomocy tak zwanego menu. Do otwarcia menu służyć bgdzie funkcja Menu(), której wartość zostanie określona poprzez dokonany wybór. Definicja struktury danych wykorzystywana w programie, nagłówki procedur oraz program główny są przedstawione poniżej. W programie głównym po odczytaniu zawartości pliku do tablicy w zależności od wartości podawanej przez fimkcjg Menu() jest wykonywana odpowiednia operacja. Program 8.2 program Baza#prac; uses Crt; f dołdczenie modułu Crt ) type ident = record imiepier, i mi ed rug, nazwisko: string[20] end; data = record dzien, miesiae, rok: integer; miejsce: string[20] end; adresprac = record - 78 - 8. ftekordy kod:integer; miejscowosc, ulica: string[30]; numer, mieszkanie, tel efon : i nteger end; jezyki = record angi el ski, rosyjski, n i emi ec ki, francuski : stri ng[3] end; pozi omprac = record wyksztalcenie, stanowisko: string[30]; obce: jezyki end; pracowni k = record nazw:ident; urodz: data; adres: adresprac; poziom: poziomprac end; const n max =100; var _ dane: array Cl..n max] of pracownik; baza : fi le of praeowni k; koni ec : bool ean ; n:integer; procedure Czytaj C var prac : pracowni k ) ; f Procedura wprowadzania informacji o jednym pracowniku ) begin ( Treść procedury zami eszczono poni żej ) -#9- Nauka programowania... end; procedure Wyswietl Cprac:pracownik); ( Procedura wyświetlania informacji o jednym pracowniku ; begin f Treść procedury zamieszczono poniżej } end; procedure Zapisz Cn: integer); ( Procedura zapisywania zawartości tablicy na dysk } begin ( Treść procedury zami eszczono poni żej } end; procedure Odczytaj Cvar n: integer); ( Procedura odczytywani a zawartości pl i ku do tabl i cy } begin [ Treść procedury zami eszczono poni żej } end; function Menu:integer; ( Funkcja tworzenia menu systemu } begin C Treść funkcj i zami eszc2ono poni żej ; end; procedure Wszyscy; f Procedur#wyświetlania informacji o wszystkich pracownikach } begin ( Treść procedury zamieszczono poniżej } end ; # procedure Zamieszk; { Procedura znajdowania pracowników zamieszkałych na podanej ul i cy } begin C Treść procedury zami eszczono poni żej ; end; ' O' 8. R,ekordy procedure Wiek; f Procedura znajdowania pracowników urodzonych po roku 1958 ) begin f Treść procedury zami eszczono poni żej ) end; procedure Wyzsze; f Procedura znajdowania pracownikbw z wyższymwykształceniem ) begin { Treść procedury zami eszczono poni żej ) end; begin C pocz#tek programu ) Odczytaj Cn ) ; ( odczytani e zawartości pl i ku ) koniec := false; repeat case Menu of 1: Wszyscy ; f wyświ etl eni e i nformacj i o wszy5tki ch pracowni kach ) 2 : i f n C n max then begin n:=n+1; { wczytanie danych dla jednego pracownika ) Czytaj Cdane Cn]) end; 3 : Wi ek ; f wi ek pracowni ka ) 4: Zamieszk; ( zamieszkanie pracownika ) 5: Wyzsze;f wykształcenie wyższe l 0 : begin ( zapi sani e zawartości tabl i cy do pl i ku ) Zapi szCn) ;- .~ , koni ec := true end end unti 1 koni ec ; f pętl a ni es kończona ) end. Możemy teraz przystąpić do uszczegóławiania programu poprzez odpowiednie zaprojektowanie procedur. Najpierw zaprojektujemy algorytm wykorzystywany w funkcji Menu(). Nauka programowania... Algorytm 8.1. wyświetl menu systemu powtarzaj zidentyfikuj ostatnio naciśnięty klawisz aż ostatnio naciśniętym klawiszem był klawisz 0,1,2,3,4,5 lub Esc wyznacz warfość przypisanQ funkcji Menu() #eść funkcji Menu() jest przedstawiona poniżej. function Menu:integer; ( Funkcja tworzenia menu systemu ) var znak: char; begin C1 rScr ; wri tel n C ' Li czba rekordów w bazi e ', n ) ; wri tel n ; writeln C' GŁÓWNE MENU PROGRAMU '); writeln; writelnC ' 1 - Wyświetlanie danych dla wszystkich pracowników' ); wri tel n C ' 2 - Dodawani e i nformacj i o nowym pracowni ku ' ) ; writelnC' 3 - Znajdowaniewszystkichpracowników'. ' urodzonych po roku 1958 ' ) ; writelnC' 4 - Znajdowaniewszystkich pracowników', ' zami eszkalych na danej ul i cy ' ) ; writelnC ' 5 - Znajdowanie wszystkich pracowników z ', #'wykształceniem wyższym'); wri tel n C ' 0 - Wyj ści e z systemu ' ) ; wr#tel n ; wri te C ' Wprowadź 1 i czbg z 0 - 5 ' ) ; repeat zna k := Read Key ; until znakin ['0'..'5',chr C27)]; if ordCznak) = 27 then menu := 0 el se -82- 8. ftekordy menu := ordCznak) - ordC '0' ) end; Zwróćmy jeszcze uwagg na sposób sprawdzenia, czy wczytano odpowiedni znak. W tym celu wykorzystuje sig operator in, ktflry bada przynależność naciśniętego znaku do zbioru znaków od zera do pigciu i znaku Esc. Jeżeli naciśnięto klawisz Esc, to funkcja Menu() podaje wartość 0, natomiast gdy naciśnigto klawisz odpowiadąjący liczbie, to wyznaczenie wartości podawanej przez funkcjg Menu() odbywa sig poprzez wykorzystanie funkcji ond(), ktńra podąje numer porządkowy argumentu. (W jgzyku Pascal wszystkie znaki mają przydzielony numer porządkowy, na przykład ord( '0 ') wynosi 48, a ord( '5 ') wynosi 53). Algorytm wykorzystany w procedurze Zapisz jest nastgpujący: Algorytm 8.2. otwórz plik powtarzaj zapisz kolejny rekord do pliku aż zapisano wszystkie rekordy zamknij plik l5reść procedury jest podana poniżej. procedure Zapisz Cn:integer); C Procedura zapisywania zawartości tablicy na dysk ) var i:integer; begin assign Cbaza,'bazadysk'); ( przypisanig nazwy ) rewrite Cbaza); ( otworzenie pliku ) i :=1; repeat -" write Cbaza,dane Ci)); i:=i+1 unti 1 i # n ; cl ose C baza ) ( zamkni ęci e pl i ku ) end; Algorytm zastosowany w procedurze Odczytąj jest następujący: Nauka programowania.. Algorytm 8.3. otwórz plik podczas gdy nie napotkano symbolu końca pliku odczytaj kolejny rekord z pliku zapamiętaj liczbę odczytanych rekordów A oto treść procedury Odczytaj: procedure Odczytajfvarn:integer); C Procedura odczytywani a zawartości pl i ku do tabl i cy ) var i:integer; begin assign Cbaza,'bazadysk'); ( przypisanie nazwy ) reset C baza ) ; C otworzeni e pl i ku ) i :=0; whi 1 e not eof C baza ) do begin i:=i+1; read Cbaza,dane Ci]); end; close Cbaza); n := i f zapamiętanie liczby odczytanych rekordów ) end; Procedura Wszyscy jest dość prosta i nie wymaga podania pseudo-kodu. Jej treść j#.st następująca. procedure Wszyscy; Ć Procedura wyświetlania informacji o wszystkich pracownikach ) var - i : i nte9er ; begin for i :=1 to n do C dl a każdego pracowni ka ) begin writeln C'Rekord numer: ',i); # wyświ etl ani e danych dl a i -tego pracowni ka ) Wyswietl Cdane[i]) end end; -84- 8. ftekordy poniżej. podany w procedurze Zamieszk, a następnie jej treść są podane Algorytm 8.4. wczytaj nazwę szukanej ulicy da każdego pracownika wykonuj jeśli pracownik mieszka na szukanej ulicy to drukuj nazwisko pracownika procedure Zamieszk; ( Procedura znajdowania pracownikdw zamieszkałych na podanej ulicy ) var i:integer; nazwaulicy: string[30]; begin C1 rScr ; writeln C'Podaj nazwę ulicy'); readln Cnazwaulicy); writeln; wri tel n C ' Wykaz pracowni ków zami eszkałych na ul i cy nazwaul i cy ) ; fori:=ltondo ( powi#zanie identyfikatorbw p61 z rekordem daneCi ] oraz podrekordami adres oraz nazw ) with daneCi ],adres, nazw do begin i f ul i ca = nazwaul i cy then # writeln Cimiepier, nazwisko) end; readln end; Algorytm wykorzystany w procedurze Wiek jest podobny do zastosowanego w procedurze Zamieszk. A oto treść tej procedury. procedure Wiek; ( Procedura znajdowania pracowników urodzonych po roku 1958 2 var i:integer; begin ClrScr; -85- Nauka programowania... writelnC ' Wykaz pracowni ków urodzonych po 1958 roku ' ) : for i :=1 to n do f dl a każdego pracowni ka } f powi#zanie identyfikatordw pól z rekordem daneCi] oraz podrekordami urodz oraz nazw } with daneCi ], urodz, nazw do begin if rok > 1958 then writeln Cimiepier:8, nazwisko:8) end; readln end; Algorytm wykorzystany w procedurze Wyzsze jest również analogiczny do zastosowanego w procedurze Zamieszk. procedure Wyzsze; ( Procedura znajdowania pracownikbw z wyksztalceniemwyższym } var i:integer; begin C1 rScr ; wri tel n C ' Wykaz pracowni ków z wyksztalceni em wyższym: ' ) ; for i :=1 to n do C dl a każdego pracowni ka } f powiązanie identyfi katorów pól z rekordem daneCi ] oraz podrekordami poziom oraz nazw } withdane[i],poziom,nazw do begin " ifwyksztalcenie= 'wyzsze' then writeln Cimiepier, nazwisko) end; readln end; Na zakończenie podamy treść procedur Czytaj oraz Wyswietl. procedure Czytaj Cvar prac: pracownik); ( Procedura wprowadzania informacji o jednym pracowniku ; begin C1 rScr ; C powi #zani e i dentyfi katorów pól ze wszystki mi pol ami rekordu prac } with prac,nazw,urodz,adres,poziom,obce do -86- 8. ftekordy begin writeln C'Podaj pierwszeimig:'); readln Cimiepier); wri tel n C ' Podaj drugi e i mi ę : ' ) ; readln Cimiedrug); writeln('Podaj nazwisko:'); readln Cnazwisko); writeln C'Podaj dzień urodzenia:'); readln Cdzien); writeln C'Podaj miesi#c urodzenia:'); readlnfmiesiac); writeln C'Podaj rokurodzenia:'); readln Crok); writeln('Podaj miejsce urodzenia:'); readln Cmiejsce); writeln('Podaj kod:'); readln Ckod); writeln C'Podaj miejscowość:'); readlnfmiejscowosc); writelnf'Podaj ulicę:'); read Culica); writeln('Podaj numer:'); readln Cnumer); writeln C'Podaj numer mieszkania'); readln Cmieszkanie); writeln C'Podaj numer telefonu'); readln Ctelefon); writelnC 'Czy.z#ajęzyk an.gi-e#ski ')r; readln(angielski); writeln C'Czy znajęzyk ro5yjski'); readln Crosyjski); writelnC 'Czy zna język niemiecki ' ) ; readlnCniemiecki ); writelnC 'Czy zna jgzyk francuski ' ) ; readlnffrancuski); writeln('Podaj wyksztalcenie:'); Nauka programowania... readln Cwyksztalcenie); writeln C'Podaj stanowisko:'); readln Cstanowisko) end; end procedure Wyswietl Cprac:pracownik); ( Procedura wyświetlania informacji o jednym pracowniku ; begin ( powi#zanie identyfikatorów pól ze wszystkimi polami rekordu prac) with prac,nazw,urodz,adres,poziom,obce do begin Cl rScr ; writeln C'Pierwszeimię. ',imiepier): writeln C'Drugie imig . ',imiedrug); writeln C'Nazwisko . ',nazwisko); writeln; writeln C'Miejsce urodzenia: ',miejsce); writeln C'Data urodzenia. ,dzien,'/',miesiac,'/',rok); writeln; writeln C'Miejscowość zamieszkania: ', miejscowosc); writeln C'Kod . ',kod); #writelnC'Ulica . ',ulica); writeln C'Numer . ',numer); writeln C'Numer mieszkania : ',mieszkanie); writeln C'Numer telefonu. ',telefon); writeln; writelnC ' angielski. ',angielski ); writelnC ' rosyjski . ',rosyjski ) ; writelnC ' niemiecki . ',niemiecki ); writeln C' francuski. ',francuski); wri tel n ; writeln C'Wyksztalcenie: ',wyksztalcenie); writeln C'Stanowisko: ',stanowisko); 8. Rekordy writeln; writeln C'Naciśnij klawisz ENTER') end; readln end; W ostatnim przykładzie wystąpił dość istotny problem związany ze wczytywaniem danych, którego do tej pory nie analizowaliśmy. Otóż zwróćmy uwagę, że jeżeli pole jest typu tekstowego, to możemy do niego wprowadzać zarówno liczby jak i teksty (liczba bgdzie traktowana po prostu jako t#kst). Natomiast do pola typu numeryeznego możemy wprowadzać wyłącznie liczby, omyłkowe wprowadzenie tekstu spowoduje przerwanie pracy programu i wyświetlenie komunikatu o błędzie wykonania. Dla ścisłości trzeba dodać, że to przerwanie pracy programu zależy od ustawienia dyrektyw kompilatora. Dyrektywy kompilatora sterują jego pracą i można je umieszczać w programie w następujący sposób: {$ dyrektywa } Obecnie omówimy tylko dyrektywę I+ oraz I- (W rozdziale 12 jest jeszcze omówiona dyrektywa {$F+}, natomiast wykaz wszystkich dyrektyw kompilatora znajduje się w pracy [14)). Jeżeli w pewnym miejscu programu pojawi się tekst {$I+} to od tego miejsca, aż do napotkania tekstu {$I-} każdy błąd związany z wczytywaniem danych spowoduje przerwanie pracy programu. Natomiast wprowadzenie dyrektywy {$I-} powoduje, że praca programu nie jest przerywana, natomiast w zmiennej systemowej o nazwie InOutRes zostaje zapamiętany numer błędu. Jeżeli wartość tej zmiennej jest różna od zera, oznacza to, że wystąpił błąd związany z #vczytywaniem danych. Warto jeszcze znać funkcję IOResult(), która podaje wartość zmiennej InOutRes i jednocześnie ją zeruje. Zabezpieczenie się przed-omyłkowyt#z wpisaniem tekstu do pola typu numerycznego może wyglądae następująco: repeat writeln C'Podaj dzień urodzenia:'); readln Cdzien); unti 1 IOResul t = 0 ; W celu wykorzystania tej konstrukcji dla dowolnej zmiennej typu integer zapiszemy ją w postaci procedury. procedure Czytaj#liczbe Ctekst: string; varliezba:integer); begin -89- Nauka programowAria... repeat writeln Ctekst); readln Cliczba); unti 1 IoResul t = 0 end; Przypomnijmy jeszcze, że najpierw musi być podana w programie dyrektywa I- w postaci tekstu ($I-}. Instrukcja repeat bgdzie wykonywana tak długo, aż funkcja IOFtesult() poda wartość zero, co oznacza, że operacja wczytywania danych zakończyła sig poprawnie. Procedura Czyt#j z poprzedniego przykładu zabezpieczona przed błgdnym wpisywaniem danych jest podana poniżej (w programie musi być podany tekst ($I-} oraz treść procedury Czytąj liczbe). procedure Czytaj Cvar prac: pracownik); begin Clr Scr; with prac,nazw,urodz,adres,poziom,obce do begin writeln C'Podaj pierwszeimig:'); readln Cimiepier); writelnC 'Podaj drugie imig: ' ); readln Cimiedrug); writeln C'Podaj nazwisko:'); readln Cnazwisko); Czytaj#liczbe C'Podaj dzień urodzenia',dzien); Czytaj#liczbe C'Podaj miesi#c urodzenia',miesiac); ,Czytaj#liczbe C'Podaj rok urodzenia',rok); writelnf'Podaj miejsce urodzenia:'); readln Cmiejsce); Czytaj#liczbe C'Podaj kod',kod); " writeln C'Podaj miejscowość:'); readln Cmiejscowosc); writeln C'Podaj ulicg:'); read Culica); Czytaj#liczbe C'Podaj numer',numer); Czytaj#liczbe C'Podaj numer mieszkania', mieszkanie); Czytaj#liczbe C'Podaj numer telefonu',telefon); writelnC 'Czy zna jgzyk angielski ' ) ; readln Cangielski); -90- 8. Rekordy writeln C'Czy zna jezyk rosyjski'); readln Crosyjski); writelnC 'Czy zna jezyk niemiecki ' ) ; readln Cniemiecki); writelnC 'Czy zna jezyk francuski ' ) ; readln Cfrancuski); writeln C'Podaj wykształcenie:'); readln Cwyksztalcenie); writeln C'Podaj stanowisko:'); readln Cstanowisko) end end; Na zakończenie zilustrujemy wykorzystanie tablicy jako pola rekordu. Przykład #I1 przykładzie zaprojektujemy elementy bazy danych przechowującej wyniki uzyskane na zawodach przez poszczególnych sportowców. Z uzyskanych wyników jest wyciągana średnia, która jest również zapamiętywana w bazie danych. System umożliwia wyszukanie sportowca o najwigkszej średniej. Modyfkacjg systemu tak, aby wykonywał więcej operacji zostawiamy jako ćwiczenie Czytelnikowi. Informacjg o startach jednego sportowca zapamigtamy w tablicy, która bgdzie polem rekordu zawierającego wszystkie informacje o danym sportowcu. Rekordy umieścimy w tablicy, aby można było wygodnie operować posiadaną informacją. Struktura wykorzystywanego rekordu jest następująca: zawodnik # nazw wynlki i srednia imiepier Ir#ledrug = - r1 # zwi k gdzie zawodnik jest rekordem, a wyniki są tablicą przechowująca wyniki sportowe. W projektowanym programie wykorzystamy czgść programu zamieszczonego w poprzednim przykladzie. W ten sposób zilustrujemy możliwość modyfikacji istniejącego programu do różnych celów. Wykorzystamy nastgpujące procedury: Zapisz, Odczytaj i funkcję Menu(). Funkcja Menu() powinna być nieco zmieniona tak, aby uwzględniała inne opcje systemu. Definicja struktury danych zastosowanej w programie, naglówki proce - 91- Nauka programowania... dur oraz program główny są przedstawione poniżej, natomiast algorytmy i treść procedur Czyt Obl oraz Srednia są podane w dalszym ciągu przykładu. Program 8.3 program Baza zawodn; uses Crt; const 1 i czbaprob = 5 ; type tabwyn = array Cl..liczbaprob] of real; ident = record imiepier, i mi edrug, nazwisko: string C20] end; zawodni k = record nazw:ident; wyni ki : tabwyn ; srednia: real end; const n#ma x =10 0 ; var dane : arrayC 1. . n max] of zawodni k ; baza : fi le of zawodni k ; ń integer; koni ec : bool ean ; procedure Zapisz Cn: integer); C Procedura zapisywania zawartości tabl icy na dysk ) f Treść procedury jest podana w poprzednim przykładzie ) begin end; procedure0dczytaj Cvarn:integer); C Procedura odczytywani a zawartości pl i ku do tabl i cy ) -92- g. R#ekordy f Treść procedury jest podana w poprzednim przykladzie ) begin end; function Menu : integer; f Funkcja tworzenia menu systemu ) f Podstawowa treść procedury jest podana w poprzednim przykładzie ) begin end; procedure Czyt# Obl Cvarzaw: zawodnik); ( Procedura wczytywania danych dl a jednego zawodni ka i obl i czani a średni ej ) begi n end ; procedure Srednia; f Procedura obliczania maksymalnej wartości średniej ; begi n end ; begin Odczytaj Cn); koniec := false; repeat case Menu of 1: i f n C n max then begin n:=n+1; Czyt Obl Cdane Cn]) # end; 2: Srednia; 0: begin Zapi sz'Ćri ) ;koniec := true end end until koniec; end. Możemy teraz przystąpić do zaprojektowania procedury Czyt Obl wczytującej dane i wyznaczającej wartość średnią. Algorytm wykorzystany w tej procedurze jest następujący: -93- Nauka programowania... Algorytm 8.5. wczytaj imię i nazwisko zawodnika wczytaj wyniki zawodnika oblicz warfość średniĄ A oto treść procedury. procedure Czyt Obl Cvar zaw: zawodni k) ; ( Procedura wczytywani a danych dl a jednego zawodni ka i ob1 i czani a średni ej ) var i:integer; suma: real; begin with zaw, nazw do C powi#zanie identyfikatorbw pól z rekordem zaw i podrekordem nazw ) begin wri tel n C ' Podaj pi erwsze i mi ę, drugi e i mi g i nazwi sko ' ) ; readln Cimiepier,imiedrug.nazwisko); writeln C'Podaj wyniki zawodnika'); suma :=0; fori :=1 to liczbaprob do Cdla każdego wyniku) begin wri tel nf ' Podaj wyni k ', i, ' zawodni ka ' ) ; readln Cwyniki[i]); suma := suma + wyni ki [i ] - end ; srednia := suma/liczbaprob end end; Algorytm wykorzystany w procedurze Srednia jest nastgpuj#cy: AlgOrytm 8.6. dla każdego rekordu wykonuj jeśli aktualna warfość średnia jest większa od dotychczas wyznaczonej warfości maksymalnej to zapamiętaj nowq warfość maksymalnĄ i numer rekordu wydrukuj nazwisko zawodnika z zapamiętanego rekordu 'I#eść procedury jest podana poniżej. -94- 8. ftekordy Procedure Srednia; ( Procedura obliczania maksymalnej wartości średniej ) var nr,i : integer; max: real; begin max := 0; for i :=1 to n do ( dl a każdego rekordu ) withdaneCi] do { powiazanie identyfikatorbwpbl z rekordem dane Ci] ) if srednia > max then begin nr:=i; max := srednia end; withdaneCnr],nazwdo f powiazanie identyfikatorów pbl z rekordem daneCnr) i podrekordem nazw ) writeln C'Zawodnik ',imiepier,imiedrug,nazwisko, ' maksymalna średni# rbwna: ',max:7:2); readln end; 8.4. Zadania l.W pliku zapamiętujemy rekordy zawierąjące"następujące informacje: nazwisko ucznia, jego imię oraz uzyskaną średnią. Po wczytaniu pewnego zakresu należy wydrukować: a) nazwiska uczniów, którz.y uzyskali średnią większą niż prawy kra- # niec podanego zakresu; b) nazwiska uczniów, których średnia zawiera się w podanym zakresie, I c) nazwiska uczniów, których średnia jest poniżej lewego krańca podanego zakresu. 2.W pliku zapamiętujemy rekordy zawierające nastgpujące informacje: nazwisko, imię, data urodzenia oraz wyniki uzyskane w czterech konkurencjach lekkoatletycznych: bieg na 100 m, skok w dal, skok wzwyż, skok o tyczce. Zaprojektować system umożliwiający aktualizację danych oraz wyznaczanie następującej informacji: -95- Nauka programowania... a) średnią wyników dla wszystkich sportowców w poszczególnych dyscyplinach, b) sportowca o nąjlepszym wyniku w poszczególnych konkurencjach, c) sportowca o nąjgorszym wyniku w poszczególnych konkurencjach. 3. Rozszerzyć przykład ilustrujący przechowywanie informacji o pracownikach tak, aby można było uzyskiwać następujące informacje: a) liczbg pracowników znających trzy i wigcej jgzyków obcych oraz ich nazwiska, b) liczbę pracowników znających dwa jgzyki obce oraz ich nazwiska, c) liczbg pracowników znających tylko jeden jgzyk oraz ich nazwiska. 4. Wydrukować podstawowe informacje o pracowniku według klucza, którym bgdzie nazwisko pracownika. -96- Rozdział REI#URENC#IA 9.1. Wprowadzenie Rekurencja polega na wywoływaniu danego podprogramu w jego treści. ftekurencja może być bezpośrednia i pośrednia. Rekurencja bezpośrednia zachodzi wtedy, gdy tekst danego podprogramu zawiera odwołanie do samego siebie. Natomiast z rekurencją pośrednią mamy do czynienia wtedy, gdy tekst podprogramu zawiera wywołanie podprogramu, w wyniku działania ktńrego nastgpuje wywołanie danego podprogramu. Rekurencja pośrednia nie będzie omawiana w niniejszej książce. Zauważmy tylko, że przy stosowaniu rekurencji pośredniej jest niezbgdna dyrektywa zapowiedzi podprogramu forward, która jest dokładnie omówiona w pracaeh [ 3,14 ]. Pojgcie rekurencji wyjaśnimy na przykładzie podprogramu drukowania w odwrotnej kolejności linii tejistu umiesZczonego w pliku. Dla porównania najpierw podamy program iteracyjny wykonujący to zadanie. Program 9.1 program Odwrotny; ( Program drukowani a 1 i ni i pl i ku tekstowego w kol ejności odwrotnej ) const 1 max =100 ; C maksymal ny rozmi ar tabl i cy ) var pl i k : text ; C pl i k tekstowy ) 1 i ni a : stri ng[80) ; C 1 ini a tekstu ) .g7# Nauka programowania... tab: array Cl..lmax] of string C807; ftablica zliniami tekstu) i, f zmi enna pomocni cza ) n ; f 1 i czba 1 i ni i w pl i ku tekstowym ) integer; begin assign Cplik,'test'); f przypisanie nazwy ) reset C pl i k ) ; f otworzeni e pl i ku ) n := 0; while not eofCplik) do f podczas gdy nie napotkano symbol u końca pl i ku ) begin n:=n+1; ifn # lmax then f jeśli za mała tablica ) begin writeln C'Za mala tablica'); halt end; readlnCplik,tabCn]); f wczytanie linii tekstu ) end; f wydruk w kolejności odwrotnej ) ! for i := n downto 1 do wr#teln Ctab Ci]); close Cplik) i end. Zauważmy, że powyższy program wymaga zadeklarowania tablicy, sprawdzenia, czy liczba linii w pliku nie jest wigksza od liczby elementów tablicy oraz wydruk elementów tablicy w kolejności odwrotnej. Spróbujemy teraz napisać wersjg rekurencyjną tego programu. Zadanie drukowania linii tekstu w kolejności odwrotnej realizować bgdzie procedura Odwroc. Procedura ta wykonuje tylko następujące operacje: wczytuje kolejną linię t#kstu, rekurencyjnie wywołuje samą siebie i drukuje zapamigtaną linig. Pełen tekst programu jest podany poniżej. Program 9.2 program Odwrotny; -98- 8. R,ekurencj a ( Program drukowani a 1 i ni i tekstu w kol ejności odwrotnej ) var pl i k : text : C pl i k tekstowy ) procedure Odwroc Cvar plik: text); ( Rekurencyjna procedura odwracania kolejności ) var 1 i ni a : string[80] ; ( 1 i ni a tekstu ) begin ifnot eofCplik) then (jeśli nie napotkano końca pliku) begin readlnCplik,linia); f wczytanie linii } Odwroc Cplik); (rekurencyjne wywolanie procedury) writelnClinia); C wydruk linii ) end end; begin assignCplik, 'test' ); f przypisanie nazwy } reset C pl i k ) ; ( otworzeni e pl i ku ) OdwrocCplik); ( wydrukw kolejności odwrotnej } close Cplik) end. Przeanalizujemy tQraz działanie programu. Przypuśćmy, że plik zawiera następujące linie: a8aaa bbbbb ccccc ddddd Instrukcje zawarte w pr.eeedurze wy#onują#e jakąś operacjg ponumerujmy w kolejności od 1 do 3: { 1 } readln(plik,linia); { wczytanie linii } { 2 } Odwroc(plik); { rekurencyjne wywołanie procedury } { 3 } writQln(linia); { wydruk linii } Schemat wywołańrekurencyjnych przedstawiono poniżej (liczbami rzymskimi zaznaczono poziom wywołania rekurencyjnego): -99- Nauka programowania... 1. readln(plik,linia) - aaaaa 2. Odwroc(plik) 1. readln/plik,linia) - bbbbb 2. Odwroc(plik) 1. readln/plik,linia) - ccccc 2. Odwroc(plik) 1. readln(plik,linia) - ddddd ## ### #V 2. Odwroc(plik) ( Koniec pliku ) 3. writeln(linia) - ddddd 3. writeln(linia) - ccccc 3. writeln(linia) - bbbbb 3. writeln(linia) - aaaaa Wczytane linie pliku są pamiętane w zmiennych lokalnych linia lkażda dla poszczególnego wywołania procedury), co powoduje utworzenie stosu tych zmiennych (na wierzchołku stosu znajduje się zmienna o zawart,ości odpowiadającej czwartemu - ostatniemu - poziomowi wywołania): wartość zmiennej lokalnej linia poziom wywołania ddddd '# ccccc III bbbbb II ; I aaaaa I ;' 1 Wyprowadzenie wart,ości zmiennych lokalnych daje w wyniku wydruk linu tekstu w kolejności odwrotnej niż są umieszczone w pliku. Porównując oba przedstawione programy stwierdzamy,że rozwiązanie rekurencyjne jest bardziej przejrzyste i krótsze.W programie rekurencyjnym uniknęliśmy deklaracji tablicy i sprawdzania,czy liczba linii w pliku nie jest większa nit liczba elementów tablicy.Należy jednak podkreślić,że w progra- mach rekurencyjnych pamigć do przechowywania wartości zmiennych lokal- nych jest również potrzebna,mimo iż nie jest ona deklarowana jawnie. Rekurencjg należy zat,em stosować z dużą ostrożnością pamigtając,że nie zawsze rozwiązanie rekurencyjne jest lepsze od rozwiązania nierekuren- cyjnego. Istnieje jednak pewna klasa problemów, w których rozwiązania rekurencyjne są zdecydowanie bardziej eleganckie i prostsze od rozwiązań iteracyjnych. Można powiedzieć, że są t,o zagadnienia związane przede wszystkim z rekurencyjnymi strukturami danych,które zostaną omówione w rozdziale 12,oraz te problemy,które można rozłożyć na podproblemy takie same jak problem początkowy.Właściwie wykorzystana rekurencja jest potężnym narzgdziem pozwalającym na zwarty i jednocześnie przejrzys- ty zapis skomplikowanych operacji. # OO # 9. Rekurencja W nastgpnych podrozdziałach zilustrujemy kilkoma przykładami wykorzystanie rekurencji. Omówione bgdą takie problemy, w których rekurencyjne rozwiązanie jest znacznie lepsze niż rozwiązanie it#racyjne. 9.2. Algorytmy z powrotami Algorytmy z powrotami są bardzo często stosowane do rozwiązywania problemów kombinatorycznych, które można sformułować w nastgpujący sposób. Danych jest n uporządkowanych zbiorów Z1,...,Zn. Należy skonstruować wektor A = (al,...,an), gdzie al e Zl,...,a# e Z#, który spełnia dane warunki lub ograniczenia. Wektor A tworzy się nastgpująco: kolejno przeszukuje sig zbiory Z1,...,Zn zaczynając zawsze od elementu najmniejszego danego zbioru i wykonując powrót do poprzedniego zbioru w przypadku wyczerpania wszystkich elementflw aktualnie przeszukiwanego zbioru. Algorytmy z powrotami zilustrujemy dwoma przykładami. Przykład W przykładzie zaprojektujemy i zrealizujemy algorytm ustawiania 8 hetmanów na szachownicy, tak aby żaden z nich nie znajdował sig w polu atakowanym przez innego hetmana. Liczba wszystkich możliwych ustawień hetmanów na szachownicy wynosi 8s (przy założeniu, że w każdej kolumnie znajduje się tylko jeden hetman). Rozwiązanie polegające na wygenerowaniu wszystkich możliwych ustawień hetmanów na szachownicy i sprawdzeniu, które z nich spełniają warunki zadania, jest zatem nie do przyjęcia. W celu rozwiązania problemu wykorzystamy algorytm powrotu. Kolejne hetmany będziemy ustawiać na szachownicy poczynając od pierwszej kolumny Pierwszego hetmana ustawimy w pierwszej kolumnie, drugiego - w drugiej itd. licząc od lewej strony szachownicy do prawej. W ka#dej kolumnie pieryvszą badaną pozycją bgdzie najniższa dotychczas nie sprawdzona. Na rys. 9.1. są przedstawione pozycje pierwszych pigciu hetmanów po ustawieniu ich zgodnie z podanymi regułami. W szóstej kolurnnie nie można ustawić hetmana, ponieważ wszystkie pola są pod działaniem hetmanów umieszczonych w pierwszych pięeiu kolurnnach. Należy w tym momencie wykonać powrót i powrócić do kolumny piątej przestawiając stojącego tam hetmana na pozycję wyższą spełniającą warunki zadania. Rys. 9.2. przedstawia pozycje pierwszych pięciu hetmanów po wykonaniu powrotu. Kroki te wykonuje się tak długo, aż zostanie znalezione rozwiązanie lub stwierdzony jego brak. #lOl' Nauka programowania... 3 2 1 6 5 4 3 1 1 2 3 4 5 6 7 8 Hys. 8.2. Pozycje pierwszych pigciu hetmanów po wykonaniu powrotu Powyższy algorytm zrealizujemy przy pomocy procedury rekurencyjnej o nazwie Ustaw. Procedura ta próbuje ustawić hetmana w j-tej kolumnie w wierszu nąjniższym. Pozytywne zakończenie próby powoduje wywołanie procedury rekurencyjnej dla kolumny j + l. W przypadku nieudanej próby ustawienia hetmana w j + 1 kolumnie następuje powrót i usunigcie ostatnio ustawionego hetmana z kolumny j. Procedurę kończy ustawienie hetmana zgodnie z przyjętymi zasadami lub osiągnięcie ostatniej kolumny szachow -102 - 1 2 3 4 5 6 7 8 Rye. 9.1. Pozycje pierwszych pięciu hetmanów 8. R#kurencja nicy Algorytm zastosowany w tej procedurze możemy sformułować nastgpuj#co. Algorytm 8.1. przypisz i warfość 0 powtarzaj wybierz następnQ pozycję ( i := i + 1) jeśli pozycja jest dobra tozaznacz ustawienie hetmana jeśli j < 8 to wywolaj rekurencyjnie opisywanQ procedurę dla j + 1 jeśli nie powiodło się ustawienie hetmana to , usuń zaznaczenie ostatnio ustawionego hetmana at powiodło się ustawienie hetmana lub nie ma pozycji (i = 8) Obecnie zaprojektujemy strukturg danych wykorzystywaną w programie. Zauważmy nąjpierw, że gdyby pozycje hetmanów przechowywać w tablicy dwuwymiarowej, to sprawdzenie czy dany hetman nie znąjduje sig w polu bgdącym pod kontrolą innego hetmana, wymagałoby przeglądania tablicy we wszystkich możliwych kierunkach. Oczywiście takie rozwiązanie jest nie do przyjgcia i należy poszukać innego. W książce "Nauka programowania dla początkujących" [20] była podawana zależność na indeksy elementów leżących na przekątnych na prawo w skos i na lewo w skos. Zauważmy, że hetman stojący na pozycji k,l kontroluje przekątną prawo w skos, której indeksy spełniąją zależność i + j = k + 1, przekątną lewo w skos, której indeksy spełniają zależność i - j # k -1 oraz k-ty wiersz oraz 1-tą kolumng. Ilustruje to rys. 9.3. Struktura danych wykorzystywana w programie powinna być zatem złożona z trzech tablic zawierąjących informacjg o tym, czy dany wiersz, przekątna lewo w skos i przekątna prawo w skos są w polu działania danego hetmana (ponieważ każdego hetmana umieszczamy w oddzielnej kolumnie, nie jest potrzebna informacja o kontrolowaniu danej kolumny przez hetmana). Deklaracja tych tablic jest podana poniżej: wiersz: array[1..8] ofboolean; prawa: array[2..16] of boolean; lewa: array[-7..7) ofboolean; # IO3 # Nauka programowania... hetman: array[1..8] of integer; 1 2 3 4 5 6 7 8 Rys. 9.3. Pola kontrolowane przez pojedynczego hetmana Rys. 9.4 podaje przykładowe zawartości tych tablic w trakcie wykonywania algorytmu, a na rys. 9.5. są zaznaczone pola kontrolowane przez hetmany, o których informacja jest zawarta w tych tablicach. wiersz F F F F F T T T prawa I F T T F F T F F T T T T T T T - lewa ` . I T T T T T F F F F F T T T T T hetman 1 3 5 2 4 Rys. 9.4. Przykładowe zawartości tablic hetman, wiersz, prawa, lewa -104 - 9. R,ekurencja Mąjąc określoną strukturę danyeh można teraz sprecyzować zdania seudo-kodu. Zdanie pseudo-kodu "zaznacz ustawienie hetmana" sprecyzujey w sposób następujący: hetman[j ] := i ; wiersz[i] := false; prawa[i+j] :=false; lewa[i -j] := false; Natomiast zdania "usuń ustawienie hetmana" zapiszemy w sposób następujący: wiersz[i] := true; prawa[i+j] := true; lewa[i-j) := true; Warunek czy pozycjajes_t d.e#ra może b#># wyrażony następująco: wiersz[i) and prawa Ci+j] andlewa[i-j) co oznacza, że i-ty wiersz, przekątna prawo w skos o sumie indeksów itj oraz przekątna lewo w skos o sumie indeksów i ;j nie znajdują się w polu ', ; # działania żadnego hetmana. Program 9.3 program Hetmany; ( Program ustawiania ośmiu hetmanbw na szachownicy ) var ; -105 - 1 2 3 4 5 6 7 8 Rys. 9.5. Pola kontrolowane przez hetmany Nauha programowania... j, k : i nteger ; f zmi enne pomocni cze ) ok : bool ean ; f zmi enna kontrol na ) wi ersz : arrayC 1. . 8] of bool ean ; f zajętość wi ersza ) prawa: array[2. .16] of boolean; f zajętość przek#tnej prawo w skos) 1 ewa : arrayC -7. . 7) of bool ean ; f zaj ętość przek#tnej 1 ewo w skos ) hetman : arrayCl. .8] of i nteger ; f polożeni e hetmanów w kol umnach ) procedure Ustaw Cj : i nteger ; var ok : bool ean ) ; f Rekurencyjna procedura ustawiania hetmana ) var i:integer; begin i := 0 ; f ustawi eni e pocz#tkowe ) repeat i:=i+1# ok := fal se ; ifwierszCi] andprawa[i+j] andlewa[i-j] then begin f zapami ętani e ustawi eni a hetmana ) hetman[j] := i ; wiersz[i] :# false; prawa Ci+j] ;= false; lewa[i-j] :=false; if j C 8 then f jeśl i s# jeszcze kol umny ) begin f rekurencyjne wywolanie procedury dla następnej kolumny ) Ustaw Cj + 1, ok ) ; i f not ok then begin f usuni ęci e zaznaczeni a hetmana ) wiersz[i) := true; prawa[i+j ] := true; lewa[i-j] :=true end end else ok := true f znal ezi ono ustawi eni e ośmi u hetmanów ) end unti 1 ok or C i = 8 ) f aż znal ezi ono ustawi eni e 1 ub koni ec wi erszy ) -106 - 8. ftekurencja end: procedure Rozwi azani e ; f Procedura drukowania rozwiązania ) var i,j:integer; Degin writelnC' '7; # T - T - T # T - T - T # T - # forj := 8 downto 1 do ( dl a każdego wi ersza ) begin write Cj:3,'# '); for i :=1 to 8 do i f hetman [j ]=i then write C'H','# ') else writeC",'# '); wri tel n ; if j C# 1 then writelnC' #-+-+ end; writelnC ' # -1-1-I-1-l#l#1-# '); writelnC'12345678 ') end; begin # ustawienie warunków pocz#tkowych ) for k :=1 to 8 do wiersz[k] := true; " for k := 2 to 16 do prawaCk] := true; for k := -7 to 7 do lewaCk] := true; Ustaw C 1, ok ) ; ( ustaw#ani e hetman#w ) ' if ok then Rozwiazanie el se writeln C'Brak rozwi#zań') end. Na rys. 9.6 przedstawiono ustawienie hetmanów na szachownicy odpowiadające wygenerowanemu rozwiązaniu. -107 - Nauka programowania... 8 7 6 1 2 3 4 5 6 7 8 R,ys. 9.6. Ustawienie ośmiu hetmanów na szachownicy Spróbujmy jeszcze prześledzić kilka rekurencyjnych wywołań procedury Ustaw. Ustaw( l,ok) i = 1 # Ustaw(2,ok) i = 3 # Ustaw(3,ok) i = 5 # Ustaw(4,ok) i = 2 # Ustaw(5,ok) i = 4 # Ustaw(6,ok) ok = false ( powrót } i = 8 # Ustaw(6,ok) # ok = false ( powrót } i = 7 # Ustaw(5,ok) i=2#... W powyższym schemacie na przykład wywołanie Ustaw(3,ok) oznacza - # # wywołanie procedury Ustaw dla trzeciej kolumny, a zmienna i oznacza numer wiersza, w którym jest wstawiany hetman. Przykład W przykładzie przedstawimy znany szeroko w literaturze problem znalezienia takiej drogi skoczka szachowego, aby każde pole szachownicy było odwiedzone przez niego dokładnie raz. Podobnie jak w poprzednim przykładzie do rozwiązanie tego problemu ' IO8 ' 9. Rekurencj a wykorzystamy algorytm powrotu. Na wstępie określimy kolejność wykonywania ruchów skoczkiem. W każdym etapie obiegania szachownicy próba wykonania ruchu będzie zgodna z tą kolejnością, która może być dowolna pod warunkiem, że zawsze będzie taka sama. Przyjętą przez nas kolejność definiuje tablica przedstawiona na rys. 9.7. R,ys. 9.7. Kolejność wykonywania ruchów skoczkiem Rozważmy teraz przykładową szachownicę o rozmiarach 4 * 4 i położenie punktu początkowego 2,2. Spróbujmy wykonać kilka kroków algorytmu powrotu. Kolejne ruchy wykonujemy zgodnie z przyjętą kolejnością (zawsze zgodnie z ruchem wskazówek zegara poczynając od ruchu zaznaczonego na rys. 9.7 cyfrą 1). W przypadku gdy danego posunięcia nie da się wykonać, próbujemy wykonać kolejny możliwy do wykonania ruch z danego punktu. Poszczególne ruchy zaznaczamy kolejnymi liezbami całkowitymi. 1 2 3 4 ftys. 9.8. Kilka ruchów skoczka na szachownicy Zauważmy, że w sytuacji podanej na rys. 9.8. z punktu o współrzędnych 4,1 nie można wykonać żadnego ruchu. Należy zatem wykonać podstawowy krok algorytmu powrotu i cofnąć się do takiego położenia, z którego można kontynuować ustawianie. W naszym przypadku usuwamy ruch o numerze 4 -109 - Nauka programowanig... i wykonujemy go teraz do punktu o wspó#'zgdnych 2,1. Kilka następnych posunięć pokazuje szachownica przedstawiona na rys. 9.9. 1 14 5 2 2 4 1 8 11 3 13 10 3 6 4 7 12 9 1 2 3 4 Rys. 8.9. Kilka ruchów skoczka na szachownicy po wykonaniu powrotu Dla ruchu o numerze 14 nie można wykonać żadnego następnego posunięcia, musimy się zatem cofnąć do takiego położenia, z którego można wykonać ruch, który dotychczas nie był wykonywany Analizując szachownicę dochodzimy do wniosku, że należy się cofnąć do ruchu o numerze 11 i ruch 12 zamiast wykonać do punktu o współrzędnych 4,3 wykonać do punktu o współrzędnych 1,2. Sytuację tę ilustruje rys. 9.10. 1 12 5 2 2 4 1 8 11 3 10 3 6 4 7 9 1 2 3 4 Rys 9.10. Sytuacja na szachownicy po wykonaniu kolejnego powrotu Przedstawiony algorytm zrealizujemy przy pomocy procedury rekurencyjnej. Unikamy w ten sposób jawnego pamiętania, który ruch spośród ośmiu możliwych został wykonany Na przykład w sytuacji podanej na rys. 9.8- trzeba pażniętać dane: numer rucbu startowego numer wykonanego ruchu 1 1 2 5 3 5 W przypadku konieczności powrotu do ruchu o numerze 3 będziemy próbowali wykonać posunięcie o numerze wyższym niż 5 spośród ośmiu możliwych do wykonania ruchów. W tym przypadku zostanie wykonany ruch o numerze 6. -110 - 8. Rekurencja - Ogólna wersja algorytmu wykonywania następnego ruchu wykorzystanego w procedurze o nazwie Ruch jest przedstawiona poniżej. Algorytm 9.2. zdefiniuj ustawienie poczqtkowe powtarzaj wybierz następny ruch jeśli ruch jest możliwy to zaznacz wykonanie ruchu ů jeśli sQ jeszcze wolne pola to wykonaj rekurencyjnie procedurę dla następnego ruchu jeśli ruch nie jest możliwy to skasuj zapis ostatniego ruchu aż ruch został wykonany poprawnie lub nie ma więcej możliwych ruchów Podobnie jak w problemie ustawienia ośmiu hetmanów na szachownicy musimy teraz określić strukturę danych, która bgdzie dalej wykorzystywana. Szachownicę bgdzie reprezentować tablica o nazwie szach. Maksymalny rozmiar tej tablicy określimy w stałej nmax, natomiast aktualny rozmiar tablicy bgdziemy wczytywać do zmiennej n. Kolejno wykonywane posunigcia będą zapisywane w postaci liczb całkowitych. Jeśli element (pole) tablicy ma wartość zero oznacza to, że pole to nie było,jeszcze odwiedzone. Parametry formalne procedury Ruch powinny być następujące: procedure RuchCi,wspl,wsp2: int,gger; var ok: boolean); gdzie i oznacza numer ostatnio wykonanego ruchu, wspl oraz wsp2 są współrzgdnymi tego ruchu, zmienna ok określa czy udało się wykonać ruch. Możemy teraz przystąpić do precyzowania zdań wystgpujących w algorytmie 9.2. Zdanie "ruch jest możliwy" zapiszemy w postaci if Cwspnastl in [1. .n)) and Cwspnast2 in [1. .n]) then ifszach[wspnastl,wspnast2] = 0 then gdzie wspnastl oraz wspnast2 są współrzędnymi następnego ruchu. Powyższe instrukcje sprawdzają, czy współrzgdne leżą wewnątrz tablicy i następ -111- Nauka prog#ramowania... nie czy pole o tych współrzędnych ma wartość zero, co oznacza, że dane pole nie było odwiedzone. Instrukcji tych nie można połączyć, ponieważ w przypadku gdy współrzędne nie leżą wewnątrz tablicy, to zmienna szach[wspnastl,wspnast2] jest nieokreślona. Zdanie "są jeszcze wolne pola" zapiszemy w postaci iCn*n; Oznacza to, że liczba wykonanych ruchów jest mniejsza niż liczba pól szachownicy. Zdanie "zaznacz wykonanie ruchu" sprecyzujemy jako szach[wspnastl,wspnast2] := i; natomiast zdanie "skasuj zapis ostatniego ruchu" zapiszemy jako szach[wspnastl,wspnast2] := 0; Należy jeszcze wprowadzić zmienną lokalną o nazwie okwewn w celu sprawdzenia, czy udało się wykonać następny ruch. Na koniec zdefiniujemy sposób wyznaczenia współrzgdnych wspnastl oraz wspnast2 w zależności od tego, który ruch spośród ośmiu możliwych jest sprawdzany W tym celu określimy globalną tablicę o nazwie ruchy, zawierającą różnice współrzędnych dla każdego spośród ośmiu ruchów. Tablica ta ma postać: ruchy[1,1] : -2; ruchy[1,2] : 1; ruchy[2,1] : -1; ruchy[2,2] := 2; ruchy[3,1] : 1; ruchy[3,2] := 2; ruchy[4,1] := 2; ruchy[4,2] : 1; ruchy[5,1] : 2; ruchy[5,2] : -1; ruchy[6,1] : 1; ruchy[6,2] : -2; ruchy[7,1] : -1; ruchy[7,2] : -2; ruchy[8,1] : -2; ruchy[8,2] : -1; Na przykład aby wykonać piąty z kolei ruch dla skoczka stojącego na polu o współrzędnych 2,3, należy zwiększyć współrzędną odpowiadającą . ů numerowi wiersza o 2 (ruchy[5,1]=2), a współrzędną odpowiadającą numerowi kolumny zmniejszyć o jeden (ruchy[5,2]=-1), a zatem musimy przesta; wić skoczka do pola o współrzędnych 4,2. Program znajdowania drogi skoczka jest podany poniżej. ' Program 9.4 program Skoczek; ( Program znajdowania drogi skoczka na uogólnionej szachownicy ) const nmax = 20;[ maksymalny rozmiar szachownicy ; -112 - 8. Rekurencja var i, j, f zmi enne pomocni cze ) n, f rozmiar szachownicy ) poczl,pocz2: f pocz#tkowe ustawienie skoczka ) integer; ok : bool ean ; f zmi enna kontrol na ) ruchy: array Cl..8,1..2) ofinteger; f różnice współrzgdnych ) szach: array Cl..nmax,l..nmax] ofinteger; f szachownica ) procedure Ruch Ci,wspl,wsp2:integer; var ok: boolean); f Rekurencyjna procedura wyznaczania następnego ruchu ) f i - numer ruchu, wspl,wsp2 - aktualne wspólrzgdne skoczka, ok - zmi enna kontrol na ) var okwewn: boolean; nr, f kolejny ruch spośród ośmiu możliwych ruchów ) wspnastl, wspnast2: f wspólrzędne następnego ruchu ) integer; begin nr := 0; f przygotowanie wyboru ruchów ) repeat nr := nr + 1; f wybranie nastgpnego ruchu spośród ośmi u możl iwych ruchów ) okwewn := fal se ; f ustawi eni e wartości zmi ennej kontrolnej ) f ustalenie wspólrzędnych następnego ruchu ) wspnastl := wspl + ruchy[nr,1] ; wspnast2 := wsp2 + ruchy[nr,2] ; if Cwspnastl in.[#'.n]) and C-#spnast-2 in [1. .n]) then if szach[wspnastl,wspnast2] = 0 then f ruch dopuszczalny ) begin f zaznaczenie ustawienia nastgpnego ruchu ) szach[wspnastl,wspnast2] :=i; if i C n * n then f jeśli s# wolne pola ) begin f rekurencyjne wywolanie procedury dla nastgpnego ruchu ) Ruch Ci+l,wspnastl,wspnast2,okwewn); Nauka programowania... if not okwewn then f usuni gcie zaznaczeni a ruchu } szach[wspnastl,wspnast2] := 0 end el se o kwewn : = t rue end until okwewn or Cnr = 8) ; C aż ruch zostal wykonany poprawni e 1 ub ni e ma wi gcej możl i wych ruchów } ok := okwewn ( wyprowadzenie na zewn#trz wartości kontrolnej } end; begin writeln C'Podaj rozmiar szachownicy'); readln Cn); writeln C'Podaj punkty poczatkowe'); readln Cpoczl,pocz2); if C not Cn in [1. .nmax])) or C not Cpoczl in [1. .n])) or C not Cpocz2 in [1. . n] ) ) then begin writeln C'Bląd danych'); halt end; ( wyznaczenie różnic współrzgdnych } ruchyCl,l) : -2; ruchy[1,2] : 1; ruchy[2,1] : -1; ruchy C2,2) := 2; ruchyC3,1) : 1; ruchy[3,2] := 2; r#chy[4;1] := 2; ruchy[4,2] : 1; ruchy C5,1] := 2; ruchy[5,2] : -1; ruchy C6,1] : 1; ruchy C6,2] : -2; ruchy[7,1] : -1; ruchy[7,2] : -2; ruchy[8,1] : -2; ruchy CB,2) : -1; f przygotowani e tabl i cy } fori:=ltondo for j :=1 to n do szach[i,j] := 0; -114 - 8. ftekurencj a szach[poczl,pocz2] := 1; Ruch C2,poczl,pocz2,ok); C wyznaczanie ruchów ) if ok then ( wydruk rozwi dzani a ) for i :=1 to n do begin for j :=1 to n do write Cszach[i,j]:4); writeln end el se writeln C'Brak rozwi#zania') end. Na rys. 9.12 są podane wyniki wygenerowane przez program dla sza- ! chownicy o rozmiarach 5 * 5, a na rys. 9.11 wygenerowane wyniki dla # rozmiarów 8 * 8. W obu przypadkach punktem startowym jest punkt o i' współrzgdnych 1,1. 8 1 38 55 34 3 36 19 22 7 54 47 2 37 20 23 4 17 6 39 56 33 46 35 18 21 10 5 48 53 40 57 24 11 16 5 4 59 32 45 52 41 26 9 12 3 44 49 58 25 62 15 6 27 2 31 60 51 42 29 8 13 64 1 50 :4-## 30 :6#` 14 63 28 7 1 2 3 4 5 6 7 8 Rys. 8.11. Wygenerowane wyniki dla szachownicy o rozmiarach 8 * 8. Rozwiązanie dla szachownicy 8 * 8 generowane było jednak długo, bo ## około 50 minut na komputerze IBM PC/AT ( 12 minut na komputerze IBM # PC/386 DX ). -115 - Nauka prog#ramowania... 5 1 20 17 12 3 4 16 11 2 7 18 3 21 24 19 4 13 2 10 15 6 23 8 1 25 22 9 14 5 1 2 3 4 5 ftys. 9.12. Wygenerowane wyniki dla szachownicy o rozmiarach 5 * 5 9.3. Algorytmy sortowania W niniejszym podrozdziale podamy dwa nowoczesne algorytmy sortowania tablic. Rozważymy tak zwane sortowanie szybkie i sortowanie przez łączenie. Sortowanie szybkie charakteryzuje sig najlepszym oczekiwanym czasem sortowania. Jego wadą jest powolność działania, w przypadku szczególnym tzn., gdy tablica zawiera takie same elementy. Mimo to jest ona najlepszą ze znanych obecnie metod sortowania tablie. Drugą z kolei jest metoda sortowania przez łączenie, której mankamentem jest konieczność wykorzystania tablicy o 2 * n elementach w celu posortowania tablicy o n elementach. Przykład W przykładzie rozważymy sortowanie szybkie. Jak już wyżej wspomniano, metoda ta pod wzglgdem oczekiwanego czasu działania jest najlepszą z dotychczas znanych metod. Oczekiwany czas działania jest to średni czas otrzymany przy sortowaniu dużej liczby tablic zawierających elementy , , ustawione w sposób przypadkowy. Algorytm sortowania szybkiego w sposób jak najbardziej ogólny w postaci opisu słownego można przedstawić nastgpująco. Krok 1. Wybierz dowolny element x z tablicy. Krok 2. Podziel tablicę na dwie spójne czgści: czgść lewostronną T1 z elementami mniejszymi niż x oraz część prawostronną T2 z elementami wigkszymi bądź równymi x. T 1 j ) Powyższy algorytm zilustrujemy na przykładzie tablicy. 7 1 8 6 4 9 5 Element środkowy tablicy wyznaczymy p#zy pomocy instrukcji: x := a[Clewy + prawy')#div 2 ]; W naszym przypadku element ten będzie równy 6. Nnastępnie zostanie wykonany następujący ciąg zamian: i j 2amieniane elementy tablica po zamianie 1 7 7H5 5186497 3 5 8H4 5146897 5 4 Po wykonaniu tylko dwóch zamian uzyśkaliśmy tablicę, w której można wyróżnić dwie części: pierwszą (od elementu pierwszego do czwartego), w -117 - Nauka programowania... której wystgpują elementy mniejsze bądź równe 6 i drugą (od elementu piątego do siódmego), w której wystgpują elementy wigksze od 6. Po podzieleniu tablicy na dwie czgści wykonujemy nastgpnie ten sam algorytm dla każdej z nich, tak długo aż otrzymamy czgści jednoelementnwe. Dla omawianej tablicy otrzymamy dwie nastgpujące czgści 5 1 4 6 oraz 8 9 7, dla których dalej wykonujemy podany algorytm. Obecnie przedstawimy rekurencyjną wersjg szybkiego sortowania tablicy Dla zachowania zgodności z algorytmem 9.3 należałoby dodać żądanie posortowania lewej i prawej czgści tablicy A otn program testujący rekurencyjną wersjg szybkiego sortowania. Program 9.5 program Test; ( Program testujacy rekurencyjnd wersję szybkiego sortowania tablicy ) const nmax =100 ; ( maksymal ny rozmi ar tabl i cy ) type tablica = array[l. .nmax] of integer; var n, f rozmi ar tabl i cy ) i : ( zmi enna pomocni cza ) integer; a: tablica; procedure Szybkie Cvara:tablica;lewy, prawy:integer); ( Rekureneyjna procedura szybkiego sortowania ) " ( 1 ewy - 1 ewy krani ec sortowanego wyci nka, prawy - prawy kraniec sortowanego wycinka ) var i, ( zmi enna przebi egajaca 1 ew# część tabl i cy ) j, ( zmi enna przebi egaj#ca praw# część tabl i cy ) x, C element środkowy ) pom: f zmi enna pomocni cza do zami any el ementów ) integer; begin i : =1 ewy ; j := prawy; C wybranie środkowego elementu ) -118 - 9. R,ekurencja x := a[Clewy + prawy ) div 2 ); repeat whi le a Ci ] C x do i:=i+1; whi 1 e x C a Cj ] do j :#j - 1; i f i C= j then '" begin ( zamiana wybranych elementów ) pom :=aCi]; aCi] :=aCj]; aCj] :=pom; i:=i+1; ' j :=j - 1 I end unti 1 i # j ; ( aż przej rzel i śmy 1 ew# i prawa czgść tabl i cy ) f wywolanie procedury dla lewej części ) if lewy C j then SzybkieCa,lewy,j); C wywolanie procedury dla prawej czgści ) if i C prawy then SzybkieCa,i,prawy) end; begin writeln('Podaj rozmiar tablicy'); readln Cn); writeln('Podaj elementy tablicy'); fori:=ltondo :## read Ca Ci]); SzybkieCa,l,n); writeln C'Tablica posortowana:'); fori:=ltondo wri teln Ca Ci ] ) ; end. Obecnie dla porównania podamy nierekurencyjną wersjg algorytmu -119 - Nauka programowania... sortowania szybkiego. Ta wersja algorytmu wymaga użycia stosu (patrz rozdz.12 ). Przy podziale tablicy na dwie czgści lewa część jest sortowana bezpośrednio, a żądanie posortowania prawej części zapamiętuje się na stosie. Po zakończeniu sortowania lewych części pobiera sig żądanie z wierzchołka stosu. Czynności te wykonuje się tak długo, aż stos będzie pusty. A oto algorytm zapisany w pseudo-kodzie. Algorytm 9.4. wpisz na stos żqdanie posortowania całej tablicy powtarzaj powtarzaj pobierz ze stosu żqdanie posortowania wycinka tablicy określonego przez zmienne lewy i prawy przestaw elementy wycinka, tak aby otrzymać podział tego wycinka na dwie części: pierwszq zawierajqcq elementy mniejsze od wyróżnionego elementu i drugq zawierajqcq elementy większe od wyróżnionego elementu jeśli prawa część wycinka nie jest pusta to zapamiętaj na stosie żqdanie posortowania prawej części wycinka zmiennej prawy przypisz wartość określajqcq ostatni element lewej części wycinka aż lewy >= prawy aż stos jest pusty Podamy teraz nierekurencyjną procedurg realizującą szybkie sortowanie tablic wraz z programem jej testowania. Progranl 9.6 prógram Test; C Program testowania nierekurencyjnej wersji sortowania szybkiego ) const nmax =100 ; ( maksymal ny rozmi ar tabl i ey ) type tablica = arrayCl. .nmax] of integer; var n, ( rozmi ar tabl i cy ) i : f zmi enna pomocni cza ) integer; -120 - 9. ftekurencja a : tabl i ca ; f sortowana tabl i ca ) procedure Szybkie nier Cvar a:tablica; lewy,prawy:integer); f Procedura sortujdca tablicę bez wykorzystania rekurencji) const maxstos = 30 ; f maksymal na 1 i czba el ementów na stosi e ) var i, f zmi enna przebi egaj dca 1 ewd część tabl i cy ) j, f zmi enna przebi egaj #ca praw# czgść tabl i cy ) x, f środkowy element ) pom: f zmi enna pomocni cza do zami any el ementów ) integer; wskstos: O..maxstos; f wskaźnik stosu ) stos: array Cl..maxstos,1..2] ofinteger; begin f wpi sani e na stos ż#dani a posortowani a całej tabl i cy ) wskstos :=1; stosCl,l] :=1; stosCl 2] :=n; repeat f pobrani e ze stosu ż#dani a posortowani a wycinka tabl i cy ) lewy := stosCwskstos,l); prawy := stos[wskstos,2]; wskstos := wskstos - 1; repeat f przestawienie elementów wycinka określonego przez zmi enne 1 ewy i prawy ) i : =1 ewy ; j := prawy; . f wybranie środkowego elementu wycinka ) x:=a[Clewy+prawy)div2]; repeat whilea[i]Cxdo i:=i+1; while x C a[j] do j :=j - 1; -121- Nauka programowania... i f i C= j then begin ( zami ana wybranych el ementów } pom := a Ci ] ; aCi] :=aCj]; a Cj ] := pom; i:=i+1; j :=j - 1; end unti 1 i # j ; ( aż nastapi lo spotkani e ) if i C prawy then f jeśli prawa czgść nie jest pusta ) begin C zapamiętanie na stosie ż#dania posortowania prawej części wycinka ) wskstos := w5kstos + 1; stos Cwskstos,l] := i; stos Cwskstos,2] := prawy end; prawy := j { określ eni e prawego krańca 1 ewego wyci nka ) unti 1 1 ewy #= prawy C aż ni e ma 1 ewych wyci n ków ) until wskstos = 0( aż stos jest pusty ) end; begin wri tel,p C ' Podaj rozmi ar tabl i cy ' ) ; readln Cn); writeln C'Podaj elementy tablicy'); fori:=ltondo . ` readůtaCi)); Szybkie#nierCa,l,n); writeln C'Tablica posortowana:'); fori:=ltondo writelnCaCi )) ; end. Podsumowując można stwierdzić, że wersja rekurencyjna algorytmu szybkiego sortowania jest krótsza i bardziej przejrzysta. Jej wadą jest nato -122 - 9. R,ehurencja miast fakt, że wymaga ona użycia w sposób niejawny stosu, ktńrego rozmiar jest proporcjonalny do ilości elementów tablicy. Dla dużych tablic takie rozwiazanie jest nie do przyjgcia. Przyhład W przykładzie rozważymy sortowanie przez łączenie. Jak już sama nazwa wskazuje, metoda ta polega na podzieleniu tablicy na dwie części, rekurencyjnym ich posortowaniu i następnie na scaleniu posortowanych czgści. Algorytm wykorzystany w rekurencyjnej procedurze, którą nazwiemy Sortuj, jest następujący: Algorytm 8.5. podziel tablicę na dwa wycinki jeśli lewy wycinek zawiera więcej niż jeden element to wywolaj rekurencyjnie procedurę Sorfuj jeśli prawy wycinek zawiera więcej niż jeden element to wywotaj rekurencyjnie procedurę Sorfuj scal dwa posorfowane wycinki Scalanie wykonywane w algorytmie należy rozumieć jako proces scalania dwóch posortowanych wycinków tablicy w jeden. Algorytm scalania zostanie podany nieco dalej, zauważmy tylko, że bazuje on na pierwotnym uporządkowaniu wycinków. #kst procedury Sortuj jest podany poniżej. procedure Sortujfnl,n2: integer; var tab: tablica); ( Procedura rekurencyjnego sortowania przez ł#czenie ) var polowa: integer; begin polowa := (nl + n2) diw#2; ( wy#-naćzenie`środkowego indeksu ) if nl C polowa then (jeśli lewy wycinek zawiera wi gcej ni ż dwa el ementy ) Sortuj Cnl, pol owa. tab ) ; ( sortuj 1 ewy wyci nek ) if pol owa + 1 C n2 then ( jeśl i prawy wyci nek zawi era wi gcej ni ż dwa el ementy ) Sortuj(polowa+l,n2,tab); ( sortuj prawy wycinek ) -123 - Nauka programowania... sortowania szybkiego. Ta wersja algorytmu wymaga użycia stosu (patrz rozdz.l2 ). Przy podziale tablicy na dwie części lewa częśe jest sortowana bezpośrednio, a żądanie posortowania prawej części zapamiętuje się na stosie. Po zakońezeniu sortowania lewych części pobiera sig żądanie z wierzchołka stosu. Czynności te wykonuje się tak długo, aż stos będzie pusty. A oto algorytm zapisany w pseudo-kodzie. Algorytm 9.4. wpisz na stos żqdanie posortowania całej tablicy powtarzaj powtarzaj pobierz ze stosu żQdanie posorfowania wycinka tablicy określonego prcez zmienne lewy i prawy przestaw elementy wycinka, tak aby otrzymać podział tego wycinka na dwie części: pierwszq zawierajqcq elementy mniejsze od wyróżnionego elementu i drugQ zawierajqcQ elementy większe od wyróżnionego elementu jeśli prawa część wycinka nie jest pusta to zapamiętaj na stosie żqdanie posortowania prawej części wycinka zmiennej prawy przypisz wartość określajQcq ostatni element lewej części wycinka aż lewy >= prawy aż stos jest pusty Podamy teraz nierekurencyjną procedurę realizującą szybkie sortowanie tablie wraz z programem jej testowania. Program 9.6 program Test; ( Program testowania nierekurencyjnej wersji sortowania szybkiego ) const nmax =100 ; ( ma ksymal ny rozmi ar tabl i cy 5 type tablica = array Cl..nmax] ofinteger; var n, ( rozmiar tablicy ) i : C zmi enna pomocni cza ) integer; -120 - 9. Rekurencj a a : tabl i ca ; f sortowana tabl i ca ) procedure Szybkie nier Cvara:tablica;lewy,prawy:integer); f Procedura sortuj#ca tablicę bez wykorzystania rekurencji) eon5t maxstos = 30 ; f maksymal na 1 i czba el ementów na stosi e ) var i, f zmi enna przebi egaj aca 1 ew# czgść tabl i cy ) j, f zmi enna przebi egaj dca prawa czgść tabl i cy ) x, { środkowy element ) pom: f zmi enna pomocni cza do zami any el ementów ) integer; wskstos: 0. .maxstos; f wskaźni k stosu ) stos: array[l..maxstos,1..2) ofinteger; begin f wpi sani e na stos żddani a posortowani a ca#ej tabl i cy ) wskstos :=1; stosCl,l] :=1; stosCl 2] :=n; repeat f pobrani e ze stosu ż#dani a posortowani a wyci nka tabl i cy ) lewy := stos Cwskstos,l]; prawy := stos[wskstos,2]; wskstos := wskstos - 1; repeat f przestawienie elementów wycinka określonego przez zmi enne 1 ewy i prawy ) i :=lewy; j := prawy; . f wybranie środkowego elementu wycinka ; x := a[Clewy + prawy) div 2]; repeat whi 1 e a [ i ] C x do i:=i+1; while x C a[j] do j :=j - 1; -121- Nauka programowania... której występują elementy mniejsze bądź równe 6 i drugą (od elementu piątego do siódmego), w której występują elementy wigksze od 6. Po podzieleniu tablicy na dwie czgści wykonujemy nastgpnie t#n sam algorytm dla każdej z nich, tak długo aż otrzymamy czgści jednoelementowe. Dla omawianej tablicy otrzymamy dwie nastgpujące czgści 5 1 4 6 oraz 8 9 7, dla których dalej wykonujemy podany algorytm. Obecnie przedstawimy rekurencyjną wersjg szybkiego sortowania tablicy Dla zachowania zgodności z algorytmem 9.3 należałoby dodać żądanie posortowania lewej i prawej części tablicy A oto program testujący rekurencyjną wersję szybkiego sortowania. Program 9.5 program Test; ( Program testuj#cy rekurencyjnd wersję szybkiego sortowania tablicy ) const nmax =100 ; C maksymal ny rozmi ar tabl i cy ) type tablica = array Cl..nmax] ofinteger; var n, ( rozmi ar tabl i cy ) i : ( zmi enna pomocni cza ) integer; a:tablica; procedure Szybkie Cvara:tablica;lewy, prawy:integer); C Rekure#cyjna procedura szybkiego sortowania ) ( lewy - lewy kraniec sortowanego wycinka, prawy - prawy krani ec sortowanego wyci nka ) var i, ( zmi enna przebi egaj#ca 1 ewd czgść tabl i cy ) j, ( zmi enna przebi egaj#ca praw# część tabl i cy ) x, ( element środkowy ) pom : C zmi enna pomocni cza do zami any el ementów ) integer; begin i : =1 ewy ; j := prawy; f wybranie środkowego elementu ) -118 - 8. ftekurencja x := aCClewy + prawy ) div 2 ]; repeat while a Ci ] C x do i:=i+1; whi 1 e x C a Cj ] do j :#j - 1; if i C= j then begin ( zami ana wybranych el ementów ) pom := a Ci ) ; a Ci ] := a Cj ] ; a Cj ] := pom; i:=i+1; j := j - 1 end unti 1 i > j ; ( aż przej rzel i śmy 1 ewą i prawą częśE tabl i cy ) f wywolanie procedury dla lewej części ) if lewy C j then SzybkieCa,lewy,j); l wywołanie procedury dla prawej czgści ) if i C prawy then S2ybkieCa,i,prawy) end; begin writeln C'Podaj rozmiar tablicy'); readln Cn); writeln C'Podaj elementy tablicy'); for i :=1 to n do ů # read Ca Ci)); Szybkie Ca,l,n); end writeln C'Tablica posortowana:'); fori:=ltondo writelnCaCi]); Obecnie dla porównania podamy nierekurencyjną wersję algorytmu -119 - Nauka programowania... 5 1 20 17 12 3 4 16 11 2 7 18 3 21 24 19 4 13 2 10 15 6 23 8 1 25 22 9 14 5 1 2 3 4 5 ftys. 9.12. Wygenerowane wyniki dla szachownicy o rozmiarach 5 * 5 9.3. Algorytmy sortowania W niniejszym podrozdziale podamy dwa nowoczesne algorytmy sortowania tablic. Rozważymy tak zwane sortowanie szybkie i sortowanie przez łączenie. Sortowanie szybkie charakteryzuje sig najlepszym oczekiwanym czasem sortowania. Jego wadą jest powolność działania, w przypadku szczególnym tzn., gdy tablica zawiera takie same elementy. Mimo to jest ona najlepszą ze znanych obecnie metod sortowania tablic. Drugą z kolei jest metoda sortowania przez łączenie, której mankamentem jest konieczność wykorzystania tablicy o 2 * n elementach w celu posortowania tablicy o n elementach. Przykład W przykładzie rozważymy sortowanie szybkie. Jak już wyżej wspomniano, metoda ta pod wzglgdem oczekiwanego czasu działania jest najlepszą z dotychczas znanych metod. Oczekiwany czas działania jest to średni czas otrzymany przy sortowaniu dużej liczby tablic zawierających elementy ustawione w sposób przypadkowy. Algorytm sortowania szybkiego w sposób jak najbardziej ogólny w postaci opisu słownego można przedstawić następująco. Krok l. Wybierz dowolny element x z tablicy. Krok 2. Podziel tablicę na dwie spójne części: część lewostronną T1 z elementami mniejszymi niż x oraz część prawostronną T2 z elementami większymi bądź równymi x. Tl Powyższy algorytm zilustrujemy na przykładzie tablicy 7 1 8 6 4 9 5 Element środkowy tablicy wyznaczymy przy pomocy instrukcji: + raw ) di # x :=a[Clewy p y # ]; W naszym przypadku element ten bgdzie równy 6. Nnastgpnie zostanie wykonany nastgpujący ciąg zamian: i J zamieniane elementy tablica po zamianie 1 7 7H5 5186497 3 5 8H4 5146897 5 4 i Po wykonaniu tylko dwóch zamian uzyśkaliśmy tablicg, w której można wyróżnić dwie czgści: pierwszą (od elementu pierwszego do czwartego), w -117 - Nauka programowania... if not okwewn then f usuni ęcie zaznaczeni a ruchu ) szach[wspnastl,wspnast2] := 0 end el se okwewn := true end unti 1 okwewn or Cnr = 8) ; ( aż ruch zostal wykonany poprawni e 1 ub nie ma wigcej możliwych ruchów ) ok := okwewn ( wyprowadzenie na zewnatrz wartości kontrolnej ) end; begin writeln C'Podaj rozmiar szachownicy'); readln Cn); writeln C'Podaj punkty pocz#tkowe'); readln Cpoczl,pocz2); if C not Cn in [1. .nmax])) or C not Cpoczl in [1. .n])) or C not Cpocz2 in [l..n])) then begin writeln C'Błąd danych'); halt end; C wy#naczeni e różni c współ rzgdnych ) ruchy Cl,l] : -2; ruchy[1,2] : 1; ruchy[2,1] : -1; ruchy[2,2] := 2; ruchy[3,1] : 1; ruchy[3,2) := 2; . ` ruchy.C4,1) := 2; ruchy[4,2] : 1; ruchyCS,1) := 2; ruchyC5,2] : -1; ruehy[6,1) : 1; ruchy[6,2] : -2; ruchy[7,1) : -1; ruchy C7,2] : -2; ruchy[8,1] : -2; ruchy[8,2] : -1; ( przygotowani e tabl i cy ) fori:=ltondo for j :=1 to n do SzachCi,j] := 0; -114 - 8. R#ehurencja szach Cpoczl,poez2] := 1; Ruch C2,poczl,pocz2,ok); f wyznaczanie ruchów ) if ok then C wydruk rozwiazania ) for i :=1 to n do begi n for j :=1 to n do write Cszach Ci,j]:4); writeln end el se writeln C'Brak rozwi#zania') end. Na rys. 9.12 są podane wyniki wygenerowane przez program dla szachownicy o rozmiarach 5 * 5, a na rys. 9.11 wygenerowane wyniki dla rozmiarów 8 * 8. W obu przypadkach punktem startAwym jest punkt o współrzędnych 1,1. 8 1 38 55 34 3 36 19 22 7 54 47 2 37 20 23 4 17 6 39 56 33 46 35 18 21 10 5 48 53 40 57 24 11 16 5 4 59 32 45 52 41 26 9 12 3 44 49 58 25 62 15 6 27 2 31 60 51 42 29 8 13 64 1 50 43= #30 61: "' 14 ń3 28 7 1 2 3 4 5 6 7 8 ftys. 8.11. Wygenerowane wyniki dla szachownicy o rozmiarach 8 * 8. Rozwiązanie dla szachownicy 8 * 8 generowane było jednak długo, bo około 50 minut na komputerze IBM PC/AT ( 12 minut na komput#rze IBM PC/386 DX ). -115 - Nauka programowania... nie czy pole o tych współrzgdnych ma wartość zero, co oznacza, że dane pole nie było odwiedzone. Instrukcji tych nie można połączyć, ponieważ w przypadku gdy współrzędne nie leżą wewnątrz tablicy, to zmienna szach[wspnastl,wspnast2) jest nieokreślona. Zdanie "są jeszcze wolne pola" zapiszemy w postaci iCn*n; Oznacza to, że liczba wykonanych ruchów jest mniejsza niż liczba pól szachownicy. Zdanie "zaznacz wykonanie ruchu" sprecyzujemy jako szach[wspnastl,wspnast2] :=i; natomiast zdanie "skasuj zapis ostatniego ruchu" zapiszemy jako szach[wspnastl,wspnast2] := 0; Należy jeszcze wprowadzić zmienną lokalną o nazwie okwewn w celu sprawdzenia, czy udało się wykonać następny ruch. Na koniec zdefniujemy sposób wyznaczenia współrzgdnych wspnastl oraz wspnast2 w zależności od tego, który ruch spośród ośmiu możliwych jest sprawdzany W tym celu określimy globalną tablicę o nazwie ruchy, zawierającą różnice współrzędnych dla każdego spośród ośmiu ruchów. Tablica ta ma postać: ruchy[1,1] : -2; ruchy[1,2] : 1; ruchy[2,1] : -1; ruchy[2,2] := 2; ruchy[3.1] : 1; ruchy[3,2] := 2; ruchy[4,1] :- 2; ruchy[4,2] : 1; ruchy[5,1] : 2; ruchy[5,2] : -1; ruchy[6.1] : 1; ruchy[6.2] : -2; ruchy[7,1] : -1; ruchy[7,2] : -2; ruchy[8,1] : -2; ruchy[8,2] : -1; Na przykład aby wykonać piąty z kolei ruch dla skoczka stojącego na polu o współrzgdnych 2,3, należy zwigkszyć współrzędną odpowiadającą :-m#merowi wiersza o 2 (ruchy[5,1]=2), a współrzędną odpowiadającą numerowi kolumny zmniejszyć o jeden (ruchy[5,2]=-1), a zatem musimy przestawić skoczka do pola o współrzędnych 4,2. Program znajdowania drogi skoczka jest podany poniżej. Program 9.4 program Skoczek; ( Program znajdowania drogi skoczka na uogólnionej szachownicy ; const nmax = 20; ( maksymalny rozmiar szachownicy ; -112 - 9. Rekurencja var i, j, { zmi enne pomocni cze ) n, { rozmiar szachownicy ) poczl,pocz2: { pocz#tkowe ustawienie skoczka ) integer; ok : bool ean ; { zmi enna kontro na ruchy: array Cl..8.1..2] ofinteger; { różnice wspólrzędnych ) szach: array Cl..nmax,l..nmax] ofinteger; { szachownica ) procedure Ruchfi,wspl,wsp2:integer; var ok: boolean); { Rekurencyjna procedura wyznaczania nastgpnego ruchu ) { i - numer ruchu, wspl.wsp2 - aktualne wspólrzędne skoczka, ok - zmi enna kontrol na ) var okwewn : bool ean ; nr, f kol ejny ruch spośród ośmi u możl i wych ruchbw ) wspnastl, wspnast2: { wspblrzgdne nastgpnego ruchu ) integer; begin nr := 0; { przygotowanie wyboru ruchbw ) repeat nr := nr + 1; { wybranie następnego ruchu spośród ośmi u możl iwych ruchbw ) okwewn := fal se ; f ustawi eni e wartości zmi ennej kontrolnej ) { ustalenie wspblrzgdnych nastgpnego ruchu ) wspnastl :=wspl + ruchyCnr,l); wspnast2 := wsp2 + ruchy[nr,2] ; if Cwspnastl in C1, :rr31 and Cwspnast2 inrCl. .n]) then if szachCwspnastl,wspnast2] = 0 then { ruch dopuszczalny ) begin { zaznaczeni e ustawi eni a następnego ruchu ) szach[wspnastl,wspnast2] := i; if i C n * n then { jeśli s# wolne pola ) begin { rekurencyjne wywolanie procedury dla następnego ruchu ) Ruch Ci+l,wspnastl,wspnast2,okwewn); -113 - Nauka programowania... i wykonujemy go teraz do punktu o współrzgdnych 2,1. Kilka nastgpnych posunięć pokazuje szachownica przedstawiona na rys. 9.9. 1 14 5 2 2 4 1 8 11 3 13 10 3 6 4 7 12 9 1 2 3 4 Rys. 8.9. Kilka ruchów skoczka na szachownicy po wykonaniu powrotu Dla ruchu o numerze 14 nie można wykonać żadnego nastgpnego posunigcia, musimy sig zatem cofnąć do takiego położenia, z którego można wykonać ruch, który dotychczas nie był wykonywany Analizując szachownicę dochodzimy do wniosku, że należy się cofnąć do ruchu o numerze 11 i ruch 12 zamiast wykonać do punktu o współrzędnych 4,3 wykonać do punktu o współrzgdnych 1,2. Sytuację tg ilustruje rys. 9.10. 1 12 5 2 2 4 1 8 11 3 10 3 6 4 7 9 1 2 3 4 Rys. #.10. Sytuacja na szachownicy po wykonaniu kolejnego powrotu Przedstawiony algorytm zrealizujemy przy pomocy procedury rekurencyjnej. Unikamy w ten sposób jawnego pamigtania, który ruch spośród ośrt#iu mo#liwych został wykonany Na przykład w sytuacji podanej na rys. 9.8 trzeba pamigtać dane: numer ruchu startowego numer wykonauego ruchu 1 1 2 5 3 5 W przypadku konieczności powrotu do ruchu o numerze 3 bgdziemy próbowali wykonać posunigcie o numerze wyższym niż 5 spośród ośmiu możliwych do wykonania ruchów. W tym przypadku zostanie wykonany ruch o numerze 6. -110 - 9. Rekurencja Ogólna wersja algorytmu wykonywania nastgpnego ruchu wykorzystanego w procedurze o nazwie Ruch jest przedstawiona poniżej. Algorytm 8.2. zdefiniuj ustawienie poczĄtkowe powtarzaj wybierz następny ruch jeśli ruch jest możliwy to zaznacz wykonanie ruchu jeśli sq jeszcze wolne pola to wykonaj rekurencyjnie procedurę dla następnego ruchu jeśli ruch nie jest możliwy to skasuj zapis ostatniego ruchu aż ruch został wykonany poprawnie lub nie ma więcej możliwych ruchów Podobnie jak w problemie ustawienia ośmiu hetmanów na szachownicy musimy teraz określić strukturg danych, która będzie dalej wykorzystywana. Szachownicg bgdzie reprezentować tablica o nazwie szach. Maksymalny rozmiar tej tablicy określimy w stałej nmax, natomiast aktualny rozmiar tablicy będziemy wczytywać do zmiennej n. Kolejno wykonywane posunigcia będą zapisywane w postaci liczb całkowitych. Jeśli element (pole) tablicy ma wartość zero oznacza to, że pole to nie było jeszcze odwiedzone. Parametry formalne procedury Ruch powinny być nastgpujące: procedure Ruch Ci,wspl,wsp2:integer; var ok: boolean); gdzie i oznacza numer ostatnio wykonanego ruchu, wspl oraz wsp2 są współrzędnymi tego ruchu, zmienna ok określa czy udało sig wykonać ruch. Możemy teraz przystąpić do precyzowania zdań występujących w algorytmie 9.2. Zdanie "rueh jest możliwy" zapiszemy w postaci if Cwspnastl in [1. .n)) and Cwspnast2 in Cl..n]) then if szach[wspnastl,wspnast2] = 0 then gdzie wspnastl oraz wspnast2 są wspóhzgdnymi następnego ruchu. Powyższe instrukcje sprawdzają, czy współrzgdne leżą wewnątrz tablicy i nastgp -111- Nauka programowania... 1 2 3 4 5 6 7 8 Rys. 9.6. Ustawienie ośmiu hetmanów na szachownicy Spróbujmy jeszcze prześledzić kilka rekurencyjnych wywołań procedury Ustaw. Ustawl 1,ok) i =1 # Ustaw(2,ok) i = 3 # Ustaw(3,ok) i = 5 # Ustaw(4,ok) i = 2 # UstawC5,ok) i = 4 # Ustaw(6,ok) ok = false { powrót } i = 8 # Ustaw(6,ok) . ok = false { powrót } i = 7 # Ustaw(5,ok) i=2#... "W powyższym schemacie na przykład wywołanie Ustaw(3,ok) oznacza vvywołanie procedury Ustaw dla trzeciej kolumny, a zmienna i oznacza numer wiersza, w którym jest wstawiany hetman. Przykład W przykładzie przedstawimy znany szeroko w literaturze problem znalezienia takiej drogi skoczka szachowego, aby każde pole szachownicy było odwiedzone przez niego dokładnie raz. Podobnie jak w poprzednim przykładzie do rozwiązanie tego problemu -108 - 9. Rekurencja wykorzystamy algorytm powrotu. Na wstępie określimy kolejność wykonywania ruchów skoczkiem. W każdym etapie obiegania szachownicy próba wykonania ruchu będzie zgodna z tą kolejnością, która może być dowolna pod warunkiem, że zawsze będzie taka sama. Przyjętą przez nas kolejność definiuje tablica przedstawiona na rys. 9.7. Rys. 9.7. Kolejność wykonywania ruchów skoczkiem Rozważmy teraz przykładową szachownicg o rozmiarach 4 * 4 i położenie punktu początkowego 2,2. Spróbujmy wykonać kilka kroków algorytmu powrotu. Kolejne ruchy wykonujemy zgodnie z przyjętą kolejnością (zawsze zgodnie z ruchem wskazówek zegara poczynając od ruchu zaznaczonego na rys. 9.7 cyfrą 1). W przypadku gdy danego posunigcia nie da sig wykonać, próbujemy wykonać kolejny możliwy do wykonania ruch z danego punktu. Poszczególne ruchy zaznaczamy kolejnymi liczbami całkowitymi. 1 2 4 1 2 3 4 ftys. 9.8. Kilka ruchów skoczka na szachownicy Zauważmy, że w sytuacji podanej na rys. 9.8. z punktu o współrzędnych 4,1 nie można wykonać żadnego ruchu. Należy zatem wykonać podstawowy krok algorytmu powrotu i cofnąć sig do takiego położenia, z którego można kontynuować ustawianie. W naszym przypadku usuwamy ruch o numerze 4 -109 - Nauha programowania... j, k : i nteger ; ( zmi enne pomocni cze ) ok : bool ean ; ( zmi enna kontrol na ) wi ersz : array C 1. . 8) of bool ean ; ( zaj ętość wi ersza ) prawa: arrayC2. .16] of boolean; C zajętość przek#tnej prawo w skos) 1 ewa : arrayC -7. . 7] of bool ean ; f zaj ętość przek#tnej 1 ewo w s kos ) hetman: arrayCl. .8) of integer; f położenie hetmanów w kolumnach) procedure Ustaw Cj:integer; var ok: boolean); ( Rekurencyjna procedura ustawiania hetmana ) var i:integer; begin i := 0; ( ustawienie pocz#tkowe ) repeat i:=i+1; ok := false; ifwierszCi] andprawaCi+j) andlewaCi-j) then begin ( zapami gtani e ustawi eni a hetmana ) hetmanCj] := i ; wiersz Ci] := false: prawaCi+j] := false; lewa Ci-j] := false; if j C 8 then C jeśl i s# jeszcze kol umny ) begin ( rekurencyjne wywołanie procedury dla następnej kolumny ) Ustawfj + 1, ok ) ; i f not ok then begin ( usuni gci e zaznaczeni a hetmana ) wiersz Ci] := true; prawa Ci+j ] := true; lewaCi-j] :=true end end else ok := true f znal ezi ono ustawi eni e ośmi u hetmanów ) en d unti 1 ok or C i = 8 ) ( aż znal ezi ono ustawi eni e 1 ub koni ec wi erszy ) -106 - 9. Rekurencja end; procedure Rozwiazanie; ( Procedura drukowania rozwiązania ) var i,j:integer; begin writelnC'#-T-T#T-T-T-T#T-# ); forj := 8 downto 1 do C dl a każdego wi ersza ) begin write Cj:3.'# '); for i :=1 to 8 do i f hetman [j ]=i then write C'H','# '1 else writeC".'# '); writeln; if j C> 1 then writelnC' I--+-+ end; writelnC ' # - 1 - 1 - 1 1 - 1 # # - 1 - # ' ) ; writelnC' 12345678') end; begin C ustawienie warunkbw początkowyeh ) for k :=1 to 8 do wiersz[k] := true; , for k := 2 to 16 do prawa[k] := true; for k := -7 to 7 do lewaCk] := true; Ustaw Cl,ok); C ustawian Te hetmanńw- # if ok then Rozwiazanie el se writeln C'Brak rozwidzań') end. Na rys. 9.6 przedstawiono ustawienie hetmanów na szachownicy odpowiadające wygenerowanemu rozwiązaniu. -107 - Nauka programowania... hetman: array[1..8] of integer; 1 2 3 4 5 6 7 8 R,ys. 9.3. Pola kontrolowane przez pojedynczego hetmana Rys. 9.4 podaje przykładowe zawartości tych tablic w trakcie wykonywania algorytmu, a na rys. 9.5. są zaznaczone pola kontrolowane przez hetmany, o ktńrych informacja jest zawarta w tych tablicach. wiersz F F F F F T T TI prawa# - lewa hetman 1 3 5 2 4 ftys. 9.4. Przykładowe zawartości tablic hetman, wiersz, prawa, lewa -104 - 9. Rekurencja Mając określoną strukturę danych można teraz sprecyzować zdania pseudo-kodu. Zdanie pseudo-kodu "zaznacz ustawienie hetmana" sprecyzujemy w sposób następujący: hetman[j ] := i ; wi ersz[i ] := fal se; prawa Ci+j] := false; lewa Ci-j] := false; Natomiast zdania "usuń ustawienie hetmana" zapiszemy w sposób następujący: wiersz[i] := true; prawa[i+j) := true; lewa Li-j] := true; Warunek czy pozycja jest dobx.a-może być_ vwyrażon# następująco: wiersz[i] and prawa[i+j] andlewa Ci-j] co oznacza, że i-ty wiersz, przekątna prawo w skos o sumie indeksów i+j oraz przekątna lewo w skos o sumie indeksów ij nie znajdują się w polu działania żadnego hetmana. Program 9.3 program Hetmany; ( Program ustawi ani a ośmi u hetmanów na szachowni cy ) var ; i -105 - 1 2 3 4 5 6 7 8 Rys. 9.5. Pola kontrolowane przez hetmany Nauka programowania... 8 3 # 2 1 2 3 4 5 6 7 8 ftys. 8:2. Pozycje pierwszych pięciu hetmanów po wykonaniu powrotu Powyższy algorytm zrealizujemy przy pomocy procedury rekurencyjnej o nazwie Ustaw. Procedura ta próbuje ustawić hetmana w j-tej kolumnie w wierszu nąjniższym. Pozytywne zakończenie próby powoduje wywołanie procedury rekurencyjnej dla kolumny j + 1. W przypadku nieudanej próby ustawienia hetmana w j + 1 kolumnie następuje powrót i usunigcie ostatnio ustawionego hetmana z kolumny j. Procedurę kończy ustawienie hetmana zgodnie z przyjętymi zasadami lub osiągnięcie ostatniej kolumny szachow -102 - 1 2 3 4 5 6 7 8 ftys. 8.1. Pozycje pierwszych pięciu hetmanów 9. Rehurencja nicy. Algorytm zastosowany w t#j procedurze możemy sformułować nastgpuj#co. Algorytm 9.1. przypisz i warfość 0 powtarzaj wybierz następn5l pozycję ( i := i + 1) jeśli pozycja jest dobra to # zaznacz ustawienie hetmana jeśli j < 8 to wywołaj rekurencyjnie opisywanĄ procedurę dla j + 1 jeźli nie powiodło się ustawienie hetmana to usuń zaznaczenie ostatnio ustawionego hetmana aż powiodło się ustawienie hetmana lub nie ma pozycji (i = 8) Obecnie zaprojektujemy strukturg danych wykorzystywaną w programie. Zauważmy nąjpierw, że gdyby pozycje hetmanów przechowywać w tablicy dwuwymiarowej, to sprawdzenie czy dany hetman nie zn#jduje sig w polu bgdącym pod kontrolą innego hetmana, wymagałoby przeglądania tablicy we wszystkich możliwych kierunkach. Oczywiście takie rozwiązanie jest nie do przyjgcia i należy poszukać innego. W książce "Nauka programowania dla początkujących" [20] była podawana zależność na indeksy elementów leżących na przekątnych na prawo w skos i na lewo w skos. Zauważmy, że hetman stojący na pozycji k,l kontroluje przel#ątną prawo w skos, ktńrej indeksy spełniąją zależność i + j = k + 1, przekątną lewo w skos, której indeksy spełniają zależność i - j = k -1 oraz k-ty wiersz oraz 1-tą kolumnę. Ilustruje to rys. 9.3. Struktura danych wykórzystywana##v prograiziie powinna być zatem złożona z trzech tablic zawier#jących informację o tym, czy dany wiersz, przekątna lewo w skos i przekątna prawo w skos są w polu działania danego hetmana (ponieważ każdego hetmana umieszczamy w oddzielnej kolumnie, nie jest potrzebna informacja o kontrolowaniu danej kolumny przez hetmana). Deklaracja tych tablic jest podana poniżej: wiersz: array(1..8] ofboolean; prawa: array[2..16] of boolean; lewa: array[-7..7) of boolean; ' IO3 ' Nauka programowania... 1. readln(plik,linia) - aaaaa 2. Odwroc(plik) 1. readln(plik,linia) - bbbbb 2. Odwroc(plik) 1. readln(plik,linia) - ccccc 2. Odwroc(plik) 1. readln(plik,linia) - ddddd ## ### #V 2. Odwroc(plik) # Koniec pliku ) 3. writeln(linia) - ddddd 3. writeln(linia) - ccccc 3. writeln(linia) - bbbbb 3. writeln(linia) - aaaaa Wczytane linie pliku są pamiętane w zmiennych lokalnych linia lkażda dla poszczególnego wywołania procedury), co powoduje utworzenie stosu tych zmiennych lna wierzchołku stosu znajduje się zmienna o zawartości odpowiadającej czwartemu - ostatniemu - poziomowi wywołania): wartość zmiennej lokalnej linia poziom wywołania ddddd ccccc III bbbbb II aaaaa I Wyprowadzenie wartości zmiennych lokalnych daje w wyniku wydruk linii tekstu w kolejności odwrotnej niż są umieszczone w pliku. Porównując oba przedstawione programy stwierdzamy, że rozwiązanie rekurencyjne jest bardziej przejrzyste i krótsze. W programie rekurencyjnym uniknęliśmy deklaracji tablicy i sprawdzania, czy liczba linii w pliku nie jest większ# niż liczba elementów tablicy. Należy jednak podkreślić, że w programach rekurencyjnych pamięć do przechowywania wartości zmiennych lokalnych jest również potrzebna, mimo iż nie jest ona deklarowana jawnie. ~ ftekurencję należy zatem stosowae z dużą ostrożnością pamiętając, że nie zawsze rozwiązanie rekurencyjne jest lepsze od rozwiązania nierekurencyjnego. Istnieje jednak pewna klasa problemów, w których rozwiązania rekurencyjne są zdecydowanie bardziej eleganckie i prostsze od rozwiązań iteracyjnych. Można powiedzieć, że są to zagadnienia związane przede wszystkim z rekurencyjnymi strukturami danych, które zostaną omówione w rozdziale 12, oraz te problemy, które można rozłożyć na podproblemy takie same jak problem początkowy. Właściwie wykorzystana rekurencja jest potężnym narzędziem pozwalającym na zwarty i jednocześnie przejrzysty zapis skomplikowanych operacji. # OO # 9. ftekurencja W następnych podrozdziałach zilustrujemy kilkoma przykładami wykorzystanie rekurencji. Omówione będą takie problemy, w których rekurencyjne rozwiązanie jest znacznie lepsze niż rozwiązanie iteracyjne. 9.2. Algorytmy z powrotami Algorytmy z powrotami są bardzo czgsto stosowane do rozwiązywania problemów kombinatorycznych, ktflre można sformułować w następujący sposób. Danych jest n uporządkowanych zbiorów Z1,...,Zn. Należy skonstruować wektor A = (a"...,an), gdzie al e Zl,...,an e Z#, który spełnia dane warunki lub ograniczenia. Wektor A tworzy się następująco: kolejno przeszukuje się zbiory Z1,...,Zn zaezynając zawsze od elementu najmniejszego danego zbioru i wykonując powrót do poprzedniego zbioru w przypadku wyczerpania wszystkich elementów aktualnie przeszukiwanego zbioru. Algorytmy z powrotami zilustrujemy dwoma przykładami. Przykład W przykładzie zaprojektujemy i zrealizujemy algorytm ustawiania 8 hetmanów na szachownicy, tak aby żaden z nich nie znajdował się w polu atakowanym przez innego hetmana. Liczba wszystkich możliwych ustawień hetmanów na szachownicy wynosi 8s (przy założeniu, że w każdej kolumnie znajduje się tylko jeden hetman). Rozwiązanie polegające na wygenerowaniu wszystkich możliwych ustawień hetmanów na szachownicy i sprawdzeniu, które z nich spełniają warunki zadania, jest zatem nie do przyjęcia. W celu rozwiązania problemu wykorzystamy algorytm powrotu. Kolejne hetniany będziemy ustawiać na szachownicy poczynając od pierwszej kolumny. Pierwszego hetmana ustawimy w pierwszej kolumnie, drugiego - w drugiej itd. licząc od lewej strony szachownicy do prawej. W ka,#dej kolumniQ pierwszą badaną pozycją będzie najniższa dotychczas nie śprawdzona. Na rys. 9.1. są przedstawione pozycje pierwszych pięciu hetmanów po ustawieniu ich zgodnie z podanymi regułami. W szóstej kolumnie nie można ustawić hetmana, ponieważ wszystkie pola są pod działaniem hetmanów umieszczonych w pierwszych pięciu kolumnach. Należy w tym momencie wykonać powrót i powrócić do kolumny piątej przestawiając stojącego tam hetmana na pozycję wyższą spełniającą warunki zadania. Rys. 9.2. przedstawia pozycje pierwszych pięciu hetmanów po wykonaniu powrotu. Kroki te wykonuje się tak długo, aż zostanie znalezione rozwiązanie lub stwierdzony jego brak. -101- Nauka programowania... tab: array Cl..lmax] of string[80]; Ctablica z liniami tekstu) i, C zmienna pomocnicza 1 n : ( 1 i czba 1 i ni i w pl i ku tekstowym ) integer; begin assign Cplik,'test'); ( przypisanie nazwy ) resetCpl i k) ; C otworzeni e pl i ku ) n :=0; while not eofCplik) do { podczas gdy nie napotkano symbol u końca pl i ku ) begin n:=n+1; ifn # lmax then f jeśli za mała tablica ) begin writeln C'Za mała tablica'); halt end; readlnCplik,tabCn]); ( wczytanie linii tekstu ) end; C wydruk w kolejności odwrotnej ) fori := n downto 1 do Writelnftab Ci]); close Cplik) end. Zauważmy, że powyższy program wymaga zadeklarowania tablicy, -sprawdzeńia, czy liczba linii w pliku nie jest większa od liczby elementńw tablicy oraz wydruk elementów tablicy w kolejności odwrotnej. Spróbujemy teraz napisać wersję rekurencyjną tego programu. Zadanie drukowania linii tekstu w kolejności odwrotnej realizować bgdzie procedura Odwroc. Procedura ta wykonuje tylko następujące operacje: wczytuje kolejną linig tekstu, rekurencyjnie wywołuje samą siebie i drukuje zapamigtaną linig. Pełen tekst programu jest podany poniżej. Program 9.2 program Odwrotny; -98- 8. R#ekurencja f Program drukowani a 1 i ni i tekstu w kol ejności odwrotnej ) var pl i k : text ; f pl i k tekstowy ) procedure Odwroc Cvar plik: text): f Rekurencyjna procedura odwracania kolejności } var 1 i ni a : stri ng[80] ; f 1 i ni a tekstu } begin if not eofCpl i k) then fjeśl i nie napotkano końca pl i ku} begin readlnCplik,linia); f wczytanie linii ) Odwroc Cplik); frekurencyjne wywolanie procedury) writelnClinia): f wydruk linii ) end end; begin assignCplik,'test'): f przypisanienazwy ) reset C pl i k ) ; f otworzeni e pl i ku ) OdwrocCpli k) ; f wydruk w kolejności odwrotnej ) close Cplik) end. Przeanalizujemy teraz działanie programu. Przypuśćmy, że plik zawiera nastgpujące linie: aaaaa bbbbb ' csccc ddddd Instrukcje zawarte w p#edurze wy#nujące, jakąś operacjg ponumerujmy w kolejności od 1 do 8: { 1 } readln(plik,linia); { wczytanie linii } { 2 } Odwroc(plik); { rekurencyjne wywołanie procedury } { 3 } writeln(linia); { wydruk linii } Schemat wywołań rekurencyjnych przedstawiono poniżej (liczbami rzymskimi zaznaczono poziom wywołania rekurencyjnego): -99- Nauka programowania... a) średnią wyników dla wszystkich sportowców w poszczególnych dyscyplinaeh, b) sportowca o najlepszym wyniku w poszczególnych konkurencjach, c) sportowca o nąjgorszym wyniku w poszczególnych konkurencjach. 3. Rozszerzyć przykład ilustrujący przechowywanie informacji o pracownikach tak, aby można było uzyskiwać nastgpujące informacje: a) liczbg pracowników znających trzy i wigcej języków obcych oraz ich nazwiska, b) liczbę pracowników znających dwa języki obce oraz ich nazwiska, c) liczbę pracowników znających tylko jeden język oraz ich nazwiska. 4. Wydrukować podstawowe informacje o pracowniku według klucza, którym bgdzie nazwisko pracownika. -96- Rozdział REKURENC#TA 9.1. Wprowadzenie Rekurencja polega na wywoływaniu danego podprogramu w jego treści. Rekurencja może być bezpośrednia i pośrednia. Rekurencja bezpośrednia zachodzi wtedy, gdy tekst danego podprogramu zawiera odwołanie do samego siebie. Natomiast z rekurencją pośrednią mamy do czynienia wtedy, gdy tekst podprogramu zawiera wywołanie podprogramu, w wyniku działania którego następuje wywołanie danego podprogramu. Rekurencja pośrednia nie będzie omawiana w niniejszej książce. Zauważmy tylko, że przy stosowaniu rekurencji pośredniej jest niezbędna dyrektywa zapowiedzi podprogramu forward, która jest dokładnie omówiona w pracach [ 3,14 ]. Pojęcie rekurencji wyjaśnimy na przykładzie podprogramu drukowania w odwrotnej kolejności linii tekstu umieszcąonego w pliku. Dla porównania najpierw podamy program i#eracyjny wyk#ńujący tó zadanie. Program 9.1 program Odwrotny; f Program drukowani a 1 i ni i pl i ku tekstowego w kol ejności odwrotnej ) const lmax=100; C maksymalny rozmiar tablicy ) var pl i k : text ; C pl i k tekstowy ) linia: string[80];f linia tekstu ) -97- Nauka programowania... Algorytm 8.5. wczytaj imię i nazwisko zawodnika wczytaj wyniki zawodnika oblicz wartość średniĄ A oto treść procedury procedure Czyt Obl C var zaw: zawodni k) ; ( Procedura wczytywani a danych dl a jednego zawodni ka i obl i czani a średni ej ) var i:integer; suma: real ; begin with zaw, nazw do C powidzanie identyfi katorbw p61 z rekordem zaw i podrekordem nazw ) begin wri tel n C ' Podaj pi erwsze imi ę, drugi e i mi ę i nazwi sko ' ) ; readln Cimiepier,imiedrug,nazwisko); writeln C'Podaj wyniki zawodnika'); suma :=0; fori :=1 to liczbaprob do Cdla każdego wyniku) begin wri tel n C ' Podaj wyni k ', i, ' zawodni ka ' ) ; readln Cwyniki[i]); suma := 5uma + wyni ki Ci ] # end ; srednia := suma/liczbaprob end end; Algorytm wykorzystany w procedurze Srednia jest nastgpujący: Algorytm 8.6. dla każdego rekordu wykonuj jeśli aktualna warfość średnia jest większa od dotychczas wyznaczonej wartości maksymalnej to zapamiętaj nowq warfość maksymaln5l i numer rekordu wydrukuj nazwisko zawodnika z zapamiętanego rekordu l#eść procedury jest podana poniżej. -94- 8. R,ekordy procedure Srednia; ( Procedura obliczania maksymalnej wartości średniej ) var nr,i:integer; max: real; begin max := 0; for i :=1 to n do C dl a każdego rekordu ) with daneCi ) do ( powiazanie identyfikatorów pbl z rekordem dane Ci] ) i f s redn i a # max then begin nr := i; max := srednia end; wi th dane Cnr], nazw do C powi dzani e i dentyfi katordw pbl z rekordem daneCnr] i podrekordem nazw ) writeln C'Zawodnik ',imiepier,imiedrug,nazwisko. ' maksymaln# średnid równ#: ',max:7:2); readln end; 8.4. Zadania 1.W pliku zapamigtujemy rekordy zawierające ńastępujące informacje: nazwisko ucznia, jego imig oraz uzyskaną średnią. Po wczytaniu pewnego zakresu należy wydrukować: a) nazwiska uczniów, którz##uzyskali ś#ednią większą niż prawy kraniec podanego zakresu, # b) nazwiska uczniów, których średnia zawiera się w podanym zakresie, c) nazwiska uczniów, których średnia jest poniżej lewego krańca podanego zakresu. 2.W pliku zapamigtujemy rekordy zawierające następujące informacje: nazwisko, imig, data urodzenia oraz wyniki uzyskane w czterech konkurencjach lekkoatletycznych: bieg na 100 m, skok w dal, skok II wzwyż, skok o tyczce. Zaprojektować system umożliwiający aktualizacjg danych oraz wyznaczanie nastgpującej informacji: -95- Nauka programowania... dur oraz program główny są przedstawione poniżej, natomiast algorytmy i treść procedur Czyt Obl oraz Srednia są podane w dalszym ciągu przykładu. Program 8.8 program Baza#zawodn; uses Crt: const 1 i czbaprob = 5 ; type tabwyn = array Cl..liczbaprob] of real; ident = record imiepier, imiedrug, nazwisko: string[20] end: zawodn i k = record nazw:ident; wyni ki : tabwyn ; srednia: real end; const n#ma x =100 ; var dane: array[l..n max] ofzawodnik; baza : fi 1 e of zawodn i k ; - n : i nteger ; koniec: boolean; procedure Zapisz Cn:integer); C Procedura zapisywania zawartości tablicy na dysk ) ( Treść procedury jest podana w poprzednim przykładzie ) begin end: procedure0dczytaj Cvarn:integer); ( Procedura odczytywani a zawartości pl i ku do tabl i cy ) -92- 8. Rekordy ( Treść procedury jest podana w poprzednim przykładzie ) begin end; function Menu: integer; ( Funkcja tworzenia menu systemu ) ( Podstawowa treść procedury jest podana w poprzednim przykładzie ) begin end; procedure Czyt Obl Cvar zaw: zawodni k) ; ( Procedura wczytywania danych dla jednego zawodnika i obl i czani a średni ej ) begin end; procedure Srednia; ( Procedura obliczania maksymalnej wartości średniej ; begin end; begin Odczytaj Cn); koniec := false; repeat case Menu of 1: ifnCn maxthen begin n:=n+1; Czyt Obl Cdane Cn])# end; 2: Srednia; 0 : begin Zapi sz f-n#) # koniec := true end end unti 1 koni ec ; end. j Możemy teraz przystąpić do zaprojektowania procedury Czyt Obl wczytującej dane i wyznaczającej wartość średnią. Algorytm wykorzystany w tej procedurze jest następujący: -93- Nauka programowania... repeat writeln(tekst); readln Cliczba); until IoResult = 0 end; Przypomnijmy jeszcze, że nąjpierw musi być podana w programie dyrektywa I- w postaci tekstu ($I-}. Instrukcja repeat będzie wykonywana tak długo, aż funkcja IOFtesult() poda wartość zero, co oznacza, że operacja wczytywania danych zakończyła sig poprawnie. Procedura Czytąj z poprzedniego przykładu zabezpieczona przed błędnym wpisywaniem danych jest podana poniżej (w programie musi być podany tekst ($I-} oraz treść procedury Czytąj liczbe). procedure Czytaj Cvarprac: pracownik); begin C1 rScr ; with prac,nazw,urodz,adres,poziom,obce do begin writeln C'Podaj pierwszeimię:'); readln Cimiepier); writelnC 'Podaj drugie imię: ' ); readln Cimiedrug); writeln C'Podaj nazwisko:'); readln(nazwisko); Czytaj#liczbel'Podaj dzień urodzenia',dzien); Czytaj#liczbe C'Podaj miesi#c urodzenia',miesiac); , Czytaj#liczbe C'Podaj rok urodzenia',rok); writeln C'Podaj miejsce urodzenia:'); readln Cmiejsce); Czytaj#liczbe C'Podaj kod',kod); ~ : writeln C'Podaj miejscowość:'); readln Cmiejscowosc); writeln C'Podaj ulicę:'); read Culica); Czytaj#liczbe C'Podaj numer',numer); Czytaj#liczbe C'Podaj numer mieszkania', mieszkanie); Czytaj#liczbe C'Podaj numer telefonu',telefon); writelnC'Czy zna jgzyk angielski '); readln Cangielski); -90- 8. Rekordy writeln C'Czy zna jezyk rosyjski'); readln Crosyjski); writelnC 'Czy zna jezyk niemiecki ' ) ; readlnCniemiecki ); writelnC 'Czy zna jezyk francuski ' ) ; readln Cfrancuski); writeln C'Podaj wykształcenie:'); readln Cwyksztalcenie); writeln C'Podaj stanowisko:'); readln Cstanowisko) end end; Na zakończenie zilustrujemy wykorzystanie tablicy jako pola rekordu. Przykład W przykładzie zaprojektujemy elementy bazy danych przechowującej wyniki uzyskane na zawodach przez poszczególnych sportowców. Z uzyskanych wyników jest wyciągana średnia, która jest również zapamigtywana w bazie danych. Syst#m umożliwia wyszukanie sportowca o największej średniej. Modyfkację systemu tak, aby wykonywał więcej operacji zostawiamy jako ćwiczenie Czytelnikowi. Informację o startach jednego sportowca zapamiętamy w tablicy, która będzie polem rekordu zawier#jącego wszystkie informacje o danym sportowcu. ftekordy umieścimy w tablicy, aby można było wygodnie operować posiadaną informacją. Struktura wykorzystywanego rekordu jest następująca: zawodnik nazw wynlki # srednia imiepier ir#ledrug gdzie zawodnik jest rekordem, a wyniki są tablicą przechowująca wyniki sportowe. W projektowanym programie wykorzystamy część programu zamieszczonego w poprzednim przykładzie. W t#n sposób zilustrujemy możliwość modyfikacji istniejącego programu do różnych celów. Wykorzystamy następujące procedury: Zapisz, Odczytąj i funkcję Menu(). Funkcja Menu() powinna być nieco zmieniona tak, aby uwzględniała inne opcje systemu. Definicja struktury danych zastosowanej w programie, nagłówki proce - 91- Nauka programowania... end; readln Cwyksztalcenie); writeln C'Podaj stanowisko:'); readln Cstanowisko) end procedure Wyswietl Cprac:pracownik); ( Procedura wyświetlania informacji o jednym pracowniku ) begin f powiązanie identyfikatorów pól ze wszystkimi polami rekordu prac) with prac,nazw,urodz,adres,poziom,obce do begin ClrScr; writeln C'Pierwszeimię. ',imiepier); writeln C'Drugie imig . ',imiedrug); writeln C'Nazwisko . ',nazwisko); writeln; writeln C'Miejsce urodzenia: ',miejsce); writeln C'Data urodzenia. ,dzien,'/',miesiac,'/',rok); wri tel n ; writeln C'Miejscowość zamieszkania: ', miejscowosc); wri tel n C ' Kod . ', kod ) ; # writelnC'Ulica . ',ulica); writeln C'Numer . ',numer); writeln C'Numer mieszkania : ',mieszkanie); wri tel n C ' Numer tel efon u. ', tel efon ) ; # wri tel n ; wri tel n C ' angi el ski. ', angi el ski ) ; writeln C' rosyjski. ',rosyjski); wri tel n C ' ni emi ecki. ',ni emi ecki ) ; writelnC ' francuski. ',francuski ); writeln; writeln C'Wyksztatcenie: ',wyksztaleenie); writeln C'Stanowisko: ',stanowisko); 8. Rekordy writeln; writeln C'Naciśnij klawisz ENTER') end; readln end; W ostatnim przykładzie wystąpił dość istotny problem związany ze wczytywaniem danych, którego do tej pory nie analizowaliśmy. Otóż zwróćmy uwagę, że jeżeli pole jest typu tekstowego, to możemy do niego wprowadzać zarówno liczby jak i teksty (liczba będzie traktowana po prostu jako tekst). Natomiast do pola typu numerycznego możemy wprowadzać wyłącznie liczby, omyłkowe wprowadzenie tekstu spowoduje przerwanie pracy programu i wyświetlenie komunikatu o błędzie wykonania. Dla ścisłości trzeba dodać, że to przerwanie pracy programu zależy od ustawienia dyrektyw kompilatora. Dyrektywy kompilatora sterują jego pracą i można je umieszczać w programie w następujący sposób: {$ dyrektywa } Obecnie omówimy tylko dyrektywg I+ oraz I- (W rozdziale 12 jest jeszcze omówiona dyrektywa {$F+}, natomiast wykaz wszystkich dyrektyw kompilatora znajduje się w pracy [14)). Jeżeli w pewnym miejscu programu pojawi sig tekst {$I+} to od tego miejsca, aż do napotkania tekstu {$I-} każdy błąd związany z wczytywaniem danych spowoduje przerwanie pracy programu. Natomiast wprowadzenie dyrektywy {$I-} powoduje, że praca programu nie jest przerywana, natomiast w zmiennej systemowej o nazwie InOutRes zostaje zapamiętany numer błgdu. Jeżeli wartość tej zmiennej jest różna od zera, oznacza to, że wystąpił błąd związany z wc#ytywaniem danych. Warto jeszcze znać funkcję IOResult(), która podaje wartość zmiennej InOutRes i jednocześnie ją zeruje. Zabezpieczenie sig przed,oz#yłkowym.s#pisanięm tekstu do pola typu numerycznego może wyglądać następująco: repeat writeln C'Podaj dzień urodzenia:'); readln Cdzien); unti 1 I O Resul t = 0 ; W celu wykorzystania tej konstrukcji dla dowolnej zmiennej typu integer zapiszemy ją w postaci proeedury. procedure Czytaj#liczbe Ctekst: string; varliczba: integer); begin -89- Nauka prog'ramowania... writelnC ' Wykaz pracowni k6w urodzonych po 1958 roku ' ) ; for i :=1 to n do C dl a każdego pracowni ka ) ( powi#zanie identyfikatorów pól z rekordem daneCi] oraz podrekordami urodz oraz nazw ) with daneCi ], urodz, nazw do begin if rok # 1958 then writeln Cimiepier:8, nazwisko:8) end; readln end; Algorytm wykorzystany w procedurze Wyzsze jest również analogiczny do zastosowanego w procedurze Zamieszk. procedure Wyzsze: ( Pro Cedura znajdowania pracowników z wykształceniem wyższym ) var i:integer; begin C1 rScr ; wri tel n C ' Wykaz pracowni kbw z wyksztalceni em wyższym: ' ) ; for i :=1 to n do C dl a każdego pracowni ka ) f powi#zanie identyfikatorów p61 z rekordem daneCi] oraz podrekordami poziom oraz nazw ) with daneCi ],pozi om,nazw do begin # if wyksztal ceni e = 'wyzsze' then writeln Cimiepier, nazwisko) end; #eadln erid ; ů Na zakończenie podamy treść procedur Czytaj oraz Wyswietl. procedure Czytaj Cvar prac: pracownik); ( Procedura wprowadzania informacji o jednym pracowniku ; begin C1 rScr ; f powi #zani e i dentyfi katorów pól ze wszystki mi pol ami rekordu prac ) with prac,nazw,urodz,adres,poziom,obce do -86- 8. R,ekordy begin writeln C'Podaj pierwszeimię:'); readln Cimiepier); wri tel n C ' Podaj drugi e i mi ę : ' ) ; readln Cimiedrug); writeln C'Podaj nazwisko:'); readln Cnazwisko); writeln C'Podaj dzień urodzenia:'); readln Cdzien); writeln C'Podaj miesidc urodzenia:'); readln Cmiesiac); writeln C'Podaj rok urodzenia:'); readln Crok); writeln C'Podaj miejsce urodzenia:'); readln Cmiejsce); writeln C'Podaj kod:'); readlnfkod); writeln C'Podaj miejscowość:'); readln Cmiejscowosc); writeln C'Podaj ulicę:'); read Culica); writeln C'Podaj numer:'); readln Cnumer); writeln C'Podaj numer mieszkania'); readln Cmieszkanie); , writeln C'Podaj numer telefonu'); readln Ctelefon); writelnC 'Czy zna#gzyk ang.ie#'ski ' ) ;r readln Cangielski); writeln C'Czy zna język rosyjski'); readln Crosyjski); writelnC 'Czy zna jgzyk niemiecki ' ) ; readln Cniemi ecki ) ; writeln C'Czy znajgzyk francu5ki'); readln Cfrancuski); writeln C'Podaj wykształcenie:'); Nauka programowania... Algorytm 8.3. otwórz plik podczas gdy nie napotkano symbolu końca pliku odczytaj kolejny rei nierówność zbiorów <= oraz => zawieranie sig zbiorów Obecnie dla przypomnienia podamy defnicjg sumy, różnicy i iloczynu zbiorów. Sumą zbiorów A oraz B jest zbiór, którego elementy należą do zbioru A lub do zbioru B. Iloc"#ynem zbioraw A oraz B jest zbiór, którego I elementy należą do zbioru A i do zbioru B. Natomiast różnicą zbiorów A oraz B jest zbiór, ktflrego elementy należą do zbioru A, ale nie należą do I ' zbioru B. Wszystkie zdefiniowane operacje na zbiorach ilustruje poniższy przykład. Przykład Rozważmy następujący zbiór artykułów sportowych: { narty, kijki, buty nar, łyżwy, sanki, rakiety, piłki, płetwy, okulary"pływ, rowery, motocykle} -53- Nauka programowania... end. writeln C' Pliki nie s# identyczne') Przykłady dotyczące wykorzystania plików elementowych znajdują się również w rozdziale 8 poświęconym zastosowaniu rekordów. W rozdziale tym są też zamieszczone zadania utrwalające wprowadzony materiał. -50- Rozdział ZBIORY 7.1. Wprowadzenie Język Pascal umożliwia wykorzystywanie w programach zbiorów teorio- # ', mnogościowych, których elementy muszą należeć do pewnego określonego ; ' typu. #p zbiorowy definiujemy w sposób następujący: type nazwa = set of nazwa typu ; gdzie nazwa jest nazwą typu zbiorowego, a nazwa typu jest nazwą tzw. typu podstawowego, który stanowi elementy zbioru (może to być typ integer, char, boolean, wyliczeniowy lub okrojony). Wartościami zmiennych typu #' zbiorowego są zatem wszystkie zbiory, które można utworzyć z wartości ` typu podstawowego oraz zbiór pusty (pusty nie zawiera żadnego elementu). Wartości zmiennym typu#źl#iorowego. na#ąjem# przy pomocy tzw. konstruktora zbioru, którym jest para nawiasów prostokątnych [), wewnątrz których wpisujemy wartości typu podstawowego. Przykład type abc='a'..'c'; trzyl i tery = set of abc ; var x: trzylitery; - 51- Nauha pro#ramowania... ( odczytani e tabl i c z pl i ku ) resetfpl i k) ; C otworzenie pl i ku ) whi le not eof Cpl i k) do begi n readfplik,tab);C odczytanie tablicy ) f kontrolne wydrukowanie zawartości tablicy ) for i :=1 to n do write Ctab Ci]:2); writeln end; closeCplik) end. Przykład l#eścią przykładu jest program umożliwiąjący porównanie dwóch plików elementowych przechowujących całe tablice. Wykorzystany algorytm polega na kolejnym porównywaniu zawartości odczytanych tablic aż do końca krótszego pliku i następnie w przypadku uzyskania pozytywnej odpowiedzi na sprawdzeniu długości obu plików Program 6.4 program P1 i ki 4; ( Porównywanie dwóch plikbw elementowych przechowujdcych tablicg ) const n=10; type wyniki = arrayCl. .n] of integer; r,a r pi erwszy, ( pl i k pi erwszy ) drugi : ( pl i k drugi ) fi le of wyni ki ; tabl, tab2 : wyni ki ; ( przechowywane tabl i ce ) nazwa#l, ( nazwa pi erwszego pl i ku ) nazwa 2 : ( nazwa drugi ego pl i ku ) string[12]; function Porownaj Cnazwa#l,nazwa#2: string):boolean; -48- 6. Pliki elementowe ( Porównywani e pl i ku nazwa#l z pl i ki em nazwa 2 ) var blad: boolean; i:integer; begin assign Cpierwszy,nazwa#l); reset Cpierwszy); assignfdrugi,nazwa#2); reset Cdrugi); blad :=true; while blad and not eofCpierwszy) and not eofCdrugi ) do begin ( odczytani e tabl i cy z pi erwszego pl i ku l read Cpierwszy,tabl); C odczytani e tabl i cy z drugi ego pl i ku ) read Cdrugi,tab2); for i :=1 to n do if tabl[i ] C# tab2[i ] then bl ad := fal se f tabl i ce są rbżne ) end; f sprawdzenie rbwności długości plikbw ) if not CeofCpierwszy) = eoffdrugi )) then blad := false; close Cpierwszy); close Cdrugi); Porownaj :=blad end; begin writeln C'Podaj nazwę pliku pierwszego:'): readln Cnazwa#l); wri tel n C ' Podaj nazwę pl i ku drugi ego : ' ) ; readln Cnazwa#2); if Porownaj Cnazwa#l,nazwa 2) then wri tel n C ' P1 i ki sd i dentyczne ' ) else -49- Nauka programowania... end. Przykład #'eścią przykładu jest program umożliwiający kopiowanie pliku elementowego przechowującego liczby całkowite. Program 6.2 program P1 i ki#2 ; ( Program kopi owani a pl i ku el ementowego ) type pl i k = file of integer; var pierwszy, ( plik, z którego kopiujemy ) drugi : ( plik, do którego kopiujemy ) plik; nazwa#l, ( nazwa pl i ku pi erwszego } nazwa 2 : ( nazwa pl i ku drugi ego ) string[20]; procedure Kopiuj Cvar pierwszy,drugi: plik); ( Kopi owani e pl i ku pi erwszy do pl i ku drugi ) var el ement : i nteger ; ( el ement pl i ku ) begin while not eofCpierwszy) do begin read Cpierwszy,element); write Cdrugi,element) end ..#nd ; , begin writeln C'Podaj nazwg pliku wejściowego:'); readln Cnazwa#l); writeln C'Podaj nazwg pliku wyjściowego:'); readln Cnazwa#2); assign Cpierwszy,nazwa#l); reset Cpierwszy); assign Cdrugi,nazwa#2); -46- 6. Pliki elementowe rewrite Cdrugi); Kopiuj Cpierwszy,drugi); close Cpierwszy); close Cdrugi) end Przykład Zamieszczony niżej program pozwala na utworzenie pliku elementowego przechowującego całe tablice. Program 6.3 program P1 i ki#3; C Tworzeni e pl i ku el ementowego zawi erającego tabl i ce ) const n=10; type wyniki = arrayCl. .n] of integer; var tab: wyniki ; pl i k : fi 1 e of wyni ki ; nazwa: string[12]; i:integer; begin writeln C'Podaj nazwę pliku'); readln Cnazwa); assign Cplik,nazwa); rewrite Cplik); ( zapi s tabl i c do pl i ku, tabl i ca o zerowym pi erwszym elemencie kończy operacjg l repeat writeln C'Podaj tablicę'); fori :=1 to n do read Ctab Ci]); write Cplik,tab); until tabCl] = 0; -4#- Rozdział PLIT#T ELEMENTOWE Pliki elementowe są to pliki, w których przechowywana informacja jest przedstawiona w postaci zakodowanej niemożliwej do bezpośredniego odczytania. Deklaracja zmiennej plikowej dla pliku elementowego jest postaci: nazwa pliku: file of typ składowy gdzie nazwa pliku jest nazwą zmiennej plikowej, a typ#składowy jest typem prostym lub strukturalnym (typ#składowy nie może być typem plikowym lub wskaźnikowym). Podobnie jak dla plików tekstowych przyporządkowanie nazwy pliku dyskowego do konkretnej zmiennej plikowej dokonujemy przy pomocy procedury assign. Otwieranie plików wykonujemy przy pomocy procedur rewrite i reset (ale bez procedury append), a zamykanie przy pomocy # procedńry close. Wykorzystanie plików elementowych zilustrujemy kilkoma przykładami. Przykład W przykładzie podamy program, który umożliwia wykonywanie dwóch podstawowych operacji tzn. wczytywania i wyprowadzania danych z pliku elementowego. Operacje te wykonamy dla dwóch plików: jednego przechowującego liczby całkowite i drugiego przechowującego liczby rzeczywiste. -44- 6. Pliki elementowe program 6.1 Program P1 i ki#l ; ( Programilustruj#cy wykorzystanie plików elementowych } const n=100; var pl i kcal k : fi 1 e of i nteger ; pl i krzecz : fi 1 e of real ; i,m:integer; x,y: real; begin assign Cplikcalk,'pl'); rewri te Cpl i keal k) ; assign Cplikr2ećz,'p2'); rewrite Cplikrzecz); ( pl i k z 1 i czbami cal kowi tymi } ( pl i k z 1 i czbami rzeczywi stymi } ( przyporzddkowani e nazwy do pl i ku } { otworzenie pl i ku } ( zapi s do pl i kdw } for i :=1 to n do write Cplikcalk,i); for i :=1 to n do begin x:#0.345*i; wri te Cpl i krzecz, x ) end ; ( odczytywani e z pl i kbw } reset C pl i kcal k) ; ( otworzeni e pl i ku } while not eofCpli kcal k) do begin read C pl i kcal-k ;r#; write Cm:4) end; reset Cpl i krzecz ) ; ( otworzeni e pl i ku } while not eofCplikrzecz) do begin read Cplikrzecz,y); write Cy:8:3) end -45- Nauka programowania... Przykład Poniżej zamieszczono program testujący prncedurę Usun, ktńra umożliwia usunięcie z tekstu zdefiniowanego fragmentu. Usuwane są wszystkie wystąpienia tego fragmentu tekstu. Przy usuwaniu jest wykorzystywana standardowa procedura Delete, a przy wyznaczaniu położenia danego fragmentu standardowa procedura Pos. Program 5.13 program Usuwanie; ( Program usuwani a z tekstu zdefi ni owanego fragmentu } var x, f tekst podstawowy } y: f fragment tekstu do usunigcia } string; procedure UsunCvar tekst, zam: string); ( Usuwanie tekstu zam z tekstu tekst } var nr: integer; ( numer pozycji wyst#pienia tekstu } begin repeat f wyznaczenie kolejnej pozycji wyst#pienia tekstu zam } nr :=PosCzam,x); if nr C# 0 then f usunigcie fragmentu tekstu o dlugości LengthCzam) poczynaj ac od pozycj i nr } " Delete Cx,nr,Length Czam)); unti 1 nr = 0 end; 6egin # x := ' A1 a ma ma kota ma ', y := 'ma ' Usunfx,y); writeln Cx) end. W wyniku wykonania programu otrzymamy wydruk: Ala kota - 42 - 5. Pliki tekstowe i operacje na tekstach 5.5. Zadania 1.Napisać program kopiowania jednego pliku tekstowego do drugiego zastępując jednocześnie każdy ciąg spacji jedną spacją (ciąg spacji na początku wiersza ma pozostać bez zmiany). 2.Napisać program wczytywania słowa i obliczania ile razy to słowo wystąpiło w danym tekście. 3.Napisać program zastępowania wyróżnionego słowa w tekście innym słowem. 4. Napisać program usuwania zde#iniowanej linii w tekście. 5.Napisać program wstawiania podanego tekstu po określonej linii tekstu. 6. Napisać program znajdowania najdłuższego słowa w tekście. 7. Napisać program drukowania pliku tekstowego na drukarce wraz z numerami linii. 8.Zmodyfikować program Pokaz tak, by możliwe było przewijanie plików tekstowych o dowolnej długości. 8.Napisać program drukowania tekstu dowolnego programu zapisanego w języku Pascal w ten sposób, by słowa kluczowe były pogrubione. -43- Nauha programowania... Przykład W przykładzie zaprojekt#jemy program centmwania tekstu w każdej linii pliku tekstowego. Centrowanie polegać bgdzie na umieszczeniu każdej linii tekstu na środku wydruku. W programie jest wykorzystana procedura Usun#spacje, ktńra pozwala na usunięcie spacji umieszczonych na początku i na końcu tekstu. Po usunięciu tych spacji wyznaczamy długość "czystego" tekstu, co umożliwia wyznaczenie liczby spacji, które powinny zostać umieszczone na początku linii po to, by tekst znalazł się na środku. Program 5.12 program Centruj; ( Program centrowani a tekstu w każdej 1 ini i pl i ku ) const max#l i ne = 80 ; type jedna#linia = string[max#line); var pl i kl, ( pl i k wej ści owy ) pl i k2 : ( pl i k wyjści owy ) text; linia: jedna#linia; ( linia tekstu ) nazwa#l, ( nazwa pl i ku wej ści owego ) nazwa#2: C nazwa pliku wyjściowego ) string[12]; spacje:integer; functron Usun#spacje Clinia:jedna#linia): jedna#linia; C Usunięcie pocz#tkowych i końcowych spacji z jednej linii tekstu ) var ~ n, ( d1 ugość 1 i ni i ) i, ( zmienna pomocnicza startujdca od poczatku linii ) j: ( zmienna pomocnicza startuj#ca od końca linii ) integer; wynik:jedna#linia: begin n := LengthClinia); i :=1; j :=n; wynik := -40- 5. Plihi tehstowe i operacje na tehstach C wyznaezeni e 1 i czby spacj i od pocz#tku 1 i ni i ) while Ci C= n) and CliniaCi]='' ) do i := i + 1; C wyznaczeni e 1 i czby 5pacj i od końca 1 i ni i ) while Cj C= n) and CliniaCj7 = '' ) do j := j - 1; C przepi sani e tekstu bez pocz#tkowych i końcowych spacj i ) whi 1 e i C= j do begin wynik:=wynik+linia[i]; i;=i+1 end: Usun#spacj e := wyni k end; begin writeln C'Podaj nazwę pliku wejściowego:'); readln Cnazwa#l); writeln C'Podaj nazwę plikuwyjściowego:'): readln Cnazwa 2); assign Cplikl,nazwa#l); reset Cplikl); assi gn C pl i k2,nazwa 2 ) ; rewrite Cplik2); whi 1 e not eof C pl i kl ) do begin readln Cplikl,linia): C wyznaczeni e 1 i czby spacj i na pocz#tku drukowanej 1 i ni # 1 " spacje := Cmax line - Length C Usun#spacje Clinia))) div2; writeln Cplik2,' :spacje, Usun#spacje Clinia)); end; close Cplikl); cl ose C pl i k2 ) ; end - 4# - Nauka programowania... writeC' W&WObejrzyj','Liczba linii: :60,max-1); Goto XYC1,25); ClrEo1; writef' Plik: ', nazwa, '@K. Walczak ':65); Text Background C Black); ( Kolor tla: czarny ; TextColorCWhite);{ Kolor tekstu: bialy ; windowCl,2,80,24); ( ustawienie okna do wyprowadzania tekstu ; linia:=1; wyswietl Clinia); koni ec := fal se ; repeat case Menu of 1: Nastepny; ( przesunigcie o jedn# linig w dól ; 2 : Poprzedni ; ( przesuni ęci e o j edn# 1 i ni g w górg ; 3: Strona#dol ; ( przesunigcie o strong w dól ; 4: Strona#gora; ( przesunigcie o stronę w górę ; 0 : begi n windowCl,1,80,25); f okno na caly ekran ; C1 rScr ; koniec := true f koniec pracy programu ; end end unti 1 koni ec end. ů 5.3. Wyprowadzanie danych na drukarkg Wyprowadzanie danych na drukarkę zilustrujemy przykładem. Przykład W przykładzie podamy dwa programy umożliwiające skierowanie wydruku na drukarkę. Program 5.10 program Wydruk#l; 5. Pliki tekstowe i operacje na tekstach var plik: text; begin assign Cplik,'lptl'); rewrite Cplik); writeln Cplik,'Pewien tekst'); close Cplik) end. Powyższy program można skrócić wykorzystując dostępny w języku #rbo Pascal moduł Printer. Po przyłączeniu modułu należy następnie użyć standardową zmienną lst, ktflra oznacza kierowanie wydruku na drukarkg. Program 5.11 program Wydruk#2; uses Printer; begin writeln Clst,'Pewien tekst') end. 5.4. Operacje na tekstach W tym punkcie zilustrujemy dwoma przykładami wykonywanie operacji na tekstach przechowywanych w plikach tekstowych. Nąjpierw jednak wspomnimy o kilku podstawowych funkcjach dz#ałąjących na zmiennych typu łańcuchowego. Dokładny opis tych funkcji można znaleźć w pracy [14]. Concat(x,y) sklejenie, takie samo działanie jak x + y Lenglzt(x) podaje długość #miennej x # Pos(x,znak)podaje pozycję pierwszego wystąpienia znaku znak w zmiennej x Delete(x,n,k) usuwa k znaków ze zmiennej x zaczynąjąc od pozycji n Zmienne typu łańcuchowego można ze sobą porównywać przy pomocy operatorów <, >, <>. Istnieje rownież możliwość wstawienia odpowiedniego znaku na daną pozycję. Dokonuje się tego w sposób następujący: x[n] :=znak gdzie x tak jak i poprzednio jest zmienną typu łańcuchowego, znak zmienną typu znakowego. -39- Nauha prngramowania... end end; write Ctablica Clinia]) procedure Strona#gora; ( Przesunigcie tekstu jedn# strong w g8rę ) begin if linia > 1 then begin linia := linia - 23; if linia C 1 then linia :-1; Wyswietl Clinia) end end; procedure Strona# Dol; ( Przesunięcie tekstu jedna strong w d61 ) begin if 1 inia C max - 23 then begin linia :# linia + 23; if linia > max - 23 then linia :=max - 23; Wyswietltlinia) end end; function Menu:integer; C Sterowanie prac# programu ) var znak: char; : #egin ů i sprawdzenie ostatnio naciśnigtego klawisza, kody używanych klawiszy: 27 - Esc, 72 - strzalka w g6rę 73 - PgUp 80 - strzalka w d81 81 - PgDn ) repeat -36- 5. Plihi tehstowe i operacje na tehstach znak := ReadKey; f wczytanie znaku ) unti 1 znak in Cchr CBO),chr C72),chr C73),chr C81),chr C27)]; if ordCznak) = 27 then menu := 0 f kl awi sz Esc ) else if ordCznak) = 80 then menu :=1 f klawisz strzalka w dól ) else if ordCznak) = 72 then menu := 2 f klawisz strzałka w g6rę ) el se i f ord C znak ) = 81 then menu :=3 f klawisz PgDn ) else if ordCznak) = 73 then menu :=4 f klawisz PgUp ) begin C1 rScr ; Goto XYC1,24); writeln C' write C'Podaj nazwę pliku: '); readln Cnazwa); Assign Cplik,nazwa); reset Cplik); f wpi sywani e wi erszy tekstu do tabl i cy ) max :=1; whi 1 e not eof C pl i k ) do begin readln Cplik,tablica Cmax]); max := max + 1 end; 1 TextBackgroundCWhite); f Kolor tla: bialy ) Text Color C Black); f Kolor tekstu: czarny ) Goto XY(1,1); C1 r Eol ; f wyczyszczeni e do końca 1 i ni i ) -37- Nauka prog#ramowania... wyświetlania można wykorzystywać pewne klawisze umożliwiające sterowanie przesuwaniem tekstu. Przykład W przykładzie zaprojektujemy program umożliwiający wyświetlanie na ekranie zawartości pliku tekstowego. Podczas wyświetlania tekstu powinniśmy mieć możliwość jego przewijania o jedną linig w górę lub w dół oraz o jedną stronę w górę lub w dół. Dostępne powinny być zatem następujące klawisze: strzałka w górę, strzałka w dół oraz PgDn i PgUp. Ponadto naciśnięcie klawisza Esc powinno zakończyć wyświetlanie tekstu. Sterowanie pracą programu odbywa się przy pomocy funkcji Menu(), która podaje odpowiednią wartość w zależności od naciśniętego klawisza. W przypadku naciśnięcia klawisza strzałka w górę jest wywoływana procedura Poprzedni, natomiast naciśnięciu klawisza strzałka w dół powoduje wywołanie procedury Nastepny, a po naciśnięciu klawiszy PgDn i PgUp są odpowiednio wywoływane procedury Strona dol i Strona#gora. W programie jest ponadto wykorzystywana procedura Wyswietl umożliwiająca wyświetlenie tekstu poczynając od wskazanej linu. Kompletną treść programu zamieszczono poniżej. W programie użyto następujących funkcji i procedur zawartych w module Crt: ClrScr, GotoXY, InsLine, TextBackground, Z7extColor, Window. Ich działanie jest wyjaśnione w komentarzach zamieszczonych w programie. Program 5.9 Program Pokaz; f Program wyświ etl ani a zawartości pl i ku tekstowego ; uses ert;: const max#line=80;{ maksymalna liczba znakóww linii ) #niax#row = 500; { maksymalna 1 i czba 1 ini i w pl i ku ; var pl i k : text ; f anal i zowany pl i k tekstowy ; nazwa :string[12] ; f nazwa pl i ku ) tablica: array [l..max#row] of string[max#line]; max : i nteger ; { maksymal na 1 i czba zaj gtych wi erszy tabl i cy ) linia: integer;f aktualna linia tekstu ) koni ec : bool ean ; { sterowani e zakończeni em pracy programu ) procedure Wyswietlfa: integer); -34- 5. Pliki tekstowe i operacje ha tekstach f Wyświ etl eni e tekstu na ekrani e poczynaj ac od 1 i ni i o numerze a ) var j:integer; begin C1 rScr ; f wyczyszczeni e ekranu ) j :=a; f podczas gdy ni e wyjdzi emy poza ekran 1 ub poza koni ec tekstu ) while Cj C a + 23) and Cj C max) do begin wri tel n ; f wydruk j-tej linii tekstu ) write Ctablica Cj]); j;=j+1 end; end procedure Nastepny; f Wyświ etl eni e nastgpnej 1 i ni i tekstu ) begin if linia + 25 C max then f jeśli nie wyjdziemy poza koniec tekstu ) begin f ustawi eni e kursora w 231 i ni i i w 80 kol umni e ) gotoxy C80,23); linia := linia + 1; writeln; fwyświ etl eni e nowej 1 i ni i tekstu na dol e ekranu ) writeCtablicaClinia + 24]) # end end; procedure Poprzedni ; =ů # f Wyświ etl ani e poprzedni ej 1 i ni i tekstu ) begin if linia # 1 then f jeśli nie wyjdziemy poza pocz#tek tekstu ) begin linia :=linia - 1; gotoxy Cl,l); InsLine; f wstawienie linii ) fwyświ etl eni e nowej 1 i ni i tekstu na górze ekranu) -35- Nauka programowania... begin 1 i czba :=1 i czba + 1; noweslowo := false end end; close Cplik) end; begin writeln C'Podaj nazwę pliku'); readln Cnazwa); Slowa Cnazwa,n); wri tel n C ' Li czba słów w pl i ku ',nazwa, ' wynosi ', n : 5 ) end. Przykład Przykład zawiera funkcję porównywania zawartości dwóch plików tekstowych. Wykorzystany algorytm polega na sprawdzaniu równości znaków do końca krótszego pliku, a następnie w przypadku pozytywnego wyniku na sprawdzeniu długości plików. Program 5.8 program Tekst#6; f Program porównywani a dwóch pl i ków tek5towych ) var ' pi erwszy, f pl i k pi erwszy ) drugi : ( pl i k drugi ) " text ; nazwa 1, ( nazwa pl i ku pi erwszego ) nazwa 2: ( nazwa pliku drugiego ) string Cl2]; function Porownaj Cnazwa#l,nazwa#2: string):boolean; ( Funkcja porównywani a dwóch pl i ków tekstowych ) var znakl, { odczytany znak z pl i ku pi erwszego ) znak2 : f odczytany znak z pl i ku drugi ego ) char; -32- 5. Pliki tekstowe i operacje na tekstach bl ad : bool ean ; ( zmi enna i nformuj#ca o r8wności pl i ków) begin assignfpierwszy,nazwa#l); reset Cpierwszy); assi gn Cdrugi,nazwa 2) ; reset Cdrugi); bl ad := true ; # pl i ki s# jednakowe ) C sprawdzeni e znak8w do końca krótszego pl i ku ) while blad and not eofCpierwszy) and not eofCdrugi ) do begin read Cpierwszy,znakl); read Cdrugi,znak2); if znakl C# znak2 then bl ad := fal se( pl i ki s# r8żne ) end; l jeśl i różna dlugość pl i k8w ) ifnot CeofCpierwszy) = eofCdrugi)) then blad := false; close Cpierwszy); close Cdrugi); Porownaj := bl ad end; begin writeln C'Podaj nazwę pliku wejściowego:')# readln Cnazwa#l); writeln C'Podaj nazwg pliku wyjściowego:'); readln Cnazwa 2); if Porownaj Cnazwa#l,nazwa#2) then wri teln C ' P1 i ki są identyczne ' ) else writelnC' Pliki nie s# identyczne') end Ostatni przykład jest poświgcony nieco trudniejszemu problemowi, a mianowicie wyświetlaniu na ekranie zawartości pliku tekstowego. W trakcie Nauka programowania.. n : i nteger ; f 1 i czba wi erszy w pl i ku ) nazwa : string[12] ; f nazwa pl i ku ) procedure Wiersze Cnazwa: string; varliczba:integer); f Procedura obl i czani a 1 i czby wi erszy ) var znak : char ; f j eden znak w pl i ku 1 Degin assign Cplik,nazwa); reset Cplik); 1 i czba : = 0 ; while not eofCplik) do begin f przetwarzani e jednego wi ersza tekstu ) while not eolnCpl i k) do read Cplik,znak); readln Cplik); 1 i czba :=1 i czba + 1 f zwi ększeni e 1 i czby wi erszy ) end; close Cplik) end; begin writeln C'Podaj nazwę pliku'); readln Cnazwa); Wi ersze C nazwa, n ) ; wri tel n C ' Li czba wi erszy w pl i ku ', nazwa, ' wynosi ', n : 5 ) end. Przykład Przykład jest poświgcony obliczeniu liczby słów w pliku tekstnwym. Zakładamy, że poszczególne słowa są oddzielone znakiem spacji, tabulacji lub końcem linii. Ponadto zakładamy, że migdzy słowami może być tylko jeden znak spacji. Obliczenie liczby słów realizuje procedura Slowa, której algorytm jest podany poniżej. Algorytm 5.1. podczas gdy nie napotkano symbolu końca pliku wykonuj '3O' 5. Plihi tehstowe i operacje na tehstach wczytaj znak jeśli znak jest symbolem końca słowa to zapamiętaj, że nowe słowo w przeciwnym przypadku jeśli nowe słowo to zwiększ licznik słów zapamiętaj, że nie nowe słowo A oto program testujący procedurg Slowa. Program 5.? program Tekst#5; { Program obl iczani a 1 i Czby sł6w w pl i ku tekstowym } Const TABULACJA = 9; pl i k : text ; { pl i k, w którym zostana zl i czone słowa } n : i nteger ; { 1 i czba sł 6w w pl i ku } nazwa : stri ng[12) ; { nazwa pl i ku } procedure Slowa Cnazwa: string; varli Czba:integer); { Procedura obl i czani a 1 i czby słbw w pl i ku } znak: char; { jeden znak z pliku }# noweslowo: boolean; begin assign Cplik,nazwa); reset Cplik); liczba := 0; while not eofCpl i k) do begin read Cplik,znak); if Cznak= '') oreoln(plik) or Cord Cznak) = TABULACJA) then noweslowo := true el se i f nowesl owo then Nauka programowania... end; readlnCpierwszy); C odczytanie znaku końca linii ; wri tel n Cdrugi ) C zapi sani e znaku końca 1 i ni i ; end; cl ose C pi erwszy ) ; C zamkni ęci e pl i ku ; close Cdrugi); writeln C'Skopiowano plik end; ', nazwa#l, ' do pl i ku ',nazwa#2) begin writeln C'Podaj nazwę pliku wejściowego:'); readln Cnazwa 1); writelnf'Podaj nazwę pliku wyjściowego:'); readln Cnazwa#2); Kopi uj Cnazwa#l,nazwa 2 ) C skopi owani e pl i ku o nazwi e nazwa#l ; end. Przykład W przykładzie podamy procedurę umożliwiającą podanie liczby znaków zawartych w pliku tekstowym. Wykorzystany algorytm polega na przejrzeniu wszystkich znaków w tekście i zliczeniu ich liczby. Przeglądanie odbywa się linia po linii z wykorzystaniem funkcji eoln(). Program 5.4 program Tekst#3; ( Program zl i czani a znaków ; var pl i k : ůtext ; ( pl i k, w którym zostan# zl i czone znaki ; n : i nteger ; ( 1 i czba znaków w pl i ku ; nazwa : stri ng[12] ; f nazwa pl i ku ; procedure Znaki Cnazwa: string; varliczba:integer); f Procedura zl i czani a zna ków w pl i ku, nazwa - nazwa pl i ku, 1 i czba - 1 i czba znaków w pl i ku ; var znak : char ; C jeden znak tekstu ; -28- 5. Pliki tekstowe i operacje na tekstach begin assign Cplik,nazwa); reset Cplik); liczba := 0; whi 1 e not eof C pl i k ) do begin C przetwarzanie jednej linii tekstu ) while not eolnCpli k) do begin read Cplik,znak); 1 i czba :=1 i czba + 1 end; readlnCplik) f wczytanie znaku końca linii ) end; close Cplik) end; begin writeln C'Podaj nazwę pliku'); readln Cnazwa); Znaki Cnazwa.n); writelnC 'Liczba znaków w pliku ',nazwa, ' wynosi ',n:5) end Przykład W odróżnieniu od poprzednieg_o#rzykładu t,8matem którego było podanie liczby znaków tekstu, obecnie zaprojektujemy procedurę, która umożliwia wyznaczenie liczby wierszy tekstu. Podobnie jak w poprzednim przykładzie są przeglądane wszystkie znaki tekstu, a obliczanie liczby wierszy odbywa się dopiero w momencie zakończenia przeglądania danego wiersza tekstu. Program 5.6 program Tekst 4 ; ; Program obl i czani a 1 i czby wi erszy w pl i ku tekstowym ) var pl i k : text ; ; pl i k, w którym zostan# zl i czone wi ersze ) -29- Nauka programowania... wykorzystanie funkcji eofi), ktńra podąje wartość true, jeżeli napotkamy koniec pliku. Program 5.2 program Tekst#l; f Kopi owani e pl i ku tekstowego 1 ini ami ) var pi erwszy, f pl i k pi erwszy ) drugi : f pl i k drugi ) text; linia: string[80]; f jedna linia tekstu ) nazwa#l, f nazwa pl i ku pi erwszego ) nazwa#2: f nazwa pl i ku drugi ego ) string[20]; assign Cpierwszy,nazwa#l); f przyporz#dkowanie nazwy do pliku ) reset C pi erwszy ) ; f otworzeni e pl i ku ) assign Cdrugi,nazwa 2); rewri te Cdrugi ) ; f otworzeni e pl i ku ) procedure Kopiuj Cnazwa#l,nazwa#2: string); f Procedura kopi owani a pl i ków ) begin whi 1 e not eof C pi erwszy ) do begin f odczytanie jednej linii tekstu ) . readln Cpierwszy,linia); f zapi sani e jednej 1 ini i tekstu ) writeln Cdrugi,linia) end; cl ose C pi erwszy ) ; f zamkni ęci e pl i ku ) close Cdrugi); wri tel n C 'Skopi owano pl i k ', nazwa#l, ' do pl i ku ', nazwa 2 ) end; begin writeln C'Podaj nazwę pliku wejściowego:'); readln Cnazwa#l); -26- 5. Plihi tehstowe i operacje na tehstach writeln C'Podaj nazwę pliku wyjściowego:'); readln Cnazwa 2); Kopiuj Cnazwa#l,nazwa 2) f skopiowanie pliku o nazwie nazwa 1 } end. Przyhład W odróżnieniu od poprzedniego przykładu obecnie podamy prooedurę kopiowania pliku tekstowego znak po znaku. Procedura ta zostanie wykorzystana w programie llekst 2. Warto zwrócić uwagg na funkcję eoln(), która umożliwia przetwarzanie znaków umieszczonych w jednej linii. Funkcja ta podaje wartość true, gdy napotkano koniec pliku. Program 5.8 program Tekst 2 ; f Kopiowanie pliku tekstowego znak po znaku } var pi erwszy, f pl i k pi erwszy } drugi : f pl i k drugi } text; znak: char; f jeden znak tekstu } nazwa#l, f nazwa pl i ku pi erwszego } nazwa 2: f nazwa pl i ku drugi ego } string[20); procedure Kopiuj Cnazwa#l,nazwa#2: string); f Procedura kopi owani a pl i k6w } begin a5sign Cpierwszy,nazwa#l); f przypisanie na2wy } resetCpierwszy); f otworzenie pliku } assign Cdrugi,nazwa 2) rewrite Cdrugi); whi 1 e not eof C pi erwszy ) do begin f skopi owani e do końca 1 i ni i } while not eolnCpierwszy) do begin read Cpierwszy,znak); write Cdrugi,znak) -27- Nauka programowania... Zapisywanie i odczytywanie danych z plików tekstowych dokonujemy przy pomocy instrukcji read, readln, write oraz writeln, które zostały omówione w [20]. Obecnie instrukcje te wzbogacimy o podanie nazwy pliku. Po tym uzupełnieniu postać tych instrukcji jest nastgpująca: read(nazwa pliku,lista argvmentów); write(nazwa pliku,lisfa argumenfów); Poniższe przykłady zilustrują wykonywanie operacji na plikach tekstowych. Przykład W przykładzie podarny program realizujący zapisywanie i odczytywanie danych z plików tekstowych. Po uruchomieniu programu można obejrzeć zawartości utworzonych plików tekstowych. Bgdziemy wykorzystywać trzy pliki, wszystkie tekstowe, z których jeden przechowuje liczby całkowite, drugi liczby rzeczywiste, a trzeci znaki. Program 5.1 program Tekst#0; { Program i 1 ustruj#cy zapi sywani e i odczytywani e danych z pl i ków tekstowych } const n=10; var pl i kcal k, { pl i k z 1 i czbami cal kowi tymi } pl i krzecz, { pl i k z 1 i czbami rzeczywi stymi } pl i#sl ow: { pl i k ze znakami } text; i, { zmienna kontrolna pętl i } m: integer; { zmienna pomocnicza } . ~ x,y:ůreal ; { zmienne pomocnicze } slowo: string[10];{ zmienna pomocnicza } begin assi gn Cpl i kcal k, ' tl ' ) ; { przyporządkowani e nazwy do pl i ku } rewri te C pl i kcal k ) ; { otworzeni e pl i ku } assign Cplikrzecz,'t2'); rewrite Cplikrzecz); assign Cplikslow,'t3'); rewrite Cplikslow); -24- 5. Pliki tekstowe i operacje na tekstach fori:=ltondo write Cplikcalk,i:4); fori:=ltondo begin x := 0.345 * i ; writeCplikrzecz, x:8:3 ) end; fori:=ltondo write Cplikslow,'a'); reset C pl i kcal k ) ; C otworzeni e pl i ku ) while not eofCplikcalk) do begin read Cplikcalk,m); write Cm:8) end; writeln; reset Cplikrzecz); while not eof Cplikrzecz) do begin read Cplikrzecz,y); write Cy:10:3) end; writeln; reset Cplikslow); while not eof(plikslow) do begin read Cplikslow,slowo); writeCslowo,'') end end Przykład 1t'eścią przykładu jest procedura umożliwiająca kopiowanie zawartości pliku tekstowego linia po linii. W podanym programie warto zwrócić uwagę na -25- Rozdział PLIKI TEKSTOWE I OPEZ#AC#TE NA TEKSTACH W niniejszym rozdziale omówimy pliki tekstowe tzn. takie, w których dane są przedstawiane w postaci ciągu znaków. W nastgpnym rozdziale omówimy pliki elementowe, w których dane są przedstawiane w postaci zakodowanej, niemożliwej do odczytania przez edytor #.l. Pliki input i output Pliki input i output są standardowymi plikami tekstowymi zawierąjącymi dane do programu i wyniki wykonania programu. Plik input może być wczytywany tylko jeden raz, natomiast inne pliki tekstowe mogą być wczytywane wielokrotnie. Do wprowadzania danych i wyprowadzania wyników służą instrukcje read, readln, write, writeln, które zostały omówione w książce [20) pierwszej w cyklu poświęconym nauce programowania. Przy wprowadzaniu i wyprowadzaniu danych można wykorzystywać funkcjg eofi) stwierdzającą, czy osiągnęliśmy koniec pliku oraz funkcję eoln() stwierdzającą czy osiągngliśmy koniec linii. Wykorzystanie tych funkcji -22- 5. Plihi tehstowe i operacje na tehstach zostanie omówione w następnym punkcie poświęconym plikom tekstowym. 5.2. Pliki tekstowe Pliki tekstowe są to pliki zawierąjące informację niezakodowaną, czytelną w bezpośredni sposób. Plik tekstowy deklarujemy w sposób nastgpujący: var nazwa pliku: text; gdzie nazwa pliku jest nazwą tak zwanej zrniennej plikowej. Przed wykonaniem jakichkolwiek operacji na tekście przechowywanym w pliku na dysku powinniśmy najpierw przyporządkować nazwę pliku dyskowego do konkretnej zmiennej plikowej wykorzystywanej w programie. Do tego celu służy procedura standardowa assign. Jej wywołanie jest postaci: assignlnazwa pliku, nazwa dysk); gdzie nazwa pliku jest nazwą zmiennej plikowej w programie, a nazwa dysk jest nazwą pliku na dysku. Nastgpnie należy otworzyć plik przy pomocy jednej ze standardowych procedur rewrite, reset lub append. Dokonuje sig tego w sposób następujący: rewrite(nazwa pliku); lub reset(nazwa pliku); lub append(nazwa pliku); Migdzy procedurami reset oraz rewrite istnieje drobna ale istotna różnica. Otóż procedura reset otwie_xa tylko jużů.istniejący plik (w przypadku próby otwarcia nie istniejącego pliku zostanie zasygnalizowany błąd). Natomiast procedura rewrite otwiera dany plik nawet wtedy, gdy nie istniał on poprzednio na dysku. Jednak przy zastosowaniu tej procedury jest wymagana szczególna ostrożność. Jeśli plik istniał na dysku, to użycie procedury rewrite spowoduje nadanie mu zerowej długości. Procedura append powoduje otwarcie pliku wyłącznie do zapisu (dane bgdą dopisywane na koniec pliku). Po wykonaniu żądanych operacji na pliku należy go koniecznie zamknąć przy pomocy procedury close o postaci: close(nazwa pliku); -23- Nauka programowania... xl,yl,zl, f wspólrzgdne jednego końca przek#tnej ; x2,y2,z2: f wspólrzędne drugiego końca przekątnej ; integer; function Przekatna Ct: tablica; xl,yl,zl,x2,y2,z2: integer):integer; f Funkcja obliczania sumy elementdw leż#cych na przek#tnej o wspólrzędnych jednego końca xl,yl,zl i wspó#rzgdnych drugi ego końca x2,y2, z2 ; var i,j,k:integer; f zmienne wyznaczaj#ce kolejne elementy na przek#tnej ; dx, f zmi ana w ki erunku x ; dy, f zmi ana w ki erunku y ; dz : f zmi ana w ki erunku z ) integer; suma: integer; f suma elementów na przek#tnej ; kroki, f 1 i czba el ementów na przekatnej ; ster : f zmi enna steruj #ca obl i czani em sumy el ementdw ; integer; begin dx := 0; dy := 0; dz := 0; kroki :=1; if x2 - xl C# 0 then begin dx := Cx2 - xl) div absCx2 - xl) ; kroki := absCx2 - xl ) + 1 end; ify2 - yl C# 0 then . ` begin dy := Cy2 - yl ) di v abs Cy2 - yl ) ; kroki := absCy2 - yl) + 1 end; if z2 - zl C# 0 then begin dz := C z2 - zl ) di v abs C z2 - zl ) ; kroki := absCz2 - zl ) + 1 end; -20- 4. Moduły suma := 0; i := xl ; j := yl ; k := zl ; for ster :=1 to kroki do begin suma := suma + tCi,j,k]; f ustawienie wspólrzgdnych nastgpnego elementu przek#tnej ) k := k + dz ; j:=j+dy; i := i + dx end; przekatna := suma end; begin writeln C'Wczytanie tablicy trzywymiarowej:'); Czytaj Ct); writeln C'Wczytane wartości:'); Drukuj Ct); writeln; writeln C'Wspblrzędne punktu pocz#tkowego'); readln Cxl,yl,z1); writeln C'Wspbłrzgdne punktu końcowego'); readln Cx2,y2,z2); if Cxl in [1. .n]) and Cyl in [1. .n]) and Czl in [1. .n]) and Cx2 in [1. .n]) and Cy2 in [1. .n]) and Cz2 in [1. .n]) then writeln C'Przekdtna C',xl,', ,yl, ',',zl,') -C',x2,',',y2, z2, ' ) = ',Prze-kat`#aCt,xl,yl;#źl,x2,y2,z2)) el se writeln C'Błąd danych') end - 21- Nauka programowania... deklaracje modułów Cześć opisowa definicje typów i stałych definic#e zmienny#ch lista nagłówkbw procedur i funkcji i I#m#nbli0n d#nicje procedur i funkcji, ktbrYch nagłbwki podano Cześć implementacyjna w cześci interface definicje typów, stałych i zmienny#ch dostępny#h wyt#cznie wevm#trz modułu Cześć inicjuj#ca { instrukcja złożona Iub sfowo kluczowe #nd ftys. 4.1. Struktura modułu Przyhład Moduł podany w przykładzie zawiera dwie procedury Czytaj oraz Drukuj, ktflre zostały zaprojektnwane w poprzednim rozdziale. Procedura Czytąj służy do wprowadzania danych do tablicy trzywymiarowej, a procedura Drukuj umożliwia wyprowadzanie danych. Procedury te mogą być wykorzystywane również w innych programach, dlatego jest celowe umieszczenie ich w module. l#eść modułu zamieszczono poniżej. unit Wprowadz; interface const n=3; type tabl i ca = array C 1. . n,1. . n,1. . n) of i nteger ; procedure Czytaj Cvar t: tablica); procedure Drukujlt:tablica); implementation procedure Czytaj Cvar t: tablica); (Procedura wezytywania elementów tablicy trzywymiarowej) vari,j,k:integer; begin fori:=ltondo for j :=1 to n do for k :=1 to n do -18 - 4. Moduły begin write C'C'.i:2,', .j:2,',',k:2,')= '); readln Ct Ci]Cj]Ck]) end end procedure Drukuj Ct:tablica); f Procedura drukowania elementów tablicy trzywymiarowej ) var i,j,k: integer; begin fori:=ltondo begin forj:=ltondo begin for k :=1 to n do write Ct Ci]Cj]Ck]:4); wri tel n end; wri tel n end end; end. Obecnie pokażemy na przykładzie programu obliczania sumy elementów na dowolnej przekątnej tablicy trzywymiarowej wykorzystanie zaprojektowanego wyżej modułu Wprowadz. W celu użycia zamieszczonych tam procedur Czytaj oraz Drukuj wystarczy (po skompilowaniu modułu) podać w programie instrukcję: uses Wprowadz; a treści tych procedur nie potrzeba już zamieszczać. Gdyby procedura Przekatna:#tżała być wy#orzystywana w innych programach, to również można ją umieścić w module. W przedstawionym niżej programie procedura ta jest podana bezpośrednio w treści programu. Program 4.1 program Trzywymiary; (Program obliczania sumy elementów leżących na dowolnej przek#tnej) uses Wprowadz; var t : tabl i ca ; C anal i zowana tabl i ca ) -19 - Nauka programowania... end. writeln('Błąd danych') 3.2. Zadania 1. Napisać program znajdowania minimalnego i maksymalnego elementu w tablicy trójwymiarowej oraz jego położenia. 2. Napisać program tworzenia wektora zawierającego sumy elementów tablic dwuwymiarowych odpowiadających pierwszemu indeksowi tablicy trzywymiarowej. 3. Napisać program wyznaczania iloczynu oraz sumy elementów tablicy trzywymiarowej różnyeh od zera. 4. Napisać program wyznaczania sumy tych elementów tablicy trzywymiarowej, których wszystkie indeksy są liczbami parzystymi. -16 - Rozdział MODU#Y Jak już wspomniano w książce [20], w systemie llzrbo Pascal procedury i funkcje standardowe są umieszczane w tak zwanych modułach. Modułem podstawowym jest moduł System, który jest automatycznie dołączany do każdego programu. Ponadto istnieją jeszcze moduły Dos, Crt, Graph, Printer i Overlay Przypomnijmy jeszcze, że jeśli chcemy wykorzystać procedury i funkcje zawarte w tych modułach, to należy w części głównej programu bezpośrednio po instrukcji p#ograin użyć instrukcję uses. Obecnie wyjaśnimy metodę tworzenia własnych modułów, w których można umieścić zaprojektowane procedury i funkcje. Moduł tworzy sig w następujący sposób. Piszemy najpierw słowo kluczowe unit, po którym podajemy nazwę modułu. Nazwa pliku, w którym znajduje się moduł, powinna być taka sama jak nazwa modułu. W treści modułu możemy wyróżnić trzy części: opisową, impleme#cyjną oraz##nicjującą. Część inicjująca musi kończyć się kropką. Utworzone moduły powinny być przechowywane w plikach o rozszerzeniu.pas. Plik ten należy skompilować w analogiczny sposób jak program, a tekst wynikowy zostanie zapisany w pliku o rozszerzeniu.tpu. Aby wykorzystać skompilowany moduł w programie, należy podać jego nazwę w instrukcji uses. Wówczas wszystkie procedury i funkcje zdefniowane w module będą dostępne w danym programie. -17 - Nauka programowania... begin for j :=1 to n do begin for k :=1 to n do writeCt[i,j,k] :4) ; writeln end; wri tel n end end; function Przekatna Ct: tablica; xl,yl,zl,x2,y2,z2: integer): integer; { Funkcja obl i czani a sumy el ementów 1 eżących na przekdtnej o współrzędnych jednego końca xl,yl,zl i współrzgdnych drugi ego końca x2,y2, z2 ) var i, j, k : i nteger ; { zmi enne wyznaczaj ace kol ejne elementy na przekdtnej ) dx, { zmi ana w ki erun ku x ) dy, { zmi ana w ki erun ku y ) dz : { zmi ana w ki erunku z ) integer; suma: integer; { suma elementów na przekatnej ) kroki, { 1 i czba el ementów na przek#tnej ) ster : { zmi enna steruj aca obl i czani em sumy el ementów ) integer; begin dx := 0; dy := 0; dz := 0; kroki :=1; if x2 - xl C# 0 then # begin dx := Cx2 - xl) div absCx2 - xl); kroki := absfx2 - xl) + 1 end; i f y2 - yl C# 0 then begin dy := Cy2 - yl ) di v ab5 Cy2 - yl ) ; kroki := absCy2 - yl) + 1 end; -14 - 3. Tablice (uzupełnienie) if z2 - zl C> 0 then begin dz := Cz2 - zl) div absCz2 - zl); kroki := absCz2 - zl ) + 1 end; suma :=0; i := xl ; j := yl ; k := zl ; for ster :=1 to kroki do begin suma := suma + tCi,j,k] ; f ustawienie wspólrzędnych następnego elementu przek#tnej l k:=k+dz; j:=j+dy; i := i + dx end; przekatna := suma end; begin writeln C'Wczytanie tablicy trzywymiarowej:'); Czytajft); writeln C'Wczytane wartości:'); Drukuj Ct); writeln; writeln C'Wspólrzędne punktu poczatkowego'); readln Cxl,yl,z1); writeln C'Wspólrzgdne ##nktu końco Wego'); readln Cx2,y2,z2); Csprawdzenie czy wczytane wspbłrzędne nie wyprowadzaja poza tabl i cę ) if Cxl in [l..n]) and Cyl in C1. .n]) and Czl in [1. .n]) and Cx2 in [1. .n]) and Cy2 in [1. .n]) and Cz2 in [1. .n]) then writeln C'Przek#tna C',xl,','.yl, ',',zl,') - C',x2,',',y2, ',',z2,') = ',Przekatna Ct,xl,yl,zl,x2,y2,z2)) el se -15 - Nauka programowania... Rys. 3.1. Przykładowa tablica trzywymiarowa na przecięciu j-tego wiersza i k-tej kolumny. Na rys. 3.2 przedstawiono indeksy pierwszej tablicy dwuwymiarowej. 111 112 113 121 122123 131 132 133 ftys. 3.2. Indeksy pierwszej tablicy dwuwymiarowej Przy pomocy pogrubienia zaznaezono indeksy jednej z dwóch przekątnych. Jeden z końców przekątnej ma indeksy 111, a drugi koniec indeksy 133. Wykorzystany algorytm polega na znalezieniu liczby elementów przekątnej oraz trzech wartości oznaczanych w programie przy pomocy dx,dy,dz podających, o ile muszą się zmienić indeksy tablicy. Wartość dx podaje zmianę dla zmiennej i, dy określa zmianę dla zmiennej j, a dz wyznacza zmianę dla zmiennej k. W analizowanym przypadku dx ma wartość 0, dy wartość 1 oraz dz wartość 1. Wartości te wyznacza się przy pomocy poniższej konstrukcji, ktorą dla przykładu podamy dla zmiennej x (wyrażenie to ma sens, wtedy gdy x2 - xl jest różne od zera): dx := Ćx2 - xl) div absCx2 - xl); gdzie operator div wykonuje dzielenie całkowite. Jak łatwo można zauważyć, wartość ta może być równa albo +1 albo -l. Liczbę kroków wyznaczamy przy pomocy konstrukcji: kroki := abs Cx2 - xl ) + 1; oczywiście tylko wtedy, gdy x2 - xl jest różne od zera. Ponieważ tablice dwuwymiarowe są kwadratowe, to nie ma znaczenia, z obliczenia której zmiennej wyznaczymy wartość kroku. Obliczenie sumy elementów leżących na dowolnej przekątnej odbywa się już w bardzo prosty -12 - 3. Tablice (uzupełnienie) sposób poprzez wykonanie w pętli następujących instrukcji: suma := suma + tCi,j,k]; C ustawienie wspblrzędnych następnego elementu przekątnej ) k := k + dz ; j:=j+dy; i := i +dx; A oto kompletny program realizujący omawiane zadanie. Program 8.1 program Trzywymiary; (Program obliczania sumy elementów leż#cych na dowolnej przek#tnej) constn=3; type tablica = array [l..n,l..n,l..n] ofinteger; var t : tabl i ca ; C anal i zowana tabl i ca ) xl,yl,zl, C współrzgdne jednego końca przek#tnej ) x2,y2,z2: f wspólrzędne drugiego końca przek#tnej ) integer; procedure Czytaj Cvar t: tablica); ( Procedura wczytywania elementbw tablicy trzywymiarowej ) var i, j, k : i nteger ; f zmi enne kontrol ne pętl i ) begin fori:=ltondo for j :=1 to n do fork:=ltondo begin write C'C',i:2,',',j:2 ',',k:2,') = '); readlnC#tZi,j,k]) end end; procedure Drukuj Ct: tablica); ( Procedura drukowania elementów tablicy trzywymiarowej ) var i, j, k : i nteger ; C zmi enne kontrol ne pętl i ) begin for i :=1 to n do -13 - Nauha programowania... d: tydzien; x:integer; Przy powyższej deklaracji funkcja succ(sroda) podaje wartość czwartek, funkcja succ(11) wartość 12. Wartością funkcji pred(wtorek) jest poniedzia lek, a funkcji pred(15) wartość 14. Funkcja ord(piatek) podaje wartość 5, funkcja ord(13) wartość 13 (podawany numer jest taki jak dana wartoś całkowita). ' lO ' Rozdział TABLICE (UZUPE#NIENIE) 3.1. Tablice trzywymiarowe W pracy [20] podano szereg przykładów ilustrujących wykorzystanie tablic, ale tylko tablic jedno i dwuwymiarowych. W jgzyku Pascal tablice mogą mieć wigcej wymiarów. W zaprezentowanym obecnie przykładzie wykorzystamy tablicg o trzech wymiarach. ' Przykład Napisać program obliczania sumy elementów"leżących na dowolnej przekątnej w tablicy trzywymiarowej l#wadratowej. Tablićg trzywymiarową oraz jedną przekątną główną i jedną boczną ilustruje rys. 3. l. Zastanówmy sig teraz nad algorytmem obliczania sumy elementów leżących na dowolnej przekątnej w tablicy trzywymiarowej. Najważniejsze jest oczywiście wyznaczenie współrzgdnych poszczególnych elementów Wyobraźmy sobie najpierw tablicę trzywymiarową jako n tablic dwuwymiarowych położonych jedna nad drugą. Rozważmy na początek przekątną położoną w pierwszej tablicy dwuwymiarowej. Umówmy się jeszcze, że element tablica[i,j,k] oznacza element leżący w i-tej tablicy dwuwymiarowej 'lI# Rozdział PRO STE TYPY D#C H W poprzedniej książce [20] pierwszej w cyklu poświęconym nauce programowania wprowadziliśmy następujące typy danych: całkowity, rzeczywisty, znakowy, łańcuchowy oraz logiczny. Obecnie omówimy typy danych, które mogą zostać zdefiniowane przez programistę. Należy do nich typ wyliczeniowy oraz typ okrojony. lj#p wyliczeniowy jest definiowany następująco: type nazwa = (sl,...,sn) gdzie nazwa jest nazwą typu, a s; są identyflkatorami stałych, których wartości zltoże przyjmować zmienna danego typu. Przykład typ# mebl e = C stol, krzesl o, szafa, wersal ka ) ; var ml,m2: meble; W przykładzie zdefiniowano typ wyliezeniowy meble oraz zmienne ml oraz m2 typu meble. Wartości typu wyliczeniowego nie można wczytywać ani drukować w normalny sposób. Można je natomiast wykorzystywać w relacjach, funkcjach i instrukcjach przypisania. Przykłady programów, w których wyko 2. Proste typy danych rzystano typ wyliczeniowy są podane w rozdziale 7. 1#p okrojony jest to podzbiór wartości typu całkowitego, znakowego, logicznego lub wyliczeniowego. lj#p ten definiujemy następująco: type nazwa = min..max gdzie nazwa jest nazwą typu, min jest dolnym a max górnym ograniczeniem wartości, jakie może przyjmować zmienna typu okrojonego. Przykład type litera = 'a'..'z'; tydzien = C poniedzialek, wtorek, sroda, czwartek, piatek sobota niedziela ); robocze = poniedzialek..piatek; zakres =10. .20; var 11,12:litera; dni: robocze; zl,z2: zakres Zmienne 11,12, dni, zl, z2 są typu okrojonego i mogą przyjmować następujące wartości: zmienne 11 i 12 - litery a, 'b ',..., z zmienna dni - poniedzialek, wtorek, sroda, czwartek, piatek zmienne zl, z2 - liczby z przedziału <10,20> 1`ypy integer, char, Boolean oraz wprowadzońy wyżej typ wyliczeniowy i okrojony są tak zwanymi typami porządkowymi. Charakteryzują się one tym, że można je uporządkować i dla danej wartości podać wartość poprzednią i następną. Dla typów...#orządkowyd3 można wykorzystywać szereg użytecznych funkeji stańdardowych. Funkcja succ(arg) podaje wartość następną w danym typie po wartości argumentu. Funkcja pred(arg) podaje wartość poprzednią w danym typie przed wartością argumentu. Funkcja ord(arg) podaje numer, jaki wartość argumentu zajmuje w danym typie. Przykład type tydzi en = C poni edzi al ek, wtorek, sroda, czwartek, pi atek, sobota, ni edzi el a ) ; var -9- Nauka programowania... góły języka). Jest to książka do nauki programowania, a nie praca poświgcona samemu językowi. Pełny opis języka ltzrbo Pascal można znaleźć w pracach [6,13,14]. Materiał przedstawiony w książce można podzielić na kilka części. Pierwsza jest poświęcona uzupe#ieniu podstawowych wiadomości dotyczących typów danych, wykorzystania tablic trzywymiarowych oraz projektowaniu modułów (rozdz. 2,3,4). Część druga omawia algorytmy stosowane przy przetwarzaniu plików i techniki stosowane w operacjach na zbiorach oraz rekordach (rozdz. 5-8). Następna część jest poświgcona projektowaniu algorytmów rekurencyjnych (rozdz. 9). Kolejna część podąje techniki programowania z wykorzystaniem wskaźników (rozdz. 10). Część piąta zawiera wprowadzenie do programowania obiektowego (rozdz. 11). Ostatnia bardzo obszerna część książki to omówienie technik stosowanych przy przetwarzaniu list, stosów, kolejek i drzew binarnych z jednoczesnym wykorzystaniem programowania obiektowego (rozdz.12). W książce znajduje się wiele programów wraz z zaprojektowanymi algorytmami. Podobnie jak w pracy [20] algorytmy są zapisywane nąjpierw w pseudo-kodzie. Zamieszczone przykłady są już o wiele trudniejsze niż podane w [20], większość z nich bazuje na klasycznych algorytmach wykorzystywanych w nauce prograrnowanie i mających jednocześnie duże zastosowanie praktyczne. Można tu wymienić zwłaszcza algorytmy sortowania szybkiego i przez scalanie, programy wykorzystujące algorytm nawrotu oraz algorytmy stosowane przy przetwarzaniu list oraz drzew binarnych. Projektowanie algorytmów powinno przebiegać w oparciu o systematyczne techniki ich projektowania. Do podstawowych technik należą projektowanie wst#pujące i zstępujące. Projektowanie wstępujące polega na rozpoczęciu projektowania od wyodrębnienia w danym algorytmie niepodzielnych części, które następnie łączy się w większe jednostki tak długo, aż otrzymamy rozwiązanie danego próblemu. Można je określić jako projektowanie od szczegółu do ogółu. Natomiast projektowanie zstępujące polega na zaprojektowaniu algorytmu w pierwszym etapie bez rozpatrywania szczegółów. Częściami składowymi algorytmu są bloki funkcjonalne realizujące ściśle określone operacje, które następnie w dalszej fazie projektowania uściśla się tak długo, aż dojdzie się do operacji możliwych do zaprojektowania bezpośrednio. Określamy je jako projektowanie od ogółu do szczegółu. W niniejszej książce będziemy wykorzystywać obie wymienione techniki projektowania algorytmów. Mamy nadzieję, że Czytelnik bez trudu zorientuje się, ktńra technika została wykorzystana w konkretnym przypadku. -6- 1. Wstęp Cały podany materiał został wyłożony w sposób jak najbardziej czytelny i przejrzysty, zamieszczone programy są bogato skomentowane i opisane, a wszystkie trudniejsze algorytmy są zapisane w pseudo-kodzie. Po każdym rozdziale są podane przykładowe zadania utrwaląjące wyłożony materiał. Książka jest przeznaczona dla wszystkich osób interesujących sig programowaniem. Może być także wykorzystywana jako podrgcznik do nauki programowania przez studentów wyższych uczelni. -7- Nauka programowania... 9. Rekurencj a. . 97 9.1. Wprowadzenie . 97 9.2. Algorytmy z powrotami . . 101 9.3. Algorytmy sortowania 116 9.4. Zadania 128 10. Wskaźniki. . 13o 10.1. Wprowadzenie 130 10.2. Operacje na wskaźnikach i zmiennych dynamicznych 133 10.3. Tablice wskaźników 134 10.4. Zadania 140 11. Podstawy programowania obiektowego 14 11.1. Wprowadzenie 141 11.2. Dziedziczenie 147 11.3. Metody wirtualne. 155 11.4. Rozszerzalność obiektów. 159 11.5. Klasa do tworzenia menu programu. . 161 12. Programowanie dynamicznych struktur danych z wykorzystaniem programowania obiektowego 12.1. Listy 173 12.2. Stosy 241 12.3. Kolejki 249 12.4- Drzewa binarne. . 255 12.5. Zadania 276 13; Podsumowanie . 279 LITERATURA UZUPEŁNIAJĄCA. 280 SKOftOWIDZ 282 -4- Rozdział wsT#P Niniejsza książka jest drugą z kolei w serii poświgconej nauce programowania. Pierwsza to "Nauka programowania dla początkujących" [20]. Zapoznanie się z tą książką lub inną zawierającą podobny materiał oraz rozwiązanie pewnej liczby przykładów jest niezbgdne do rozpoczęcia studiowania niniejszej pozycji. Praca ta może być również wykorzystywanaů przez bardziej zaawansowanego Czytelnika, który chce poznać techniki programowania obiektowego. Jak wskazuje sam tytuł, książka ta jest poświęcona nauce programowania na poziomie nieco wyższym niż podstawowy. Zakładamy, że Czytelnik posiada już podstawową umiejętność programowania i potrafi wykorzystać instrukcje sterujące, tablice oraz podprogramy. Obecnie postaramy się nauczyć Czytelnika programować z wykorzystaniem wszystkich mechanizmów dostępnych w języku Pascal łącznie z# programowaniem obiektowym. Podobnie jak w pracy [20] jako język do nauki programowania wybraliśmy jgzyk l#zrbo Pascal w wersji 6.0 (możliwość programowania obiektowego jest ćlostgpna od wersji 5.5 jgzyka). Drogi Czytelniku, numer wersji danego języka przy nauce programowania naprawdg nie jest istotny Ważne jest jedynie, aby dana wersja posiadała wszystkie wykładane mechanizmy. Ucząc się programować, nie należy zatem przejmować się tym, że ukazała sig już nowsza wersja języka. Należy podkreślić, że książka nie zawiera pełnego opisu języka Ztzrbo Pascal (nie zostały omowione mniej istotne w nauce programowania szcze -5- O Copyright by Anna Struzińska-Walczak, Krzysztof Walczak Warszawa 1994 "Nauka programowania dla już nie całkiem początkujących" Autorzy: Anna Struzińska-Walczak, Krzysztof Walczak Książka zawiera wykład nauki programowania na poziomie nieco wyższym niż podstawowy. Jest ona kontunuacją pracy "Nauka programowania dla początkujących". W książce są wyjaśnione wszystkie techniki programowania możliwe do wykorzystania w jgzyku Pascal łącznie z obszernym omówieniem programowania obiektowego. Wykład został poprowadzony w sposób jak nąjbardziej czytelny i przejrzysty, zamieszczone programy są bogato skomentowane i opisane, a trudniejsze algorytmy są zapisane w pseudokodzie. Książka jest przeznaczona dla wszystkich osób interesujących sig programowaniem. Może być także wykorzystywana przez student Aw wyższych uczelni jako podrgcznik do nauki programowania. Uwaga: W wydawnictwie można zakupić dyskietkg zawierającą kody źródłowe programów zawartych w książce. Wydawca Wydawnictwo W & W Adres korespondencyjny ul. Tołstoja 1/13 Ol-910 Warszawa tel. 35 90 24 ISBN 83-900519-4-X SPIS TRESCI l. Wstęp 2. Proste typy danych 5 8 3. Tablice ( uzupełnienie ). . . . . . . . . . 3.1. Tablice trzywymiarowe. . . 11 3.2. Zadania. . 16 4. Moduły 17 5. Pliki tekstowe i operacje na tekstach . . . . . 22 5.1. Pliki input i output . 22 5.2. Pliki tekstowe. .. 23 5.3. Wyprowadzanie danych na drukarkę. . 38 5.4. Operacje na tekstach. . 39 5.5. Zadania. 6. Pliki elementowe. . . . . 7.Zbiory........ .......... 51 7.1. Wprowadzenie. . ",# . 51 7.2. Operacje na zbiorach . 53 7.3. Podstawowe algorytmy. . . . 55 7.4. Zadania . 67 8.ftekordy. ......... ................... s9 8.1. Wprowadzenie . 69 8.2. Instrukcja with . 74 8.3. Tablice rekordów. . . 77 8.4. Zadania . 95 Anna Struzińska-Walczak Krzysztof Walczak PROG OWANIA DLA... #UZ NIE CA#KIEM POCZ#TKU##CYCH Wydawnictwo W & W