Krzysztof Pancerz

Algorytmy i struktury danych

Algorytmy

i

struktury danych

WYKŁAD 3

Dr inż. Krzysztof Pancerz

Krzysztof Pancerz

Algorytmy i struktury danych

Stos

●

Stos jest strukturą danych, do której dostęp jest
możliwy tylko z jednej strony

●

Zasada działania stosu określana jest regułą
“Last In First Out” (LIFO)

Krzysztof Pancerz

Algorytmy i struktury danych

Stos (cd.)

●

Operacje na stosie:

–

stack_init( ) - utworzenie pustego stosu.

–

empty( ) - sprawdzanie czy stos jest pusty.

–

push(element) – dodanie elementu na stos.

–

pop( ) - usunięcie elementu ze stosu.

–

top( ) - pobranie elementu ze stosu bez jego
usuwania.

Krzysztof Pancerz

Algorytmy i struktury danych

Stos (cd.)

●

Stos może być implementowany na różne
sposoby.

●

Jedną z możliwych implementacji jest
implementacja przy użyciu tablicy.

Przyjmujemy:

●

Tablica:

int tab[n];

n - rozmiar tablicy.

●

t – zmienna używana do indeksowania
wierzchołka stosu.

Krzysztof Pancerz

Algorytmy i struktury danych

Stos (cd.)

Krzysztof Pancerz

Algorytmy i struktury danych

Stos (cd.)

void stack_init( )
{

t=-1;

}

int empty( )
{

if(t==-1) return 1;
else return 0;

}

Krzysztof Pancerz

Algorytmy i struktury danych

Stos (cd.)

●

Przy dodawaniu elementu na stos
inkrementujemy zmienną t i umieszczamy
element w komórce o indeksie t.

●

Zakładamy, że tablica nie jest pełna.

void push(int element)
{

t=t+1;
tab[t]=element;

}

Krzysztof Pancerz

Algorytmy i struktury danych

Stos (cd.)

●

Przy usuwaniu elementu ze stosu
dekrementujemy zmienną t.

●

Zakładamy, że stos nie jest pusty.

void pop()
{

t=t-1;

}

Krzysztof Pancerz

Algorytmy i struktury danych

Stos (cd.)

●

Zakładamy, że stos nie jest pusty.

int top()
{

return tab[t];

}

Krzysztof Pancerz

Algorytmy i struktury danych

Kolejki

●

Kolejka jest strukturą danych o ograniczonym
dostępie.

●

Elementy mogą być dodawane tylko na koniec
kolejki. Elementy mogą być usuwane
(pobierane) tylko z początku kolejki.

●

Zasada działania kolejki określana jest regułą:
“First In First Out” (FIFO)

Krzysztof Pancerz

Algorytmy i struktury danych

Kolejki (cd.)

●

Operacje na kolejce:

–

queue_init( ) - utworzenie pustej kolejki.

–

empty( ) - sprawdzenie czy kolejka jest pusta.

–

enqueue(element) – dodanie elementu do
kolejki.

–

dequeue( ) - usunięcie elementu z kolejki.

–

front( ) - pobranie pierwszego elementu z
kolejki bez jego usuwania.

Krzysztof Pancerz

Algorytmy i struktury danych

Kolejki (cd.)

●

Kolejka może być implementowana na różne
sposoby.

●

Jedną z możliwych implementacji jest
implementacja przy użyciu tablicy.

Przyjmujemy:

●

Tablica:

int tab[n];

n – rozmiar tablicy.

●

r – zmienna używana do indeksowania końca
kolejki, f - zmienna używana do indeksowania
początku kolejki.

Krzysztof Pancerz

Algorytmy i struktury danych

Kolejki (cd.)

Krzysztof Pancerz

Algorytmy i struktury danych

Kolejki (cd.)

void queue_init( )
{

r=-1; f=-1;

}

int empty( )
{

if(r==-1) return 1;
else return 0;

}

Krzysztof Pancerz

Algorytmy i struktury danych

Kolejki (cd.)

void enqueue(int element)
{

if(r=-1)
{ r=0; f=0; }
else
{ r=r+1; }
tab[r]=element;

}

Krzysztof Pancerz

Algorytmy i struktury danych

Kolejki (cd.)

●

Zakładamy, że kolejka nie jest pusta.

void dequeue()
{

f=f+1;

}

Krzysztof Pancerz

Algorytmy i struktury danych

Kolejki (cd.)

●

Zakładamy, że kolejka nie jest pusta.

int front()
{

return tab[f];

}

Krzysztof Pancerz

Algorytmy i struktury danych

Listy powiązane

●

Lista powiązana jest strukturą danych z
dynamiczną alokacją pamięci.

●

Lista składa się z obiektów nazywanych
węzłami.

Krzysztof Pancerz

Algorytmy i struktury danych

Listy powiązane (cd.)

●

Każdy węzeł listy powiązanej zawiera element
oraz wskaźnik na następny węzeł. W tym
przypadku lista jest nazywana listą
jednokierunkową.

●

Pierwszy węzeł listy jest dostępny za pomocą
wskaźnika head.

●

Ostatni węzeł listy jest dostępny za pomocą
wskaźnika tail.

Krzysztof Pancerz

Algorytmy i struktury danych

Listy powiązane (cd.)

Krzysztof Pancerz

Algorytmy i struktury danych

Listy powiązane (cd.)

●

W najgorszym wypadku dostęp do elementu na
liście realizowany jest w czasie liniowym θ(n).

Krzysztof Pancerz

Algorytmy i struktury danych

Listy powiązane (cd.)

●

Wstawienie nowego elementu na liście:

Krzysztof Pancerz

Algorytmy i struktury danych

Listy powiązane (cd.)

●

Usunięcie elementu z listy:

Krzysztof Pancerz

Algorytmy i struktury danych

Listy powiązane dwukierunkowe

●

W liście powiązanej dwukierunkowej każdy
węzeł zawiera element oraz dwa wskaźniki:

–

wskaźnik na następny węzeł,

–

wskaźnik na poprzedni węzeł.

Krzysztof Pancerz

Algorytmy i struktury danych

Listy powiązane dwukierunkowe (cd.)