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:

Objectives:

• To create two singly linked lists with n number of nodes.
• To display Linked List 1 and Linked List 2 as a separate list
• To find the Intersection of two linked list
• To find the Union of two linked List

Logic:

Node Creation: To create a node assign a head for each list and insert a node at the start of the list. Then head address will be pointing to the next node, then it will continue to n nodes.

Intersection: To find the intersection of two lists, each node of list 1 is compared to each node of list 2. Then the common nodes of List 1 & 2 are returned and stored as another list.

Union: To find the union of two list, each node of list 1 is compared to each node of list 2. Then it merges the duplicate value in each list and creates a new list called the union and it has all the nodes of lists 1 & 2.

Program:

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

struct Node //declaring a structure
{
int data;
struct Node* next;
};

void createnode(struct Node** head_ref, int new_data);
int check(struct Node* head, int data);

void createnode(struct Node** head_ref, int new_data)//function to creating nodes at the starting point
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));//memeory allocation to each nodes

new_node->data = new_data;//creating node

new_node->next = (*head_ref);//linking the address of next node data

(*head_ref) = new_node;//point the head node
}

int check(struct Node* head, int data)//To check the particular list has data or not
{
struct Node* t = head;
while (t != NULL)//If data present true
{
if (t->data == data)
{
return 1;
}
t = t->next;
}
return 0;
}

struct Node* getIntersection(struct Node* head1, struct Node* head2)
{
struct Node* result = NULL;
struct Node* t1 = head1;

while (t1 != NULL)//List 1 data is compared with List 2 to get intersected node
{
if (check(head2, t1->data))
{
createnode(&result, t1->data);
}
t1 = t1->next;
}
return result;
}

struct Node* getUnion(struct Node* head1, struct Node* head2)//To get all the element in list 1 and list 2 except repeated data
{
struct Node* result = NULL;
struct Node *t1 = head1, *t2 = head2;

while (t1 != NULL)
{
createnode(&result, t1->data);
t1 = t1->next;
}

while (t2 != NULL)
{
if (!check(result, t2->data))
{
createnode(&result, t2->data);
}
t2 = t2->next;
}
return result;//It returns all the union nodes except repeated nodes in a single list
}

void display(struct Node* node)//for displaying linked list
{
if(node == NULL)//if in list no data present it prints no data
{
printf("No Intersected Nodes");
}
else//printing nodes of respecting functions
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

}

int main()
{
int n,m,temp,i;//variable declaration
printf("Enter number of nodes in List 1: ");
fflush(stdout);
scanf("%d", &n);

printf("Enter number of nodes in List 2: ");
fflush(stdout);
scanf("%d", &m);

struct Node* head1 = NULL;//list 1
struct Node* head2 = NULL;//list 2
struct Node* intersecn = NULL;//intersection list
struct Node* unin = NULL;//union list

printf("\n");
for(i=0;i<n;i++)
{
printf("Enter the List 1 node[%d]: ",i);
fflush(stdout);
scanf("%d", &temp);
createnode(&head1, temp);
}

printf("\n");
for(i=0;i<m;i++)
{
printf("Enter the List 2 node[%d]: ",i);
fflush(stdout);
scanf("%d", &temp);
createnode(&head2, temp);
}

intersecn = getIntersection(head1, head2);//calling intersection function by value
unin = getUnion(head1, head2);//calling union function by value

printf("\nList 1: ");
display(head1);//To display List 1 - calling display function of head1

printf("\n\nList 2: ");
display(head2);//To display List 2 - calling display function of head2

printf("\n\nIntersection of Lists: ");
display(intersecn);//printing intersection of two list

printf("\n\nUnion of Lists: ");
display(unin);//printing union of two list

return 0;
}