Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List
Theory:
intersection (list1, list2):
Initialize the result list as NULL. Traverse list1 and look for every element in list2, if the element is present in list2, then add the element to the result.
Union (list1, list2):
Initialize a new list ans and store first and second list data to set to remove duplicate data and then store it into our new list ans and return its head.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// Linked list node
struct Node
{
int data;
struct Node* next;
};
// function to insert a node at the beginning of a linked list
void push(struct Node** head_ref, int new_data);
// function to check if given data is present in a list or not
bool isPresent(struct Node* head, int data);
// function to get union of two linked lists head1 and head2
struct Node* getUnion(struct Node* head1,struct Node* head2)
{
struct Node* result = NULL;
struct Node *t1 = head1, *t2 = head2;
// Insert all elements of list1 to the result list
while (t1 != NULL)
{
push(&result, t1->data);
t1 = t1->next;
}
// Insert those elements of list2 which are not present in result list
while (t2 != NULL)
{
if (!isPresent(result, t2->data))
push(&result, t2->data);
t2 = t2->next;
}
return result;
}
// Function to get intersection of two linked lists head1 and head2
struct Node* getIntersection(struct Node* head1,struct Node* head2)
{
struct Node* result = NULL;
struct Node* t1 = head1;
/* Traverse list1 and search each element of it in list2.
If the element is present in list 2,then insert the element to result*/
while (t1 != NULL)
{
if (isPresent(head2, t1->data))
push(&result, t1->data);
t1 = t1->next;
}
return result;
}
// function to insert a node at the beginning of a linked list
void push(struct Node** head_ref, int new_data)
{
// allocate node
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
// put in the data
new_node->data = new_data;
// link the old list of the new node
new_node->next = (*head_ref);
// move the head to point to the new node
(*head_ref) = new_node;
}
// function to print a linked list
void printList(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// function that returns true if data is present in linked list or return false
bool isPresent(struct Node* head, int data)
{
struct Node* t = head;
while (t != NULL)
{
if (t->data == data)
return 1;
t = t->next;
}
return 0;
}
// main program initialization
int main()
{
// Start with the empty list
struct Node* head1 = NULL;
struct Node* head2 = NULL;
struct Node* intersecn = NULL;
struct Node* unin = NULL;
//create a 1st linked lists
push(&head1, 1);
push(&head1, 2);
push(&head1, 3);
push(&head1, 4);
push(&head1, 5);
//create a 2nd linked lists
push(&head2, 4);
push(&head2, 5);
push(&head2, 6);
push(&head2, 7);
push(&head2, 8);
intersecn = getIntersection(head1, head2);
unin = getUnion(head1, head2);
printf("\nFirst list: \n");
printList(head1);
printf("\nSecond list: \n");
printList(head2);
printf("\n Intersection list: \n");
printList(intersecn);
printf("\nUnion list: \n");
printList(unin);
return 0;
}
OUTPUT
First list:
5 4 3 2 1
Second list:
8 7 6 5 4
Intersection list:
4 5
Union list:
6 7 8 1 2 3 4 5
