1 Algorytmy i Struktury Danych Struktury DanychWykład 2 Prowadzący: dr Paweł Drozda
2 Plan Wykładu Tablice Stosy Kolejki Listy Drzewa dr Paweł Drozda
3 Struktury danych – po co?porządkowanie informacji na komputerach w formie zrozumiałej dla człowieka pomocne narzędzie przy rozwiązywaniu skomplikowanych problemów algorytmicznych listy – ułatwiają tworzenie elastycznych baz danych drzewa binarne – ułatwiają analizę wyrażeń arytmetycznych grafy – duże zastosowanie w dziedzinie sztucznej inteligencji dr Paweł Drozda
4 Tablice (1) Najprostsza struktura danychKontener zawierający N elementów typu T Dostęp do elementów przy pomocy indeksu (pozycji) Operacje USTAW(τ, x, p) – w tablicy τ wstaw element x na pozycji p POBIERZ(τ, p) – z tablicy τ odczytaj element na pozycji p USUŃ(τ, p) – z tablicy τ usuń element na pozycji p Przykład: tablica liczb całkowitych indeks 1 2 3 4 5 6 7 8 9 11 13 17 19 23 element tablicy o indeksie 2, zawierający wartość 3 dr Paweł Drozda
5 Tablice (2) Tworzenie tablicy w C++ Dostęp do elementówT nazwa[const rozmiar]; int tab[100]; char znaki[] = {‘x’, ’y’, ’z’}; Dostęp do elementów indeksy: 0,…,N-1 tab[0] = 1; int x = tab[i]; Rozmiar tablicy musi być znany a priori (tablica statyczna) dr Paweł Drozda
6 Tablica – przykład void usun (int tab, int p) {#include
7 Tablice wielowymiaroweDeklaracja tablicy wielowymiarowej T tab[N1] [N2]…[Nk] można zapisać N1 *N2*…*Nk elementów w tablicy Przykład int tab[2][2][2]; tab[][][]={{1,2,3},{-1,4,3},{5,6,7},{7,6,5},{2,2,2}} Dostęp do elementów poprzez indeksy n1 n2…nk Przykład – tablica dwuwymiarowa (macierz) tab[0][0]=1 tab[1][2]=5 #include
8 Stos Każdy element składa się z dwóch pól: Dodatkowy element:dostęp tylko od wierzchołka zasada działania tzw. LIFO (Last In First Out) Dostępne dwie podstawowe funkcje: PUSH(S,X) – umieszczenie elementu na stosie POP(S) – zdjęcie elementu ze stosu Każdy element składa się z dwóch pól: dane – dowolna zmienna wskaźnik - zawiera informacje o miejscu przechowania kolejnego elementu na stosie Dodatkowy element: Top – przechowuje wskaźnik do szczytu stosu Dodatkowe funkcje stosu: przepełnienie - dla stosu o zadeklarowanej max wielkości stos pusty – sprawdza czy stos nie jest pusty dane3 wskaźnik Top dane2 wskaźnik ogniwo dane1 wskaźnik … dr Paweł Drozda
9 Przykład – użycie stosupush(S,1) push(S,5) 3 5 1 PUSTO push(S,3) pop(S) -> 3 top(S) -> 5 pop(S) ->5 S dr Paweł Drozda
10 Implementacja stosu - wskaźnikivoid push (int x) { ELEMENT *q = new ELEMENT; if (top==NULL) q->wartosc=x; top=q; } else{ q-> wartosc =x; q-> next=top; dr Paweł Drozda
11 Stos jako tablica 1 2 3 4 5 6 7 12 START, Wielkość stosu 6 top[S]=4 1PUSH(S,4), PUSH(S,5) PUSH(S,7) – przepełnienie!! top[S]=6 1 2 3 4 5 6 7 12 POP(S), POP(S), POP(S) top[S]=3 dr Paweł Drozda
12 Stos jako tablica - implementacjaint Pusty(S){ if (top(S)==0) return true; else return false; } void Push(S,x){ top(S)=top(S)+1; S[top(S)]=x; Pop(S){ If Pusty(S) error „nie ma co zdjac”; else { top(S)--; return S[top(S)+1];} dr Paweł Drozda
13 Kolejka Zasada działania – FIFO (First In First Out)Podstawowe funkcje: ENQUEUE(Q,x) – dodanie elementu x do kolejki DEQUEUE(Q) – zdjęcie elementu z kolejki Struktura elementu: wartość elementu wskaźnik do elementu następnego w kolejce Elementy dodatkowe Head – przechowuje wskaźnik do początku kolejki Tail – przechowuje wskaźnik do końca kolejki head tail dane1 wskaźnik dane2 wskaźnik dane3 wskaźnik dr Paweł Drozda
14 Przykład – użycie kolejkiEnqueue(Q,2) Enqueue(Q,5) Enqueue(Q,3) DEQUEUE(Q) HEAD(Q) -> 5 Dequeue(Q) 2 5 3 dr Paweł Drozda
15 Implementacja kolejkivoid dequeue(Q){ if (head!=NULL) head=head->next; else error „nic nie ma w kolejce”; } void enqueue(Q, x){ ELEMENT *q= new ELEMENT; q->wartosc=x; tail->next=q; tail=q; dr Paweł Drozda
16 Kolejka za pomocą tablicy1 2 3 4 5 6 7 12 START Head(Q)=4, Tail(Q)=7 1 2 3 4 5 6 7 14 12 ENQUEUE(Q,4), ENQUEUE(Q,1) Tail(Q)=2, Head(Q)=4 1 2 3 4 5 6 7 14 DEQUEUE(Q), DEQUEUE(Q) Tail(Q)=2, Head(Q)=6 dr Paweł Drozda
17 Kolejka – implementacja tablicyvoid dequeue(Q){ x = Q[head(Q)]; If (head(Q)= length(Q)) head(Q)=1; else head(Q)++; return x; } void enqueue(Q,x){ if (tail(Q))==lenght(Q)) tail(Q)=1; else tail(Q)++; Q[tail(Q)]=x; dr Paweł Drozda
18 Problem Jak za pomocą dwóch kolejek stworzyć stos?Jak za pomocą dwóch stosów stworzyć kolejkę? Kolejka 2 2 5 Kolejka 1 2 5 3 dr Paweł Drozda
19 Listy (1) Struktura danych z elementami ułożonymi w liniowym porządku – porządek ustalony przez wskaźniki Element złożony: lista jednokierunkowa: wartość i wskaźnik lista dwukierunkowa wartość, dwa wskaźniki head tail Lista jednokierunkowa wartość następny wartość następny wartość NULL dr Paweł Drozda
20 Listy (2) Podstawowe funkcjeSearch(L, x) – znajduje wskaźnik do elementu o kluczu x, bądź NULL gdy nie ma elementu z kluczem x Insert (L, x, w) – wstawia element o kluczu x w miejscu wskazywanym przez w Delete (L,w) – usuwa element wskazywany przez w Min(L) – zwraca element o najmniejszym kluczu Max(L) – zwraca element o największym kluczu head tail Lista dwukierunkowa wartość prev | next wartość prev | next wartość prev | next dr Paweł Drozda
21 Tworzenie listy Head(L) Tail(L) Tail(L) / 3 5 6 7 / Insert(L,3,Head)Delete(L,Tail) Insert(L,5,Tail) Insert(L,6,Tail) Insert(L,3,Tail) Search(L,5) dr Paweł Drozda
22 Lista jednokierunkowaDodanie elementu pomiędzy dwa istniejące wartość następny wartość następny wartość NULL wartość następny dr Paweł Drozda
23 Listy - implementacja Search (L,x){ temp=head(L); while ((temp->next!=null) &&(temp->wartosc!=x)) temp=temp->next; return temp; } Insert(L,x){ // na koniec listy ELEMENT q = new ELEMENT; tail->next=q; tail=q; q->wartosc=x; dr Paweł Drozda
24 Listy - własności Liniowe uporządkowanie elementów Elastycznośćwstawianie / usuwanie na dowolnej pozycji dynamiczna długość Brak bezpośredniego dostępu do i-go elementu (O(n)) Dodatkowy koszt pamięciowy (wskaźniki)
25 Drzewa binarne (1) Węzeł reprezentowany za pomocą rekordów klucz węzławskaźnik do ojca wskaźnik do lewego syna wskaźnik do prawego syna parent klucz left right parent klucz left right parent klucz left right parent klucz left right parent klucz left right parent klucz left right parent klucz left right dr Paweł Drozda
26 Drzewo binarne (2) Oznaczeniaroot(T) – wierzchołek korzenia – gdy wskaźnik parent wskazuje na NULL leaf(T) – wierzchołek liścia – gdy wskaźniki left i right wskazują na NULL dr Paweł Drozda