Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List
/*
* Set_LinkList.c
*
* Created on: Sep 5, 2023
* Author: Deependra Bhati
*
* Project 1 - Creation of user defined data type to implement the user interfaces
* for working with ‘Set’ (Mathematical Set theory) using Linked List
*/
#include
#include
#include
//Define the node structure for the linked list
typedef struct Node
{
int data;
struct Node *next;
} Node;
//Define the set structure
typedef struct Set
{
Node *head; //pointer to first element of linked list
int size; //Number of elements in the Set
}Set;
//Function prototypes
Set *createSet(); // Function to create empty set
bool isEmpty(Set *set); // Function to check if set is empty
bool contains(Set *set,int element);// Function to check if the element exist in the Set
void add(Set *set,int element);//Function to add an element to a Set
Set *unionSet(Set* set1, Set* set2);
Set* intersectSet(Set* set1, Set* set2);
void removeElement(Set *set, int element); // Function to remove an element from the Set
void display(Set *set); //Function to display the elements of the set
void freeSet(Set *set); //Function to free the memory used by Set
int main()
{
// Create two sets and add elements
Set* setA = createSet(); //Create an empty set (Set is a user defined data type)
Set* setB = createSet(); //Create an empty set (Set is a user defined data type)
add(setA,1);
add(setA,2);
add(setA,3);
add(setB,2);
add(setB,3);
add(setB,4);
// Display the original sets
printf("Set A: ");
display(setA);
printf("Set B: ");
display(setB);
// Compute and display the union
Set* unionResult = unionSet(setA, setB);
printf("Union: ");
display(unionResult);
// Compute and display the intersection
Set* intersectResult = intersectSet(setA, setB);
printf("Intersection: ");
display(intersectResult);
// Clean up and free memory
freeSet(setA);
freeSet(setB);
freeSet(unionResult);
freeSet(intersectResult);
return 0;
}
// Function to create a new empty set
Set *createSet()
{
Set *set = (Set*)malloc(sizeof(Set)); // Allocate memory for the Set structure
set -> head = NULL; //Initialize head pointer to NULL,indicating an empty set
set -> size =0; // Initialize the size of the set to 0 as its currently empty
return set; // Return a pointer to newly created set
}
//Function to check if an element exists in the set
bool contains(Set *set,int element)
{
Node *current = set-> head; // Start from the head of the linked list
//Traverse the linked list to search for the element
while(current != NULL)
{
if(current->data==element)
{
return true; //Element found in the set
}
current = current ->next; // Move to next node
}
return false; // ELement not found in the set
}
//Function to check if set is empty
bool isEmpty(Set *set)
{
return set->size == 0; // If size is zero set is empty,so return true othervise return false
}
//Function to add an element to the set
add(Set *set, int element)
{
if(!contains(set,element))//only add the element if it is not already in the set
{
Node *new_node = (Node*)malloc(sizeof(Node)); // Allocate memory for a new node
new_node -> data = element; // Set the data of the new_node to the given element
new_node -> next = set -> head; //Make new node point to current head of the linked list
set->head = new_node; //Update head to the new node , making it the first element
set->size++; //Increment the size of the set
}
}
// Function to compute the union of two sets
Set* unionSet(Set* set1, Set* set2) {
Set* resultSet = createSet(); // Create an empty set for the result
// Iterate through set1 and add its elements to the result set
Node* current = set1->head;
while (current != NULL) {
add(resultSet, current->data);
current = current->next;
}
// Iterate through set2 and add its elements to the result set, avoiding duplicates
current = set2->head;
while (current != NULL) {
if (!contains(resultSet, current->data)) {
add(resultSet, current->data);
}
current = current->next;
}
return resultSet;
}
// Function to compute the intersection of two sets
Set* intersectSet(Set* set1, Set* set2) {
Set* resultSet = createSet(); // Create an empty set for the result
// Iterate through set1 and add its elements to the result set if they are also in set2
Node* current = set1->head;
while (current != NULL) {
if (contains(set2, current->data)) {
add(resultSet, current->data);
}
current = current->next;
}
return resultSet;
}
//Function to remove an element from the set
void removeElement(Set *set,int element)
{
Node *current = set->head; // Start from the head of the linked list
Node *prev = NULL; //Initialize pointer to keep track of the previous node
//Traverse the linked list to find the element to remove
while(current!=NULL)
{
if(current->data == element)
{
if(prev == NULL)
{
set->head = current->next; // If element to remove is the head, update the head to the next node
}
else
{
prev->next = current->next;//Link the previous node to the next node ,skipping the current node
}
free(current); //Free the memory of the current node
set->size--; //Decrement the size of the set
return; //exit the function after removing the element
}
prev = current; //Move previous node pointer to the current noode
current = current->next;// Move to the next node
}
}
//Function to display the elements of the set
void display(Set *set)
{
printf("Set: {");
Node *current =set->head; //Start from the head of the linked list
//Traverse the linked list to print the elements
while(current !=NULL)
{
printf("%d", current->data);
current =current->next; // Move to the next node
}
printf("}\n");
}
//Fnction to free memory used by set
void freeSet(Set *set)
{
Node *current = set->head; //Start from the head of the linked list
//Traverse the linked list to free the memory of all nodes
while(current!=NULL)
{
Node *temp =current;
current = current->next;
free(temp);
}
free(set); //Free memory used by set structure
}