Programowanie dynamiczne pod TP


Funkcje i procedury dynamicznego przydziału pamięci


Do rozważanej w tym punkcie grupy należy osiem
funkcji i procedur standardowych: Dispose, FreeMem,
GetMem, Mark, MaxAvail, MemAvail, New i Release. Służą one do
zarządzania obszarem pamięci przeznaczonym na zmienne dynamiczne
oraz do tworzenia i usuwania (zwalniania) zmiennych dynamicznych.

Uwaga: Identyfikator New oznacza procedurę lub funkcję
standardową.

Do utworzenia zmiennej dynamicznej i ustalenia zmiennej
wskaźnikowej wskazującej na nią (dokładniej: podstawienia pod
zmienną wskaźnikową odpowiedniego adresu pamięci) służą procedury
New i GetMem.

Wywołanie procedury New ma postać:

New (zmienna-wskaźnikowa)

lub

New (zmienna-wskaźnikowa, konstruktor)

W obu przypadkach do utworzonej za pomocą wywołania zmiennej
dynamicznej można odwołać się za pomocą zmiennej wskazywanej
postaci zmienna-wskaźnikowa^ (zob. p. 9.5). Przydzielony przy tym
zmiennej dynamicznej blok pamięci jest równy rozmiarowi typu, z
którym związana jest wyspecyfikowana zmienna wskaźnikowa. Jeśli
w obszarze pamięci przeznaczonym na zmienne dynamiczne nie ma
wystarczającej pamięci, to wystąpi błąd. Drugą postać wywołania
procedury New stosuje się do utworzenia zmiennej dynamicznej typu
obiektowego. Konstruktor oznacza tu wywołanie odpowiedniego kon-
struktora. Szczegóły dotyczące tworzenia i przetwarzania
obiektów, w tym obiektów dynamicznych, znajdują się w rozdziale
15.

Druga procedura (GetMem), której wywołanie ma postać:

GetMem (zmienna-wskaźnikowa, rozmiar)

gdzie rozmiar oznacza w ogólności wyrażenie typu Word, powoduje
utworzenie zmiennej dynamicznej (do której można odwołać się za
pomocą konstrukcji zmienna-wskaźnikowa^) o podanym (w bajtach)
rozmiarze. Podobnie jak poprzednio może przy tym wystąpić błąd,
jeśli w segmencie pamięci przeznaczonym na zmienne dynamiczne
brakuje wystarczającego obszaru.

Przykłady 14.6

1) Załóżmy, że w pewnym programie zdefiniowano typ tablica i
zmienną wskaźnikową wskaznik:

type tablica = array [1..100] of Real;
var wskaznik : ^tablica;

Wówczas wywołanie procedury New postaci:

New (wskaznik);

spowoduje utworzenie zmiennej dynamicznej typu tablica, która
zajmie 600 bajtów pamięci. Do zmiennej tej w dalszej części
programu będzie można odwołać się za pomocą zmiennej
wskazywanej wskaznik^. Na przykład instrukcja:

wskaznik^[50]:=12.34;

spowoduje przypisanie podanej wartości pięćdziesiątemu
elementowi utworzonej tablicy.

2) Niech identyfikatory tablica i wskaznik będą określone jak w
poprzednim przykładzie. Wywołanie procedury:

GetMem (wskaznik, 400);

spowoduje również utworzenie zmiennej dynamicznej typu
tablica, ale przydzieli się jej tylko 400 bajtów pamięci.
Odwołanie np. wskaznik^[90] przekroczy ten rozmiar i błąd nie
będzie sygnalizowany (może to doprowadzić do nieprzewidzianych
konsekwencji). Wywołanie natomiast:

GetMem (wskaznik, 600);

jest równoważne z wywołaniem procedury New z poprzedniego
przykładu.

Do zwolnienia obszaru pamięci dynamicznej i tym samym
eliminacji odpowiedniej zmiennej dynamicznej służą procedury
Dispose, FreeMem i Release o wywołaniach odpowiednio:

Dispose (zmienna-wskaźnikowa)

lub

Dispose (zmienna-wskaźnikowa, destruktor)

oraz

FreeMem (zmienna-wskaźnikowa, rozmiar)

i

Release (zmienna-wskaźnikowa)

Procedura Dispose zwalnia obszar pamięci dynamicznej
zajmowany przez zmienną wskazywaną zmienna-wskaźnikowa^ , tj.
zmienną, na którą wskazuje wyspecyfikowana zmienna wskaźnikowa.
Wymagane jest przy tym, aby eliminowana zmienna dynamiczna była
uprzednio utworzona za pomocą wywołania procedury New. Drugą
postać wywołania procedury Dispose stosuje się do zwalniania
pamięci zajmowanej przez obiekt dynamiczny (zob. p. 15.6).

Procedura FreeMem powoduje zwrócenie do stosu przeznaczonego
na zmienne dynamiczne obszaru pamięci wskazywanego
wyspecyfikowaną zmienną wskaźnikową i zajmującego liczbę bajtów
określoną drugim argumentem (typu Word). Wymagane jest przy tym,
aby rozmiar był taki sam, jak w wywołaniu procedury GetMem
tworzącej daną zmienną dynamiczną.

Trzecia z powyższych procedur (Release) powoduje usunięcie
ze stosu zmiennej dynamicznej wskazywanej podaną zmienną
wskaźnikową i wszystkich zmiennych następujących po niej (zob.
rys. 74).

Przykłady 14.7

1) Niech zmienna wskaźnikowa wskaznik wskazuje na zmienną
dynamiczną, którą symbolicznie oznaczymy zmienna-3. Po
wywołaniu

Dispose (wskaznik);

postać stosu zmiennych dynamicznych będzie taka, jak
przedstawiono na rys. 177 b), a po wywołaniu

Release (wskaznik);

jak na rys. 74 c).

2) W poniższym programie do przydziału i zwolnienia pamięci dla
zmiennych dynamicznych zastosowano procedury standardowe
GetMem i FreeMem oraz New i Dispose.

program AM59;
type wskaznik = ^kwadraty;
kwadraty = array [1..100] of Integer;
var i : Byte;
tab_1, tab_2 : wskaznik;
komunikat : ^string;
begin
GetMem (tab_1, 10);
GetMem (tab_2, 20);
New (komunikat);
komunikat^:='Początek programu.';
Writeln (komunikat^);
komunikat^:='To jest ostatni komunikat programu.';
Writeln ('Rozmiar tablicy tab_1 = ', SizeOf(tab_1^));
Writeln ('Rozmiar tablicy tab_2 = ', SizeOf(tab_2^));
for i:=1 to 20 do
tab_1^[i]:=i+i;
for i:=1 to 20 do
tab_2^[i]:=i*i;
for i:=1 to 15 do
Writeln (i:2, ' ', tab_1^[i]:2);
Writeln (komunikat^);
Dispose (komunikat);
FreeMem (tab_1, 10);
FreeMem (tab_2, 20)
end.

Opis funkcji SizeOf znajduje się w p. 14.4.11. Wykonanie
programu powoduje wyświetlenie na ekranie następujących
napisów (zawartość ostatnich trzech wierszy może być różna):

Poczatek programu.
Rozmiar tablicy tab_1 = 200
Rozmiar tablicy tab_2 = 200
1 2
2 4
3 6
4 8
5 10
6 12
7 14
8 16
9 1
10 4
11 9
12 16
13 25
14 36
15 49
!Di komunikat programu.VWv LXFv%h Yh YVj
h Ył uhć3h% Y ^j & wjt h- Y ^j & j\ h/p Y t t
G

Wystąpienie śmieci w trzech ostatnich wierszach jest
spowodowane błędnym przydziałem pamięci w procedurach GetMem.
Pierwsze wywołanie tej procedury przydziela 10 bajtów pamięci
tablicy tab_1, a drugie 20 bajtów tablicy tab_2. Ponieważ
każda liczba całkowita typu Integer zajmuje dwa bajty pamięci,
tablica tab_1 może pomieścić 5, a tablica tab_2 10 liczb
tego typu. Powoduje to, że w pętli przypisującej wartości
tablicy tab_1 tylko pierwszych pięć elementów jest prawidłowo
umieszczanych w stosie, a pozostałe wypełniają stos w obszarze
przeznaczonym dla tablicy tab_2. Występujące następnie w pro-
gramie przypisania wartości tablicy tab_2 powodują prawidłowe
umieszczenie w odpowiednim obszarze stosu tylko dziesięciu
pierwszych jej elementów (pozostałe są zapisywane w obszarze
przeznaczonym na komunikat). Kompilator nie generuje błędu,
gdyż z deklaracji wynika, że obie tablice składają ze 100
liczb całkowitych (zajmują po 200 bajtów).

Przykład ten pokazuje, że niewłaściwe stosowanie procedur
GetMem i FreeMem może prowadzić do niesygnalizowanych błędów.

Wywołanie procedury Mark postaci:

Mark (zmienna-wskaźnikowa)

powoduje przypisanie wyspecyfikowanej zmiennej wskaźnikowej
bieżącej wartości wskaźnika stosu przeznaczonego na zmienne
dynamiczne, tj. adresu jego szczytu (pamiętanym w literale
zmiennym HeapPtr zob. p. 14.4.1).

Funkcje standardowe MaxAvail i MemAvail, których wywołanie
odbywa się poprzez same nazwy (są to funkcje bezparametrowe),
podają w bajtach rozmiar największego wolnego bloku (MaxAvail)
i sumę rozmiarów wszystkich wolnych bloków (MemAvail) w segmencie
przeznaczonym na zmienne dynamiczne. Obie wartości są typu
LongInt. Minimalny i maksymalny rozmiar tego stosu może być
określony za pomocą polecenia Memory sizes opcji Options (zob.
p. 3.9.2) lub za pomocą dyrektywy kompilatora M (zob. p. 6.3.2).

Przykłady 14.8

1) W podanym programie najpierw przydzielono pamięć wszystkim
(dynamicznym) elementom tablicy lista_num, a następnie
zwolniono pamięć zajmowaną przez element trzeci, szósty i
dziewiąty tej tablicy. Ponieważ każdy element tablicy
lista_num jest 20-elementową tablicą dynamiczną liczb typu
Real, a pojedyncza liczba tego typu zajmuje 6 bajtów pamięci,
więc do jego zapamiętania potrzeba 20 ś 6 = 120 bajtów
pamięci.

program AM60;
type tablica = array [1..20] of Real;
var i : Integer;
lista_num : array [1..10] of ^tablica;
begin
Writeln ('MemAvail = ', MemAvail, ' MaxAvail = ',
MaxAvail);
for i:=1 to 10 do
begin
New (lista_num[i]);
Writeln ('W stosie przydzielono ',
SizeOf(lista_num[i]^), ' bajtów')
end;
Writeln ('MemAvail = ', MemAvail, ' MaxAvail = ',
MaxAvail);
for i:=1 to 10 do
if (i mod 3)=0
then begin
Dispose (lista_num[i]);
Writeln ('W stosie zwolniono ',
SizeOf(lista_num[i]^), ' bajtów')
end;
Writeln ('MemAvail = ', MemAvail, ' MaxAvail = ',
MaxAvail)
end.

Wartością funkcji SizeOf jest rozmiar podanego argumentu (zob.
p. 14.4.11). Wykonanie programu AM60 spowoduje wyświetlenie
napisów podobnych do następujących (w zależności od bieżącego
rozmiaru stosu wartości początkowe mogą się różnić):

MemAvail = 494560 MaxAvail = 494560
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
W stosie przydzielono 120 bajtów
MemAvail = 493360 MaxAvail = 493360
W stosie zwolniono 120 bajtów
W stosie zwolniono 120 bajtów
W stosie zwolniono 120 bajtów
MemAvail = 493720 MaxAvail = 493360

Zauważmy, że po zwolnieniu pamięci zajmowanej przez niektóre
elementy tablicy tab_num maksymalny dostępny obszar stosu nie
zwiększył się. Jest to spowodowane faktem, że zwolniono
obszary wewnątrz zajętej części stosu, a nie na jego szczycie.

2) [37] program AM61;
type FriendRec = record
Name : string [30];
Age : Byte
end;
var p : Pointer;
recsize : Word;
begin
recsize:=SizeOf(FriendRec);
if MaxAvail then Writeln ('Za mało pamięci')
else begin
GetMem (p, SizeOf(FriendRec));
...
end
end.

W programie tym funkcję MaxAvail zastosowano do zbadania, czy
w stosie (dokładniej: na jego wierzchołku) jest wystarczająco
dużo miejsca do przydzielenia pamięci rekordowi FriendRec
(adres rekordu dynamicznego jest przypisywany zmiennej p, a
jego rozmiar jest ustalany za pomocą wywołania funkcji SizeOf
zob. p. 14.4.11).

Jak już wspomnieliśmy, identyfikator New oznacza także
funkcję standardową, której wywołanie ma postać:

New (typ-wskaźnikowy)

lub

New (typ-wskaźnikowy, konstruktor)

W przypadku drugiego wywołania podany typ wskaźnikowy musi
wskazywać na typ obiektowy, a konstruktor musi być wywołaniem
konstruktora tego typu obiektowego (zob. rozdział 15). Wartością
funkcji New jest wartość zmiennej dynamicznej wyspecyfikowanego
typu.

Tworzenie i przetwarzanie dynamicznych struktur danych


Procedury służące do dynamicznego przydzielania
i zwalniania pamięci, zmienne typów wskaźnikowych (zob. p. 8.5)
i zmienne wskazywane (zob. p. 9.5) są wykorzystywane przede
wszystkim do programowania tzw. dynamicznych struktur danych, tj.
prostych i złożonych struktur danych, którym pamięć jest przy-
dzielana i zwalniana w trakcie wykonywania programu. Takie
złożone struktury danych, zwane też strukturami listowymi, są
uporządkowanymi zbiorami składników, niekoniecznie o jednakowych
typach. Poszczególne składniki mogą być elementami prostymi (np.
liczbami i pojedynczymi znakami) lub elementami złożonymi (np.
tablicami, rekordami, obiektami, a nawet listami).

Ze względu na organizację oraz sposoby dołączania, wstawiania
i usuwania składników, wśród struktur listowych można wyróżnić
m.in.:

 stosy, w których wstawianie, usuwanie i dostęp są możliwe
tylko w jednym końcu zwanym wierzchołkiem stosu,
 kolejki, w których można dołączyć składniki tylko w jednym
końcu, a usunąć tylko w drugim końcu,
 listy (liniowe), które charakteryzują się tym, że dla każdego
składnika (poza pierwszym i ostatnim) jest określony jeden
składnik poprzedni i jeden składnik następny lub tylko skład-
nik poprzedni lub następny, przy czym w dowolnym miejscu
takiej struktury można dołączyć nowy składnik lub usunąć
składnik istniejący,
 drzewa, w których dla każdego składnika (poza pierwszym) jest
określony jeden składnik poprzedni i dla każdego składnika
(poza ostatnimi w strukturze) jest określonych n (n 2)
składników następnych (poza ostatnimi),
 grafy, które definiowane są przez dwa zbiory: zbiór
wierzchołków i zbiór krawędzi, określający powiązania
pomiędzy poszczególnymi wierzchołkami.

W niniejszym punkcie opisano pokrótce tworzenie i
przetwarzanie w języku Turbo Pascal podanych wyżej struktur
listowych (z wyjątkiem grafów). Z punktu widzenia tworzenia i
przetwarzania tych struktur, tj. dołączania, usuwania i dostępu
do składników, nie jest ważne, jakiego typu danymi są
poszczególne składniki. Dlatego też skoncentrujemy naszą uwagę
na prawidłowym ustalaniu powiązań pomiędzy składnikami, nie
wdając się specjalnie w rozważania dotyczące ich struktury.

Stosy


Stos (ang. stack) jest to struktura danych
składająca się z liniowo uporządkowanych zbiorów
składników (elementów), z których tylko największy jest w danej
chwili dostępny. Miejsce dostępu nazywa się wierzchołkiem stosu.
Jest to jedyne miejsce, do którego można dołączyć lub z którego
można usuwać elementy. Schemat organizacji stosu jest
przedstawiony na rys. 75.


Jak widać na powyższym rysunku, każdy składnik stosu posiada
wyróżniony element (wskaźnik), który wskazuje składnik
następujący po nim (dokładniej: adres tego składnika). Wskaźnik
ostatniego składnika stosu wskazuje na adres pusty (nil). Dane
są tu umowną nazwą pewnych struktur.

W celu utworzenia stosu, a później jego przetwarzania,
praktycznie jest zdefiniować następujące typy:

type wskaznik_stosu = ^skladnik_stosu;
skladnik_stosu = record
dane : typ-danych;
wskaznik : wskaznik_stosu
end;

gdzie typ danych oznacza pewien typ standardowy lub zdefiniowany
przez programistę. W dalszym ciągu założymy, że wszystkie dane
są tego samego typu (w ogólności typ danych może być różny dla
różnych składników). Zdefiniowany wyżej typ wskaźnikowy
wskaznik_stosu jest związany ze zbiorem wskazań danych typu
skladnik_stosu. Zatem zmienne typu wskaznik_stosu będą określały
adresy pamięci danych typu skladnik_stosu. W praktycznych
zastosowaniach stosów często zamiast typu rekordowego stosuje się
typ obiektowy (zob. rozdział 15).

Poniżej podajemy przykładowe procedury do utworzenia stosu
i dołączania do niego składników oraz do usuwania składników ze
stosu, a także program wykorzystujący te procedury.

Przykłady 14.9

1) Procedura tworzenia stosu i dołączania do niego składników:

procedure NaStos (var element : typ-danych;
var wierzcholek : wskaznik_stosu);
var punkt : wskaznik_stosu;
begin
punkt:=wierzcholek;
New (wierzcholek);
with wierzcholek^ do
begin
dane:=element;
wskaznik:=punkt
end
end;

Wywołanie procedury NaStos w chwili tworzenia stosu, tj.
zapisywania jego pierwszego składnika, wymaga, aby drugi
argument wywołania (odpowiadający parametrowi wierzcholek)
reprezentował adres pusty (nil). Pierwsza instrukcja
przypisania, występująca w treści procedury, powoduje
zapamiętanie pod zmienną punkt adresu aktualnego wierzchołka
stosu. Następnie, za pomocą wywołania procedury New, jest
tworzona zmienna dynamiczna o adresie podstawianym pod zmienną
wierzchołek. Mówiąc dokładniej: w segmencie pamięci
przeznaczonym na zmienne dynamiczne zostanie przydzielony blok
pamięci o rozmiarze równym rozmiarowi typu, z którym związana
jest zmienna wierzcholek, a adres początku tego bloku zostanie
przypisany tej zmiennej. Ostatnie dwie instrukcje przypisania
powodują zapamiętanie w stosie wprowadzanego elementu oraz
zapamiętanie dla danego składnika adresu składnika następnego
w stosie, tzn. tego, który w chwili wywołania procedury
znajdował się na jego wierzchołku.

2) Procedura usuwania (zdejmowania) składnika z wierzchołka
stosu:

procedure ZeStosu (var element : typ-danych;
var wierzcholek : wskaznik_stosu);
var punkt : wskaznik_stosu;
begin
if wierzcholek<>nil
then begin
with wierzcholek^ do
begin
element:=dane;
punkt:=wskaznik
end;
Dispose (wierzcholek);
wierzcholek:=punkt
end
end;

Wywołanie procedury ZeStosu powoduje usunięcie składnika stosu
znajdującego się na wierzchołku z przypisaniem jego wartości
pierwszemu argumentowi wywołania, a następnie zwolnienie
obszaru pamięci zajmowanego przez ten składnik (za pomocą
procedury Dispose). W ostatniej instrukcji przypisania
zmiennej wskaźnikowej wierzcholek przypisuje się adres
początku następnego składnika stosu, dzięki czemu, po
wykonaniu procedury, zmienna ta zawiera bieżący adres
wierzchołka stosu.

3) Poniższy program tworzy z tekstów (łańcuchów) wprowadzanych
kolejno z klawiatury stos, zdejmuje (usuwa) ze stosu podaną
liczbę składników, po czym odczytuje pozostałe teksty ze
stosu i wyświetla je na ekranie. Czynność usuwania składników
ze stosu może być powtórzona. W programie są wykorzystywane
procedury podane w przykładach 1) i 2) oraz pewne procedury
zdefiniowane w module Crt (zob. p. 14.5).

program AM62;
uses Crt;
type wskaznik_stosu = ^skladnik_stosu;
skladnik_stosu = record
dane : string [70];
wskaznik : wskaznik_stosu
end;
var wierzcholek, element : wskaznik_stosu;
tekst : string;
koniec : Boolean;
i, k, n : Integer;
{$I STOS.PAS} { Zbiór STOS.PAS zawiera procedury NaStos
i ZeStosu.
Pierwszy parametr w obu procedurach jest
typu string }
begin
ClrScr;
TextColor (Yellow);
TextBackground (Blue);
GotoXY (32, 1);
Writeln ('PRZYKŁAD STOSU');
Window (1, 3, 80, 25);
TextBackground (Black);
Write ('Wprowadź teksty (każdy max. 70 znaków; ');
Writeln ('** koniec wprowadzania)');
wierzcholek:=nil;
i:=0;
koniec:=False;
repeat
i:=i+1;
Writeln ('Tekst ', i, ' :');
Readln (tekst);
if tekst='**'
then koniec:=True
else NaStos (tekst, wierzcholek)
until koniec;
if i>1
then begin
ClrScr;
Writeln ('Stos został utworzony.');
i:=i1;
Writeln ('Liczba składników stosu : ', i);
koniec:=False;
repeat
Write ('Podaj liczbę n tekstów do usunięcia ');
Write ('ze stosu (n<1 koniec) : ');
Readln (n);
if n<1
then koniec:=True
else if n>i
then Writeln ('Liczba składników stosu
: ', i)
else begin
k:=0;
repeat
k:=k+1;
ZeStosu (tekst, wierzcholek)
until (wierzcholek=nil) or (k=n);
Writeln ('Teksty pozostałe w stosie
:');
if wierzcholek=nil
then begin
Writeln ('Brak tekstów');
koniec:=True
end
else begin
i:=0;
element:=wierzcholek;
repeat
i:=i+1;
Writeln ('Tekst ', i, ' :');
Writeln (element^.dane);
element:=element^.wskaznik
until element=nil
end
end
until koniec;
for k:=1 to i do
ZeStosu (tekst, wierzcholek);
Writeln ('Koniec programu.');
Delay (2000)
end
end.

Kolejki


Kolejka (ang. queue) jest strukturą danych
składającą się z liniowo uporządkowanych zbiorów
składników, do której można dołączyć składnik tylko w jednym
końcu (na końcu kolejki), a usunąć tylko w drugim końcu (na
początku kolejki).
poczatek ż ż
kolejki ł  ł 
ł ł
dane ł dane ł dane
wyjście ł ł
wskaźnik Ł wskaźnik Ł wskaźnik ż
ź ź ź ł
skladnik 1 skladnik 2 skladnik 3 ł
ł
Ł
ł ż ż koniec
 ł  ł  kolejki
ł ł
dane ł dane ł dane
ł ł
wejście
wskaźnik  Ł wskaźnik Ł wskaźnik  nil
ź ź ź
skladnik 4 skladnik n-1 skladnik n

Rys. 76. Organizacja kolejki


Powiązanie pomiędzy składnikami kolejki (zob. rys. 76) jest
takie samo, jak pomiędzy składnikami stosu. Usunięcie składnika
z początku kolejki odbywa się w taki sam sposób, jak usunięcie
składnika z wierzchołka stosu. Natomiast w celu dołączenia nowego
składnika na końcu kolejki należy zmienić wskaźnik ostatniego
składnika, tak aby wskazywał na nowy składnik, a wskaźnikowi
dołączanego elementu przypisać wskazanie puste (adres pusty).

W tworzeniu i przetwarzaniu kolejek praktyczne jest
posługiwanie się następującymi typami (są to typy analogiczne do
typów zdefiniowanych dla stosu zob. p. 14.4.4.1):

type wskaznik_kolejki = ^skladnik_kolejki;
skladnik_kolejki = record
dane : typ-danych;
wskaznik : wskaznik_kolejki
end;

przy czym typ danych oznacza, podobnie jak poprzednio, dowolny
typ (standardowy lub zdefiniowany przez programistę). W
zależności od zastosowania kolejek, zamiast typu record można
posłużyć się typem object (zob. rozdział 15).

Poniżej podajemy przykład procedury do tworzenia kolejki i
dołączania do niej nowych elementów, przykład procedury do
usuwania elementów z kolejki (poza użytymi nazwami nie różni się
ona od procedury podanej w przykładzie 14.8 p. 2) oraz program
wykorzystujący te procedury.

Przykłady 14.10

1) Procedura tworzenia kolejki i dołączania na jej końcu nowych
składników:

procedure DoKolejki (var element : typ-danych;
var koniec_kolejki : wskaznik_kolejki);
var punkt : wskaznik_kolejki;
begin
punkt:=koniec_kolejki;
New (koniec_kolejki);
with koniec_kolejki^ do
begin
dane:=element;
wskaznik:=nil
end;
if punkt<>nil
then punkt^.wskaznik:=koniec_kolejki
end;

Wywołanie procedury DoKolejki w chwili tworzenia kolejki, tj.
zapisywania jej pierwszego składnika, wymaga, aby drugi
argument wywołania (odpowiadający parametrowi koniec_kolejki)
reprezentował adres pusty (nil). Wykonanie instrukcji
przypisania

punkt:=koniec_kolejki;

powoduje zapamiętanie pod zmienną punkt adresu aktualnego
końca kolejki. Następnie, za pomocą procedury New, jest
tworzona nowa zmienna dynamiczna, której adres zostanie
podstawiony pod zmienną koniec_kolejki. Ponieważ jest to
ostatni element kolejki, więc zmienna koniec_kolejki^.wskaznik
wskazuje na adres pusty (nil). Element, który był ostatnim w
kolejce przed wywołaniem procedury musi wskazywać na aktualnie
ostatni element. Stąd też konieczna jest ostatnia instrukcja
przypisania (jeśli do kolejki nie wprowadza się pierwszego
elementu).

2) Procedura usuwania składnika z początku kolejki:

procedure ZKolejki (var element : typ-danych;
var poczatek_kolejki : wskaznik_kolejki);
var punkt : wskaznik_kolejki;
begin
if poczatek_kolejki<>nil
then begin
with poczatek_kolejki^ do
begin
element:=dane;
punkt:=wskaznik
end;
Dispose (poczatek_kolejki);
poczatek_kolejki:=punkt
end
end;

3) Poniższy program tworzy z tekstów (łańcuchów) wprowadzanych
kolejno z klawiatury kolejkę, po czym usuwa określoną liczbę
tekstów z kolejki i wyświetla pozostałe na ekranie. Usuwanie
składników kolejki można powtórzyć. Wykorzystywane są tu
procedury podane w przykładach 1) i 2) oraz procedury modułu
Crt (zob. p. 14.5.2).

program AM63;
uses Crt;
type wskaznik_kolejki = ^skladnik_kolejki;
skladnik_kolejki = record
dane : string [70];
wskaznik : wskaznik_kolejki
end;
var element, poczatek_kolejki, koniec_kolejki :
wskaznik_kolejki;
tekst : string;
koniec : Boolean;
i, k, n : Integer;
{$I KOLEJKA.PAS} { Zbiór KOLEJKA.PAS zawiera procedury
DoKolejki i ZKolejki. Pierwszy
parametr w obu
procedurach powinien być typu string.
}
begin
ClrScr;
TextColor (Yellow);
TextBackground (Blue);
GotoXY (31, 1);
Writeln ('PRZYKŁAD KOLEJKI');
Window (1, 3, 80, 25);
TextBackground (Black);
Write ('Wprowadź teksty (każdy max. 70 znaków; ');
Writeln ('** koniec wprowadzania)');
koniec_kolejki:=nil;
i:=0;
koniec:=False;
repeat
i:=i+1;
Writeln ('Tekst ', i, ' :');
Readln (tekst);
if tekst='**'
then koniec:=True
else begin
DoKolejki (tekst, koniec_kolejki);
if i=1
then poczatek_kolejki:=koniec_kolejki
end
until koniec;
if i>1
then begin
ClrScr;
Writeln ('Kolejka została utworzona.');
i:=i1;
Writeln ('Liczba składników kolejki : ', i);
koniec:=False;
repeat
Write ('Podaj liczbę n tekstów do usunięcia ');
Write ('z kolejki (n<1 koniec) : ');
Readln (n);
if n<1
then koniec:=True
else if n>i
then Writeln ('Liczba składników
kolejki : ', i)
else begin
k:=0;
repeat
k:=k+1;
ZKolejki (tekst,
poczatek_kolejki)
until (poczatek_kolejki=nil) or
(k=n);
Writeln ('Teksty pozostałe w
kolejce:');
if poczatek_kolejki=nil
then begin
Writeln ('Brak tekstów');
koniec:=True
end
else begin
i:=0;
element:=poczatek_kolejki;
repeat
i:=i+1;
Writeln ('Tekst ', i, '
:');
Writeln (element^.dane);

element:=element^.wskaznik
until element=nil
end
end
until koniec;
for k:=1 to i do
ZKolejki (tekst, poczatek_kolejki);
Writeln ('Koniec programu.');
Delay (2000)
end
end.

Listy


Listą (liniową) nazywamy liniowo
uporządkowany zbiór składników, z którego w
dowolnym miejscu można usunąć składnik, jak również dołączyć nowy
składnik. W zależności od powiązań pomiędzy składnikami wyróżnia-
my:

 listy jednokierunkowe,
 listy dwukierunkowe,
 listy cykliczne.

Organizacja listy jednokierunkowej podobna jest do
organizacji stosu i kolejki, tzn. dla każdego składnika (poza
ostatnim) jest określony następny (zob. rys. 77) lub dla każdego
składnika (poza pierwszym) jest określony składnik poprzedni
(zob. rys. 78).


poczatek ż ż
listy ł  ł 
ł ł
dane ł dane ł dane
ł ł
wskaźnik Ł wskaźnik Ł wskaźnik ż
ź ź ź ł
skladnik 1 skladnik 2 skladnik 3 ł
ł
Ł
ł ż ż koniec
 ł  ł  listy
ł ł
dane ł dane ł dane
ł ł
wskaźnik  Ł wskaźnik Ł wskaźnik  nil
ź ź ź
skladnik 4 skladnik n-1 skladnik n

Rys. 77. Organizacja listy jednokierunkowej o kierunku do
przodu


poczatek ż ż ż
listy  ł  ł  ł
ł ł ł
dane ł dane ł dane ł
ł ł ł
nil  wskaźnik Ą wskaźnik Ą wskaźnik ł
ź ź ź ł
skladnik 1 skladnik 2 skladnik 3 ł
ł
Ł
ł ż ż koniec
ł  ł  ł listy
ł ł ł
ł dane ł dane ł dane
ł ł ł
Ą wskaźnik Ą  wskaźnik Ą wskaźnik
ź ź ź
skladnik 4 skladnik n-1 skladnik n

Rys. 78. Organizacja listy jednokierunkowej o kierunku do tyłu


Do przetwarzania listy jednokierunkowej można wykorzystać
typy określone następująco:

type wskaznik_listy1 = ^skladnik_listy1
skladnik_listy1 = record
dane : typ-danych; wskaznik : wskaznik_listy1
end;

przy czym typ danych oznacza dowolny typ standardowy lub
zdefiniowany przez programistę.

Poniżej podajemy przykładowe procedury do tworzenia i
przetwarzania list jednokierunkowych o kierunku do przodu.
Napisanie analogicznych procedur dla list jednokierunkowych o
kierunku do tyłu pozostawiamy Czytelnikowi.

Przykłady 14.11

1) Procedura tworzenia listy jednokierunkowej i dołączania do
niej nowych składników:

procedure DoListy1 (var element : typ-danych;
var skladnik_biezacy : wskaznik_listy1);
var poprzedni_skladnik, nastepny_skladnik :
wskaznik_listy1;
begin
if skladnik_biezacy<>nil
then begin
poprzedni_skladnik:=skladnik_biezacy;
nastepny_skladnik:=skladnik_biezacy^.wskaznik
end
else begin
poprzedni_skladnik:=nil;
nastepny_skladnik:=nil
end;
New (skladnik_biezacy);
with skladnik_biezacy^ do
begin
dane:=element;
wskaznik:=nastepny_skladnik
end;
if poprzedni_skladnik<>nil
then poprzedni_skladnik^.wskaznik:=skladnik_biezacy
end;

Wywołanie procedury DoListy1 w momencie tworzenia listy, tj.
zapisywania jej pierwszego składnika, wymaga, aby drugi
argument wywołania (odpowiadający parametrowi skladnik_bie-
zacy) reprezentował adres pusty (nil). W pierwszej instrukcji
warunkowej sprawdza się, czy do listy dołącza się nowy
składnik, czy też zapisuje się jej pierwszy składnik. Jeśli do
listy dołącza się nowy składnik (adres tego elementu podaje
drugi argument wywołania, odpowiadający parametrowi
skladnik_biezacy), to pod zmiennymi poprzedni_skladnik i
nastepny_skladnik zapamiętuje się powiązania z dołączanym
składnikiem. W drugim przypadku zmiennym tym przypisuje się
adres pusty (nil). Następnie, za pomocą procedury New, jest
tworzona nowa zmienna dynamiczna, której adres zostanie pod-
stawiony pod zmienną skladnik_biezacy. Ustala się przy tym
powiązania rekordu skladnik_biezacy^ z następnym składnikiem
listy oraz wprowadza się do niego element (dokładniej: wartość
zmiennej element jest przypisywana do pola
skladnik_biezacy^.dane). Ostatnia instrukcja warunkowa służy
do ustalenia powiązania pomiędzy starymi składnikami listy i
nowym, dołączonym do niej składnikiem.

2) Procedura ustalania adresu k-tego składnika listy
jednokierunkowej:

procedure AdresSkladnikaListy1 (var k : Integer;
var pierwszy_skladnik,
skladnik_biezacy
: wskaznik_listy1);
var nastepny_skladnik : wskaznik_listy1;
i : Integer;
begin
if pierwszy_skladnik<>nil
then if k=1
then skladnik_biezacy:=pierwszy_skladnik
else if (k=2) and
(pierwszy_skladnik^.wskaznik=nil)
then k:=0
else begin
nastepny_skladnik:=pierwszy_skladnik;
i:=1;
repeat
i:=i+1;
if nastepny_skladnik^.wskaznik<>nil
then nastepny_skladnik:=
nastepny_skladnik^.wskaznik
until
(nastepny_skladnik^.wskaznik=nil) or (i=k);
if (nastepny_skladnik^.wskaznik=nil)
and (i then k:=0
else
skladnik_biezacy:=nastepny_skladnik
end
end;

Drugi argument wywołania musi wskazywać na adres pierwszego
elementu listy (jeśli wskazuje on na adres pusty, to wywołanie
procedury nie powoduje żadnego działania). Działanie procedury
jest następujące: Jeśli ma być określony adres pierwszego
składnika listy (tzn. k=1), to pod zmienną skladnik_biezacy
jest podstawiana wartość drugiego argumentu wywołania
procedury. W przeciwnym przypadku, poczynając od pierwszego
składnika (jeżeli nie jest on jedynym składnikiem listy), pod
zmienną nastepny_skladnik jest podstawiany adres pierwszego
składnika listy, a następnie sukcesywnie adresy kolejnych
składników, na które wskazuje bieżąca wartość zmiennej
nastepny_skladnik^.wskaznik. Podstawienia te są kontynuowane
aż do szukanego k-tego elementu listy lub do napotkania końca
listy. W pierwszym przypadku adres k-tego elementu listy jest
przypisywany zmiennej skladnik_biezacy (trzeciemu argumentowi
wywołania procedury), a w drugim zmiennej k jest
przypisywana wartość 0 (jeśli szukanym adresem nie jest adres
ostatniego składnika listy), co umożliwia wykonanie
odpowiednich czynności przez program wywołujący rozważaną
procedurę. Pod zmienną k jest podstawiana wartość 0 także w
przypadku, gdy lista zawiera tylko jeden składnik, a poszukuje
się adresu drugiego lub następnych jej składników.
3) Procedura usuwania składnika z listy jednokierunkowej:

procedure ZListy1 (var element : typ-danych;
var pierwszy_skladnik, skladnik_biezacy
: wskaznik_listy1);
var poprzedni_skladnik, nastepny_skladnik :
wskaznik_listy1;
begin
if (pierwszy_skladnik<>nil) and (skladnik_biezacy<>nil)
then if pierwszy_skladnik<>skladnik_biezacy
then begin
poprzedni_skladnik:=pierwszy_skladnik;

nastepny_skladnik:=poprzedni_skladnik^.wskaznik;
if nastepny_skladnik<>skladnik_biezacy
then repeat

poprzedni_skladnik:=nastepny_skladnik;

nastepny_skladnik:=poprzedni_skladnik^.wskaznik
until
nastepny_skladnik=skladnik_biezacy;
with skladnik_biezacy^ do
begin
element:=dane;
poprzedni_skladnik^.wskaznik:=wskaznik
end;
Dispose (skladnik_biezacy);
skladnik_biezacy:=poprzedni_skladnik
end
else begin
with pierwszy_skladnik^ do
begin
element:=dane;
pierwszy_skladnik:=wskaznik
end;
Dispose (skladnik_biezacy);
skladnik_biezacy:=pierwszy_skladnik
end
end;

Drugi argument wywołania powyższej procedury musi wskazywać na
adres pierwszego elementu listy. Usunięcie składnika listy (na
którego adres wskazuje skladnik_biezacy) będzie zachodzić
tylko w przypadku, gdy drugi i trzeci argument wywołania
procedury nie wskazują na adres pusty. Nastąpi wówczas zmiana
wskazania w składniku poprzednim w stosunku do usuwanego (pod
zmienną poprzedni_skladnik^.wskaznik zostanie podstawiony
adres następnego po usuwanym składnika listy) i usunięcie
składnika (za pomocą procedury Dispose). Jeśli usuniętym
składnikiem nie był pierwszy składnik listy, to zmiennej
wskaźnikowej skladnik_biezacy przypisywany jest adres
poprzedniego składnika (w stosunku do składnika usuniętego),
a w przeciwnym przypadku adres aktualnie pierwszego
składnika listy.

4) Poniższy program tworzy listę jednokierunkową z tekstów
(łańcuchów) wprowadzanych kolejno z klawiatury, usuwa z niej
tekst o podanym numerze i wyświetla pozostałe w liście
teksty na ekranie. Czynność usunięcia tekstu może być
powtarzana aż do usunięcia wszystkich tekstów z listy.
Program wykorzystuje procedury podane w przykładach 1), 2)
i 3) oraz procedury modułu Crt (zob. p. 14.5.2).

program AM64;
uses Crt;
type wskaznik_listy1 = ^skladnik_listy1;
skladnik_listy1 = record
dane : string [70];
wskaznik : wskaznik_listy1
end;
var pierwszy_skladnik, skladnik_biezacy :
wskaznik_listy1;
tekst : string;
koniec : Boolean;
i, k : Integer;
{$I LISTA1.PAS} { Zbiór LISTA1.PAS zawiera
procedury DoListy1,
ZListy1 i AdresSkladnikaListy1. W
pierwszych dwóch
procedurach pierwszy parametr jest typu
string }
begin
ClrScr;
TextColor (Yellow);
TextBackground (Blue);
GotoXY (24,1);
Writeln ('PRZYKŁAD LISTY JEDNOKIERUNKOWEJ');
Window (1, 3, 80, 25);
TextBackground (Black);
Write ('Wprowadź teksty (każdy max. 70 znaków; ');
Writeln ('** koniec wprowadzania)');
skladnik_biezacy:=nil;
i:=0;
koniec:=False;
repeat
i:=i+1;
Writeln ('Tekst ', i, ' :');
Readln (tekst);
if tekst='**'
then koniec:=True
else begin
DoListy1 (tekst, skladnik_biezacy);
if i=1
then pierwszy_skladnik:=skladnik_biezacy
end
until koniec;
if i>1
then begin
ClrScr;
Writeln ('Lista została utworzona.');
i:=i1;
Writeln ('Liczba składników listy : ', i);
koniec:=False;
repeat
Write ('Podaj numer k tekstu do usunięcia ');
Write ('z listy (k<1 koniec) : ');
Readln (k);
if k<1
then koniec:=True
else begin
AdresSkladnikaListy1 (k,
pierwszy_skladnik,
skladnik_biezacy);
if k=0
then Writeln ('Największy numer
tekstu : ', i)
else begin
ZListy1 (tekst,
pierwszy_skladnik,
skladnik_biezacy);
i:=i1;
Writeln ('Teksty pozostałe w
liście :');
if skladnik_biezacy=nil
then begin
Writeln ('Brak tekstów');
koniec:=True
end
else for k:=1 to i do
begin
AdresSkladnikaListy1
(k,
pierwszy_skladnik,
skladnik_biezacy);
Writeln ('Tekst ', k,
' :');
Writeln
(skladnik_biezacy^.dane)
end
end
end
until koniec;
for k:=1 to i do
begin
AdresSkladnikaListy1 (k, pierwszy_skladnik,
skladnik_biezacy);
ZListy1 (tekst, pierwszy_skladnik,
skladnik_biezacy)
end;
Writeln ('Koniec programu.');
Delay (2000)
end
end.

Listą dwukierunkową nazywamy liniowo uporządkowany zbiór
składników, w którym dla każdego składnika, poza pierwszym i
ostatnim, jest określony składnik poprzedni i następny. Dla
ostatniego składnika listy dwukierunkowej jest określony składnik
poprzedni, a dla pierwszego następny (zob. rys. 79).

Jak widać na rys. 79, każdy składnik listy posiada dwa
wskaźniki: wskaźnik-1, który wskazuje składnik poprzedni
(dokładniej: adres tego składnika), oraz wskaźnik-2, określający
składnik następny. W celu dołączenia do listy nowego składnika,
tak aby stał on się k-tym (k 1 i k n) składnikiem listy,
należy jego adres przypisać drugiemu wskaźnikowi k-tego składnika
i pierwszemu wskaźnikowi (k+1)-szego składnika listy, ustalając
jednocześnie odpowiednie wskazania w dołączanym składniku. W
przypadku dołączania nowego składnika na początku listy, jego
pierwszy wskaźnik powinien wskazywać na adres pusty (nil), a
drugi na pierwszy składnik listy. Podobnie należy ustalić
wskazania przy dołączaniu nowego składnika na końcu listy:
pierwszy wskaźnik powinien wskazywać na ostatni składnik listy,
a drugi na adres pusty.

Usunięcie k-tego (k 1 i k n) składnika listy polega na
ustaleniu wskazania drugiego wskaźnika (k1)-szego składnika na
składnik (k+1)-szy i wskazania pierwszego wskaźnika (k+1)-szego
składnika na składnik (k1)-szy. Przy usuwaniu pierwszego
składnika listy należy pierwszemu wskaźnikowi drugiego składnika
przypisać adres pusty (nil), a przy usuwaniu ostatniego adres
pusty powinien zostać przypisany drugiemu wskaźnikowi (n1)-szego
składnika.



poczatek ż ż
ż
listy  ł  ł 
ł
ł ł
ł
nil  wskaźnik-1 Ą wskaźnik-1 Ą wskaźnik-1
ł

ł
dane dane dane
ł

ł
wskaźnik-2 ż wskaźnik-2 ż wskaźnik-2 ż
ł
ź ł ź ł ź ł
ł
ł  ł  ł
ł
ĄŁ ĄŁ ł
ł
skladnik 1 skladnik 2 skladnik 3 ł
ł
ł
ł
Ł
ł
ł Ł
ł ł ż ż
koniec
ł ł  ł  ł
listy
ł ł ł ł

ł Ą wskaźnik-1 Ą  wskaźnik-1 Ą wskaźnik-
1
ł

ł dane dane dane

ł

ł wskaźnik-2  ż wskaźnik-2 ż wskaźnik-
2  nil
ł ź ł ź ł
ź
ł  ł  ł 
ĄŁ ĄŁ ĄŁ
skladnik 4 skladnik n-1 skladnik
n

Rys. 79. Organizacja listy dwukierunkowej
Przy przetwarzaniu list dwukierunkowych jest wygodnie
posługiwać się typami zdefiniowanymi następująco:

type wskaznik_listy2 = ^skladnik_listy2;
skladnik_listy2 = record
wskaznik1 : wskaznik_listy2;
dane : typ-danych;
wskaznik2 : wskaznik_listy2
end;

gdzie typ danych oznacza dowolny typ standardowy lub zdefiniowany
przez programistę (typ record może być zastąpiony typem object
zob. rozdział 15).

Poniżej podajemy przykładowe procedury do przetwarzania list
dwukierunkowych. Sądzimy, że na podstawie programu AM64 z
przykładu 14.10 p. 4) napisanie programu wykorzystującego te
procedury nie sprawi Czytelnikowi kłopotu.

Przykłady 14.12

1) Procedura tworzenia listy dwukierunkowej i dołączania do
niej nowych składników:

procedure DoListy2 (var element :
typ-danych;
var skladnik_biezacy : wskaznik_listy2);
var poprzedni_skladnik, nastepny_skladnik :
wskaznik_listy2;
begin
if skladnik_biezacy<>nil
then begin
poprzedni_skladnik:=skladnik_biezacy;
nastepny_skladnik:=skladnik_biezacy^.wskaznik2
end
else begin
poprzedni_skladnik:=nil;
nastepny_skladnik:=nil
end;
New (skladnik_biezacy);
with skladnik_biezacy^ do
begin
wskaznik1:=poprzedni_skladnik;
dane:=element;
wskaznik2:=nastepny_skladnik
end;
if poprzedni_skladnik<>nil
then
poprzedni_skladnik^.wskaznik2:=skladnik_biezacy;
if nastepny_skladnik<>nil
then nastepny_skladnik^.wskaznik1:=skladnik_biezacy
end;

Wywołanie procedury DoListy2 w momencie tworzenia listy, tj.
zapisywania jej pierwszego składnika, wymaga, aby drugi
argument wywołania (odpowiadający parametrowi skladnik_bie-
zacy) reprezentował adres pusty (nil). W pierwszej instrukcji
warunkowej sprawdza się, czy do listy dołącza się nowy
składnik, czy też zapisuje się jej pierwszy składnik. Jeśli do
listy dołącza się nowy składnik (adres tego elementu podaje
drugi argument wywołania, odpowiadający parametrowi
skladnik_biezacy), to pod zmiennymi poprzedni_skladnik i na-
stepny_skladnik zapamiętuje się powiązania z dołączanym
składnikiem. W drugim przypadku zmiennym tym przypisuje się
adres pusty (nil). Następnie, za pomocą procedury New, jest
tworzona nowa zmienna dynamiczna, której adres zostanie
podstawiony pod zmienną skladnik_biezacy. Ustala się przy tym
powiązania rekordu skladnik_biezacy^ z poprzednim i następnym
składnikiem listy oraz wprowadza się do niego element
(dokładniej: wartość zmiennej element jest przypisywana do
pola skladnik_biezacy^.obiekt). Ostatnie dwie instrukcje
warunkowe służą do ustalenia powiązań pomiędzy starymi
składnikami listy i nowym, dołączonym do niej składnikiem.

2) Procedura ustalania adresu k-tego składnika listy
dwukierunkowej:

procedure AdresSkladnikaListy2 (var k :
Integer;
var skladnik_biezacy :
wskaznik_listy2);
var poprzedni_skladnik, nastepny_skladnik :
wskaznik_listy2;
i : Integer;
begin
if skladnik_biezacy<>nil
then if (skladnik_biezacy^.wskaznik1<>nil) or
(k<>1)
then begin
poprzedni_skladnik:=skladnik_biezacy;
if poprzedni_skladnik^.wskaznik1<>nil
then repeat
poprzedni_skladnik:=
poprzedni_skladnik^.wskaznik1
until
poprzedni_skladnik^.wskaznik1=nil;
if k=1
then
skladnik_biezacy:=poprzedni_skladnik
else if (k=2) and
(poprzedni_skladnik^.wskaznik2=nil)
then k:=0
else begin

nastepny_skladnik:=poprzedni_skladnik;
i:=1;
repeat
i:=i+1;
if
nastepny_skladnik^.wskaznik2
<>nil
then nastepny_skladnik:=

nastepny_skladnik^.wskaznik2
until
(nastepny_skladnik^.wskaznik2=nil)
or (i=k);
if
(nastepny_skladnik^.wskaznik2=nil)
and (i then k:=0 else
skladnik_biezacy:=nastepny_skladnik
end
end
end;

Drugi argument wywołania musi wskazywać na dowolny składnik
listy (jeśli wskazuje on na adres pusty, to wywołanie
procedury nie powoduje żadnego działania). Jeśli argument ten
wskazuje na pierwszy składnik listy i k=1, to adres jest już
ustalony i procedura nie zmienia wartości żadnego argumentu.
W przeciwnym przypadku za pomocą pierwszej instrukcji repeat
zostanie ustalony pierwszy składnik listy. Dalsza treść
procedury jest podobna do treści procedury
AdresSkladnikaListy1 z przykładu 14.11 p. 2).

3) Procedura usuwania składnika z listy dwukierunkowej:

procedure ZListy2 (var element : typ-danych;
var skladnik_biezacy : wskaznik_listy2);
var poprzedni_skladnik, nastepny_skladnik :
wskaznik_listy2;
begin
if skladnik_biezacy<>nil
then begin
with skladnik_biezacy^ do
begin
poprzedni_skladnik:=wskaznik1;
element:=dane;
nastepny_skladnik:=wskaznik2;
if wskaznik1<>nil
then
poprzedni_skladnik^.wskaznik2:=wskaznik2;
if wskaznik2<>nil
then
nastepny_skladnik^.wskaznik1:=wskaznik1
end;
Dispose (skladnik_biezacy);
if poprzedni_skladnik<>nil
then skladnik_biezacy:=poprzedni_skladnik
else skladnik_biezacy:=nastepny_skladnik
end
end;

Usunięcie składnika listy będzie mieć miejsce tylko w
przypadku, gdy parametr skladnik_biezacy nie wskazuje na adres
pusty. Nastąpi wówczas zapamiętanie wskazań na składniki
poprzedni i następny w stosunku do usuwanego (pod zmiennymi
poprzedni_skladnik i nastepny_skladnik), a także zmiana
wskazań w tych składnikach (jeżeli nie są to składniki
pierwszy i ostatni) i usunięcie składnika (za pomocą procedury
Dispose). Jeśli usuniętym składnikiem nie był pierwszy
składnik listy, to zmiennej wskaźnikowej skladnik_biezacy jest
przypisywany adres poprzedniego składnika (w stosunku do
składnika usuniętego), natomiast w przeciwnym przypadku
adres aktualnie pierwszego składnika listy.

Lista cykliczna powstaje z listy jedno- lub dwukierunkowej
przez powiązanie ostatniego składnika listy z jej pierwszym
składnikiem. W wyniku takiego powiązania wyróżnione składniki
(pierwszy i ostatni) przestają pełnić swoje funkcje. W liście
cyklicznej żaden składnik nie jest wyróżniony (zob. rys. 80).


ż ż ż
 ł  ł  ł
ł ł ł
wskaźnik-1 Ą wskaźnik-1 Ą wskaźnik-1 ł
ł ł
ł dane dane dane ł
ł ł
ł wskaźnik-2 ż wskaźnik-2 ż wskaźnik-2 ż ł
ł ź ł ź ł ź ł ł
ł  ł  ł  ł ł
ł Ł ĄŁ ĄŁ ł ł
ł ł ż Ł ł
ł ł  ł  ł
ł ł ł ł
ł Ą wskaźnik-2 Ą  wskaźnik-2 ł
ł ł
ł dane dane ł
ł ł
ł wskaźnik-1  ż wskaźnik-1 Ł
ł ź ł ź
ł  ł 
ĄŁ ĄŁ

Rys. 80. Organizacja listy cyklicznej


Tworzenie listy cyklicznej, dołączanie do niej nowych
składników oraz ich usuwanie jest podobne do operacji
wykonywanych dla listy jedno- lub dwukierunkowej. W celu ułatwie-
nia analizy składników listy cyklicznej, w każdym składniku
wyróżnia się pewną zmienną (pole) służącą do identyfikacji.
Identyfikatorem może być na przykład numer składnika liczony
względem umownego składnika pierwszego.

Do przetwarzania list cyklicznych zalecamy stosowanie typów
zdefiniowanych następująco:

type wskaznik_listy = ^skladnik_listy;
skladnik_listy = record
wskaznik1 : wskaznik_listy;
numer : Integer;
dane : typ-danych;
wskaznik2 : wskaznik_listy
end;

gdzie pole numer służy do identyfikacji składnika listy, a typ
danych oznacza, podobnie jak poprzednio, dowolny typ standardowy
lub typ zdefiniowany przez programistę. Zamiast typu rekordowego
można także stosować typ obiektowy (zob. rozdział 15).

W kolejnych przykładach podano procedury służące do
utworzenia listy cyklicznej i dodania do niej nowego składnika,
ustalenia adresu k-tego składnika względem umownego składnika
pierwszego oraz do usunięcia k-tego składnika.

Przykłady 14.13

1) Procedura tworzenia listy cyklicznej i dołączania do niej
nowych składników:

procedure DoListy (var element : typ-danych;
var skladnik_biezacy : wskaznik_listy;
var k : Integer);
var poprzedni_skladnik, nastepny_skladnik :
wskaznik_listy;
begin
if skladnik_biezacy<>nil
then begin
poprzedni_skladnik:=skladnik_biezacy;
nastepny_skladnik:=skladnik_biezacy^.wskaznik2
end
else begin
poprzedni_skladnik:=nil;
nastepny_skladnik:=nil
end;
New (skladnik_biezacy);
if (poprzedni_skladnik=nil) and (nastepny_skladnik=nil)
then begin
poprzedni_skladnik:=skladnik_biezacy;
nastepny_skladnik:=skladnik_biezacy;
poprzedni_skladnik^.numer:=0
end;
with skladnik_biezacy^ do
begin
wskaznik1:=poprzedni_skladnik;
numer:=poprzedni_skladnik^.numer+1;
k:=numer;
dane:=element;
wskaznik2:=nastepny_skladnik
end;
if k<>1
then begin
poprzedni_skladnik^.wskaznik2:=skladnik_biezacy;
nastepny_skladnik^.wskaznik1:=skladnik_biezacy
end
end;

Pierwsze wywołanie procedury DoListy (tworzenie listy
cyklicznej) wymaga, aby argument odpowiadający parametrowi
skladnik_biezacy reprezentował adres pusty (nil). Po sprawdze-
niu w pierwszej instrukcji warunkowej, czy do istniejącej
listy dołącza się nowy składnik, czy też zapisuje się jej
pierwszy składnik, za pomocą procedury New jest tworzona nowa
zmienna dynamiczna, której adres jest przypisywany zmiennej
skladnik_biezacy. Jeśli jest to pierwszy składnik listy
cyklicznej, to pola wskaznik1 i wskaznik2 zmiennej
skladnik_biezacy^ powinny wskazywać, podobnie jak zmienna
skladnik_biezacy, na ten składnik. Ponadto należy zabezpieczyć
przypisanie polu skladnik_biezacy^.numer wartości 1. Czynności
związane z organizacją tych przypisań są wykonywane w
instrukcji złożonej drugiej instrukcji warunkowej. W
instrukcji with następują przypisania odpowiednich wartości
polom zmiennej dynamicznej skladnik_biezacy^. Jeśli procedura
nie tworzy pierwszego składnika listy, to w ostatniej
instrukcji warunkowej ustala się powiązania pomiędzy starymi
składnikami listy i nowym, dołączonym do niej składnikiem.
Parametr k podaje na wyjściu numer kolejny dołączonego do
listy składnika.

2) Procedura ustalania adresu k-tego składnika listy cyklicznej
względem umownego składnika pierwszego:

procedure AdresSkladnikaListy (var k :
Integer;
var skladnik_biezacy :
wskaznik_listy);
var nastepny_skladnik : wskaznik_listy;
maxi : Integer;
begin
if (skladnik_biezacy<>nil) and
(skladnik_biezacy^.numer<>k)
then begin
nastepny_skladnik:=skladnik_biezacy;
repeat
maxi:=nastepny_skladnik^.numer;
nastepny_skladnik:=nastepny_skladnik^.wskaznik2
until nastepny_skladnik^.numer<=maxi;
if k>maxi
then k:=0
else begin
nastepny_skladnik:=skladnik_biezacy;
repeat

nastepny_skladnik:=nastepny_skladnik^.wskaznik2
until nastepny_skladnik^.numer=k;
skladnik_biezacy:=nastepny_skladnik
end
end
end;

Procedura jest napisana przy założeniu, że składniki listy
ponumerowane są kolejno od 1 i numery te są pamiętane dla
każdego składnika w jego polu o nazwie numer. Drugi argument
wywołania procedury powinien wskazywać na dowolny składnik
listy. Jeśli wskazuje on na adres pusty (nil) lub na k-ty
składnik, to wywołanie procedury nie powoduje wykonania żadnej
operacji.

Pierwsza instrukcja repeat powoduje ustalenie liczby
składników listy (liczba ta jest przypisywana pomocniczej
zmiennej maxi) i jeśli k maxi, to zmiennej skladnik_biezacy
jest przypisywany szukany adres.

3) Procedura usuwania składnika z listy cyklicznej:

procedure ZListy (var element : typ-danych;
var skladnik_biezacy : wskaznik_listy);
var poprzedni_skladnik, nastepny_skladnik :
wskaznik_listy;
k : Integer;
begin
if skladnik_biezacy<>nil
then begin
with skladnik_biezacy^ do
begin
poprzedni_skladnik:=wskaznik1;
element:=dane;
k:=numer;
nastepny_skladnik:=wskaznik2;
poprzedni_skladnik^.wskaznik2:=wskaznik2;
nastepny_skladnik^.wskaznik1:=wskaznik1
end;
Dispose (skladnik_biezacy);
if (poprzedni_skladnik=nastepny_skladnik)
and (k=nastepny_skladnik^.numer)
then skladnik_biezacy:=nil
else begin
skladnik_biezacy:=poprzedni_skladnik;
if nastepny_skladnik^.numer<>1
then repeat
nastepny_skladnik^.numer:=k;
k:=k+1;
nastepny_skladnik:=
nastepny_skladnik^.wskaznik2
until nastepny_skladnik^.numer=1
end
end
end;

Działanie powyższej procedury jest podobne do działania
procedury ZListy1 i ZListy2 z przykładów 14.11 p. 3) i 14.12
p. 3). Z uwagi na cykliczność listy w niniejszej procedurze po
usnięciu składnika z listy następuje przenumerowanie
następnych składników aż do umownego końca listy (dokładniej:
wartości pola numer następnych składników zmniejszane są o 1
aż do napotkania składnika, którego wspomniane pole zawiera
wartość 1). Jeśli jest usuwany pierwszy i jedyny składnik
listy, to zmiennej skladnik_biezacy jest przypisywany adres
pusty (nil).

Drzewa


W praktycznych zastosowaniach często mamy do
czynienia ze strukturami danych, których
poszczególne składniki są powiązane ze sobą bardziej
skomplikowanymi relacjami niż listy. Niektóre z tych struktur
dają się opisać za pomocą struktur drzewiastych.

Drzewem nazywamy strukturę danych o następujących
powiązaniach pomiędzy elementami składowymi:

 dla każdego składnika, z wyjątkiem pierwszego, istnieje
dokładnie jeden składnik poprzedni (poprzednik),
 każdy składnik posiada co najwyżej n (n2) składników
następnych (następników),
 pierwszy składnik (korzeń) nie posiada poprzednika,
 wszystkie składniki ostatnie (liście) nie mają następników.

Jeśli n=2, to drzewo nazywamy drzewem binarnym. Innymi słowy:
drzewo binarne jest to drzewo, w którym każdy składnik posiada
co najwyżej dwa następniki (zob. rys. 81). W przeciwnym
przypadku, tj. gdy n>2, drzewo nazywamy drzewem wielokierunkowym
(zob. rys. 82) rzędu n.



korzeń

dane

wskaźnik-1
ł
ł wskaźnik-2 ż
ł ź ł
  liść

dane dane


wskaźnik-1 wskaźnik-1

ł ł
ł wskaźnik-2 ż ł wskaźnik-2
ż
ł ź ł ł ź
ł
ł ł Ą nil nil
Ł
 

dane dane

wskaźnik-1 wskaźnik-1
ł ł
ł wskaźnik-2 ż ł wskaźnik-2 ż
ł ź ł ł ź ł
ł nil Ł ł ł
  

dane dane dane


wskaźnik-1 wskaźnik-1 wskaźnik-1

ł ł ł
ł wskaźnik-2 ż ł wskaźnik-2 ż ł wskaźnik-2
ż
ł ź ł ł ź ł ł ź
ł
ł ł Ą nil ł Ą nil
ł
 liść  liść  liść
 liść


dane dane dane
dane


wskaźnik-1 wskaźnik-1 wskaźnik-1
wskaźnik-1
ł ł ł ł

ł wskaźnik-2 ż ł wskaźnik-2 ż ł wskaźnik-2 ż ł
wskaźnik-2 ż
ł ź ł ł ź ł ł ź ł ł
ź ł
Ą nil nil Ł Ą nil nil Ł Ą nil nil Ł Ą nil
nil Ł

Rys. 81. Przykład organizacji drzewa binarnego
Każdą strukturę dającą się przedstawić drzewem
wielokierunkowym można także przedstawić w postaci równoważnego
drzewa binarnego. Przekształcenie drzewa wielokierunkowego w
drzewo binarne zachowuje poszczególne składniki, choć zmieniają
się powiązania pomiędzy nimi i semantyka tych powiązań. Na rys.
83 przedstawiono drzewo binarne równoważne drzewu
wielokierunkowemu z rys. 82.




korzeń
A
dane

wskaźnik-1
ł
ł wskaźnik-2
ł ł
ł ł wskaźnik-3 ż
ł łź ł
ł Ąż ł
 liść  
B C D
dane dane dane

wskaźnik-1 wskaźnik-1 wskaźnik-1
ł ł ł
ł wskaźnik-2 ł wskaźnik-2 ł wskaźnik-2
łł łł łł
łł wskaźnik-3 ż łł wskaźnik-3 ż łł wskaźnik-3 ż
łłźł łłźł łłź ł
łĄ nil nil Ł łĄ nil nil Ł łĄ nil ł
Ą nil ł Ą nil ł
Ąż ł
 
E
F
dane dane



wskaźnik-1
wskaźnik-1
ł ł

ł wskaźnik-2 ł
wskaźnik-2
ł ł
łł
ł ł wskaźnik-3 ż łł
wskaźnik-3 ż
ł łź ł
łłźł
ł Ąż ł łĄ nil
nil Ł
ł ł ł Ąż
 liść  liść  liść 
liść
G H I
J
dane dane dane dane



wskaźnik-1 wskaźnik-1 wskaźnik-1
wskaźnik-1
ł ł ł ł

ł wskaźnik-2 ł wskaźnik-2 ł wskaźnik-2 ł
wskaźnik-2
łł łł łł
łł
łł wskaźnik-3 ż łł wskaźnik-3 ż łł wskaźnik-3 ż łł
wskaźnik-3 ż
łłźł łłźł łłźł
łłźł
łĄ nil nil Ł łĄ nil nil Ł łĄ nil nil Ł łĄ nil
nil Ł
Ą nil Ą nil Ą nil Ą nil

Rys. 82. Przykład organizacji drzewa wielokierunkowego rzędu 3
(A, B, ..., J oznaczenia składników) korzeń
A
dane


wskaźnik-1

ł
ł wskaźnik-2
ż
ł ź
ł
ł nil
Ł

B
dane

wskaźnik-1
ł
ł wskaźnik-2 ż
ł ź ł
ł nil Ł

C
dane

wskaźnik-1
ł
ł wskaźnik-2 ż
ł ź ł
 
E D
dane dane

wskaźnik-1 wskaźnik-1
ł ł
ł wskaźnik-2 ż ł wskaźnik-2 ż
ł ź ł ł ź ł
ł nil Ł ł nil Ł
 
G F
dane dane

wskaźnik-1 wskaźnik-1
ł ł
ł wskaźnik-2 ż ł wskaźnik-2 ż
ł ź ł ł ź ł
ł nil Ł ł nil Ł
  liść
H J
dane dane

wskaźnik-1 wskaźnik-1
ł ł
ł wskaźnik-2 ż ł wskaźnik-2 ż
ł ź ł ł ź ł
ł nil Ł Ą nil nil Ł
 liść
I
dane

wskaźnik-1
ł
ł wskaźnik-2 ż
ł ź ł
Ą nil nil Ł

Rys. 83. Drzewo binarne równoważne drzewu wielokierunkowemu
z poprzedniego rysunku (zachowano oznaczenia
składników) Przekształcenie drzewa wielokierunkowego na drzewo binarne
prowadzi zawsze do efektywniejszego wykorzystania pamięci. Jednak
z drugiej strony średnia liczba odwołań, związana z poszukiwaniem
pewnego składnika w drzewie wielokierunkowym, jest zawsze mniej-
sza od średniej liczby analogicznych odwołań w przypadku drzewa
binarnego. Oznacza to, że z punktu widzenia czasu przetwarzania
posługiwanie się drzewami wielokierunkowymi jest efektywniejsze.

W przetwarzaniu drzew binarnych stosuje się zwykle
następujące typy:

type wskaznik_drzewa = ^skladnik_drzewa;
skladnik_drzewa = record
dane1 : string;
dane2 : typ-danych;
wskaznik1, wskaznik2 :
wskaznik_drzewa
end;

gdzie typ danych oznacza dowolny typ standardowy lub typ
zdefiniowany przez programistę, a za pomocą zawartości pola dane1
porządkuje się składniki drzewa (zwykle za pomocą relacji
mniejszości lub większości). Warto w tym miejscu zaznaczyć, że
dobrym narzędziem do opisu struktur drzewiastych są obiekty (zob.
rozdział 15), głównie z uwagi na posiadaną przez nie cechę
dziedziczności.

Przykłady zawierają procedury służące do utworzenia drzewa
binarnego, dołączania do niego nowego składnika, poszukiwania
wybranego składnika i usuwania całego drzewa z pamięci, a także
program wykorzystujący te procedury. Napisanie procedury
usuwającej wybrany składnik drzewa pozostawiamy jako zadanie dla
Czytelnika.

Przykłady 14.14

1) Procedura tworzenia drzewa binarnego i dołączania do niego
nowych składników:

procedure DoDrzewa (var element1 : string;
var element2 : typ-danych;
var korzen : wskaznik_drzewa;
var wymiana : Boolean);
var poprzedni_skladnik, skladnik_biezacy :
wskaznik_drzewa;
dodanie_skladnika : Boolean;
odp : Char;
procedure Podstawienie;
begin
with skladnik_biezacy^ do
begin
dane1:=element1;
dane2:=element2;
wskaznik1:=nil;
wskaznik2:=nil;
dodanie_skladnika:=True
end
end;
begin
if korzen=nil
then begin
New (korzen);
with korzen^ do
begin
dane1:=element1;
dane2:=element2;
wskaznik1:=nil;
wskaznik2:=nil
end;
end
else begin
skladnik_biezacy:=korzen;
dodanie_skladnika:=False;
while not dodanie_skladnika do
if element1 then if skladnik_biezacy^.wskaznik1=nil
then begin

poprzedni_skladnik:=skladnik_biezacy;
New (skladnik_biezacy);
poprzedni_skladnik^.wskaznik1:=
skladnik_biezacy;
Podstawienie
end
else
skladnik_biezacy:=skladnik_biezacy^.wskaznik1
else if element1>skladnik_biezacy^.dane1
then if
skladnik_biezacy^.wskaznik2=nil
then begin
poprzedni_skladnik:=
skladnik_biezacy;
New (skladnik_biezacy);

poprzedni_skladnik^.wskaznik2:=
skladnik_biezacy;
Podstawienie
end
else skladnik_biezacy:=
skladnik_biezacy^.wskaznik2
else begin
Writeln;
Write ('Drzewo już zawiera
podany ');
Writeln ('składnik.');
repeat
Write ('Wymienić? (t/n): ');
Readln (odp);
odp:=UpCase(odp)
until (odp='T') or (odp='N');
if odp='T'
then begin
skladnik_biezacy^.dane1:=
element1;
wymiana:=True
end;
dodanie_skladnika:=True
end
end
end;

Podczas pierwszego wywołania procedury DoDrzewa, tj. podczas
tworzenia drzewa binarnego, argument odpowiadający parametrowi
korzen powinien wskazywać na adres pusty. Nastąpi wówczas
utworzenie rekordowej zmiennej dynamicznej korzen^ i
przypisanie jej polom wartości podanych drugim i trzecim
argumentem wywołania, a ponadto polom wskazującym na następne
elementy drzewa zostanie przypisany adres pusty. Kolejne wywo-
łanie procedury (po utworzeniu korzenia drzewa) spowoduje
utworzenie liścia drzewa, przy czym o miejscu jego
doczepienia do struktury decyduje wartość pierwszego argumentu
wywołania procedury, będącego jednym z elementów liścia.
Relacją porządkującą jest tu relacja mniejszości (<). Jeśli w
drzewie znajduje się już składnik, którego pole dane1 zawiera
taki sam łańcuch jak argument odpowiadający parametrowi
element1, to nastąpi wyświetlenie zapytania o wymianę
składnika drzewa. Po wymianie zmiennej wymiana jest
przypisywana wartość True i wartość ta przekazywana jest na
zewnątrz procedury. Jest istotne, aby przy każdym wywołaniu
procedury (poza pierwszym) zmienna korzen wskazywała na
początek drzewa, tj. aby wartość nadana tej zmiennej w wyniku
pierwszego wywołania procedury nie uległa zmianie.

2) Procedura poszukiwania (adresu) składnika drzewa:

procedure AdresSkladnikaDrzewa
(var element1 : string;
var korzen, skladnik_biezacy :
wskaznik_drzewa);
begin
if korzen<>nil
then begin
skladnik_biezacy:=korzen;
if element1<>korzen^.dane1
then repeat
if element1 then
skladnik_biezacy:=skladnik_biezacy^.wskaznik1
else
skladnik_biezacy:=skladnik_biezacy^.wskaznik2
until (element1=skladnik_biezacy^.dane1)
or (skladnik_biezacy=nil)
end
end;

Powyższa procedura powoduje przypisanie zmiennej skladnik_
biezacy adresu składnika drzewa, którego pole dane1 zawiera
tekst podany pierwszym argumentem wywołania procedury. Jeśli
żadne pole dane1 nie zawiera tego tekstu, to zmiennej
skladnik_biezacy zostanie przypisany adres pusty (nil).

3) Procedura usuwania drzewa z pamięci:

procedure UsuniecieDrzewa (var korzen : wskaznik_drzewa);
var poprzedni_skladnik, nastepny_skladnik :
wskaznik_drzewa;
begin
if korzen<>nil
then begin
repeat
nastepny_skladnik:=korzen;
while nastepny_skladnik^.wskaznik1<>nil do
begin

poprzedni_skladnik:=nastepny_skladnik;

nastepny_skladnik:=nastepny_skladnik^.wskaznik1
end;
while nastepny_skladnik^.wskaznik2<>nil do
begin

poprzedni_skladnik:=nastepny_skladnik;

nastepny_skladnik:=nastepny_skladnik^.wskaznik2
end;
if
poprzedni_skladnik^.wskaznik1=nastepny_skladnik
then poprzedni_skladnik^.wskaznik1:=nil
else poprzedni_skladnik^.wskaznik2:=nil;
Write ('Eliminowany składnik : ');
Writeln (nastepny_skladnik^.dane1);
Dispose (nastepny_skladnik);
Delay (500)
until nastepny_skladnik=korzen;
korzen:=nil
end
end;

Procedura UsuniecieDrzewa usuwa całe drzewo o adresie
korzenia określonym przez wartość argumentu wywołania. Pola
dane1 eliminowanych kolejno z drzewa składników są wyświetlane
na ekranie.

4) Poniższy program, wykorzystując procedury podane w
przykładach 1), 2) i 3) oraz pewne procedury modułu Crt
(zob. p. 14.5.2), tworzy listę adresów o strukturze
drzewiastej, a następnie umożliwia jej przeglądanie. Po
zakończeniu przeglądania drzewo jest usuwane z pamięci.

program AM65;
uses Crt;
type zapis = record
ulica_nr : string [30];
kod : string [5];
miejscowosc : string [25];
telefon : string [6]
end;
wskaznik_drzewa = ^skladnik_drzewa;
skladnik_drzewa = record
dane1 : string [70];
dane2 : zapis;
wskaznik1, wskaznik2 :
wskaznik_drzewa
end;
var korzen, skladnik_biezacy : wskaznik_drzewa;
nazwisko_imie : string;
inne_dane : zapis;
wymiana,koniec : Boolean;
i : Integer;
odp : Char;
{$I DRZEWO.PAS} { Zbiór DRZEWO.PAS zawiera procedury
DoDrzewa,
AdresSkladnikaDrzewa i UsuniecieDrzewa.
W procedurze
DoDrzewa drugi parametr powinien być
typu zapis,
zdefiniowanego w programie }
begin
ClrScr;
TextColor (Yellow);
TextBackground (Blue);
GotoXY (27, 1);
Writeln ('PRZYKŁAD DRZEWA BINARNEGO');
Window (1, 3, 80, 25);
TextBackground (Black);
Writeln ('Wprowadź dane (** koniec wprowadzania)');
korzen:=nil;
i:=0;
koniec:=False;
repeat
i:=i+1;
Writeln ('Dane ', i, ' :');
Write ('Nazwisko i Imie : ');
Readln (nazwisko_imie);
if nazwisko_imie='**'
then koniec:=True
else begin
with inne_dane do
begin
Write ('Ulica i numer domu : ');
Readln (ulica_nr);
Write ('Kod (pięć cyfr) : ');
Readln (kod);
Write ('Miejscowość : ');
Readln (miejscowosc);
Write ('Numer telefonu (sześć cyfr) :
');
Readln (telefon)
end;
wymiana:=False;
DoDrzewa (nazwisko_imie, inne_dane, korzen,
wymiana);
if wymiana
then i:=i1
end
until koniec;
if i>1
then begin
ClrScr;
Writeln ('Drzewo binarne zostało utworzone.');
i:=i1;
Writeln ('Liczba składników drzewa : ', i);
Writeln;
Delay (1500);
koniec:=False;
repeat
ClrScr;
Writeln ('PRZEGLĄDANIE ADRESÓW');
Writeln;
Write ('Podaj nazwisko i imię (* koniec
przeglądania) :');
Writeln;
Write (' ');
Readln (nazwisko_imie);
if nazwisko_imie='*'
then koniec:=True
else begin
AdresSkladnikaDrzewa (nazwisko_imie,
korzen,
skladnik_biezacy);
if skladnik_biezacy=nil
then Writeln ('Brak danych')
else with skladnik_biezacy^.dane2
do
begin
Writeln ('Adres : ',
ulica_nr);
Writeln (' ', Copy(kod, 1,
2), '',
Copy(kod, 3, 3), ' ',
miejscowosc);
Writeln ('Telefon : ',
Copy(telefon, 1, 3),
'', Copy(telefon, 4,
3))
end;
Writeln;
Writeln ('Naciśnij dowolny
klawisz...');
repeat
odp:=ReadKey
until odp<>''
end
until koniec;
Writeln;
UsuniecieDrzewa (korzen);
Writeln ('Koniec programu.');
Delay (2000)
end
end.

Wyszukiwarka

Podobne podstrony:
Metody układania algorytmów rekurencja, metoda dziel i zwyciężaj, programowanie dynamiczne, metoda
Lekcja programowanie dynamiczne
Tworzenie dynamicznych tablic komunikacyjnych w programie Power Point(1)
Program naprawczy podniesienie frekwencji uczniów kl III TP
zestawy cwiczen przygotowane na podstawie programu Mistrz Klawia 6
Międzynarodowy Program Badań nad Zachowaniami Samobójczymi

więcej podobnych podstron