dokumentacja, C++


C++

SORTOWNIA

Sortownia (dalej zwana SRT) ma za zadanie porządkowania wprowadzonych liczb przez użytkownika w sposób dynamiczny w oparciu o drzewo czerwono-czarne oraz wyświetlenie posortowanych liczb na ekranie. Dodatkowo program powinien posiadać możliwość wczytywania liczb z pliku podanego przez użytkownika.

  1. Analiza danych wejścia/wyjścia

Użytkownik zobowiązany jest do podania z góry informacji o ilości wprowadzanych liczb lub też nazwy pliku do otwarcia. W przypadku wyboru opcji pliku do otwarcia, program wczyta w sposób dynamiczny liczby z podanego pliku. W innym wypadku użytkownik musi wprowadzić n liczb. SRT wczyta liczby do drzewa i je posortuje, wynik wyświetli nam na ekranie. Na koniec zwolni zajęte bity w pamięci.

  1. Opis algorytmu

Algorytm został napisany w oparciu o język programowania C++, został zoptymalizowany i podzielony na kilka ważniejszych etapów (nagłówek, menu, sortowanie)

Po uruchomieniu programu, wyświetla nam się menu i SRT pyta się nas czy chcemy wczytać liczby z pliku, czy też sami je wprowadzić. Do wyboru opcje `t' lub `n'. W przypadku odpowiedzi twierdzącej jesteśmy proszeni o podanie nazwy pliku do otwarcia. SRT otworzy plik i wczyta dane do drzewa. Jeżeli wprowadzona nazwa jest błędną, odpowiednio nas o tym poinformuje. Możemy również sami wprowadzać liczby. Odpowiednio wcześniej deklarujemy ile liczb chcemy wprowadzić, po czym je wypisujemy. Wprowadzone liczby są porządkowane i wynik zostaje wyświetlony na ekranie. Sercem programu jest algorytm odpowiedzialny za sortowanie, który działa następująco:

Deklarowana jest zmienna drzewa, po czym drzewo to jest inicjalizowane jako nowe. SRT zapisuje liczby do drzewa korzystając z odpowiedniej funkcji. Struktura drzewa ma w sobie zapisany wskaźnik na korzeń. Jeżeli korzeń nie wskazuje na nic (drzewo jest puste na początku) to trzeba stworzyć nowy węzeł. Wstawiamy pierwszą liczbę. Funkcje w SRT wywołują się w sposób rekurencyjny. Chcąc wstawić drugi element program porównuje go z pierwszym i jeżeli jest większy od niego, to go wstawia na prawo, jeżeli mniejszy lub równy to na lewo. Oczywiście SRT sprawdza czy kolejny węzeł już istnieje, jeżeli nie to go tworzy. Każdy węzeł posiada swój kolor. Czarny „ojciec” ma czerwone „dzieci”, czerwony ojciec czarne dzieci, korzeń jest zawsze czarny. Rekurencja działa w następujący sposób (przedstawione w sposób komiczny, aby było łatwiejsze do zaprezentowania mechanizmu działania )


„Każdy węzeł sobie tak myśli jak dostanie komunikat od innego węzła
Hej! Weź się wypisz printNode(…)”: OK., to powiem tym mniejszym
żeby się najpierw wypisali (krzyczy do lewego syna „Hej! Weź się wypisz!”), później uznaje że pora na niego „Hej! Tu jestem! Oto moja wartość: (…)!”
a później myśli … no teraz pora na starszych i mówi do prawego poddrzewa
„Hej! Weź się wypisz”. Jak już usłyszy że całe prawe poddrzewo się wywołało,
to węzłowi który mu kazał się wypisać mówi, że się wypisał, chyba że już
nikogo takiego nie ma„ - koniec rekurencji.

Podsumowując historyjkę - jak się już rekurencja skończy to się okazuje, że każdy się raz wywołał gdzie jest i to w kolejności od najmniejszego do największego.

Po wyświetleniu na ekranie posortowanych liczb, osobny algorytm czyści zajętą pamięć. Usuwa wszystkie węzły jak i całe drzewo. Koniec programu.

  1. Uwagi

Algorytm drzewa jest napisany w sposób dość okrojony. Można dodawać tylko elementy. Nie ma żadnego wyważania drzewa gdyż wymaga to dosyć skomplikowanych algorytmów.



Wyszukiwarka

Podobne podstrony:
DOKUMENTACJA OBROTU MAGAZYNOWEGO prawidł
Proces pielęgnowania Dokumentacja procesu
dokumentacja 2
Wykład 3 Dokumentacja projektowa i STWiOR
20 Rysunkowa dokumentacja techniczna
dokumentacja medyczna i prawny obowiązek jej prowadzenia
W 5 dokumentacja ZSJ
Dokumentacja pracy na kąpielisku
Dokumenty aplikacyjne CV list
Dokumentacja pracy fizjoterapeuty
Dokumentacja medyczna bloku operacyjnego
W 5 Dokumentacja operacji gospodarczych ZAZ
DOKUMENTOWANIE GEOTECHNICZNE kurs
3)kontrola dokumentˇw
Opracowanie dokumentacji powypadkowej BHP w firmie
dokument ubiegajacy sie o kredyt inwestycyjny w banku
Dokument
09 Posługiwanie się dokumentacją techniczną (2)

więcej podobnych podstron