Aisd W11

Algorytmy i struktury danych Temat: Zastosowania struktur liniowych

Zastosowania struktur liniowych

■ ■ ■

Kolejki Tablice rzadkie Tablice rozproszone

Algorytmy i struktury danych, wykład 4

2

Przykłady liniowych struktur danych ■

■

Definicja listy stanowi podstawę dla zdefiniowania struktury liniowej. Wszystkie przypadki struktur liniowych można zdefiniować bazując na ich odpowiednich reprezentacjach listowych Przykłady liniowych struktur danych: ◆ kolejki, ◆ stosy, ◆ napisy, ◆ tablice sekwencyjne ◆ tablice rzadkie ◆ tablice rozproszone (z haszowaniem).

Algorytmy i struktury danych, wykład 4

3

Kolejki Kolejka (queue) jest strukturą danych wykorzystywaną najczęściej jako bufor przechowujący dane określonych typów. ■ Organizacje kolejek: ◆ FIFO (First In First Out) - pierwszy element wchodzący staje się pierwszym wychodzącym ◆ Round-Robin - cykliczna kolejka z dyscypliną czasu obsługi komunikatu przechowywanego w kolejce (w systemach operacyjnych, sieciach komputerowych) ◆ LIFO (Last In First Out) - ostatni wchodzący staje się pierwszym wychodzącym (stos) ◆ kolejki priorytetowe - dodatkowo w standardowym mechanizmie kolejki uwzględnia się wartości priorytetów przechowywanych danych Algorytmy i struktury danych, wykład 4 ■

4

Kolejki FIFO ■

Dyscyplina First In First Out:

We

d1

Wy

We

d2 d1

Wy

d2

Wy

We Algorytmy i struktury danych, wykład 4

d6

d5

d4

d3

d1

5

Stos (kolejka LIFO) ■

Dyscyplina Last In First Out:

We Wy We Wy We Wy Algorytmy i struktury danych, wykład 4

d1

d2

d1

d6

d5

d4

d3

d2

d1 6

Realizacje liniowych struktur danych  Realizacje sekwencyjne - wtedy, gdy z góry znamy maksymalny rozmiar przetwarzanej struktury liniowej i z góry chcemy zarezerwować dla niej określony zasób (pamięć operacyjna, pamięć zewnętrzna. W czasie wytwarzania programów komputerowych bazujemy wtedy na zmiennych statycznych,  Realizacje łącznikowe - wtedy, gdy rozmiar struktury nie jest z góry znany i w czasie jej przetwarzania może istnieć konieczność dodawania do niej nowych elementów lub ich usuwania. W czasie wytwarzania programów komputerowych bazujemy wtedy na zmiennych dynamicznych (wskaźnikowych),  Realizacje łącznikowo-sekwencyjne - połączenie obu powyższych metod - wtedy gdy konieczny jest odpowiedni balans pomiędzy zmiennymi statycznymi i dynamicznymi Algorytmy i struktury danych, wykład 4

7

Implementacja stosu (kolejki LIFO) We Wy

d6

d5

d4

d3

d2

d1



W praktyce wykorzystuje się wiele różnych implementacji stosu, np.  realizacja tablicowa,  realizacja dynamiczna (wskaźnikowa), np. z użyciem list  Typowe operacje na stosie:  clear() – wyczyszczenie stosu  isEmpty() – sprawdzenie, czy stos jest pusty  isFull() – sprawdzenie, czy stos jest pełny  push(wart) – włożenie na stos wartości wart  pop() – zdjęcie ze stosu ostatniego elementu  top() – odczytanie (bez zdejmowania) ostatniego elementu Algorytmy i struktury danych, wykład 4

8

Tablicowa realizacja stosu (kolejki LIFO) #define rozmiar 100 static TypElmStosu stos[rozmiar]; static int ses =−1;

int isFull(void) { // sprawdzenie, czy stos jest pełny return ses == rozmiar − 1; } int isEmptyl(void) { // sprawdzenie, czy stos jest pusty return ses == − 1; } void clear(void) { // wyczyszczenie stosu ses == − 1; }

Algorytmy i struktury danych, wykład 4

9

Tablicowa realizacja stosu (kolejki LIFO) void push(TypElmStosu elm) { // włożenie na stos elementu elm if(!isFull()){ ses += 1; stos[ses] = elm; } else printf("\nNie mozna dodac elementu. Stos jest pelny!"); } TypElmStosu pop(void) { // zdjęcie ze stosu ostatniego elementu if(!isEmpty()) ses -= 1; else printf("\nNie mozna zdjac elementu. Stos jest pusty!"); } TypElmStosu top(void) { // odczytanie ostatniego elementu if(!isEmpty()) return stos[ses]; else printf("\nNie mozna odczytac wartosci elementu szczytowego. Stos jest pusty!"); } Algorytmy i struktury danych, wykład 4

10

Listowa realizacja stosu (kolejki LIFO)     

Stos wygodnie jest implementować za pomocą jednokierunkowej listy niecyklicznej Korzeń listy wskazuje na element szczytowy Włożenie nowego elementu na stos realizowane jest poprzez dodanie go na początek listy Zdjęcie elementu ze stosu polega na usunięciu pierwszego elementu listy Stos nie ma wówczas ograniczenia liczby elementów

Algorytmy i struktury danych, wykład 4

11

Listowa realizacja stosu (kolejki LIFO) static TypElmStosu stos[rozmiar]; struct ElmStosu { TypElmStosu wartosc; struct ElmStosu *next;}; static ElmStosu *stos; int isEmptyl(void) { // sprawdzenie, czy stos jest pusty return stos==NULL; } void clear(void) { // wyczyszczenie (usunięcie) stosu while (!isEmpty()) pop(); }

Algorytmy i struktury danych, wykład 4

12

Listowa realizacja stosu (kolejki LIFO) void push(TypElmStosu wart) { // włożenie na stos wartości wart ElmStosu *new new=malloc(sizeof(ElmStosu)); if(new != NULL){ new->wartosc=wart; new->next=stos; stos=new; } else printf("\nNie mozna dodac elementu. Brak pamieci!"); } void pop(void) { // zdjęcie ze stosu elementu szczytowego ElmStosu *first; if(!isEmpty()) { first = stos; stos=first->next; free(first); else printf("\nNie mozna zdjac elementu. Stos jest pusty!"); } Algorytmy i struktury danych, wykład 4

13

Listowa realizacja stosu (kolejki LIFO) TypElmStosu top(void) { // odczytanie (bez zdejmowania) ostatniego elementu if(!isEmpty()) return stos->wartosc; else printf("\nNie mozna odczytac wartosci elementu szczytowego. Stos jest pusty!"); }

Algorytmy i struktury danych, wykład 4

14

Implementacja kolejki FIFO We

d6

d5

d4

d3

d2

d1

Wy



W praktyce wykorzystuje się wiele różnych implementacji kolejki FIFO, np.  realizacja tablicowa  realizacja dynamiczna (wskaźnikowa), np. z użyciem list  Typowe operacje na kolejce:  clear() – wyczyszczenie (usunięcie) kolejki  isEmpty() – sprawdzenie, czy kolejka jest pusta  isFull() – sprawdzenie, czy stos jest pełny  enqueue(wart) – wstawienie do kolejki wartości wart  dequeue() – usunięcie z kolejki pierwszego elementu  first() – odczytanie (bez usuwania) pierwszego elementu Algorytmy i struktury danych, wykład 4

15

Tablicowa implementacja kolejki FIFO   

Kolejka FIFO jest trudniejsza w implementacji niż stos W implementacji tablicowej często stosuje się tzw. tablicę cykliczną Wymagane są dwa wskaźniki:  head – wskazuje na początek kolejki  tail – wskazuje na koniec kolejki H

0 head=3, tail=7 Po dodaniu wartości: R, T, S head=3, tail=0 Po usunięciu wartości D head=4, tail=0

T

S T

S

Algorytmy i struktury danych, wykład 4

1

2

T

3

4

5

6

7

8

9

D

A

C

F

G

A

C

F

G

R

T

C

F

G

R

T

H

D

H

A

16

Tablicowa implementacja kolejki FIFO 

Wstawienie elementu do kolejki zwiększa tail o 1



Usunięcie elementu z kolejki zwiększa head o 1



W tablicy cyklicznej może być problem z określeniem, czy kolejka jest pusta czy pełna

Kolejka pełna head=3, tail=2

T

H

0

1

2

3

4

5

6

7

8

9

S

Y

Z

D

A

C

F

G

R

T

Po usunięciu dziewięciu wartości:

head=2, tail=2

H

T

Z T

H

Po usunięciu kolejnej wartości:

head=3, tail=2 Algorytmy i struktury danych, wykład 4

17

Tablicowa implementacja kolejki FIFO

Możliwe rozwiązania: 

wprowadzenie nowej zmiennej, która przechowuje liczbę elementów w kolejce



użycie tablicy o jedną pozycję dłuższej niż liczba elementów kolejki T

Kolejka pełna head=3, tail=1

0

1

Y

Z

Po usunięciu dziewięciu wartości:

head=1, tail=1

H

H

2

3

4

5

6

7

8

9

10

D

A

C

F

G

R

T

S

T

Z T

H

Po usunięciu kolejnej wartości:

head=2, tail=1 Algorytmy i struktury danych, wykład 4

18

Tablicowa implementacja kolejki FIFO 

Kolejka jest pusta, gdy spełniony jest warunek: (tail+1)%RozmiarKolejki==head



Kolejka jest pełna, gdy gdy spełniony jest warunek: (tail+2)%RozmiarKolejki==head T

Kolejka pełna head=3, tail=1

0

1

Y

Z

Po usunięciu dziewięciu wartości:

head=1, tail=1

H

H

2

3

4

5

6

7

8

9

10

D

A

C

F

G

R

T

S

T

Z T

H

Po usunięciu kolejnej wartości:

head=2, tail=1 Algorytmy i struktury danych, wykład 4

19

Listowa realizacja stosu (kolejki LIFO) #define RozmiarKolejki 100 //maksymalna liczba wartości w kolejce #define RozmiarTablicy (RozmiarKolejki+1) static TypElmKolejki kolejka[RozmiarTablicy]; static int head=1; static int tail=0; int isFull(void) { // sprawdzenie, czy kolejka jest pełna return (tail+2)% RozmiarTablicy ==head; } int isEmptyl(void) { // sprawdzenie, czy kolejka jest pusta return (head+1)% RozmiarTablicy ==head; } void clear(void) { // wyczyszczenie (usunięcie) kolejki head=1; tail=0; Algorytmy i struktury danych, wykład 4 }

20

Tablicowa realizacja stosu (kolejki LIFO) void enqueue(TypElmKolejki wart) { if(!isFull()){ tail=(tail+1)% RozmiarTablicy; kolejka[tail]=wart; } else printf("\nNie mozna dodac wartosci. Kolejka jest pelna!"); } void dequeue(void) { if(!isEmpty()) head=(head+1)% RozmiarTablicy; else printf("\nNie mozna pobrac wartosci. Kolejka jest pusta!"); } TypElmKolejki first(void) { if(!isEmpty()) return kolejka[head]; else printf("\nNie mozna pobrac wartosci. Kolejka jest pusta!"); } Algorytmy i struktury danych, wykład 4

21

Kolejka priorytetowa





Implementacja kolejek priorytetowych jest trudniejsza niż „zwykłych” kolejek (o kolejności pobierania elementów z kolejki decyduje ich priorytet); Zasad ustalania priorytetów może być wiele;

Algorytmy i struktury danych, wykład 4

22

Kolejka priorytetowa Przykładowe możliwości implementacji kolejki priorytetowej:  za pomocą listy uporządkowanej wg kluczy (złożoność wstawiania elementu do kolejki wynosi O(1), pobieranie ma złożoność O(n));  za pomocą listy uporządkowanej wg priorytetów (złożoność wstawiania elementu do kolejki wynosi O(n), pobieranie ma złożoność O(1));  za pomocą dwóch list: krótkiej uporządkowanej wg priorytetów i listy nieuporządkowanej pozostałych elementów; liczba elementów na liście krótkiej zależy od tzw. priorytetu progowego (złożoność wstawiania elementu do kolejki wynosi O( n ) , pobieranie ma złożoność O(1));  za pomocą kopca (złożoność operacji wstawiania/pobierania elementu do/z kolejki wynosi O(lg n);

Algorytmy i struktury danych, wykład 4

23

Kopiec jako kolejka priorytetowa   

Kopiec może być podstawą bardzo efektywnej implementacji kolejki priorytetowej; Aby wstawić element do kolejki dodaje się go na koniec jako ostatni liść (należy wówczas najczęściej odtworzyć własność kopca); Pobieranie elementu z kolejki polega na pobraniu wartości z korzenia; na jego miejsce przesuwany jest ostatni liść (najczęściej trzeba potem odtworzyć własność kopca);

Algorytmy i struktury danych, wykład 4

24

Kopiec jako kolejka priorytetowa Idea algorytmu wstawiania elementu do kolejki: WstawDoKolejki_Kopca(elm) wstaw elm na koniec kopca; while (elm nie jest korzeniem && elm > poprzednik(elm)) zamień miejscami elm i poprzednik(elm);

Algorytmy i struktury danych, wykład 4

25

Kopiec jako kolejka priorytetowa Idea algorytmu wstawiania elementu do kolejki-kopca 25

18

20 17

19

9

10

Należy dodać do kolejki wartość 22 7

14

Algorytmy i struktury danych, wykład 4

16

22

26

Kopiec jako kolejka priorytetowa Przywracanie własności kopca 25

18

20 17

7

19

14

Algorytmy i struktury danych, wykład 4

16

9

10

22

27

Kopiec jako kolejka priorytetowa Kopiec z dodanym elementem 25

18

22 17

7

20

14

Algorytmy i struktury danych, wykład 4

16

9

10

19

28

Kopiec jako kolejka priorytetowa Idea algorytmu pobierania elementu z kolejki: PobierzZKolejki_Kopca() pobierz element z korzenia; wstaw do korzenia element z ostatniego liścia; usuń ostatni liść; // lewe i prawe poddrzewo są kopcami p=korzeń; while (p nie jest liściem && p < którykolwiek następnik(p)) zamień miejscami p i większy następnik(p));

Ostatnie trzy wiersze algorytmu to przywracanie drzewu własności kopca (realizuje to funkcja MoveDown)

Algorytmy i struktury danych, wykład 4

29

Kopiec jako kolejka priorytetowa Idea algorytmu pobierania elementu z kolejki 25

18

22 17

7

20

14

Algorytmy i struktury danych, wykład 4

16

9

10

19

30

Kopiec jako kolejka priorytetowa Zastąpienie korzenia ostatnim liściem 19

18

22 17

7

20

14

Algorytmy i struktury danych, wykład 4

9

10

16

31

Kopiec jako kolejka priorytetowa Przywrócenie własności kopca 19

18

22 17

7

20

14

Algorytmy i struktury danych, wykład 4

9

10

16

32

Kopiec jako kolejka priorytetowa Kolejka z usuniętym elementem o najwyższym priorytecie 22

18

20 17

7

19

14

Algorytmy i struktury danych, wykład 4

9

10

16

33

Algorytmy i struktury danych Temat: Tablice rzadkie

Tablice sekwencyjne  W praktyce programowania najczęściej spotykamy się z tablicami: ◆ jednowymiarowymi (wektory), ◆ dwuwymiarowymi (macierze) ◆ trójwymiarowymi (kostki, prostopadłościany)  Bardzo często używa się pojęcia tablica dla określenia implementacji macierzy  Liczna grupa metod numerycznych wykorzystuje pojęcie tablicy (ciągu, sekwencji liczb)

Algorytmy i struktury danych, wykład 4

35

Tablice rzadkie

 Tablica rzadka – tablica, w której wykorzystany jest jedynie niewielki procent komórek („marnotrawstwo” pamięci); w takim przypadku tablicę lepiej zastąpić zestawem list  Tablice rzadkie w implementacji listowej przechowują jedynie tzw. wartości niezerowe, ponieważ komórka tablicy z wartością zerową nie występuje (brak pozycji na liście oznacza wartość zerową)

Algorytmy i struktury danych, wykład 4

36

Tablice rzadkie Przykład – ewidencja ocen studentów w centrum kursowym nr studenta 1

2

3

4

5

...

7 999

8 000

1 2

5

4

3

3

3

nr kursu

4

3

5

5

4

...

299

4

4

300

Algorytmy i struktury danych, wykład 4

37

Tablice rzadkie Przykład – ewidencja ocen studentów w centrum kursowym Wykorzystanie pamięci przykładowej tablicy rzadkiej: ■ Liczba studentów: 8000 ■ Liczba kursów: 300 ■ Maksymalna liczba kursów, w których może uczestniczyć student: 4 ■ ■

■

Liczba komórek tablicy: 8000 x 300=2 400 000 np. bajtów Maksymalna liczba komórek tablicy zajętych na oceny: 4 x 8000=32 000 Wykorzystanie pamięci w tablicy: 32 000 / 2 400 000 = 0,013 =1 %

Algorytmy i struktury danych, wykład 4

38

Tablice rzadkie Przykład – implementacja listowa (zestaw list) nr studenta 1

1 2

nr kursu

2

3

4

5

1

3

5

2

2

2

5

4

3

...

7999

8000

3 4 5

1

2

...

4

4

3

5

300

Algorytmy i struktury danych, wykład 4

39

Tablice rzadkie ■

Przykład realizacji tablic rzadkich (lista dwupoziomowa):

Pocz

1

2

3

17

1 2

5.00

3.24

5 2.01

7 0.01

Algorytmy i struktury danych, wykład 4

5 7.04

40

Tablice rzadkie

■

■

Tablice rzadkie mogą być wykorzystywane do implementacji macierzy koincydencji wierzchołków w grafach Innym zastosowaniem tablic rzadkich jest przechowywanie obrazów rastrowych (szczególnie wtedy, gdy na obrazie jest mało „zapalonych” punktów)

Algorytmy i struktury danych, wykład 4

41

Algorytmy i struktury danych Temat: Tablice rozproszone

Definicja tablicy rozproszonej (z haszowaniem) ■

Tablicą rozproszoną nazywamy trójkę uporządkowaną

T = K, D, h gdzie K = {k1, k2, k3,..., kn} - zbiór kluczy, D = {d1, d2, d3,..., dn} - zbiór adresów, h - funkcja mieszająca (haszująca):

h:K → D Tradycyjnym obszarem zastosowań tablic rozproszonych są zagadnienia związane z przetwarzaniem danych. Algorytmy i struktury danych, wykład 4

43

Tablice rozproszone, funkcja haszująca ■

■

■

■

Zadaniem funkcji haszującej h jest w miarę równomierne obciążanie tablicy rozproszonej. Zagadnienie definiowania funkcji mieszającej jest istotne dla efektywności obliczeń realizowanych na bazie tablic rozproszonych. Ma to szczególnie duże znaczenie dla tablic rozproszonych przetwarzanych bezpośrednio w nośnikach zewnętrznych (taśmach, dyskach) Na ogół nie można wykluczyć powstawania tzw. konfliktów w tablicach rozproszonych.

Algorytmy i struktury danych, wykład 4

44

Konflikty w tablicach rozproszonych ■

Kolizją (konfliktem) w tablicy rozproszonej nazywamy sytuację powstałą wtedy, gdy:

∃ ki ,k j ∈ K , ki ≠ k j

■

h( k i ) = h( k j )

Klucze ki, kj biorące udział w kolizji nazywamy synonimami

Algorytmy i struktury danych, wykład 4

45

Metody haszowania w tablicach rozproszonych 1. Metoda dzielenia ◆ adres w tablicy wyliczany jest według formuły: h(K) = K mod RozmiarTablicy lub h(K) = wartość(K) mod RozmiarTablicy h(K) - adres w tablicy rozproszonej wartość(K) - wartość funkcji wyliczona na podstawie klucza RozmiarTablicy = sizeof(tablica) ◆

w zastosowaniach praktycznych metoda ta jest bardzo efektywna

Algorytmy i struktury danych, wykład 4

46

Metody haszowania w tablicach rozproszonych, cd. 2. Metoda składania (z tzw. składaniem z przesuwaniem) K 21

O W A L 25 33 11 22

S K I 29 21 19

- klucz - kody

znaków

29 21

21

19

25 33 11 22 składania 21 25 00

■

29

21

- sposób 19

h(KOWALSKI) = 292119 + 331122 + 212500 = 835741

Algorytmy i struktury danych, wykład 4

47

Metody haszowania w tablicach rozproszonych, cd. 3. Metoda składania (z tzw. składaniem brzegów) sposób składania 1

■

2

3

4

5

1

2

3

6

5

4

7

8

9

1 566

h(123456789) = 1566

Algorytmy i struktury danych, wykład 4

6

7

8

9 Schemat składania:

- wyliczony adres

48

Metody haszowania w tablicach rozproszonych 4. Metoda kwadratu środka K 21

O W A 25 33 11

L 22

S 29

K 21

I - klucz 19 - kody

znaków

11

22

- wycięty

środek

1258884

- kwadrat

wyciętej liczby

h(KOWALSKI)=588 588 Algorytmy i struktury danych, wykład 4

- wyliczony adres 49

Metody haszowania w tablicach rozproszonych, cd. Przykłady zastosowania metody dzielenia (tablica ma 1000 pozycji): ◆ niech h(KOWALSKI)= 913 913 mod 1000 = 913 ◆ niech h(KOWALSKI) = 834741 834741 mod 1000 = 741 ◆ niech h(123456789) = 1566 1566 mod 1000 = 566

Algorytmy i struktury danych, wykład 4

50

Organizacja tablic rozproszonych Problemy kolizji mogą być rozwiązywane dwiema metodami: ◆

Tablice rozproszone bez obszaru nadmiarowego dane znajdują się wyłącznie w obszarze bazowym tablicy

◆

Tablice rozproszone z obszarami nadmiarowymi: ✦ ✦

z listami synonimów rozproszone tablice indeksowe

Algorytmy i struktury danych, wykład 4

51

Usuwanie konfliktów w tablicach rozproszonych Bez obszarów nadmiarowych – adresowanie otwarte ■

■

jeśli wyznaczony klucz koliduje z innym kluczem, znajdowana jest w tablica inna, dostępna komórka stosuje się tutaj technikę próbkowania (aż do znalezienia wolnej komórki): h1(K)=[(h(K)+p(1)] mod R h2(K)=[h(K)+p(2)] mod R, ... hi(K)=[h(K)+p(i)] mod R, gdzie p(i) jest tzw. funkcją próbkującą a R jest rozmiarem tablicy (liczba komórek)

Algorytmy i struktury danych, wykład 4

52

Usuwanie konfliktów w tablicach rozproszonych, cd. Bez obszarów nadmiarowych – próbkowanie liniowe ◆

funkcja próbkująca ma postać:

p(i)=i ◆

wówczas:

h1(K)=[h(K)+i] mod R ◆

wada: tendencje do „grupowania” zajętych komórek w tablicy (wówczas można stosować tzw. próbkowanie kwadratowe p(i)=i2 )

Algorytmy i struktury danych, wykład 4

53

Usuwanie konfliktów w tablicach rozproszonych, cd. Z wykorzystaniem obszarów nadmiarowych ◆

lista synomimów: pierwsze wstawienie do wolnego miejsca w obszarze bazowym. Kiedy wyliczona funkcją haszującą pozycja z obszaru bazowego jest zajęta, to wstawiamy nowy element do listy synonimów przypisanych do tej pozycji w obszarze bazowym. Listy synonimów tworzą obszary nadmiarowe

◆

rozproszona tablica indeksowa - wszystkie dane są wstawiane do obszaru nadmiarowego

Algorytmy i struktury danych, wykład 4

54

Organizacja tablic rozproszonych, przykład Przykład rozproszonej tablicy indeksowej

0 1 / 2

wart 1

wart 2

wart

wart

p-1

wart

Obszar bazowy Algorytmy i struktury danych, wykład 4

wart3

Obszar nadmiarowy 55

Algorytmy i struktury danych, wykład 4

56