Transcript
POLITECHNIKA KRAKOWSKA WYDZIAŁ INŻYNIERII ELEKTRYCZNEJ i KOMPUTEROWEJ Katedra Automatyki i Technik Informacyjnych
Algorytmy i Struktury Danych www.pk.edu.pl/~zk/AISD_HP.html
Wykładowca: dr inż. Zbigniew Kokosiński
[email protected]
Wykład 1: Podstawowe struktury danych 1. Tablica. 2. Lista i jej warianty: kolejka (FIFO - First In-First Out)
stos (LIFO - Last In-First Out) kolejka podwójna 3. Zbiór.
4. Graf. 5. Drzewo. 6. Kopiec. Kolejka priorytetowa. 7. Struktury, unie. 8. Abstrakcyjne typy danych.
Tablice 1
Tablice 2
Listy 1
Listy 2
Listy 3
Listy 4
Listy 5
Listy 6
Złożoność operacji na listach
Stos - implementacja
Zastosowanie stosu – notacja odwrotna polska
Notacja odwrotna polska - przykład
Kolejka - implementacja
Zbiór 1
Zbiór 2
Grafy 1
Grafy 2
Graf – reprezentacja tablicowa
Graf – reprezentacja listowa
Drzewa, kopce
Kopiec zupełny – reprezentacje Def. Kopiec zupełny jest to drzewo prawie pełne, w którym liści może brakować tylko na ostatnim poziomie i są one spójnie ułożone od lewej do prawej.
reprezentacja grafowa
reprezentacja tablicowa
Kopiec zupełny – reprezentacja tablicowa
Aby przejść z danego wierzchołka na pozycji j do jego rodzica wyznacz jego pozycję i ze wzoru : 1) i =j/2 , gdy j jest parzyste, lub 2) i =⌊j/2⌋ , gdy j jest nieparzyste (⌊ ⌋ oznacza zaokrąglenie do najbliższej liczby całkowitej w dół) Aby przejść z danego wierzchołka na pozycji j do jego dwojga dzieci wyznacz ich pozycje k i l ze wzorów : 3) k =2j , i 4) l =2j+1 .
Kopiec zupełny – operacje 1
Dodanie nowego wierzchołka P do kopca zupełnego (wierzchołek P umieszczamy jako ostatni element i przywracamy własność kopca)
Kopiec zupełny – operacje 2
Zastąpienie elementu maksymalnego X przez element C (w miejsce X umieszczamy element C i przywracamy własność kopca)
Kopiec zupełny – operacje 3
Usunięcie elementu maksymalnego T z kopca zupełnego (w miejsce T umieszczamy element ostatni M i przywracamy własność kopca)
Budowa kopca – metoda top-down
Litery tworzące napis A SORTING EXAMPLE dodajemy kolejno do pustego kopca dbając o zachowanie własności kopca.
Budowa kopca – metoda bottom-up
Litery tworzące napis A S O R T I N G E X A M P L E umieszczamy na kolejnych poziomach drzewa binarnego, a następnie przywracamy własność kopca od dołu.
Sortowanie przez kopcowanie
Sortowanie przez kopcowanie w porządku nierosnącym polega na usuwaniu kolejnych elementów maksymalnych z korzenia kopca, przywracaniu własności kopca i umieszczaniu usuniętych elementów na zwolnionych w ten sposób pozycjach drzewa binarnego. Litery tworzące napis A SORTING EXAMPLE odczytujemy posortowane na kolejnych poziomach drzewa.
Struktura
Unia
Źródła rysunków : 1. Banachowski L., Diks K., Rytter W. : Algorytmy i struktury danych, WNT 1996 2. Sedgewick R. : Algorithms in C, Addison-Wesley 1990
