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

Project

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

Aim:

• The union of two sets A and B is the set of all those elements which are either in A or in B, i.e. A ∪ B, whereas the intersection of two sets A and B is the set of all elements which are common
• The intersection of these two sets is denoted by A ∩ B

Program code:

#include
#include

struct Node //initilizes the structure data type
{
int data; //declared the integer data type
struct Node* next; // a structure node and stores the address of next variable
};

void push(struct Node** head_ref, int new_data); // the head of a list and an int, inserts a new node on the front of the list.
int isPresent(struct Node* head, int data); //initlizes the data in pointer of user data

struct Node* getUnion(struct Node* head1, struct Node* head2) // get union of two linked lists head1 and head2
{
struct Node* result = NULL; //creating a linked list
struct Node *n1 = head1, *n2 = head2; // Traverse both lists and store the element in the resu1tant list.
// Insert all elements of list1 to the result list
while (n1 != NULL) //initilizes he while loop if list1 is not equal to NULL
{
push(&result, n1->data); //push the data into list 1 and store in result
n1 = n1->next; // data is returned to store and next user input data in list 1
}

// Insert those elements of list2 which are not present in result list
while (n2 != NULL) //initilizes the while loop list2 not present in result
{
if (!isPresent(result, n2->data)) //initilizes the if loop list2 not present in result
{
push(&result, n2->data); //push the data inti list2
}
n2 = n2->next; // data is returned to store and next user input data in list2
}
return result; //main function returning to the result
}

// get intersection of two linked lists head1 and head2
struct Node* getIntersection(struct Node* head1, struct Node* head2)
{
struct Node* result = NULL;
struct Node* n1 = head1;
// Traverse list1 and search each element of it in list2.
//If the element is present in list 2, then insert the element to result
while (n1 != NULL) //initilizes the while loop list is not equal to null
{
if (isPresent(head2, n1->data)) //if loop data transverse to list 1 into head 2 location
{
push(&result, n1->data); //push the result of data into list1 into result
}
n1 = n1->next; // data is returned to store and next user input data in list 1
}
return result; //main function returning to the result
}
void push(struct Node** head_ref, int new_data)// insert a node at the beginning of a linked list
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));// allocate node and its size of node
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}

void printList(struct Node* node) // function to print a linked list
{
while (node != NULL) //initilizes the node data not equal to NULL
{
printf("%d ", node->data); //print the node data
node = node->next; //store the next input data from user
}
}
// function that returns true if data is present in linked list else return false
int isPresent(struct Node* head, int data)
{
struct Node* n = head; //node of pointer location to head of data
while (n != NULL) //initilizes the while loop transeverse list not equal to null
{
if (n->data == data) //initilizes data transper into transverse to data
{
return 1; //main function successfully executed by aruguments of function by returning 1
}
n = n->next; //transverse list data stores next input from user
}
return 0; //main function successfully executed by returning by 0
}

int main() // Driver program to test above function using main function
{
int p,q,temp; //declared the variables n,m and temp

printf("enter the value of number of value in link list(both): ");
fflush(stdout);
scanf("%d %d", &p, &q);
// structure pointer with the empty list
struct Node* head1 = NULL;
struct Node* head2 = NULL;
struct Node* intersecn = NULL;
struct Node* unin = NULL; NULL;
for(int i=0;i{
printf("Enter the value in link list1 %d: ",i); //print enter values in list 1
fflush(stdout);
scanf("%d", &temp);
push(&head1, temp); //push the data`from head 1 into temporary storage
}
//for loop for link list2
for(int i=0;i{
printf("Enter the value in link list2 %d: ",i); //print the enter values in list 1
fflush(stdout);
scanf("%d", &temp);
push(&head2, temp); //push the data`from head 2 into temporary storage
}
//function calling with structure pointer as argument
intersecn = getIntersection(head1, head2); //call the function of intersection
unin = getUnion(head1, head2); //call the function of union
printf("\n First list is ");
printList(head1);
printf("\n Second list is ");
printList(head2);
printf("\n Intersection list is ");
printList(intersecn);
printf("\n Union list is ");
printList(unin);
return 0;
}

OUTPUT:

Logic and Comments

• Linked List is a linear data structure
• Each node stores the data and the address of the next node
• Linked list is created of struct node which contains a data of integer datatype and address of the next node
• Inserting a node infront of linked list  as  void insert(struct Node** head_ref, int new_data); where **head denotes where the head is pointed and what is data stored
• Function to get union of two linked lists head1 and head2 with syntax
  struct Node* get_Union(struct Node* head1, struct Node* head2)
• Insert all elements of list1 to the result list using While loop, while the t1 is not equal to null and points to next data
• Similary with another while loop insert those elements of list2 which are not present in result list
• Function to get intersection of two linked lists head1 and head2 with syntax
  struct Node* get_Intersection(struct Node* head1, struct Node* head2)
• Traverse list1 and search each element of it in list2. If the element is present in list 2, then insert the element to result using while loop
• To insert a node at the beginning of linked list using malloc with syntax struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); where memory allocation depends on the size of node
• The int data passed new_data is the new_node data  and pointer of new_node will be pointed to the head of the linked list
• The head is then moved to the new node ,mark new node as the head of the linked list
• Function is printed to link list using the syntax void print_List(struct Node* node) , void is used as there is nothing to return while printing the linked list
• int is_Present(struct Node* head, int data) is the syntax used to search an element in linked list linearly traversing  ,the element to be searched and the address of head pointed are defined here
• p,q and temp are initialized to be integer datatypes
• If head is NULL , node is empty otherwise the pointed variable at head points to the next one
• Always intialize the linked list with NULL inorder to avoid storing of any by default value to memory
•  Started structure pointer with the empty list :struct Node* head1 = NULL;
  struct Node* head2 = NULL;
  struct Node* intersect = NULL;
  struct Node* unin = NULL;
• In main function , we are calling the function declared earlier
• First we enter the number of elements in both the list
• The values of linked list1 and linked list2 are entered with the help of for loops
• Call the function of intersection and union
• Function calling with structure pointer as argument is done and both the lists are printed also intersection and union of the list is found out throug this program

Result:

• Created a user define data to implement the user interfacces for working with set using Linked list
• Union and intersection of sets is found with the help of program.