verkettete Liste

[Reen]

Hallo!

Mal ne Frage. Beschäftige mich gerade mit verketteten Listen. Habe hierzu auch ein Bsp. gefunden http://www.hh.schule.de/julius-leber-schule/UlfChrist/verklisten.html. Das Prob am Ganzen ist, dass die Ausgabe in der genau umgekehrten Reihenfolge passiert, wie die Elemente in die Liste geschrieben wurden. d.h. das die neuen Elemente werden immer zwischen Kopf und dem aktuellen Nachfolger vom Kopf eingeschoben. Das ist aber irgendwie Mist.

Ich finde auch keinen Weg, wie ich das anders in die Liste schreiben kann, dass die Ausgabe der Eingabe entspricht.

Kann mir da ma jemand einen Tipp geben?

Danke
Reen

 

[moormaster]

Ist doch klar... die Methode fuegeNache(knoten, neuerKnoten) fügt den neuen Knoten direkt hinter den anderen als Parameter angegebenen Knoten ein. In der Beispiel main Methode werden Elemente immer direkt hinter dem Kopf eingefügt.

D.h. wenn du eine leere Liste hast

k->[null]

und Elemente immer wieder direkt hinterm Kopf einfügst, veränderst du damit eben die Reihenfolge:

fuegeNach(k, "1"):
k->"1"->[ende]

fuegeNach(k, "2");
k->"2"->"1"->[ende]

fuegeNach(k, "3");
k->"3"->"2"->"1"->[ende]

Wenn die Reihenfolge der vom Kopf bis zum Ende gelesenen Elemente der Reihenfolge des Einfügens entsprechen soll, dann musst du neue Elemente immer hinter dem letzten Element der Liste einfügen... bedeutet natürlich mehr Arbeit, weil du immer wissen musst, welches gerade das letzte Element ist.


fuegeNach(k, "1");
k->"1"->[ende]

fuegeNach(Referenz auf "1", "2");
k->"1"->"2"->[ende]

fuegeNach(Referenz auf "2", "3");
k->"1"->"2"->"3"->[ende]

 

[Reen]

Moin.

Kann mir nochma einer erklären, was folgender Syntax bedeutet. Code aus obrigem Link (da ist übrigens ein Punkt am Ende des Links zu viel :wink: )

neuKnoten.naechstes  = vorgaenger.naechstes

Also mir gehts jetzt nich darum, was dieses Stück Code macht. Das weiss ich, aber mir ist der Syntax nich ganz klar.
Die Var. "vorgaenger" ist eine Var. der Klasse Liste und "naechster" eine Var. der Klasse Knoten vom Typ Knoten.

Diese Kombination der beiden Var. verstehe ich nich ganz. Wird eine neue Instanz von Knoten erstellt, steht NULL in "naechstes". In "vorgaenger" steht immer die Adresse von "kopf".

Was passiert jetzt eigentlich mit beiden Variablen in dieser Kombination. Beides sind ja eigentlich nur Variablen! :bahnhof:

Danke
Reen

 

[SlaterB]

alles vier sind Variablen, mit denen man Objekte ansprechen kann

vorgaenger kann zu diesem Zeitpunkt wohl einen sinnvollen naechstes haben (nicht unbedingt null)

diese Referenz auf ein Objekt möchte man kopieren,
man speichert sie in einer anderen Variablen, und zwar in
neuKnoten.naechstes

da ist doch nix dabei?

Normalfall:
KlassenName einObjekt = irgendas;
irgendeineVariable = einObjekt;

hier:
KlassenName einObjekt = vorgaenger.naechstes;
neuKnoten.naechstes= einObjekt;


kürzer in einer Zeile

 

[Reen]

Jo...danke. Bin dann langsam auch dahinter gekommen.

So....jetzt nochma zu der Liste. Die sollte ja in der gleichen Reihenfolge ausgegeben werden, wie es auch in die Liste geschrieben wurde. Einen kleinen Teilerfolg konnte ich erzielen. Nur ganz ist es noch nich so, wie es sein soll.

Jetzt stimmt zwar die Reihenfolge der übergebenen Strings, aber mit dem Knoten "Kopf" und "Ende" hat er ein Prob.
Die Ausgabe sieht dann folgendermaßen aus.

kopf
ende
Element 1

Warum auch immer. Ich habe mir extra ein paar Ausgaben zusätzlich gemacht, um zu sehen, wie er die Adressen hin und her kopiert.

Also erstes zeigt ja "Kopf" auf "Ende". Der Knoten Ende wird ja dann durch einen neuen Knoten ersetzt, der dann Werte enthält. Die Adresse von Kopf zeigt ja immer noch auch die gleiche Folgeadresse, nur das eben der Knoten quasi ersetzt wurde. Eigentlich werden ja nur die Adressen verändert.

Jemand ne Idee, wie ich das jetzt noch vollkommen richtig in Reihe bekommen?

Danke
Reen

class Knoten                  
{                            
  public Knoten naechster;    

  public Object element;      
                             
  
  public Knoten(Object obj)   
  {                           
    element = obj;            
   
  }
}

class Kette                                     
	{                                           
	  public Knoten kopf = new Knoten("kopf");  
	  public Knoten ende = new Knoten("ende");  
	 
	  
	  public Kette()                            
	  {                                         
		kopf.naechster = ende;                  
	    ende.naechster = null;
	  }                                         


	  public void fuegeNach(Object neuObj)
	  {   System.out.println("Adresse Kopf: " + kopf); 
	      System.out.println("Adresse Kopf (naechster): " + kopf.naechster);
	      
	      System.out.println("Adresse Ende: " + ende);
	      System.out.println("Adresse Ende (naechster): " + ende.naechster);
	      
	      
	      Knoten neuKnoten = new Knoten(neuObj);
	      Knoten aktueller_neuKnoten = neuKnoten;
	      
	      	      
   	      System.out.println("\nneuKnoten (Adresse): " + neuKnoten);
     	  System.out.println("neuKnoten nächster: " + neuKnoten.naechster);
   	      
	      
	      neuKnoten = ende;
	      neuKnoten.naechster = aktueller_neuKnoten;
	      ende = aktueller_neuKnoten;
	      
	      System.out.println("\nAdresse vom neuKnoten mit Ende Knoten tauschen\n");
	      System.out.println("neuKnoten (Adresse): " + neuKnoten);
	      System.out.println("neuKnoten nächster (Adresse): " + neuKnoten.naechster);
	      
	      System.out.println("Ende Knoten: " + ende);
	      System.out.println("Ende Knoten (naechster): " + ende.naechster);
	  }                                                 
	  
	 
	  public void ausgeben()
	  {
	    Knoten aktuellerKnoten = kopf;                    

	    while (aktuellerKnoten != null)                   
	    {
	      System.out.println(aktuellerKnoten.element);    
	      aktuellerKnoten = aktuellerKnoten.naechster;    
	    }                                                 
	  }                                                   
	}

import java.util.Vector;

public class Kettentest
{
  public static void main(String[] params)
  {    
	Kette liste = new Kette ();
	
	liste.fuegeNach ("Element 1");

   liste.ausgeben ();
  }
}

 

[SlaterB]

also bei so bescheuerten Namen helfe ich zumindest nicht, sorry (bis auf die folgenen allgemeinen Tipps)
nenne sie 1,2,3,4


und überhaupt, versuche erstmal ein Element einzufügen, klappt das?
dann ein zweites, geht das?, Reihenfolge richtig? Schritte nachzuvollziehen?
dann drei, dann vier,

wann tritt das erste mal der Fehler aus?,
was genau geht, die Sache mit den Adressen habe ich nicht verstanden,

schön ist die Operation ausgeben, die hilft weiter,
beim fraglichen Schritt (beim ersten bei dem der Fehler auftritt, nicht wenn die Liste eh schon voll und alles durcheinander ist!) führe diese VOR und NACH dem Einfügen durch,

und in der Einfüge-Operation Schritt für Schritt-Ausgaben der Änderungen,
da hast du ja schon ne Menge, verstehst du es trotzdem nicht oder was ist das Problem?

 

[Reen]

So....ich habs ma bissl abgeändert (oben den Code).

Ich poste ma die Ausgabe der Adressen, wo die Objekte liegen

Adresse Kopf: Knoten@119c082
Adresse Kopf (naechster): Knoten@1add2dd
Adresse Ende: Knoten@1add2dd
Adresse Ende (naechster): null

neuKnoten (Adresse): Knoten@eee36c
neuKnoten nächster: null

Adresse vom neuKnoten mit Ende Knoten tauschen

neuKnoten (Adresse): Knoten@1add2dd
neuKnoten nächster (Adresse): Knoten@eee36c
Ende Knoten: Knoten@eee36c
Ende Knoten (naechster): null

Das sieht für mich alles logisch aus. Kopf hat die Adresse "119c082" und zeigt auf den EndeKonten mit "1add2dd".

Jetzt legt es einen neuen Knoten mit Adr. "eee36c" an, welcher vorerst auf NULL zeigt. Im nächsten Schritt tausche ich die Adressen von Ende-Knoten mit dem neuen Knoten. d.h. der neue Knoten bekommt die Adresse "1add2dd" und der Ende Knoten die Adresse "eee36c".

Jetzt verstehe ich nich, warum die Ausgabe folgendermaßen aussieht !

kopf
ende
Element 1

Element 1 ist das erste Object, was dann vom "main" Prog. übergeben wird.

Wo könnte der Fehler denn liegen? Ist es vllt der Fall, dass ich zwar die Adresse tausche, aber nicht gleichzeitig auf den neues Inhalt verweise, was ich mir aber nich wirklich vorstellen kann!

Gebt mir mal bitte einen Tipp!

Danke
Reen

 

[SlaterB]

geniale Idee, neben den (eindeutigen!) NAMEN der Knoten auch noch deren Hashcode zu betrachten,
komplizierter gehts ja kaum..
----

davon abgesehen, was ist das Problem?
wo sollte das neu eingefügte Element hin wenn nicht ans Ende?

und du schreibst ja auch 'Adresse vom neuKnoten mit Ende Knoten tauschen'
was danach klingt, dass neuKnoten ans Ende soll?

und du führst ja auch genau die Schritte aus, die den neuKnoten genau ans Ende setzen,
alles paletti?

-------

class Kette
{
    public Knoten kopf = new Knoten("kopf");
    public Knoten ende = new Knoten("ende");


    public Kette()
    {
        kopf.naechster = ende;
        ende.naechster = null;
    }

    public void fuegeNach(Object neuObj)
    {
        System.out.println("Kopf: " + kopf);
        System.out.println("Ende: " + ende);

        Knoten neuKnoten = new Knoten(neuObj);
        Knoten aktueller_neuKnoten = neuKnoten;

        System.out.println("\nneu : " + neuKnoten);


        neuKnoten = ende;
        neuKnoten.naechster = aktueller_neuKnoten;
        ende = aktueller_neuKnoten;

        System.out.println("\nAdresse vom neuKnoten mit Ende Knoten tauschen\n");
        System.out.println("neu : " + neuKnoten);
        System.out.println("Ende: " + ende);
    }

    public void ausgeben()
    {
        Knoten aktuellerKnoten = kopf;

        while (aktuellerKnoten != null)
        {
            System.out.println(aktuellerKnoten.getSingleDescription());
            aktuellerKnoten = aktuellerKnoten.naechster;
        }
    }


    public static void main(String[] params)
    {
        Kette liste = new Kette();
        System.out.println("Liste vor einfügen: ");
        liste.ausgeben();

        liste.fuegeNach("Element 1");

        System.out.println("\nListe nach einfügen: ");
        liste.ausgeben();
    }


    class Knoten
    {
        public Knoten naechster;
        public Object element;

        public Knoten(Object obj)
        {
            element = obj;

        }

        public String getSingleDescription()
        {
            String info = "Knoten, Inhalt: " + (element == null ? "leer" : element.toString());
            return info;
        }

        public String toString()
        {
            return getSingleDescription() + "  ----  naechser: " + 
               (naechster == null ? "null" : naechster.getSingleDescription());
        }

    }


}

 

[Reen]

Moin...

Ich meinte das so, dass das neu eingefügte Element genau zwischen "Kopf" und "Ende" Knoten soll.

Also in Form von

Kopf
Element 1
Element 2
usw.
Ende

Das war eigentlich mein Anliegen. Kam vllt nich so deutlich rüber. Sry

Warum ist das Kompliziert, die Hashadressen zu betrachten. Meiner Meinung nach kann man ja dann zumindest sehen, an welchen Adressen die Objekte im Speicher liegen und wie man was tauschen kann :?

mfg
Reen

PS: Nich gleich aufregen, weil irgendwas zu kompliziert ist. Bin schließlich noch Java Anfänger.

 

[SlaterB]

ja, aber jeder Knoten hat doch einen Inhalt,
ist doch viel leichter wenn da steht 'hier ist Element 1' also was da steht 'hier ist Element df8907s9' und ich noch nicht weiß, ob das kopf, ende oder Element 1 ist

> Nich gleich aufregen, weil irgendwas zu kompliziert ist. Bin schließlich noch Java Anfänger

mich kann nichts schocken, ich zeige dir nur was man alles falsch machen kann und was das für Folgen hat,
erst nachdenken, dann programmieren

und ist natürlich nur eine Meinung, manche finden Hashcode eben schicker

-----

also zum Zwischeneinfügen hast du bisher noch nichts gemacht,
darüber kann man nun nachdenken

wo soll es denn hin wenn die Liste 10 Elemente hat?
genau in die Mitte oder eins nach Anfang oder eins vor Ende?
letzteres klingt ja noch am besten,

da brauchst du nun das Element VOR ende,
mit einer doppelt verketteten Liste könntest du den 'vorgaener' von Ende abfragen,
hast du aber nicht, also musst du bei kopf anfangen und die ganze Liste durchlaufen und dir jeweils den Vorgänger merken bis du am Ende bist,

dann ist doch nicht schwer:
dieser Vorgaenger zeigt in seiner naechster-Referenz auf das neue Element (vorher auf ende),
das neue zeigt bei naechster auf ende (vorher auf gar nix)

ende selber musst du überhaupt nicht verändern oder neusetzen

 

[Reen]

Oki...danke. Werde ich ma versuchen.

Eins musst du mir aber nochma verraten. Du hast die Funkt. Knoten um zwei Funktionen erweitert, aber an keiner Stelle im Prog. rufst du diese Funktion auf. Trotzdem werden diese abgearbeitet.

Über welchen Umweg ruft dann Java diese Funkt. auf?

thx

 

[SlaterB]

toString ist eine Standard-Operation

System.out.println("Kopf: " + kopf);
=
System.out.println("Kopf: " + kopf.toString()); // wenn nicht null



normalerweise liefert sie Klassenname + Hashcode: Knoten@119c082

 

[Reen]

Dangöööööö

Sowas muss man auch erstma wissen :wink:

 

[NTB]

Ich fand die Betrachtung der Hashcodes jetzt nicht so schlimm, aber man sieht einfach schneller, was man macht, wenn man sich eine vernünftige Ausgabe bastelt.

Ein Tip, was mir dazu einfällt: Wenn Du sowas baust, mal Dir auf jeden Fall ein Bild mit den Objekten und was Du mt den Zeigern machen willst etc und arbeite dann Dein Bild in Programmcode um. Das hilft enorm, weil man sich das dann einfach besser vorstellen kann.

Edit:
So wie das da z.B.
http://www.peter-junglas.de/fh/vorlesungen/algorithmen/images/bild18.gif