Dynamiczne struktury danych w języku Turbo Pascal Dynamiczne struktury danych w języku Turbo Pascal Rodzaje zmiennych Typy wskaźnikowe. Wskaźniki Typ wskaźnikowy Pointer Dynamiczny przydział pamięci Obsługa braku pamięci na stercie Czas życia zmiennych dynamicznych Procedura Getmem Operacje arytmetyczne na wskaźnikach Typ rekordowy Organizacja listy jednokierunkowej Podstawowe operacje wykonywane na liście jednokierunkowej Sortowanie listy jednokierunkowej Stosy i kolejki Lista dwukierunkowa Zadania do samodzielnego rozwiązania Rodzaje zmiennych W języku Pascal zmienne dzielą się na statyczne i dynamiczne. Zmienna statyczna tworzona jest w trakcie kompilacji programu i istnieje do momentu jego zakończenia lub też do momentu zakończenia funkcji lub procedury, w której została zadeklarowana. Program w momencie uruchamiania otrzymuje od systemu operacyjnego fragment pamięci o rozmiarze 64KB przeznaczony na dane statyczne - fragment ten nazywamy segmentem danych. W segmencie tym są umieszczane wszystkie zmienne globalne programu a także zmienne zadeklarowane lokalnie w procedurach i funkcjach. Łączny rozmiar tych zmiennych nie może przekroczyć rozmiaru segmentu danych, tj. 65536 bajtów. Zmienną dynamiczną nazywamy zmienną utworzoną w trakcie wykonywania programu. Zmienne te tworzone są na tzw. stercie, której rozmiar jest na ogół różny i może wynosić nawet do 600KB. W odróżnieniu od segmentu danych zmienną utworzoną na stercie można w dowolnym momencie usunąć, zwalniając w ten sposób niepotrzebnie zajmowaną pamięć. Typy wskaźnikowe. Wskaźniki Do pracy ze zmiennymi dynamicznymi używa się typów wskaźnikowych. Elementami tych typów są zmienne wskaźnikowe, które krótko nazywamy wskaźnikami. Wskaźnik jest adresem pewnej zmiennej określonego typu. Mówiąc o wskaźniku zawsze mamy na myśli zmienną, której adres zawiera wskaźnik. Ze względu na różny typ zmiennych mówimy o wskaźniku na liczbę typu Byte, wskaźniku na liczbę rzeczywistą Real, wskaźniku na łańcuch typu String itd - zawsze ze wskaźnikiem związany jest typ zmiennej na którą wskazuje dany wskaźnik. Używamy tu sformułowania "wskaźnik wskazuje na zmienną" gdyż w rzeczywistości zawiera on adres tej zmniennej. Adresy zmiennych mają swoją specyficzną budowę, która wynika ze sposobu adresacji pamięci w komputerach PC. Pamięć ta jest dzielona na segmenty o rozmiarze 64KB (65536). Segment taki zawiera 65536 bajtów (komórek) pamięci. Zarówno segmenty pamięci jak również wszystkie komórki pamięci w danym segmencie są numerowane od zera, co oznacza że do zapamietania adresu segmentu wystarcza liczba typu Word, oraz za pomocą takiej liczby można określić adres komórki pamięci w danym segmencie. Drugi z tych adresów, czyli położenie komórki w segmencie nazywamy ofsetem lub przesunięciem. Adres komórki pamięci znajdującej się w segmencie Seg i przesuniętej względem początku tego segmentu o Ofs komórek zapisujemy najczęściej w postaci $Seg:$Ofs, przy czym obie wartości zapisane są szesnastkowo. Standardowe funkcje języka Seg(Zmienna) Ofs(Zmienna) zwracają w postaci liczby typu Word odpowiednio segment i ofset podanej jako argument zmiennej. Przykład 1 Napisz program, który wypisze adresy dwóch zadeklarowanych w nim zmiennych oraz adres dowolnej funkcji lub procedury. (dop) Program Adresy; Uses Crt; Procedure Pusta; Begin End; Var A : Integer; B : Real; Begin ClrScr; WriteLn('Adres zmiennej A = ', Seg(A), ':', Ofs(A)); WriteLn('Adres zmiennej B = ', Seg(B), ':', Ofs(B)); WriteLn('Adres procedury Pusta = ', Seg(Pusta), ':', Ofs(Pusta)); ReadKey; End. Deklaracja zmiennej wskaźnikowej ma postać: Var Wsk : ^TYP; gdzie TYP jest dowolnym typem standardowym lub zdefiniowanym przez programistę. Niech dany będzie fragment programu: Var A, B : Integer; Wsk : ^Integer; Begin ... A:=-7; B:=12; Wsk:=@A; WriteLn('Wartość zmiennej A=', Wsk^); Wsk:=Addr(B); WriteLn('Wartość zmiennej B=', Wsk^); ... End. Wykonanie powyższego fragmentu spowoduje wydrukowanie liczb -7 oraz 12, czyli kolejno wartości zmiennych A i B. Początkowo zmiennej wskaźnikowej Wsk został przypisany adres zmiennej A za pomocą tzw. operatora pobrania adresu @. Po wykonaniu przypisania zmienna wskaźnikowa Wsk wskazuje na zmienną A. Wyrażenie Wsk^ jest w języku Pascal odwołaniem do zmiennej, na którą wskazuje dany wskaźnik - w tym wypadku jest to odwołanie do zmiennej A. Adres zmiennej można przypisać wskaźnikowi również za pomocą standardowej funkcji Addr. Po wykonaniu przypisania Wsk:=Addr(B) zmienna wskaźnikowa Wsk wskazuje na zmienną B i w tym momencie odwołanie Wsk^ jest równoznaczne z odwołaniem do zmiennej B. Typ wskaźnikowy Pointer W Pascalu istnieje uniwersalny typ wskaźnikowy Pointer, który jest zgodny z każdym innym typem wskaźnikowym. Oznacza to, że zmiennej wskaźnikowej typu Pointer można przypisać wartość dowolnego innego wskaźnika i odwrotnie, każdemu wskaźnikowi można przypisać wartość wskaźnika typu Pointer. Standardowa funkcja Ptr(Seg, Ofs) : Pointer; tworzy wskaźnik typu Pointer wskazujący komórkę pamięci w podanym segmencie i o wskazanym przesunięciu. Mając zmienną N:Byte oraz wskaźnik Wsk:^Byte można wskaźnikowi Wsk przypisać adres zmiennej N również w następujący sposób: Wsk:=Ptr(Seg(N), Ofs(N)); Przykład Przyjmijmy następującą definicję łańcucha: "Łańcuch reprezentowany jest przez zmienną typu ^Char. Wartość Nil tej zmiennej nazywamy łańcuchem pustym. Łańcuch tworzą wszystkie znaki poczynając od znaku wskazywanego zmienną reprezentującą łańcuch aż do znaku #0 (znak #0 nie jest częścią łańcucha). Napisz program, który wygeneruje losowy początek łańcucha, wydrukuje wszystkie znaki łańcucha o kodach od 32 oraz poda jego długość. Program Lancuch; Uses Crt; Var N : LongInt; Wsk : ^Char; Begin ClrScr; Randomize; Wsk:=Ptr(Random(65535), Random(65535)); N:=0; If Wsk<>Nil Then While Wsk^<>#0 Do Begin If Wsk^>=#32 Then Write(Wsk^); Inc(Wsk); Inc(N); End; WriteLn; WriteLn('Długość łańcucha = ', N); WriteLn('Naciśnij jakiś klawisz...'); While KeyPressed Do ReadKey; ReadKey; While KeyPressed Do ReadKey; End. Dynamiczny przydział pamięci Wskaźnikowi po zadeklarowaniu można przypisać adres dowolnej istniejącej zmiennej identycznego typu jak typ wskaźnika. Niezależnie od typu wskaźnika zawsze można mu przypisać tzw. adres pusty, który w języku Pascal oznaczamy słowem Nil - wskaźnik o wartości Nil nie wskazuje niczego. Program w dowolnym momencie może utworzyć nową zmienną i jej adres przypisać zmiennej wskaźnikowej. Tak powstałą zmienną nazywamy zmienną dynamiczną. Standardowa procedura New(Zmienna wskaźnikowa) tworzy na stercie nową zmienną typu identycznego z typem wskaźnika i jej adres przypisuje zmiennej wskaźnikowej. Po poprawnym wykonaniu procedury New zmienna wskaźnikowa zawiera adres utworzonej zmiennej, jeżeli jednak utworzenie zmiennej dynamicznej nie jest możliwe z powodu braku pamięci na stercie, to następuje błąd wykonania programu i w konsekwencji jego przerwanie. W związku z tym należy przed każdą próbą przydziału pamięci sprawdzać możliwość wykonania tej operacji za pomocą funkcji bezparametrowej MaxAvail, wartością której jest ilość możliwej do przydzielenia przez procedurę New pamięci. Sposób postępowania ilustruje poniższy przykład: Var Wsk : ^Integer; Begin ... If MaxAvail>=SizeOf(Integer) Then New(Wsk) Else Begin obsługa błędu End; ... End. Standardowa funkcja SizeOf zwraca rozmiar zmiennej podanego jako argument typu w bajtach. Przykład 2 Dana jest liczba N typu 1..100 oraz ciąg N łańcuchów typu String. Napisz program, który wyznaczy ilość liter alfabetu we wszystkich napisach. (dst) Program IloscLiter; Uses Crt; Var Napisy : Array[1..100] Of ^String; I, J, N : 1..100; Ilosc: Word; Begin ClrScr; Repeat Write('Podaj N='); ReadLn(N); Until (N>0) And (N<101); For I:=1 To N Do If MaxAvail<SizeOf(String) Then Begin WriteLn('Brak pamięci potrzebnej do wykonania.'); Napisy[I]:=Nil; End Else Begin New(Napisy[I]); Write('Podaj napis numer ', I,' = '); ReadLn(Napisy[I]^); End; Ilosc:=0; For I:=1 To N Do If Napisy[I]<>Nil Then For J:=1 To Length(Napisy[I]^) Do If Napisy[I]^[J] In ['a'..'z', 'A'..'Z'] Then Inc(Ilosc); WriteLn('Napisy zawierały ', Ilosc, ' liter.'); WriteLn('Naciśnij jakiś klawisz...'); While KeyPressed Do ReadKey; ReadKey; While KeyPressed Do ReadKey; End. W powyższym przykładzie znana jest maksymalna liczba wszystkich napisów równa 100, faktyczna liczba wprowadzonych napisów jest podawana dopiero w momencie wykonywania programu. Gdyby zadeklarować tablicę 100 napisów, to zajęłaby ona 256*100=25600 bajtów, czyli prawie połowę pamięci przeznaczonej na dane statyczne. Zamiast tego w programie zadeklarowano tablicę 100 wskaźników, która zajmuje zaledwie 200 bajtów, zaś pamięć dla napisów przydzielana jest podczas wykonywania programu. Dzięki takiemu postępowaniu program przydzieli tylko tyle pamięci ile jest niezbędne do prawidłowego wykonania programu. Obsługa braku pamięci na stercie Standardową reakcją na brak wymaganej do przydzielenia pamięci jest błąd wykonania programu. Błąd ten można obsłużyć programowo - wymaga to zdefiniowania w programie funkcji: Function Nazwa(Rozmiar : Word) : Integer; Far; Begin Nazwa:=1; End; której nazwa jest dowolna - istotne jest tylko przypisanie liczby 1 jako wartości funkcji. Ponadto funkcja ta musi zostać zadeklarowana jako "daleka" ze słowem kluczowym Far. Adres tak zdefiniowanej funkcji należy w programie przypisać standardowej zmiennej HeapError za pomocą instrukcji przypisania: ... HeapError:=@Nazwa; ... Po wykonaniu tych dwóch czynności program nie będzie kontrolował błędu braku pamięci na stercie - w momencie wystąpienia takiej sytuacji wskaźnikowi będącemu argumentem funkcji New będzie przypisywana wartość Nil. Dzięki temu można nie wywoływać funkcji MaxAvail przed przydziałem pamięci, a jedynie sprawdzić wartość wskaźnika po wykonaniu procedury New: Function Sterta(X : Word) : Integer; Far; Begin Sterta:=1; End; Var Wsk : ^Integer; Begin ... HeapError:=@Sterta; ... New(Wsk); If Wsk=Nil Then Begin obsługa błędu End; ... End. Czas życia zmiennych dynamicznych Zmienna dynamiczna utworzona procedurą New istnieje do momentu usunięcia jej przez programistę - w odróżnieniu od zmiennych statycznych zmienne dynamiczne nigdy nie są usuwane automatycznie. Usunięcie zmiennej wykonuje się procedurą Dispose(Zmienna wskaźnikowa) Należy pamietać, że jeżeli program utworzy zmienną dynamiczną, której adres zostanie zapamietany w zmiennej wskaźnikowej, a następniej przed usunięciem tej zmiennej dokona zmiany wskaźnika, to jej usunięcie nie będzie już możliwe - nie będzie bowiem znany adres tej zmiennej. W poniższym przykładzie: ... New(Wsk); ReadLn(Wsk^); If Wsk^=0 Then Wsk:=Nil; ... tworzona jest zmienna, której adres przypisywany jest zmiennej wskaźnikowej Wsk. Następnie następuje odczyt wartości liczbowej do tej zmiennej, po czym wskaźnik Wsk może otrzymać adres pusty Nil. Na skutek wykonania tej instrukcji program "gubi" adres utworzonej zmiennej - zmienna ta będzie zajmować pamięć do czasu zakończenia programu. Procedura GetMem Pamięć na stercie można również przydzielić procedurą GetMem(Zmienna wskaźnikowa, Rozmiar) w której argument rozmiar określa ilość potrzebnej do przydzielenia pamięci. Przed wykonaniem procedury należy sprawdzić ilość dostępnej pamięci funkcją MaxAvail lub też jeżeli program obsługuje błąd braku pamięci na stercie, wartość wskaźnika po wywołaniu procedury. Pamięć przydzieloną procedurą GetMem zwalnia się za pomocą procedury FreeMem(Zmienna wskaźnikowa, Rozmiar) gdzie argument rozmiar powinien być identyczny z argumentem użytym podczas przydziału pamięci. Procedur New i Dispose oraz GetMem i FreeMem nie wolno ze sobą mieszać - pamięć przydzielona przez New musi być zwolniona przez Dispose, analogicznie pamięć przydzielona przez GetMem należy zwolnić procedurą FreeMem. Operacje arytmetyczne na wkaźnikach Wskaźniki można ze sobą porównywać za pomocą operatorów = oraz <>. Dwa wskaźniki uważamy za równe, gdy wskazują na ten sam obszar pamięci lub gdy oba mają wartość Nil. Dozwolona jest również operacja zwiększania i zmniejszania wskaźnika o liczbę całkowitą za pomocą procedur Inc i Dec. Po wykonaniu instrukcji Inc(Wsk); wskaźnik Wsk wskazuje na kolejny element w pamięci typu identycznego z typem wskaźnika, tzn. jeżeli Wsk jest typu ^Word, to dodanie do wartości wskaźnika liczby 1 powoduje przesunięcie wskaźnika na kolejną liczbę typu Word, czyli o dwa bajty. Ogólnie, jeżeli Wsk jest typu ^TYP, to zwiekszenie wskaźnika o 1 procedurą Inc przesuwa wskaźnik o SizeOf(TYP) bajtów. Analogiczne zasady obowiązują podczas zmniejszania wskaźnika o liczbę całkowitą procedurą Dec. Przykład 3 Dana jest liczba naturalna N typu 1..100 i ciąg N liczb typu Integer. Napisz program, który wyznaczy liczbę najmniej różniącą się od średniej tego ciągu. (dst) Program MinSrednia; Uses Crt; Function Srednia(Tab : Pointer; N : Word) : Real; Var Wsk : ^Integer; Suma : Longint; I : Word; Begin Suma:=0; Wsk:=Tab; I:=N; While I>0 Do Begin Inc(Suma, Wsk^); Inc(Wsk); Dec(I); End; Srednia:=Suma/N; End; Function MinRoznica(Tab : Pointer; N : Word; Sr : Real) : Integer; Var Wsk : ^Integer; Wynik : Integer; Begin Wsk:=Tab; Wynik:=Wsk^; While N>1 Do Begin Inc(Wsk); Dec(N); If Abs(Sr-Wsk^)<Abs(Sr-Wynik) Then Wynik:=Wsk^; End; MinRoznica:=Wynik; End; Var T, Wsk : ^Integer; N, I : Word; Begin ClrScr; Repeat Write('Podaj ilość liczb N='); ReadLn(N); Until (N>=1) And (N<=100); If MaxAvail<N*SizeOf(Integer) Then Begin WriteLn('Brak pamięci potrzebnej do wykonania programu.'); WriteLn('Potrzebne:',N*SizeOf(Integer),' Dostępne:', MaxAvail); WriteLn('Nacisnij jakiś klawisz...'); While KeyPressed Do ReadKey; ReadKey; While KeyPressed Do ReadKey; Halt; End; GetMem(T, N*SizeOf(Integer)); Wsk:=T; For I:=1 To N Do Begin Write('Liczba numer ', I, ' = '); ReadLn(Wsk^); Inc(Wsk); End; WriteLn('Liczba najmniej różniąca sie od średniej : ', MinRoznica(T, N, Srednia(T, N))); WriteLn('Nacisnij jakiś klawisz...'); While KeyPressed Do ReadKey; ReadKey; While KeyPressed Do ReadKey; End. Typ rekordowy Rekord jest złożoną strukturą danych składającą się z pól o dowolnych typach, do których odwołania następują poprzez nazwę pola. Definicja typu rekordowego ma postać: Type Nazwa = Record pole01, pole02, ... : Typ1; pole11, pole12, ... : Typ2; ... polen1, polen2, ... : Typn; End; Definicja typu opisującego ucznia mogłaby mieć postać: Type Uczen = Record Nazwisko, Imie : String[30]; Adres : String[100]; Wiek : 15..20; Klasa : String[2]; End; Var A, B : Uczen; Odwołania do pól rekordu wykonuje się za pomocą operatora wyboru pola '.', np. A.Nazwisko:='Nowak', WriteLn(B.Wiek), itd. Obowiązuje przy tym następująca zasada: jeżeli X oznacza zmienną rekordową, Y jest nazwą pola tego rekordu typu TYP, to wyrażenie X.Y jest odwołaniem do pola Y rekordu X i traktowane jest jak zmienna typu TYP. Zatem wyrażenie A.Nazwisko jest zmienną typu String[30] a wyrażenie B.Wiek zmienną typu 15..20. Organizacja listy jednokierunkowej Niech dana będzie definicja typu rekordowego Skladnik: Type WSkladnik = ^Skladnik; Skladnik = Record X : Integer; Next : WSkladnik; End; Rekord Skladnik zawiera dwa pola: pole X typu Integer oraz pole wskaźnikowe Next typu WSkladnik, czyli wskaźnik na rekord Skladnik. Załóżmy, że w programie zadeklarowana jest zmienna Start typu wskaźnik na Skladnik, czyli Start : WSkladnik. Program może utworzyć dynamicznie zmienną rekordową, jej adres przypisać zmiennej wskaźnikowej Start i wczytać do tej zmiennej liczbę typu Integer: ... New(Start); Start^.Next:=Nil; Write('Podaj liczbę całkowitą = '); ReadLn(Start^.X); ... Ponieważ pole Next rekordu może zawieraż adres rekordu typu Skladnik można utworzyć dynamicznie kolejny rekord przypisując jego adres polu Next utworzonego przez chwilą rekordu: ... New(Start^.Next); Start^.Next^.Next:=Nil; Write('Podaj liczbę całkowitą = '); ReadLn(Start^.Next^.X); ... Powstała w ten sposób struktura zawierająca dwa rekordy, przy czym adres pierwszego pamiętany jest w zmiennej wskaźnikowej Start, adres drugiego w polu Next pierwszego rekordu. Wyrażenie Start jest typu WSkladnik i jest adresem pierwszego z rekordów, wyrażenie Start^.Next również jest typu WSkladnik i jest adresem rekordu drugiego. Proces ten można powtórzyć po raz trzeci: ... New(Start^.Next^.Next); Start^.Next^.Next^.Next:=Nil; Write('Podaj liczbę całkowitą = '); ReadLn(Start^.Next^.Next^.X); ... W ten sposób zostanie utworzony trzeci rekord, którego adres będzie pamiętany w polu Next drugiego z rekordów. Możemy utworzyć kolejny czwarty rekord wpisując jego adres w pole Next rekordu trzeciego, rekord piąty wpisując jego adres w pole Next rekordu czwartego, itd. Przyjmijmy teraz, że została utworzona tego typu struktura zawierająca 20 połączonych ze sobą rekordów. Każdy z rekordów zawiera jedną liczbę całkowitą typu Integer. Program może w każdej chwili odwołać się do dowolnej z tych liczb, choć odwołanie takie może być kłopotliwe - odwołanie do szóstej liczby miałoby postać: Start^.Next^.Next^.Next^.Next^.Next^.X - chcąc odwołać się do liczby o numerze 20 należałoby podać 19 razy wyrażenie Next^. Szczególna uwagę należy jednak poświęcić pamięci zajmowanej przez liczby w segmencie danych. Do zapamiętania owych 20 liczb użyto jednej zmiennej statycznej, a mianowicie wskaźnika Start, który zajmuje zaledwie 2 bajty segmentu danych. Oczywistym jest, że zwiększając ilość liczb w utworzonej strukturze np. do 200 nie zajmujemy żadnego dodatkowego bajtu w segmencie danych - wszystkie te liczby zostaną zapamietane dzieki użyciu jednego dwubajtowego wskaźnika Start : WSkladnik. Tak utworzoną strukturę nazywamy listą jednokierunkową (liniową). Rekord, który został użyty do utworzenia tej listy nazywamy składnikiem listy, zaś jej pierwszy składnik początkiem listy. Bardzo ważnym elementem listy jest pole Next o wartości Nil. Pamiętając adres pierwszego składnika listy mamy dostęp do wszystkich jej składników musimy jednak wiedzieć w którym miejscu lista się kończy. Koniec ten jest wyznaczany właśnie przez pole Next o wartości Nil. Ostatni składnik listy ma pole Next równe Nil, wszystkie poprzednie składniki przechowują w tym polu adres składnika następnego. Nazwa lista jednokierunkowa wynika ze sposobu łączenia poszczególnych składników listy: mając adres N-tego składnika można ustalić adres każdego ze składników o numerach N+1, N+2, N+3, itd., nie jest natomiast możliwe ustalenie adresu składnika wcześniejszego np. N-1. Po liście możemy zatem poruszać się tylko w jednym kierunku - od początku do końca listy, przejście w drugą stroną nie jest możliwe. Podstawowe operacje wykonywane na liście jednokierunkowej Poniższe przykłady zawierają definicje kilku podstawowych funkcji służących do zarządzania listą jednokierunkową. Za składnik listy przyjęto zdefiniowany powyżej rekord typu Skladnik. Przykład 4 Zdefiniować funkcję LRozmiar wartością której będzie ilość składników listy utworzonej przy pomocy rekordu typu Skladnik. (dst) Function LRozmiar(Start : WSkladnik) : Word; Var Wynik : Word; Begin Wynik:=0; While Start<>Nil Do Begin Start:=Start^.Next; Inc(Wynik); End; LRozmiar:=Wynik; End; Przykład 5 Zdefiniować funkcję LAdres która zwróci adres N-tego składnika na liście lub adres pusty Nil jeżeli lista nie zawiera takiego składnika. (dst) Function LAdres(Start : WSkladnik; N : Word) : WSkladnik; Begin If (N<1) Or (N>LRozmiar(Start)) Then LAdres:=Nil Else Begin While N>1 Do Begin Start:=Start^.Next; Dec(N); End; LAdres:=Start; End; End; Przykład 6 Zdefiniować funkcję LWar wartością której będzie N-ta liczba listy utworzonej przy pomocy rekordu Skladnik lub zero jeżeli lista nie zawiera składnika o takim numerze. (dst) Function LWar(Start : WSkladnik; N : Word) : Integer; Var Adr : WSkladnik; Begin Adr:=LAdres(Start, N); If Adr=Nil Then LWar:=0 Else LWar:=Adr^.X; End; Przykład 7 Zdefiniować funkcję LDodaj o wartościach logicznych, która doda do listy utworzonej przy pomocy rekordu Skladnik kolejną liczbę na jej końcu. Funkcja powinna zwrócić True w przypadku powodzenia operacji, False w przeciwnym wypadku. (dst) Function LDodaj(Var Start : WSkladnik; Liczba : Integer) : Boolean; Var Adr : WSkladnik; Begin If MaxAvail<SizeOf(Adr^) Then LDodaj:=False Else Begin New(Adr); Adr^.X:=Liczba; Adr^.Next:=Nil; If Start=Nil Then Start:=Adr Else LAdres(Start, LRozmiar(Start))^.Next:=Adr; LDodaj:=True; End; End; Przykład 8 Zdefiniować procedurę LUsunPierw, która usunie w listy utworzonej przy pomocy rekordu Skladnik pierwszy jej skladnik. (dst) Procedure LUsunPierw(Var Start : WSkladnik); Var Adr : WSkladnik; Begin If Start=Nil Then Exit; Adr:=Start; Start:=Start^.Next; Dispose(Adr); End; Sortowanie listy Przejdziemy teraz do zagadnienia sortowania listy. Listę zawierającą porównywalne elementy można posortować podobnie jak tablicę używając algorytmu sortowania bąbelkowego. W przypadku tablicy podstawową operacją wykonywaną na elementach tablicy jest zamiana miejscami dwóch kolejnych elementów. W ten sam sposób można posortować listę zamieniając miejscami dwie liczby przechowywane na dwóch kolejnych składnikach. Druga z metod polega na zmianie kolejności składników, tzn. jeżeli sortujemy listę rosnąco i liczba przechowywana w składniku I jest większa niż liczba przechowywana w składniku I+1, to zamieniamy miejscami składniki tak aby następnym składnikiem po składniku I-1 był składnik I+1, zaś następnym składnikiem po składniku I+1 składnik I. Przykład 9 Zdefiniować procedurę LZamien, która dla argumentu N typu Word zamieni miejscami dwa składniki listy: składnik o numerze N ze składnikiem o numerze N+1. (bdb) Procedure LZamien(Var Start : WSkladnik; N : Word); Var Adr, AdrNast, AdrPop : WSkladnik; Begin If N=0 Then N:=1; If N>=LRozmiar(Start) Then Exit; Adr:=LAdres(Start, N); AdrNast:=LAdres(Start, N+1); Adr^.Next:=AdrNast^.Next; AdrNast^.Next:=Adr; If N=1 Then Start:=AdrNast Else Begin AdrPop:=LAdres(Start, N-1); AdrPop^.Next:=AdrNast; End; End; Przykład 10 Dany jet ciąg liczb całkowitych zakończony liczbą zero, które nie jest elementem ciągu. Napisz program, który wydrukuje liczby tego ciągu w kolejności rosnącej. (bdb) Program SortujListe; Uses Crt; { ... Tutaj należy umieścić definicję wszystkich funkcji i procedur ... } Var Start : WSkladnik; X : Integer; I, J, Ilosc : Word; Begin ClrScr; Start:=Nil; Write('Podaj pierwszą liczbę ciągu = '); ReadLn(X); If X<>0 Then If Not LDodaj(Start, X) Then Begin WriteLn('Brak pamięci.'); Halt; End; While X<>0 Do Begin Write('Podaj kolejną liczbę = '); ReadLn(X); If X<>0 Then If Not LDodaj(Start, X) Then Begin WriteLn('Brak pamięci.'); Halt; End; End; If LRozmiar(Start)=0 Then WriteLn('Ciag nie zawiera żadnych liczb.') Else Begin Ilosc:=LRozmiar(Start); For I:=1 To Ilosc Do For J:=1 To Ilosc-I Do If LAdres(Start, J)^.X>LAdres(Start, J+1)^.X Then LZamien(Start, J); WriteLn('Liczby ciągu ułożone rosnąco:'); For I:=1 To Ilosc Do WriteLn('Liczba numer ', I, ' = ', LWar(Start, I)); End; WriteLn('Naciśnij jakiś klawisz...'); While KeyPressed Do ReadKey; ReadKey; While KeyPressed Do ReadKey; End. Stosy i kolejki Program może przetwarzać listę jednokierunkową w pewien specyficzny sposób. Jeżeli program dodaje kolejny składnik zawsze na końcu listy, zaś po przetworzeniu usuwa z listy jej pierwszy składnik, to taką strukturę nazywamy kolejką. Nazwa kolejki wywodzi się z kolejki w sklepie, w której obowiązuje zasada, że jako pierwszy opuszcza kolejkę ten, kto przebywa w niej najdłużej. Zasadę tą często formułuje się krótko: pierwszy przyszedł, pierwszy wychodzi. Jeżeli program przetwarzając listę jednokierunkową dodaje do niej kolejne składniki zawsze na początku, zaś po przetworzeniu usuwa z listy jej pierwszy składnik, to taką strukturę nazywamy stosem. Stos można sobie wyobrazić jako słupek ułożonych jedna na drugiej monet - zawsze można dołożyć monetę na szczycie stosu a także można usunąć tylko monetę znajdującą się na szczycie. W organizacji stosu obowiązuje zasada ostatni przyszedł, pierwszy wychodzi. Lista dwukierunkowa Umieszczenie w rekordzie pola o nazwie Next zawierającego adres kolejnego składnika listy pozwala na poruszanie się po jej składnikach w jednym kierunku. Jeżeli oprócz pola Next rekord bedzie zawierał pole o nazwie Last zawierające adres składnika poprzedniego, to taką strukturę nazywamy listą dwukierunkową. Program przetwarzając listę dwukierunkową pamięta dwa wskaźniki: adres pierwszego jej elementu oraz adres elementu ostatniego. Pole Next pozwala na przejście po wszystkich składnikach od pierwszego do ostatniego, pole Last na przejście od składnika ostatniego do pierwszego. Do utworzenia dwukierunkowej listy liczb całkowitych potrzebne są następujące typy danych: Type WSkladnik2 = ^Skladnik2; Skladnik2 = Record X : Integer; Last, Next : WSkladnik2; End; Dla listy dwukierunkowej można zdefiniować analogiczne funkcje i procedury jak dla listy jednokierunkowej. W tym wypadku każda z funkcji i procedur powinna otrzymać jako argumenty dwa wskaźniki: Start i Koniec wskazujące odpowiednio adres pierwszego i ostatniego elementu listy. Zadania do samodzielnego rozwiązania Napisz program, który wydrukuje ilość dostępnej na stercie pamięci, utworzy dynamiczną zmienną typu Byte, po czym ponownie wydrukuje ilość dostępnej pamięci. (dop) Napisz program, który zużyje całą dostępną na stercie pamięć tworząc dynamiczne zmienne typu Byte i wydrukuje ilość utworzonych zmiennych. Następnie typ Bajt zamień na typ Word. Na podstawie wyników oceń prawdziwość następującego stwierdzenia: "Liczba możliwych do utworzenia dynamicznie zmiennych typu Word jest dwa razy mniejsza niż liczba zmiennych typu Byte". (dop) Dana jest liczba naturalna N typu 1..100 oraz ciąg N liczb typy Integer. Napisz program, który wydrukuje liczbę najwięcej różniącą się od średniej liczb tego ciągu. (dst) Napisz program, który pozwoli ocenić prawdziwość następującego stwierdzenia: "Jeżeli argumentem funkcji lub procedury jest wskaźnik, to funkcja lub procedura może zmieniać dowolnie wartość tego wskaźnika, niemniej jednak po zakończeniu funkcji lub procedury argument podany faktycznie w wywołaniu pozostaje bez zmian". (db) Napisz program, który pozwoli ocenić prawdziwość następującego stwierdzenia: "Jeżeli argumentem funkcji lub procedury jest wskaźnik, to funkcja lub procedura może zmieniać dowolnie wartość wskazywaną przez ten wskaźnik, niemniej jednak po zakończeniu funkcji lub procedury wartość wskazywana przez wskaźnik podany faktycznie w wywołaniu pozostaje bez zmian". (db) Liczba rzeczywista typu Real zajmuje sześć bajtów pamięci. Napisz program, który wydrukuje 48 bitowy zapis liczby podanej przez użytkownika. (dst) Zdefiniować funkcję Pos o nagłówku: Function Pos(Start : WSkladnik; Liczba : Integer) : Word; która zwróci miejsce pierwszego wystąpienia podanej liczby Liczba na liście jednokierunkowej lub liczbę zero jeżeli lista nie zawiera podanej liczby. (dst) Zdefiniuj funkcję Min o nagłówku: Function Min(T : Pointer; N : Word) : Word; która zwróci numer najmniejszej liczby w tablicy T zawierającej N liczb typu Real. (db) Zdefiniuj funkcję Max o nagłówku: Function Max(T : Pointer; N : Word) : Word; która zwróci numer najwiekszej liczby w tablicy T zawierającej N liczb typu Real. (db) Zdefiniuj funkcję Srednia o nagłówku: Function Srednia(T : Pointer; N : Word) : Real; która zwróci średnią arytmetyczną liczb w tablicy T zawierającej N liczb typu LongInt. (db) Zdefiniuj procedurę Kopiuj o nagłówku: Procedure Kopiuj(P1, P2 : Pointer; N : Word); która skopiuje N bajtów z miejsca pamięci wskazywanego przez wskaźnik P1 do miejsca pamięci wskazywanego przez wskaźnik P2. (bdb) Poprawić definicję procedury GetText w taki sposób, aby ostatni jej argument był typu Pointer. Analogiczną zmianę wykonać w procedurze PutText. (db) Zdefiniować procedurę o nagłówku: Procedure LUsun(Var Start : WSkladnik); usuwającą całą listę. (db) Zdefiniować funkcję LDodajN o nagłówku: Function LDodajN(Var Start : WSkladnik; Liczba : Integer; N : Word) : Boolean; która doda do listy kolejną liczbę Liczba w taki sposób, aby liczba ta po dodaniu była N-tym składnikiem listy. Jeżeli N jest większe niż rozmiar listy, to należy dodać składnik na jej końcu, jeżeli N jest równe 0 lub 1 to dodajemy składnik na początku listy. Funkcja powinna zwrócić wartość True w przypadku powodzenia operacji, w przypadku braku pamięci zwracamy wartość False. (bdb) Zdefiniować procedurę LUsunN o nagłówku: Procedure LUsunN(Var Start : WSkladnik; N : Word); usuwającą z listy N-ty jej składnik. Jeżeli N jest liczbą równą zero lub też większą niż rozmiar listy procedura nie powinna wykonywać żadnych czynności. (bdb) Dany jest ciąg liczb całkowitych zakończony liczbą zero (liczba zero nie jest elementem ciągu). Napisz program, który wczyta ten ciąg a następnie wydrukuje liczbę najmniej różniącą się od średniej arytmetycznej wszystkich liczb tego ciągu. (db) Dany jet ciąg liczb całkowitych zakończony liczbą zero, które nie jest elementem ciągu. Napisz program, który umieści liczby ciągu na liście jednokierunkowej a następnie wydrukuje liczby tego ciągu w kolejności malejącej. (bdb) Dany jest ciąg napisów (mogą to być zdania) zakończony napisem '*' (napis '*' nie jest elementem ciągu). Napisz program który wydrukuje wszystkie słowa wystepujące we wszystkich napisach w kolejności rosnącej. Każde słowo powinno być drukowane tylko jeden raz. Program powinien podać ilość wystąpień każdego słowa we wszystkich napisach. W programie należy zdefiniować typ rekordowy przeznaczony do utworzenia dynamicznej listy słów. Rekord oprócz pola typu String powinien zawierać pole Ilosc, w którym będzie przechowywana ilość wystąpień danego słowa we wszystkich napisach. (bdb) Zdefiniować funkcję WindScr o nagłówku: Function WindScr(X1, Y1, X2, Y2, Attr : Byte; Start : WSkladnik) : Word; która pozwoli na wybór jednego z napisów i zwróci numer wybranego napisu lub liczbę zero. Argument WSkladnik jest wkaźnikiem na rekord o nazwie Skladnik zawierający pole typu String w którym przechowywany jest napis - składnik ten jest pierwszym elementem listy jednokierunkowej. Można wykorzystać typy i funkcje zdefiniowane w zadaniu poprzednim. Funkcja po zakończeniu działania powinna przywrócić zawartość ekranu przykrytą przez okno w którym wyświetlane są napisy. (bdb) Zdefiniować moduł o nazwie MyList zawierający definicję typów WSkladnik oraz Skladnik, a także funkcje i procedury pozwalające na przetwarzanie jednokierunkowej listy napisów. (dst) Zdefiniować moduł o nazwie MyList2 zawierający definicję typów WSkladnik2 oraz Skladnik2, a także funkcje i procedury pozwalające na przetwarzanie dwukierunkowej listy napisów. (bdb) <<---- Spis treści