Witam,
Mam do zrobienia zadanie na zaliczenie, ale że jestem ciemną masą z programowania, to bardzo prosiłbym kogoś o pomoc, bo sam zachodzę w głowę i nic nie mogę wymyślić. Treść zadania wygląda następująco:
Zaprojektować strukturę danych (dowolną) służącą do przechowywania rozłącznych, domkniętych przedziałów. Program powinien udostępniać następujące funkcje:
a. Dodawanie przedziału do bazy - program informuje, ze dodał przedział, lub że nie mógł tego zrobić, bo podany przedział kolidował z pozostałymi.
b. Znajdowanie przedziału zawierającego dany punkt - podanie koców przedziału, lub informacji, że dany punkt nie należy do żadnego z nich.
c. Usuwanie przedziałów z bazy.
d. Realizacja punktów a. i b. w oczekiwanym (średnim) czasie krótszym, niż czas, jakiego można oczekiwać po liście dowiązaniowej. (Czyli czas aproksymacyjny rzędu mniejszego niż O(n), ewentualnie czas O(n) z bardzo zmniejszonym współczynnikiem)
Przykład działania
- wprowadz(2,5) -ok
- wprowadz(0,1) -ok
- wprowadz(3,4) -nie można, kolizja
- znajdz(4) - liczba 4 jest w przedziale [2,5]
- znajdz(6) - liczby 6 nie ma w przedziałach
Zależy mi na punktach a,b,c; prosiłbym o jak największą prostotę programu oraz komentarze wyjaśniające. Mam nadzieję, że znajdzie się ktoś chętny do pomocy. Z góry dziękuję