Wstęp
do programowania
Wykład 7 - wskaz
niki
Wskaz
niki
Definicja wskaz
nika określa jak zinterpretować
zawartość pamięci pod adresem pokazywanym
przez wskaz
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}
Wskaz
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ą
wskaz
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 wskaz
nikowej nie jest jednoznaczna z utworzeniem
zmiennej wskazywanej.
" Każda zmienna wskaz
nikowa musi być przed użyciem zainicjalizowana.
Wskaz
niki
Wskaz
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)
Wskaz
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:
wskaz
nik służący do pokazywania na obiekty jednego typu nie
może (zazwyczaj) pokazywać na obiekty innego typu
Za pomocÄ… wskaz
nika uzyskujemy dostęp do pewnego obszaru
pamięci i możemy modyfikować jego zawartość
Sposoby inicjalizacji zmiennych wskaz
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 wskaz
nikowej;
Rezerwacja obszarów pamięci
wskaz
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
wskaz
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Ä… wskaz
nika
obiekty tak tworzone są dynamiczne. Nie są wstępnie
inicjalizowane zerami
wsk : ^typ
nil - standardowa stała, mówiąca,
że zmienna wskaz
nikowa na nic nie
wsk:=nil;
wskazuje czyli tzw. adres  zero
wsk - (żaden konkretny adres)
nil
wskaz
nik można porównać z adresem 0 (w kompilatorach
Borlanda/ Delphi oznaczanym również przez NIL)
ustawienie wskaz
nika jako pokazujÄ…cego na 0 (NIL) jest
wykorzystywane do zaznaczenia, że wskaz
nik nie pokazuje na nic
konkretnego :
wsk:^byte = NIL;
bez takiego przypisania wskaz
nik pokazuje NA COÅš  tj. na jakiÅ›
losowy adres w pamięci
Wskaz
niki mogą być elementami struktur
Dozwolone jest również używanie wskaz
ników do struktur
Var w : ^typ1
w^
new(w)
w
w^:=wyrażenie
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 wskaz
nika w typu ^typ1,
który wskazuje na zmienną typu typ1,
3) nadanie wartości tego wskaz
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 wskaz
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 : @
Funkcja standardowa Addr(x)
x: typ;
zwraca wskaz
nik typu pointer
w: ^typ;
zawierajÄ…cy adres miejsca,
gdzie zapamiętane jest x
x:=12;
w:=addr(x);
w:=@ x;
w^ = =12
...
program wsk1;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
uses
SysUtils;
w1^ 5
w1
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.
program wsk2;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
Uses SysUtils;
type
w1^ Cos tam
TDane = string[60];
w1
var
w1, w2 :^TDane;
w2
begin
new(w1);
w1^ Cos tam
w1^ := 'CoÅ› tam';
w1
w2 := w1;
w2^:= Cos innego tam jest';
writeln(w1^);
w2
writeln(w2^);
dispose(w2);
readln;
end.
program wsk3;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
{ użycie zmiennych wskaz
nikowych i dynamicznych}
type
wsk_int= ^integer;
typDanych=record
x1^ 5
imie, nazwisko:string;
end;
x1
10
wsk_rek= ^typDanych;
x2^
var
x2
x1,x2:wsk_int;
r1: wsk_rek;
begin
new(r1); //zm. Dyn rekordowe
readln(r1^.imie, r1^.nazwisko);
x1^ 5
with r2^ do
writeln(imie, nazwisko);
x1
dispose(r1);
5
new(x1); //zm. Dynam calkowite
x2
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.
Zwalnianie pamięci przydzielonej w sposób dynamiczny
- procedury dispose i freemem
getmem (p,l_bajt);
new (p);
.
freemem(p,l_bajt);
.
dispose(p);
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}
Wskaz
niki i tablice
Wskaz
niki sÄ… przydatne do pracy z tablicami:
zapis
w := @tab[3];
powoduje, że wskaz
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
program wsk3;
Tablice
{$APPTYPE CONSOLE} {$O-,Q+,R+}
type
Wskaz
ników
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.
program wsk4;
Wskaz
niki
{$APPTYPE CONSOLE}{$O-,Q+,R+}
Const MaxN = 5;
do tablic
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.
program wsk5;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
Wskaz
niki
Const N = 5;
Type Tab=array[1..N]of byte;
do tablic
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.
Wskaz
niki do tablic
program wsk6;
writeln('w1=', w^[1]);
{$APPTYPE CONSOLE}{$O-,Q+,R+}
writeln('x1= ',x^[1]);
Const N = 5;
v:=w; //zapamietaj adres w
Type Tab=array[1..N]of byte;
inc(w);
wskTab=^Tab;
writeln('w2=', w^[2]);
Var i :byte; k:^byte=nil;
w,x,v :wskTab;
writeln('x2 =',x^[2]);
begin
inc(w);
new(w); // tablica dynamiczna
writeln('w3=', w^[3]);
New(x);
writeln('x3 =',x^[3]);
for i:=1 to N do w^[i]:=i;
for i:=1 to N do x^[i]:=10*i;
writeln('w5=', w^[5]); //teraz w[5]=x[3]
writeln('1-szy =', w^[1]);
writeln('adresy tablic');
writeln('N-ty =', w^[N]);
writeln(Integer(v),' ', Integer(w),' ',Integer(x));
for i:=1 to N do write(x^[i]:5);writeln;
writeln('r:',integer(@x[1])-Integer(@w[1]));
k:=@w[1];
writeln(k^, ' -1 szy elem tab w');
dispose(v); //blad dispose(w) bo adres w zmie
inc(k);
dispose(x);
writeln(k^, ' -2 gi elem tab w');
readln; End.
writeln((k+2)^, ' -4 ty elem tab w');
writeln;
Operacje arytmetyczne na
wskaz
nikach
Dozwolone jest:
dodawanie i odejmowanie od wskaz
ników liczb
naturalnych  powoduje to przesuwanie
wskaz
ników
wðponieważ wskaz
nik pokazuje na obiekt pewnego typu i
wiadomo jaki jest rozmiar tego typu, więc wiadomo o ile
przesunąć wskaz
nik
odejmowanie dwóch wskaz
ników pokazujących na
tÄ™ samÄ… tablicÄ™
wðw wyniku dostajemy liczbÄ™ elementów tablicy dzielÄ…cych
elementy pokazywane przez wskaz
niki (liczba może być
ujemna lub dodatnia, zależnie od uporządkowania tych
elementów w tablicy)
Porównywanie wskaz
ników
Wskaz
niki można ze sobą porównywać za pomocą
operatorów
= <> < > <= >=
równość wskaz
ników oznacza, że pokazują one na
ten sam obiekt
wskaz
nik, który jest mniejszy, pokazuje na element o
niższym adresie (w tablicy  na element o niższym
indeksie)
Arytmetyka wskaz
ników
- zwiększenie lub zmniejszenie zmiennej wskaz
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 wskaz
ników mają zastosowanie tylko w
wypadku elementow tablic:
jeśli zmienna wskaz
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 wskaz
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
Typ pointer
Porównania można wykonywać tylko na wskaz
nikach, które pokazują na
typy niesprzeczne;
wskaz
nikiem neutralnym, nie pokazującym na żaden typ danych jest
zmienna wskaz
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.
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
type
Część
(adres
wsk =^skladnik;
składowa
następnego
(dane)
skladnik = record
skladnika)
dane: typ;
next : wsk
end;
Listy
Dostęp do listy odbywa się poprzez wskaz
nik, który zawiera adres
pierwszego elementu na liście.
Wskaz
nik ten nazywany jest poczatkiem bÄ…dz
korzeniem listy.
Każdy następny składnik listy jest dostępny poprzez składową
zawierającą adres w składniku poprzednim.
poczÄ…tek
wð
43
wð
wð wð
1 27
NIL
wð
2
Listy
type
wsk =^skladnik;
Tworzenie nowej listy:
skladnik = record
dane: typ;
next : wsk
poczatek
procedure tworz_liste;
end;
{1}
wð
var
NIL
zn : char;
{2} wsk
begin
wð ? ?
poczatek:=nil;
wsk
repeat
{3}
wð dane ?
new(wsk);
write( Podaj kolejny element listy  )
wsk
readln(wsk^.dane);
{4}
wð dane wð
wsk^.next:=pocz;
poczatek
pocz:=wsk;
wð
{5}wsk
write( czy kontynuować ?  );
NIL
wð
dane wð
readln(zn)
poczatek
until zn<> t ;
wð
end;
NIL
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) s
Stos realizuje strategiÄ™ wstawiania/pobierania
LIFO (Last In, First Out; ostatni wszedł, pierwszy wyjdzie).
Stos odwraca kolejność wstawianych elementów.
wðOperacje:
Wstawianie, pobranie, czy jest pusty, pierwszy element, inicjalizacja, usuwan
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 Nagl}
wietla element wskazywany przez W, na pocz. wyˆ
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ń czyli pierwszy węzeł zwany
korzeń
jest czasami węzłem głównym;
Węzły bez gałęzi nazywamy liśćmi.
węzeł
gałąz

W drzewie binarnym wyróżniamy
wðwð
prawą i lewą część
węzeł
liść
wðwð wðwð
NIL
liść
NIL NIL
wðwð
type
NIL NIL
wsk_w=^wezel;
wezel = record
Drzewo binarne nazywamy uporządkowanym jeżeli zawartość
dane: typ;
każdego węzła jest większa od zawartości jego lewego następnika
lewy :wsk_w;
i jednocześnie mniejsza od zawartości jego prawego następnika.
prawy :wsk_wl
Pojęcie mniejszości i większości zależy od klucza wg którego
end;
dokonywane jest sortowanie. UporzÄ…dkowane drzewo binarne
var
uzyskuje się przez odpowiednie wpisywanie nowych węzłów.
korzen, wskaz : wsk_wl
Type wsk_w=^wezel;
wezel = record
liczba: integer;
//sortowanie
lewy:wsk_w;
procedure wstaw_sort(var wezel_stary :wsk_w;
prawy:wsk_w
wstaw:integer);
end;
var
wezel_nowy : wsk_w;
begin
procedura drzewo tworzy nowy węzeł i wpisuje
if wezel_stary=nil then
go do drzewa w ustalonym porzÄ…dku co
uzyskuje się przez rekurencyjne wywołanie
begin
tej procedury. Procedura ta powinna być
new(wezel_nowy);
wywoływana po raz pierwszy
wezel_nowy^.liczba:=wstaw;
z parametrem będącym korzeniem drzewa np.:
wezel_nowy^.lewy:=nil;
wezel_mowy^.prawy:=nil;
procedure wstaw_drzewo(var korzen:wsk_w);
wezel_stary:=wezel_nowy;
var tliczba:integer;
end
begin
else
repeat
writeln( Podaj liczbÄ™ do wpisu :  );
if wstawreadln(liczba);
wstaw_sort(wezel_stary^.lewy,wstaw)
if liczba<>-1 then
else
wstaw_sort(korzen, liczba)
if wstaw>wezel_stary^.liczba then
until liczba=-1
wstaw_sort(wezel_stary^.prawy,wstaw)
end;
else writeln( Podana liczba jest już w spisie ! )
end;
Sortowanie dokonywać się będzie od
tego węzła w lewo i w prawo. Pierwszy
Program główny będzie wywoływał
węzeł umieszczony w drzewie zawsze
procedurÄ™ wpisywania danych do drzewa:
pełni rolę korzenia.
program binarne_drzewo;
Załóżmy, że wczytany będzie ciąg liczb:
uses crt;
4,6,2,9,3,1,12
type
W pierwszym wywołaniu procedury
wsk_w=^wezel;
Drzewo korzen wskazuje na nil
wezel = record
a pierwszÄ… wczytanÄ… liczbÄ… jest 4
liczba: integer;
Ponieważ wezel_stary wskazuje na nil
lewy:wsk_w;
więc zostaje wykonane:
prawy:wsk_w
new(wezel_nowy);
end;
wezel_nowy ^.liczba:=4;
var
wezel _nowy ^.lewy:=nil;
korzen:wsk_w;
wezel _nowy ^.prawy:=nil;
...
wezel_stary :=wezel_ nowy;
korzeń
begin
korzen:=nil;
4
wstaw_drzewo(korzen);
lewy prawy
wðwð
....
end. NIL NIL
Po wpisaniu drugiej wartości (2) zostaje wywołana
procedura drzewo z parametrem korzen, który korzeń
teraz nie wskazuje na nil lecz na pierwszy węzeł.
4
Zostaje więc wykonana część else instrukcji if:
lewy prawy
wðwð
else
if wstaw2 NIL
lewy prawy
wstaw_sorto(wezel_stary^.lewy,wstaw) wðwð
else
NIL NIL
if wstaw>wezel_stary^.liczba then
wstaw_sort(stary_wezel^.prawy,wstaw)
W taki sam sposób uzyskamy dopisanie
else writeln( Podana liczba jest już w spisie ! )
liczby 6 w postaci trzeciego węzła, który
Ponieważ 2<4 {wstawtym razem będzie zawieszony na prawej
następuje wywołanie
gałęzi:
wstaw_sort(wezel_stary^.lewy,wstaw)
procedura wywołuje samą siebie z lewym
korzeń
wskaz
nikiem, który wskazuje nil.
if stary_wezel=nil then
lewy 4 prawy
begin wð wð
new(wezel_nowy);
2 6
lewy prawy
wezel_nowy^.liczba:=2;
lewy prawy
wð wð wð wð
wezel_nowy^.lewy:=nil;
NIL NIL
wezel_nowy^.prawy:=nil;
NIL NIL
wezel_stary :=wezel_nowy;
end; {jest lewą gałęzią pierwszego węzła}
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
korzeń
porównanie 9 i 6.
Ponieważ 9>6 następuje wywołanie rekurencyjne, w
lewy 4 prawy
którym wezel_stary jest węzłem z elementem 6:
wð wð
wstaw_sort(wezel_stary^.prawy,wstaw)
2 6
lewy prawy
lewy prawy
Teraz wezel_stary^.prawy wskazuje na nil zatem
wð wð wð wð
wykonywana jest część then:
NIL
NIL
NIL
new(wezel_nowy);
prawy
9
lewy
wezel_ nowy ^.liczba:=9; wð wð
wezel_ nowy ^.lewy:=nil;
NIL 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ę:
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;
korzeń
lewy 4 prawy
wð wð
2 6
lewy prawy
lewy prawy
wð wð wð wð
NIL
NIL
NIL
prawy
9
Wywołanie tej procedury dla drzewa,
lewy
wð wð
które stworzyliśmy
NIL NIL
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)
Drzewo-
program binarne_drzewo;
{$APPTYPE CONSOLE}{$O-,Q+,R+}
uses SysUtils;
przykład
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 wstawwstaw_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;
begin
procedure wstaw_drzewo(var korzen:wsk_w);
korzen:=nil;
var aliczba:integer;
begin
repeat wstaw_drzewo(korzen);
writeln(' Podaj liczbÄ™ do wpisu (-1:Koniec) : ');
Wyswietl(korzen);
readln(aliczba);
usun_drzewo(korzen);
if aliczba<>-1 then
readln;
wstaw_sort(korzen, aliczba)
korzen:=nil;
until aliczba=-1
end.
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; //wskaz
nik na poczÄ…tek listy
procedure inicjuj(var Lista :TLista);
begin
Lista := nil;
end;
procedure dopisz(var Lista :TLista; D
procedure usunWszystko(var Lista :TLista
:TDane);
Var w :PElem;
Var w :PElem;
begin begin
w := Lista;
while Lista <> nil do begin
new(Lista);
w := Lista;
Lista^.Dane := D;
Lista := Lista^.Nast;
Lista^.Nast := w;
end;
dispose(w);
end; end;
procedure wypiszWszystko(Lista :TLista);
Var Lst :TLista;
Var w :PElem;
begin
begin
w := Lista;
inicjuj(Lst);
while w <> nil do
dopisz(Lst, 'pierwszy');
begin
dopisz(Lst, 'drugi');
writeln(w^.Dane);
w := w^.Nast; dopisz(Lst, '3333');
end;
wypiszWszystko(Lst);
end;
usunWszystko(Lst);
readln; end.
procedure usunWszystko(var Lista
:TLista);