Wskaźniki i zmienne wskazywane. Zmienne dynamiczne.
Do tej pory używaliśmy zmiennych statycznych. Zmienna statyczna, zadeklarowana deklaracją VAR jest tworzona w chwili uruchomienia programu. Jej rozmiar definiujemy w trakcie pisania programu - tak więc w przypadku tablic pisząc program musimy przyjąć jakąś maksymalną liczbę elementów tablicy. Dodatkowym ograniczeniem w TurboPascal-u jest to, że zmienne zadeklarowane w jednym module nie mogą mięć więcej niż 64kB. Ominąć ten problem pozwalają tzw. zmienne dynamiczne. Zmienna statyczna z punktu widzenia procesora jest fragmentem pamięci o rozmiarze pozwalającym pomieścić dane określonego typu. W trakcie wykonywania programu procesor nic nie wie o nazwach zmiennych - posługuje się jedynie adresem, który mówi gdzie zmienna znajduje się w pamięci. W trakcie kompilacji na podstawie zadeklarowanego typu zmiennej kompilator przyporządkowuje odwołaniom do zmiennych konkretne procedury działające na zmiennych zadeklarowanego typu. Linker przydziela zaś zmiennym adresy, tak, aby nie nakładały się na siebie.
Zmienne dynamiczne reprezentują obiekty dla których pamięć jest przydzielana i zwalniana na określone żądanie. Są one pamiętane w specjalnym obszarze pamięci o strukturze stosowej zwanym stertą (heap). Zmienne te nie posiadają identyfikatorów (nazw), a odwołanie do nich następuje za pomocą wskaźników. Zmienna wskaźnikowa pozwala w trakcie działania programu przydzielać pamięć zmiennym dynamicznym za pomocą specjalnych procedur. Wartościami wskaźników są elementy typu wskaźnikowego, które określają adresy zmiennych dynamicznych w pamięci. Zawartość zmiennej wskaźnikowej jest więc adresem wskazującym na miejsce w pamięci, gdzie ma być przechowywana wartość zmiennej dynamicznej.
Definicja typu wskaźnikowego i deklaracja zmiennej wskaźnikowej
Zmienna wskaźnikowa (zawierająca adres do zmiennej jakiegoś konkretnego typu) jest zmienną typu definiowanego przez użytkownika:
type nazwa_typu = ^ typ_zmiennej;
var nazwa_zmiennej_wskaznikowej : nazwa_typu;
lub też
var nazwa_zmiennej_wskaznikowej : ^ typ_zmiennej;
"nazwa_zmiennej_wskaznikowej" oraz "nazwa_typu" są dowolnymi akceptowanymi przez Pascal nazwami identyfikatorów. "typ_zmiennej" określa typ zmiennej wskazywanej przez zadeklarowany wskaźnik. Na tej podstawie kompilator rozpoznaje jaką ilość pamięci zawiera zmienna wskazywana przez wskaźnik i jakich procedur użyć do wykonywania operacji na niej. Typ ten musi być określony jednym identyfikatorem!
Zmienna wskaźnikowa zajmuje 4 bajty w pamięci operacyjnej komputera.
Istnieje predefiniowany typ Pointer, którego zmienne nie wskazują danych żadnego typu lecz są zgodne z dowolnym typem wskaźnikowym.
Słowo kluczowe nil oznacza stałą typu wskaźnikowego nie określającą żadnego adresu (adres pusty).
Definicja typu wskaźnikowego dopuszcza jeden wyjątek w podstawowej regule składni języka Pascal, że można używać tylko identyfikatorów zadeklarowanych: deklaracja zmiennej (lub typu) wskaźnikowej może odwoływać się do typu, który zostanie zadeklarowany po deklaracji zmiennej (lub typu) wskaźnikowej:
type
pOsoba =^TOsoba;
TOsoba =record
imie,
nazwisko :string;
nastepny :pOsoba;
end;
Zwykle przy deklaracji typów wskaźnikowych (podobnie jak i zmiennych) nazwę identyfikatora typu lub zmiennej zaczyna się od małej litery „p”.
Odwołanie do zmiennej wskaźnikowej
W naszym programie, aby dostać się do wartości na która wskazuje zmienna wskaźnikowa (inaczej mówiąc do zmiennej umieszczonej w pamięci pod adresem zawartym w zmiennej wskaźnikowej) musimy do nazwy zmiennej dodać znak „ ^ ”
var
x, y : ^integer;
z : integer;
begin
{...}
z := 2
x^ := z + 2;
y := x^ * 3
z := x^ + y^;
{...}
end.
Operacje na wskaźnikach
Na zmiennych wskaźnikowych można wykonać niewiele operacji. Zmienne wskaźnikowe jak i zmienne przez nie wskazywane można przypisywać - należy wtedy pamiętać aby typy były zgodne. Istnieje możliwość wyłączenia kontroli typów zmiennych wskazywanych przez wskaźniki - pozwala to na różne interpretacje wartości zmiennej. W podanym poniżej przykładzie zastosowano operator "@" - nazwa identyfikatora zmiennej (lub podprogramu) poprzedzona tym operatorem daje adres (czyli wskaźnik) do danej zmiennej. W przykładzie do zmiennej p (wskaźnika do tablicy 6-cio bajtowej) wstawiamy adres do zmiennej x typu REAL (też 6-cio bajtowej). Umożliwia nam to dostęp do poszczególnych bajtów zmiennej x:
type
TByteArray=array[1..6] of byte;
var
x : real;
p : ^TByteArray;
i : integer;
s : string;
begin
x := 2.5;
p := @x;
Writeln('Liczba typu real o wartości: ', x:0, ' składa się z następujących bajtów:');
for i := 1 to 6 do
Writeln('Bajt ', i, ' = ', p^[i] );
s := `ABC';
p := @s;
Writeln('Łańcuch o wartości: ', s, ' składa się z następujących bajtów:');
for i := 1 to 6 do
Writeln('Bajt ',i,' = ', p^[i] );
end.
Oprócz przypisania wskaźniki można porównywać. Pozwala to sprawdzić czy dwa wskaźniki wskazują na to samo miejsce w pamięci. Aby stwierdzić czy zmiennej wskaźnikowej nadano wartość wprowadzono definicję specjalnego adresu, który oznacza umowny „brak adresu” - „nil”. Tak więc, aby sprawdzić czy zmienna wskaźnikowa wskazuje na jakąś zmienną można użyć konstrukcji:
if zmienna <> nil then {operacje na zmiennej}
Tworzenie i likwidowanie zmiennych dynamicznych
Najważniejszą rzeczą przy zmiennych dynamicznych jest ich tworzenie (inaczej alokacja) w pamięci, a następnie ich likwidowanie. Do utworzenia zmiennej (czyli rezerwacji miejsca w pamięci na zmienną wskazywana przez zmienną wskaźnikową) służy procedura NEW:
procedure new(var x : pointer);
Procedura new rezerwuje w pamięci RAM obszar pamięci, który pozwoli przechować zmienną typu wskazywanego przez zmienną wskaźnikową x. Adres początku tego obszaru pamięci wpisywany jest do zmiennej x.
Operację odwrotną wykonuje procedura DISPOSE:
procedure dispose(var x : pointer);
Procedura ta eliminuje zmienną dynamiczną wskazywaną przez wskaźnik i zwalnia zajmowany przez nią obszar pamięci na stercie. Należy pamiętać, że likwidowanie zmiennej dynamicznej procedurą dispose nie nadaje niestety zmiennej wskaźnikowej wartości NIL. Operację tą należy przeprowadzić samodzielnie i nie odwoływać się do obszaru, który został już zwolniony.
Przykład
type ident = record
imie, nazwisko : string[20];
end;
wskident = ^ident; { typy wskaźnikowe }
var id1, id2 : wskident; { zmienne wskaźnikowe }
Przed wykonaniem procedury new():
id1 ? wskaźniki nie zainicjowane
id2 ?
Po wykonaniu procedury new( id1):
id1 adres zmiennej → ? | ? zmienne wskazywane nie zainicjowane
Czytanie zmiennych wskazywanych
readln ( id1^.imie, id1^.nazwisko);
id1 adres zmiennej → Jan | Kowal zmienne wskazywane zainicjowane
Można użyć instrukcji wiążącej with
with id^ do readln ( imie, nazwisko);
Podstawienie
id2 := id1;
powoduje, że oba wskaźniki wskazują na ten sam obszar pamięci. Zlikwidowanie zmiennej dynamicznej procedurą dispose (id1) (lub dispose(id2)) sprawi, że wskazanie przez drugi wskaźnik nie będzie już dłużej aktualne.
Przykład
Utworzenie tablicy dynamicznej
type tablica = array[1..100] of real;
var wsk : ^tablica; { deklaracja zmiennej wskaźnikowej }
new (wsk); { utworzenie zmiennej dynamicznej typu tablica }
wsk^[40] := 12.34; { odwołanie do 40 elementu tablicy }
Przykład
Tablica wskaźników
W wielu zastosowaniach bardzo przydatne jest umieszczenie zmiennych wskaźnikowych w tablicy. Jeżeli wskaźniki wskazują na rekordy, to otrzymujemy zamiast tablicy rekordów tablicę wskaźników na rekordy. Podejście takie pozwala na przykład na szybkie uporządkowanie rekordów według pewnego klucza. Zamiast bowiem porządkować rekordy, będziemy porządkować wskaźniki.
tab[1]^ → rekord
tab[2]^ → rekord
tab[3]^ → rekord
. . . . . . . . . . . . . . .
tab[n]^ → rekord
Element tab[i] wskazuje na zmienną dynamiczną tab[i]^, która w tym przypadku jest rekordem.
Tablicę wskaźników wykorzystamy w przykładzie fragmentów programu umożliwiającego obsługę bazy danych o pracownikach.
type ident = record
imie, nazwisko : string[20];
end;
data = record
dzien, miesiac, rok : integer;
miejsce : string[30];
end;
adresprac = record
kod : string[6];
miejscowosc, ulica : string[30];
telefon : string[10];
end;
poziomprac = record
wyksztalcenie, stanowisko : string[30];
end;
pracownik = record
nazw : ident;
urodz : data;
adres : adresprac;
poziom : poziomprac;
end;
wskprac = ^pracownik; { wskaźniki na rekordy typu pracownik }
tablica = array[1..100] of wskprac;
var baza : file of pracownik; { plik rekordów }
twsk : tablica; { tablica wskaźników }
n, pozycja : integer; { aktualny rozmiar tablicy wskaźników }
procedure Wstaw ( n:integer; var twsk:tablica; nowy:wskprac);
{umożliwia wstawienie nowego rekordu (wskaźnika) na miejsce określone przez nazwisko pracownika. Tablica zawiera n-1 elementów, a n-ty element jest pusty. Przeszukiwanie tablicy od końca do początku z przesuwaniem elementów w prawo aż do znalezienia właściwego miejsca i wstawianie nowego elementu na właściwe miejsce}
begin
if n>1 then
while ( twsk[n-1]^.nazw.nazwisko > nowy^.nazw.nazwisko )
begin
twsk[n] := twsk[n-1]; { przesunięcie w prawo }
n := n-1;
end;
twsk[n] := nowy;
end;
procedure Czytaj ( var n:integer; var twsk:tablica);
{ procedura wczytywania nowego rekordu }
var nowy : wskprac;
begin
ClrScr;
new (nowy); { utworzenie zmiennej dynamicznej dla zapamiętania rekordu }
with nowy^, nazw, urodz, adres, poziom do
begin
write (`Podaj imię: `);
readln (imie);
. . . . . . . . . . . . . . { wczytanie wszystkich danych do rekordu }
end;
n := n+1;
Wstaw (n, twsk, nowy); { wstawienie nowego wskaźnika na właściwe miejsce }
end;
procedure Wyszukaj ( n:integer; klucz:string; twsk:tablica; var pozycja:integer);
{ procedura wyszukiwania binarnego rekordu zawierającego podany klucz }
var lewy, { lewy kraniec przedziału }
prawy, { prawy kraniec przedziału }
srodek: { środek przedziału }
integer;
wynik: boolean; { wynik wyszukiwania }
begin
lewy := 1; prawy := n;
wynik := false;
repeat
srodek := (lewy+prawy) div 2;
if twsk[srodek]^.nazw.nazwisko = klucz then wynik := true
else
if twsk[srodek]^.nazw.nazwisko < klucz then lewy := srodek+1
else prawy := srodek-1;
until wynik or ( lewy>prawy);
if wynik then pozycja := srodek { znaleziono rekord }
else pozycja := 0;
end;
Przykład
Dynamiczna tablica rekordów.
type wpis = record
nazwisko, wydzial : string[30];
ocena : real;
end;
tablica = array[1..N] of wpis;
wskaznik =^tablica;
var wsk :wskaznik;
i : integer;
begin
new (wsk); { utworzenie tablicy dynamicznej }
if wsk = nil then Exit; { sprawdzenie czy prawidłowa alokacja pamięci }
for i:=1 to N do
begin
readln (wsk^[i].nazwisko); { wczytanie danych do tablicy }
. . . . . . . . . . . . . . . . . . . . . . .