Verkettete Liste

Danke!

Der Lehrer sagte wie sollen das folgende Unterprogramm fertigstellen, da es so noch nicht ganz funktioniert:

Zeile 30-34 fügen ja den neuen Spielzug ein.
Aber Zeile 37-39 macht ja alles kaputt wieder oder?
Was soll man damit bezwecken?

C++:
spielzug* insert_before(spielzug * liste, spielzug * element_before, spielzugfile * neuer_zug)
{
	spielzug* act_spielzug = NULL;

	if (element_before == NULL)
	{
		fprintf(stderr,"element position impossible(NULL)!");
		return(liste);
	}

  act_spielzug = (spielzug* )malloc(sizeof(spielzug));
	if (act_spielzug == NULL) 
	{
		exit(-1);
	}

	act_spielzug->posx=neuer_zug->posx;
	act_spielzug->posy=neuer_zug->posy;
	act_spielzug->zeichen=neuer_zug->zeichen;
	act_spielzug->next=NULL;
	act_spielzug->prev=NULL;

	if (liste == NULL)
	{
		liste = act_spielzug;
	}

  else
	{
		act_spielzug->prev=element_before->prev;
    act_spielzug->prev->next= act_spielzug;

		element_before->prev=act_spielzug;
		act_spielzug->next = element_before;

		
		act_spielzug->next = liste;
		liste->prev = act_spielzug;
		liste = act_spielzug;
	}
  return(liste);
}
 
Zuletzt bearbeitet:
Weißt du, was diese Funktion zurückgeben sollte? Also einen Pointer auf das eingefügte Element oder einen Pointer auf den Anfang der Liste oder was? Und wird der im main() irgendeinem Pointer zugewiesen? Könntest du vielleicht mal einen Aufruf im main() zeigen?

Lg
 
Das Blöde ist es ist noch nicht aufgerufen und ich würde sagen es wird der 1. Spielzug zurückgegeben.

spielzug * liste wird übergeben --> 1. element.

Aber das alles ergibt dann keinen Sinn....
 
Aber du hast Recht, die letzten 3 Zuweisungen sind wirklich nutzlos. Wenn du sie weglässt sollte alles funktionieren.
Du sagtest bei deinem Post, dass ihr noch etwas ändern müsst, weil noch nicht alles funktioniert. Was funktioniert denn noch nicht?

Lg
 
Ah jetzt fällt es mir wieder ein :)

Es kann ja auch passieren das der Kunde den Spielzug vor dem 1. einfügen will, und das machen die 3 Zeilen oder?

Jetzt muss ich nur noch schaun das ich die Zeilen getrennt behandle...
 
Hallo,

ich versuche gerade hinzubekommen wie man bei einer doppelt Verketteten Liste Elemente vertauscht.
Den Algorithmos für das vertauschen müsste ich schon haben, aber da gibt es ja Sonderfälle, die ich im Programm zeige.
Da muss ich dann in meinem Fall 5mal den gleichen Code-Vertausch-Abschnitt benutzen oder?
Kann man das nicht einfacher machen?

Wenn so ein Sonderfall eintritt, dann kann ich den unteren Teil des geposteten Codes vergessen, da ich nämlich das element bevor change1/2 oder danach sichere --> wenn aber change 1=1. element, dann ist in dem Fall before1=NULL und before1->next=temp, kann ich dann net machen.

C++:
spielzug* change_pointer(spielzug* liste, spielzug* change1, spielzug* change2) //liste zeigt auf das 1. Element der Kette, change1 zeigt auf das element in der kette das mit einen anderen Element in der kette, wo change2 draufzeigt, vertauscht werden muss
{
  spielzug* after1 = NULL;//element nach change1
  spielzug* before1 = NULL;//element bevor change1
	spielzug* after2 = NULL;//element nach change2
  spielzug* before2 = NULL;//element bevor change2
	spielzug* temp = NULL;//pointer zum zwischenspeichern von change2
	
  //4 Sonderfälle:
	if(change1->next == NULL)//es kann ja sein das change1 auf das letzte Element zeigt --> es gibt kein element danach
	{
	  before1=change1->prev;
	}

	if(change2->next == NULL)//es kann ja sein das change1 auf das letzte Element zeigt --> es gibt kein element danach
	{
	  before2=change1->prev;
	}

	if(change1->prev == NULL)//es kann ja sein das change1 auf das erste Element zeigt --> es gibt kein vorheriges Element
	{
	  after1=change1->next;
	}

	if(change2->prev == NULL)//es kann ja sein das change2 auf das erste Element zeigt --> es gibt kein vorheriges Element
	{
	  after2=change1->next;
	}

  /* hier wird zwischen gespeichert, da später das verloren geht */
  before1 = change1->prev;
	after1 = change1->next;
	before2 = change2->prev;
	after2 = change2->next;
	temp=change2;

	//von hier 
  before2->next = change1;
	change1->prev = before2;
	change1-next = after2;
	after2->prev = change1;
	
	before1->next = temp;
	temp->prev = before1;
	temp->next = after1;
	after1->prev = temp;
  // bis hier, werden die Elemente vertauscht also wenn Change 1/2 nicht auf den ersten oder letzten wert der kette zeigen


	return();
}

Gruß
 
Hallo,

so sollte es klappen (ungetestet):

C:
spielzug* change_pointer(spielzug* liste, spielzug* change1, spielzug* change2)
{
    spielzug* temp;

    if (change1 == change2) {
        // Sonderfall: nichts zu tun bei selbem Element
        return liste;
    }

    // Nachbarn tauschen
    temp = change1->next;
    change1->next = change2->next;
    change2->next = temp;

    temp = change1->prev;
    change1->prev = change2->prev;
    change2->prev = temp;

    // Neue Nachbarn informieren
    if (change1->next) {
        change1->next->prev = change1;
    }
    if (change1->prev) {
        change1->prev->next = change1;
    }

    if (change2->next) {
        change2->next->prev = change2;
    }
    if (change2->prev) {
        change2->prev->next = change2;
    }

    // Neuen Kopf der Liste ermitteln
    if (change1->prev == NULL) {
        return change1;
    } else if (change2->prev == NULL) {
        return change2;
    } else {
        return liste;
    }
}

Grüße,
Matthias
 
Das Programm vertauscht nur Nachbarn oder? Die ifs verstehe ich leider nicht. Warum verlgeicht man nix miteinander? "==, <=,> etc."? Was machen den deine ifs?
 
Das Programm vertauscht nur Nachbarn oder?
Die Funktion vertauscht die Nachbarn der zu vertauschenden Elemente, womit diese effektiv ihre Position in der doppelt verketteten Liste tauschen. Mach dir am besten mal ein Beispiel auf Stift und Papier und vollziehe nach, was passiert.

Die ifs verstehe ich leider nicht. Warum verlgeicht man nix miteinander? "==, <=,> etc."? Was machen den deine ifs?
Du kannst dir bei diesen Abfragen ein != NULL hinzudenken, das ist äquivalent.

Grüße,
Matthias
 
Zurück