Material‎ > ‎

Beispiele für Datentypen

Hier finden Sie den Quellcode des MiniCollection Beispiels aus der Vorlesung, zusammen mit den gezeigten Unit-Test Klassen. Um die Tests zu kompilieren brauchen Sie das JUnit Test Framework. Alle Quellcode Dateien finden Sie auch gepackt in: BeispieleDatentypen.zip


IStack.java

import java.util.Iterator;

/**
 * An interface to stack datatypes.  Stacks allow pushing, popping, and clearing.
 * The stack allows the size() to be queried (a better choice might be just to provide empty()).
 */

public interface IStack<E> {
  /**
   * Return the current number of elements in the collection.
   */
  int size();
  /**
   * Add the element e to the top of the stack.
   */
  void push(E e);
  /**
   * Add all the elements form c to the stack.
   */
  void pushAll(Iterable<E> c);
  /**
   * Remove an element from the top of the stack.
   */
  E pop();
  /**
   * Remove all elements from the stack.
   */
  void clear();
  /**
   * Return an iterator that steps through the elements of the stack.
   */
  Iterator<E> iterator();
}


AStack.java

// Abstract stack class providing implementations of more complex
// functionality in terms of primitives.

public abstract class AStack<E> implements IStack<E> {
    public void pushAll(Iterable<E> c) {
        for(E e : c) push(e);
    }

    // NB: this may be a fairly inefficient way to clear the stack.
    // Specific implementations may do better.
    public void clear() {
        while(size()>0) pop();
    }
}

ListStack.java

import java.lang.Iterable;
import java.util.Iterator;

// A stack implementation using linked lists.

public class ListStack<E> extends AStack<E> implements IStack<E>,Iterable<E> {

    // The internal representation is a linked list.

    private static class Node<E> {
        E elt;
        Node<E> next;
    }

    // The start of the list.

    private Node<E> elts = null;

    // The total number of elements in the list.

    private int count = 0;

    // The size() operation is constant time because the object
    // keeps track of the size in a separate variable.

    public int size() {
        return count;
    }

    public void push(E e) {
        Node<E> n = new Node<E>();
        n.elt = e;
        n.next = elts;
        elts = n;
        count++;
    }

    public E pop() {
        --count;
        Node<E> n = elts;
        elts = n.next;
        return n.elt;
    }

    public void clear() {
        elts = null;
    }

    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> current;
            public boolean hasNext() {
                return current!=null;
            }
            public E next() {
                E result = current.elt;
                current = current.next;
                return result;
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

ListStackTest.java

import junit.framework.TestCase;
import java.util.Random;

// Unit tests for stacks.

public class ListStackTest extends TestCase {

    // Override this in subclasses to test other stack implementations.

    <S> IStack<S> create() {
        return new ListStack<S>();
    }

    // Test basic pushing and popping.

    public void testPush() {
        IStack<Integer> s = create();
        assertEquals("size",0,s.size());
        s.push(99);
        assertEquals("size",1,s.size());
        int result = s.pop();
        assertEquals("result",99,result);
        assertEquals("size",0,s.size());
    }

    // Test basic pushing and popping with many elements; this
    // exercises stack doubling.

    public void testPushMany() {
        ListStack<Integer> s = new ListStack<Integer>();
        for(int i=0;i<10000;i++)
            s.push(i);
        for(int i=9999;i>=0;i--)
            assertEquals("pop",i,(int)s.pop());
        assertEquals("size",0,s.size());
    }
}


ArrayStack.java

import java.lang.Iterable;
import java.util.Iterator;

// ArrayStack<E> is an implementation of both the IArray and the
// IStack interfaces.  It also implements Iterable, so that it can be
// used with standard Java iteration notation.
//
// The internal representation is a storage array and a fill counter.
// The array is doubled when its capacity is reached, allowing for
// amortized linear time append.  The pop() operation does not free
// memory.
//
// For the documentation of the individual public methods, see the
// IArray and IStack interfaces.

public class ArrayStack<E> extends AStack<E> implements IArray<E>,IStack<E>,Iterable<E> {
    E[] data;
    int fill;

    public ArrayStack() {
        fill = 0;
        allocate(10);
    }

    public void allocate(int newsize) {
        E[] ndata = (E[])new Object[newsize];
        int n = fill<newsize?fill:newsize;
        for(int i=0;i<n;i++) ndata[i] = data[i];
        data = ndata;
    }

    public void resize(int newsize) {
        allocate(newsize);
        fill = newsize;
    }

    public int size() {
        return fill;
    }

    public void push(E e) {
        if(fill==data.length) {
            int newsize = 2*fill+1;
            if(newsize<5) newsize = 5;
            allocate(newsize);
        }
        data[fill++] = e;
    }

    public E pop() {
        return data[--fill];
    }

    public E at(int i) {
        assert i>=0 && i<fill;
        return data[i];
    }

    public void put(int i,E e) {
        assert i>=0 && i<fill;
        data[i] = e;
    }

    public void clear() {
        fill = 0;
    }

    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int index = 0;
            public boolean hasNext() {
                return index<fill;
            }
            public E next() {
                assert index<fill;
                return data[index++];
            }
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

ArrayStackTest.java

import junit.framework.TestCase;
import java.util.Random;

// Unit tests for stacks.  These tests are identical to the
// ListStackTest, except we use ArrayStack instances.

public class ArrayStackTest extends ListStackTest {
    <S> IStack<S> create() {
        return new ArrayStack<S>();
    }
}


IArray.java

public interface IArray<E> {
  /**
   * Return the total number of elements in the array.
   */
  int size();
  /**
   * Return the element at position i (0 <= i < size()).
   */
  E at(int i);
  /**
   * Change the element at position i (0 <= i < size()).
   */
  void put(int i,E e);
  /**
   * Change the size of the array.  If newsize<size(), this
   * truncates the array.  If newsize>size(), the new elements
   * are undefined.
   */
  void resize(int newsize);
}

Quicksort.java

import java.util.Random;

public class Quicksort {
  public static <E extends Comparable<E>> ArrayStack<E> quicksort(ArrayStack<E> c) {
    if(c.size()<2) return c;
    
    ArrayStack<E> lo = new ArrayStack<E>();
    ArrayStack<E> mid = new ArrayStack<E>();
    ArrayStack<E> hi = new ArrayStack<E>();
    
    E pivot = c.at(c.size()/2);
    
    for(E e : c) {
      int sign = e.compareTo(pivot);
      if(sign<0) lo.push(e);
      else if(sign>0) hi.push(e);
      else mid.push(e);
    }
    
    lo = quicksort(lo);
    hi = quicksort(hi);
    
    ArrayStack<E> result = new ArrayStack<E>();
    for(E e : lo) result.push(e);
    for(E e : mid) result.push(e);
    for(E e : hi) result.push(e);
    return result;
  }
  
  public static void main(String[] args) {
    ArrayStack<Integer> data = new ArrayStack<Integer>();
    Random rng = new Random();
    for(int i=0;i<10;i++) data.push(rng.nextInt(100));
    ArrayStack<Integer> result = quicksort(data);
    for(int i=0;i<result.size();i++) 
      System.out.println(""+i+" "+result.at(i));
  }
}

ċ
BeispieleDatentypen.zip
(4k)
Ludwig Schmidt-Hackenberg,
11.02.2011, 01:14
Comments