Pseudokody do wyk ladu 4

17 marzec 2011

Tablicowa implementacja stosu

Stos zawieraja

,

cy nie wie

,

cej ni˙z n element´

ow mo˙zna zaimplementowa´

c

w tablicy S[1..n], z kt´

ora

,

jest zwia

,

zany atrybut top[S], kt´

orego

warto´

s´

c jest indeksem ostatnio wstawionego elementu

Stos sk lada sie

,

z element´

ow S[1..top[S]], gdzie S[1] jest elementem

na dnie stosu , a S[top[S]] jest elementem na wierzcho lku stosu

Je˙zeli 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 ,,przepe lnienie”
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´

ow z wierzcho lka stosu S (lub opr´

o˙zniania

go je´

sli na stosie by lo mniej ni˙z k element´

ow)

MULTIPOP (S, k)

while not STACK-EMPTY(S) and k

̸= 0

do POP(S)

k

← k − 1

Tablicowa implementacja kolejki

Kolejke

,

o co najwy˙zej n

− 1 elementach mo˙zna zaimplementowa´c

za pomoca

,

tablicy Q[1..n].

Atrybuty:

head[Q] – wskazuje na pocza

,

tek kolejki

tail[Q] – wyznacza wolna

,

pozycje

,

, na kt´

ora

,

mo˙zna wstawi´

c

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´

srednim

naste

,

pnikiem pozycji o numerze n.

Je´

sli head[Q] = tail[Q], to kolejka jest pusta

Je´

sli head[Q] = tail[Q] + 1, to kolejka jest pe lna

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˙zdy element listy jest rekordem sk ladaja

,

cym sie

,

z trzech p´

ol:

key – zawiera klucz elementu

next – dla danego elementu x na li´

scie next[x] wskazuje

na jego naste

,

pnik na li´

scie

prev – dla danego elementu x na li´

scie prev[x] wskazuje

na jego poprzednik

Je˙zeli prev[x] = N IL, to x nie ma poprzednika – pierwszy element
listy (x jest g lowa

,

listy)

Je˙zeli next[x] = N IL, to x nie ma naste

,

pnika – ostatni element

listy (x jest ogonem listy)

Atrybut head[L] wskazuje na pierwszy element listy L.

Je˙zeli

head[L] = N IL, to lista jest pusta

Wyszukiwanie na listach z dowia

,

zaniami

Procedura LIST-SEARCH wyznacza pierwszy element o kluczu k
na li´

scie L. W wyniku wywo lania otrzymujemy wska´

znik do tego

elementu, a je´

sli nie ma na li´

scie ˙zadnego elementu o kluczu k to

zwracana jest warto´

s´

c NIL

LIST-SEARCH (L, k)

x

← head[L]

while (x

̸= NIL) and (key[x] ̸= k)

do x

← next[x]

return x

4

Wstawianie do listy z dowia

,

zaniami

Procedura LIST-INSERT przy la

,

cza element x (kt´

orego pole key

zosta lo wcze´

sniej zainicjowane) na pocza

,

tek listy

LIST-INSERT (L, x)

next[x]

← head[L]

if head[L]

̸= NIL

then prev[head[L]]

← x

head[L]

← x

prev[x]

← NIL

Usuwanie z listy z dowia

,

zaniami

Procedura LIST-DELETE powoduje usunie

,

cie elementu x z listy.

Do LIST-DELETE zostaje przekazany wska´

znik do elementu x,

po czym element ten zostaje ,,usunie

,

ty” z listy przez modyfikacje

,

warto´

sci odpowiednich wska´

znik´

ow.

LIST-DELETE (L, x)

if prev[x]

̸= NIL

then next[prev[x]]

← next[x]

else head[L]

← next[x]

if next[x]

̸= NIL

then prev[next[x]]

← prev[x]

W celu usunie

,

cia elementu o zadanej warto´

sci klucza nale˙zy naj-

pierw wywo la´

c procedure

,

LIST-SEARCH, aby wyznaczy´

c wska´

znik

do takiego elementu.

Wartownik

Z lista

,

L zwia

,

zany jest element nil[L], kt´

ory odgrywa role

,

sta lej

NIL, ale jest rekordem o takich samych polach jak wszystkie
elementy listy.

5

Element nil[L] wstawiamy pomie

,

dzy g lowe

,

a ogon. Zatem

next[nil[L]]

wskazuje na g lowe

,

listy (nie musimy pamie

,

ta´

c atrybutu head[L]),

a

prev[nil[L]]

wskazuje na ogon listy.

Lista pusta sk lada 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)

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]