Pseudokody do wykladu 4
17 marzec 2011
Tablicowa implementacja stosu
Stos zawieraja cy nie wiecej niż n elementów można zaimplementować
w tablicy S[1..n], z która jest zwia zany atrybut top[S], którego
wartość jest indeksem ostatnio wstawionego elementu
Stos sklada sie z elementów S[1..top[S]], gdzie S[1] jest elementem
na dnie stosu , a S[top[S]] jest elementem na wierzcholku stosu
Jeżeli top[S] = 0, to stos jest pusty
STACK-EMPTY (S)
if top[S] = 0
then return true
else return false
PUSH (S, x)
top[S] �! top[S] + 1
if top[S] > n
then error ,,przepelnienie
else S[top[S]] �! x
POP (S)
if STOCK-EMPTY (S)
then error ,,niedomiar
else top[S] �! top[S] - 1
return S[top[S] + 1]
Typeset by AMS-TEX
1
2
Operacja usuwania k elementów z wierzcholka stosu S (lub opróżniania
go jeśli na stosie bylo mniej niż k elementów)
MULTIPOP (S, k)
while not STACK-EMPTY(S) and k = 0
8
do POP(S)
k �! k - 1
Tablicowa implementacja kolejki
Kolejke o co najwyżej n - 1 elementach można zaimplementować
za pomoca tablicy Q[1..n].
Atrybuty:
head[Q]  wskazuje na pocza tek kolejki
tail[Q]  wyznacza wolna pozycje, na która można wstawić
nowy element
Elementy kolejki sa na pozycjach
head[Q], head[Q] + 1, . . . , tail[Q] - 1
Tablica Q jest ,,cykliczna , tj. pozycja o numerze 1 jest bezpośrednim
nastepnikiem pozycji o numerze n.
Jeśli head[Q] = tail[Q], to kolejka jest pusta
Jeśli head[Q] = tail[Q] + 1, to kolejka jest pelna
Pocza tkowo head[Q] = tail[Q] = 1
ENQUEUE (Q, x)
Q[tail[Q]] �! x
if tail[Q] = length[Q]
then tail[Q] �! 1
else tail[Q] �! tail[Q] + 1
3
DEQUEUE (Q)
x �! Q[head[Q]]
if head[Q] = length[Q]
then head[Q] �! 1
else head[Q] �! head[Q] + 1
return x
Listy dwukierunkowe
Każdy element listy jest rekordem skladaja cym sie z trzech pól:
key  zawiera klucz elementu
next  dla danego elementu x na liście next[x] wskazuje
na jego nastepnik na liście
prev  dla danego elementu x na liście prev[x] wskazuje
na jego poprzednik
Jeżeli prev[x] = NIL, to x nie ma poprzednika  pierwszy element
listy (x jest glowa listy)
Jeżeli next[x] = NIL, to x nie ma naste pnika  ostatni element
listy (x jest ogonem listy)
Atrybut head[L] wskazuje na pierwszy element listy L. Jeżeli
head[L] = NIL, to lista jest pusta
Wyszukiwanie na listach z dowia zaniami
Procedura LIST-SEARCH wyznacza pierwszy element o kluczu k
na liście L. W wyniku wywolania otrzymujemy wskaz
nik do tego
elementu, a jeśli nie ma na liście żadnego elementu o kluczu k to
zwracana jest wartość NIL
LIST-SEARCH (L, k)
x �! head[L]
while (x = NIL) and (key[x] = k)
8 8
do x �! next[x]
return x
4
Wstawianie do listy z dowia zaniami
Procedura LIST-INSERT przyla cza element x (którego pole key
zostalo wcześniej zainicjowane) na pocza tek listy
LIST-INSERT (L, x)
next[x] �! head[L]
if head[L] = NIL
8
then prev[head[L]] �! x
head[L] �! x
prev[x] �! NIL
Usuwanie z listy z dowia zaniami
Procedura LIST-DELETE powoduje usuniecie elementu x z listy.
Do LIST-DELETE zostaje przekazany wskaz
nik do elementu x,
po czym element ten zostaje ,,usunie ty z listy przez modyfikacje
wartości odpowiednich wskaz
ników.
LIST-DELETE (L, x)
if prev[x] = NIL
8
then next[prev[x]] �! next[x]
else head[L] �! next[x]
if next[x] = NIL
8
then prev[next[x]] �! prev[x]
W celu usuniecia elementu o zadanej wartości klucza należy naj-
pierw wywolać procedure LIST-SEARCH, aby wyznaczyć wskaz
nik
do takiego elementu.
Wartownik
Z lista L zwia zany jest element nil[L], który odgrywa role stalej
NIL, ale jest rekordem o takich samych polach jak wszystkie
elementy listy.
5
Element nil[L] wstawiamy pomiedzy glowe a ogon. Zatem
next[nil[L]]
wskazuje na glowe listy (nie musimy pamietać atrybutu head[L]),
a
prev[nil[L]]
wskazuje na ogon listy.
Lista pusta sklada sie tylko z wartownika i oba pola next[nil[L]]
oraz prev[nil[L]] wskazuja na nil[L]
LIST-SEARCH" (L, k)
x �! next[nil[L]]
while (x = nil[L]) and (key[x] = k)
8 8
do x �! next[x]
return x
LIST-INSERT" (L, x)
next[x] �! next[nil[L]]
prev[next[nil[L]]] �! x
next[nil[L]] �! x
prev[x] �! nil[L]
LIST-DELETE" (L, x)
next[prev[x]] �! next[x]
prev[next[x]] �! prev[x]