リンクリストのノードを入れ替えよう

Question

リンクリストのノードを入れ替えるための関数（swapNodes）を作ろうとしました。 ここでは、スワップされるノードの前後のアドレスが格納されています。 しかし、私のコードは無限ループに詰まっていました。

このコードを有効にしても問題ないのですか？

#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

あなたはあなたにswapNodes機能ビットを書き換える必要があります。

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; 
} 

あなたがnext1とnext2ポインタを必要としない見ることができるように。しかし、temp1またはtemp2が頭であるかどうかをチェックする必要があります。頭を別のノードに置き換える必要がある場合は特殊なケースです。残りの部分は簡単です。バッファノードを介してノードを交換するだけです。それは例えばheadrがNULLかprev1に等しくすることができるとprev2がNULLに等しくすることができることを考慮に入れていないので、

Answer 2

関数が未定義の動作をしています。

与えられたデータに対応するノードを見つけるもう1つの関数を書くとよいでしょう。

それにもかかわらず、関数swapNodesは次のように書くことができます。スワップされるノードを見つけ、ノードとそのデータメンバへのポインタをスワップします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); 
} 

あるが実証プログラムです。

#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; 
} 

その出力は、実際にそれが（与えられたデータのためのノードを見つけ別機能なし）が書き込まれるように機能swapNodesは2つのことを行い

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

である：それは1）は、2つのノードを見つけて2）それらを交換する。ノードの検索が失敗する可能性があります。したがって、関数は、ノードがスワップされたかどうかをユーザーに報告する必要があります。この場合、戻り値の型がintであると宣言することが望ましいです。例えば

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; 
} 

それはノードがより明確かつ簡単になりますスワップ、関数前述したように、ノードを検索する別の関数を書くことができます。

#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; 
}