6. AP 2 Praktikum

Die Aufgabenblätter sind hier zu finden: http://www.gm.fh-koeln.de/~ehses/ap/index.html

Aufgabe 1:

Node.java:

package search.util;

public class Node {
public Object value;
public Node next;

Node (Object value, Node next) {
this.value = value;
this.next = next;
}
}

ConcatenateList.java:

package search.util;

import java.util.Comparator;
public class ConcatenateList {
private Node first = null;

 public boolean isEmpty() {
return first == null;
}

public Object removeFirst() {
Object retValue = first.value;
first = first.next;

return retValue;
}

 public void addLast(Object o) {
Node newNode = new Node(o, null);

 if (first == null) {
first = newNode;
}
else {
   Node temp = first;
 while (temp.next != null) {
    temp = temp.next;
} 
temp.next = newNode;
}
 }

public void clear() {
first = null;
}

public void add(Object o, Comparator cmp) {
if ( isEmpty() ) {
first = new Node(o, null);
 }
else {
Node temp = first;
Node temp_prev = null;

 while ( temp != null && cmp.compare(o, temp.value) > 0 ) {
temp_prev = temp;
temp = temp.next;
}

 if (temp == null) {
    temp_prev.next = new Node (o, null);
 }
else if (temp == first){
first = new Node (o, temp);
 }
else{
    temp_prev.next = new Node (o, temp);
}
 }
 }

public Object removeLast() {

Node temp = first;
Node temp_prev = null;

while (temp.next != null) {
   temp_prev = temp;
temp = temp.next;
}

 if (temp == first) {
   first = null;
return temp.value;
  }
else {
   temp_prev.next = null;
return temp.value;
 }
 }
}

FIFOQueue.java:

package search.util;

import java.util.NoSuchElementException;

public final class FIFOQueue implements IQueue {

private ConcatenateList snake = new ConcatenateList();

 public void clear() {
snake.clear();
}
 public Object get() {
 if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
return snake.removeFirst();
}
 public boolean isEmpty() {
return snake.isEmpty();
}
public void put(Object p) {
snake.addLast(p);
}

}

LIFOQueue.java:

package search.util;

import java.util.NoSuchElementException;

public final class LIFOQueue implements IQueue {

private ConcatenateList stack = new ConcatenateList();

 public void clear() {
stack.clear();
}
 public Object get() {
  if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
return stack.removeLast();
}
 public boolean isEmpty() {
return stack.isEmpty();
}
 public void put(Object p) {
stack.addLast(p);
}

}

PriorityQueue.java:

package search.util;

import java.util.Comparator;
import java.util.NoSuchElementException;

public final class PriorityQueue implements IQueue {

private ConcatenateList prio = new ConcatenateList();

private Comparator cmp;

 public PriorityQueue(Comparator cmp) {
this.cmp = cmp;
}

 public void clear() {
prio.clear();
}
public Object get() {
 if (this.isEmpty()) throw new NoSuchElementException(“Queue is empty”);
return prio.removeFirst();
}
 public boolean isEmpty() {
return prio.isEmpty();
}
 public void put(Object p) {
prio.add(p, this.cmp);
}
}

Aufgabe 3:

numberOfNodes():

public static int numberOfNodes(ITreeNode root) {
 if(root==null){
      return 0;
 }
else{
int countNodes = 1;
  for (Iterator iter = root.getChildren().iterator(); iter.hasNext();) {
ITreeNode child = (ITreeNode) iter.next();
countNodes += numberOfNodes(child);
}
return countNodes;
 }
}

Aufgabe 4:

getPathToGoal():

public static List getPathToGoal(ITreeNode root, Object goalNode) {
List pathList = null;

 if (root == null) {
      return pathList;
 }

 if (goalNode.equals(root.getValue())) {
pathList = new ArrayList();
pathList.add(goalNode.toString());
return pathList;
 }

for (Iterator iter = root.getChildren().iterator(); iter.hasNext();) {
            ITreeNode child = (ITreeNode) iter.next();
pathList = getPathToGoal(child, goalNode);
if (pathList != null) {
             pathList.add(0, root.getValue().toString());
return pathList;
}
}

return pathList;
}