Algoritmi in podatkovne strukture 1

Navodila

Napišite javanski razred LinkedSequence, ki implementira abstraktni podatkovni tip zaporedje (ang. sequence) z uporabo dvosmernega linearnega povezanega seznama brez čuvaja.

Pri rešitvi uporabite naslednje razrede in vmesnike:

class CollectionException extends Exception {
    public CollectionException(String msg) {
         super(msg);
    }
}

 interface Collection {

    static final String ERR_MSG_EMPTY = "Collection is empty.";
    // static final String ERR_MSG_FULL = "Collection is full.";
    boolean isEmpty();
    // boolean isFull();
    int count();
    String toString();
}

interface Sequence<T extends Comparable> extends Collection {
    static final String ERR_MSG_INDEX = "Wrong index in sequence.";
    T get(int i) throws CollectionException;
    T set(int i, T x) throws CollectionException;
    void insert(int i, T x) throws CollectionException;
    T delete(int i) throws CollectionException;
}

Poleg razredov in vmesnikov, ki ste jih spoznali že pri enem izmed prejšnjih izzivov, je: 

• Sequence<T extends Comparable> generični vmesnik (abstraktni podatkovni tip) za zaporedje (primerljivih) elementov, ki je posebna vrsta zbirke (ang. collection). 
  

Vmesnik Sequence lahko hrani le elemente, ki so med seboj primerljivi (objekte iz razredov, ki implementirajo vmesnik Comparable). 

V testnem razredu Izziv5 prikažite urejanje zaporedja objektov tipa Oseba z izboljšano metodo hitrega urejanja (quicksort), ki jo v ta namen ustrezno prilagodite. Izboljšava se nanaša na preklop urejanja particije z navadnim vstavljanjem, ko velikost le-te pade pod določeno mejo. Metoda naj po izvedbi izpiše število premikov in primerjav.

Dvosmerni linearni povezani seznam brez čuvaja 

Razred LinkedSequence<T extends Comparable> naj vsebuje notranji razred Node, ki predstavlja en člen enosmernega povezanega seznama elementov - ta vsebuje vrednost value (generičnega tipa T) in vrednosti next in prev - povezavi na naslednji in predhodni člen v zaporedju: 

class Node {
    T value;
    Node next, prev;
}

Seznam naj bo dosegljiv preko atributa first, ki v primeru, ko zaporedje vsebuje elemente, kaže na prvi člen v seznamu, sicer pa ima vrednost null (ker zahtevana izvedba nima čuvaja).

Ker je seznam linearen (in ne krožen), je naslednik zadnjega člena null. 

V primeru težav naj se sproži izjema tipa CollectionException, ki vsebuje tudi izjemo zaradi napačnega indeksa v zaporedju (ERR_MSG_INDEX). Ker je povezani seznam dinamična struktura, do napake zaradi napolnjene zbirke (ERR_MSG_FULL) ne more priti.

Urejanje zaporedja objektov tipa Oseba

V testnem razredu Izziv5 preverite delovanje zaporedja tako, da najprej tvorite zaporedje objektov tipa Oseba, ter ga nato uredite z izboljšano metodo hitrega urejanja (quicksort). 

Izboljšava se nanaša na uporabo navadnega vstavljanja, ki se uporabi, ko velikost particije pade pod določeno velikost. Velikost se posreduje kot parameter ob klicu metode za urejanje. 

Metoda naj med urejanjem prešteje število premikov in primerjav in ju po izvedbi izpiše.

Neobvezna alternativna rešitev: Razmislite o optimalnejši izvedbi algoritma, ki bi bolje izkoristila našo izvedbo zaporedja (recimo nadomeščanje indeksov z povezavami na objekte ...). Kje bi se nahajala takšna metoda za urejanje?  Implementirajte takšno rešitev.  

Testni razred

V testnem razredu izvedite naslednji postopek:

 Vnesi velikost zaporedja n
 Generiraj zaporedje z1, ki vsebuje n naključnih oseb (z zaporednim vrivanjem na 1. mesto) 
 Zanka:
   Prepiši zaporedje z1 v zaporedje z2
   Vnesi in nastavi atr
   Vnesi in nastavi smer
   Izpiši zaporedje z2
   Vnesi velikost v (za preklop na navadno vstavljanje)
   Uredi z2 z hitrim urejanjem za velikost preklopa v (metoda izpiše število premikov in primerjav)
   Izpiši (urejeno) zaporedje z2
   Izberi ponovitev ali konec

 Oddaja

Vse razrede oddajte na običajen način do prvega ponedeljka po novem letu, do 23.55 ure.