Einfach verkettete Liste - Elemente vertauschen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • 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:

    Quellcode

    1. typedef struct satz *zeiger_typ;
    2. typedef struct satz {
    3. int zahl;
    4. zeiger_typ next;
    5. } 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!

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

    Einer meiner Vertauschen-Versuch sieht so aus:

    Quellcode

    1. void nachbarn_vertauschen(zeiger_typ *l) {
    2. zeiger_typ p,q;
    3. p=*l;
    4. q=p->next;
    5. p->next=p->next->next;
    6. q->next=*l;
    7. }


    Ich habe mal ein Bild gemalt wie ich mir das vorstelle. Der Einfachheit halber ist die Liste mit 1234 gefüllt.
    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?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von FinnZiper ()

  • Hallo. Eigentlich schon. Ich erstelle eine Liste mit:

    Quellcode

    1. void anfuegen_hinten(zeiger_typ *pl, int z) {
    2. zeiger_typ p, q;
    3. q = (zeiger_typ)malloc(sizeof(satz_typ));
    4. q->zahl = z;
    5. q->next = NULL;
    6. if (*pl == NULL) {
    7. *pl = q;
    8. }else {
    9. p = *pl;
    10. while (p->next != NULL) {
    11. p = p->next;
    12. };
    13. p->next = q;
    14. }
    15. }
    Alles anzeigen


    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:

    Quellcode

    1. void liste_ausgeben(zeiger_typ l){
    2. if (l == NULL) {
    3. printf("\n");;
    4. }else {
    5. printf("%d ", l->zahl);
    6. liste_ausgeben(l->next);
    7. }
    8. }

  • Quellcode

    1. typedef struct satz *zeiger_typ;
    2. ...
    3. void nachbarn_vertauschen(zeiger_typ *l) {
    4. ...
    5. 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:

    Quellcode

    1. zeiger_typ anfuegen_hinten(zeiger_typ pl, int z) {
    2. zeiger_typ p, q;
    3. q = (zeiger_typ)malloc(sizeof(satz_typ));
    4. q->zahl = z;
    5. q->next = NULL;
    6. if (pl == NULL) {
    7. pl = q;
    8. } else {
    9. p = pl;
    10. while (p->next != NULL) {
    11. p = p->next;
    12. }
    13. p->next = q;
    14. }
    15. return pl;
    16. }
    Alles anzeigen


    hier auch die korrigierte Tauschfunktion

    Quellcode

    1. zeiger_typ nachbarn_vertauschen(zeiger_typ l) {
    2. zeiger_typ p, q;
    3. p = l->next;
    4. q = l;
    5. q->next = p->next;
    6. p->next = q;
    7. return p;
    8. }

  • 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.