Dodawanie/usuwanie zakresów liczb do/z tablicy

0

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ę

0
zlt napisał(a)

Mam do zrobienia zadanie na zaliczenie

+1 do szczerości :)

zlt napisał(a)

bardzo prosiłbym kogoś o pomoc, bo sam zachodzę w głowę i nic nie mogę wymyślić

Od takich próśb jest dział "Praca". Mogę jednak pomóc Ci bo w porównaniu z ostatnimi tematami tego typu ładnie poprosiłeś, a nie rozkazałeś napisanie komuś programu i to trzeba zacząć chwalić bo chamstwa jednak przybywa :), a więc z mojej strony:
spróbuj zacząć pisać to zadanie sam, jeśli masz konkretny problem to w tedy wal na forum z tym co już masz, pokaż chęci i zaangażowanie, a nie szukaj frajera, który odpali Ci program za free :)
pozdrawiam

0

chcialem napisac Ci pare wskazowek, ale wskazowki w takiej formie szybciej mi sie napisalo..

typedef std::pair<long, long> przedzial;    // te cztery linie ustalaja owe, tutejsze nazwy - zebys nie musial potem myslec
typedef std::list<przedzial> zbiorprzedzialow;     // nad tym ze jest to jakies estede,  i jakies konstyteretor, tylko po prostu tego uzywal
typedef zbiorprzedzialow::const_iterator chodzik;
typedef zbiorprzedzialow::iterator chodzik2;       // tak na wszelki wypadek, jedna z metod listy --mooze- go wymaga

// stad w dol - przykladowe funkcje, ktore robia to co w zadaniu jest wymagane
// rzeczy wymagajace znajomosci std::list/iteratorow sa juz napisane
// zostalo Ci zrozumienie i dopsanie po 2-3-linijki

przedzial pobierz(std::istream& input)
{
    przedzial tmp;
    ......uzupelnij
    return tmp;
}

void wypisz(std::ostream& output, przedzial const & p)
{
    output << ......uzupelnij
}

bool czyWystepuje(przedzial const & p, zbiorprzedzialow const & baza)
{
    for(chodzik it = baza.begin(); it != baza.end(); ++ it)
    {
         przedzial const & aktualny = *it;
         bool trafiony = .......uzupelnij;
         if(trafiony)
             return true;
    }
    ......uzupelnij
}

void dodaj(przedzial const & p, zbiorprzedzialow & baza)
{
     if( ...tutaj wykorzystaj poprzednia funkcje )
          .....uzupelnij
     else
     {
          baza.   ..uzupelnij.. (p);
          ....uzupelnij
     }
}

przedzial znajdz(long punkt, zbiorprzedzialow const & baza)
{
    for(chodzik it = baza.begin(); it != baza.end(); ++ it)
    {
         przedzial const & aktualny = *it;
         bool trafiony = .......uzupelnij;
         if(trafiony)
             return *aktualny;
    }
    ......uzupelnij-wymysl rozwiazanie
}

void usun(przedzial const & p, zbiorprzedzialow & baza)
{
    for(chodzik it = baza.begin(); it != baza.end(); ++ it)   // tutaj byc moze bedziesz musial zamienic 'chodzik' na 'chodzik2'
    {
         przedzial const & aktualny = *it;
         bool trafiony = .......uzupelnij;
         if(trafiony)
         {
             baza.erase(aktualny);
             return;
         }
    }
}

// a to juz napisz wedle swojego widziCisię
int main()
{
    . ..... uzupelnij
}

Osobom chetnym do pomocy sugeruje pozostawienie pominietych czesci jako cwiczenie dla autora

1 użytkowników online, w tym zalogowanych: 0, gości: 1