Einfach verkettete Liste umdrehen

[paco89]

hallo, ich habe folgende aufgabe versucht zu lösen:

Betrachten sie eine nicht gewordnete, lineare Liste, deren elemente Instanzen der Klasse Element sind.
Schreiben Sie je eine rekursive und nicht-rekursive methode, die die reihenfolge der elemente innerhalb einer liste umkehrt.

also die klasse element sieht so aus:

public class Element 
{
	int wert;
	Element weiter;
	
	public Element(int i)
	{
		wert = i;
		weiter = null;
	}
}

eine klasse Liste habe ich dann dazu so definiert:

public class Liste
{
	Element kopf;
	
}

sie entählt also nur ein attribut kopf, welches auf das 1. element der liste zeigt. das letzte element der liste zeigt auf null.
nun: ich habe schon mal versucht die rekursive methode in einer klasse Reverse zu implementieren:

ublic class Reverse 
{
	public List reverse()
	{
			return new Liste (reverse(kopf));
	}
	
	private static Liste reverse(Element a)
	{	
		
		if(a == null)
			return null;
		
			
	}

aber wie immer kam ich nur bis zum trivialen fall, dass der kopf auf null zeigt, also was passiert, wenn die liste leer ist. zu den anderen fällen hatte ich zwar ideen, aber an der umsetzung hats gescheitert. zum beispiel wäre die aufgabe schnell gelöst, wenn ich zusätzlich noch ein attribut vorgaenger hätte, das auf das vorherige element zeigt. aber das habe ich ja hier nicht.

als letztes hatte ich mir überlegt, dass ich mit kopf.weiter die liste so lange durchlaufe bis ich auf das letzte element stoße (also das element, das auf null zeigt). das wird dann das erste element der neuen liste und danach entferne ich das element aus der usprungsliste, sodass das usprünglich vorletzte element, das letzte element wird. usw.

aber nachher fand ich diese idee auch zu kompliziert und...na ja....irgendwann kam ich an einen punkt wo ich fast aufgehört hab. deshalb wäre es echt super, wenn mir jmd. unter die arme greifen würde.

vielen dank schonmal im voraus...


lg

 

[Airborne]

ich verstehe den Sinn deines Objekt "Liste" da nicht ganz...

"Eine geordnete, lineare Liste" ist doch einfach eine List?
Nimmste halt eine ArrayList<Element>.

 

[Marcinek]

Nein. Das ist schon richtig im Sinne einer Aufgabe im ersten Semester Informatik.

Du hast mehrere Möglichkeiten.

1. Google. Die Aufgabe hat jeder Student gemacht.


2. Rekursiv durchgehen.

3. Beim durchlaufen neue liste bauen. Indem man die Elemente immer an den Kopf hinzufügt.
Dann gibt man die neue liste aus.

 

[M_Schaffrath]

Die Listenelemente sind ja so angelegt, dass jedes Element seinen Nachfolger kennt. Eine Liste aus fünf Elementen könnte dann so aussehen:

Element root = new Element(0);
root.weiter = new Element(1);
root.weiter.weiter = new Element(2);
root.weiter.weiter.weiter = new Element(3);
root.weiter.weiter.weiter.weiter = new Element(4);

Die Liste muss nicht explizit vorhanden sein, solange ich das erste Element habe und jedes Element seinen Nachfolger kennt, kann ich mich durch die Elemente "durchhangeln" bis ich das gesuchte Element habe.

// gib den Wert des x-ten Elements der Liste aus
Element tmp = root;
for(int i = 0; i < x; i++)
   tmp = tmp.weiter;
System.out.println(String.valueOf(tmp.wert));

 

[paco89]

ja, also die klasse List stand nicht in der aufgabenstellung. die habe ich selber geschrieben. ich hatte das in allen anderen aufgaben gesehen, die wir in der uni hatten. sie beinhaltet ja auch nur ein einziges Attribut , das auf das erste element der liste zeigt. so viel dazu.

ähm, ich werde dann mal schauen, was ich so alles im netz finde. vtl. sollte ich mal das ganze mit der nichtrekursiven methode beginnen, so kann ich mir das selber viel besser erklären. und erst dann die rekursion angehen.

vielen dank für die beiträge, hilfestellungen etc. im mom lerne ich für ne andere klausur. das programmieren mache ich immer dann , wenn ich mir ne pause gönne. deshalb könnte es eine weile dauern bis ich meine ergebnisse hier poste. bis dann....

 

[Firephoenix]

tipp zur rekursion:

-die umgekehrte leere liste ist die leere liste
-(die umgekehrte liste aus einem element ist wieder diese liste)
-die umgedrehte liste aus mehreren elementen ist die umgedrehte liste ohne das erste element konkateniert mit dem ersten element

Gruß

 

[faetzminator]

Ich würde das so schreiben:

neueListe = ... // neue, leere liste erstellen
aktuellesElement = neueListe.head = alteListe.head
solange nächstes element vorhanden
    aktuellesElement = nächstes element
    erzeuge neuesElement
    setze wert von neuesElement
    neuesElement.weiter = neueListe.head
    neueListe.head = neuesElement
gib neueListe zurück

Ok, ok, das lässt sich schon fast 1:1 in Java Code abtippen, aber ich bin halt nicht der Pseudocodeschreiber

 

[paco89]

Ich würde das so schreiben:

neueListe = ... // neue, leere liste erstellen
aktuellesElement = neueListe.head = alteListe.head
solange nächstes element vorhanden
    aktuellesElement = nächstes element
    erzeuge neuesElement
    setze wert von neuesElement
    neuesElement.weiter = neueListe.head
    neueListe.head = neuesElement
gib neueListe zurück

okay, verstanden....aber ganz zum schluss müsste ich doch den nachfolger von alteListe, was auf das erste element meiner usprünglichen liste zeigt auf null setzen, oder?

 

[paco89]

hallo, ich hab das jetzt in code abgetippt:

public Liste umkehren()
{
	Liste neueListe = new Liste(this.start);
	Element aktuell = neueListe.start = this.start;
	
	while(aktuell.nachfolger != null)
	{
		aktuell = aktuell.nachfolger;
		Element a = new Element(aktuell.wert, neueListe.start);
		neueListe.start = a;
	}
	
	return new Liste (a);
	
	}
}

so und jetzt muss ich das nur noch die rekursion schreiben....(falls das richtig sein sollte)