7356


  1. Typ wskaźnikowy, organizacja list

    1. Charakterystyka ogólna

Dotychczas były omawiane statyczne struktury danych takie, jak tablice, rekordy, pliki i zbiory. Oprócz cech charakterystycznych każdego typu, mają one pewne cechy wspólne. Na przykład maksymalna liczba elementów tablicy, rekordu i zbioru jest ograniczona. Jest ona określona za pomocą deklaracji i nie ulega zmianom podczas pracy programu. Ponadto, co dotyczy także plików, poszczególne elementy tych struktur są umieszczone w pamięci, w stałej kolejności względem siebie, (stała numeracja elementów tablicy, pliku i zbioru, stała kolejność pól rekordu). Spójny obszar pamięci na te zmienne, stanowiące zmienne globalne programu, jest przydzielany podczas kompilacji. Jest on umieszczany w obszarze pamięci statycznej (segment danych - ang. data segment). Jego rozmiar nie może jednak wynosić więcej niż 65520 bajtów, na wszystkie zmienne statyczne (w tym dla pliku tylko na nagłówek pliku). Zmienne lokalne, deklarowane w procedurach, są umieszczane w segmencie stosu - (ang. stack), którego rozmiar może zawierać się pomiędzy 1024 i 65520 bajtów. Standardowy rozmiar segmentu stosu jest równy 16384 bajty. Pamięć dla zmiennych lokalnych jest przydzielana przy wywołaniu procedury i zwalniana po jej zakończeniu. Rozmiar pamięci stosu dla programu można określić za pomocą pierwszego parametru dyrektywy kompilatora {$M...}.

Te cechy statycznych struktur danych uniemożliwiają zastosowanie ich do pewnego rodzaju aplikacji, w których dynamicznie tworzy się grupy elementów danych, o nieokreślonej z góry i często zmieniającej się liczbie elementów. Pewne aplikacje wymagają stosowania list, których elementy zajmują niespójny obszar pamięci i są połączone logicznie za pomocą specjalnych łączników (wiązań, wskaźników). Dla tych struktur danych, podczas kompilacji są przydzielane obszary na zmienne reprezentujące ich nagłówki. Natomiast dla danych, umieszczanych w elementach list, oraz samych elementów, pamięć jest przydzielana i zwalniana dynamicznie, na żądanie.

Zmienne dynamiczne są umieszczane w pamięci dynamicznej nazywanej stertą (ang. heap). Jej rozmiary - minimalny i maksymalny, określa się za pomocą dyrektywy kompilatora {$M...}, dla której stanowią odpowiednio drugi i trzeci parametr. Standardowy rozmiar sterty jest taki jak dla stosu.

    1. Zasady organizacji struktur listowych

Jeżeli pamięć może być przydzielana zmiennym dynamicznym na żądanie, podczas wykonywania programu, to podczas kompilacji, w pamięci statycznej rezerwuje się tylko miejsce, na przechowywanie adresu obszaru pamięci, przydzielanego tym zmiennym. Aby jednak nie przechowywać adresu każdej zmiennej generowanej dynamicznie, zmienne dynamiczne łączy się w grupy, których elementy są dostępne za pomocą adresu, wskazującego na pierwszy element grupy.

Struktury listowe służą do grupowania zmiennych dynamicznych jednego typu. Podstawową ideą listy jest to, że każdy jej element, stanowiący zmienną dynamiczną, oprócz danych zawiera łącznik, który wskazuje, gdzie znajduje się następny element listy. Każdy element może być do listy dołączony, lub z niej usunięty, bez zmiany położenia innych elementów listy w pamięci. Liczba elementów listy nie jest z góry ograniczona. Praktycznie takie ograniczenie wynika z rozmiarów: elementu listy i pamięci sterty.

Listą prostą (ang. linked list, linear list) jest nazywana struktura danych, w której każdy element ma tylko jeden bezpośredni następnik i tylko jeden bezpośredni poprzednik. (W odróżnieniu od drzewa, stanowiącego strukturę hierarchiczną, w którym każdy element może mieć jeden bezpośredni poprzednik i wiele bezpośrednich następników).

Struktury danych wykorzystujące ideę list różnią się dwoma cechami:

Ze względu na sposób łączenia rozróżnia się

Lista jednokierunkowa składa się z elementów, które oprócz danych elementu, zawierają jeden łącznik, wskazujący na następny element listy. Dostęp do elementów listy jest sekwencyjny, przez przeglądanie ich w kolejności od pierwszego do ostatniego. Do tego celu wykorzystuje się:

Lista dwukierunkowa składa się z elementów, które oprócz danych elementu listy, zawierają dwa łączniki, jeden do następnego, a drugi do poprzedniego elementu listy. Dostęp do elementów listy dwukierunkowej jest także sekwencyjny. Przy pamiętaniu wskaźnika końca listy, lista taka może być przeglądana także w porządku odwrotnym, czyli od ostatniego do pierwszego elementu.

Lista cykliczna zawiera dodatkowy element listy stanowiący jej nagłówek, który wskazuje na pierwszy i ostatni element listy. Ten element jest poprzednikiem pierwszego elementu listy i następnikiem ostatniego elementu listy. Lista cykliczna może być zrealizowana w oparciu o listę jedno- lub dwukierunkową. Praktyczne zastosowania mają listy cykliczne dwukierunkowe.

Ze względu na organizację logiczną nałożoną na fizyczną strukturę listy wyróżnia się

struktury danych uporządkowane według:

Według kolejności dołączania elementów rozróżnia się struktury danych, w których elementy są uporządkowane w kolejności:

Struktury danych uporządkowanych według jednego, lub wielu atrybutów nazywane są listami uporządkowanymi.

Operacje na listach jednokierunkowych będą omawiane w p. 13.4, na listach dwukierunkowych w p. 13.5 i cyklicznych w p. 13.7. Zasady organizacji różnych rodzajów stosów, kolejek, list uporządkowanych i innych dynamicznych struktur danych będą rozważane w rozdziale 14. Jest możliwe, aby element listy w swoich atrybutach danych, zawierał wskaźnik początku swojej podlisty, lub dodatkowe łączniki za pomocą, których mógłby być dołączony do innej listy. Są to struktury danych bardziej złożone od list prostych. Jednak zasady ich organizacji, a tym samym zasady ich programowania, wykorzystują zasady dotyczące list prostych. Wszystkie dynamiczne struktury danych są tworzone w oparciu o typ wskaźnikowy.

    1. Typ wskaźnikowy

Pascal wzorcowy i Turbo Pascal definiują typ wskaźnikowy, który umożliwia organizację dynamicznych struktur danych dowolnego typu, przy stosowaniu zbioru tych samych zasad.

Przy stosowaniu zmiennych dynamicznych wyróżnia się dwa rodzaje zmiennych:

Zmienne wskaźnikowe są zmiennymi statycznymi - nazywanymi też referencyjnymi, które wskazują na zmienne dynamiczne. Postać definicji typu wskaźnikowego jest następująca:

TYPE Nazwa_Typu_Wskaźnikowego=^Nazwa_Typu;

Definicja typu wskaźnikowego, np. PT wiąże go więc z typem wskazywanym np. T:

PT = ^T;

Każdy typ wskaźnikowy, związany z innym typem wskazywanym, jest różny, mimo że zmienne każdego typu wskaźnikowego służą do przechowywania adresu zmiennej wskazywanej.

      1. Deklaracja typu

Typ wskaźnikowy może być związany z różnymi typami danych:

TYPE

PI=^INTEGER;

PR=^REAL;

PB=^BYTE;

a także z typem plikowym

plik=FILE OF Element;

PPlik = ^plik;

Te typy jednak mają małe praktyczne zastosowanie. Praktyczne zastosowanie do organizacji dynamicznych struktur danych mają typy wskaźnikowe związane z rekordami, a także typ wskaźnikowy związany z typem napisowym:

PS=^STRING;

Typem wskazywanym, wykorzystywanym do organizacji list, musi być typ rekordowy zawierający pole reprezentujące dane, przechowywane w elemencie listy, oraz jedno lub dwa pola łączników typu wskaźnikowego. Mogą to być pola o nazwach np.: Nast i Poprz. Pole Nast, zarówno w liście jedno- jak i dwukierunkowej - wskazuje na następny element listy,. Pole Poprz - wskazuje na poprzedni element listy w liście dwukierunkowej. Definicja typu rekordowego T, służącego do organizacji listy jednokierunkowej i jego typu wskaźnikowego PT, może mieć następującą postać:

TYPE

PT=^T;

T =RECORD

Dane:Typ_Danych;

Nast:PT;

END;

Ta definicja zawiera strukturalne pole, zawierające dane elementu listy typu Typ_Danych, który musi być wcześniej zdefiniowany. Dane elementu listy mogą być także deklarowane bezpośrednio, jako pola elementu listy, bez użycia pomocniczego typu rekordowego.

Wyłącznie przy definicji typu wskaźnikowego używa się nazwy typu wskazywanego, przed jego zdefiniowaniem. Położenie pól wskaźnikowych w rekordzie jest nieistotne. Na rysunkach poniżej, dla ich uproszczenia przyjęto, że pole zawierające łącznik do elementu listy jednokierunkowej, jest pierwszym polem rekordu dynamicznego.

      1. Deklaracje zmiennych wskaźnikowych

Deklaracja zmiennej wskaźnikowej:

VAR AdrT:PT;

podczas kompilacji programu rezerwuje pamięć na przechowywanie adresu, który może wskazywać na obszar pamięci, zawierający rekord typu T. Adres ten nie jest określony po kompilacji programu, a tym samym pamięć na rekord typu T, nie jest jeszcze przydzielona. Wartość nieokreślonego adresu jest oznaczana za pomocą stałej NIL. Zmiennym wskaźnikowym, które w programie będą podlegały badaniu, przed ich modyfikacją, powinno się nadawać wartości początkowe:

AdrT:=NIL;

Dla każdej listy implementowanej w programie, będącej listą globalną, należy zadeklarować zmienną reprezentującą adres początku tej listy np.:

VAR pocz:PT;

Dla struktur danych listowych, w których przewiduje się dopisywanie nowych elementów na końcu listy, należy także zadeklarować zmienną reprezentującą koniec listy np.:

VAR kon:PT;

Te zmienne powinny być przekazywane jako parametry do procedur wykonujących działania na liście. W tych procedurach należy deklarować zmienne wskaźnikowe lokalne, np. na nowy element dołączany do listy lub na adres bieżącego elementu listy przeglądanej listy.

Zmienne dynamiczne, w odróżnieniu od zmiennych statycznych, nie mają nazwy, są identyfikowane za pomocą adresu wskazującego na początek obszaru zajmowanego przez zmienną. Wielkość tego obszaru (równa SIZEOF(T)) i kolejność pól rekordu dynamicznego są określone przez typ zmiennej wskazywanej. Nazwę "posiada" tylko zmienna dynamiczna, na którą aktualnie wskazuje zmienna wskaźnikowa. Adres zmiennej dynamicznej jest wpisywany do zmiennej wskaźnikowej podczas jej generacji i programista tym adresem jawnie nie manipuluje. Wartość adresu można jednak odczytać podczas wykonywania programu, na zasadzie zwykłego podglądu zmiennych, udostępnianego przez program uruchamiający debugger.

Zbliżony do typu wskaźnikowego, w sensie przeznaczenia, jest predefiniowany typ adresowy POINTER. Zmienne typów wskaźnikowych oraz zmienne typu POINTER zajmują 4 bajty.

Zmienne

VAR

AdrT:PT;

adr :POINTER;

mogą być przypisywane, przy czym zarówno przypisanie:

adr:=adrT;

jak i przypisanie

adrT:=adr;

są poprawne w Turbo Pascalu 7.0. oraz w BP. W starszych wersjach TP drugie przypisanie wymagało konwersji typu:

adrT:=PT(adr);

W TP7 zdefiniowano dodatkowy typ wskaźnikowy PCHAR, dostępny przy opcji rozszerzonej składni {$X+}, służący do operowania długimi napisami (z zakresu 255..65535 znaków) o zmiennej i nieokreślonej długości. Napis tego typu nie zawiera licznika długości, ale kończy go wyróżniony znak CHR(0). W module Strings, zdefiniowano zbiór procedur do obsługi tego typu, podobnych do procedur działających na napisach, rozszerzony o dodatkowe możliwości.

      1. Przydzielanie i zwalnianie pamięci dla zmiennych dynamicznych.

        1. Generowanie i kasowanie zmiennych dynamicznych

Zmienne dynamiczne nie są deklarowane tak jak zmienne statyczne, ponieważ są generowane i kasowane dynamicznie, podczas działania programu. Istnieją w programie od chwili wygenerowania do chwili skasowania. W programie deklaruje się zmienne, wskazujące na zmienne dynamiczne. Deklaracja zmiennej typu wskaźnikowego ma postać:

VAR Nazwa_Zmiennej_Wskazującej=Nazwa_Typu_Wskaźnikowego;

Deklaracja zmiennej wskaźnikowej p, która będzie wskazywać na element typu T:

VAR p:PT;

rezerwuje obszar pamięci na adres zmiennej dynamicznej, a nie na samą zmienną. Przydzielenie pamięci na zmienną dynamiczna, o rozmiarze odpowiednim do typu zmiennej wskazywanej, jest realizowane za pomocą instrukcji NEW. Może ona być wywoływana w dwóch wersjach: jako procedura:

NEW(p);

lub jako funkcja:

p:=NEW(PT);

Wykonanie instrukcji NEW, oprócz przydziału pamięci, powoduje przypisanie adresu początkowego przydzielonego obszaru pamięci do zmiennej wskaźnikowej p, użytej w instrukcji. Generowanie nowej zmiennej dynamicznej jest wykonywane wówczas, gdy program potrzebuje dodatkowego miejsca, na nowe dane. Dopiero po wygenerowaniu zmiennej dynamicznej można nadać wartości, polom rekordu dynamicznego. Na przykład po wykonaniu NEW(p), można nadać wartości polom rekordu typu T, wskazywanego przez zmienną p.

Powiązanie zmiennej wskaźnikowej ze zmienną dynamiczną pokazuje rys. 13.1. Na tym i dalszych rysunkach przyjęto, że adresy kolejno generowanych rekordów dynamicznych będą oznaczone literami:

A, B, C, D...

Rys. 13.1 Powiązanie zmiennej wskaźnikowej ze zmienną dynamiczną

A- umowny adres obszaru pamięci, przydzielonego na zmienną dynamiczną przez instrukcję NEW(p).

Zwolnienie pamięci zajmowanej przez zmienną dynamiczną, wskazywaną przez p, realizuje instrukcja:

DISPOSE(p);

Instrukcję DISPOSE wykonuje się po ostatnim wykorzystaniu danych ze zmiennej dynamicznej. Dane, które stały się zbędne dla programu, są w ten sposób kasowane, w celu zwolnienia obszaru pamięci sterty na dalsze zmienne dynamiczne. Kolejność zwalniania pamięci jest niezależna od kolejności jej przydziału. Zwalniany jest obszar, na który wskazuje zmienna wskaźnikowa. Zwolnienie obszaru już zwolnionego - jest błędem. Odwoływanie się do pól rekordu zwolnionego nie jest wykrywane, ale może doprowadzić do błędu wykonania. Może on spowodować zawieszenie się programu, ponieważ dane mogą zostać przypadkowo wpisane pod niepożądany adres i zniszczyć, znajdujący się tam fragment programu.

Każda wykonanie instrukcji:

NEW(p);

przydziela nowy obszar na zmienną dynamiczną typu T i zapamiętuje adres początkowy przydzielonego obszaru w zmiennej p. Adres przechowywany w zmiennej przed wykonaniem kolejnego NEW, zostanie zniszczony. Aby zmienne dynamiczne nie gubiły się i nie zaśmiecały sterty, muszą zostać zwolnione lub dołączone do struktury danych, grupującej zmienne dynamiczne, przed wykonaniem kolejnej instrukcji NEW, z nazwą tej samej zmiennej. O tym jak będą łączone rekordy dynamiczne, będzie decydował typ struktury danych, którą programista chce zastosować w programie.

        1. Zwalnianie pamięci dla grupy zmiennych dynamicznych

Jeżeli pamięć dynamiczną przydziela się i zwalnia jednocześnie dla grupy rekordów, można całą pamięć zwolnić jedną instrukcją. W tym celu należy zarejestrować adres początku sterty przed pierwszym przydzieleniem przez NEW(p), w pewnej zmiennej, np. V typu POINTER przez wykonanie instrukcji:

MARK(V);

Procedura RELEASE(V), zwalnia całą pamięć dynamiczną przydzieloną programowi, w czasie od wykonania MARK do wykonania RELEASE.

Pamięć na stercie jest przydzielana blokami, stanowiącymi wielokrotność 8 bajtów. Wielkość pamięci, przydzielana dla rekordu, jest więc zaokrąglana do liczby bloków, która może pomieścić wszystkie bajty. Ponieważ zwalnianie na ogół nie jest realizowane w tej samej kolejności co przydzielanie, wolna pamięć sterty składa się z bloków różnej wielkości.

Jest dostępna funkcja

MaxAvail typu LONGINT

która podaje rozmiar największego bloku sterty.

a także funkcja:

MemAvail typu LONGINT

która podaje wielkość wolnej pamięci na stercie, będącą sumą rozmiarów wolnych bloków sterty.

        1. Operacje na blokach pamięci

Są także dostępne procedury przydziału i zwalniania bloku pamięci, o rozmiarze określonym w bajtach. Ten przydział pamięci nie jest związany z konkretnym typem, ale wielkość przydzielonego bloku zależy oczywiście od rozmiaru danych, które chce się w nim przechować.

Wielkość żądanego bloku rozmiar i zmienna typu POINTER, przechowująca adres tego bloku są parametrami obydwu procedur, których nagłówki i funkcje są następujące:

GETMEM(VAR adres:POINTER; rozmiar:WORD);

- przydziela blok pamięci,

FREEMEM(VAR adres:POINTER; rozmiar:WORD);

- zwalnia blok pamięci.

Operacje na blokach pamięci są wykorzystywane do przydzielania pamięci na napisy. Napisy nawet okrojone, np. typu:

TYPE st20=STRING[20];

zajmują zawsze o jeden bajt więcej, niż zadeklarowano w deklaracji typu, bez względu na to z ilu znaków, składa się napis, wprowadzony do zmiennej napisowej. W programach wykorzystujących wiele napisów można uzyskać dużą oszczędność pamięci, jeżeli zamiast zmiennych napisowych, będzie się wykorzystywało wskaźniki do napisów. Przydział pamięci na ten napis powinien uwzględniać rozmiar konkretnego napisu. Na przykład dla deklaracji:

TYPE PS=^STRING;

VAR

s :STRING;

ws:POINTER;

d :BYTE;

po nadaniu wartości pomocniczej zmiennej napisowej s, można :

d:=LENGTH(s);

GETMEM(ws,d);

PS(ws)^:=s;

      1. Odwołania do pól rekordów dynamicznych

Dla typu T, w którym zadeklarowano pole nazwisko oraz typu wskaźnikowego PT:

TYPE

PT=^T;

T =RECORD

nazwisko:st20;

Nast :PT;

END;

oraz zmiennej p

VAR p:PT;

selektor pola nazwisko rekordu dynamicznego, ma postać:

p^.nazwisko

Operator '^' (w Pascalu wzorcowym Wirtha znak '↑ ') jest nazywany operatorem wyłuskiwania. Jeżeli do procedury, która ma wczytać (lub wyświetlić) rekord, zostanie przekazany parametr typu wskaźnikowego, przekazujący adres rekordu, tak jak w nagłówku procedury:

PROCEDURE Wprowadz_Rek(VAR adres:PT);

to instrukcja wiążąca używana w procedurze, odnosząca się do rekordu dynamicznego, wskazywanego przez ten parametr, także używa tego operatora:

WITH adres^

BEGIN

WRITE('Podaj nazwisko ');

READLN(nazwisko);

END;

Zapis adres^ jest synonimem nazwy zmiennej typu rekordowego i dotyczy tego rekordu, na który zmienna wskaźnikowa aktualnie wskazuje. Zasady budowy selektorów dla strukturalnych pól rekordu dynamicznego, łączą w sobie zasady odwołania do rekordu dynamicznego i pól statycznych.

      1. Przypisywanie adresów i zmiennych dynamicznych

Jeżeli zadeklarujemy dwie zmienne wskaźnikowe tego samego typu:

VAR p,q:PT;

przypisanie

p:=q;

jest przypisaniem adresów. Po jego wykonaniu, zmienne p i q będą wskazywać na ten sam rekord dynamiczny, do tej pory wskazywany przez q. Wskaźnik p straci dostęp do rekordu, na który wskazywał przed tym przypisaniem. Rekord, wskazywany dotąd przez zmienną p, stanie się po tej operacji niedostępny.

Jeżeli sekwencja instrukcji:

NEW(p);

p^.nazwisko:='Kowalski';

NEW(q);

q^.nazwisko:='Nowak'

zostanie zakończona instrukcją przypisania:

p:=q;

to przypisanie zmiennych wskaźnikowych, spowoduje, że zmienna p straci dostęp do rekordu Kowalskiego, natomiast dwa adresy p i q będą wskazywać na rekord Nowaka. Stan zmiennych przed i po wykonaniu powyższej instrukcji, pokazano na rys. 13.2.

0x01 graphic

a) b)

Rys. 13.2 Powiązanie pomiędzy zmiennymi wskaźnikowymi i rekordami dynamicznymi :
a) przed i b) po wykonaniu instrukcji przypisania wskaźników p:=q.

Natomiast przypisanie:

p^:=q^;

jest przypisaniem rekordów dynamicznych, czyli przypisaniem zmiennych wskazywanych. Realizuje ono skopiowanie treści rekordu dynamicznego, wskazywanego przez zmienną q, do obszaru pamięci wskazywanego przez zmienną p. Po jego wykonaniu obszar pamięci, wskazywany przez p, będzie zawierał dokładnie to samo, co obszar pamięci, wskazywany przez q, czyli że każdemu polu rekordu, wskazywanego przez p, zostanie przypisane odpowiednie pole z rekordu, wskazywanego przez q.

Wykonanie instrukcji:

p^:=q^;

gdy p wskazuje na rekord Kowalskiego, a q na rekord Nowaka, spowoduje, że dane Nowaka wypełnią dwa rekordy, a dane Kowalskiego zginą. Stan zmiennych wskaźnikowych oraz wskazywanych przez nie obszarów pamięci, przed i po omawianym przypisaniu rekordów dynamicznych, pokazano na rys. 13.3.

0x01 graphic

Rys. 13.3 Powiązanie pomiędzy zmiennymi wskaźnikowymi i rekordami dynamicznymi -

a) przed i b) po wykonaniu instrukcji przypisania zmiennych dynamicznych p^:=q^.

Oczywiście można także przypisywać sobie, zgodne co do typu pola rekordów, w tym także pola wskaźnikowe. Przypisanie:

p^.nazwisko:=q^.nazwisko;

tak, jak dla rekordów statycznych, zmienia wartość pola nazwisko w rekordzie, wskazywanym przez p, na nazwisko z rekordu, wskazywanego przez q, pozostawiając pozostałe pola rekordu, wskazywanego przez p, bez zmiany.

Poniżej pokazano przykłady deklaracji typów i zmiennych oraz poprawnych przypisań, wykorzystujących dwa różne typy wskaźnikowe: typ PT, wskazujący na rekord i typ PStr, wskazujący na napis. Sekwencja instrukcji pokazuje jak można przypisać polu typu napisowego (nazwisko), należącego do dynamicznego rekordu, wartość dynamicznego napisu, wskazywanego przez zmienną wskaźnikową, wskazującą na napis.

TYPE

PStr=^STRING;

VAR

AdrElem:PT;

zn :PStr;

el :T;

BEGIN

NEW(zn);

zn^:='Nowak';

el.Nazwisko:='Kowalski';

AdrElem := @el; {lub adrelem :=Addr(el);}

WRITELN(AdrElem^.nazwisko);

AdrElem^.Nazwisko:=zn^;

WRITELN(AdrElem^.Nazwisko);

READLN;

END;

Pierwsza instrukcja WRITELN z tej sekwencji, wyprowadzi nazwisko 'Kowalski', a druga nazwisko 'Nowak'.

Łącznik rekordu, który nie jest połączony z żadnym innym rekordem, powinien wskazywać na wartość NIL. Ustala się to przez przypisanie:

p^.Nast:=NIL;

Dla rekordów wypełnionych danymi Kowalskiego i Nowaka, wskazywanych odpowiednio przez zmienne wskaźnikowe: p -wskazującą na rekord Kowalskiego i q -wskazującą na rekord Nowaka przypisanie:

p^.Nast:=q;

spowoduje, że do rekordu wskazywanego przez p, w polu Nast zostanie wpisany adres rekordu, który był przechowywany w zmiennej wskaźnikowej q. Łącznik w rekordzie wskazywanym przez q, powinien wskazywać na wartość NIL, ponieważ do tego rekordu nie jest dołączony żaden rekord.

q^.Nast:=NIL;

Po wykonaniu operacji połączenia rekordów za pomocą pola łącznika, zmienna p wskazuje na początek dwuelementowej listy rekordów z nazwiskami, która jest pokazana na rys. 13.4.

0x01 graphic

Rys. 13.4 Dwuelementowa lista rekordów zawierających dane Kowalskiego i Nowaka

Po wygenerowaniu i wypełnieniu nowego rekordu:

a) NEW(q);

b) q^.nazwisko:='Ros';

rekord Nowaka nie został zgubiony i możemy do niego dołączyć rekord z danymi Rosa.

Przypisanie:

c) p^.Nast^.Nast:=q;

spowoduje utworzenie trzyelementowej listy rekordów, uporządkowanych w kolejności dołączania, zawierającej dane Kowalskiego, Nowaka i Rosa, pokazanej na rys. 13.5:

Rys. 13.5 Trzyelementowa lista rekordów zawierających dane Kowalskiego, Nowaka i Rosa.

Operacje a) i b) można powtarzać, wpisując nowe dane do rekordów. Operacja c) dołączania na końcu wymagałaby coraz dłuższej sekwencji odwołań do pól łączników, pozwalającej sięgnąć do ostatniego rekordu listy, lub należałoby przeglądać listę, aż do znalezienia ostatniego elementu. Przy dołączaniu elementów na końcu listy, wygodniej jest dodatkowo pamiętać adres ostatniego elementu listy np. k

VAR k:PT;

W tym przypadku dołączenie nowego elementu na końcu listy wymaga:

NEW(q);

q^.Nast:=NIL;

IF p=NIL

THEN p:=q

ELSE k^.Nast:=q;

k:=q;
Pomimo dołączania elementu do końca listy, w jednym przypadku określono także nowy początek listy, ponieważ przy dołączaniu do pustej listy przy p=NIL, dołączany element staje się jednocześnie pierwszym i ostatnim elementem listy.

Pełna procedura dołączania elementu z danymi na końcu listy jest zamieszczona poniżej.

Przy dołączaniu elementu do końca listy można nie używać zmiennej pomocniczej q :

IF k<>NIL

THEN

BEGIN

NEW(k^.Nast);

k:=k^.Nast;

END

ELSE

BEGIN

NEW(k);

p:=k;

END;

Jeżeli p jest pierwszym elementem listy, dołączenie elementu q przed p, czyli na początku listy:

q^.Nast:=p;

wymaga także określenia nowego początku listy:

p:=q;

Jeżeli wszystkie wygenerowane powyżej elementy będą dołączane na początku listy, utworzy się trzyelementowa lista, pokazana na rys. 13.6, w której elementy będą uporządkowane w kolejności odwrotnej do kolejności dołączania.

Rys. 13.6 Trzyelementowa lista rekordów zawierających dane Kowalskiego, Nowaka i Rosa, w postaci stosu.

Przy wykorzystaniu przydzielania i zwalniania pamięci za pomocą procedur GETMEM i FREEMEM, dane muszą być wpisywane do przydzielonego obszaru procedurą MOVE:

MOVE(Nazwa_Zmiennej_Zrodlowej,Nazwa_Zmiennej_Docelowej,Rozmiar);

Parametrem Nazwa_Zmiennej_Zrodlowej, może być zmienna wskaźnikowa.

Zmienne wskaźnikowe porównuje się, aby sprawdzić czy wskazują na ten sam adres, np.

IF p=q...

Najczęściej jednak sprawdza się czy adres jest określony:

IF p<>NIL...

Zmienne wskazywane typu napisowego i typów prostych można porównywać, wykorzystując operatory relacji:

IF p^=q^...

Podobnie można porównywać pola rekordów dynamicznych, np:

IF p^.nazwisko<=q^.nazwisko...

Mogą być one porównywane także z polami rekordów statycznych, ze zmiennymi prostymi i stałymi, typów odpowiednich do typu porównywanego pola.

Zakładanie listy jednokierunkowej, aktualizacja elementów listy oraz wyszukiwanie maksimum w liście, są pokazane w zad48.txt. W p.13.4 omówiono różne algorytmy operacji wykonywanych na liście jednokierunkowej, zaimplementowane przez odpowiednie procedury.

    1. Operacje na liście jednokierunkowej

      1. Struktura elementu i listy

Element listy jednokierunkowej zawiera jeden łącznik do następnego rekordu w liście oraz dowolne dane. Definicja typu elementu listy i typu wskaźnikowego może być następująca:

PElement = ^TElement;

TElement = RECORD

Dane:TDane;

Nast :PElement;

END;

W programie musi być zadeklarowana zmienna wskazująca na początek listy, np.: Pocz.

Jeżeli przewiduje się dołączanie elementów na końcu listy, można dodatkowo zadeklarować zmienną wskazującą na koniec listy, np.: Kon. Struktura takiej listy jest pokazana na rys. 13.7.

Dołączanie elementów na końcu listy, bez pamiętania wskaźnika końca listy wymaga, dla każdego dołączanego elementu, przeglądania listy w celu znalezienia jej ostatniego elementu.

VAR Pocz,Kon:PElement;

Rys. 13.7. Lista jednokierunkowa

      1. Moduł do obsługi listy jednokierunkowej

Operacje wykonywane na listach jednokierunkowych i ich elementach, które będą omawiane w dalszych podrozdziałach, są realizowane przez odpowiednie procedury. Wykorzystują one definicje: typu elementu listy, typu wskaźnikowego, wskazującego na element listy oraz typu danych elementu listy. Zmienne reprezentujące adresy początku i końca listy oraz inne potrzebne do wykonania procedur dane, lub zwracane przez procedurę wyniki, będą przekazywane za pomocą parametrów. Wszystkie wymienione definicje typów i procedur, związane z obsługą określonej struktury danych, mogą zostać umieszczone w jednym module. Jeżeli w module obsługi struktury danych, np. listy jednokierunkowej, definiuje się typ danych, które będą stanowiły dane elementu tej struktury, (np. dane elementu listy), to ten moduł będzie mógł być wykorzystywany tylko do obsługi struktur danych, przechowujących dane tego typu. Aby opracowany zestaw procedur mógł być wykorzystany do tworzenia struktur danych tego samego rodzaju, ale przechowujących inne dane, trzeba będzie wymienić w nim definicję typu danych i obsługujące go procedury, z pozostawieniem przyjętych nazw, używanych w definicjach procedur obsługi struktury danych. Omawiane poniżej procedury, służące do obsługi listy jednokierunkowej, umieszczono w module ListyU1.pas, który znajduje się na dyskietce. Moduł ten zawiera: