Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List

/*Set theory is the mathematical theory of well-determined collections, called sets, of objects
that are called members, or elements, of the set.*/

#include
#include

// A structure of linked list node
struct node

{
int data;
struct node *next;

} *FirstList, *SecondList, *Union_List, *Intersection_List;

void insert(struct node **head, int num)//Inserts a given node in front of a single linked list.

{
struct node* newNode = (struct node*) malloc(sizeof(struct node));// Create a new List node
newNode->data = num;
newNode->next = *head;// Next pointer of new node will point to head node of list
*head = newNode;//make new node as new head of list
}

int search(struct node *head, int num)// Searches an element in List by linearly traversing from head to null

{
while (head != NULL)

{
if (head->data == num)

{
return 1;
}
head = head->next;
}
return 0;

}

/*Set A is said to be a subset of Set B if all the elements of Set A are also present in Set B.
In other words, set A is contained inside Set B.*/

int SubSet(struct node *FirstList, struct node *SecondList)
{
struct node* p = FirstList, *q = SecondList;
int checker=0;

for(p=FirstList;p!=NULL;p=p->next){
for(q=SecondList;q!=NULL;q=q->next){
if(q->data==p->data){
checker=1;
break; // The element is found, no need to go further in SecondList
}
}
}

return checker;
}

/*The union of two sets A and B is defined as the set of all the elements
which lie in set A and set B or both the elements in A and B altogether.
The union of the set is denoted by the symbol '∪'.*/

struct node* findunion(struct node *FirstList, struct node *SecondList)//Returns the union of two given linked list*/

{
Union_List = NULL;
struct node *temp = FirstList; // Add all nodes of first Linked List to temp list
while(temp != NULL)

{
insert(&Union_List, temp->data);// Insert nodes of temp list into unionList
temp = temp->next;
}
while(SecondList != NULL)

{
if(!search(FirstList, SecondList->data))

{
insert(&Union_List, SecondList->data);// Insert those nodes of SecondList which is not present in FirstList
}
SecondList = SecondList->next;
}
return Union_List;
}

/*The intersection of sets can be denoted using the symbol '∩'.
As defined above, the intersection of two sets A and B is the set of all those elements
which are common to both A and B. Symbolically,
we can represent the intersection of A and B as A ∩ B.*/

struct node* findintersection(struct node *FirstList, struct node *SecondList)
//Returns the Linked List which contains common nodes of two given linked list

{
Intersection_List = NULL;
//Search every element of FirstList in SecondList, If found then add it to intersection List
while(FirstList != NULL)

{
if(search(SecondList, FirstList->data))

{
insert(&Intersection_List, FirstList->data);
}
FirstList = FirstList->next;
}
return Intersection_List;
}

void displayList(struct node *nodePtr)//Prints a linked list from head node till null

{
while (nodePtr != NULL)

{
printf("%d", nodePtr->data);
nodePtr = nodePtr->next;
if(nodePtr != NULL)
printf(", ");

}
}

int main()

{
int i, FirstListCount, SecondListCount, temp;//declare two list nodecount and temp list
FirstList = SecondList = NULL;//initialize two list data as null
//Creating First linked List
printf("Enter number of nodes in first List\n");
scanf("%d", &FirstListCount);//to getting first list node count
printf("Enter %d integers\n", FirstListCount);
for(i=0; i

{
scanf("%d", &temp);//to getting first list node data
insert(&FirstList, temp);
}
displayList(FirstList);//to print FirstList data
printf("\nEnter number of nodes in second List\n");
scanf("%d", &SecondListCount);//to getting Second list node count
printf("Enter %d integers\n", SecondListCount);
for(i=0; i

{
scanf("%d", &temp);//to getting Second list node data
insert(&SecondList, temp);
}
displayList(SecondList);//to print SecondList data

if(SubSet(FirstList,SecondList)){
printf("\nFirst list is a subset of SecondList\n");//to print if First list is a subset of SecondList
}
else{
printf("\nFirst list is not a subset of SecondList\n");//to print if First list is not a subset of SecondList
}

findunion(FirstList, SecondList);//calling union function
findintersection(FirstList, SecondList);//calling intersection fuction
printf("\nUnion Linked List\n");
displayList(Union_List); //printing Union of two given linked list
printf("\nIntersection Linked List\n");
displayList(Intersection_List); //printing intersection of two given linked list

return 0;
}