Skip to content

Instantly share code, notes, and snippets.

@menzerath
Created February 26, 2015 15:55
Show Gist options
  • Save menzerath/5f78565ce7ca79bed8f2 to your computer and use it in GitHub Desktop.
Save menzerath/5f78565ce7ca79bed8f2 to your computer and use it in GitHub Desktop.
Abiturklassen
package abiturklassen.baumklassen;
/**
* <p>Materialien zu den zentralen
* Abiturpruefungen im Fach Informatik ab 2012 in
* Nordrhein-Westfalen.</p>
* <p>Klasse BinarySearchTree</p>
* <p>In einem Objekt der Klasse BinarySearchTree werden beliebig viele Objekte in einem Binaerbaum (binaerer Suchbaum)
* entsprechend einer Ordnungsrelation verwaltet. Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder
* verwaltet ein Inhaltsobjekt sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinarySearchTree sind.
* Dabei gilt:
* Die Inhaltsobjekte sind Objekte einer Unterklasse von Item, in der durch &uuml;berschreiben der
* drei Vergleichsmethoden isLess, isEqual, isGreater (s. Item) eine eindeutige Ordnungsrelation festgelegt sein muss.
* Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binaerbaumes.
* Alle Objekte im rechten Teilbaum sind groeßer als das Inhaltsobjekt des Binaerbaumes.
* Diese Bedingung gilt auch in beiden Teilbaeumen.</p>
*
* <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur
* im Fach Informatik</p>
*
* @version 2011-01-05
*/
public class BinarySearchTree {
private BinaryTree bintree;
/**
*Der Konstruktor erzeugt einen leeren Suchbaum.
*/
public BinarySearchTree() {
bintree = new BinaryTree();
}
/**
*Diese Anfrage liefert den Wahrheitswert true, wenn der Suchbaum leer ist, sonst liefert sie den Wert false.
*@return true, wenn der binaere Suchbaum leer ist, sonst false
*/
public boolean isEmpty() {
return bintree.isEmpty();
}
/**
* Falls ein bezueglich der verwendeten Vergleichsmethode isEqual mit pItem uebereinstimmendes Objekt im geordneten Baum enthalten ist,
* passiert nichts. Andernfalls wird das Objekt pItem entsprechend der vorgegebenen Ordnungsrelation in den Baum eingeordnet.
* Falls der Parameter null ist, aendert sich nichts.
* @param pItem einzufuegendes Objekt
*/
public void insert(Item pItem) {
if (pItem!=null) {
if (bintree.isEmpty()) // wenn der Suchbaum leer ist, dann wird der Suchbaum mit dem Inhalt pItem gefuellt
bintree=new BinaryTree(pItem);
else {
Item lItem = (Item)bintree.getObject();
if (pItem.isLess(lItem)) { // links Einfuegen
BinarySearchTree lTree=this.getLeftTree();
lTree.insert(pItem);
this.bintree.setLeftTree(lTree.bintree);
}
else
if (pItem.isGreater(lItem)) { // rechts Einfuegen; bei Gleichheit wird nicht noch einmal eingefuegt
BinarySearchTree rTree=this.getRightTree();
rTree.insert(pItem);
this.bintree.setRightTree(rTree.bintree);
}
}
}
}
/**
* Falls ein bezueglich der verwendeten Vergleichsmethode isEqual mit pItem uebereinstimmendes Objekt im binaeren Suchbaum enthalten ist,
* liefert die Anfrage dieses, ansonsten wird null zurueckgegeben.
* Falls der Parameter null ist, wird null zurueckgegeben.
* @param pItem zu suchendes Objekt
* @return das gefundene Objekt, bei erfolgloser Suche null
*/
public Item search(Item pItem) {
if (bintree.isEmpty() || pItem==null) // Suche war erfolglos oder es gab nichts zum Suchen
return null;
else {
Item lItem = (Item)bintree.getObject();
if (pItem.isLess(lItem)) // links suchen
return this.getLeftTree().search(pItem);
else
if (pItem.isGreater(lItem)) // rechts suchen
return this.getRightTree().search(pItem);
else
return lItem; // gefunden
}
}
/**
* Falls ein bezueglich der verwendeten Vergleichsmethode isEqual mit pItem uebereinstimmendes Objekt im binaeren Suchbaum enthalten ist,
* wird dieses entfernt.
* Falls der Parameter null ist, aendert sich nichts.
* @param pItem zu entfernendes Objekt
*/
public void remove(Item pItem)
{
Item lWurzelInhalt;
BinaryTree lKnoten,lGroessterLinkerKnoten;
if (!this.isEmpty() && pItem!=null) {
lWurzelInhalt=(Item) bintree.getObject();
if (lWurzelInhalt.isEqual(pItem)) {
if (bintree.getRightTree().isEmpty() && bintree.getLeftTree().isEmpty()) {
//Blatt loeschen
//bintree = new BinaryTree();
bintree.setEmpty();
}
else {
// kein Blatt loeschen
if (bintree.getRightTree().isEmpty()) {
//rechter Teilbaum leer
lKnoten=bintree.getLeftTree();
bintree.setObject(lKnoten.getObject());
bintree.setLeftTree(lKnoten.getLeftTree());
bintree.setRightTree(lKnoten.getRightTree());
}
else {
if (bintree.getLeftTree().isEmpty()) {
lKnoten=bintree.getRightTree();
bintree.setObject(lKnoten.getObject());
bintree.setLeftTree(lKnoten.getLeftTree());
bintree.setRightTree(lKnoten.getRightTree());
}
else {
//beide Teilbaeume links und rechts sind nicht leer
lGroessterLinkerKnoten=bintree.getLeftTree();
while (!lGroessterLinkerKnoten.getRightTree().isEmpty())
lGroessterLinkerKnoten=lGroessterLinkerKnoten.getRightTree();
bintree.setObject(lGroessterLinkerKnoten.getObject());
this.getLeftTree().remove((Item)lGroessterLinkerKnoten.getObject());
}
}
}
}
else
{
if (lWurzelInhalt.isLess(pItem)) { // rekursiv loeschen im rechten Teilbaum
BinarySearchTree lRechterBaum=this.getRightTree();
lRechterBaum.remove(pItem);
}
else { // rekursiv loeschen im linken Teilbaum
BinarySearchTree lLinkerBaum=this.getLeftTree();
lLinkerBaum.remove(pItem);
}
}
}
}
/**
* Diese Anfrage liefert das Inhaltsobjekt des Suchbaumes. Wenn der Suchbaum leer ist, wird null zurueckgegeben.
* @return das Inhaltsobjekt bzw. null, wenn der Suchbaum leer ist.
*/
public Item getItem() {
if (this.isEmpty())
return null;
else
return (Item) bintree.getObject();
}
/**
* Diese Anfrage liefert den linken Teilbaum des binaeren Suchbaumes.
* Der binaere Suchbaum aendert sich nicht. Wenn er leer ist, wird null zurueckgegeben.
* @return den linken Teilbaum bzw. null, wenn der Suchbaum leer ist.
*/
public BinarySearchTree getLeftTree() {
if (this.isEmpty())
return null;
else {
BinarySearchTree lTree = new BinarySearchTree(); // der linke Teilbaum muss ein Baum der Klasse BinarySearchTree sein
lTree.bintree=bintree.getLeftTree();
return lTree;
}
}
/**
* Diese Anfrage liefert den rechten Teilbaum des binaeren Suchbaumes.
* Der binaere Suchbaum aendert sich nicht. Wenn er leer ist, wird null zurueckgegeben.
* @return den rechten Teilbaum bzw. null, wenn der Suchbaum leer ist.
*/
public BinarySearchTree getRightTree() {
if (this.isEmpty())
return null;
else {
BinarySearchTree lTree = new BinarySearchTree(); // der rechte Teilbaum muss ein Baum der Klasse BinarySearchTree sein
lTree.bintree=bintree.getRightTree();
return lTree;
}
}
/**
* Für die Testausgabe
*/
BinaryTree gibBaum()
{
return bintree;
}
}
package abiturklassen.baumklassen;
/**
* <p>Materialien zu den zentralen
* Abiturpruefungen im Fach Informatik ab 2012 in
* Nordrhein-Westfalen.</p>
* <p>Klasse BinaryTree</p>
* <p>Mithilfe der Klasse BinaryTree koennen beliebig viele Inhaltsobjekte in einem Binaerbaum verwaltet werden.
* Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt sowie einen
* linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinaryTree sind.</p>
*
* <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur
* im Fach Informatik</p>
*
* @version 2011-01-05
*/
public class BinaryTree
{
private Object lContent;
private BinaryTree lLeftTree, lRightTree;
/**
*Nach dem Aufruf des Konstruktors existiert ein leerer Binaerbaum.
*/
public BinaryTree() {
lContent = null;
lLeftTree = null;
lRightTree = null;
}
/**
*Wenn der Parameter pContent ungleich null ist, existiert nach dem Aufruf des Konstruktors der Binaerbaum und hat pContent als Inhaltsobjekt
*und zwei leere Teilbaeume. Falls der Parameter null ist, wird ein leerer Binaerbaum erzeugt.
*@param pContent Inhaltsobjekt
*/
public BinaryTree(Object pObject) {
if (pObject!=null) {
lContent = pObject;
lLeftTree = new BinaryTree();
lRightTree = new BinaryTree();
}
else {
lContent = null;
lLeftTree = null;
lRightTree = null;
}
}
/**
*Wenn der Parameter pContent ungleich null ist, wird ein Binaerbaum mit pContent als Objekt
*und den beiden Teilbaeume pLeftTree und pRightTree erzeugt. Sind pLeftTree oder pRightTree gleich null, wird der entsprechende Teilbaum
*als leerer Binaerbaum eingefuegt. Wenn der Parameter pContent gleich null ist, wird ein leerer Binaerbaum erzeugt.
*@param pContent Inhaltsobjekt
*@param pLinkerBaum linker Binaerbaum
*@param pRechterBaum rechter Binaerbaum
*/
public BinaryTree(Object pContent, BinaryTree pLinkerBaum, BinaryTree pRechterBaum){
if (pContent!=null) {
lContent = pContent;
if (pLinkerBaum!=null)
lLeftTree = pLinkerBaum;
else
lLeftTree = new BinaryTree();
if (pRechterBaum!=null)
lRightTree = pRechterBaum;
else
lRightTree = new BinaryTree();
}
else { // da der Inhalt null ist, wird ein leerer Baum erzeugt
lContent = null;
lLeftTree = null;
lRightTree = null;
}
}
/**
*Diese Anfrage liefert den Wahrheitswert true, wenn der Binaerbaum leer ist, sonst liefert sie den Wert false.
*@return true, wenn der Binaerbaum leer ist, sonst false
*/
public boolean isEmpty() {
return (lContent==null);
}
/**
*Wenn der Binaerbaum leer ist, wird der Parameter pObject als Inhaltsobjekt sowie ein leerer linker und rechter Teilbaum eingefuegt.
*Ist der Binaerbaum nicht leer, wird das Inhaltsobjekt durch pObject ersetzt. Die Teilbaeume werden nicht geaendert.
*Wenn pObject null ist, bleibt der Binaerbaum unveraendert.
*@param pObject neues Inhaltsobjekt
*/
public void setObject(Object pObject) {
if (pObject!=null) {
if (this.isEmpty()) {
lLeftTree = new BinaryTree();
lRightTree = new BinaryTree();
}
lContent = pObject;
}
}
/**
*Diese Anfrage liefert das Inhaltsobjekt des Binaerbaums. Wenn der Binaerbaum leer ist, wird null zurueckgegeben.
*@return Inhaltsobjekt (bzw. null, wenn der Baum leer ist)
*/
public Object getObject() {
return lContent ;
}
/**
*Wenn der Binaerbaum leer ist, wird pTree nicht angehaengt.
*Andernfalls erhaelt der Binaerbaum den uebergebenen Baum als linken Teilbaum. Falls der Parameter null ist, aendert sich nichts.
*@param pTree neuer linker Teilbaum
*/
public void setLeftTree(BinaryTree pTree) {
if (!this.isEmpty() && pTree!=null)
lLeftTree = pTree;
}
/**
*Wenn der Binaerbaum leer ist, wird pTree nicht angehaengt.
*Andernfalls erhaelt der Binaerbaum den uebergebenen Baum als rechten Teilbaum. Falls der Parameter null ist, aendert sich nichts.
*@param pTree neuer rechter Teilbaum
*/
public void setRightTree(BinaryTree pTree) {
if (! this.isEmpty() && pTree!=null)
lRightTree = pTree;
}
/**
*Diese Anfrage liefert den linken Teilbaum des Binaerbaumes.
*Der Binaerbaum aendert sich nicht. Wenn der Binaerbaum leer ist, wird null zurueckgegeben.
*@return linker Teilbaum
*/
public BinaryTree getLeftTree() {
if (! this.isEmpty())
return lLeftTree;
else
return null;
}
/**
*Diese Anfrage liefert den rechten Teilbaum des Binaerbaumes.
*Der Binaerbaum aendert sich nicht. Wenn der Binaerbaum leer ist, wird null zurueckgegeben.
*@return rechter Teilbaum
*/
public BinaryTree getRightTree() {
if (! this.isEmpty())
return lRightTree;
else
return null;
}
/**
*Der Baum wird durch diesen Auftrag geleert.
*Die Anfrage isEmpty liefert danach true zurueck und auf die beiden urspruenglichen Teilbaeume kann nicht mehr zugegriffen werden.
*/
public void setEmpty() {
lContent = null;
lLeftTree = null;
lRightTree = null;
}
}
package abiturklassen.baumklassen;
/**
* <p>Materialien zu den zentralen
* Abiturpruefungen im Fach Informatik ab 2012 in
* Nordrhein-Westfalen.</p>
* <p>Klasse Item</p>
* <p>Die Klasse Item ist abstrakte Oberklasse aller Klassen, deren Objekte in einen Suchbaum (BinarySearchTree) eingef&uuml;gt werden sollen.
* Die Ordnungsrelation wird in den Unterklassen von Item durch &Uuml;berschreiben der drei abstrakten Methoden isEqual, isGreater und isLess festgelegt. </p>
*
* <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur
* im Fach Informatik</p>
*
* @version 2010-10-20
*/
public abstract class Item {
/**
*Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gew&uuml;nschten Ordnungsrelation gr&ouml;ßer als das Objekt pItem ist,
*wird true geliefert.
*Sonst wird false geliefert.
*@param pItem es wird &uuml;berpr&uuml;ft, ob das aufrufende Objekt gr&ouml;ßer als dieser Parameter pItem ist
*/
public abstract boolean isGreater (Item pItem);
/**
*Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gew&uuml;nschten Ordnungsrelation kleiner als das Objekt pItem ist,
*wird true geliefert.
*Sonst wird false geliefert.
*@param pItem es wird &uuml;berpr&uuml;ft, ob das aufrufende Objekt kleiner als dieser Parameter pItem ist
*/
public abstract boolean isLess (Item pItem);
/**
*Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gew&uuml;nschten Ordnungsrelation gleich dem Objekt pItem ist,
*wird true geliefert.
*Sonst wird false geliefert.
*@param pItem es wird &uuml;berpr&uuml;ft, ob das aufrufende Objekt gleich dem Parameter pItem ist
*/
public abstract boolean isEqual (Item pItem);
}
package abiturklassen.listenklassen;
/**
* <p>Materialien zu den zentralen
* Abiturpruefungen im Fach Informatik ab 2012 in
* Nordrhein-Westfalen.</p>
* <p>Klasse List</p>
* <p>Objekte der Klasse List verwalten beliebig viele,
* linear angeordnete Objekte. Auf hoechstens ein Listenobjekt,
* aktuelles Objekt genannt, kann jeweils zugegriffen werden.
* Wenn eine Liste leer ist, vollstaendig durchlaufen wurde oder
* das aktuelle Objekt am Ende der Liste geloescht wurde, gibt es
* kein aktuelles Objekt. Das erste oder das letzte Objekt einer
* Liste koennen durch einen Auftrag zum aktuellen Objekt gemacht werden.
* Außerdem kann das dem aktuellen Objekt folgende Listenobjekt
* zum neuen aktuellen Objekt werden. Das aktuelle Objekt kann gelesen,
* veraendert oder geloescht werden. Ausserdem kann vor dem aktuellen
* Objekt ein Listenobjekt eingefügt werden.</p>
*
* <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur
* im Fach Informatik</p>
*
* @version 2011-03-31
*/
public class List
{ private Node first, tail, current;
// Node
private class Node {
private Object contentObj;
private Node nextNode;
public Node(Object pContent) {
contentObj = pContent;
nextNode = null;
}
public void setContent(Object pContent) {
contentObj = pContent;
}
public Object content() {
return contentObj;
}
public void setNext(Node pNext) {
nextNode = pNext;
}
public Node getNext() {
return nextNode;
}
} // Ende der Klasse Node
/**
* Eine leere Liste wird erzeugt.
*/
public List() {
tail = new Node(null); // Dummy
first = tail;
tail.setNext(tail);
/* Der next-Zeiger des hinteren Dummy-Elementes
* zeigt auf das vorangehende Element.
*/
current=first;
}
/**
* Die Anfrage liefert den Wert true, wenn die Liste
* keine Objekte enthaelt, sonst liefert sie den Wert false.
* @return true, wenn die Liste leer ist, sonst false
*/
public boolean isEmpty() {
return first == tail;
}
/**
* Die Anfrage liefert den Wert true, wenn es ein
* aktuelles Objekt gibt, sonst
* liefert sie den Wert false.
* @return true, falls Zugriff moeglich, sonst false
*/
public boolean hasAccess() {
return (!this.isEmpty()) && (current != tail);
}
/**
* Falls die Liste nicht leer ist, es ein aktuelles
* Objekt gibt und dieses nicht das letzte Objekt der
* Liste ist, wird das dem aktuellen Objekt in der Liste
* folgende Objekt zum aktuellen Objekt, andernfalls gibt
* es nach Ausführung des Auftrags kein aktuelles Objekt,
* d.h. hasAccess() liefert den Wert false.
*/
public void next() {
if (this.hasAccess())
current = current.getNext();
}
/**
* Falls die Liste nicht leer ist, wird das erste
* Objekt der Liste aktuelles Objekt.
* Ist die Liste leer, geschieht nichts.
*/
public void toFirst() {
if (!this.isEmpty())
current = first;
}
/**
* Falls die Liste nicht leer ist, wird das
* letzte Objekt der Liste aktuelles Objekt.
* Ist die Liste leer, geschieht nichts.
*/
public void toLast() {
if (!this.isEmpty())
current = tail.getNext();
}
/**
* Falls es ein aktuelles Objekt gibt
* (hasAccess() == true), wird das aktuelle Objekt
* zurueckgegeben, andernfalls (hasAccess()== false)
* gibt die Anfrage den Wert null zurueck.
* @return Inhaltsobjekt
*/
public Object getObject() {
if (this.hasAccess())
return current.content();
else
return null;
}
/**
* Falls es ein aktuelles Objekt gibt (hasAccess() == true)
* und pObject ungleich null ist, wird das aktuelle Objekt
* durch pObject ersetzt. Sonst bleibt die Liste unveraendert.
* @param pObject Inhaltsobjekt
*/
public void setObject(Object pObject) {
if (pObject != null && this.hasAccess() )
current.setContent(pObject);
}
/**
* Ein neues Objekt pObject wird am Ende der Liste eingefuegt.
* Das aktuelle Objekt bleibt unveraendert. Wenn die Liste
* leer ist, wird das Objekt pObject in die Liste eingefuegt
* und es gibt weiterhin kein aktuelles Objekt
* (hasAccess() == false). Falls pObject gleich null ist,
* bleibt die Liste unveraendert.
*@param pObject Inhaltsobject
*/
public void append(Object pObject) {
if (pObject != null) {
Node lNewNode,lPos0;
lPos0 = current;
lNewNode = new Node(pObject);
lNewNode.setNext(tail);
if (this.isEmpty())
first = lNewNode;
else {
Node lPrevious = tail.getNext();
lPrevious.setNext(lNewNode);
}
tail.setNext(lNewNode);
current = lPos0;
}
}
/**
*Falls es ein aktuelles Objekt gibt (hasAccess() == true),
*wird ein neues Objekt vor dem aktuellen Objekt in die
*Liste eingefuegt. Das aktuelle Objekt bleibt unveraendert.
*Wenn die Liste leer ist, wird pObject in die Liste eingefuegt
*und es gibt weiterhin kein aktuelles Objekt
*(hasAccess() == false). Falls es kein aktuelles Objekt gibt
*(hasAccess() == false) und die Liste nicht leer ist oder
*pObject gleich null ist, bleibt die Liste unveraendert.
*@param pObject Inhaltsobjekt
*/
public void insert(Object pObject) {
if (pObject != null) {
Node lNewNode,lFront,lPos;
if (this.isEmpty())
this.append(pObject);
else
if (this.hasAccess() ) {
lPos = current;
lNewNode = new Node(pObject);
lNewNode.setNext(current);
if (lPos == first )
first = lNewNode;
else {
this.toFirst();
lFront = current;
while (this.hasAccess() & !(current == lPos)) {
lFront = current;
this.next();
}
lFront.setNext(lNewNode);
}
current=lPos;
}
}
}
/**
* Die Liste pList wird an die Liste angehaengt. Anschliessend
* wird pList eine leere Liste. Das aktuelle Objekt bleibt unveraendert.
* Falls pList null oder eine leere Liste ist, bleibt die Liste
* unveraendert.
* @param pList Liste
*/
public void concat(List pList) {
Node lCurrent1, lCurrent2, lPos0;
if (pList != null && !pList.isEmpty() ) {
if (this.isEmpty() ) {
first = pList.first;
tail = pList.tail;
current = tail;
}
else {
lPos0 = current;
current = tail.getNext();
lCurrent1 = current;
pList.toFirst();
current = pList.current;
lCurrent2 = pList.current;
lCurrent1.setNext(lCurrent2);
if (lPos0 != tail)
current = lPos0;
else
current = pList.tail;
tail = pList.tail;
}
// pList wird zur leeren Liste
pList.tail = new Node(null); // Dummy
pList.first = pList.tail;
pList.tail.setNext(tail);
pList.current = pList.tail;
}
}
/**
* Falls es ein aktuelles Objekt gibt (hasAccess() == true),
* wird das aktuelle Objekt geloescht und das Objekt hinter
* dem gelaeschten Objekt wird zum aktuellen Objekt. Wird das
* Objekt, das am Ende der Liste steht, geloescht, gibt es kein
* aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste
* leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false),
* bleibt die Liste unveraendert.
*/
public void remove() {
Node lPos, lFront;
if (this.hasAccess() ) {
if (current == first ) {
first = current.getNext();
if (current.getNext() == tail)
tail.setNext(first);
current = first;
}
else {
lPos = current;
this.toFirst();
lFront = current;
while (this.hasAccess() && !(current == lPos)) {
lFront = current;
this.next();
}
lFront.setNext(lPos.getNext());
current = lFront.getNext();
if (current == tail)
tail.setNext(lFront);
}
}
}
}
package abiturklassen.listenklassen;
/**
* <p>Materialien zu den zentralen
* Abiturpruefungen im Fach Informatik ab 2012 in
* Nordrhein-Westfalen.</p>
* <p>Klasse Queue</p>
* <p>Objekte der Klasse Queue (Warteschlange) verwalten beliebige
* Objekte nach dem First-In-First-Out-Prinzip, d.h. das zuerst
* abgelegte Objekt wird als erstes wieder entnommen.</p>
*
* <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur
* im Fach Informatik</p>
*
* @version 2010-10-20
*/
public class Queue
{
private Node head, tail;
/**
* Ein Knoten besteht aus einem Inhaltsobjekt
* und einem Nachfolgeknoten.
*/
private class Node
{
private Object content;
private Node nextNode;
/**
* Es wird ein neuer Knoten erzeugt.
*
* @param pContent das Inhaltsobjekt
* @param pNext der Nachfolgeknoten
*/
public Node(Object pContent, Node pNext)
{ content = pContent;
nextNode = pNext;
}
/**
* Das Inhaltsobjekt wird ge&auml;ndert.
*
* @param pContent das neue Inhaltsobjekt
*/
public void setContent(Object pContent)
{
content = pContent;
}
/**
* Das Inhaltsobjekt wird zur&uuml;ckgegeben.
*
* @return das Inhaltsobjekt
*/
public Object content()
{
return content;
}
/**
* Der Nachfolgeknoten wird ge&auml;dert.
*
* @param pNext der neue Nachfolgeknoten
*/
public void setNext(Node pNext)
{
nextNode = pNext;
}
/**
* Der Nachfolgeknoten wird zur&uuml;ckgegeben.
*
* @return der Nachfolgeknoten
*/
public Node next()
{
return nextNode;
}
}
/**
* Eine leere Schlange wird erzeugt.
*/
public Queue()
{
head = null;
tail = null;
}
/**
* Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte
* enthaelt, sonst liefert sie den Wert false.
*
* @return true, falls die Schlange leer ist, sonst false
*/
public boolean isEmpty(){
return head == null;
}
/**
* Das Objekt pObjekt wird an die Schlange angehaengt.
* Falls pObject gleich null ist, bleibt die Schlange
* unveraendert.
*
* @param pObject das anzuhaengende Objekt
*/
public void enqueue(Object pObject)
{
if (pObject != null){
Node lNewNode = new Node(pObject, null);
if (this.isEmpty()){
head = lNewNode;
tail = lNewNode;
}
else{
tail.setNext(lNewNode);
tail = lNewNode;
}
}
}
/**
* Das erste Objekt wird aus der Schlange entfernt.
* Falls die Schlange leer ist, wird sie nicht
* veraendert.
*/
public void dequeue()
{
if (!this.isEmpty()){
head = head.next();
}
}
/**
* Die Anfrage liefert das erste Objekt der Schlange.
* Die Schlange bleibt unveraendert. Falls die
* Schlange leer ist, wird null zur&uuml;ck gegeben.
*
* @return das erste Objekt der Schlange oder null, falls
* die Schlange leer ist.
*/
public Object front(){
if (this.isEmpty())
{
return null;
}
else{
return head.content();
}
}
}
package abiturklassen.listenklassen;
/**
* <p>Materialien zu den zentralen
* Abiturpruefungen im Fach Informatik ab 2012 in
* Nordrhein-Westfalen.</p>
* <p>Klasse Stack</p>
* <p>Objekte der Klasse Stack (Keller, Stapel) verwalten beliebige
* Objekte nach dem Last-In-First-Out-Prinzip, d.h. das zuletzt
* abgelegte Objekt wird als erstes wieder entnommen.</p>
*
* <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur im Fach Informatik</p>
*
* @version 2010-10-20
*/
public class Stack {
private Node head;
// Node
private class Node {
private Object content = null;
private Node nextNode = null;
public Node(Object pObject) {
content = pObject;
nextNode = null;
}
public void setNext(Node pNext) {
nextNode = pNext;
}
public Node getNext() {
return nextNode;
}
public Object getContent() {
return content;
}
} // Ende Node
// Stack
/**
* Ein leerer Stapel wird erzeugt.
*/
public Stack() {
head = null;
}
/**
* Die Anfrage liefert den Wert true, wenn der Stapel
* keine Objekte enthaelt, sonst liefert sie den Wert false.
* @return true, falls der Stapel leer ist, sonst false.
*/
public boolean isEmpty() {
return (head == null);
}
/**
* Das Objekt pObject wird oben auf den Stapel gelegt.
* Falls pObject gleich null ist, bleibt der Stapel unveraendert.
* @param pObject ist das einzufuegende Objekt.
*/
public void push(Object pObject) {
if (pObject != null) {
Node lNode = new Node(pObject);
lNode.setNext(head);
head=lNode;
}
}
/**
* Das zuletzt eingefuegte Objekt wird von dem Stapel entfernt.
* Falls der Stapel leer ist, bleibt er unveraendert.
*/
public void pop() {
if (!isEmpty())
head = head.getNext();
}
/**
* Die Anfrage liefert das oberste Stapelobjekt.
* Der Stapel bleibt unveraendert.
* Falls der Stapel leer ist, wird null zurueck gegeben.
* @return Inhaltsobjekt
*/
public Object top() {
if (!this.isEmpty())
return head.getContent();
else
return null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment