Eine verkettete Liste

Status
Nicht offen für weitere Antworten.

avikop08

Mitglied
Hallo an alle,

leider komme ich mit der Aufgabe unten nicht klar 🙁

Das Programm unten ist der Ausgangspunkt. Jetzt muss ich das Programm so erweitern, dass das Listenende beim Anhängen nicht immer wieder neu ermittelt werden muss, sondern neue Elemente am Ende der Liste angehängt werden können.
Aber wie soll das gehen?
ich würde mich freuen, wenn jemand von Euch bei dieser Aufgabe helfen könnte.

Ich bedanke mich im Voraus :lol:
Avi


Code:
/*######################################
 * Eine verkettete Liste Version 2
 ######################################*/

//die Klasse für die Listenelemente
//jetzt auch mit Methoden
class Listenelement {
		String daten;
		Listenelement naechster;

		//die Methode zum Setzen der Daten
		void setDaten(String datenNeu) {
			//die Zeichenkette setzen
			daten = datenNeu;
			//das Ende markieren
			naechster = null;
		}

		//die Methode zum Anhängen eines neuen Elements
		//sie ruft sich rekursiv auf, bis das Ende erreicht ist
		void anhaengen(String datenNeu) {
			//wenn das Ende erreicht ist, ein neues Element erzeugen
			if (naechster == null) {
				naechster = new Listenelement();
				naechster.setDaten(datenNeu);
			}
			//sonst ruft sich die Methode selbst wieder auf
			else
				naechster.anhaengen(datenNeu);
			//nur zur Veranschaulichung
			System.out.println("Daten " + datenNeu + " wurden eingefügt.");
		}

		//die Methode zur Ausgabe der Liste
		//sie ruft sich ebenfalls rekursiv auf, bis das Ende erreicht ist
		void ausgeben() {
			System.out.println(daten);
			if (naechster != null)
				naechster.ausgeben();
		}
	}

public class Java05_10 {
	public static void main(String[] args) {
		//ein neues Listenelement erzeugen
		Listenelement listenAnfang = new Listenelement();

		//die Daten im ersten Listenelement setzen
		listenAnfang.setDaten("Element 1");

		//weitere Elemente in einer Schleife einfügen
		for (int element = 2; element < 4; element++)
			listenAnfang.anhaengen("Element " + element);

		//die Liste ausgeben
		listenAnfang.ausgeben();
	}
}

Edit Illuvatar: Code-Tags FTW
 
die wahrscheinlich einfachste variante ist es, der klasse einen statischen member zu verpassen, der immer auf das letzte element der liste zeigt.

wenn jetzt ein neues element angehängt werden soll, so wird entsprechend eine neue instanz erzeugt, diese als 'naechster' des aktuell letzten elements gesetzt und das neue letzte element dem statischen feld zugewiesen.

du musst dabei dann allerdings bedenken, dass diese variante nur dann funktioniert, solange stets nur eine "hauptinstanz" der liste existiert 😉 wenn das unerwünscht ist, dann würd ich nen wrapper um die derzeitige implementierung setzen, der solche informationen vorhält.
 
mit nur einer Klasse ist das schlecht,
du müsstest für alle Listenelemente ein neues Attribut 'letztesListenElement' einführen,
was nur das Anfangs-Element effektiv nutzt, um sich das letzte Element zu merken

besser ist es, eine zweite Klasse Liste zu bauen,
mit Referenzen auf das erste und letzte Element der Liste,

edit: zum statischen Element: dann kann es im ganzen Programm nur eine Liste geben
 
Danke für alle Antworte. wow das geht hier aber sehr schnell.

Aber leider sind alle Vorschläge, wie sie formuliert wurden,zu hoch für mich und ich bräuchte konkretere Beispiele, die ich in das Programm einbauen könnte.

Danke
 
Code:
class Liste
{
  private Listenelement last;
  
  public anhaengen( String daten )
  {
     this.last.anhaengen( daten );
     this.last = this.last.naechster;
  }
}

minimalbeispiel, funktioniert so natürlich noch nicht korrekt.
 
Hallo Janus,

könnest Du bitte mein Programm so ändern, wie es in der Aufgabe verlangt. Danach werde ich es über Ostern lernen.

Danke
avikop08
 
Hallo Janus,

ich habe versucht es umzusetzen, wie Du mir geschrieben hast und bin dabei leider nicht weiter gekommen. Ich wollte Dich nicht alle paar Sekunden mit weiteren Fragen nerven.

Danke trotzdem
avikop08
 
Poste deinen aktuellen Stand (am besten ein compilierbares Beispiel) und beschreibe genau, was du dir bei dem, was du gemacht hast, gedacht hast, und beschreibe, was nicht funktioniert ....
 
Hallo Marco13,

ich kann mit dieser Aufgabe nichts anfangen und mir ist wichtig vor allem zu wissen, wofür diese Aufgabe gut ist und was passiert, wenn man sie richtig gelöst hat(wie sieht die Ausgabe aus). Ich versuche nicht Freiwillige, die für mich die Arbeit machen, wie man angedeutet hat. Ich habe mich heute bei dieser Forum registriert, damit ich was lernen kann.

Danke
 
Hallo,

gibt es jemanden in dieser Forum, der diese "einfache" Frage beantworten kann.
Bitte nur vollständige Lösung und keine einzelnen Sätze. Ich Frage, weil ich das nicht kann.

Danke
 
du zeigst kein bestreben, die vorschläge anzuwenden, um das problem aus eigenem antrieb zu verstehen. stell konkretere fragen, poste codeteile, zeig ansätze, dann wird dir auch geholfen.
 
ich habe ganz klar formuliert, was ich erwarte. Wenn man mir nicht helfen möchte, weil man denkt, dass ich nicht genug fleißig bin, dann bin ich vielleicht falsch in dieser Forum. Aber ich lasse mich überraschen.
 
avikop08 hat gesagt.:
ich kann mit dieser Aufgabe nichts anfangen und mir ist wichtig vor allem zu wissen, wofür diese Aufgabe gut ist und was passiert, wenn man sie richtig gelöst hat(wie sieht die Ausgabe aus).
Die Ausgabe ist eigentlich die gleiche, wie wenn man das Listenende jedesmal neu sucht. Der Unterschied liegt im Laufzeitverhalten: Wenn man annimt, das es 1 Sekunde kosten würde, einen "Schritt" entlang der Liste zu machen, und 0.1 Sekunden, ein Element anzuhängen, dann würde das bei der ALTEN Version beim Einfügen von 7 Elementen bedeuten:
1. Element einfügen: 0.1 Sekunden
2. Element einfügen: Direkt ans 1. Hängen, 0.1 Sekunden
3. Element einfügen: 1 "Schritt" zum 2. Element machen, daran das neue anhängen: 1.1 Sekunden
4. Element einfügen: 2 "Schritte" bis zum 3. Element machen, daran das neue anhängen: 2.1 Sekunden
5. Element einfügen: 3 "Schritte" bis zum 4. Element machen, daran das neue anhängen: 3.1 Sekunden
6. Element einfügen: 4 "Schritte" bis zum 5. Element machen, daran das neue anhängen: 4.1 Sekunden
7. Element einfügen: 5 "Schritte" bis zum 6. Element machen, daran das neue anhängen: 5.1 Sekunden

Insgesamt hätte das Aufbauen der Liste mit 7 Elementen dann also 0.1+0.1+1.1+2.1+3.1+4.1+5.1 = 15.7 Sekunden gedauert. Die Laufzeit ist quadratisch, (also "O(n²)") d.h. wenn man "viele" Elemente einfügen will, dauert das unerträglich lange. Ganz grob: Wenn man die Anzahl der Elemente, die eingefügt werden, verdoppelt, dann vervierfacht sich die dafür benötigte Zeit.

Bei der NEUEN Version, wo man immer direkt ans Ende anhängen kann, würde das Einfügen von 7 Elementen so ablaufen:

1. Element einfügen: 0.1 Sekunden
2. Element einfügen: Direkt ans 1. Hängen, 0.1 Sekunden
3. Element einfügen: Direkt ans letzte eingefügte hängen: 0.1 Sekunden
4. Element einfügen: Direkt ans letzte eingefügte hängen: 0.1 Sekunden
5. Element einfügen: Direkt ans letzte eingefügte hängen: 0.1 Sekunden
6. Element einfügen: Direkt ans letzte eingefügte hängen: 0.1 Sekunden
7. Element einfügen: Direkt ans letzte eingefügte hängen: 0.1 Sekunden

Insgesamt hätte das Aufbauen der Liste mit 7 Elementen dann also nur 0.7 Sekunden gedauert. Die Laufzeit ist linear (also "O(n)"), d.h. wenn man die Anzahl der Elemente, die eingefügt werden, verdoppelt, dann verdoppelt sich die dafür benötigte Zeit (aber sie vervierfacht sich nicht, wie bei der ersten Lösung)

avikop08 hat gesagt.:
Ich habe mich heute bei dieser Forum registriert, damit ich was lernen kann.
Vielleicht hat das ja funktioniert :wink: Wenn du noch mehr zu dieser Frage (Laufzeitverhalten und Komplexität von Algorithmen) dann ist das hier vielleicht ein guter Startpunkt: http://de.wikipedia.org/wiki/Landau-Symbole

Konkrete Fragen kannst du aber auch immer hier posten.

(Code? Welcher Code?)
 
Danke Marco13,

Du hast mir das Prinzip super erklärt.

Ich soll das Anhängen jetzt so ändern, dass das aktuelle Ende der
Liste gespeichert wird und die Liste beim Anhängen nicht immer wieder von Anfang an durchlaufen werden muss. ich muss also dafür sorgen, dass ich das
aktuelle Ende der Liste zwischenspeichern kann und dann dieses Ende beim Anhängen eines neuen Elements benutze. Dadurch wird das Anhängen sehr viel schneller.

Aber ich weiss einfach nicht, was ich an dem Programm ändren bzw. wie ich das Programm erweitere damit die Elemente direkt am Ende angehängt werden. 🙂
 
Bräuchte ich eine zusätliche Klasse oder die vorhandenen Klassen reichen?

Aber ich weiss es nicht, wie ich die theoretische Erklärung von Marco13 im Programm umsetze.

class Listenelement {

}



public class Java05_10 {
public static void main(String[] args) {
//ein neues Listenelement erzeugen
Listenelement listenAnfang = new Listenelement();


}
}
 
> Bräuchte ich eine zusätliche Klasse oder die vorhandenen Klassen reichen?

lies noch mal die ersten beiden Antworten durch,
Janus hat dir sogar schon die neue Klasse halb hingeschrieben..
 
Bräuchte ich eine zusätliche Klasse oder die vorhandenen Klassen reichen?

Eine zusätzliche Klasse wäre wohl sinnvoll. Vielleicht GENAU SO EINE, die Janus sie beschrieben hat!? :roll:
Janus hat gesagt.:
Code:
class Liste
{
  private Listenelement last;
  
  public anhaengen( String daten )
  {
     this.last.anhaengen( daten );
     this.last = this.last.naechster;
  }
}
 
class Liste
{
private Listenelement last;

public anhaengen( String daten )
{
this.last.anhaengen( daten );
this.last = this.last.naechster;
}
}

Wofür ist diese Klasse gut? wie kann ich sie mit meinem Programm kombinieren?
 
Die Klasse speichert das letzte Listenelement, und kann mit deinem Programm kombiniert werden, indem du zum Anfügen neuer Elemente nichtmehr die Methode
void anhaengen(String datenNeu) {
aus der Klasse "Listenelement" verwendest, sondern die Methode
public void anhaengen( String daten )
aus der Klasse "Liste". Dazu muss die Klasse aber noch ein bißchen erweitert werden (z.B. muss man sich überlegen, was in der Methode passieren soll, wenn noch keine Listenelmente vorhanden sind).
 
Ähm... Also, ich würde hier gerne folgendes anmerken:
Beim Programmieren geht es nicht darum, code einzutippen, das ist eher nebensächlich. Zuerst musst du verstehen was du überhaupt tun willst.

Ich glaube ich hätte hier einen ziemlich guten beispiel.



Du befindest dich in einem absolut abgedunkelten Raum.

Auf dem Boden sind lauter farbige büroklammer verstreut. Überall. manche sind zu klumpen und ketten verknüpft, es herrst ein totales durcheinander. Das soll symbolisch den flüchtigen speicher deines PC's darstellen. Mit dem ganzen inhalt kannst du nichts anfangen.

Jetzt bekommst du aber eine Aufgabe. Da kommt ein programmierer an und sagt dir "Du musst jetzt eine Liste verwalten".

Eine Liste wird symbolisch durch eine Kette aus büroklammern einer ganz besonderen Farbe repräsentiert.

Jetzt fängt irgendein Programm an, dir diese besonderen klammer an den Kopf zu schmeißen.
Was brauchst du mindestens, um eine solche Kette aus klammern zu verwalten?

Du weißt:
-du kannst zwei klammer verknüpfen. Wenn du eine Klammer aus der kette in der Hand hast, kannst du auch auf die nächste klammer zugreifen.
-du musst wenigstens die erste klammer in der hand halten. Wenn du gar keine klammer mehr in der Hand hälst, fällt die Kette auf den boden, und du hast keine möglichkeit mehr, die elementen der kette von allen anderen klammern zu unterscheiden. Der garbage collector kommt angekrochen und verspeist genüsslich die kette aus den ganzen klammern. Du kannst nur sabbergeräusche in der Dunkelheit hören...


Also braucht man zumindest mal folgendes, um die "kette nicht zu verlieren", um die liste irgendwie zusammenzuhalten:
Code:
public class Liste{
    
    //Listenelement=Büroklammer
    private static class Listenelement{
        private Listenelement next; //referenz zum nächsten element=verbindung zur nächten klammer
    }

    //Das erste Listenelement= die erste büroklammer, die du in der hand hältst
    private Listenelement first;
}


Bis jetzt bist du jedoch nur in der lage, die kette einfach nur zu halten. Du musst ja noch elemente anhängen können. Die erste Idee, die dir in den sinn kommt ist folgende:
Wenn du eine klammer anhängen musst, fängst du mit der ersten klammer an, findest die nächste klammer, wenn es nicht das ende der kette ist, suchst du dir die nächste klammer usw. usw. usw. bis du das ende der kette gefunden hast. Dort hängst du die klammer an. Das war der Ansatz bei dem code den du gepostet hast.

Das läuft anfangs ganz gut, aber als die kette etwa siebzehn kilometer lang wird, stellst du fest, dass es eigentlich recht zeitaufwendig ist, die ganze kette jedesmal durchzugehen und das ende zu suchen.

Und da kommt die die unglaublich geniale idee, dass du das ende der kette nach dem anhängen eines elementes nicht einfach in die Dunkelheit schmeißt, sondern stattdessen das ende der Kette von anfang an immer in der hand hälst.

Wenn du jetzt ein element anhängen musst, musst du die letzte klammer nicht mehr suchen. Du hängst einfach das neue element da dran, das wird dann auch gleich das neue ende deiner kette sein.


Hiermit erhälst du auch den code:
Code:
public class Liste{
    
    //Listenelement=Büroklammer
    private static class Listenelement{
        public Listenelement next; //referenz zum nächsten element=verbindung zur nächten klammer
        //constructor etc...
    }

    //Das erste Listenelement= die erste büroklammer, die du in der hand hältst
    private Listenelement first;
    //Das ende der Kette auch mitspeichern
    private Listenelement last; 

    public anhaengen( String daten ){ 
        Listenelement temp=new Listenelement(daten);
        last.next=temp;
        last =temp;
    } 
}

So, jetzt ist die idee da, bleibt nur noch ein wenig langweilige schreibarbeit...
 
Hallo Andrey,

danke für dein beispiel und deine mühe.

ich erhalte zwar viele ideen, die scheinbar sehr nützlich sind aber ich weiss nicht, wie ich es in mein programm einbauen kann, damit es funktioniert.

ich schaffe es leider nicht die vorschläge auf mein programm zu übertragen.
 
Hallo ich habe einen anderen Ansatz gestartet:
ich habe jetzt noch eine weitere Variable zu daten und nächster hinzugefügt: static Listenelement letzter
Immer wenn ich beim Anhängen beim letzten Element bin (nächster == null) dann muss ich auch das neue hinten angefügte Element wieder als neues letztes Element setzen.

Dann habe ich einen Konstruktor (public ListenElement() {...}) eingeführt denn wenn das erste Element erstellt wird ist es somit auch das letzte und die neue Variable muss auf sich selbst gesetzt werden!! (Also wenn im Konstoruktor das LetzteListenElement == null dann ist das erzeugte Objekt das erste erzeugte Objekt und somit Anfang und Ende der Liste..)

Trotzdem hat sich bei der Ausgabe nichts geändert. Woran liegt das?




Code:
class Listenelement {      
	String daten;      
	Listenelement naechster;      
	static Listenelement letzter; //neue Variable            
	//Konstruktor    
	public Listenelement() {       
		if (letzter == null)   
			letzter = this;    
	}    
	void setDaten(String datenNeu) {              
		daten = datenNeu;          
		naechster = null;     
	}      
	void anhaengen(String datenNeu) {         
		if (naechster == null) {         
			naechster = new Listenelement();    
			naechster.setDaten(datenNeu);            
			letzter = naechster;  //Variante 1       
		}                  
		else           
			naechster.anhaengen(datenNeu);               
			System.out.println("Daten " + datenNeu + " wurden eingefügt.");   
	}     
	void ausgeben() {        
		System.out.println(daten);         
		if (naechster != null)            
			naechster.ausgeben();       
	} 
} 
public class Java05_10 {  
		public static void main(String[] args) {        
					Listenelement listenAnfang = new Listenelement();      
					listenAnfang.setDaten("Element 1");            
					for (int element = 2; element < 4; element++)         
						listenAnfang.anhaengen("Element " + element);       
					listenAnfang.ausgeben();   
		}
}
 
nur weil du irgendwo eine statische Variable definierst, ändert sich doch nicht per Zauberhand irgendwas in deinem Programm?

und von der Ausgabe ist doch zum ersten Mal die Rede?
niemand weiß
a) wie die Ausgabe vorher war
b) wie sie nun ist
c) wie du haben willst
d) was irgendeine der statischen Variablen in deinem Programm oder sonstwo auf der Welt damit zu tun hat

also: Genauigkeit ist machmal hilfreich 😉
 
Wenn man das Programm ausführen lässt, dann weiss man, was dabei rauskommt. Was ich möchte, steht in meiner Frage ganz am Anfang.
 
Du hast am code nichts wesentliches verändert, also ändert sich auch nichts an der ausgabe, was hast du denn sonst erwartet?

Du musst die lahme rekursive "anhaengen()" methode durch eine schnelle statische ersetzen... sind etwa 3 zeilen, und die stehen auch schon mehrfach in den ganzen anderen beiträgen...
Dann ist die Aufgabe quasi erfüllt... Was da raus kommt ist natürlich eine völlig unbrauchbare implementierung einer Liste, aber da musst du dich bei demjenigen beschweren, der sich diese aufgabe ausgedacht hat... :roll:
 
> Jetzt muss ich das Programm so erweitern, dass das Listenende beim Anhängen nicht immer wieder neu ermittelt werden muss, sondern neue Elemente am Ende der Liste angehängt werden können.

ohne dich nerven zu wollen: inwiefern würde sich dadurch die Ausgabe denn ändern?

abgesehen von der Ausgabe zur eigentlichen Frage:
nur das Element letzte zu definieren bringt dir nicht viel Ruhm und Ehre,
in der Operation anhaengen() musst du diesen neuen Anker auf verwenden,
nicht mehr auf naechster schauen usw. sondern direkt an letzter ranhängen
 
Hallo Marco13

die Klasse bzw. die Methode anhaengen, die Du mir empfohlen hast, weist bei mir Fehler auf. Das Wort anhaengen wir rot markiert.
 
Dann ist es kein denkfehler im programm sondern ein syntaxfehler=> zählt meistens nicht als fehler, sondern soll als schreibhilfe angesehen werden...
 
Spielt keine Rolle. Tatsache funktioniert das Ganze nicht. Langasam frage ich mich, ob es jemanden gibt, der diese Aufgabe lösen kann. Denn ich kann mir kaum vorstellen, dass man mich zappeln lassen würde.
 
Wenn es "rot markiert" wird, nehme ich mal an dass du Eclipse o.ä. verwendest. Bei den fehlern, die rot angestrichen werden, erscheinen links oder rechts kleine markierungen, wenn man mit der maus darüberscrollt, erscheinen fehlerbeschreibungen, und evtl sogar verbesserungsvorschläge... Wenn es rot angestrichen wird, dann heißt es dass du es einfach nur falsch eingetippt hast, dass eine solche methode beispielsweise gar nicht existiert, oder vielleicht andere argumente erwartet...

Wie sollen wir dir denn helfen, wenn du was falsch eingetippt hast? Soll einer schnell vorbeikommen es richtig eintippen oder wie? :wink:

Außerdem verstehe ich nicht, warum du dich auf den code von Marco 13 beziehst... Sein letztes Beispiel wies eine ziemlich andere programmstruktur auf, die hier mehrmals vorgeschlagen wurde, die du aber aus irgendwelchen gründen nicht übernehmen möchtest (nun gut, das wäre ja auch sowas wie aufgabenstellung abändern, da können die leute hier auch nix für, wenn die aufgabe merkwürdig gestellt ist...)

avikop08 hat gesagt.:
Langsam frage ich mich, ob es jemanden gibt, der diese Aufgabe lösen kann
[lol] komm Marco13, gibs doch zu, du kannst es auch nich 😛 [/lol]
 
avikop08 hat gesagt.:
die Klasse bzw. die Methode anhaengen, die Du mir empfohlen hast, weist bei mir Fehler auf. Das Wort anhaengen wir rot markiert.

Wenn du nicht auf die Idee gekommen bist, aus dem
public anhaengen(...)
ein
public void anhaengen(...)
zu machen, solltest du dir nochmal ein Grundlagenbuch ansehen.

Ich halt' mich hier jetzt raus. Wird mir zu trollig. :roll:
 
soweit war ich auch. Hat Du überhaupt versucht für dich es zu lösen oder Du machst Vorschläge ohne zu wissen, ob es überhaupt gehen sollte.
 
- ich kanns nicht
man könnte es so lösen
- ich kanns nicht
guck hier, so
- ich kanns nicht
hier sind details
- ich kanns nicht
hier ist eine fast vollständige lösung
- ich kanns nicht
wo hakts?
- du bist doof

hast ne tolle art, fragen zu stellen
 
Janus hat gesagt.:
- ich kanns nicht
man könnte es so lösen
- ich kanns nicht
guck hier, so
- ich kanns nicht
hier sind details
- ich kanns nicht
hier ist eine fast vollständige lösung
- ich kanns nicht
wo hakts?
- du bist doof

hast ne tolle art, fragen zu stellen
lol!
 
Status
Nicht offen für weitere Antworten.

Neue Themen


Zurück
Oben