bst.cpp

Download: bst.cpp

Pobierz

4 KB

• Zaimplementować słownik oparty na binarnym drzewie poszukiwań BST Implementacja dynamiczna (nie tablicowa), każdy węzeł drzewa posiada wyłącznie referencje do lewego i prawego potomka (rozważyć zastosowanie stosu, dla którego typem podstawowym jest referencja do węzła drzewa).
• Słownik ma umożliwić przechowywanie danych w postaci element = {klucz}. Dostęp do słownika za pomocą funkcji:
o add( element)
o element del( klucz)
o element search( klucz)
o DSW()
o inorder() f-cja pomocnicza przechodząca drzewo w porządku inorder
• W głównej pętli programu nr 1 inicjalizujemy słownik, następnie dodajemy do niego minimalnie 100 tys losowych elementów, po czym wyprowadzamy na konsolę informację o strukturze drzewa, równoważymy drzewo algorytmem DSW i ponownie wyprowadzamy na konsolę informacje o strukturze drzewa, następnie przechodzimy je w porządku inorder wyprowadzając na konsolę wartości kluczy odwiedzanych kolejno węzłów.

Komentarze:

Nie ma jeszcze żadnego komentarza. Dodaj go jako pierwszy!

Aby dodawać komentarze musisz się zalogować

Mam_Las

Idź do chomika

Inne foldery z plikami do pobrania

Programy C++

Inne pliki do pobrania z tego chomika

ambbst.cpp

• Zaimplementować słownik oparty na samoorganizującym się drzewie BST. Implementacja dynamiczna (nie tablicowa), każdy węzeł drzewa posiada referencje do lewego i prawego potomka oraz węzła rodzicielskiego. • Drzewo powinno wykorzystywać strategię modyfikacji struktury drzewa po wyszukaniu węzła o określonej wartości klucza AMB (Allena, Munro, Bitnera – węzeł o wartości klucza będącej argumentem operacji wstawienia lub wyszukania jest na drodze kolejnych rotacji promowany do poziomu korzenia – operacja splay). • Słownik ma umożliwić przechowywanie danych w postaci element = {klucz}. Dostęp do słownika za pomocą funkcji: o add( element) o element del( klucz) o element search( klucz) o inorder() f-cja pomocnicza przechodząca drzewo w porządku inorder • W głównej pętli programu nr 1 inicjalizujemy słownik, następnie dodajemy do niego minimalnie 100 tys. losowych elementów (po każdym wstawieniu dokonując modyfikacji struktury zgodnie ze wskazaną strategią), po czym wyprowadzamy na konsolę informację o strukturze drzewa, następnie przechodzimy je w porządku inorder wyprowadzając na konsolę wartości kluczy odwiedzanych kolejno węzłów.

kopiec.cpp

• Zaimplementować kopiec minimaksowy (ang. minmax heap). • Kopiec ma umożliwić przechowywanie danych w postaci element = {klucz}. Jako typ danych dla klucza przyjąć integer. Dostęp do kopca za pomocą funkcji: o add(klucz) o element delmin(klucz) – usunięcie węzła o najmniejszej wartości klucza o element delmax(klucz) – usunięcie węzła o największej wartości klucza • W głównej pętli programu inicjalizujemy kopiec, następnie dodajemy do niego minimalnie 10 tys losowych elementów, po czym na przemian usuwamy elementy najmniejszy i największy wyprowadzając informację o wartości klucza usuwanego węzła na konsolę. Proces usuwania węzłów ma trwać aż do całkowitego opróżnienia kopca.

skiplista.cpp

• Zaimplementować słownik oparty na liście z przeskokami (ang. skip list). Implementacja dynamiczna, wykorzystująca strażników (stałe elementy: najmniejszy i największy). Maksymalna liczba poziomów kolejki wynosi 10 (poziom 0 kompletny, poziom 9 najrzadszy). Prawdopodobieństwo pojawienia się nowo dodanego elementu na kolejnym poziomie pod warunkiem występowania na poziomie aktualnym wynosi 0,25. • Słownik ma umożliwić przechowywanie danych w postaci element = {klucz}. Jako typ danych dla klucza przyjąć integer. Dostęp do słownika za pomocą funkcji: o add(klucz) o element del(klucz) o element search(klucz) o show(level) f-cja pomocnicza - wyświetlenie elementów na wybranym poziomie o count() f-cja pomocnicza - wyświetlenie liczby elementów na wszystkich poziomach od 0 do 9 • W głównej pętli programu inicjalizujemy słownik, następnie dodajemy do niego minimalnie 10 tys losowych elementów, po czym wyświetlamy zawartość poziomu 8 i 9.

listacykliczna.cpp

• Zaimplementować jednokierunkową listę cykliczną. Pojedyncze elementy listy zawierają wskaźnik na element kolejny oraz klucz będący łańcuchem znaków (o zmiennej długości). Lista jest identyfikowana przez wskaźnik na pierwszy element, nie przetrzymujemy wskaźnika na element ostatni ani ilości elementów w liście. Porządkowanie listy według klucza zgodnie ze wskazaniami prowadzącego. • Dostęp do listy za pomocą funkcji: o find( klucz) o insert( klucz) o delete( klucz) Nie dopuszczamy elementów o tych samych kluczach. Funkcje insert i delete powinny wykorzystywać funkcję find. • W głównej pętli programu inicjalizujemy pustą listę, następnie dodajemy do niej minimalnie 10 tysięcy elementów losowych oraz kilka o ustalonych kluczach (insert), wyszukujemy elementy o losowych kluczach oraz o kluczach znanych (find) po czym wykonujemy próbę usunięcia elementów z kluczami losowymi* oraz znanymi. * brak

więcej plików z tego folderu...