Dr Aleksander Klosow
PWSZ Legnica, 2003
www.strony.wp.pl/wp/klosov/
Algorytmy i Struktury Danych
Wykład 6
DYNAMICZNE STRUKTURY DANYCH
MEMORIA na temat TYPÓW DANYCH
OKREÅšLENIE TYPU DANYCH POZWALA:
1. Dokładnie wyznaczyć zakres potrzebnej pamięci
2. Jednoznacznie zinterpretować wynik wyrażenia
3. Wyznaczyć sposób wyświetlania (int, char) oraz przechowywania w pamięci (int, float)
WADY PROSTYCH TYPÓW DANYCH (int, char, real, boolean i inne)
1. Nie pozwalają na zapis obiektów o złożonej strukturze
WADY ZA
OŻONYCH TYPÓW DANYCH (tablica, rekord, zbiór)
1. Potrzeba wyznaczenia z góry rozmiar zajmowanej pamięci
2. Wymaga ciągłego obszaru w pamięci, co utrudnia przechowywanie dużych bloków danych
DYNAMICZNE STRUKTURY DANYCH - Idea
Cechy charakterystyczne:
1. Powtarzające się złożone statyczne jednostki danych (rekordy)
2. Liczba wszystkich danych nie jest z góry określona
3. Dane są łatwo dostępne
4. Dane mogą być umieszczane w dowolnym obszarze pamięci w zależności
od wolnego miejsca
5. Rekurencyjność
Dodatkowe wymagania od środowiska programowania:
1. Dynamiczny przydział pamięci
2. Typ danych przechowujący adresy w zamian wartości
RODZAJE DYNAMICZNYCH STRUKTUR DANYCH
Lista jednokierunkowa
Lista dwukierunkowa
Lista cykliczna
Stos
Kolejka FIFO
Sterta
Kolejka priorytetowa
Drzewa binarne
Drzewa zrównoważone
Drzewa wielokierunkowe
B-Drzewa
Grafy
Kopce dwumianowe
Kopce Fibonacciego
WYBRANE STRUKTURY DYNAMICZNE
- Lista jednokierunkowa
- Lista dwukierunkowa
- Stos
- Kolejka FIFO
- Drzewa binarne
ZASTOSOWANIE
- Problemy baz danych
- Problemy sztucznej inteligencji
- Analiza symboliczna wyrażeń arytmetycznych
- Wiele innych zagadnień programistycznych
LISTA JEDNOKIERUNKOWA
Struktura
type T = record struct T {
{dane;...} /* dane; ... */
nast.: ^T; T* nast.;
end }
GÅ‚owa element1 element2 element3
adres null
adres
adres
dane dane
dane
LISTA JEDNOKIERUNKOWA
Operacje
OperacjÄ™ podstawowe:
1. Dodawanie nowego elementu:
1.1. Dołączanie
1.2. Wstawianie
2. Usuwanie elementu
3. Wyszukiwanie elementu
Operacje pochodne:
4. Wymiana dwóch elementów
5. Sortowanie
6. Złączenie dwóch list
LISTA JEDNOKIERUNKOWA
Wymiana elementów
B Ô! C
A.adres = C Tmp = A.adres
B.adres = D A.adres = A.adres.adres
C.adres = B Tmp.adres = A.adres.adres
A.adres.adres = Tmp
A B C D
adres null
adres
adres
dane dane
dane
LISTY - INNE RODZAJE
" Lista uporzÄ…dkowana
" Lista cykliczna
" Lista 2-kierukowa
STOS
FILO - First In Last Out
Struktura o ograniczonym dostępie!
Operacje:
1. Odkładanie danych na wierzchołek stosu (operacja push())
2. Zdejmowanie danych z wierzchołka stosu (operacja pop())
Góra
adres
Dane1
adres
Dane2
adres
Dane3
STOS
Ćwiczenie
Ile elementów będzie zawierał stos oraz jaki element będzie na wierzchu w
wyniku wykonania następujących operacji?
Push(A);
Push(B);
Pop();
Push(C);
Push(D);
Pop();
STOS
Odpowiedz

Góra
adres
C
adres
A
KOLEJKA
FIFO - First In First Out
element1 element2 element3
adres null
adres
Ogon
dane dane
dane
GÅ‚owa
Operacje:
1. Dodawanie elementu na koniec kolejki (ogon)
2. Usuwanie elementu z początku kolejki (głowa)