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

Overview of the project:

In mathematical set theory, a set is defined as a collection of elements which may be mathematical (e.g. numbers, functions) or not. If there are two sets, A and B, then A U B (A union B) is the collection of all the elements of A as well as all the elements of B. A ⋂ B (A intersection B) is the collection of those elements that are common to both A and B. For e.g. if A = {1,2,3,4,5} and B = {3,4,5,6,7}, then

A U B = {1,2,3,4,5,3,4,5,6,7}

and

A ⋂ B = {3,4,5}

In this program, I have written the code to create two linked lists containing integers as the data elements of two sets and compute the union and intersection of both the linked lists.

Goals:

The goals of this project are to:

1. Create the user interface for mathematical set theory using C programming

2. Computing the union and intersection of the two linked lists and displaying it as the output.

1. Implementation of the interface for mathematical set theory:

In order to create the linked lists, I have first declared a self-referential structure named 'node' which consists of 1 integer variable named 'data' and a pointer variable named 'next' which is of the same data-type as the structure 'node'. I have declared four function prototypes named, 'creating_node_list', 'displaying_node_list', 'intersection_lists' and 'union_lists'.

In the main function, I have acquired the values of the number of nodes for each linked list and the called the function 'creating_node_list' twice with the number of nodes as the input argument to the function each time. I have requested the user to enter which linked list should be displayed and displayed the corresponding linked list. Then, depending on the user's choice I have called the functions to compute and display the intersection and union of the two linked lists.

2. Creation, display, intersection and union of the two linked lists:

In order to create the linked list, I have used a for loop that iterates as many times as the number of nodes entered by the user. In the for loop, I have used dynamic memory allocation (malloc function) to allocate the memory for a single node. I have acquired the value to be stored from the user and saved it to the integer variable of the structure. Then I have stored '0' in the pointer variable of the structure since it is the last node of the linked list. Then, I have stored the address of the node which is contained in the pointer 'newnode' into the 'head' pointer as well as the 'temp' pointer. The 'temp' pointer gets updated to point to the next node everytime the for-loop is executed. This creates the node list.

To display the linked list, I have requested the user to enter which list should be displayed and intialized the 'temp' pointer to point to the address of the first node of the corresponding linked list. I have done this by using two pointers dedicated to point to the address of the first node of each linked list. These pointers are named, 'first_list' and 'second_list'. Then the 'temp' pointer traverses the corresponding the linked list and prints the data in the console.

To compute and display the intersection of the two lists, I have initialized 'tmp1' pointer to point to the address of the first node of the first linked list and initialized 'tmp2' pointer to point to the address of the first node of the second linked list. I have used a while loop which is executed as long as neither of the pointers is NULL. As the 'tmp1' pointer traverses the first linked list, only those values which are common to both linked lists are printed. When 'tmp1' pointer completes traversal of the first linked list, 'tmp2' pointer is updated to point to the next element of the second linked list and the 'tmp1' pointer is re-initialized to point to the first node of the first linked list. This each element of the first linked list is compared to each element of the second linked list and only the elements which are common to both are printed.

To compute and display the union of the two sets, I have used 'tmp1' pointer to traverse and display all the elements of the first linked list. After this is done, I have used 'tmp2' pointer to traverse and display all the elements of the second linked list.

One of the highlights of the program is that I have also included one function to insert nodes into either of the two linked lists after they have been created if necessary. To accomplish this, I have initialized four integer variables named sel, pos, i and j. I request the user to verify whether any nodes need to be inserted in either the first linked list or the second linked list or in neither. Depending on the user input, I initialize the 'temp' pointer to point to the first node of either the first linked list or the second linked list. Then, I acquire from the user, the position of the node after which the new node needs to be inserted. If the position is more than the number of nodes in the list, then an error message is displayed. If the position is less than or equal to the number of nodes in the list then the 'temp' pointer traverses the list till the node after which the new node needs to be inserted. Then the 'next' field is updated with the address of the next node and the next field of the previous node is updated with the address of the new node. Thus, the new node is inserted in the required position.

====================================================================

I will type the program below so that it can be tested on an online compiler. I will also include the source file for the program in the attachments as well as the output screenshots.

PROGRAM:

/*
* Challenge_6.c
*
* Created on: Jun 22, 2022
* Author: Admin
*/
#include <stdio.h>
#include <stdlib.h>

/*Declaration of data type of node in the form of a structure*/
typedef struct
{
int data;
struct node *next;
} node;

/*Declaration of function prototypes for creating, displaying, inserting, intersection and union of linked lists*/
void creating_node_list(int n); //Function prototype for creating a linked list
void displaying_node_list(); //Function prototype for displaying chosen linked list
void intersection_lists(); //Function prototype to compute the intersection of two sets
void union_lists(); //Function prototype to compute the union of two sets
void inserting_node(); //Function prototype for inserting a node in the chosen linked list

/*Declaration on integer variables
* num1: Number of nodes in the first linked list
* num2: Number of nodes in the second linked list
* intersel: Integer variable to select whether the intersection of the two sets should be displayed
* unisel: Integer variable to to select whether the union of the two sets should be displayed */

int num1, num2, intersel, unisel;

/*Declaration of pointers of type 'node'
* head: Pointer to store the address of the first node while creating the node list
* newnode: Pointer to store the address of the newly created node
* temp: Pointer to traverse the linked list
* first_list: Pointer to store the 'head' address of the first linked list
* second_list: Pointer to store the 'head' address of the second linked list
* tmp1: Pointer to traverse the first linked list while executing intersection and union functions
* tmp2: Pointer to traverse the second linked list while executing intersection and union functions*/

node *head, *newnode, *temp, *first_list, *second_list, *tmp1, *tmp2;

int main()
{
printf("\n Enter the number of nodes of first list: ");
fflush(stdout);
scanf(" %d",&num1); //Acquisition of number of nodes of the first list from the user
printf("\n Enter the number of nodes of second list: ");
fflush(stdout);
scanf(" %d",&num2); //Acquisition of number of nodes of the second list from the user
creating_node_list(num1); //Calling the function to create first linked list
first_list = head; //Storing the address of the first node of the first linked list
creating_node_list(num2); //Calling the function to create second linked list
second_list = head; //Storing the address of the first node of the second linked list
displaying_node_list(); //Calling the function to display the chosen linked list
inserting_node(); //Calling the function to insert a node in the chosen linked list
printf("\n Do you want to print the intersection of the two lists? ");
printf("\n Enter '1' for 'YES and Enter '0' for 'NO'");
fflush(stdout);
scanf(" %d",&intersel); //Acquisition of user input to either display or not display the intersection of the two sets
if(intersel == 1)
{
intersection_lists(); //Calling the intersection function based on user input
}
printf("\n Do you want to print the union of the two lists? ");
printf("\n Enter '1' for 'YES and Enter '0' for 'NO'");
fflush(stdout);
scanf(" %d",&unisel); //Acquisition of user input to either display or not display the union of the two sets
if(unisel == 1)
{
union_lists(); //Calling the union function based on user input
}
return(0);
}

/*Function to create nodes of the linked list*/

void creating_node_list(int n)
{
int i = 1;
head = 0;
temp = head;
printf("\n ********* Creation of a new list ********** \n");
for(i=1;i<=n;i++)
{
newnode = (node *)malloc(sizeof(node)); //Dynamic memory allocation to create a node
if(newnode == 0)
{
printf("\n Error in memory allocation.");
}
else
{
printf("\n Enter the data for the '%d' node of the list: ",i);
fflush(stdout);
scanf(" %d",&newnode->data); //Acquisition of the data to be stored in each node
newnode->next = 0; //Declaring the newly created node as the last node of the linked list
if(head == 0)
{
head = temp = newnode; //Storing the address of the first node in 'head' and 'temp' pointers
}
else
{
temp->next = newnode; //Storing the address of the newly created node in the 'next' field of the previous node
temp = newnode; //'temp' points to the newly created node
}
}
}
}

/*Function to display chosen linked list*/

void displaying_node_list()
{
int choice;
while(1)
{
printf("\n Do you want to display the first list, the second list or neither list? ");
printf("\n Enter '1' for first list, '2' for second list or '0' for neither: ");
fflush(stdout);
scanf(" %d",&choice); //Acquiring the user's choice for displaying the linked lists
if(choice == 1)
{
temp = first_list; //'temp' is initialized to point to the address of the first node of the first linked list
printf("\n The data in the first linked list is as follows: ");
while(temp != 0)
{
printf("\n Data: %d",temp->data);
temp = temp->next; //Traversing the first linked list
}
}
else if(choice == 2)
{
temp = second_list; //'temp' is initialized to point to the address of the first node of the second linked list
printf("\n The data in the second linked list is as follows: ");
while(temp != 0)
{
printf("\n Data: %d",temp->data);
temp = temp->next; //Traversing the second linked list
}
}
else if(choice == 0)
{
printf("\n --------------------------------------------------------------------");
break; //Exit while loop when use does not want to display either linked list
}
}
}

/*Function to insert a node in the linked list*/

void inserting_node()
{
/*Declaration of integer variables for inserting a node
* sel: integer variable to select which linked list, the node should be inserted in
* pos: integer variable to select the position where the node should be inserted
* i: integer variable to traverse the linked list upto the position where the node should be inserted*/

int sel, pos, i, j;
while(1)
{
printf("\n Do you want to insert a node in the first or second linked list?");
printf("\n Enter '1' for first linked list, '2' for second linked list and '0' for neither");
fflush(stdout);
scanf(" %d",&sel); //Acquisition of the choice of linked list where node should be inserted
if(sel == 1)
{
temp = first_list; //Initializing 'temp' pointer to the address of the first node of the first linked list
printf("\n Enter the position of the node after which a new node should be inserted: ");
fflush(stdout);
scanf(" %d",&pos); //Acquisition of the position where the node should be inserted
if(pos>num1)
{
printf("\n Enter valid position: ");
}
else if(pos !=0 && pos<=num1)
{
newnode = (node *)malloc(sizeof(node)); //Creation of the node
printf("\n Enter the data for the node to be inserted: ");
fflush(stdout);
scanf(" %d",&newnode->data); //Acquisition of the data to be stored in the new node
for(i=2;i<=pos;i++)
{
temp = temp->next; //Traversal of first linked list upto the node after which a new node is to be inserted
}
newnode->next = temp->next; //Updating the newnode with address of the next node
temp->next = newnode; //Updating the previous node with address of the new node
}
else if(pos == 0)
{
newnode = (node *)malloc(sizeof(node));
printf("\n Enter the data for the node to be inserted: ");
fflush(stdout);
scanf(" %d",&newnode->data); //Acquisition of the data to be stored in the new node
newnode->next = temp; //Updating the new node with address of the next node
temp = newnode; //Updating the previous node with address of the new node
first_list = temp; //Updating the pointer 'first_list' with the new address
}
}
if(sel == 2) //All the operations are the same as above but for the second linked list
{
temp = second_list;
printf("\n Enter the position of the node after which a new node should be inserted: ");
fflush(stdout);
scanf(" %d",&pos);
if(pos>num2)
{
printf("\n Enter valid position: ");
}
else if(pos !=0 && pos<=num2)
{
newnode = (node *)malloc(sizeof(node));
printf("\n Enter the data for the node to be inserted: ");
fflush(stdout);
scanf(" %d",&newnode->data); //Acquisition of the data to be stored in the new node
for(j=2;j<=pos;j++)
{
temp = temp->next; //Traversal of second linked list upto the node after which a new node is to be inserted
}
newnode->next = temp->next;
temp->next = newnode;
}
else if(pos == 0)
{
newnode = (node *)malloc(sizeof(node));
printf("\n Enter the data for the node to be inserted: ");
fflush(stdout);
scanf(" %d",&newnode->data); //Acquisition of the data to be stored in the new node
newnode->next = temp;
temp = newnode;
second_list = temp;
}
}
if(sel == 0)
{
printf("\n -------------------------------------------------------");
break;
}
}
}

/*Function to compute the intersection of two sets stored in two different linked lists*/

void intersection_lists()
{
tmp1 = first_list; //Initializing 'tmp1' to point to the address of the first node of the first linked list
tmp2 = second_list; //Initializing 'tmp2' to point to the address of the first node of the second linked list
printf("\n The intersection of the two lists is as follows: ");
while(tmp1 != 0 && tmp2 != 0)
{
if(tmp1->data == tmp2->data) //Displaying only those values which are common to both linked lists
{
printf("\n Data: %d ",tmp1->data);
}
tmp1 = tmp1->next; //Traversing the first linked list

if(tmp1 == 0) //After traversing the first linked list completely
{
tmp1 = first_list; //Reinitializing 'tmp1' to point to the address of the first node of the first linked list
tmp2 = tmp2->next; //Traversing the second linked list
}
}
printf("\n ---------------------------------------------------------------");
}

/*Function to compute the union of two sets stored in two different linked lists*/

void union_lists()
{
tmp1 = first_list; //Initializing 'tmp1' to point to the address of the first node of the first linked list
tmp2 = second_list; //Initializing 'tmp2' to point to the address of the first node of the second linked list
printf("\n The union of the two lists is as follows: ");
while(tmp1 != 0)
{
printf("\n Data: %d",tmp1->data);
tmp1 = tmp1->next; //Traversing the first linked list
}
while(tmp2 != 0)
{
printf("\n Data: %d",tmp2->data);
tmp2 = tmp2->next; //Traversing the second linked list
}
printf("\n -------------------------------------------------------------");
}

====================================================================