Wstęp

do programowania

Wykład 7 - wskaźniki

Wskaźniki

Definicja wskaźnika określa jak zinterpretować

zawartość pamięci pod adresem pokazywanym

przez wskaźnik

np. wsk :^byte; oznacza, że obszar zawiera liczbę

typu byte

var

wsk_int : ^ integer; {zmienna wskazująca zmienną typu

integer}

wsk_char: ^char; {zmienna wskazująca zmienną typu char}

wsk_real: ^real; {zmienna wskazująca zmienną typu real}

Wskaźniki

type

tab=array[1..10] of integer;
wsk=^tab;

var

wsk_tab: ^tab; {zmienna wskazująca zmienną tablicową}

wsk_tab : wsk;

tab_wsk: array[1..10] of

^integer; {tablica, której elementami są

wskaźniki do typu integer}

p: pointer; {zmienna wskazująca zmienną dowolnego typu}

Zawartość zmiennej typu pointer można podstawić do zmiennej dowolnego

typu i na odwrót.

Jednak odwołując się do obiektu wskazywanego trzeba jawnie określić typ.

• Deklaracja zmiennej wskaźnikowej nie jest jednoznaczna z utworzeniem

zmiennej wskazywanej.

• Każda zmienna wskaźnikowa musi być przed użyciem zainicjalizowana.

Wskaźniki

Wskaźniki

Nazwa zmiennej odwołuje się do obszaru pamięci

o określonym

adresie

Adres pamięci pod którym znajduje się zmienna można uzyskać

za pomocą operatora @ (@zmienna)
Wskaźnik może odwoływać się do

różnych

miejsc w pamięci

przy czym jest tak zdefiniowany że pokazuje na obiekty

jednego określonego typu:

wskaźnik służący do pokazywania na obiekty jednego typu nie

może (zazwyczaj) pokazywać na obiekty innego typu

Za pomocą wskaźnika uzyskujemy dostęp do pewnego obszaru

pamięci i możemy modyfikować jego zawartość

Sposoby inicjalizacji zmiennych wskaźnikowych:
(czyli nadawania im początkowych wartości)

- przypisanie standardowej wartości stałej nil;
- przypisanie adresu utworzonej zmiennej dynamicznej -
procedury new i getmem;
- przypisanie adresu dowolnej istniejącej zmiennej;
- przypisanie wartości wcześniej zainicjalizowanej
zmiennej wskaźnikowej;

Rezerwacja obszarów pamięci

wskaźnik pokazuje na jakiś obszar w pamięci



może to być obszar przechowujący zmienną – a więc

zarezerwowany



My możemy zarezerwować (zaalokować) obszar używając

wskaźnika. Służy do tego funkcja new



jeśli obszar jest nam niepotrzebny, to należy go zwolnić.

Służy do tego funkcja dispose

obiekty utworzone za pomocą operatora new istnieją dopóki ich

nie zlikwidujemy funkcją dispose
Tak utworzony obiekt nie ma nazwy, można odwoływać się do

niego tylko za pomocą wskaźnika
obiekty tak tworzone są dynamiczne. Nie są wstępnie

inicjalizowane zerami

nil

wsk

wsk : ^typ

wsk:=nil;

nil - standardowa stała, mówiąca,
że zmienna wskaźnikowa na nic nie
wskazuje czyli tzw. adres „zero”
- (żaden konkretny adres)

wskaźnik można porównać z adresem 0 (w kompilatorach

Borlanda/ Delphi oznaczanym również przez NIL)

ustawienie wskaźnika jako pokazującego na 0 (NIL) jest

wykorzystywane do zaznaczenia, że wskaźnik nie pokazuje na nic

konkretnego :

wsk:^byte = NIL;



bez takiego przypisania wskaźnik pokazuje NA COŚ – tj. na jakiś

losowy adres w pamięci



Wskaźniki mogą być elementami struktur

Dozwolone jest również używanie wskaźników do struktur

Var w : ^typ1

new(w)
w^:=wyrażenie w

w^

Tworzenie zmiennej dynamicznej
1) utworzenie nowej zmiennej dynamicznej typu typ1,

która w tym momencie nie jest określona,
nadawana jest jej automatycznie nazwa w^,

2) utworzenie nowego wskaźnika w typu ^typ1,

który wskazuje na zmienną typu typ1,

3) nadanie wartości tego wskaźnika zmiennej,

dla której procedura new została wywołana

(czyli nadanie zmiennej dynamiczej w^ adresu pamięci
Przeznaczonego dla zmiennej typu typ1
4) Zapis do obszaru pamięci na który wskazuje wskaźnik w
konkretnej wartości danych zawartych w wyrażeniu

p:^typ

getmem(p,l_bajt)

procedura getmem różni się od
procedury new tym, że wielkość
zarezerwowanego miejsca w pamięci
określana jest dopiero w czasie
trwania programu i sami możemy
zdecydować o rozmiarze potrzebnej
pamięci podając drugi parametr tej
procedury - l_bajt

Operator adresu : @

x: typ;
w: ^typ;

x:=12;

w:=@ x;

w^ = =12

...

Funkcja standardowa Addr(x)

zwraca wskaźnik typu pointer
zawierający adres miejsca,
gdzie zapamiętane jest x

w:=addr(x);

program wsk1;
{$APPTYPE CONSOLE}{$O-,Q+,R+}

uses

SysUtils;

type

TDane = string[60];

var

w1 :^TDane;

begin

new(w1);
w1^ := 'Coś tam';
w1^[2]:='U'; //podmiana drugiej litery w lancuchu

Writeln(w1^ );

dispose(w1);
readln;

end.

w1

w1^

5

program wsk2;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
Uses SysUtils;

type

TDane = string[60];

var

w1, w2 :^TDane;

begin

new(w1);

w1^ := 'Coś tam';
w2 := w1;

w2^:=‘Cos innego tam jest';

writeln(w1^);
writeln(w2^);

dispose(w2);
readln;

end.

w2

w1

w1^

Cos tam

w1

w1^ Cos tam

w2

program wsk3;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
{ użycie zmiennych wskaźnikowych i dynamicznych}
type

wsk_int= ^integer;
typDanych=record

imie, nazwisko:string;

end;

wsk_rek= ^typDanych;

var

x1,x2:wsk_int;
r1: wsk_rek;

begin

new(r1); //zm. Dyn rekordowe

readln(r1^.imie, r1^.nazwisko);

with r2^ do

writeln(imie, nazwisko);
dispose(r1);

new(x1); //zm. Dynam calkowite
new(x2);
x1^:=5; x2^:=10;
writeln('x1^=',x1^);
x2^:=x1^; //przepisanie zawartości
x2:=x1; //przepisanie adresu
writeln('x1^=',x1^);
writeln('x2^=',x2^);

dispose(x1); dispose(x2);
readln; end.

x2

x2^

x1

x1^

10

5

x1

x1^

5

x2

5

new (p);
.
.
dispose(p);

Zwalnianie pamięci przydzielonej w sposób dynamiczny
- procedury dispose i freemem

getmem (p,l_bajt);

freemem(p,l_bajt);

Procedury te umożliwiają powtórne wykorzystanie obszarów pamięci
oddawanych przez niepotrzebne już zmienne dynamiczne.

Może się zdarzyć, że w czasie zakładania zmiennych dynamicznych wystąpi
błąd - zabraknie miejsca w pamięci.

Wielkość dostępnej pamięci w bajtach można poznać korzystając z dwóch
funkcji:

memavail

- zwraca wielkość dostępnej pamięci, która jest sumą

wszystkich wolnych obszarów na stercie;

maxavail

- zwraca wielkość największego z wolnych bloków i takiej

wielkości zmienną dynamiczną można utworzyć

Zwalnianie pamięci przydzielonej w sposób dynamiczny

- procedury dispose i freemem

if maxavail>=sizeof(r1^) then new(r1) else.....

if maxavail>=siezeof(x1^) then getmem(x1,sizeof(x1^)) else....

Zalecana jest ostrożność przy korzystaniu z procedury getmem
- kompilator nie jest w stanie sprawdzić odwołań do tak zdefiniowanej
zmiennej:

type

tab=array[1..20] of integer;
wsk_tab=^tab;

var

wpom : wsk_tab;

..

getmem(wpom,20*sizeof(integer)); {utworzenie zmiennej dynamicznej o 20
elementach}
wpom^[1]:=5;

{poprawne odwołanie do elementu pierwszego}

wpom^[-2]:=10; {błąd zakresu zgłaszany przez kompilator}

wpom^[25]:=-7; {uwaga: błąd zakresu nie zgłaszany przez kompilator}

Wskaźniki i tablice

Wskaźniki są przydatne do pracy z tablicami:



zapis

w := @tab[3];

powoduje, że wskaźnik wsk ustawia się na elemencie

tablicy o indeksie 3



Nazwa tablicy jest równocześnie adresem jej

pierwszego elementu zatem napisanie

w = @tab;

jest równoważne napisaniu w = @tab[pocz];



Jeśli pocz jest pierwszym elementem tablicy

Tablice

Wskaźników

program wsk3;
{$APPTYPE CONSOLE} {$O-,Q+,R+}
type

TDane = string[30];

Const MaxN = 5;
var

A: array[0..MaxN-1] of ^TDane;
i :0..MaxN;

begin

for i := 0 to MaxN-1 do A[i] := nil;
new(A[2]); A[2]^ := 'Coś tam';
new(A[4]); A[4]^ := 'Coś innego';
for i := 0 to MaxN-1 do

if A[i] <> nil then begin

writeln('nr: ' , i, ' ',A[i]^);

dispose(A[i]); // A[i] := nil;

end;

readln;

end.

Wskaźniki

do tablic

program wsk4;

{$APPTYPE CONSOLE}{$O-,Q+,R+}

Const MaxN = 5;

Type Tab=array[1..MaxN]of byte;

wskTab=^Tab;

Var i :byte;

B: Tab; //tablica statyczna

w :wskTab;

begin

for i:=1 to MaxN do B[i]:=i; //tab statyczna

w:=@B; //ustaw wsk

writeln(w^[1]); //writeln(B[1]);

inc(w);

writeln(w^[2]); //inc adresu poza adres całej tablicy

w:=@B[3]; writeln(w^[1]); //pokazuje na 3-ci element

readln; End.

Wskaźniki

do tablic

program wsk5;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
Const N = 5;

Type Tab=array[1..N]of byte;

wskTab=^Tab;

Var i :byte;

w,x :wskTab;

begin
new(w); // tablica dynamiczna

for i:=1 to N do w^[i]:=i;

writeln('1-szy =', w^[1]);
writeln('2- gi =', w^[2]);
writeln('N-ty =', w^[N]);
x:=w;
x^[N]:=115;

for i:=1 to N do write(x^[i]:5);writeln;

k:=@w; //losowy element

writeln(k^);
k:=@w;[1] //pierwszy element
writeln(k^);

dispose(w);

readln; End.

Wskaźniki do tablic

program wsk6;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
Const N = 5;

Type Tab=array[1..N]of byte;

wskTab=^Tab;

Var i :byte; k:^byte=nil;

w,x,v :wskTab;

begin
new(w); // tablica dynamiczna
New(x);

for i:=1 to N do w^[i]:=i;
for i:=1 to N do x^[i]:=10*i;

writeln('1-szy =', w^[1]);
writeln('N-ty =', w^[N]);

for i:=1 to N do write(x^[i]:5);writeln;

k:=@w[1];
writeln(k^, ' -1 szy elem tab w');
inc(k);
writeln(k^, ' -2 gi elem tab w');

writeln((k+2)^, ' -4 ty elem tab w');

writeln;

writeln('w1=', w^[1]);

writeln('x1= ',x^[1]);

v:=w; //zapamietaj adres w

inc(w);

writeln('w2=', w^[2]);

writeln('x2 =',x^[2]);

inc(w);

writeln('w3=', w^[3]);

writeln('x3 =',x^[3]);

writeln('w5=', w^[5]); //teraz w[5]=x[3]

writeln('adresy tablic');

writeln(Integer(v),' ', Integer(w),' ',Integer(x));

writeln('r:',integer(@x[1])-Integer(@w[1]));

dispose(v); //blad dispose(w) bo adres w zmien

dispose(x);

readln; End.

Operacje arytmetyczne na

wskaźnikach

Dozwolone jest:



dodawanie i odejmowanie od wskaźników liczb

naturalnych – powoduje to przesuwanie

wskaźników



ponieważ wskaźnik pokazuje na obiekt pewnego typu i

wiadomo jaki jest rozmiar tego typu, więc wiadomo o ile

przesunąć wskaźnik



odejmowanie dwóch wskaźników pokazujących na

tę samą tablicę



w wyniku dostajemy liczbę elementów tablicy dzielących

elementy pokazywane przez wskaźniki (liczba może być

ujemna lub dodatnia, zależnie od uporządkowania tych

elementów w tablicy)

Porównywanie wskaźników

Wskaźniki można ze sobą porównywać za pomocą

operatorów

= <>

<

>

<=

>=

równość wskaźników oznacza, że pokazują one na

ten sam obiekt
wskaźnik, który jest mniejszy, pokazuje na element o

niższym adresie (w tablicy – na element o niższym

indeksie)

Arytmetyka wskaźników

- zwiększenie lub zmniejszenie zmiennej wskaźnikowej o określonym typie
(nie pointer) za pomocą

procedur inc i dec; zmiana wartości zmiennej jest równa rozmiarowi typu

wskazywanego

np. x: ^Double; inc(x,2) spowoduje zwiększenie o 2*3 = 6 bajtów;

k:^integer; inc(k,3)spowoduje zwiększenie o 3*2 = 6 bajtów

Operacje zwiększania i zmniejszania wskaźników mają zastosowanie tylko w

wypadku elementow tablic:

jeśli zmienna wskaźnikowa zw wskazuje na element 5 tablicy to dec(zw)

będzie wskazywać na element 4 niezależnie od typu elementów.



jeśli ustawiliśmy wskaźnik na pewnym elemencie tablicy, to napisanie

Inc(wsk);

powoduje, że przesuwa się on do następnego elementu tej tablicy



uwaga – nie jest sprawdzane, czy w ten sposób nie przesuniemy się

poza zakres tablicy

Porównania można wykonywać tylko na wskaźnikach, które pokazują na

typy niesprzeczne;

wskaźnikiem neutralnym, nie pokazującym na żaden typ danych jest

zmienna wskaźnikowa typu pointer;

służy jedynie do przekazywania adresów innych zmiennych;
var

wsk_i:^integer;
wsk_c: ^char;
wsk:pointer;

begin

(* new(wsk);

wsk^:=5; *) {niedopuszczalne}

new(wsk_i);
wsk_i^:=5;
wsk:=wsk_i; {dopuszczalne}
wsk:=wsk_c;
if wsk=wsk_i then ... {dopuszczalne bo wsk jest typu pointer}

end.

Typ pointer

Kolejki i Listy, stosy

W wielu algorytmach pojawia się potrzeba
wykorzystania struktury danych, umożliwiającej
wstawianie i pobieranie danych. Najprostszymi taki
strukturami są kolejka i stos.

Kolejki

• Kolejka to rodzaj listy jednokierunkowej, do której można dopisać

element tylko na końcu a usunąć element znajdujący się na początku.

Umożliwia wstawianie nowych elementów na koniec i
pobieranie elementów z początku.
Kolejka realizuje strategię wstawiania/pobierania - pierwszy
wszedł, pierwszy wyjdzie).
Kolejka zachowuje kolejność wstawianych elementów.
Operacje:

wstawianie. Pobieranie, usuń element, usuń wszystko, wyświetl,

czy pusta

Listy

Lista jednokierunkowa
Lista jest zbiorem elementów zwanych węzłami, z których każdy zwykle

jest rekordem i składa się z dwóch części.

Część łącząca

(adres

następnego

skladnika)

Część

składowa
(dane)

type

wsk =^skladnik;

skladnik = record

dane: typ;

next : wsk

end;

Listy

Dostęp do listy odbywa się poprzez wskaźnik, który zawiera adres

pierwszego elementu na liście.

Wskaźnik ten nazywany jest poczatkiem bądź korzeniem listy.

Każdy następny składnik listy jest dostępny poprzez składową

zawierającą adres w składniku poprzednim.









1

2

27

43

początek



NIL

Listy

Tworzenie nowej listy:

procedure tworz_liste;
var

zn : char;

begin

poczatek:=nil;
repeat

new(wsk);
write(’ Podaj kolejny element listy ’)
readln(wsk^.dane);
wsk^.next:=pocz;
pocz:=wsk;
write(’ czy kontynuować ? ’);
readln(zn)

until zn<>’t’;

end;



{1}

poczatek

NIL

{2}



?

?

wsk

{3}



?

dane

wsk



NIL





dane

poczatek

wsk

{4}



NIL





dane

poczatek

wsk

{5}

type

wsk =^skladnik;

skladnik = record

dane: typ;

next : wsk

end;

Najważniejsze operacje dotyczące wszystkich typów list:

wpisywanie nowego elementu

- kiedy lista jest pusta,
-

na jej początku,

-

na jej końcu,

-

w dowolnym miejscu wewnątrz listy.

usuwanie elementu

-

znajdującego się na początku,

-

znajdującego się na końcu,

-

w dowolnym miejscu wewnątrz listy.

wyświetlanie listy

Aby możliwe było wykonanie operacji wstawiania oraz usuwania
nowych elementów lista musi być posortowana wg określonego
klucza. Kluczem do sortowania może być np. pole nazwisko jeśli mamy
do czynienia z listą osób.

Dla uproszczenia przyjmiemy, że kluczem jest pole dane oraz że
możemy wykonywać na tym polu zwykłe operacje porównania.

Drzewa i Stosy

Stos

Umożliwia wstawianie elementów i ich pobieranie z początku (wierzchołka) stosu.

Stos realizuje strategię wstawiania/pobierania

LIFO (Last In, First Out; ostatni wszedł, pierwszy wyjdzie).
Stos odwraca kolejność wstawianych elementów.



Operacje:

Wstawianie, pobranie, czy jest pusty, pierwszy element, inicjalizacja, usuwanie
wyświetlanie



jak reprezentować stos, czyli co to jest TStos (tablica, lista),

często spotykane nazwy angielskie (wstaw - push; pobierz - pop;

pusta - empty; pierwszy - top),

Stos

Zadanie : Program z operacjami na stosie
Dane : tablica kwadratowa
Operacje:
Wkladanie na stos,
Zdejmowanie ze stosu
Dodawanie, odejmowanie, mnaozenie tablic na wierzołku stosu
Wykonac
W programie glownym wykonać
C:=A+B
C=A-B
C:=A+(B*C)

Program Stos;
const NMax=2;
Type float=double;

TArr=array[0..NMax-1,0..NMax-1] of float;

PElement=^TElement;

TElement =record

poprz :PElement;
X:TArr;

end;

TStos=PElement;{wskaľnik na wierzchoˆ

ek stosu}

procedure NaStos(var St :TStos; _X :TArr); {X -dane nowego elementu stosu}

var w :PElement;

begin

new(w);
w^.X:=_X;
w^.poprz:=St;
St:=w;

end;

procedure ZeStosu(var St :TStos; var _X :TArr); {X -zawartos likwidowanego el.}

var w :PElement;

begin

if (St=nil) then EXIT; {bˆ

Ąd!}

w:=St;
_X:=w^.X;
St:=w^.poprz;
Dispose(w);

end;
procedure Dodaj(var St :TStos); {dodaje 2 g˘rne elementy stosu -

zdejmuje 1 a wynik umieszcza w wierzchoˆ

ku stosu}

var i, j :0..NMax-1;

T :TArr;

begin

ZeStosu(St, T);
for i:=0 to NMax-1 do

for j:=0 to NMax-1 do

St^.X[i,j]:=St^.X[i,j]+T[i,j];

end;

procedure Odejmij(var St :TStos); {odejmuje najwyľszy od niľszego

element stosu - zdejmuje 1 element a wynik umieszcza w wierzchoˆ

ku stosu}

var i, j :0..NMax-1; T :TArr;

begin

ZeStosu(St, T);
for i:=0 to NMax-1 do

for j:=0 to NMax-1 do

St^.X[i,j]:=St^.X[i,j]-T[i,j];

end;
procedure Mnoz(var St :TStos); {mnoľy elementy stosu poniľszy*g˘rny

a wynik umieszcza w wierzchoˆ

ku stosu}

var i, j, k :0..NMax-1;

A {czynik}, C {wynik} :TArr;

begin

ZeStosu(St, A);{2-gi czynnik}
for i:=0 to NMax-1 do

for j:=0 to NMax-1 do begin

C[i,j]:=0;
for k:=0 to NMax-1 do

C[i,j]:=C[i,j]+St^.X[i,k]*A[k,j];

end;

{zdejmij ze stosu 2-gi czynik, a poˆ

˘ľ tam wynik}

ZeStosu(St, A);
NaStos(St, C);

end;

procedure Wyswietl(Nagl:string; A :TArr);
{wyˆ

wietla element wskazywany przez W, na pocz. wyˆ

wietla Nagl}

var i, j :0..NMax-1;

begin

writeln(Nagl);
for i:=0 to NMax-1 do begin

for j:=0 to NMax-1 do

write(A[i,j]:6:1,' ');

writeln;

end;
writeln;

end;
procedure InicjujDowolnie(var A :TArr);

var i, j :0..NMax-1;

begin

for i:=0 to NMax-1 do

for j:=0 to NMax-1 do

A[i,j]:=random(10) -5.0;

end;

procedure Pause; begin write('Naciˆ

nij ENTER...':60); readln; end;

var St :TStos;
var A,B,C :TArr;

procedure TestStNil; begin

if (St<>nil) then writeln('Program zawiera bˆ

ledy!');

end;

BEGIN

writeln(#13#10,'=== Stos i odwrotna notacja polska ===':60);

St:=nil;
Randomize; InicjujDowolnie(A); InicjujDowolnie(B);

Wyswietl('A:',A); Wyswietl('B:',B);

NaStos(St,A);
NaStos(St,B);
Dodaj(St);
ZeStosu(St,C); Wyswietl('C=A+B',C);

TestStNil; Pause;

NaStos(St,A);
NaStos(St,B);
Odejmij(St);
ZeStosu(St,C); Wyswietl('C=A-B',C);

TestStNil; Pause;

NaStos(St,A);

NaStos(St,B);
Mnoz(St);
ZeStosu(St,C); Wyswietl('C=A*B',C);

TestStNil; Pause;

NaStos(St,A);
NaStos(St,B);
NaStos(St,C);
Dodaj(St);
Mnoz(St);
ZeStosu(St,C); Wyswietl('C=A*(B+C)',C);

TestStNil; Pause;

END.

Drzewo binarne - struktura dynamiczna składająca się z węzłów i
gałęzi, przy czym każdy węzeł ma co najwyżej dwie gałęzie.

 

 

 

 

korzeń

węzeł

liść

węzeł

liść

NIL

NIL

NIL

NIL

NIL

gałąź

Korzeń czyli pierwszy węzeł zwany
jest czasami węzłem głównym;
Węzły bez gałęzi nazywamy liśćmi.
W drzewie binarnym wyróżniamy
prawą i lewą część

type

wsk_w=^wezel;

wezel = record

dane: typ;

lewy :wsk_w;

prawy :wsk_wl

end;

var

korzen, wskaz : wsk_wl

Drzewo binarne nazywamy uporządkowanym jeżeli zawartość
każdego węzła jest większa od zawartości jego lewego następnika
i jednocześnie mniejsza od zawartości jego prawego następnika.
Pojęcie mniejszości i większości zależy od klucza wg którego
dokonywane jest sortowanie. Uporządkowane drzewo binarne
uzyskuje się przez odpowiednie wpisywanie nowych węzłów.

//sortowanie
procedure wstaw_sort(var wezel_stary :wsk_w;

wstaw:integer);

var

wezel_nowy : wsk_w;

begin

if wezel_stary=nil then

begin

new(wezel_nowy);
wezel_nowy^.liczba:=wstaw;
wezel_nowy^.lewy:=nil;
wezel_mowy^.prawy:=nil;
wezel_stary:=wezel_nowy;

end

else

if wstaw<wezel_stary^.liczba then

wstaw_sort(wezel_stary^.lewy,wstaw)

else

if wstaw>wezel_stary^.liczba then

wstaw_sort(wezel_stary^.prawy,wstaw)

else writeln(’Podana liczba jest już w spisie !’)

end;

procedura drzewo tworzy nowy węzeł i wpisuje
go do drzewa w ustalonym porządku co
uzyskuje się przez rekurencyjne wywołanie
tej procedury. Procedura ta powinna być
wywoływana po raz pierwszy
z parametrem będącym korzeniem drzewa np.:

procedure wstaw_drzewo(var korzen:wsk_w);
var tliczba:integer;
begin

repeat
writeln(’ Podaj liczbę do wpisu : ’);
readln(liczba);
if liczba<>-1 then

wstaw_sort(korzen, liczba)

until liczba=-1

end;

Type wsk_w=^wezel;

wezel = record

liczba: integer;
lewy:wsk_w;
prawy:wsk_w

end;

Program główny będzie wywoływał
procedurę wpisywania danych do drzewa:

program binarne_drzewo;
uses crt;
type

wsk_w=^wezel;

wezel = record

liczba: integer;
lewy:wsk_w;
prawy:wsk_w

end;

var

korzen:wsk_w;

...

begin

korzen:=nil;

wstaw_drzewo(korzen);

....

end.

Załóżmy, że wczytany będzie ciąg liczb:
4,6,2,9,3,1,12
W pierwszym wywołaniu procedury
Drzewo korzen wskazuje na nil
a pierwszą wczytaną liczbą jest 4

Sortowanie dokonywać się będzie od
tego węzła w lewo i w prawo. Pierwszy
węzeł umieszczony w drzewie zawsze
pełni rolę korzenia.

Ponieważ wezel_stary wskazuje na nil
więc zostaje wykonane:

new(wezel_nowy);

wezel_nowy ^.liczba:=4;

wezel _nowy ^.lewy:=nil;
wezel _nowy ^.prawy:=nil;
wezel_stary :=wezel_ nowy;

 

4

korzeń

NIL

NIL

prawy

lewy

Po wpisaniu drugiej wartości (2) zostaje wywołana
procedura drzewo z parametrem korzen, który
teraz nie wskazuje na nil lecz na pierwszy węzeł.
Zostaje więc wykonana część else instrukcji if:
else

if wstaw<wezel_stary^.liczba then

wstaw_sorto(wezel_stary^.lewy,wstaw)

else

if wstaw>wezel_stary^.liczba then

wstaw_sort(stary_wezel^.prawy,wstaw)

else writeln(’Podana liczba jest już w spisie !’)

Ponieważ 2<4 {wstaw<wezel_stary^.liczba}
następuje wywołanie

wstaw_sort(wezel_stary^.lewy,wstaw)

procedura wywołuje samą siebie z lewym
wskaźnikiem, który wskazuje nil.
if stary_wezel=nil then

begin

new(wezel_nowy);
wezel_nowy^.liczba:=2;
wezel_nowy^.lewy:=nil;
wezel_nowy^.prawy:=nil;
wezel_stary :=wezel_nowy;

end; {jest lewą gałęzią pierwszego węzła}

W taki sam sposób uzyskamy dopisanie

liczby 6 w postaci trzeciego węzła, który

tym razem będzie zawieszony na prawej

gałęzi:



4

korzeń

NIL

prawy

lewy





2

prawy

lewy



NIL

NIL

 

 

 

korzeń

4

2

6

NIL

NIL

NIL

NIL

lewy

lewy

lewy

prawy

prawy

prawy

Następną wprowadzoną liczbą jest 9
Po wywołaniu procedury wstaw_drzewo
wezel_stary wskazuje na węzeł z elementem 4
czyli wykonywana jest część else i element 9
zostaje porównany z elementem 4.

Ponieważ 9>4

następuje rekurencyjne wywołanie

wstaw_sort(wezel_stary^.prawy,wstaw)

Teraz stary_wezel^.lewy wskazuje na węzeł z elementem
6 (nie na nil) czyli ponownie wykonana jest część else i
porównanie 9 i 6.
Ponieważ 9>6 następuje wywołanie rekurencyjne, w
którym wezel_stary jest węzłem z elementem 6:

wstaw_sort(wezel_stary^.prawy,wstaw)

Teraz wezel_stary^.prawy wskazuje na nil zatem
wykonywana jest część then:

new(wezel_nowy);

wezel_ nowy ^.liczba:=9;
wezel_ nowy ^.lewy:=nil;
wezel_ nowy ^.prawy:=nil;
wezel_stary := wezel_ nowy

Tutaj kończy się rekurencyjne wywoływanie
procedury sortowany_wpis i drzewo ma
następującą strukturę:

 

 

 

korzeń

4

2

6

NIL

NIL

NIL

lewy

lewy

lewy

prawy

prawy

prawy

 

9

NIL

NIL

lewy

prawy

Usuwanie drzewa również odbywa się poprzez rekurencję:

procedure Usun_drzewo(var pozycja:wsk_wl);
begin

if pozycja<>nil then

begin

if pozycja^.lewy<>nil then usun_drzewo(pozycja^.lewy);
if pozycja^.prawy<>nil then usun_drzewo(pozycja^.prawy);
dispose(pozycja)

end

end;

I tak jak w przypadku tworzenia drzewa wywołanie odbywało się
od korzenia, tak również w tym przypadku w celu usunięcia drzewa
trzeba dokonać wywołania:

usun_drzewo(korzen);
korzen:=nil;

Wywołanie tej procedury dla drzewa,
które stworzyliśmy
będzie miało następujący przebieg:

usuwanie_drzewa(korzen) ---> węzeł (4)
usuwanie_drzewa(4) ---> węzeł (2)
dispose (węzeł 2)
usuwanie_drzewa(4) {powrót} ---> węzeł (6)
usuwanie_drzewa(6) ---> węzeł (9)

dispose (węzeł 9)
dispose(6)
dispose(4)

 

 

 

korzeń

4

2

6

NIL

NIL

NIL

lewy

lewy

lewy

prawy

prawy

prawy

 

9

NIL

NIL

lewy

prawy

Drzewo-

przykład

program binarne_drzewo;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
uses SysUtils;
Type wsk_w=^wezel;

wezel = record

liczba: integer;
lewy:wsk_w;
prawy:wsk_w

end;

Var korzen:wsk_w;
procedure Wyswietl(pozycja :wsk_w); {przeglądanie metodą inorder}

begin

{1. Wyświetl lewe poddrzewo}
if (pozycja^.lewy <> nil) then Wyswietl(pozycja^.lewy);
{2. Wyświetl dane korzenia drzewa/poddrzewa}
with pozycja^ do

writeln( 'wezel=' ,liczba);

{3. Wyświetl prawe poddrzewo}
if (pozycja^.prawy <> nil) then

Wyswietl(pozycja^.prawy);

end;

//sortowanie
procedure wstaw_sort(var wezel_stary :wsk_w;wstaw:integer);
Var wezel_nowy : wsk_w;
begin

if wezel_stary=nil then

begin

new(wezel_nowy);
wezel_nowy^.liczba:=wstaw;
wezel_nowy^.lewy:=nil;
wezel_nowy^.prawy:=nil;
wezel_stary:=wezel_nowy;

end

else

if wstaw<wezel_stary^.liczba then

wstaw_sort(wezel_stary^.lewy,wstaw)

else

if wstaw>wezel_stary^.liczba then

wstaw_sort(wezel_stary^.prawy,wstaw)

else writeln('Podana liczba jest już w spisie !')

end;

procedure Usun_drzewo(var pozycja:wsk_w);
begin

if pozycja<>nil then

begin

if pozycja^.lewy<>nil then usun_drzewo(pozycja^.lewy);
if pozycja^.prawy<>nil then usun_drzewo(pozycja^.prawy);
writeln('usuwam ', pozycja^.liczba);

dispose(pozycja);

end
end;

procedure wstaw_drzewo(var korzen:wsk_w);
var aliczba:integer;
begin

repeat
writeln(' Podaj liczbę do wpisu (-1:Koniec) : ');
readln(aliczba);
if aliczba<>-1 then

wstaw_sort(korzen, aliczba)

until aliczba=-1

end;

begin

korzen:=nil;

wstaw_drzewo(korzen);

Wyswietl(korzen);

usun_drzewo(korzen);

readln;

korzen:=nil;

end.

Lista- przykład

program tworzy listę dynamiczną (dane : nazwisko) bez sortowania

(wpisuje na koniec, wyświetla i usuwa cała listę),

program Lista1;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
uses SysUtils;
type

TDane = string[60];

Type //element listy

PElem = ^TElem;
TElem = record

Dane :TDane;
Nast :PElem;

end;
TLista = PElem; //wskaźnik na początek listy

procedure inicjuj(var Lista :TLista);
begin

Lista := nil;

end;

procedure dopisz(var Lista :TLista; D

:TDane);

Var w :PElem;
begin

w := Lista;
new(Lista);
Lista^.Dane := D;
Lista^.Nast := w;

end;

procedure wypiszWszystko(Lista :TLista);
Var w :PElem;
begin

w := Lista;
while w <> nil do
begin

writeln(w^.Dane);
w := w^.Nast;

end;

end;

procedure usunWszystko(var Lista

:TLista);

procedure usunWszystko(var Lista :TLista);
Var w :PElem;
begin

while Lista <> nil do begin

w := Lista;
Lista := Lista^.Nast;
dispose(w);

end; end;

Var Lst :TLista;
begin

inicjuj(Lst);

dopisz(Lst, 'pierwszy');
dopisz(Lst, 'drugi');
dopisz(Lst, '3333');
wypiszWszystko(Lst);
usunWszystko(Lst);
readln; end.