Algorytmy i złożoność cz IV

[ Pobierz całość w formacie PDF ]
51
10. Lista liniowa dwukierunkowa
Jest to lista zþoŇona z elementw, z ktrych kaŇdy posiada,
oprcz wskaŅnika na element nastħpny, rwnieŇ wskaŅnik na
element poprzedni.
Zdefiniujmy element listy dwukierunkowej
struct ELEMD
{ int klucz;
ELEMD * left, * right;
};
name
p
7
2
4
Rys. 35 Lista liniowa dwukierunkowa
Lista liniowa dwukierunkowa nie ma wyrŇnionego
poczĢtku ani koıca Î jest symetryczna. Rolħ wskaŅnika do
caþej listy peþni tutaj wskaŅnik , ktrego poþoŇenie jest w
zasadzie dowolne, moŇe wiħc byę uŇywany, na przykþad, do
wyszukiwania elementw.
Z powyŇszego wynika rwnieŇ, Ňe algorytmy usuwajĢce
elementy powinny sprawdzaÄ™, czy usuwany element nie jest
aktualnie wskazywany przez wskaŅnik do caþej listy. JeĻli tak,
wskaŅnik do caþej listy naleŇy wczeĻniej przesunĢę na inny
element.
52
ELEMD *q = new ELEMD;
p
left
right = q;
q
left = p
left;
p
left = q;
q
right = p;
Rys. 36 Przykþadowy algorytm wstawiania nowego
elementu, wskazywanego przez q, przed element
wskazywany przez p (zaþoŇono, Ňe element stojĢcy
na lewo od p istnieje)
p
left
right = p
right;
p
right
left = p
left;
delete p;
Rys. 37 Przykþadowy algorytm usuwania elementu
wskazywanego przez p (przy zaþoŇeniu, Ňe element
usuwany nie jest elementem skrajnie prawym, ani
skrajnie lewym)
Drzewa i lasy
11. Rekurencyjna definicja drzewa
, podobnie jak omawiana w rozdziale poprzednim
lista, jest strukturĢ, ktrĢ moŇemy zdefiniowaę w sposb
rekurencyjny.
53
Oto ta definicja:
Niech wierzchoþek w (element drzewa) bħdzie pewnego
typu T, wtedy:
1. JeŇeli dowolna, skoıczona, rozþĢczna i nie naleŇĢca do
drzewa liczba wierzchoþkw typu T, do niego
dowiĢzanych jest drzewami, to w jest drzewem.
2. Zbir pusty wierzchoþkw jest drzewem.
Jest to typowa definicja rekurencyjna, w ktrej punkt 2
stanowi warunek stopu definicji.
Pojħcie () i () zostaþy
zapoŇyczone z teorii grafw. PoniŇszy rysunek objaĻnia
podanĢ definicjħ.
root
root
w
a) b)
w
1
w
2
w
n
w
11
w
12
w
13
. . .
Rys. 38 Rekurencyjna definicja drzewa: a) drzewo puste,
b) drzewo niepuste.
54
Definicje podstawowych pojħę
1. Wierzchoþki, ktre sĢ bezpoĻrednio dowiĢzane do
danego wierzchoþka, nazywamy jego
, albo bezpoĻrednimi nastħpnikami (s
).
3. Synw tego samego ojca nazywamy braęmi.
4. Wierzchoþek, ktry nie ma bezpoĻredniego poprzednika
nazywamy . Korzeniem drzewa
nazywa siħ teŇ wskazanie do tego elementu. Jest to
jednoczeĻnie wskazanie do caþego drzewa.
6. Elementy nie bħdĢce liĻęmi nazywamy
drzewa.
7. nazywamy drzewo, w
ktrym dla kaŇdego wħzþa wewnħtrznego na jego
synach okreĻlona jest ta sama relacja liniowego
porzĢdku.
8. JeŇeli dany i, to wszystkie jego
bezpoĻrednie nastħpniki majĢ poziom i+1. ZaþoŇymy,
Ňe korzeı drzewa ma poziom 1.
2. Z kolei Î wierzchoþek taki nazywaę bħdziemy
() tych wħzþw.
5. Wierzchoþki, ktre nie majĢ bezpoĻrednich
nastħpnikw, nazywamy .
55
9. Maksymalny poziom wierzchoþkw drzewa nazywamy
s albo .
11. jest ciĢg jego wierzchoþkw
a
1
, a
2
, . . . ,a
n
taki, Ňe dla kaŇdego i = 2, 3, . . . , n para
(a
i-1
, a
i
) jest , þĢczĢcĢ dany wierzchoþek
wewnħtrzny z jego bezpoĻrednim potomkiem.
to zbir wszystkich
wierzchoþkw drzewa za wyjĢtkiem liĻci.
12. Liczba krawħdzi, jakĢ trzeba przejĻę od korzenia do
poziomu danego wierzchoþka w nazywamy
w. DþugoĻę drogi korzenia
wynosi 1. Oglnie - dþugoĻę drogi wierzchoþka na
poziomie i wynosi i.
13. s nazywaę bħdziemy uporzĢdkowany zbir
drzew. UporzĢdkowanie drzew w lesie polega na
uporzĢdkowaniu korzeni kolejnych drzew. Spina siħ je
w las poprzez umieszczenie wskaÅ…nikw do ich korzeni
w tablicy, lub w liĻcie wskaŅnikw.
12. Drzewo binarne
W praktyce uŇywa siħ zwykle drzew niewysokiego stopnia,
na przykþad drugiego (mwimy wtedy o ).
10. nazywamy maksymalnĢ liczbħ
wierzchoþkw, jakie moŇna dowiĢzaę do kaŇdego z
wħzþw.
Lista liniowa jednokierunkowa jest szczeglnym przypadkiem
drzewa. Jest to drzewo stopnia pierwszego.
[ Pobierz całość w formacie PDF ]