4. Zwei Verkettete Listen in sich verketten

Zwei Verkettete Listen in sich verketten

  • ?

    Hallo,

    ich möchte gerne zwei existierende Listen in einer Art Reisverschlussverfahren verketten. D.h. die Listenelemente beinhalten eine int-Zahl als Nutzdatenwert.

    Liste 1: 1 3 5 7 9 11 13 15 ...
    Liste 2: 2 4 6 8 10 12 14 16 ...

    Am Ende soll eine Dritte Liste erzeugt werden, welche eben alle Daten (1, 2, 3,...) beinhalten soll.

    Hier mein Ansatz:

    Node* reissverschluss(Node *kopf1, Node *kopf2)
{
    Node *tmp1, *tmp2, *tmp3, *head;

    int i, j;

    tmp1 = kopf1;
    tmp2 = kopf2;

    head = kopf1;

    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

       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

       }

    return head; // Rückgabewert = Zeiger auf Kopfelement der neuen Liste
}

    Die Funktion bekommt als Eingabeparameter die jeweiligen Kopf-Zeiger der Listen zugewiesen. Der Rückgabewert soll in Form des Kopfzeigers der neuen Liste geschehen. Das jeweils erste Element der Listen hat einen Nutzdatenwert 0 und wird deswegen Anfangs praktisch gleich "übergangen".

    Irgendwie will das Programm nie so wie ich möchte. Die Verkettung klappt irgendwie nicht so richtig, obwohl ich (für mein Verständnis) alle notwendigen Schritte dafür innerhalb der Iteration gemacht habe. Vielleicht liegt es auch nur an der Uhrzeit.

    Hier eine kleine Skizze, damit ihr wisst was ich meine.

    http://www.directupload.net/file/d/1098/Fvx3H393_jpg.htm

    Thx

    0
  • B

    wie sieht "Node" den aus ? Struktur? so?

    struct Node{

 Node *prev;

}

    Ich nehme an die Listen sind gleich lang!

    int iList1=.. //Länge
int iList2=.. //Länge
pList1Head=.. //erstes List1 elem
pList2Head=.. //erstes List2 elem

//Reisverschlusskopf
Node *pZipHead= pList1Head;

//Reisverschluss auf bestehende referenzen zusammensetzen!
for( int i=0 Node *p= pZipHead->next; i< iList1+iList2; pZipHead= pZipHead->next i++){

//Elemeent aus List 1 anhängen
if(!(i%2)){
  Node *pTmp=pList1Head; 
//Elemeent aus List 2 anhängen
else
  Node *pTmp=pList2Head; 

for(int ElemNr=0; iElemNr< i; pTmp= pTmp->next , iElem++);
pZipHead->next= pTmp;

}

    so irgendwie... Kurz reingehackt.. weis net ob es so geht...

    0
  • ?

    Sind die Listen immer so schön sortiert und gleich lang?
    Hast du schon mal über die verwendung eines debuggers nachgedacht.

    0
  • ?

    Hallo,

    die Listen sind nicht gleich lang.

    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

    Ich möchte die Aufgabe gerne ohne Debugger oder ähnlichem lösen.

    Gruß

    0
  • ?

    Achja, die Struktur sieht wie folgt aus:

    typedef struct node { 
    int key;
    struct node *next; 
} Node;
    0
  • C

    Die einfachste Lösung ist wohl die beste: Du vergleichst die Kopf-Elemente beider Listen und hängst jeweils das "bessere" um an das Ende der Zielliste.

    (wonach du "besser" definierst, hängt von deinem persönlichen Geschmack ab und bestimmt die Reihenfolge, in der die Elemente in der Zielliste auftauchen - wenn du abwechselnd Elemente nimmst, landest du beim Reißverschluß, wenn du jeweils das kleinere aussuchst, bei MergeSort)

    0
  • B

    evlt. ist dir mein code (siehe oben) hilfreich...

    0
  • ?

    warum 2 schleifen?

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