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

Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List - Intersection and union of values of two Linked list

MATHEMATICAL SET THEORY:

• Set is s collection of objects or group of objects. For example. group of players in a cricket team is a set.

UNION:

A = {1,3,5,7,9} //List1

B = {3,6,9,12,15} //List2

then , A`union`B = {1,3,5,6,7,9,12,15} //Union operation

INTERSECTION:

A = {1,3,5,7,9} //List1

B = {3,6,9,12,15} //List2

then , A `intersection`B = {3,9} //Intersection operation

PROGRAM FLOW:

Following function are used to perform the intersection and union of mathematical set theory

• insert() - To inser the values in the modes
• doIntersection() - To do the intersection operation
• doUnion() - To do the union operation
• isPresent() - To check for the similar values present in the list1 and list2
• PrintList() - To print the values of the nodes in list1 and list2

1. Get the number of values to insert in list1
2. Get the number of values to insert in list2
3. Intialize all the structure pointer with NULL
4. Insert the values for the list1 by the function "insert()" in the for loop
5. Insert the values for the list1 by the function "insert()" in the for loop

6. Now all the values of the nodes are created by the above 5 steps as below

   

7. Now to perform the Intersection operation , i used 2 functions and stored that in variable " Intersect_output"
   1. doIntersection()
   2. isPresent()
8. When the doIntersection() function is called , "isPresent()" function is also called inside.Since to perform and print only the common values in Intersection logic "isPresent()" function is implemented.
9. If the values present in the list1 (t1 datas) is present in head2(list2) and if condition iin "isPresent()" function is true, again "insert()" function is called to insert the Intersection elements.
10. Now to perform the union, we use 2 functions and stored the variable in "Union_output".
    1. doUnion()
    2. isPresent()
11. When the doUnion() function is called, [As a union set theory, we need to print all the values of list1 and list2 and print the repeated values only ,once again we call "isPresent()" and "insert()" function to insert the union values] . t1 datas are list1 -> it prints all the datas. In t2 datas -> "isPresent()" is called to compare the t2 datas with t1 results to print the repeated datas only once.
12. Finally, since we have stored all the "doIntersection" function in "Intersect_output" and "getUnion" in "Union_output" variable , we called the "printList(intersect_output)" and "printList(union_output)" to print the final outputs of Intersection and union.

/*
 * Proj1.c
 *
 *  Created on: Sep 22, 2022
 *      Author: shankar Moorthy
 */
#include<stdio.h>
#include<stdlib.h>

// Link list node
struct Node			//structure declaration
 {
    int data;			//structure member
    struct Node* next;
};

//function definition to insert the linked list1 and linked list2 elements
void insert(struct Node** head_ref, int new_data)	//called function
{
    // allocating node
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;   //Insert new data in new node
    new_node->next = (*head_ref); //Move the new node to ref pointer of the node
    (*head_ref) = new_node; //The ref pointer points to the next new node to get the values to next node
}

// function definition to check for the same value is present or not and return 1 if present , return 0 if not present
// used in both doIntersection and doUnion function call
int isPresent(struct Node* head, int data)	//called function
{
    struct Node* t = head;		//structure pointer with the head
    while (t != NULL)
    {
        if (t->data == data)	//if condition
        {
            return 1;      //return function as 1 if equal
        }
        t = t->next;	//moving next to t
    }
    return 0;	//return function as 0 if not equal
}

// Function definition to perform the intersection of two linked lists
struct Node* doIntersection(struct Node* head1, struct Node* head2)
{
    struct Node* result = NULL;	//structure pointer with the empty list
    struct Node* t1 = head1;	//structure pointer with the empty list
    // list1 traverses through the list2(through head2)values if the same value is present in list 2, then insert the value to result
    while (t1 != NULL)
    {
        if (isPresent(head2, t1->data))	//caller function
        {
            insert(&result, t1->data);	//caller function
        }
        t1 = t1->next;		//assigning next to t1
    }
    return result;
}

// Function to get union of two linked lists using arguments head1 and head2
struct Node* doUnion(struct Node* head1, struct Node* head2)	//called function
{
    struct Node* result = NULL;				//structure pointer with the empty list
    struct Node *t1 = head1, *t2 = head2;	//structure pointer with the empty list
    // Insert all elements of list1 to the result list
    while (t1 != NULL)
    {
        insert(&result, t1->data);	//caller function
        t1 = t1->next;				//moving next to t
     }
    // Insert those elements of list2 which are not present in result list(Insert the list2 repeated values in list1 only once to get the union)
    while (t2 != NULL)
    {
        if (!isPresent(result, t2->data))	//caller function to check ispresent
        {
            insert(&result, t2->data);	//caller function for insert the result values
        }
        t2 = t2->next;
    }
    return result;		//return result
}


// function to print a final values of Intersection and union
void printList(struct Node* node)	// called function
{
    while (node != NULL)
    {
        printf("%d ", node->data);	//print the value in the console
        fflush(stdout);
        node = node->next;			//moving to next node
    }
}

int main()	//main function
{
    int x,y,value;
    printf("Enter the Linked list1 count:");
    fflush(stdout);
    scanf("%d", &x);
    printf("Enter the Linked list2 count:");
    fflush(stdout);
    scanf("%d", &y);

    // Intializing all the Struct nodes with NULL pointer
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;
    struct Node* intersect_output = NULL;
    struct Node* union_output = NULL;

    //Getting the list1 values
    printf("Enter the value for linked list1 :\n");
    fflush(stdout);
    for(int i=0;i<x;i++)
    {
        scanf("%d", &value);
        insert(&head1, value);	//function call to insert the list1 values
    }

    //Getting the list2 values
    printf("Enter the values for linked list2 :\n");
    fflush(stdout);
    for(int i=0;i<y;i++)
   {
        scanf("%d", &value);
        insert(&head2, value);	//function call to insert the list2 values

   }

    //Function calls to perform set therory operations union and intersection

    intersect_output = doIntersection(head1, head2); //function call to perform the intersect operation and stores the output in intersect_output

    union_output = doUnion(head1, head2);	//function call to perform the union operation and stores the output in union_output

    //Printing the final outputs of intersection and union
    printf("\n Intersection output: ");
    fflush(stdout);
    printList(intersect_output);		//function call to print the Intersection output
    printf("\n Union output: ");
    fflush(stdout);
    printList(union_output);            //function call to print the union output
    return 0;
}

OUTPUT: