Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory)
Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory)
Algorithm:
Step 1: Create a linked list node
Step 2: To insert a node at the beginning of a linked list
Step 3: To check if given data is present in a list
Step 4: To get union of two linked lists head1 and Head2
Step 5: To Insert all elements of list1 to the result list
Step 6: To insert those elements of list2 which are not present in result list
Step 7: To get intersection of two linked lists head1 and head2
Step 8: To Transverse list1 and search each element of it in list2. If the element is present in list 2, then insert the element to result.
Step 9: To insert a node at the beginning of a linked list
Step 10: To allocate the memory of node.
Step 11: To link old list of the new node
Step 12: To move the head to point a linked list
Step 13: To utility function that returns true if data is present in linked list else return false.
Step 14: To test the above functions.
Step 15: To Print the sequences.
Step 16: End of the process.
PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Create Linked list node
struct Node
{
int data;
struct Node* next;
};
// A function to insert a node
void push(struct Node** head_ref, int new_data);
// A function to check if given data is present in a list
bool isPresent(struct Node* head, int data);
// A Function to get union of head1 and head2 sequence
struct Node* getUnion(struct Node* head1, struct Node* head2)
{
struct Node* result=NULL;
struct Node *t1=head1, *t2=head2;
// Insert all the elements of list1 to the result list1
while(t1 != NULL)
{
push(&result, t1->data);
t1=t1->next;
}
// Insert the 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 head1 and head2 sequences
struct Node* getIntersection(struct Node* head1, struct Node* head2)
{
struct Node* result=NULL;
struct Node* t1=head1;
//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;
}
// A unity function to insert a node at the begining of a linked list
void push(struct Node** head_ref,int new_data)
{
// Allocation of the 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;
}
// A utility function to print a linked list
void printList(struct Node* node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node=node->next;
}
}
// A unity function that returns true if data is present in linked list else 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;
}
// Driver program to test above function
int main()
{
//start from the empty list
struct Node* head1=NULL;
struct Node* head2=NULL;
struct Node* intersecn=NULL;
struct Node* unin=NULL;
// create a linked lists 1 : 3->6->9->12
push(&head1, 3);
push(&head1, 6);
push(&head1, 9);
push(&head1, 12);
// create linked list 2 : 12->15->18->9
push(&head2, 12);
push(&head2, 15);
push(&head2, 18);
push(&head2, 9);
intersecn=getIntersection(head1, head2);
unin=getUnion(head1, head2);
printf("\n THE FIRST SEQUENCE IS: ");
printList(head1);
printf("\n THE SECOND SEQUENCE IS: ");
printList(head2);
printf("\n THE INTESECTION SEQUENCE IS: ");
printList(intersecn);
printf("\n THE UNION SEQUENCE IS : ");
printList(unin);
return 0;
}
OUTPUT:
THE FIRST SEQUENCE IS: 12 9 6 3
THE SECOND SEQUENCE IS: 9 18 15 12
THE INTESECTION SEQUENCE IS: 9 12
THE UNION SEQUENCE IS : 15 18 3 6 9 12