Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List
/*Project 1 - Creation of user defined data type to implement the user
interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List*/
//C program to find union
// and intersection of two unsorted linked lists
Answer:
#include
#include
// A structure of linked list node
struct node
{
int data;
struct node *next;
} *Head1=NULL, *Head2=NULL, *unionLL=NULL, *intersectionLL=NULL;
//Given a Inserts a node in front of a singly linked list.
void insert(struct node **head, int num)
{
// Create a new Linked List node
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = num;
newNode->next = *head;
*head = newNode;
}
// Linked List by linearly traversing from head to tail
int search(struct node *head, int num)
{
while (head != NULL)
{
if (head->data == num)
{
return 1;
}
head = head->next;
}
return 0;
}
//Returns the union of two given linked list
struct node* findunion(struct node *Head1, struct node *Head2)
{
unionLL = NULL;
struct node *temp = Head1;
while(temp != NULL)
{
insert(&unionLL, temp->data);
temp = temp->next;
}
// Insert those nodes of Head2 linked list which is not present in Head1 linked list
while(Head2 != NULL)
{
if(!search(Head1, Head2->data))
{
insert(&unionLL, Head2->data);
}
Head2 = Head2->next;
}
return unionLL;
}
//Returns common nodes of two given linked list
struct node* intersection(struct node *Head1, struct node *Head2)
{
intersectionLL = NULL;
//Search every element of Head1 in Head2, If found then add it to intersection List
while(Head1 != NULL)
{
if(search(Head2, Head1->data))
{
insert(&intersectionLL, Head1->data);
}
Head1 = Head1->next;
}
return intersectionLL;
}
void print(struct node *nodePtr)
{
while (nodePtr != NULL)
{
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf(" ");
}
}
int main()
{
int i, Head1Count, Head2Count, temp;
//Creating First linked List
printf("Enter the nodes in first Linked List:-\n");
fflush(stdout);
scanf("%d", &Head1Count);
printf("Enter %d integers\n", Head1Count);
fflush(stdout);
for(i=0; i {
scanf("%d", &temp);
insert(&Head1, temp);
}
print(Head1);
printf("\nEnter the nodes in second Linked List:-\n");
fflush(stdout);
scanf("%d", &Head2Count);
printf("Enter %d integers\n", Head2Count);
fflush(stdout);
for(i=0; i {
scanf("%d", &temp);
insert(&Head2, temp);
}
print(Head2);
//printing Union of two given linked list
findunion(Head1, Head2);
intersection(Head1, Head2);
printf("\nUnion of two Linked List:-\n");
print(unionLL);
printf("\nIntersection of two Linked List:-\n");
print(intersectionLL);
return 0;
}
Output:
Enter the nodes in first Linked List:-
4
Enter 4 integers
1
2
3
4
4 3 2 1
Enter the nodes in second Linked List:-
4
Enter 4 integers
3
4
5
6
6 5 4 3
Union of two Linked List:-
5 6 1 2 3 4
Intersection of two Linked List:-
3 4