Dynamiczne struktury danych.pdf

14.4. Dynamiczne struktury danych

Do dynamicznych struktur danych zaliczamy listy, stosy, kolejki

otaz dtzewa binarne.

Lista jest to cig zmiennych dyrramicznych powiqzanych wskaza-

niami. Jedna zmienna wskazuje na drug4 dziki polu typu wskani-

kowego, ktre jest skadnikiem zmiennej dynamicznej. Element listy

(zmienn dynamiczn) bdziemy nazywali wzem. Na rys. 14.7 jest

przedstawiona lista prosta, w ktrej cig wskaza jest poprowadzony

tylko w jedny.rn kierunku. Natomiast na rys. 14.8 jest pokazana lista

dwukierunkowa, w ktrej cig wskaza jest poprowadzony w dwch

kierunkach.

prerwszy

ostatni

+ nil

nastepny

dane

Rys. 14.7. Lista jednokiemnkowa

prerwszy

ostatni

< +

poprzedni

nastepny

dane

+ nil

Rys. 14.8. Lista dwukierunkowa

Stos jest struktur, w ktrej nowe elementy kadzie si na wierz-

choku stosu i pobiera elementy tyiko z jego wierzchoka. Stos wyko-

rzystywany w programowaniu moemy porwna na przykad do

stosu monet, w ktrym monety kadzie si na wierzchoek i pobiera

rwnie z niego (nie ma innej moliwoci wzicia monety bez ich

rozs5ryania). Stos najwygodniej jest zreafizowa przy pomocy listy

jednokierunkowej. Taka realizacja stosu jest przedstawiona na rys.

L4.9.

-+ [n..t"pnyl .. ni|

t--Tane I

nastepny

dane

Rys. 14.9. Stos

Kolejka jest struktur4 analo$czn do zwykej kolejki pod skle-

pem. Nadchodzqce elementy kadzie si na koniec kolejki a pobiera z

poczqtku. Podobnie jak stos kolejk najwygodniej jest zreafizowa

przy pomocy listy jednokierunkowej.

Drzewa binarne sq strukturq danych umoliwiaj4cq bardzo szyb.

ki dostp do danej informacji. Kady z elementw tej struktury

moe zawiera wskazania na dwa inne elementy: Iewy i prawy.

Kazdy z yc}. elementw moe zawieta wskazania na nastpne dwa,

tak ie w rezultacie mona powiedzie, e kazdy z elementw drzewa

moe zawiera wskazania na dwa inne poddrzewa. Pierwszy element

drzewa nazywamy korzeniem. Drzewo binarne jest zaprezentowane

na rys. 14.10.

Rys. 14.10. Przykad drzewa binarnego

Obecnie zilustrujemy tworzenie dynamicznych struktur danych i

wykonywanie podstawowych operacji na przykadzie stosu. Znacznie

bardziej szczegowy opis programowania dynamicznych struktur

danych zawiera praca [13J.

Wierzchoek stosu pokazanego na rys. I4.9 oznaczymy ptzy

ostatni

pomocy wskanika o nazwie pierwszy, Dane ze stosu mog4 by pobra-

ne tylko za porednictwem tego wskanika jak rwnie dane mog4

by kadzione na stos wyqcznie z wykorzystaniem tego wskaka.

Wzami stosu bdq rekordy zawierajce wskazanie na element

nastpny stosu oraz dane' Danymi w naszJrm przypadku bd4 naz-

wisko, imi oraz adres.

W celu zaprogTamowania stosu musimy najpierw zadeklarowa

typ wskanikowy, ktry nazwiemy wsk_wezel wskazujqcy na rekord

typu rekordowego wezel. Niezbdne deklaracje s4 podane poniej.

tyPe

wsk wezel- : ^wezel;

Pole nastepny jest wskanikiem typu wsk-wezel wskazuj4cym na

nastpny element stosu.

Pierwsz4 procedur, ktr4 zaprojektujemy, bdzie procedura

dodawania nowego elementu na wierzchoek stosu. Wykorzystany

algorytm bazuje na nastpujcych operacjach. Naley na wspie

zapamita adres pierwszego elementu stosu na przykad we wska-

niku sory:

stary :: pierwszy;

Nastpnie trzeba utworzy nowy wze w sposb nastpujqcy:

New(pierwszy);

i ustawi wskazanie z nowego pierwszego elementu stosu na nastp-

ny element (nowy pierwszy element to pierwszy^) :

pierwszy^. nastepny :: stary;

Pozostaje nam jeszcze wczytanie danych do rekordu bd4cego pierw-

Szym elementem stosu. Zwtmy uv/ag' e ustawienie wskazania i

wezeL = record

nastepny: wsk wezel;

nazwisko,

imie,

adres : string [ 20 ]

end;

wczytywanie danych odbywa si w instrukcji zozonej, w ktrej

nazw rekordu podaje si w instrukcji with.

A oto tre procedury.

procedure Dodaj(var pierwszy: wsk wezel);

sary: wsk-wezel;

begin

{ zapamitanie wskazania na

starY :: Prerwszy;

{ utworzenie nowego wza ]

New(pierwszY) ;

with pierwszY^ do

wierzchoek stosu J

I dla rekordu wskaz1nlanego przez

pierwszY )

begin

nastePnY :: starY;

{ wczYtanie danYch }

writeln('Podaj nazwisko:' I ;

readln 1 nazwisko ) ;

writeIn( 'Podaj imi: ' 1 ;

readln( imre) ;

writeln( 'Podaj adres' ; ;

readln(adres;;

end;

Kolejn procedur bdzie procedura usuwania elementu z wietz.

choka stosu. Po pierws ze r'lalezy sprawdzi, czy stos nie jest pusty.

I.{astpnie drukujemy zawarto wza i usuwamy wze z pamici.

Przed usuniciem wza zapamitujemy wskazanie na nastpny

elementpoto'byprzypisagopniejwskanikovpierulszy.Tle

procedury jest nastpuj ca.

procedure Pobierz(var pierwszy:wsk-wezeL) ;

o".l'*..,ie elementu z wierzchoka stosu }

var w wezel: wsk wezel;

if pierwszy <> nil then t

jeIi stos nie jest pusty i

dla rekordu wskazYwanego

with pierwszY^ do {

{ dodawanie nowego elementu na wierzcho'ek stosu J

var

begin

begi write]-n (, zd) o ze stosu nastpuj acy element' ) ;

writeln(nazwisko);

writeln(adres);

writeln( imiel ;

{ zapamitanie wskazania na nastpny element

stosu ]

w_wezel :: nastepny;

{ usunicie wza }

dispose(pierwszy);

{ zmiana wierzcho.ka stosu }

prerwszy :: w wezel;

end

e]-se

writeln( ' Stos j est pusty' ; ;

end;

I ostatnia ju procedura o nazwie Dlugosc. Jej zadaniem jest

podanie Iiczby elementw Stosu. Wykorzystany algorytm polega na

przejciu ptzez wszystkie elementy stosu i zakadym razem zwik-

szaniu o jeden licznika elementw.

procedure Dlugosc ( pierwszy :wsk_wezel) ;

{ obliczenie liczby elementw stosu }

vaT

licznik := o;

w_wezel- :: pierwszy;

whi]-e w wezel<> nil_ do

begin

incllicznik);

{ przejcie do nastpnego elementu sosu }

w_wezel :: w_wezel^.nastepny;

end;

writeln( |D'ugo stosu wynosi: l,Iicznik:5)

end;

;

A oto program testowania zaprojektowanych procedur.

program stos;

przez Pj_erwszy ]

w_wezel: wsk-wezeI; { wskanik na aktualny wze' }

Iicznik: integer.. t ]-icznik elemenw stosu }

begin

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: