Объединение связанных списков

Question

Я создал программу, чтобы найти объединение из 2 связанных списков. Моя логика в первую очередь включает новый список insert1 в список и вставляет только те значения из списка2, которые не входят в список результатов. Мой код:

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

/* Linked list node */ 
struct node 
{ 
    int data; 
    struct node* next; 
}; 
struct node* result; 

struct node *newNode(int data) 
{ 
    struct node *new_node = (struct node *) malloc(sizeof(struct node)); 
    new_node->data = data; 
    new_node->next = NULL; 
    return new_node; 
} 

/* Function to insert a node at the beginning of the Doubly Linked List */ 
void push(struct node** head_ref, int new_data) 
{ 
    /* allocate node */ 
    struct node* new_node = newNode(new_data); 

    new_node->next=*head_ref; 
    *head_ref=new_node; 
} 

struct node *union3(struct node *first, struct node *second, struct node *result) 
{ 
    int flag = 0; 
    struct node *temp = NULL; 
    temp = first; 
    struct node *temp2 = NULL; 
    temp2 = second; 
    int value; 
    while (temp != NULL) 
    { 
     push(&result, temp->data);  // pushing first list values in result 
     temp = temp->next; 
    } 
    while (second) 
    { 
     present(second->data, result); // comparing second list each member with result 
     second = second->next; 
    } 
    return result; 
} 

void present(int data, struct node *result1) 
{ 
    printf("The value in the beginning of present function is:"); 

    int flag = 0; 
    while (result1) 
    { 
     if (result1->data == data) 
     { 
      flag++; 
     } 
     result1 = result1->next; 
    } 
    if (flag > 0) 
    { 
     printf(""); 
    } 
    else 
    { 
     push(&result, data); 
    } 
} 

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

/* Drier program to test above function */ 
int main(void) 
{ 
    struct node* first = NULL; 
    struct node* second=NULL; 
    // struct node* result=NULL; 
    struct node* union2=NULL; 
    // create first list 7->5->9->4->6 
    push(&first, 6); 
    push(&first, 4); 
    push(&first, 9); 
    push(&first, 5); 
    push(&first, 7); 
    printf("First list is:"); 
    printList(first); 
    push(&second,6); 
    push(&second,4); 
    push(&second,9); 
    push(&second,11); 
    push(&second,12); 
    printf("second list is"); 
    printList(second); 
    printf("their union is:"); 
    union2=union3(first,second,result); 
    printf("Union of 2 lists is:"); 
    printList(union2); 
    return 0; 
} 

В принципе, моя логика правильная, но проблема возникает в переменной результата. Его значения list1, введенные в него, теряются в нем, когда он идет в функции present(), хотя я сделал результат глобальной переменной. Кто-нибудь может сказать, почему выход отображает только песни1 содержимое как:

output:6 4 9 5 7 

Answer 1

С вашим алгоритмом, если песни1 Повторяющиеся они покажут в конечном итоге, но если песни2 Повторяющиеся они не будут отображаться в конечном итоге что-то вы, вероятно, не хотите.

Кроме того, я думаю, что вы имели в виду использовать temp2 вместо второго в:

while(second) 
{ 
present(second->data,result); //comparing second list each member with result      
second=second->next; 
} 

и, наконец, это заняло у меня некоторое время, но я нашел свою ошибку:

push(&result,data); 

следует привести

Надеюсь, это поможет!

Answer 2

Поймать! :) Все, что вам нужно, это добавить функцию, которая освободит выделенную память для списков.

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

/* Linked list node */ 
struct node 
{ 
    int data; 
    struct node *next; 
}; 

struct node *newNode(int data, struct node *next) 
{ 
    struct node *tmp = (struct node *) malloc(sizeof(struct node)); 

    if (tmp) 
    {   
     tmp->data = data; 
     tmp->next = next; 
    } 

    return tmp; 
} 

/* Function to insert a node at the beginning of the Doubly Linked List */ 
void push(struct node **head_ref, int data) 
{ 
    /* allocate node */ 
    struct node *tmp = newNode(data, *head_ref); 

    if (tmp != NULL) 
    {   
     *head_ref = tmp; 
    } 
} 

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

    return head != NULL; 
}  

struct node* list_union(struct node *first, struct node *second) 
{ 
    struct node *head = NULL; 
    struct node **head_ref = &head; 

    for (struct node *current = first; current != NULL; current = current->next) 
    { 
     struct node *tmp = newNode(current->data, NULL); 
     if (tmp != NULL) 
     { 
      *head_ref = tmp; 
      head_ref = &(*head_ref)->next; 
     } 
    } 

    for (struct node *current = second; current != NULL; current = current->next) 
    { 
     if (!find(first, current->data)) 
     {      
      struct node *tmp = newNode(current->data, NULL); 
      if (tmp != NULL) 
      { 
       *head_ref = tmp; 
       head_ref = &(*head_ref)->next; 
      } 
     }   
    } 

    return head; 
}  

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

    printf("\n"); 
} 

/* Drier program to test above function */ 
int main(void) 
{ 
    struct node *first = NULL; 
    struct node *second = NULL; 
    struct node *union2 = NULL; 

    // create first list 7->5->9->4->6 
    push(&first, 6); 
    push(&first, 4); 
    push(&first, 9); 
    push(&first, 5); 
    push(&first, 7); 

    printf("First list is: "); 
    printList(first); 

    push(&second, 6); 
    push(&second, 4); 
    push(&second, 9); 
    push(&second, 11); 
    push(&second, 12); 

    printf("second list is: "); 
    printList(second); 

    union2 = list_union(first, second); 

    printf("Union of 2 lists is: "); 
    printList(union2); 

    // Here you should call a function that frees all the memory allocated for the lists 
}  

Выход программы

First list is: 7 5 9 4 6 
second list is: 12 11 9 4 6 
Union of 2 lists is: 7 5 9 4 6 12 11 

Также вы можете написать функцию push таким образом, что она не будет добавлять дублированные значения в список.