4. Zwei Verkettete Listen in sich verketten

Zwei Verkettete Listen in sich verketten

  • B

    warum nicht?

    0
  • ?
     

    for(i = 0; i < 20; i++) { 

           //printf("\n1: %d / 2: %d", tmp1->key, tmp2->key);             

           tmp1->next = tmp2; // Element aus 1. Liste mit Element aus 2. Liste 
                              // verketten 
           tmp2->next = tmp3; // Element aus 2. Liste mit Nachfolgeelement des 
                              // vorherigen Elementes aus Liste 1 verketten 

           tmp1 = tmp1->next; // Eine Position weiter 
           tmp2 = tmp2->next; // Eine Position weiter 
           tmp3 = tmp3->next; // Eine Position weiter 
        }

    Hi,

    du solltest dir noch einmal die Funktionweise von Pointern klar machen.
    Hier nun zu deinem Fehler:
    zuerst einmal was passiert bei dir:

    Liste1 X1 X2 X3 X4 X5 X6
    Liste2 Y1 Y2 Y3 Y4 Y5 Y6

    seien t1, t2, t3 deine Hilfspointer

    ich schreibe die Hilfspointer nun über bzw. für die zweite Liste unter die Listenelemente auf denen sie zeigen.

    1. Schritt: Initial

    t1  t3
X1->X2->X3->X4...

Y1->Y2->Y3->Y4...
t2

    2. Schritt: Füge Y1 zwischen X1 und X2 ein: X1->Y1->X2->X3...

    t1  t3
X1  X2->X3->X4...
| /
Y1  Y2->Y3->Y4...
t2

    Dabei sollen die Zeichen | / wie folgt definiert sein:
    | = X1->Y1
    / = Y1->X2

    Hier passiert jetzt dein Fehler bzw. ist schon passiert.
    Du hast nun keinen Pointer mehr, der auf Y2 zeigt.

    3. Schritt: du aktualisierst die Pointer t1, t2, t3: und das kommt dann raus:

    t2  t3
X1  X2->X3->X4...
| /
Y1  Y2->Y3->Y4...
t1

    Der folgende Fix würde helfen:

    t1  t3
X1->X2->X3->X4...

Y1->Y2->Y3->Y4...
t2  t4

    und ersetze die Zeilen:

    tmp1 = tmp1->next; // Eine Position weiter 
           tmp2 = tmp2->next; // Eine Position weiter 
           tmp3 = tmp3->next; // Eine Position weiter

    durch die folgenden:

    tmp1 = tmp3;
           tmp2 = tmp4;
           tmp3 = tmp3->next;
           tmp4 = tmp4->next;

    So, ich habe jetzt nicht auf Korrektheit bei Listeende geachtet.
    Ein wenig kannst du ja auch selbst überlegen. 😉

    Ein Tip: Zeichne dir auf, was du machen möchtest, wenn du mit Zeigern hantierst.

    Gruß mcr

    0
  • D

    habe jetzt nicht versucht das nachzuvollziehen, aber irgendwie erscheint mir das alles sehr kompliziert.

    Der Code müsste doch eigentlich nur so aussehen:

    while(a || b) {
  if(a) {
    push_back(result, a->data);
    a = a->next;
  }
  if(b) {
    push_back(result, b->data);
    b = b->next;
  }
}
    0
  • ?

    DrGreenthumb schrieb:

    habe jetzt nicht versucht das nachzuvollziehen, aber irgendwie erscheint mir das alles sehr kompliziert.

    Der Code müsste doch eigentlich nur so aussehen:

    while(a || b) {
  if(a) {
    push_back(result, a->data);
    a = a->next;
  }
  if(b) {
    push_back(result, b->data);
    b = b->next;
  }
}

    sieht jedenfalls nicht schlecht aus und mir fällt grad kein fehler auf ;).

    habs auch mal versucht, mit der struktur hier:

    typedef struct NNode
{
        struct NNode* next;
        int num;
}Node;

    Die Funtkion tauscht die pointer immer abwechselnd, holt sich also das nächste element von list1/list2/list1/ usw. bis solange bis beide listen durchlaufen sind, und gibt immer den 2ten parameter zurück, es sei denn er ist 0, dann den ersten (der aber auch 0 sein kann).

    Node* swap(Node** p1, Node** p2)
{     
      Node* tmp=*p1;
      *p1=*p2;
      *p2=tmp;
      if(!(*p1))
           return *p2;
      return *p1;
}

    Node* zip(Node* list1, Node* list2)
{
      assert(list1 && list2);
      Node* head=list1;
      while(list2->next)
      {
            list1->next=swap(&list1->next, &list2);            
            list1=list1->next;
      }
      return head;
}

    hier werden jetzt beide listen durchlaufen, und die elemente angehängt, allerdings kommts manchmal vor, dass eins unterschlagen wird... woran kann das liegen? 😕

    0
  • ?

    @ DrGreenthumb : wie sieht denn push_back aus und warum wird da der int wert übergeben?? 😕 normalerweise soll die neue liste doch immernoch bei a beginnen, nur, dass jedes a[n] mit einem b[n] verknüpft ist (solange noch bei beiden listen ein nächstes element vorhanden ist). bei dir siehts so aus, als würde push_back speicher allokieren (müssen) 😕

    0
  • D

    push_back sollte nur ein platzhalter dafür sein, dass an die liste "result" ein neues element mit dem wert von a oder b angehängt wird.

    In meiner Variante wird also eine komplett neue Liste (result) erstellt werden und dementsprechend natürlich Speicher für die neuen Elemente allokieren.

    0
  • ?

    Hallo zusammen,

    sorry für die Späte Rückmeldung. Bin nun schon etwas weiter gekommen, allerdings hakt es irgendwo immer noch.

    Node* reisverschluss (Node *kopf1, Node *kopf2)
{
    Node *tmp1, *tmp2, *tmp3, *tmp4, *head;
    int i;      

    tmp1 = kopf1; // tmp1 auf Anfang Liste 1 setzen
    tmp2 = kopf2; // tmp2 auf Anfang Liste 2 setzen

    head = kopf1; // kopf auf Anfang Liste 1 setzen 

    if(kopf1->next != NULL && kopf2->next != NULL) { // Listen existent?

       tmp1 = tmp1->next;         // Zeigt auf Element mit Key 1
       tmp2 = tmp2->next;         // Zeigt auf Element mit Key 2
       tmp3 = tmp1->next;         // Zeigt auf Element mit Key 3
       tmp4 = tmp2->next;         // Zeigt auf Element mit Key 4 

       while(tmp4->next != NULL) {// Solange Nachfolger von tmp4 nicht NULL

           tmp1->next = tmp2;     // Key 1 mit Key 2 verketten
           tmp2->next = tmp3;     // Key 2 mit Key 3 verketten

           tmp1 = tmp3;           // tmp1 auf Key 3 setzen
           tmp2 = tmp4;           // tmp2 auf Key 4 setzen
           tmp3 = tmp3->next;     // tmp3 auf Nachfolger setzen 
           tmp4 = tmp4->next;     // tmp4 auf Nachfolger setzen

       }

        printf("1: %d 2: %d 3: %d 4: %d\n", tmp1->key, tmp2->key, tmp3->key, tmp4->key);
    }
    return kopf; // Rückgabewert = Zeiger auf Kopfelement der neuen Liste
}

    Die Ausgabe ist:

    Liste 1: 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29

    Liste 2: 2 4 6 8 10 12 14 16 18 20 22 24 26 28

    Liste 3: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 27 29

    Irgendwie unterschlägt die Funktion die 26 und die 28. Die Pointer sind nach letztmaligem Durchlauf auf tmp1: 25 tmp2: 26 tmp3: 27 tmp4: 28.

    Mich würde interessieren ob meine Abbruchbedingung der while-Schleife so passend gewählt ist. Diese habe ich so gewählt, da tmp4 ja der Zeiger ist der nach jedem Durchlauf am weitesten "durchgerückt" ist, d.h. sich am Ende befindet.

    0
  • P

    Kuckuck ! 🕶

    // length(L1) >= length(L2)
void zip( Node **L1, Node **L2 )
{
	Node* p1=*L1, *pp1=p1->next, *p2=*L2, *pp2=p2->next;

	while(  p2 )
	{
		p1->next = p2;
		p2->next = pp1;
		p1 = pp1;
		if ( pp1 )	pp1 = pp1->next;
		p2 = pp2;
		if ( pp2 )	pp2 = pp2->next;
	}
}

    🙂

    0
  • ?

    Hallo,

    hast du dir mal auf Papier aufgemalt, wie das am Ende der Zeilen aussieht?!
    Anscheinend nicht, sonst hättest du den Fehler schließlich gefunden:

    t1  t3
... 23  25->27->29->NULL
    | /
... 24  26->28->NULL
        t2  t4

    So sieht die Situation am Ende deiner Zeilen aus.
    Da deine Abbruchbedingung tmp4->next != NULL lautet bricht er zu früh ab.

    besser wäre:

    if (!tmp3 || !tmp4) break;

    Dann mußt du nur noch das folgende überprüfen:

    if (!tmp3) {
     tmp1->next = tmp2;
  }
  if (!tmp4) {
     tmp2->next = tmp3;
  }

    Hier bin ich mir nicht so sicher. Wahrscheinlich mußt du da noch ein wenig dran feilen.

    Ich weiß, dass dieser Code optimal zum lösen dieser Aufgabe ist. Es geht bestimmt schöner und besser, aber Gast0815 ist besser geholfen, ihn auf seine Fehler hinzuweisen. Vielleicht lernt er da ja mehr durch.

    Gruß mcr

    0
  • C

    hilft das?
    http://img514.imageshack.us/img514/9912/pointersct9.png

    http://c-plusplus.net/forum/viewtopic-var-p-is-1311111.html#1311111

    0
Anmelden zum Antworten