Algorytmy
i
struktury danych
WYKA
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 wskaz
nik na następny węzeł. W tym
przypadku lista jest nazywana listą
jednokierunkową.

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

Ostatni węzeł listy jest dostępny za pomocą
wskaz
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 wskaz
niki:

wskaz
nik na następny węzeł,

wskaz
nik na poprzedni węzeł.
Krzysztof Pancerz
Algorytmy i struktury danych
Listy powiązane dwukierunkowe (cd.)
Krzysztof Pancerz
Algorytmy i struktury danych