Problem bei Programmierung zyklischer Listen

Grammi

Hallo,

ich habe ein Problem bei der Programmierung einer zyklischen Liste. Und zwar sollen Elemente in eine Liste eingetragen werden können und auch wieder gelöscht werden können. Dabei möchte ich, dass nur ein Anker verwendet wird. Dieser Anker soll eine Referenz sein, die auf das jüngste Element der Liste zeigt. Und dieses jüngste Element soll auf das älteste Element zeigen, so dass im Prinzip ein verketteter Ring entsteht. Achso die Liste bzw. der Ring ist ein vorwärtsverketteter Ring. Nun klappt das mit dem Eintragen ganz gut, hab ich auch schon in einem seperaten Testtreiber getestet. Aber die Sache mit dem Entfernen bekomme ich einfach nicht hin. Es soll immer das älteste Element dabei gelöscht werden und nicht das jüngste. Im folgenden mal ein Ausschnitt aus dem Programm. Vielleicht könnt ihr mir ja helfen. Wär euch echt sehr dankbar.

public class WarteschlangeListe<Element> implements Warteschlange<Element>{

	private class Knoten<Element>{

            Element wert;
	      Knoten<Element> verbindung;

		Knoten(final Element wert, final Knoten<Element> verbindung){
			this.wert = wert;
			this.verbindung = verbindung;
		}

		Knoten(final Element wert){
			this(wert, null);
		}
	}

private Knoten<Element> anker = null; //Anker
public int anzahl;

public WarteschlangeListe(){
		anker = null;
	}

      //Liste entleeren
	public void entleeren(){
		anker = null;
	}

      //Element in die Liste eintragen und am Ende einfügen
	public void eintragen(final Element element) throws VollAusnahme{
		try{
			if (istLeer()){
				anker = new Knoten<Element>(element, null);
				anker.verbindung = anker;
			}
			else
			{
				anker = new Knoten<Element>(element, anker.verbindung);
			}
			anzahl++;
		}
		catch(OutOfMemoryError ausnahme){
			throw new VollAusnahme();
		}
	}

      //ältestes Element entfernen
	public void entfernen() throws LeerAusnahme{//fertig
		try{
			//HIER BRAUCHE ICH DIE HILFE VON EUCH!!!!!
			anzahl--;
		}
		catch(NullPointerException ausnahme){
			throw new LeerAusnahme();
		}
	}

      //ältestes Element lesen
	public Element lesen() throws LeerAusnahme{
		try{
			return (Element)anker.verbindung.wert;
		}
		catch(NullPointerException ausnahme){
			throw new LeerAusnahme();
		}
	}

      //Anfrage ob Liste leer ist
	public boolean istLeer(){
		return anker == null;
	}

      //Anfrage ob Liste voll ist
	public boolean istVoll(){
		try{
			Knoten<Element> knoten = new Knoten<Element>(null, null);
			return false;
		}
		catch(OutOfMemoryError ausnahme){
			return true;
		}
	}

	public int anzahlElemente(){
		return anzahl;
	}

      //jüngstes Element lesen
	public Element lesen_juengstes() throws LeerAusnahme{//Zusatzmethode
		if (istLeer()){
			throw new LeerAusnahme();
		}
		else return (Element)anker.wert;
	}
}

Achso mir ist da noch was eingefallen. Und zwar hab ich noch nie ein Objektdiagramm gezeichnet und weiß auch leider nicht so recht wie es funktioniert. Es soll aber einige Dinge besser verständlich machen. Könnt ihr mir vielleicht auch Tipps geben, wie an solch eine Sache rangehe oder habt ihr vielleicht ein Beispiel parat? Danke euch echt.

Hoffentlich hab' ich das jetzt richtig überschaut. Könnte man nicht deiner Klasse "Knoten<Element>" eine Eigenschaft "Knoten<Element> vorgänger" verpassen, in welcher dann jeweils der Vorgängerknoten abgelegt wird?

Dein Konstruktor würde dann wie folgt aussehen:

Knoten(final String wert, final Knoten<Element> verbindung, Knoten<Element> vorgänger)
     {
      this.wert = wert;
      this.verbindung = verbindung;
      this.vorgänger = vorgänger;
     }

Danach folgt bei deiner Methode "eintragen":

try{
            if (istLeer()){
                anker = new Knoten<Element>(element, null, null);
                anker.verbindung = anker;
            }
            else
            {
                anker = new Knoten<Element>(element, anker.verbindung, anker);

            }
            anzahl++;

Das Entfernen könnte vielleicht so ablaufen:

Knoten<Element> temp = anker;
            Knoten<Element> nachfolger = null;

            for (int k = anzahl; k > 0; k--)
            {
             if (temp.vorgänger == null)
             {
              nachfolger.vorgänger = null;
              anker.verbindung = nachfolger;
              break;
             }
             nachfolger = temp;
             temp = temp.vorgänger;
            }

            anzahl--;

Man überprüft also immer den jeweiligen Vorgänger (aktueller Knoten wird gespeichert). Ist dieser null, so wurde der Anfang erreicht. Als neuen "ältesten" Knoten setzt man dann den temporär gespeicherten "Nachfolger". Ist vielleicht nicht die eleganteste Lösung, aber sie könnte klappen.

----

Objektdiagramme gemäß UML ähneln dem Klassendiagramm (einfach mal suchen; du wirst genügend Abbildungen finden). Der Objektname wird jedoch unterstrichen und die Eigenschaften erhalten kokrete Werte. Auf die Darstellung der Methoden kann man im Objektdiagramm verzichten.

JohnDoe21

TFH-Berlin, 2 Sem. medieninformatik bei Solymosi?
Haben wir gerade als Übung gehabt:

package liste;

class Knoten<Element> {
    public Element wert = null;
	public Knoten<Element> verbindung = null;
	public Knoten (final Element wert, final Knoten<Element> verbindung){
		this.wert = wert;
		this.verbindung = verbindung;
	}
}

package liste;

import lehrbuch.*;

class ListRing<Element> implements WarteschlangeImpl<Element>{

	private Knoten<Element> anker = null;
   private final NoMoreMemoryException outOfMemory = new NoMoreMemoryException("OutOfMemoryError");
	private class NoMoreMemoryException extends VollAusnahme{
      private String info;
      public NoMoreMemoryException(String info){
         super();
         this.info = info;
      }
      public String toString(){
         return info;
      }
   }
   public void entleeren(){
		anker = null;
	}

	public void eintragen(final Element element) throws VollAusnahme{
		try{
			Knoten<Element> last = anker;
			//wenn anker ==null: Exception
			anker = new Knoten<Element>(element, last.verbindung); 
			last.verbindung = anker;

		}catch(OutOfMemoryError ausnahme){
			//throw new VollAusnahme();  //Neues Objekt ohne Memory ?! Na dann viel Glück ...
         throw outOfMemory;
		}
		//Alternativ hätte man mit if(!istLeer)/else arbeiten können 
		catch(NullPointerException e){
			anker = new Knoten<Element>(element,anker); 
			anker.verbindung = anker;
		}
	}

	public Element lesen() throws LeerAusnahme{		
		try{
			return anker.verbindung.wert;	
		}
		catch(NullPointerException e){
			throw new LeerAusnahme();
		}
	}

	public void entfernen() throws LeerAusnahme{
		if(istLeer()) throw new LeerAusnahme(); //eleganter
      //prüft, wieviele Objekte in der Liste hängen ## bei nur 1Obj: Referenz auf sich selbst 
		if(anker.verbindung.verbindung != anker.verbindung)
         anker.verbindung = anker.verbindung.verbindung;
		//wenn Referenz auf sich selbst
		else anker = null;
	}

	public boolean istLeer(){
		return anker == null;
	}

	public boolean istVoll(){
		return false;
	}
}

package liste;

import lehrbuch.*;

public interface WarteschlangeImpl<Element> {
	public void entleeren(); // ensures istLeer()
	public void eintragen(final Element element) throws VollAusnahme; // requires !istVoll() // ensures !istLeer()
	public Element lesen() throws LeerAusnahme; // const // requires !istLeer()
	public void entfernen() throws LeerAusnahme; // requires !istLeer() // ensures !istVoll()
	public boolean istLeer(); // const
	public boolean istVoll(); // const
}

package liste;

import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import lehrbuch.*;

class WarteschlangeGUI
{
	private ListRing listInstanz;

	private JFrame frame;
	private Container content;

//#########  Konstruktor  ##########
	public WarteschlangeGUI()
	{
		listInstanz = new ListRing();
//Frame erstellen
		frame = new JFrame();
		frame.setLayout(null);
		content = frame.getContentPane();
		frame.setSize(350,250);

//TextField zur Eingabe erstellen
		JTextField eingabeFeld = new JTextField("Text eingeben");
		eingabeFeld.setBounds(10,72,100,20);

//StatusLabel erstellen
		JLabel status = new JLabel("Status:");
		status.setBounds(10,200,240,20);

//Listener für Buttons
		KomponentenLauscher lauscher = new KomponentenLauscher(status,eingabeFeld);

//Buttons erstellen
		JButton eintragen = new JButton("eintragen");
		eintragen.setBounds(10,10,100,20);
		eintragen.addActionListener(lauscher);

		JButton entfernen = new JButton("entfernen");
		entfernen.setBounds(120,10,100,20);
		entfernen.addActionListener(lauscher);

		JButton entleeren = new JButton("entleeren");
		entleeren.setBounds(10,40,100,20);
		entleeren.addActionListener(lauscher);

		JButton lesen = new JButton("lesen");
		lesen.setBounds(120,40,100,20);
		lesen.addActionListener(lauscher);

//Komponenten hinzufügen
		content.add(eintragen);
		content.add(entfernen);
		content.add(entleeren);
		content.add(lesen);
		content.add(eingabeFeld);
		content.add(status);

		frame.setVisible(true);
	}

	public static void main(String [] args)	{
		WarteschlangeGUI instanzGUI = new WarteschlangeGUI();

	}

//############### ACTION ##########
class KomponentenLauscher implements ActionListener

	{
		JLabel status;
		JTextField eingabeFeld;

		public KomponentenLauscher(JLabel status, JTextField eingabeFeld){
			this.status = status;
			this.eingabeFeld = eingabeFeld;
		}

		public void actionPerformed(ActionEvent e)
		{
			if (e.getActionCommand() == "eintragen"){
				try{
					listInstanz.eintragen(eingabeFeld.getText());
					status.setText("<html>String-Objekt <font color=\"RED\"><i>'"+eingabeFeld.getText()+"'</i></font> hinzugefügt</html>");
				}
				catch(VollAusnahme voll){
					status.setText("<html>Ausnahme - Warteschlange <font color=\"RED\">voll</font></html>");
				}

			}

			if (e.getActionCommand() == "entfernen"){
				try{
					listInstanz.entfernen();
					status.setText("<html>Ältestes String-Objekt entfernt!");
					}
				catch(LeerAusnahme leer){
					status.setText("<html>Ausnahme - Warteschlange <font color=\"RED\">leer</font></html>");
				}
			}

			if (e.getActionCommand() == "entleeren"){
				listInstanz.entleeren();
				status.setText("entleert");
			}

			if (e.getActionCommand() == "lesen"){
				try{
					status.setText("<html>Ältestes-Objekt <font color=\"RED\"><i>'"+listInstanz.lesen().toString()+"'</i></font></html>");
				}
				catch(LeerAusnahme leer){
					status.setText("<html>Ausnahme - Warteschlange <font color=\"RED\">leer</font></html>");
				}
			}
		}
	}
}