Austauschen von Knoten in der verknüpften Liste

Question

Ich habe versucht, Funktion (swapNodes) zum Austauschen von Knoten in verknüpften Liste zu machen. Hier habe ich die vorherigen und nächsten Adressen von Knoten gespeichert, die getauscht werden sollen. Aber mein Code steckte in Endlosschleife.

Kann dieser Code als Arbeitscode oder als falscher Ansatz erstellt werden?

#include<stdio.h> 
#include<stdlib.h> 
struct Node 
{ 
    int data; 
    struct Node *next; 
}; 
void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = 
     (struct Node*) malloc(sizeof(struct Node)); 

    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 


void printList(struct Node *node) 
{ 
    while(node != NULL) 
    { 
     printf("%d ", node->data); 
     node = node->next; 
    } 
} 

void swapNodes(struct Node** headr,int key1,int key2) 
{ 
    struct Node* temp1 = *headr; 
    struct Node* temp2 = *headr; 

    if(key1 == key2) 
    return; 

    struct Node* prev1 =NULL; 
    struct Node* next1 =temp1; 
    while(temp1->data !=key1 && next1 !=NULL) 
    { 
    prev1 =temp1; 
    temp1 =temp1->next; 
    next1 =temp1->next; 
    } 
    struct Node* prev2 =NULL; 
    struct Node* next2 =temp2; 
    while(temp2->data !=key2 && next2 !=NULL) 
    { 
    prev2 =temp2; 
    temp2 =temp2->next; 
    next2 =temp2->next; 
    } 
    if(next1 == NULL||next2 == NULL) 
    return; 

    prev1->next =temp2; 
    temp2->next =next1; 
    prev2->next =temp1; 
    temp1->next =next2; 
} 
int main() 
{ 
    struct Node *start = NULL; 

    push(&start, 7); 
    push(&start, 6); 
    push(&start, 5); 
    push(&start, 4); 
    push(&start, 3); 
    push(&start, 2); 
    push(&start, 1); 

    printf("\n Linked list before calling swapNodes() "); 
    printList(start); 

    swapNodes(&start, 4, 3); 

    printf("\n Linked list after calling swapNodes() "); 
    printList(start); 

    return 0; 
} 

Answer 1

Sie sollten Sie umschreiben swapNodes Funktion ein bisschen:

void swapNodes(struct Node** headr, int key1, int key2) 
{ 
    struct Node* temp1 = *headr; 
    struct Node* temp2 = *headr; 

    if(key1==key2) 
     return; 

    struct Node* prev1=NULL; 
    while(temp1 && temp1->data!=key1) 
    { 
     prev1=temp1; 
     temp1=temp1->next; 
    } 
    struct Node* prev2=NULL; 
    while(temp2 && temp2->data!=key2) 
    { 
     prev2=temp2; 
     temp2=temp2->next; 
    } 

    if(temp1==NULL || temp1==NULL) 
     return; 

    // temp1 is a head 
    if (prev1 == NULL) { 
     *headr = temp2; 
    } else { 
     prev1->next = temp2; 
    } 

    // temp2 is a head 
    if (prev2 == NULL) { 
     *headr = temp1; 
    } else { 
     prev2->next = temp1; 
    } 

    struct Node *buff = temp2->next; 
    temp2->next = temp1->next; 
    temp1->next = buff; 
} 

Wie Sie können Sie nicht next1 und next2 Zeiger sehen müssen. Aber Sie müssen prüfen, ob temp1 oder temp2 ein Kopf ist: Es ist ein besonderer Fall, wenn Sie Kopf mit einem anderen Knoten ersetzen müssen. Der Rest ist trivial - tauschen Sie einfach die Knoten über den Pufferknoten aus.

Answer 2

Die Funktion undefiniert Verhalten hat, weil es nicht in Betracht zieht, dass zum Beispiel headr gleich sein kann NULL oder prev1 und prev2-NULL gleich sein können.

Es wäre gut, eine weitere Funktion zu schreiben, die den Knoten findet, der den gegebenen Daten entspricht.

Trotzdem kann die Funktion swapNodes folgendermaßen geschrieben werden. Es findet Knoten, die ausgetauscht werden sollen, und tauscht dann Zeiger auf die Knoten und ihre Datenelemente aus next. Hier

Sie sind

void swap(struct Node **first, struct Node **second) 
{ 
    struct Node *tmp = *first; 
    *first = *second; 
    *second = tmp; 
} 

void swapNodes(struct Node **headr, int key1, int key2) 
{ 
    if (key1 == key2) return; 

    struct Node **first = headr; 

    while (*first && (*first)->data != key1) first = &(*first)->next; 

    if (*first == NULL) return; 

    struct Node **second = headr; 

    while (*second && (*second)->data != key2) second = &(*second)->next; 

    if (*second == NULL) return; 

    swap(first, second); 
    swap(&(*first)->next, &(*second)->next); 
} 

hier ein Demonstrationsprogramm ist.

#include <stdio.h> 
#include <stdlib.h> 

struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = 
     (struct Node*) malloc(sizeof(struct Node)); 

    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

void printList(struct Node *node) 
{ 
    while(node != NULL) 
    { 
     printf("%d ", node->data); 
     node = node->next; 
    } 
} 

void swap(struct Node **first, struct Node **second) 
{ 
    struct Node *tmp = *first; 
    *first = *second; 
    *second = tmp; 
} 

void swapNodes(struct Node **headr, int key1, int key2) 
{ 
    if (key1 == key2) return; 

    struct Node **first = headr; 

    while (*first && (*first)->data != key1) first = &(*first)->next; 

    if (*first == NULL) return; 

    struct Node **second = headr; 

    while (*second && (*second)->data != key2) second = &(*second)->next; 

    if (*second == NULL) return; 

    swap(first, second); 
    swap(&(*first)->next, &(*second)->next); 
} 

int main(void) 
{ 
    struct Node *start = NULL; 

    push(&start, 7); 
    push(&start, 6); 
    push(&start, 5); 
    push(&start, 4); 
    push(&start, 3); 
    push(&start, 2); 
    push(&start, 1); 

    printf("\n Linked list before calling swapNodes() "); 
    printList(start); 

    swapNodes(&start, 4, 3); 

    printf("\n Linked list after calling swapNodes() "); 
    printList(start); 

    return 0; 
} 

Sein Ausgang ist

Linked list before calling swapNodes() 1 2 3 4 5 6 7 
Linked list after calling swapNodes() 1 2 4 3 5 6 7 

In der Tat die Funktion swapNodes wie geschrieben steht (ohne eine separate Funktion, die Knoten für ein gegebenen Daten findet) macht zwei Dinge: Es 1) findet zwei Knoten und es 2) tauscht sie. Das Suchen der Knoten kann nicht erfolgreich sein. Daher sollte die Funktion dem Benutzer melden, ob Knoten ausgetauscht wurden. In diesem Fall ist es wünschenswert, die Funktion mit dem Rückgabetyp int zu deklarieren.

Zum Beispiel

int swapNodes(struct Node **headr, int key1, int key2) 
{ 
    int success = key1 != key2; 

    if (success) 
    {   
     struct Node **first = headr; 
     struct Node **second = headr; 

     while (*first && (*first)->data != key1) first = &(*first)->next; 

     success = *first != NULL; 

     if (success) 
     {    
      while (*second && (*second)->data != key2) second = &(*second)->next; 

      success = *second != NULL; 
     } 

     if (success) 
     {    
      swap(first, second); 
      swap(&(*first)->next, &(*second)->next); 
     } 
    } 

    return success; 
} 

Wenn eine eigene Funktion zu schreiben, die einen Knoten sucht, wie es oben dann die Funktion erwähnt wurde, die Knoten tauscht aussehen wird klarer und einfacher.

Zum Beispiel

#include <stdio.h> 
#include <stdlib.h> 

struct Node 
{ 
    int data; 
    struct Node *next; 
}; 

void push(struct Node** head_ref, int new_data) 
{ 
    struct Node* new_node = 
     (struct Node*) malloc(sizeof(struct Node)); 

    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

void printList(struct Node *node) 
{ 
    while(node != NULL) 
    { 
     printf("%d ", node->data); 
     node = node->next; 
    } 
} 

void swap(struct Node **first, struct Node **second) 
{ 
    struct Node *tmp = *first; 
    *first = *second; 
    *second = tmp; 
} 

struct Node ** find(struct Node **headr, int data) 
{ 
    while (*headr && (*headr)->data != data) headr = &(*headr)->next; 

    return headr; 
} 

void swapNodes(struct Node **first, struct Node **second) 
{ 
    swap(first, second); 
    swap(&(*first)->next, &(*second)->next); 
} 

int main(void) 
{ 
    struct Node *start = NULL; 

    push(&start, 7); 
    push(&start, 6); 
    push(&start, 5); 
    push(&start, 4); 
    push(&start, 3); 
    push(&start, 2); 
    push(&start, 1); 

    printf("\n Linked list before calling swapNodes() "); 
    printList(start); 

    struct Node **first; 
    struct Node **second; 

    if ((first = find(&start, 4)) && (second = find(&start, 3))) swapNodes(first, second); 

    printf("\n Linked list after calling swapNodes() "); 
    printList(start); 

    return 0; 
}