Abstrakcyjne typy danych – kolejka priorytetowa



Pobieranie 0,51 Mb.
Strona1/4
Data16.04.2018
Rozmiar0,51 Mb.
  1   2   3   4

Wykład 8

Abstrakcyjne typy danych – kolejka priorytetowa




Definicja kolejki priorytetowej:
Kolejka priorytetowa to struktura danych zawierająca elementy z kluczami, która pozwala na przeprowadzanie dwóch podstawowych operacji: wstawiania nowego elementu i usuwania elementu o największej wartości (R.Sedgewick,Algorytmy w C++)

Zastosowania kolejki priorytetowej (wg R.Sedgewick,Algorytmy w C++)


  • Systemy symulacyjne, w których dane kolejki mogą odpowiadać czasom wystąpienia zdarzeń przeznaczonych do chronologicznego przetwarzania

  • Planowanie zadań w systemach komputerowych – dane kolejki mogą oznaczać priorytety wskazujące, którzy użytkownicy mają być obsługiwania w pierwszej kolejności

  • Obliczenia numeryczne, gdzie klucze mogą być wartościami błędów obliczeniowych, oznaczającymi, że największy powinien zostać obsłużony jako pierwszy

Kolejka priorytetowa

Etap 1 - Opis ADT

Nazwa typu: Kolejka elementów

Własności typu: Potrafi przechować ciąg elementów – usuwa zawsze największy element

Dostępne działania: Inicjalizacja kolejki priorytetowej

Określenie, czy kolejka priorytetowa jest pusta

Dodanie elementu do kolejki priorytetowej,

Usuwanie z kolejki priorytetowej największego elementu


Etap 2 - Budowa interfejsu

void Inicjalizacja(kolejka_p& Kolejka_P);

{ działanie: inicjuje kolejkę priorytetową



warunki wstępne: Kolejka_P jest pustą kolejką priorytetową

warunki końcowe: kolejka priorytetowa zostaje zainicjowana jako pusta}
inline int Pusty(kolejka_p Kolejka_P);

{działanie: określa, czy kolejka priorytetowa jest pusta; typ inline, bo często wywoływana



warunki wstępne: Kolejka_P jest zainicjowana,

warunki końcowe: funkcja zwraca 1, jeśli kolejka priorytetowa jest pusta, jeśli nie- 0}
int Wstaw(kolejka_p& Kolejka_P, dane Dana);

{ działanie: dodaje element w dowolny sposób do kolejki priorytetowej



warunki początkowe: Dana jest daną do wstawienia do zainicjowanej kolejki priorytetową Kolejka_P

warunki końcowe: jeśli jest to możliwe, funkcja dodaje daną Dana do kolejki priorytetową i zwraca 1, w przeciwnym wypadku 0 }
int Usun(kolejka_p& Kolejka_P);

{ działanie: usuwa największy element wstawiony do kolejki priorytetowej,



warunki początkowe: Kolejka_P jest niepustą kolejką priorytetową

warunki końcowe: usuwa element największy z kolejki priorytetowej i zwraca dane przez return. Po usuwaniu kolejka może być pusta i musi być zainicjowana}

Etap 3 - Implementacja za pomocą tablicy nieposortowanej


  1. wstawianie





  1   2   3   4


©operacji.org 2017
wyślij wiadomość

    Strona główna