1

1

Algorytmy i
Struktury
Danych

Wykład 2

2

2

Kolejka (FIFO – First In
First Out)



Kolejka to struktura danych, w której
element, który został wstawiony do kolejki
jako pierwszy, jako pierwszy z niej jest
wyciągnięty.



Tę strukturę można porównać do kolejki w
sklepie. Osoba, która jako pierwsza
przyjdzie do sklepu, jako pierwsza zostanie
w nim obsłużona i pierwsza wyjdzie ze
sklepu (zakładamy, że nie żyjemy w PRL).

3

3

Tak działa kolejka

4

4



Podobnie jak w przypadku stosu, możliwe są

dwa sposoby realizacji kolejki. Pierwszy w

tablicy (co ogranicza rozmiar kolejki). Drugi,

bazując na strukturze zwanej listą.

Tworzymy wskaźnik do początku kolejki, a

każdy kolejny składnik kolejny przechowuje

wskaźnik do kolejnego elementu kolejki.

Dodatkowo tworzymy wskaźnik, który

przechowuje adres końca kolejki. Elementy

do kolejki wstawiamy od początku struktury,

a zdejmujemy od końca lub na odwrót.

5



Naszą tablicę można

przedstawić w formie

pierścienia.



Dodając element do kolejki

należy pamiętać, że

wyznaczając indeks

kolejnego wolnego miejsca

w tablicy należy

zabezpieczyć się przed

wyjściem poza obszar

pamięci przypisany do

tablicy. Robimy to dzieląc

indeks kolejnego wolnego

elementu modulo przez

rozmiar tablicy.

6

Implementacja kolejki z
wykorzystaniem listy
jednokierunkowej



Druga metoda polega na wykorzystaniu listy
jednokierunkowej, nieposortowanej.



Listę taką należy minimalnie zmodyfikować
dokładając dodatkowy wskaźnik wskazujący
zawsze na ostatni element na liście.

7



Element do kolejki dodajemy na
końcu kolejki.

8

Usuwanie elementu z
kolejki:



Elementy usuwamy z początku
kolejki (listy).

9

Kod kolejki w C++ z
użyciem klasy (1/4).
Definicja klasy.

Push – dodanie elementu
Pop – zdjęcie elementu

10

Kod kolejki w
C++ z
użyciem klasy
(2/4).Push.

11

Kod kolejki w
C++ z
użyciem klasy
(3/4). Pop.

12

Kod kolejki w C++ (4/4).
Destruktor kolejki.

Działa jak uruchomiony wielokrotnie (w pętli
while) Pop, ale nie zwraca wartości.
Destruktor służy do zwolnienia całej
zaalokowanej dynamicznie pamięci (w C++
musi się tym zająć sam programista, np. w
Javie jest to zautomatyzowane).

13

Kolejka priorytetowa



Kolejka priorytetowa jest strukturą
danych, w której o zdjęciu elementu
z kolejki nie decyduje tylko
kolejność umieszczenia elementu
w kolejce, ale także priorytet.



Pierwszy zostanie obsłużony ten
element, który ma największy
priorytet.

14

Metody realizacji kolejki
priorytetowej



Możliwe są dwie metody realizacji
kolejki priorytetowej.



W pierwszym przypadku można
wykorzystać listę jednokierunkową
posortowaną – najlepiej malejąco.



Drugim sposobem implementacji
kolejki priorytetowej jest
wykorzystanie kopca.

15

Kolejka priorytetowa
wykorzystująca posortowaną
listę jednokierunkową.



Wstawianie elementu do takiej struktury

odbywa się na takich zasadach, jak zostały

opisane wcześniej (patrz dodawanie

elementu do listy posortowanej).



Jeśli nasza lista będzie posortowana

malejąco względem priorytetów to

obsługiwać będziemy zawsze jako pierwszy

element na początku listy.



Dla takiej struktury złożoność operacji

wstawiania będzie wynosić O(n), a złożoność

operacji zdejmowania O(1).

16

Kolejka priorytetowa z
wykorzystaniem kopca



Przy wstawianiu elementu do
takiej kolejki należy wykonać dwie
czynności:



1. Dodać nowy element na
pierwszej wolnej pozycji w kopcu.



2. Naprawić strukturę kopca.

17

Naprawa
kopca (przy
dokładaniu
jednego
elementu)

Porównujemy
nowowstawiony
(zielony) z ojcem i jeżeli
jest większy to
zamieniamy miejscami.
Wykonujemy tą
operację aż dojdziemy
do korzenia, lub ojciec
będzie większy od syna.

18

Kopiec



Kopiec to struktura drzewiasta posiadająca korzeń, od
którego rozchodzi się potomstwo, które przechowuje
zawsze mniejsze wartości niż ich ojciec.



Najwyżej w hierarchii kopca znajduje się korzeń, który
przechowuje element o największej wartości.



W kopcu znajdują się także elementy nie posiadające
już potomstwa. Określa się je mianem liści.

19

Sposoby implementacji
kopca

Kopiec możemy zaimplementować na dwa

sposoby.

1. Drzewo binarne (struktura dynamiczna) -

powstaje on z węzłów przechowujących
dane oraz dwa wskaźniki do potomstwa (do
lewego i prawego syna). Maksymalny
rozmiar kopca jest pseudo-nieograniczony.

2. Tablica (struktura statyczna). Maksymalny

rozmiar kopca jest ograniczony.

20

Kopiec w tablicy



Rozmiar kopca jest ograniczony maksymalnym

zadeklarowanym rozmiarem tablicy! Kopiec

n-poziomowy potrzebuje tablicy o 2

n

-1 elementów.



Jeśli implementujemy kopiec w tablicy i

indeksowanie elementów tablicy rozpoczyna się

od 1 (np. Pascal) to wtedy indeks lewego syna

obliczamy z wzoru 2i, a prawego z 2i+1,gdzie i to

indeks elementu. Natomiast indeks ojca elementu

i –tego obliczymy ze wzoru i%2 (symbol „%”

oznacza tu dzielenie całkowite).



Indeksy oblicza się nieco inaczej, gdy elementy

tablicy są indeksowane od zera (np. C/C++, C#,

Java). W tym przypadku indeks lewego syna to

2i+1, prawego 2i+2, a indeks przodka to (i-1)%2,

gdzie i to indeks aktualnego elementu.

21

Naprawa kopca



Do tworzenia kopca będzie potrzebna

umiejętność jego naprawienia. Stąd

zaczniemy nie od tworzenia

struktury, lecz od jej naprawiania.



Zakładamy, że lewy podkopiec i

prawy podkopiec są prawidłowe,

natomiast problem stanowi korzeń,

który burzy strukturę kopca (nie

przechowuje elementu

największego).

22

Z ojca i synów wybieramy element maksymalny,

i jeżeli nie jest nim ojciec to zamieniamy
elementy,
i wywołujemy naprawianie dla fragmentu kopca,
którego korzeniem znów jest niewłaściwy
element.

Jest to tzw. rekurencja: wykonujemy tą samą
operację dla kolejnych elementów (podprogram
wywołuje sam siebie).

23

... i ponownie rozpatrujemy trzy

elementy kopca, tam gdzie

poprzednio przesunęliśmy „jedynkę”.

24

Kopiec naprawiony!

25

Tworzenie kopca



Zajmiemy się sytuacją, w której mamy
w strukturze kopca (np. w tablicy)
umieszczone wartości w sposób
przypadkowy.

26



Teraz sytuacje jest nieco
trudniejsza, gdyż nie tylko element
w korzeniu jest nieprawidłowo
umieszczony, ale cały kopiec jest
„źle” skonstruowany.

27



Należy więc utworzyć cały kopiec. W tym celu

skorzystamy z podobnej do omówionej przed

chwilą metody naprawiania kopca. Wykonujemy

operacje naprawiania kopca dla podkopców

począwszy od podkopców umieszczonych

najniżej w strukturze (liście są już naprawione).

28



Naprawiamy coraz to większe kopce

poruszając się w górę struktury, aż będzie to

cały kopiec.

29



Kopiec naprawiony/utworzony!