Listenalgorithmus (Rekursion)

[Indira]

Hey,

ich soll einen Algorithmus entwickeln, der das n-te Element einer doppelt verketteten Liste rekursiv löscht. Die Funktion soll als Eingabe die Liste und das n erhalten und als Ausgabe die Liste ohne das n-te Element zurückgeben.

Ich stehe leider völlig auf dem Schlauch. Wär super, wenn mir jemand helfen könnte. Ich muss ja 4 Fälle unterscheiden.

1.Liste leer bzw n<1

2.n=1 also Anfang wird gelöscht

3.n=listsize Ende wird gelöscht

4.Knoten in der Mitte wird gelöscht

Das ganze ohne einen rekursiven Funktionsaufruf zu schreiben ist nicht das Problem. Nur leider fällt es mir schwer mich in die rekursive Methodik reinzudenken.

Freue mich schon auf eure Antworten,

MFG Indira

[flashpixx]

Ich verweise einmal Teile und herrsche (Informatik) ? Wikipedia das sollte eigentlich weiter helfen

Die Punkte 1-3 sollten ja eigentlich leicht zu realisieren sein und Punkt 4 kann man nach obigen Verfahren durchführen und letztendlich dann auf 1, 2 oder 3 reduzieren. Wo allerdings der Sinn der Aufgabe ist, ist absolut nicht klar, denn für eine "lineare Datenstruktur" sollte man überlegen, ob eine Rekursion was den Aufwand angeht, überhaupt sinnvoll im Rahmen der Komplexität ist

Bearbeitet 11. Juli 2010 von flashpixx

[Indira]

Ich hab ja schon was nur irgendwie krieg ich den Rekursionsabbruch nicht hin.

LinkedList* deleteNode(LinkedList*l, unsigned int n){

n--;


if(head==NULL || n<0)

return NULL;


if(n==0) //erster Knoten wird gelöscht

node=head;

head=head.next;

head.prev=NULL;

delete node;

return l;


if(n==sizeoflist) //letzter Knoten wird gelöscht

node=tail;

tail=tail.prev;

tail.next=NULL;

delete node;

return l;


if(n==1)

node=l;

l=head;

node.prev->next=node.next;

node.next->prev=node.prev;

delete node;

return l


else

return deleteNode(l.next,n);

sieht schön aus, haut nur irgendwie nicht hin -.-

[lupo49]

Du verwurschtelst das n dort. Das n steht für das Element was gelöscht werden soll, laut deiner Aufgabenbeschreibung. In deinen IF-Abfragen nutzt du es aber so, als wenn dort die Länge der Liste enthalten wäre.

Mein Ansatz wäre so:

Bei jedem Rekursionsaufruf wird die Liste um das vorderste Elemente abgeschnitten und an neue Liste gepackt, wenn das vorderste Element gleich dem Element n ist, dann wird dieses übersprungen und das zweit-vorderste Element an die Liste gepackt.

[Indira]

nene n ist die Stelle bzw. Position des Elements. Nicht das Element selbst.

[lupo49]

Wenn du n dekrementierst bei jedem Methodenaufruf, dann stimmt die Positionsangabe nach zweiten Aufruf nicht mehr?

Bei der Rekursion musst du erarbeitet Teillösungen abspeichern. Du rufst nur deleteNode(..) auf, ohne dass der Rückgabewert verwendet wird.

Bearbeitet 11. Juli 2010 von lupo49

[Indira]

Jetzt bin ich raus.

Muss das leider bis morgen fertighaben.

Finde die Aufgabe an sich echt schwachsinnig, aber was will man machen.

Sitze schon Stunden dran und irgendwie will es nicht funktionieren.

[lupo49]

Dann schau dir bspw. mal in Java unter java.util.LinkedList an, wie dort die Methoden implementiert sind.

[Indira]

	


LinkedList *deleteNode(LinkedList *l,int n) {

		if (listsize == n + 1) {

			Linkedlist i;

			i = l;

			l = l.next;

                        delete l;

			return l;

		} 

               else {

			return l.deleteNode(l*,n);

		}

	}

Soo vielleicht? Ich bin mit Java nicht so konform. Programmiere ausschließlich in C++ und bin noch echt ein Newbie.

[lupo49]

Du brauchst das nicht in Java nachmachen, sondern dir die Logik anschauen, die dahinter steckt.