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. A
ą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 wskaz
nikowe. Wskaz
niki
Do pracy ze zmiennymi dynamicznymi używa się typów wskaz
nikowych. Elementami
tych typów są zmienne wskaz
nikowe, które krótko nazywamy wskaz
nikami. Wskaz
nik
jest adresem pewnej zmiennej określonego typu. Mówiąc o wskaz
niku zawsze mamy
na myśli zmienną, której adres zawiera wskaz
nik.
Dynamiczny przydział pamięci
Wskaz
nikowi po zadeklarowaniu można przypisać adres dowolnej istniejącej zmiennej
identycznego typu jak typ wskaz
nika. Niezależnie od typu wskaz
nika zawsze można
mu przypisać tzw. adres pusty, który w języku Pascal oznaczamy słowem Nil -
wskaz
nik o wartości Nil nie wskazuje niczego.
Program w dowolnym momencie może utworzyć nową zmienną i jej adres przypisać
zmiennej wskaz
nikowej. Tak powstałą zmienną nazywamy zmienną dynamiczną.
Standardowa procedura
New(Zmienna wskaz
nikowa)
tworzy na stercie nową zmienną typu identycznego z typem wskaz
nika i jej adres
przypisuje zmiennej wskaz
nikowej.
Po poprawnym wykonaniu procedury New zmienna wskaz
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 wskaz
nikowa)
Należy pamietać, że jeżeli program utworzy zmienną dynamiczną, której adres
zostanie zapamiętany w zmiennej wskaz
nikowej, a następnie przed usunięciem tej
zmiennej dokona zmiany wskaz
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 wskaz
nikowej Wsk.
Następnie następuje odczyt wartości liczbowej do tej zmiennej, po czym wskaz
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 wskaz
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ść wskaz
nika po
wywołaniu procedury.
Pamięć przydzieloną procedurą GetMem zwalnia się za pomocą procedury
FreeMem(Zmienna wskaz
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 wkaz
nikach
Wskaz
niki można ze sobą porównywać za pomocą operatorów = oraz <>. Dwa
wskaz
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 wskaz
nika o liczbę
całkowitą za pomocą procedur Inc i Dec. Po wykonaniu instrukcji
Inc(Wsk);
wskaz
nik Wsk wskazuje na kolejny element w pamięci typu identycznego z typem
wskaz
nika, tzn. jeżeli Wsk jest typu ^Word, to dodanie do wartości wskaz
nika liczby 1
powoduje przesunięcie wskaz
nika na kolejną liczbę typu Word, czyli o dwa bajty.
Ogólnie, jeżeli Wsk jest typu ^TYP, to zwiekszenie wskaz
nika o 1 procedurą Inc
przesuwa wskaz
nik o SizeOf(TYP) bajtów.
Analogiczne zasady obowiązują podczas zmniejszania wskaz
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 wskaz
nikowe Next
typu WSkladnik, czyli wskaz
nik na rekord Skladnik.
Załóżmy, że w programie zadeklarowana jest zmienna Start typu wskaz
nik na
Skladnik, czyli Start : WSkladnik. Program może utworzyć dynamicznie zmienną
rekordową, jej adres przypisać zmiennej wskaz
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 wskaz
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 wskaz
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 wskaz
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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 wskaz
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 wskaz
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