Repetytorium - Ćwiczenia 6

Temat: Algorytmy przeszukiwania tablic.

Podczas zajęć należy wykonać jedno zadanie, które będzie realizowało określone funkcje w sposób ustalony podczas ćwiczeń. Projekt stworzony podczas zajęć jest obowiązujący dla wszystkich, a na jego wpływ można mieć jedynie podczas zajęć.

Specyfikacja:

Należy zainmplementować tablicę w taki sposób, aby dało się na niej wykonać następujące operacje:

Sczytywanie tablicy z pliku. Dane w formacie: liczba naturalna n (liczba elementów w tablicy, 0 < n < 10000), a następnie n liczb z przedziału od 0 do 10000.
Sczytywanie tablicy z klawiatury. Dane w formacie: liczba naturalna n (liczba elementów w tablicy, 0 < n < 10000), a następnie n liczb z przedziału od 0 do 10000.
Wyszukiwanie najmniejszego elementu w tablicy.
Wyszukiwanie największego elementu w tablicy.
Wyszukiwanie indeksu najmniejszego elementu w tablicy.
Wyszukiwanie indeksu największego elementu w tablicy.
Sortowanie tablicy przez wybieranie/wstawianie (elementu najmniejszego).
Stwierdzenie, w którym miejscu znajduje się pierwsze wystąpienie ustalonego elementu.
Zliczanie elementów w tablicy

Projekt:

W ramach projektu stworzone zostaną 4 klasy:

Tablica - odpowiedzialna za przechowywanie tablicy oraz wykonywanie operacji z punktów 3-9.
iLoaderTablica - interfejs, lub klasa abstrakcyjna do tworzenia tablicy.
PlikLoaderTablica - klasa dziedzicząca z iLoaderTablica, która jest odpowiedzialna za tworzenie tablicy z pliku (pkt 1).
KlawLoaderTablica - klasa dziedzicząca z iLoaderTablica, która jest odpowiedzialna za tworzenie tablicy z danych z klawiatury (pkt 2).

W klasie Tablica mają znaleźć się następujące atrybuty:

public tablica - tablica zawierająca maksymalnie 10.000 elementów z przedziału od 0 do 10000.
public n - liczba liczb w tablicy
private czyPosortowane - informacja o tym, czy tablica jest posortowana

W klasie tablica mają znaleźć się następujące metody:

public Tablica(ILoaderTablica loader) - konstruktor, który tworzy tablicę zgodnie z odpowiednim loaderem oraz ustala liczbę elementów. Ustala również, że tablica nie jest posortowana.
public void ZliczElementy(int[] tablica) - odpowiada za realizację pkt 9. Wynik zwraca w postaci tablicy przekazywanej jako parametr.
public int Minimum() - odpowiada za realizację pkt 3. Wykorzystuje metodę IndeksMinimum.
public int Maksimum() - odpowiada za realizację pkt 4. Wykorzystuje metodę IndeksMaksimum.
public int IndeksMinimum() - odpowiada za realizację pkt 5. Wykorzystuje metodę IndeksMinimumZakres.
public int IndeksMaksimum() - odpowiada za realizację pkt 6.
public void Posortuj() - odpowiada za realizację pkt 7. Ustala parametr czyPosorotowane na prawdziwy.
public int ZnajdzPierwszyIndeksLiczby(int liczba) - odpowiada za realizację pkt 8. W przypadku posortowanej tablicy należy użyć wyszukiwania binarnego!
private int IndeksMinimumZakres(int x, int y) - wyszukuje indeks najmniejszego elementu w podtablicy od elementu x do y.
we wszystkich wymienionych metodach przed wykonaniem operacji należy sprawdzić, czy tablica jest posortowana, a jeśli jest, skorzystać z tego.
wszystkie algorytmy użyte w metodach za wyjątkiem sortowania mają być optymalne ze względu na złożoność czasową.

W klasie abstrakcyjnej iLoaderTablica mają znaleźć się następujące metody:

void WczytajDane(int[] tablicaLiczb) - metoda abstrakcyjna, bez implementacji w tym miejscu

W klasie PlikLoaderTablica mają znaleźć się następujące metody:

public void WczytajDane(int[] tablicaLiczb) - odpowiedzialna za ralizację pkt 1. Wynik zwracany jest w postaci tablicy przekazywanej jako parametr. (w niektórych językach programowania drugim zwracanym parametrem może być n - liczba liczb w tablicy

W klasie KlawLoaderTablica mają znaleźć się następujące metody:

public void WczytajDane(int[] tablicaLiczb) - odpowiedzialna za ralizację pkt 2. Wynik zwracany jest w postaci tablicy przekazywanej jako parametr. (w niektórych językach programowania drugim zwracanym parametrem może być n - liczba liczb w tablicy

Zadanie

Zaimplementuj opisany powyżej projekt oraz metody.