Exercise index of this lecture   Alphabetic index   Course home   

Exercises
Arrays og Lister

5.1   Opgave i forlængelse af Vector eksemplet  

Denne opgave tager udgangspunkt i programmet, som viser brugen af en Vector til indsættelse af strenge i sorteret rækkefølge.

Modificer programmet således at strengene i Array'et args, som altid er parameter til hovedprogrammet main, indsættes i variablen 'store' inden de af brugeren indtastede strenge bliver indsat.

Se dernæst på det logiske udtryk, som styrer while løkken i proceduren insert:

    i < v.size() && ((String)v.elementAt(i)).compareTo(element) < 0
Studér først operator prioriteterne af '<' og '&&' og forklar hvorfor der ikke er parenteser om 'i < v.size()'. Vær dernæst sikker på at I forstår String operationen compareTo (slå den op i klassen java.lang.String).

Pt. er der ingen løsning til denne opgave

 

5.2   Opgave om associative arrays  

Denne opgave har til formål at få erfaringer med associative arrays, ala Java's HashTabel. Lav et program der på en naturlig måde associerer elementer i mængden af tekststrenge, som repræsenterer heltal, til elementer i mængden af heltal. Eksempelvis skal strengen 'en' associeres til 1, 'to' til 2, 'enogtyve' til 21, osv. Associeringen skal foretages på baggrund af indtastninger foretaget af brugeren af programmet. Brugeren af programmet angiver altså par af tekstrenge og tal, som associeres. På baggrund af de registrerede associeringer kan brugeren slå talværdien op af en given en tekstreng, som repræsenterer tallet.

Programmet skal benytte et associativt array til formålet. Konkret anbefales det at benyttet en Hashtabel, java.util.HashTable i denne opgave.

Pt. er der ingen løsning til denne opgave

 

5.3   Opgave om cirkulære lister  

Formålet med denne opgave er primært at få øvelse i at arbejde med 'pointere' (referencer) på relativt lavt niveau. En del af jer har aldrig prøvet det før. Dette er chancen... Øvelsen er dog også en god træning i objekt-orienteret programmering.

Ud fra ideerne på sliden, som er knyttet til denne opgave, ønskes en implementation af en klasse CircularList i Java. Bemærk referencen, som kommer 'udefra' går til det sidste element i den cirkulære liste. Tænk på denne reference som kommende fra objektet af typen CircularList.

Følgende udgør klient-interfacet af klassen:

    void insertFirst(Object el)
    Indsæt et nyt første-element med indhold el i den cirkulære liste.

    void insertLast(Object el)
    Indsæt et nyt sidste-element med indhold el i den cirkulære liste.

    void deleteFirst()
    Slet det første element i listen (svarende til el1 på sliden). Gør intet hvis listen er tom

    void deleteLast()
    Slet det sidste element i listen (svarende til el5 på sliden). Gør intet hvis listen er tom

    Object retrieveFirst()
    Returner det første element i listen, eller null hvis listen er tom

    Object retrieveLast()
    Returner det sidste element listen, eller null hvis listen er tom

    int size()
    Returner antallet af elementer i listen.

Det er en pointe i denne opgave at lave en løsning uden at benytte andre Java liste-klasser. Ud over at lave klassen CircularList får man brug for en klasse som repræsenterer kædeobjekterne. I er velkomne til at bruge min version af klassen Linkable .

Aftest klassen CircularList.

Estimer køretiden af operationerne i klassen CircularList. (Datalogerne: Brug ``Store O'' notation).

Hints: Det kan være en god ide at forsyne klassen CircularList med en række interne hjælpeoperationer, såsom returnering af første elements og næstsidste elements kædeobjekt. Endvidere er en operation, som tømmer listen og en operation som laver listen 'singulær' (altså bestående af netop ét element) nyttige.

 

Generated: Monday March 31, 2008, 12:08:30
on the system cs-unix