链表的C并集

Question

我创建了一个程序来查找2链表的并集。我的逻辑是首先取一个新的列表，将list1的内容插入到这个列表中，并只插入那些不在结果列表中的list2的值。我的代码是:

#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()函数，即使我已经使结果一个全局变量。有谁能告诉我为什么输出只显示list1的内容:

output:6 4 9 5 7

Answer 1

使用你的算法，如果list1有重复项，它们将显示在最终结果中，但如果list2有重复项，它们将不显示在最终结果中，这可能是你不想要的。

我也认为你的意思是使用temp2而不是second:

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

，最后这花了我一些时间，但我发现你的错误:

push(&result,data); 

应为result1

希望这对你有帮助!

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，它不会向列表中添加重复的值。