Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List
// This is a program to implement
// union and intersection of two sets
// as in set theory.
// Here, stdio.h and stdlib.h is included
// to use printf/scanf and malloc respectively
#include<stdio.h>
#include<stdlib.h>
// Node structure for the linked list
struct Node
{
int data;
struct Node* next;
};
// Function to create a new node
struct Node* newNode(int data)
{
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to display the linked list
void display(struct Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
// Function to insert a new node at the end of the linked list
void insertNode(struct Node** head, int data)
{
struct Node* newNodept = newNode(data);
if (*head == NULL)
{
*head = newNodept;
}
else
{
struct Node* current = *head;
while (current->next != NULL)
{
current = current->next;
}
current->next = newNodept;
}
}
// Function to take input from the user and create a linked list
struct Node* createLinkedList()
{
struct Node* head = NULL;
int n, data;
printf("\nEnter the number of elements: ");
fflush(stdout);
scanf("%d", &n);
printf("\nEnter the elements:\n");
for (int i = 0; i < n; i++)
{
fflush(stdout);
scanf("%d", &data);
insertNode(&head, data);
}
return head;
}
// Function to take union of two linked lists
struct Node* getUnion(struct Node* head1, struct Node* head2) {
struct Node* result = NULL;
struct Node* temp = NULL;
int found = 0;
// Insert all elements of list1 into result
while (head1 != NULL)
{
insertNode(&result, head1->data);
head1 = head1->next;
}
// Insert elements of list2 into result
// that are not already present
while (head2 != NULL)
{
temp = result;
found = 0;
while (temp != NULL)
{
if (temp->data == head2->data)
{
found = 1;
}
temp = temp->next;
}
if (found == 0)
{
insertNode(&result, head2->data);
}
head2 = head2->next;
}
return result;
}
// Function to take intersection of two linked lists
struct Node* getIntersection(struct Node* head1, struct Node* head2)
{
struct Node* result = NULL;
struct Node* temp = NULL;
// Traverse list1 and check each element
// if it is present in list2, then insert into result
while (head1 != NULL)
{
temp = head2;
while (temp != NULL)
{
if (head1->data == temp->data)
{
insertNode(&result, head1->data);
}
temp = temp->next;
}
head1 = head1->next;
}
return result;
}
int main()
{
// Create linked lists from user input
printf("Create List 1\n");
struct Node* list1 = createLinkedList();
printf("\nCreate List 2\n");
struct Node* list2 = createLinkedList();
// Print the original lists
printf("\nList 1: ");
display(list1);
printf("\nList 2: ");
display(list2);
// Find and print the union of the lists
struct Node* unionList = getUnion(list1, list2);
printf("\n\nUnion: ");
display(unionList);
// Find and print the intersection of the lists
struct Node* intersectionList = getIntersection(list1, list2);
printf("\nIntersection: ");
display(intersectionList);
// Free memory allocated for the lists
// Freeing the memory allocated for unionList and intersectionList
struct Node* temp;
while (unionList != NULL)
{
temp = unionList;
unionList = unionList->next;
free(temp);
}
while (intersectionList != NULL)
{
temp = intersectionList;
intersectionList = intersectionList->next;
free(temp);
}
return 0;
}