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
- Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List
Overview of the Project:
The project uses a linked list to do the mathematical set operation. A linked list is a linear data structure containing the collection of data elements called nodes. The set operations perform some operations like the Union and intersection of the list created. In this project, we have used the Boolean expression as a pre-processor directive in the header file, the node pointer, and the node declaration. Users can give the input like two lists of data; this program will give the output with the union and the intersection of these two lists.
Goals:
- Implementation of user interfaces for mathematical Set Theory using C programming.
We are creating the structure as a typedef model to rename the user-defined name and creating two datatypes int and pointer. “Int” is for storing the integer value and the “pointer” is used to store the address of that value. We have created some functions like insertion() - function to insert a node at the beginning of a linked list, compare() - function to check if given data is present in a list, getUnion() - function to get the union of two linked lists h1 and h2, getIntersection() - Function to get the intersection of two linked lists h1 and h2, printList() - Function to print a linked list. Here, we had given two lists of data as input. To get union and intersection using the linked list concept.
- Giving two lists of data as input to get the output as union & Intersection for the given list of data.
Reads data from lists h1 and h2 by performing some operation in insertion function, Firstly allocate node => put the data => link the old list of the new node => move the head to point to the new node. Then compares both lists data and gets union and intersection output accordingly.
Key Highlights of the Project:
- Generating two lists of data using the linked list method.
Creating pointer variables h1 for the first list and h2 for the second list. Starts with empty lists by assigning Null to both the lists h1 and h2. Reads data from lists h1 and h2 by performing some operation in the insertion function, Firstly allocate node => put the data => link the old list of the new node => move the head to point to the new node and prints first and second list by using printList() function.
- Insert the node to 1st and 2nd list correspondingly.
It is used to display the data which is entered for list 1 and list 2. Starts the structure pointer with an empty list and performs some operation in the insertion function and reads the value and prints the list accordingly.
- The Intersection of data of two lists.
In this function, we are using list 1 and 2 data, comparing both the data and it returns a value that is commonly used in both lists by using the “if” operation. Accordingly checks list 1 and search for each element of list 2, if the element is present in list 2 then insert the element 2 results.
- Obtaining Union of two lists.
Function to get the union of two linked lists h1 and h2. Insert all elements of list 1 into the result list. Insert those elements of the list2 which are not present in the result list.
Deliverables of this project:
- The Intersection of data of two lists.
In this function, we are using list 1 and 2 data, comparing both the data and it returns a value that is commonly used in both lists by using the “if” operation. Accordingly checks list 1 and search for each element of list 2, if the element is present in list 2 then insert the element 2 results.
- Obtaining Union of two lists.
Function to get the union of two linked lists h1 and h2. Insert all elements of list 1 into the result list. Insert those elements of list 2 which are not present in the result list.
Expected Outcomes:
- By using the linked list we can create a set of elements.
- By using lists performing set theory operations like union and intersection.
- Comparing both lists by creating functions and using while, and if conditions to get expected outputs.
Code:
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
/* Linked list node */
struct Node {
int data;
struct Node* next;
};
/* Function to insert a node at the beginning of a linked list*/
void insertion(struct Node** head_ref, int new_data);
/* Function to check if given data is present in a list */
bool compare(struct Node* head, int data);
/* Function to get union of two linked lists h1 and h2 */
struct Node* getUnion(struct Node* h1,struct Node* h2)
{
struct Node* result = NULL;
struct Node *t1 = h1, *t2 = h2;
// Insert all elements of list1 to the result list
while (t1 != NULL) {
insertion(&result, t1->data);
t1 = t1->next;
}
// Insert those elements of list2 which are not present in result list
while (t2 != NULL) {
if (!compare(result, t2->data))
insertion(&result, t2->data);
t2 = t2->next;
}
return result;
}
/* Function to get intersection of two linked lists h1 and h2 */
struct Node* getIntersection(struct Node* h1, struct Node* h2)
{
struct Node* result = NULL;
struct Node* t1 = h1;
// Check list1 and search each element of it in list2. If the element is present in list 2, then insert the element to result
while (t1 != NULL) {
if (compare(h2, t1->data))
insertion(&result, t1->data);
t1 = t1->next;
}
return result;
}
/* Function to insert a node at the beginning of a linked list*/
void insertion(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list of the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print a linked list*/
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Function that returns true if data is present in linked list else return false */
bool compare(struct Node* head, int data)
{
struct Node* t = head;
while (t != NULL) {
if (t->data == data)
return 1;
t = t->next;
}
return 0;
}
/* Main program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* h1 = NULL;
struct Node* h2 = NULL;
struct Node* intersection = NULL;
struct Node* union1 = NULL;
/*create a linked list */
insertion(&h1, 2);
insertion(&h1, 4);
insertion(&h1, 8);
insertion(&h1, 6);
insertion(&h1, 5);
/*create a linked list */
insertion(&h2, 5);
insertion(&h2, 2);
insertion(&h2, 7);
insertion(&h2, 8);
insertion(&h2, 1);
intersection = getIntersection(h1, h2);
union1 = getUnion(h1, h2);
printf("\n First list is \n");
printList(h1);
printf("\n Second list is \n");
printList(h2);
printf("\n Intersection list is \n");
printList(intersection);
printf("\n Union list is \n");
printList(union1);
return 0;
}