Løsningsforslag 6
Fra Hiofwiki
Innhold |
[rediger]
Gruppe 118
[rediger]
Oppgave 6.1
import java.io.*;
/**
*
* @author Lars Emil
*/
public class Filesys_Queue {
public static void main(String[] args)
{
CircularQueue<File> fqueue = new CircularQueue<File>();
CircularQueue<Integer> intqueue = new CircularQueue<Integer>();
fqueue.enqueue(new File(args[0]));
intqueue.enqueue(0);
while(!fqueue.isEmpty())
{
File f = fqueue.dequeue();
int n = intqueue.dequeue().intValue();
if(f.isDirectory())
{
File[] fa = f.listFiles();
for(int i = 0; i < fa.length; i++)
{
fqueue.enqueue(fa[i]);
intqueue.enqueue(n+1);
}
}
for(int i = 0; i < n; i++)
System.out.print("\t");
System.out.println(f.getName());
}
}
}
[rediger]
Oppgave 6.2
import java.io.File;
import java.util.Stack;
/**
*
* @author Lars Emil
*/
public class StacksysQueue {
public static void main(String[] args)
{
Stack<File> fqueue = new Stack<File>();
Stack<Integer> intqueue = new Stack<Integer>();
fqueue.push(new File(args[0]));
intqueue.push(0);
while(!fqueue.isEmpty())
{
File f = fqueue.pop();
int n = intqueue.pop().intValue();
if(f.isDirectory())
{
File[] fa = f.listFiles();
for(int i = 0; i < fa.length; i++)
{
fqueue.push(fa[i]);
intqueue.push(n+1);
}
}
for(int i = 0; i < n; i++)
System.out.print("\t");
System.out.println(f.getName());
}
}
}
[rediger]
Oppgave 6.3
- Oppretter en variabel som holder på verdi
- Legger this.verdi inn i variabelen
- Kopierer this.neste.verdi til this.verdi.
- Endrer this.neste til this.neste.neste
- Returnerer variabelen
[rediger]
Oppgave 6.4
Operasjonene til en stakk er: pop, push, peek og empty.
Vi skal også ha: max
Kan for eksempel bruke ArrayList
- Har en variabel som holder på max
pop
- Bruker ArrayList sin remove og fjerner siste element i lista
push
- Sammenligner max med p, endrer max hvis p er større enn max
- Bruker ArrayList sin add metode for å legge til
peek
- Bruker ArrayList sin get
empty
- Bruker ArrayList sin isEmpty
max
- returnerer max variabelen
[rediger]
Oppgave 6.5
Har gjort den, men usikker på om det er riktig, venter med å legge det ut som løsningsforslag.
- O(n^2) med ArrayList siden remove() har O(n). O(n) med LinkedList siden remove er konstant
- Nei
[rediger]
Oppgave 6.6
//Sette inn et nytt element på en bestemt posisjon
public boolean add(E element, Integer index)
{
Node temp = start;
if(index < 0 || index > size())
{
throw new IndexOutOfBoundsException("Too bad!");
}
else
{
for(int i = 0; i < index-1; i++)
temp = temp.next;
temp.next = new Node(element, temp.next);
num++;
}
return true;
}
//Fjerne et element fra en bestemt posisjon
public E remove(int index)
{
E returnElement = null;
//Hvis lista er tom, kast unntak
if(empty())
{
throw new IndexOutOfBoundsException("The list is empty!");
}
//Sjekker om elementet er det samme som det første elementet i lista
else if(index == 0)
{
returnElement = start.value;
start = start.next;
}
else
{
Node temp = start;
for(int i = 0; i < index; i++)
temp = temp.next;
returnElement = temp.next.value;
temp.next = temp.next.next;
}
return returnElement;
}
private class LinkedIterator implements Iterator<E> {
private Node p;
private Node previous;
public LinkedIterator(){
p = start;
previous = null;
}
public boolean hasNext() {
return (p != null);
}
public E next() {
E value = p.value;
previous = p;
p = p.next;
return value;
}
public void remove() {
if(previous == null)
{
start = start.next;
p = p.next;
}
else if(p.next != null)
{
p.value = p.next.value;
p.next = p.next.next;
}
else
{
previous.next = null;
}
}
}
[rediger]
Oppgave 6.7
private class ReverseListIterator implements Iterator<E> {
private DoubleNode<E> p;
public ReverseListIterator(){
p = end;
}
public boolean hasNext() {
return (p.last != null);
}
public E next() {
E verdi = p.value;
p = p.last;
return verdi;
}
public void remove() {
if(p.next == null)
{
end = end.last;
p = p.last;
}
else if(p.last != null)
{
p.value = p.last.value;
p.last = p.last.last;
}
else
{
p.next.last = null;
}
}
class Sett6Iterator<E> extends Iterator<E>
{
private int pos;
public Sett6Iterator()
{
pos = tabell.length;
}
public boolean hasNext()
{
return (pos > 0) ? true : false;
}
public E next()
{
pos--;
// eventuelle boundary checks
return tabell[pos];
}
}
