Verkette Liste Elemente vertauschen

[Özlem (Gast)]

Hallo,

ich bin C Anfängerin und bekomme das vertauschen von Elementen in einer 
verketteten Liste nicht hin.

Der erste Fall, dass die ersten zwei Elemente vertauscht werden, klappt. 
Aber wenn ich zwei beliebige Elemente vertauschen möchte, bekomme ich 
das nicht hin.

Kann mir jemand vllt. weiterhelfen? Ich bin am verzweifeln... :-(

// Perlenspiel.cpp : main project file.

#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

using namespace System;


struct perle
{
    char farbe[100];
    char typ[100];
    struct perle *naechste;
};


struct perle* vorwaerts (struct perle *akt, short x)
{
    int i = 0;
     struct perle *perl_zeiger1;


             perl_zeiger1 = akt;

             while(perl_zeiger1->naechste != NULL && i < x-1)
             {
                 perl_zeiger1 = perl_zeiger1->naechste;

                 i++;
             }
             return perl_zeiger1;
}

short loesche(struct perle **anf,short x)
    // Lösche x.
    // Rueckgabe: 0, wenn ok, 1 wenn nicht ok.
{
     int i = 0;
     struct perle *aktuell  = *anf;
     struct perle *perl_zeiger1;
     struct perle *perl_zeiger2;

     if(aktuell != NULL)
     {
         if(i==x)
         {
             *anf = aktuell->naechste;
             // "*anf" ist ein Synonym für "erste"
         }
         else
         {
             perl_zeiger1 = vorwaerts(aktuell, x);
             perl_zeiger2 = perl_zeiger1 -> naechste;

             if ( perl_zeiger2 == NULL )
                 {
                     return 1; // Fehler!
                 }
             perl_zeiger1 -> naechste = perl_zeiger2->naechste;

         }
     }


     return 0;
}

short vertausche(struct perle **anf, short x, short y)
{
    int i = 0;
    struct perle *aktuell = *anf;
    struct perle *perl_zeiger1;
    struct perle *perl_zeiger2;
    struct perle *perl_zeiger3;
    struct perle *perl_zeiger4;

    if(i==x && y == x+1)
    {



        perl_zeiger1 = aktuell->naechste;
        perl_zeiger2 = aktuell;
        perl_zeiger2->naechste = perl_zeiger1->naechste;
        perl_zeiger1->naechste = perl_zeiger2;

     }
    else
    {
        //perl_zeiger1 = (vorwaerts(aktuell,y))->naechste;
        //perl_zeiger2 = (vorwaerts(aktuell,x))->naechste;
          perl_zeiger1 = vorwaerts(aktuell,x);
          perl_zeiger2 = vorwaerts(aktuell,y);

          perl_zeiger3 = perl_zeiger1->naechste;
          perl_zeiger1->naechste = perl_zeiger2->naechste;
          perl_zeiger2->naechste = perl_zeiger3;








     }

    return 0;
}



int main(array<System::String ^> ^args)
{

    struct perle p1,p2,p3,p4;
    short fehler = 0;

    struct perle* erste;



    strcpy_s(p1.farbe, "gelb");
    strcpy_s(p1.typ, "austern");


    strcpy_s(p2.farbe, "blau");
    strcpy_s(p2.typ, "saphir");


    strcpy_s(p3.farbe, "schwarz");
    strcpy_s(p3.typ, "onyx");

    strcpy_s(p4.farbe, "rot");
    strcpy_s(p4.typ,"rubin");


    erste = &p1;
    p1.naechste = &p3;
    p3.naechste = &p2;
    p2.naechste = &p4;
    p4.naechste = NULL;

    //fehler  = loesche(&erste,4);
    vertausche(&erste,1,3);

    return 0;
}

[Dennis (Gast)]

Özlem schrieb:
> Kann mir jemand vllt. weiterhelfen? Ich bin am verzweifeln... :-(

Ok, gerne. Erkläre doch mal zuerst, wie eine verkettete Liste aufgebaut 
ist (in eigenen Worten). Besonders Interessant: welcher Zeiger ist wo 
abgelegt?

[D. I. (Gast)]

Es ist noch einiges Lernpotenzial vorhanden wenn man sich den obigen 
Code anschaut ;)

[Karl H. (kbuchegg)]

Özlem schrieb:

> Der erste Fall, dass die ersten zwei Elemente vertauscht werden, klappt.
> Aber wenn ich zwei beliebige Elemente vertauschen möchte, bekomme ich
> das nicht hin.
>
> Kann mir jemand vllt. weiterhelfen? Ich bin am verzweifeln... :-(

Aufmalen!


Das ist deine Liste


  erste
  +------+
  |  o   |
  +--|---+
     |
     |
     v
   +-------+
   | rot   |
   | a     |    +------+
   |   o------->| gelb |
   +-------+    | b    |    +-------+
                |  o------->| blau  |
                +------+    | c     |     +------+
                            |  o--------->| grau |
                            +-------+     | d    |
                                          | NULL |
                                          +------+


Leg den Editor zur Seite. Schnapp dir Papier und Bleistift und mal dir 
die Situation auf.

Was musst du tun, damit gelb und blau dir Reihenfolge in der Verkettung 
tauschen?
Du kannst beliebig viele Pointer-Variablen einführen. So viele du 
willst.
Aber: Du fängst mit einem Pointer an, der "gelb" gesucht und gefunden 
hat und ausgehend von diesem Pointer musst du die anderen Pointer so 
manipulieren, dass aus

  erste
  +------+
  |  o   |
  +--|---+
     |
     |
     v
   +-------+
   | rot   |
   | a     |    +------+
   |   o------->| gelb |
   +-------+    | b    |    +-------+
                |  o------->| blau  |
                +------+    | c     |     +------+
                            |  o--------->| grau |
                            +-------+     | d    |
                                          | NULL |
                                          +------+


das hier

  erste
  +------+
  |  o   |
  +--|---+
     |
     |
     v
   +-------+ +-------------+
   | rot   | |             |
   | a     | |   +------+  |
   |   o-----+ +>| gelb |  |
   +-------+   | | b    |  |  +-------+
               | |  o----+ +->| blau  |
               | +------+|    | c     |     +------+
               |         |    |  o------+ +>| grau |
               |         |    +-------+ | | | d    |
               |         |              | | | NULL |
               |         |              | | +------+
               +---------|--------------+ |
                         |                |
                         +----------------+

wird. Fahr ausgehend von erste den Pfeilen nach und überzeug dich davon, 
dass gelb und blau jetzt in der vertauschten Reihenfolge besucht werden.

ALso: ausgehend von einem Pointer auf "gelb"

  erste
  +------+      found
  |  o   |      +------+
  +--|---+      | o    |
     |          +-|----+
     |            |
     v            |
   +-------+      |
   | rot   |      v
   | a     |    +------+
   |   o------->| gelb |
   +-------+    | b    |    +-------+
                |  o------->| blau  |
                +------+    | c     |     +------+
                            |  o--------->| grau |
                            +-------+     | d    |
                                          | NULL |
                                          +------+

in welcher Reihenfolge, musst du welchen Pointer wohin verbiegen (bzw. 
vorher sichern), so dass du
a) keinen Pointer verlierst
b) du am Ende mit der Zielzeichnung rauskommst

Schnapp dir Papier, Bleistift und Radiergummi und probiers aus, bis du 
eine Lösung hast und die Reihenfolge der Schritte ausgetüftelt hast.

Wenn dir das am Papier klar geworden ist, dann weißt du auch wie man es 
programmieren muss.

[Karl H. (kbuchegg)]

PS.
Die ganze Systematik bei dir, mit der 'Nummerierung' der Knoten ist 
Schwachsinn. Wenn ich die Dinger durchnummerieren kann, dann verwende 
ich ein Array und keine verkettete Liste.


Ein Knoten wird durch seine Adresse identifiziert und nicht dadurch, der 
wievielte Knoten in der Liste er ist.

[i-Troll (Gast)]

Was soll den der grund fuer eine einfach verkettete Liste sein? Ich 
betrachte eine doppelt verkettete Liste als in alln faellen lohnend. 
Heisst, ich verwene keine einfach verketteten Listen. dann ist es 
einfacher.

[D. I. (Gast)]

i-Troll schrieb:
> Was soll den der grund fuer eine einfach verkettete Liste sein? Ich
> betrachte eine doppelt verkettete Liste als in alln faellen lohnend.
> Heisst, ich verwene keine einfach verketteten Listen. dann ist es
> einfacher.

Wenns die Übungsaufgabe oder der Interviewer im Vorstellungsgespräch 
verlangt ;) Außerdem doppelter Speicheraufwand für die Pointer.