Oppgavesett 6
Løsningsforslag legges på wikisidene av gruppene: 1, 3, N, 1112, 118, i, X og 14
Oppgave 1
Lag et program som tar en katalog i filsystemet som kommandolinjeargument, og som gjør bruk av en kø til å lage en nivå-ordnet utskrift av alle underkataloger og filer til denne katalogen.
Oppgave 2
Endre programmet fra oppgave 1 slik at det istedenfor en kø benytter en stakk.
Oppgave 3
Anta at vi har en referanse til en node i en enkelt-lenket liste, og at dette ikke er den siste noden i listen. Vi har ikke referanser til noen andre noder i listen (bortesett fra neste-referansene).
Beskriv en algoritme med arbeidsmengde O(1) som logisk fjerner verdien som er lagret i denne noden samtidig som listens egenskaper bevares.
Oppgave 4
Beskriv hvordan du kan implementere en datastruktur som har operasjonene til en stakk, samt en operasjon max som returnerer det største elementet. Alle operasjonene skal ha arbeidsmengde O(1).
Oppgave 5
Metoden fjernHalvparten fjerner første halvdel av listen som sendes med som parameter:
public static void fjernHalvparten(List<Integer> liste){
int h = liste.size()/2;
for (int i=0; i<h; i++)
liste.remove(0);
}
- Arbeidsmengde i O-notasjon når metoden kalles med henholdvsvis en ArrayList og en LinkedList som parameter? Begrunn svarene.
- Kan bruk av en iterator gjøre metoden raskere for en eller begge listetypene?
Oppgave 6
Utvid lenket-liste-implementasjonen fra oppgavesett 3 med metoder for å
- Sette inn et nytt element på en bestemt posisjon (indeks).
- Fjerne et element fra en bestemt posisjon
- Returnere en iterator med remove-metode.
Oppgave 7
Implementer en "baklengs-iterator" for en tabell-implementasjon av en liste. Iteratoren skal initialiseres til siste element i listen, og hvert kall til next flytter iteratoren ett hakk nærmere starten på listen.
