Einfach verkettete Liste - Elemente vertauschen - C / C++ / D

Einfach verkettete Liste - Elemente vertauschen

Beginner

Sunday, April 13th 2008, 11:41pm

Einfach verkettete Liste - Elemente vertauschen

Hallo!

Ich versuche gerade in C eine Funktion zu schreiben, die in einer einfach verketten Liste die jeweiligen Nachbarelemente vertauscht. Sie soll also beispielsweise aus: 1 2 3 4 5 6 => 2 1 4 3 6 5 machen. Ohne auf die Abbruchbedingungen (Liste hat weniger als zwei Elemente) einzugehen, oder auch die Schleife, verzweifel ich schon daran, die ersten beiden Elemente zu vertauschen.
Natürlich will ich nicht den Inhalt tauschen, sondern die Zeiger auf die Nachfolgeelemente "verbiegen". Also startzeiger auf das Listenelement zwei von dort auf Listenelement 1 und von dort auf 3. Mein Problem (außer meinem generellen Problem mit Zeigern) ist, dass ich zwar schaffe den Zeiger vom ersten Element auf das dritte zu setzen, dann ja aber nicht mehr zum zweiten komme, weil dann ja kein Zeiger mehr darauf vorhanden ist.

Zwischndurch einmal die Typdefinition für unsere Listenelemente, damit wir über das gleiche Reden:

	C/C++ Quellcode
1 2 3 4 5	typedef struct satz *zeiger_typ; typedef struct satz { int zahl; zeiger_typ next; } satz_typ;

Ich dachte ich nehme mir in meiner Funktion Hilfszeiger (ungefähr so.:
zeiger_typ zwei;
zwei = eins->next; ),damit ich einen Zeiger aufs zweite Element habe, damit ich dann von start auf 2 und von dort auf 1 komme. Aber so scheint das nicht zu funktionieren (mit meinem Hilfszeiger).
Sieht jemand, was da schief läuft? Wie kann ich denn einen Zeiger auf 2 festhalten?

Ich hoffe mein Problem ist verständlich geworden (und natürlich auch, dass mir jemand Helfen kann...)
Danke schon mal fürs Rein- und Mitdenken!

darthdespotism

Professional

Posts: 483

Monday, April 14th 2008, 6:52pm

Klingt eigentlich nach der richtigen Strategie.

Lass mal deine vertausch-funktion seh'n

FinnZiper

Beginner

Posts: 4

Tuesday, April 15th 2008, 2:39pm

Wie gesagt beis ich mir schon am vertauschen der ersten beiden Elemente die Zähne aus..

Einer meiner Vertauschen-Versuch sieht so aus:

C/C++ Quellcode

void nachbarn_vertauschen(zeiger_typ *l) {
zeiger_typ p,q; 
p=*l;
q=p->next;
p->next=p->next->next;
q->next=*l;
}

Ich habe mal ein Bild gemalt wie ich mir das vorstelle. Der Einfachheit halber ist die Liste mit 1234 gefüllt.
http://i1.fastup.de/view.asp?file=lineare+Liste.JPG
Nur leider bekomme ich am Ende nicht 2 1 3 4 sondern 1 3 4 heraus. Irgendwas stimmt also mit dem im Bild rotem q->next = *l; nicht. Kann mir jemand sagen warum das so nicht klappt?

This post has been edited 1 times, last edit by "FinnZiper" (Apr 15th 2008, 7:57pm)

markus1990

Beginner

Posts: 5

Tuesday, April 15th 2008, 3:26pm

wie zeigst du denn den Inhalt eigendlich an?

mfg

This post has been edited 1 times, last edit by "markus1990" (Apr 15th 2008, 3:31pm)

FinnZiper

Beginner

Posts: 4

Tuesday, April 15th 2008, 3:38pm

Hallo. Eigentlich schon. Ich erstelle eine Liste mit:

C/C++ Quellcode

void anfuegen_hinten(zeiger_typ *pl, int z) {
  zeiger_typ p, q;
  q = (zeiger_typ)malloc(sizeof(satz_typ));
  q->zahl = z;
  q->next = NULL;
  if (*pl == NULL) {
  *pl = q;
  }else {
  p = *pl;
  while (p->next != NULL) {
  p = p->next;
  };
  p->next = q;
  }
}

die fülle ich dann mit Elementen z.B. 1 2 3 4
und übergebe sie mit nachbarn_vertauschen(&liste2); an meine Funktion..

Fürs Ausgeben der Liste geschieht mit der Funktion:

C/C++ Quellcode

void liste_ausgeben(zeiger_typ l){
  if (l == NULL) {
  printf("\n");;
  }else {
  printf("%d ", l->zahl); 
  liste_ausgeben(l->next);
  }
}

Torben Brodt

Administrator

Posts: 8,454

Tuesday, April 15th 2008, 6:43pm

C/C++ Quellcode

typedef struct satz *zeiger_typ;
...
void nachbarn_vertauschen(zeiger_typ *l) {
...
void anfuegen_hinten(zeiger_typ *pl, int z) {

Du machst hier immer Zeiger auf Zeiger, oder?

Versuchs doch mal so... wannauch immer du die vertauschen Funktion aufrufst, das anfügen klappt:

C/C++ Quellcode

zeiger_typ anfuegen_hinten(zeiger_typ pl, int z) {
  zeiger_typ p, q;
  q = (zeiger_typ)malloc(sizeof(satz_typ));
  q->zahl = z;
  q->next = NULL;
  if (pl == NULL) {
  pl = q;
  } else {
  p = pl;
  while (p->next != NULL) {
  p = p->next;
  }
  p->next = q;
  }
  return pl;
}

hier auch die korrigierte Tauschfunktion

C/C++ Quellcode

zeiger_typ nachbarn_vertauschen(zeiger_typ l) {
  zeiger_typ p, q; 
  p = l->next;
  q = l;
  q->next = p->next;
  p->next = q;
  return p;
}

Latest blogs: Neuer EX4 Server, Java EE Summit im Juni in München, Kostenlos zur Cebit + Windows 8 Entwickler Schulung

FinnZiper

Beginner

Posts: 4

Tuesday, April 15th 2008, 8:11pm

Hallo d0nut,

vielen Dank erst Einmal. Habe mir deine Funktion mal aufgemalt und natürlich auch ausprobiert. Sieht soweit ganz gut aus, aber als Ausgabe erhalte ich für die Liste 1 2 3 4 => 1 3 4.
Es klappt einfach nicht (wie auch in meinem Beispiel, den "Listenanfangszeiger" auf Position 2 zu setzen. Ich habs im Bild auch rot markiert. Leider schaff ich es nicht das Bild einzubetten, aber so gehts wohl auch.