Wiadomosci wstępne

W Pascalu typy wskaźnikowe zostały wprowadzone w celu umożliwienia posługiwania się w programach tzw. zmiennymi dynamicznymi (odróżnienie od powszechnie znanych i dotychczas stosowanych zmiennych statycznych).
 

type    identyfikator_typu    = ^identyfikator_typu_bazowego;

Zmienne statyczne powoływane są przez napisanie w programie odpowiednich deklaracji i definicji, czas ich istnienia związany jest z blokiem, w którym  je zadeklarowano (wyjątek - pliki stałe). Powoływane są one z chwilą wejścia do danego bloku, a przestają istnieć w momencie opuszczania bloku.

Zmienne dynamiczne powoływane są na żądanie podczas realizacji programu. Czas ich istnienia nie jest związany z blokową strukturą programu. Zmienne te istnieją dopóki nie zostaną usunięte odpowiednim zleceniem.

Zmienne statyczne powstają na skutek napisania odpowiednich definicji i deklaracji, a zmienne dynamiczne powstają na skutek realizacji instrukcji tworzenia tych zmiennych.

Zasadniczym powodem stosowania zmiennych dynamicznych jest fakt, że umożliwiają one przechowywanie w pamięci operacyjnej obiektów o rozmiarach nie dających się z góry przewidzieć. Przy użyciu rekordu czy też tablicy musimy jawnie określić z ilu i jakich elementów będzie się składać struktura. Pliki umożliwiające tworzenie struktur o różnych rozmiarach ale przechowywane w pamięci zewnętrznej komputera są niewygodne w użyciu. Tworzenie w pamięci dużych struktur danych "na zapas" jest nieuzasadnioną rozrzutnością.

Tworzenie nowych zmiennych dynamicznych umożliwia standardowa procedura New, a ich usuwanie procedura Dispose. Zmienne dynamiczne, ze względu na sposób ich tworzenia nie mają nazwy (identyfikatora), stąd nazywa się je czasami zmiennymi niejawnymi (anonimowymi). Odwołanie do zmiennych dynamicznych typu Typ umożliwiają zmienne pomocnicze typu wskaźnikowego (zmienne wskaźnikowe), zwane wskaźnikami. Wskazywany przez nie odpowiedni obiekt (zmienna dynamiczna) nazywany jest zmienną wskazywaną.

Tworzenie struktury dynamicznej dowolnej wielkości umożliwia fakt, że zmienna  wskazywana nie musi być zmienną statyczną (np. zmienna wskazywana może być rekordem zawierającym pole typu wskaźnikowego).

Dynamiczne struktury danych to proste i złożone struktury danych, którym pamięć może być przydzielana i zwalniana podczas wykonywania programu. Dynamiczne struktury listowe to uporządkowane zbiory składników, niekoniecznie o jednakowych typach. Wśród tych struktur można wyróżnić:

• stosy (stack) - wstawianie, usuwanie i dostęp są możliwe tylko w jednym końcu, wierzchołku stosu (struktura LIFO - Last Input First Output)

• kolejki (queue) dołączanie wskaźników możliwe jest tylko w jednym końcu, a usuwanie w drugim (struktura FIFO - First Input First Output)

• listy liniowe (jednokierunkowe, dwukierunkowe, cykliczne) - dla każdego składnika takiej listy określony jest składnik poprzedni i następny; w dowolnym miejscu takiej struktury można usunąć lub dołączyć element

• drzewa - struktury, w których dla każdego składnika (poza pierwszym) określony jest jeden składnik poprzedni, a dla każdego składnika poza ostatnim określonych jest n (n>=2) składników następnych

• grafy - definiowane przez dwa zbiory: zbiór wierzchołków i krawędzi definiujący powiązania pomiędzy poszczególnymi elementami

Sposób działania stosu (wg. A.Marciniaka, Turbo Pascal 5.5)

Stos to struktura liniowo uporządkowanych elementów (składników) stosu, z których tylko największy (ostatnio umieszczony) jest dostępny. Miejsce dostępu to wierzchołek stosu (jedyne miejsce, do którego można dołączać lub z
którego można usuwać elementy - składniki).

Każdy element (składnik) stosu jest rekordem, w którym:

• pierwsze pole to umieszczane na stosie Dane (umowna nazwa pewnej uprzednio zdefiniowanej struktury typu TypDanych)

• drugie to wskaźnik pokazujący składnik - element (a dokładniej jego adres) następujący po nim (położony na stosie poprzednio); wskaźnik ostatniego składnika stosu wskazuje na adres pusty (nil)

W celu tak zwanego ustalenia uwagi i ułatwienia tworzenia stosu a następnie jego przetwarzania zdefiniujemy następujące typy.
 

type    WskaznikStosu =^SkladnikStosu;    SkladnikStosu = record                      Dane     : TypDanych;                      Wskaznik : WskaznikStosu                    end;

TypDanych oznacza pewien typ standardowy lub zdefiniowany przez programistę. Zakładamy, że wszystkie dane są tego samego typu (mają tą samą wielkość). W ogólności TypDanych może być różny dla różnych składników.

Typ wskaźnikowy WskaźnikStosu związany jest ze zbiorem wskazań danych typu SkladnikStosu. Zmienne typu WskaznikStosu ( w naszym przykładzie Wierzcholek) określają adresy pamięci danych typu SkladnikStosu.

Pewnym kompromisem w tworzeniu złożonych dynamicznych struktur danych jest utworzenie statycznej struktury, najczęściej tablicy, w której zapamiętywane są wskaźniki do obiektów (składników) tworzonych w pełni dynamicznie.
 

type    Character     = record         { rekord odpowiadajacy znakowi ekranu }                      Ch : Char;   { znak ekranu w trybie tekstowym }                      At : Byte;   { jego atrybut - atrament i tlo }                     end;    ScreenType    = array [1..25, 1..80] of Character; { ekran tekstowy }    ScreenTypePtr =^ScreenType;    { typ wskaźnikowy pokazujący na ekran }    TypDanych     = ScreenType;    { TypDanych przechowywanych na s t os i e }    WskaznikStosu =^SkladnikStosu; { typ wskazujący na skladnik stosu }    SkladnikStosu = record         { deklaracja typu SkladnikStosu }                      Dane : TypDanych;                      Wskaznik : WskaznikStosu                    end;  var    Screen      : ScreenTypePtr;   { wskażnik pokazujacy na pamiec ekranu }    Wierzcholek : WskaznikStosu;   { wskaznik wierzcholka stosu }  procedure InitScreen (var Screen : ScreenTypePtr);  begin                            { przypisanie adresu pamieci ekranu }    if Lo(LastMode)=7 then         { jesli tryb Hono - Hercules }      Screen:=Ptr($B000,0000)    else                           { w przeciwnym przypadku }      Screen:=Ptr($B800,0000)  end;  procedure NaStos (var Wierzcholek: WskaznikStosu;                    var Screen : ScreenTypePtr);  var    Punkt     : WskaznikStosu;  begin    Punkt:=Wierzcholek;    { zapamietanie w zmiennej punkt nowego wierzcholka }    New (Wierzcholek);     { utworzenie nowej zmiennej dynamicznej }    with Wierzcholek^ do   { wpisanie nowej danej i wskaznika }    begin      Dane. =Screen^;      { nowy ekran na stosie }      Wskaznik:=Punkt      { wskaznik do kolejnego elementu stosu }    end  end;  procedure ZeStosu (var Wierzcholek: WskaznikStosu;                     var Screen : ScreenTypePtr);  var    Punkt     : WskaznikStosu;  begin    if Wierzcholek <> nil then { sprawdzenie czy jest cos do zdjecia }    begin      with Wierzcholek^ do      begin        Screen^-=Dane;       { przepisanie danej na ekran }        Punkt:=Wskaznik      { przepisanie starego wskaznika }      end;      Dispose (Wierzcholek); { zwolnienie miejsca w pamieci }      Wierzcholek:=Punkt     { nowy wierzcholek stosu }    end   end;

 

Porównanie programu o strukturze statycznej i dynamicznej

type     Uczen = record                { typ danych, np. rekord }               Imie  : String[5];  { pierwsze pole - imie ucznia}               Ocena : Real        { drugie pole - jego ocena }             end;   var      U1,U2   : Uczen;      Srednia : Real;   begin     ReadLn (U1.Ocena ) ;     Readln (U2.Ocena) ;     Srednia:=(U1.Ocena + U2.Ocena)/2;     Writeln('Srednia = ' , Srednia:4:2);   end.

 

type { U W A G A : te definicje typow moga byc zamienione miejscami }     Uczen = record              { typ wskazywany, np. rekord }               Imie : String[5]; { pierwsze pole - imie ucznia}               Ocena : Real      { drugie pole - jego ocena }              end;     Uczniowie =^Uczen;          { typ wskaznikowy do typu Uczen }   var     U1,U2 : Uczniowie;          { U1, U2 to wskazniki do Ucznia }     Srednia : Real;   begin     New(U1);                    { powolanie do zycia U1 }     Readln (U1^.Ocena);         { czytanie danych ucznia 1 }     New(U2);     Readln(U2^.Ocena);     Srednia:=(U1^.Ocena + U2^.Ocena)/2;     Writeln('Srednia = ' , Srednia:4:2);     Dispose(U1);                { likwidacja U1 }     Dispose(U2);                { likwidacja U2 }   end.

• Ul, U2 to wskaźniki (pointery) do odpowiednich  wskazywanych przez nie struktur danych  (pewne adresy, mówiące gdzie fizycznie  w pamięci są one zapamiętane)

• U1^, U2^ wskazują (pokazują) na odpowiednie  struktury danych umieszczone w pamięci  zarezerwowanej na dynamiczne struktury  danych

• Uczniowie =^Uczen definicja typu wskazującego  na typ Uczen

Uwaga: Deklaracja zmiennych Ul i U2 może być  również w inny sposób, bez powoływania  typu wskaźnikowego Uczniowie : Ul, U2 :^Uczen

---