Dynamiczne struktury danych w języku Turbo Pascal
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.
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.
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 zapamiętany w zmiennej wskaźnikowej, a następnie 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.
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
Zdefiniować funkcję LRozmiar wartością której będzie ilość składników listy
utworzonej przy pomocy rekordu typu Skladnik.
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
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
Zdefiniować procedurę LUsunPierw, która usunie w listy utworzonej przy pomocy
rekordu Skladnik pierwszy jej składnik.
Procedure LUsunPierw(Var Start : WSkladnik);
Var
Adr : WSkladnik;
Begin
If Start=Nil Then Exit;
Adr:=Start;
Start:=Start^.Next;
Dispose(Adr);
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.
Przykładowe możliwe zadania do wykonania na laboratorium: (Zadania
będą indywidualne)
Utworzyć następujące struktury danych:
1 – Lista jednokierunkowa
2 – Lista dwukierunkowa
3 – Stos
4 – Kolejka
5 – Tablica list jednokierunkowych / dwukierunkowych / stosów / kolejek
Na strukturach tych powinno być możliwe realizowane następujących operacji:
Każda struktura powinna umożliwiać wyświetlanie umieszczonych w niej elementów a
ponadto:
1 – Lista jednokierunkowa
–
dodawanie elementu w dowolnym (wybranym przez użytkownika programu)
miejscu listy
-
usuwanie dowolnego elementu listy
2 – Lista dwukierunkowa
-
dodawanie elementu w dowolnym (wybranym przez użytkownika programu)
miejscu listy
-
usuwanie dowolnego elementu listy dwukierunkowej
3 – Stos
-
dodawanie elementu na stos
-
usuwanie elementu ze stosu
-
podawanie ilości elementów na stosie
4 – Kolejka
-
dodawanie elementu do kolejki
-
usuwanie elementu z kolejki
-
podawanie ilości elementów, które znajdują się w kolejce
5 – Tablice list:
-
wybór listy do na której chcemy operować
-
pozostałe operacje jak na zwykłych listach