Informatyka EP AGH Kr
- 1 -
Zmienne dynamiczne - podstawowe pojęcia
Każdy skompilowany program, napisany w Turbo/Borland Pascalu zajmuje cześć pamięci operacyjnej komputera, w sposób
przedstawiony na rysunku poniżej.
HeapEnd
wolny obszar stosu
HeapPtr
stos dla zmiennych dynamicznych
HeapOrg OvrHeapEnd
bufor nakładkowy
OvrHeapOrg
segment stosowy dla zmiennych lokalnych
SSeg:SPtr
wolny obszar segmentu stosowego
SSeg:0000
zmienne globalne
segment danych
literały zmienne
DSeg:0000
blok kodu modułu System
blok kodu pierwszego modułu
zawartość obrazu
bloki kodu kolejnych modułów
zbioru .EXE
blok kodu ostatniego modułu
blok kodu programu
blok wstępny programu (PSP)
PrefixSeg
Blok wstępny Kod programu Kody modułów
Podczas wczytywania zbioru .EXE do pamięci, system operacyjny DOS tworzy blok wstępny programu (blok PSP). Ten obszar
pamięci służy do komunikacji pomiędzy systemem operacyjnym i programem. Blok PSP (Program Segment Prefix) zajmuje 256 bajtów.
Adres segmentu pamięci, od którego rozpoczyna się ten blok jest pamiętany w predefiniowanej zmiennej PrefixSeg.
Kod programu głównego zajmuje pierwszy blok kodowy.
W kolejnych blokach pamiętane są kody zadeklarowanych w programie modułów (w odwrotnej kolejności niż zadeklarowane). W
ostatnim bloku kodowym pamiętany jest kod standardowego modułu System .
Żaden z bloków kodowych nie może zając więcej niż 64 kB pamięci, natomiast rozmiar wszystkich bloków łącznie jest
ograniczony jedynie wielkością pamięci komputera.
Segment danych Segment stosowy Bufor nakładkowy
f& W segmencie danych pamiętane są wszystkie literały zmienne zdefiniowane w programie i modułach oraz zmienne globalne
zadeklarowane w programie i modułach. Początek adresu tego segmentu jest wartością standardowej funkcji DSeg. Rozmiar segmentu
danych (podobnie jak poszczególnych segmentów kodowych) nie może przekraczać 64 kB.
f& W segmencie stosowym pamiętane są zmienne lokalne. Kolejne zmienne zapamiętywane są w kierunku malejących adresów
pamięci. Rozmiar segmentu stosowego (max 64 kB) ustala się za pomocą dyrektywy kompilatora M lub w menu systemu Turbo/Borland
Pascal.
f& Do przechowywania segmentów nakładkowych programu jest wykorzystywany bufor nakładkowy. Jeśli program nie posiada
segmentów nakładkowych, rozmiar tego bufora jest równy zeru. Adresy początku i końca bufora nakładkowego pamiętane są
w predefiniowanych zmiennych OvrHeapOrg i OvrHeapEnd.
Zmienne statyczne a dynamiczne Sterta
f& Zmienne typu statycznego (globalne - umieszczane w segmencie danych i lokalne - umieszczane w segmencie stosowym) istnieją
przez cały czas wykonywania tej części programu, w której są zadeklarowane. Każdy z tych segmentów ma rozmiar
maksymalny równy 65635 bajtów.
W Turbo/Borland Pascalu, obok zmiennych statycznych występują zmienne dynamiczne reprezentujące obiekty dla
których pamięć jest przydzielana na określone żądanie. Zmienne te nie posiadają identyfikatorów, a odwołanie do nich
następuje za pomocą wskaz
nika. Wartościami zmiennych dynamicznych są elementy typu wskaz
nikowego, które
określają adresy pamięci zmiennych dynamicznych.
f& Zmienne dynamiczne przechowywane są na stosie dla zmiennych dynamicznych (na stercie). Pamięć dla tych zmiennych jest
przydzielana za pomocą standardowych procedur New i GetMem. Zmienne dynamiczne mogą zajmować całą resztę pamięci dostępną
podczas wykonywania programu. Adres początku stosu pamiętany jest w zmiennej HeapOrg, a adres wierzchołka stosu w zmiennej
HeapPtr.
Informatyka EP AGH Kr
- 2 -
Definicja typu wskaz
nikowego
Definicja typu wskaz
nikowego ma postać:
type identyfikator_typu_wskaz
nikowego = ^identyfikator_typu_bazowego;
Zmienne typu wskaz
nikowego wskazują na dane typu bazowego.
Identyfikator typu bazowego może być określony wcześniej lub w tym samym
zdaniu type, w którym występuje definicja danego typu wskaz
nikowego.
Przykłady:
a) type Macierz = Array[1..10, 1..10] of Byte;
Macierz_dynamiczna = ^Macierz;
b) type Lista_dynamiczna = ^Lista;
Lista = record
Lp : Byte
X,Y : Real;
end;
c) type Liczba = ^LongInt;
Zmienne wskaz
nikowe
Po wprowadzeniu deklaracji:
var M : Macierz_dynamiczna;
L : Lista_dynamiczna;
zmiennej wskaz
nikowej M można będzie w programie przypisywać adresy pamięci danych (zmiennych dynamicznych) typu Macierz,
natomiast zmiennej wskaz
nikowej L - adresy pamięci danych (zmiennych dynamicznych) typu Lista.
Deklaracja zmiennej wskaz
nikowej
var x : Liczba
umożliwi przypisanie zmiennej x adresów pamięci danych (zmiennych dynamicznych) typu LongInt.
Zmienne wskaz
nikowe można również zadeklarować następująco:
var M1 : ^Macierz; L1 : ^Lista; X1 : ^LongInt;
Zmienne dynamiczne pamiętane są segmencie pamięci o strukturze stosowej.
Zmienne wskazywane
Aby odwołać się do zmiennej typu wskaz
nikowego stosuje się zmienne wskazywane postaci:
zmienna_wskaz
nikowa^
Przykład:
type Lista = record
Lp : Byte; X,Y : Real;
end;
Lista_dynamiczna = ^Lista;
var L : Lista_dynamiczna;
Zmienna wskaz
nikowa L jest związana z typem wskaz
nikowym Lista_dynamiczna. Wartościami zmiennej wskaz
nikowej L będą adresy
pamięci danych (zmiennych dynamicznych) typu Lista. Zmienna wskazywana L^ będzie natomiast rekordem typu Lista o adresie
określonym przez zmienną wskaz
nikową L.
Odwołania za pomocą zmiennych wskazywanych:

Odwołania typu
L.Lp:=1; L.X:=10.0; L.Y:=20.0;
są błędne, ponieważ L jest zmienną wskaz
nikową.
Poprawne odwołanie powinno być zapisane za pomocą zmiennych wskazywanych:
L^.Lp:=1; L^.X:=10.0; L^.Y:=20.0;
(wcześniej jednak należy w odpowiedni sposób utworzyć zmienną dynamiczną).
Zmienne wskazywane stosuje się przede wszystkim do dynamicznego zarządzania pamięcią operacyjną. Do tworzenia i zwalniania
zmiennych dynamicznych oraz do zarządzania obszarem pamięci przeznaczonym na zmienne dynamiczne służą procedury i funkcje
standardowe:
New, GetMem - do utworzenia zmiennej dynamicznej i podstawienia pod zmienną wskaz
nikową
odpowiedniego adresu pamięci.
Dispose, FreeMem, Release - do zwolnienia obszaru pamięci dynamicznej (usunięcia odpowiedniej
zmiennej dynamicznej z pamięci).
Mark, MaxAvail, MemAvail.
Informatyka EP AGH Kr
- 3 -
Procedura New
New (zmienna_wskaz
nikowa)
lub
New (zmienna_wskaz
nikowa, konstruktor) - do utworzenia zmiennej dynamicznej typu obiektowego.
Przykład:
New(L);
Do utworzonej zmiennej dynamicznej można odwołać się za pomocą zmiennej wskazywanej postaci zmienna_wskaz
nikowa^, np:
L^.Lp:=1; L^.X:=10.0; L^.Y:=20.0;
Zmiennej dynamicznej tworzonej za pomocą procedury New jest przydzielany blok pamięci równy rozmiarowi typu, z którym związana
jest wyspecyfikowana zmienna wskaz
nikowa. W przykładzie powyżej, zmiennej dynamicznej będzie przydzielony blok pamięci równy 13
bajtów (Lp - 1 bajt, X,Y - po 6 bajtów).
Procedura GetMem
GetMem (zmienna_wskaz
nikowa, rozmiar_pamięci)
Rozmiar_pamieci jest wyrażeniem typu Word określającym rozmiar pamięci rezerwowany na zmienną dynamiczną.
Przykład:
GetMem(L,13);
jest równoważne New(L);
Procedura Dispose
Dispose(zmienna_wskaz
nikowa)
lub Dispose(zmienna_wskaz
nikowa, destruktor) - do zwolnienia pamięci zajmowanej przez obiekt dynamiczny.
Procedura Dispose zwalnia obszar pamięci zajmowany przez zmienną wskazywaną.
Na przykład:
Dispose(L);
(Uwaga, wymagane jest, aby zwalniana zmienna dynamiczna była uprzednio utworzona za pomocą procedury New).
Procedura FreeMem
FreeMem(zmienna_wskaz
nikowa, rozmiar_pamięci)
Procedura ta zwraca do stosu przeznaczonego na zmienne dynamiczne obszar pamięci wskazywany zmienną_wskaz
nikową i zajmujący
liczbę bajtów określoną argumentem rozmiar_pamięci, Np.
FreeMem(L,13);
(Uwaga, wymagane jest, aby rozmiar_pamięci był taki sam jak w wywołaniu procedury GetMem tworzącej tę zmienną dynamiczną.
Procedura Release
Release(zmienna_wskaz
nikowa)
Procedura ta usuwa ze stosu zmienną dynamiczną wskazywaną zmienną_wskaz
nikową oraz wszystkie zmienne następujące po niej.
Przykład:
{$M 30000,0,655008}
type Wektor_statyczny = Array[1..50] of Byte;
Wektor_dynamiczny = ^Wektor_statyczny;
Macierz_dynamiczna = Array[1..100] of Wektor_dynamiczny;
var
M : Macierz_dynamiczna; i, j : Integer; rozmiar: LongInt;
begin
rozmiar:=SizeOf(M); { wyznaczenie rozmiaru zmiennej wskaz
nikowej M }
Writeln('Maksymalny blok pamieci : ',MaxAvail);
Writeln('Rozmiar zmiennej wskaznikowej M : ',rozmiar);
for i:=1 to 100 do New(M[i]); { przydzielenie pamięci zmiennej dynamicznej wskazywanej przez M[i] }
for i:=1 to 100 do
for j:=1 to 50 do M[i]^[j]:=i+j; { wartość i+j jest przypisywana zmiennej wskazywanej o adresie określonym przez M[i] }
for i:=1 to 100 do
for j:=1 to 50 do Writeln(M[i]^[j]);
for i:=100 downto 1 do Dispose(M[i]); { zwolnienie obszaru pamięci zajmowanego przez zmienną dynamiczną wskazywaną przez M[i]}
end.
Informatyka EP AGH Kr
- 4 -
Przykład programu umożliwiającego analizę wykorzystania pamięci operacyjnej
program analiza;
{$M 1024,0,30}
type s60 = String[60];
var a,b,c,d,s : LongInt;
g,h,i : ^Double;
t: Text;
procedure pisz(napis:S60; liczba:LongInt);
begin
Writeln(t,napis:60,liczba:30)
end;
procedure pisz10 (napis:S60; liczba1,liczba2:LongInt);
begin
Write(t,napis:60,' ',liczba1,':');
case liczba2 of
0..9 : Write (t, '000',liczba2);
10..99 : Write (t, '00',liczba2);
99..999 : Write (t, '0',liczba2)
else Write (t, liczba2);
end; {case }
Write (t, (liczba1*16+liczba2):16 );
end; { pisz10 }
procedure pisz16(liczba1,liczba2:Word);
const znak : Array [0..$F] of Char = '0123456789ABCDEF';
begin
Write(t,' ');
Write(t, znak [Hi(liczba1) shr 4] );
Write(t, znak [Hi(liczba1) and $F] );
Write(t, znak [Lo(liczba1) shr 4] );
Write(t, znak [Lo(liczba1) and $F] );
Write(t,':');
Write(t, znak [Hi(liczba2) shr 4] );
Write(t, znak [Hi(liczba2) and $F] );
Write(t, znak [Lo(liczba2) shr 4] );
Write(t, znak [Lo(liczba2) and $F] );
Writeln(t);
end; { pisz16 }
procedure jeden;
var d,e,f:Double;
begin
pisz10('Adres wolnego segmentu stos. dla zm.lokalnych',SSeg,0);
pisz16(SSeg,0);
Writeln(t);
pisz('Wolna przestrzen segmentu dla zm. lokalnych *',SPtr);
pisz10('Adres ost. zajetego bajtu w seg. stos. *',SSeg,SPtr);
pisz16(SSeg,SPtr);
Informatyka EP AGH Kr
- 5 -
pisz10('Adres 1-ego zajetego bajtu w seg. stos. *',SSeg,1023);
pisz16(SSeg,1023);
pisz('Rozmiar segmentu stosowego zajetego przez zmienne lokalne *',(s*OvrHeapOrg-(s*SSeg+SPtr)) );
Writeln(t);
pisz('Razem max. rozmiar segmentu stosowego dla zmiennych lokalnych',s*(OvrHeapOrg-SSeg) );
Writeln(t);
pisz10('Adres zmiennej lokalnej d {rozmiar 8}',Seg(d),Ofs(d) );
pisz16(Seg(d),Ofs(d));
pisz10('Adres zmiennej lokalnej e {rozmiar 8}',Seg(e),Ofs(e) );
pisz16(Seg(e),Ofs(e));
pisz10('Adres zmiennej lokalnej f {rozmiar8 }',Seg(f),Ofs(f) );
pisz16(Seg(f),Ofs(f));
Writeln(t);
end; { jeden }
procedure dwa;
begin
pisz10('Adres zmiennej dynamicznej wskazywanej przez g^ {rozmiar 8}',Seg(g^),Ofs(g^));
pisz16(Seg(g^),Ofs(g^));
pisz10('Adres zmiennej dynamicznej wskazywanej przez h^ {rozmiar 8}',Seg(h^),Ofs(h^));
pisz16(Seg(h^),Ofs(h^));
pisz10('Adres zmiennej dynamicznej wskazywanej przez i^ {rozmiar 8}',Seg(i^),Ofs(i^));
pisz16(Seg(i^),Ofs(i^));
end; { dwa }
begin { analiza }
Assign(t,'8.res');
Rewrite(t);
s:=16;
for a:=1 to 66 do Write(t,' ');
Writeln(t,'Seg:Ofs Seg*16+Ofs $$$$:FFFF');
Writeln(t);
pisz10('Adres poczatku bloku PSP',PrefixSeg,0);
pisz16(PrefixSeg,0);
pisz('Rozmiar bloku PSP',256);
Writeln(t);
pisz10('Adres bloku kodu programu od',CSeg,0);
pisz16(CSeg,0);
for a:=1 to 42 do Write(t,' ');
Writeln(t,'Rozmiar zbioru EXE',s*(DSeg-CSeg):30);
Writeln(t);
pisz10('Adres poczatku segmentu danych',DSeg,0);
pisz16(DSeg,0);
pisz('Rozmiar segmentu danych',s*(SSeg-DSeg));
Writeln(t);
pisz10('Adres zmiennej globalnej a {4 bajty }',Seg(a),Ofs(a));
pisz16(Seg(a),Ofs(a));
pisz10('Adres zmiennej globalnej b {4 bajty }',Seg(b),Ofs(b));
Informatyka EP AGH Kr
- 6 -
pisz16(Seg(b),Ofs(b));
pisz10('Adres zmiennej globalnej c {4 bajty}',Seg(c),Ofs(c));
pisz16(Seg(c),Ofs(c));
Writeln(t);
jeden;
pisz10('Adres bufora nakladkowego',OvrHeapOrg,0);
pisz16(OvrHeapOrg,0);
pisz('Rozmiar bufora nakladkowego', s*(OvrHeapend-OvrHeapOrg));
New(g);
New(h);
New(i);
Writeln(t);
pisz10('Adres stosu zmiennych dynamicznych' ,Seg(HeapOrg^),Ofs(HeapOrg^));
pisz16( Seg(HeapOrg^),Ofs(HeapOrg^));
dwa;
Writeln(t);
pisz10('Adres poczatku wolnego obszaru stosu',Seg(HeapPtr^),Ofs(HeapPtr^));
pisz16(Seg(HeapPtr^),Ofs(HeapPtr^));
pisz10('Adres konca wolnego obszaru stosu',Seg(Heapend^),Ofs(Heapend^));
pisz16( Seg(Heapend^),Ofs(Heapend^));
Dispose(i);
Dispose(h);
Dispose(g);
Close(t);
end. { analiza }
Informatyka EP AGH Kr
- 7 -
Informacja Seg:Ofs Seg*16+Ofs $Seg:$Ofs
Adres poczatku bloku PSP 6216:0000 99456 $1848:$0000
Rozmiar bloku PSP 256
Adres bloku kodu programu od 6232:0000 99712 $1858:$0000
Rozmiar zbioru EXE 6800
Adres poczatku segmentu danych 6657:0000 106512 $1A01:$0000
Rozmiar segmentu danych 976
Adres zmiennej globalnej a { 4 bajty } 6657:0098 106610 $1A01:$0062
Adres zmiennej globalnej b { 4 bajty } 6657:0102 106614 $1A01:$0066
Adres zmiennej globalnej c { 4 bajty } 6657:0106 106618 $1A01:$006A
Adres wolnego segmentu stosowego dla zmiennych lokalnych 6718:0000 107488 $1A3E:$0000
Wolna przestrzen segmentu dla zmiennych lokalnych * 988
Adres ostatniego zajetego bajtu w segmencie stosowym * 6718:0984 108472 $1A3E:$03DE
Adres pierwszego zajetego bajtu w segmencie stosowym * 6718:1023 108511 $1A3E:$03FF
Rozmiar segmentu stosowego zajety przez zmienne lokalne * 36
Razem max.rozmiar segmentu stos. dla zmiennych lokalnych 1024
Adres zmiennej lokalnej d { rozmiar 8 } 6718:1008 108496 1A3E:$03F0
Adres zmiennej lokalnej e { rozmiar 8 } 6718:1000 108488 $1A3E:$03E8
Adres zmiennej lokalnej f { rozmiar 8 } 6718:0992 108480 $1A3E:$03E0
Adres bufora nakladkowego 6782:0000 108512 $1A7E:$0000
Rozmiar bufora nakladkowego 0
Adres stosu zmiennych dynamicznych 6782:0000 108512 $1A7E:$0000
Adres zmiennej dynamicznej wskazywanej przez g^ {rozmiar 8} 6782:0000 108512 $1A7E:$0000
Adres zmiennej dynamicznej wskazywanej przez h^ {rozmiar 8} 6782:0008 108520 $1A7E:$0008
Adres zmiennej dynamicznej wskazywanej przez i^ {rozmiar 8} 6783:0000 108528 $1A7F:$0000
Adres poczatku wolnego obszaru stosu 6783:0008 108536 $1A7F:$0008
Adres konca wolnego obszaru stosu 6797:0000 108752 1A8D:$0000
program balagan_na_stosie;
var a : Array[1..4] of ^Double;
i : Byte;
begin
Writeln('Balagan na stosie'); Writeln;
Writeln('Poczatek programu :', MemAvail:38, MaxAvail:10); { wypisz informacje dotyczące pamięci ... }
Writeln;
Writeln('Na stosie przydzielono Przydzielony adres MemAvail MaxAvail');
Writeln;
for i:=1 to 4 do
begin
New(a[i]); { utwórz nową zmienną dynamiczną i podstaw jej adres pod zmienną wskaz
nikową a[i] }
Write (SizeOf(a[i]^):6,' bajtow'); { wypisz rozmiar zmiennej dynamicznej na którą wskazuje a[i]^ }
Write (' a[',i,']^' ,(Seg(a[i]^)*16+Ofs(a[i]^)):8); { wypisz adres zmiennej dynamicznej na którą wskazuje a[i]^ }
Writeln(MemAvail:16,MaxAvail:10); { wypisz informacje dotyczące pamięci ... }
Informatyka EP AGH Kr
- 8 -
end;
Writeln;
Writeln('Ze stosu zwolniono Zwolniony adres
MemAvail MaxAvail');
Writeln;
for i:=1 to 2 do
begin
Dispose(a[i]); { zwolnij pamięć zajmowaną przez zmienną dynamiczną której adres pamiętany przez zmienną
wskaz
niopwą a[i] }
Write (SizeOf(a[i]^):6,' bajtow'); { wypisz rozmiar zmiennej dynamicznej na którą wskazuje a[i]^ }
Write (' a[',i,']^', (Seg(a[i]^)*16+Ofs(a[i]^)):8); { wypisz adres zmiennej dynamicznej na którą wskazuje a[i]^ }
Writeln(MemAvail:16,MaxAvail:10); { wypisz informacje dotyczące pamięci ... }
end;
for i:=4 downto 3 do
begin
Dispose(a[i]);
Write (SizeOf(a[i]^):6,' bajtow'); { wypisz rozmiar zmiennej dynamicznej na którą wskazuje a[i]^ }
Write ('a[',i,']^ ', (Seg(a[i]^)*16+Ofs(a[i]^)):8); { wypisz adres zmiennej dynamicznej na którą wskazuje a[i]^ }
Writeln(MemAvail:16,MaxAvail:10); { wypisz informacje dotyczące pamięci ... }
end;
Writeln;
Writeln('Koniec programu : ', MemAvail:38, MaxAvail:10); { wypisz informacje dotyczące pamięci ... }
end. { balagan_na_stosie }
Przykładowy efekt wykonania programu balagan_na_stosie
Informatyka EP AGH Kr
- 9 -
Bezparametrowa funkcja MemAvail (moduł System)
zwraca w bajtach sumę rozmiarów wszystkich wolnych bloków pamięci, w segmencie przeznaczonym na zmienne dynamiczne.
Bezparametrowa funkcja MaxAvail (moduł System)
zwraca w bajtach rozmiar największego wolnego bloku pamięci, w segmencie przeznaczonym na zmienne dynamiczne.
Funcja SizeOf (identyfikator) (moduł System), gdzie identyfikator oznacza nazwę zmiennej lub nazwę typu, zwraca w bajtach rozmiar
wyspecyfikowanego elementu (rozmiar zmiennej lub typu).
Funcja TypeOf (obiekt) (moduł System), gdzie obiekt oznacza nazwę zmiennej obiektowej lub nazwę typu obiektowego (posiadających
tablicę metod wirtualnych),
zwraca adres (typu Pointer) tablicy metod wirtualnych wyspecyfikowanego obiektu.
Standardowe funkcje języka Seg(Zmienna) oraz Ofs(Zmienna) zwracają w postaci liczby typu Word odpowiednio segment i ofset podanej
jako argument zmiennej.
STOSY
element 1 (wierzchołek stosu)
STOS jest strukturą danych składających się z uporządkowanych
WEJŚCIE
liniowo elementów (składników). W danej chwili dostępny jest tylko
dane
 największy składnik stosu, tj. składnik zanjdujący się na
WYJŚCIE
adres_natępnego_elementu
wierzchołku stosu. Wierzchołek stosu jest zatem jedynym miejscem
do którego można dołączyć lub z którego można usunąć elementy.
Każdy element stosu posiada wskaz
nik, który wskazuje na adres
następnego elementu. Wskaz
nik ostatniego elementu wskazuje na
element 2
adres pusty (nil).
dane
W celu utworzenia stosu i jego przetwarzania zdefiniujemy
następujące typy:
adres_natępnego_elementu
type
adres = ^element;
element 3
element = record
dane : typ_danych;
dane
adres_nastepnego : adres
end;
adres_natępnego_elementu
Zdefiniowany powyżej typ adres jest typem wskaz
nikowym
związanym ze zbiorem wskazań danych typu element.
...................
Zmienne typu adres będą określały adresy pamięci danych
typu element.
element n
Występujący w definicji typ_danych może być typem
dane
standardowym lub zdefiniowanym przez programistę.
adres_natępnego_elementu
nil
Przykład programu tworzącego stos, dołączania i usuwania elementów:
program stos;
type adres = ^element;
element = record
dane : Real;
adres_nastepnego : adres
end;
var a,b,c:Real;
w:adres; { w - wierzcholek }
Informatyka EP AGH Kr
- 10 -
procedure na_stos(var dane_na_stos : Real; var wierzcholek: adres);
var pamiec : adres; { zmienna typu wskaz
nikowego }
begin
pamiec:=wierzcholek; { zapamiętaj element znajdujący się na wierzchołku }
New(wierzcholek); { utwórz nowy wierzchołek }
with wierzcholek^ do { wprowadz
do pól rekordu ... }
begin
dane:=dane_na_stos; { w polu dane wstaw te dane, które mają znalez
ć się na stosie }
adres_nastepnego:=pamiec; { w polu adres_nastepnego wstaw adres elementu zapamietanego }
end;
end;
procedure ze_stosu(var dane_ze_stosu : Real; var wierzcholek: adres);
var pamiec : adres; { zmienna typu wskaz
nikowego }
begin
if wierzcholek<>nil then { sprawdz
, czy na wierzchołku znajduje się element ...}
begin
with wierzcholek^ do { wypełnij pola rekordu ... }
begin
dane_ze_stosu:=dane; { w polu dane wstaw dane które mają znalez
ć się na stosie }
pamiec:=adres_nastepnego; { zapamiętaj adres następnego elementu }
end;
Dispose(wierzcholek); { zwolnij wierzchołek }
wierzcholek:=pamiec; { wierzchołek ma teraz taki adres }
end;
end;
procedure pisz(napis:String); { wypisz komunikat }
begin
Writeln(napis:20,' ',MaxAvail,' ',MemAvail,
' ',Seg(w^):6,Ofs(w^):6);
end;
begin { stosy }
Writeln(' Uwagi MaxAvail MemAvail adres ');
pisz('Poczatek programu');
na_stos(a,w); pisz('na_stos(a,w)');
na_stos(b,w); pisz('na_stos(b,w)');
na_stos(c,w); pisz('na_stos(c,w)');
ze_stosu(b,w); pisz('ze_stosu(b,w)');
ze_stosu(c,w); pisz('ze_stosu(c,w)');
ze_stosu(a,w); pisz('ze_stosu(a,w)');
end. { stos }
Przykładowy efekt wykonania programu stos w środowisku DOS
Informatyka EP AGH Kr
- 11 -
Przykładowy efekt wykonania programu stos w środowisku Windows
KOLEJKI
KOLEJKA , podobnie jak stos, jest strukturą danych składających się z uporządkowanych liniowo elementów (składników), przy
czym nowy element można dołączyć tylko na końcu kolejki, a usunąć element można tylko na początku kolejki.
Każdy element kolejki, podobnie jak każdy element stosu, posiada wskaz
nik, który wskazuje na adres następnego elementu.
Wskaz
nik ostatniego elementu wskazuje na adres pusty (nil).
element 1(początek kolejki) element 2 element 3
WYJŚCIE
dane dane dane
adres_natępnego_elementu adres_natępnego_elementu adres_natępnego_elementu
element 4 element n (koniec kolejki) WEJŚCIE
dane dane
adres_natępnego_elementu adres_natępnego_elementu
nil
...................
W celu utworzenia kolejki i jej przetwarzania zdefiniujemy następujące typy:
type
adres = ^element;
element = record
dane : typ_danych;
adres_nastepnego : adres
end;
Zdefiniowany powyżej typ adres jest typem wskaz
nikowym związanym ze zbiorem wskazań danych typu element. Zmienne typu
adres będą określały adresy pamięci danych typu element. Występujący w definicji typ_danych może być typem standardowym lub
zdefiniowanym przez programistę.
Przykład programu tworzącego kolejkę, dołączania i usuwania elementów:
program kolejka;
type
macierz = Array[1..10,1..2] of Byte;
adres = ^ element;
element = record
dane : macierz;
adres_nastepnego : adres;
end;
Informatyka EP AGH Kr
- 12 -
var
a,b,c,d : Macierz;
poczatek, koniec : adres;
procedure do_kolejki(var dane_wstawiane : Macierz; var koniec_kolejki : adres);
var
pamiec:adres;
begin
pamiec:=koniec_kolejki; { zapamiętaj adres aktualnego końca kolejki - po wprowadzeniu nowego
elementu bedzie to przedostatni składnik kolejki }
New(koniec_kolejki); { utwórz nową zmienną dynamiczną i podstaw jej adres pod zmienną koniec_kolejki }
with koniec_kolejki^ do { wprowadz
do pol rekordu ... }
begin
dane:=dane_wstawiane; { do pola dane - nowe dane które wprowadzamy do kolejki }
adres_nastepnego:=nil;{ do pola adres_nastepnego - adres pusty (ponieważ jest to ostatni element kolejki) }
end;
if pamiec<>nil then
pamiec^.adres_nastepnego:=koniec_kolejki; { jeżeli wprowadzany element nie jest pierwszym z wprowadzanych
skladników kolejki, to w elemencie przedostatnim, w polu
adres_nastepnego, wstaw adres ostatniego elementu kolejki }
Write(Seg(koniec_kolejki^):8,Ofs(koniec_kolejki^):4);{ wypisz adres wprowadzonej zmiennej dynamicznej }
Write(SizeOf(koniec_kolejki^):12); { wypisz rozmiar zmienej dynamicznej }
Writeln(MemAvail:14,MaxAvail:10); { wypisz informacje dotyczące pamięci }
end; { do_kolejki }
procedure z_kolejki(var dane_usuwane : Macierz; var poczatek_kolejki : adres);
var
pamiec:adres;
begin
if poczatek_kolejki<>nil then { jeśli w kolejce znajduje się jakiś element ... }
begin
with poczatek_kolejki^ do { odwołaj się pól rekordu ... }
begin
dane_usuwane:=dane; { w miejscu usuwanych danych wstaw dane znajdujące się na poczatku kolejki }
pamiec:=adres_nastepnego; { zapamiętaj adres drugiego elementu w kolejce
(po usunięciu początku kolejki, ten elemnt stanie się początkiem) }
end;
Write(Seg(poczatek_kolejki^):6,Ofs(poczatek_kolejki^):4) { wypisz adres usuwanej zmiennej dynamicznej }
Write(SizeOf(poczatek_kolejki^):12); { wypisz rozmiar zmiennej dynamicznej }
Dispose(poczatek_kolejki); { zwolnij pamięć zmiennej dynamicznej umieszczonej na początaku kolejki }
Writeln(MemAvail:14,MaxAvail:10); { wypisz informacje dotyczące pamięci }
poczatek_kolejki:=pamiec; { pod zmienną poczatek_kolejki wstaw adres aktualnego początku kolejki }
end;
end; { z_kolejki }
begin
Writeln('kolejka');
Writeln;
Writeln(' Działanie Adres elementu Rozmiar MemAvail MaxAvail');
Writeln;
Informatyka EP AGH Kr
- 13 -
Writeln('Poczatek programu ',MaxAvail:44,MemAvail:10);
Writeln;
Write('do_kolejki(a,koniec) '); do_kolejki (a,koniec);
poczatek:=koniec; { pierwszy element wprowadzony do kolejki jest zarazem jej końcem jak i początkiem }
Write('do_kolejki(b,koniec) '); do_kolejki (b,koniec);
Write('do_kolejki(c,koniec) '); do_kolejki (c,koniec);
Writeln;
Write('z_kolejki(b,poczatek) '); z_kolejki (b,poczatek);
Write('z_kolejki(a,poczatek) '); z_kolejki (a,poczatek);
Write('z_kolejki(c,poczatek) '); z_kolejki (c,poczatek);
Writeln;
Writeln('Koniec programu ',MaxAvail:46,MemAvail:10);
end. { kolejka }
Przykładowy efekt wykonania programu kolejka
DRZEWA BINARNE
Drzewem nazywamy strukturę utworzoną w wierzchołków (węzłów) i krawędzi łączących poszczególne
wierzchołki. Każdy wierzchołek posiada określony zbiór następników, nazywanych potomkami (synowie).
Pierwszy wierzchołek drzewa nazywamy korzeniem. Dla każdego wierzchołka oprócz korzenia można
jednoznacznie określić jego poprzednik zwany rodzicem (ojciec). Wierzchołki nie posiadające potomków
nazywamy liściami. Drogę od korzenia do liścia nazywa się gałęzią drzewa.
Na powyższym rysunku korzeniem jest wierzchołek o numerze 3, liściami są natomiast wierzchołki 17, 11
oraz 2.
Drzewo nazywamu binarnym, jeśli każdy rodzic ma co najwyżej dwóch potomków. W drzewach binarnych
dwuelementowy zbiór potomków tworzy parę uporządkowaną - pierwszego potomka nazywa się najczęściej
lewym synem, drugiego prawym. Lewymi synami są wierzchołki 12, 5, 25 i 2, prawymi wierzchołki 8, 11 i
17.
Każdemu wierzchołkowi drzewa można przypisać nieujemną liczbę całkowitą zwaną poziomem wierzchołka:
korzeń posiada poziom 0, jego synowie poziom 1, ich synowie poziom 2, itd. Poziomem drzewa możemy
nazwać maksymalny z poziomów wszystkich jego liści.
Drzewo binarne nazywamy pełnym, gdy każdy wierzchołek nie będący liściem posiada dokładnie dwóch synów i każdy liść drzewa
ma poziom równym poziomowi drzewa.
Pełne drzewo binarne na poziomie N posiada 2N wierzchołków, zaś liczba wszystkim wierzchołków pełnego drzewa binarnego o
poziomie N jest równa 2N+1-1.
Załóżmy, że pełne drzewo binarne posiada P poziomów, czyli zawiera łącznie 2P+1-1 wierzchołków. Numerując poszczególne jego
wierzchołki kolejno na poziomie zerowym 1, na pierwszym 2 i 3, na drugim 3, 5, 6 i 7, itd. możemy umieścić reprezentację drzewa w
statycznej tablicy indeksowanej od 1 do 2P+1-1.
Przy takim indeksowaniu lewym synem wierzchołka o numerze N jest element tablicy o indeksie 2*N, synem prawym element o indeksie
2*N+1. Równie łatwo można ustalić, że rodzicem wierzchołka o numerze N (N>1) jest wierzchołek N Div 2.