Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List
/*
* pt.c
*
* Created on: 23-Oct-2023
* Author: Lenovo
*/
#include <stdio.h>
#include <stdlib.h>
// Define a structure for a node in a linked list
struct Node {
int data;
struct Node* next;
};
// Function to insert a new node at the end of a linked list
void insertNode(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
} else {
struct Node* current = *head;
while (current->next != NULL) {
if (current->data == data) {
free(newNode); // Free the newly allocated node to avoid duplicates
return;
}
current = current->next;
}
if (current->data == data) {
free(newNode); // Free the newly allocated node to avoid duplicates
} else {
current->next = newNode;
}
}
}
// Function to find the intersection of two linked lists
struct Node* findIntersection(struct Node* list1, struct Node* list2) {
struct Node* result = NULL;
while (list1 != NULL) {
struct Node* temp = list2;
while (temp != NULL) {
if (list1->data == temp->data) {
insertNode(&result, list1->data);
break;
}
temp = temp->next;
}
list1 = list1->next;
}
return result;
}
// Function to find the union of two linked lists
struct Node* findUnion(struct Node* list1, struct Node* list2) {
struct Node* result = NULL;
struct Node* temp1 = list1;
struct Node* temp2 = list2;
while (temp1 != NULL) {
insertNode(&result, temp1->data);
temp1 = temp1->next;
}
while (temp2 != NULL) {
insertNode(&result, temp2->data);
temp2 = temp2->next;
}
return result;
}
// Function to display the elements of a linked list
void displayList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
struct Node* list1 = NULL;
struct Node* list2 = NULL;
printf("Enter elements of the first list (enter -1 to stop):\n");
fflush(stdout);
int data;
while (1) {
scanf("%d", &data);
if (data == -1) {
break;
}
insertNode(&list1, data);
}
printf("Enter elements of the second list (enter -1 to stop):\n");
fflush(stdout);
while (1) {
scanf("%d", &data);
if (data == -1) {
break;
}
insertNode(&list2, data);
}
struct Node* intersection = findIntersection(list1, list2);
struct Node* unionList = findUnion(list1, list2);
printf("Intersection of the two lists: ");
fflush(stdout);
displayList(intersection);
printf("Union of the two lists: ");
fflush(stdout);
displayList(unionList);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
These are standard C library headers. stdio.h is included for input and output operations, and stdlib.h for memory allocation functions like malloc.
struct Node {
int data;
struct Node* next;
};
This defines a structure called Node that represents a node in a linked list. It contains an integer data and a pointer next to the next node in the list.
void insertNode(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
} else {
struct Node* current = *head;
while (current->next != NULL) {
if (current->data == data) {
free(newNode); // Free the newly allocated node to avoid duplicates
return;
}
current = current->next;
}
if (current->data == data) {
free(newNode); // Free the newly allocated node to avoid duplicates
} else {
current->next = newNode;
}
}
}
This is the insertNode function used to insert a new node with data data at the end of a linked list. It also checks for duplicates to avoid adding the same value multiple times. The code first allocates memory for a new node, sets its data and next pointer to NULL. If the list is empty (*head == NULL), the new node becomes the first element. Otherwise, it traverses the list to find the last node. If a duplicate value is found, the newly allocated node is freed. If the data is unique, the new node is appended to the end.
struct Node* findIntersection(struct Node* list1, struct Node* list2) {
struct Node* result = NULL;
while (list1 != NULL) {
struct Node* temp = list2;
while (temp != NULL) {
if (list1->data == temp->data) {
insertNode(&result, list1->data);
break;
}
temp = temp->next;
}
list1 = list1->next;
}
return result;
}
This function, findIntersection, takes two linked lists, list1 and list2, and returns a new list containing the intersection of their elements. It iterates through both lists, comparing elements. When a match is found, it inserts the common element into the result list using the insertNode function.
struct Node* findUnion(struct Node* list1, struct Node* list2) {
struct Node* result = NULL;
struct Node* temp1 = list1;
struct Node* temp2 = list2;
while (temp1 != NULL) {
insertNode(&result, temp1->data);
temp1 = temp1->next;
}
while (temp2 != NULL) {
insertNode(&result, temp2->data);
temp2 = temp2->next;
}
return result;
}
The findUnion function takes two linked lists, list1 and list2, and returns a new list containing the union of their elements. It iterates through both lists and uses the insertNode function to insert unique elements into the result list.
void displayList(struct Node* head) {
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
The displayList function is used to print the elements of a linked list pointed to by head. It iterates through the list and prints each element.
int main() {
struct Node* list1 = NULL;
struct Node* list2 = NULL;
printf("Enter elements of the first list (enter -1 to stop):\n");
fflush(stdout);
int data;
while (1) {
scanf("%d", &data);
if (data == -1) {
break;
}
insertNode(&list1, data);
}
printf("Enter elements of the second list (enter -1 to stop):\n");
fflush(stdout);
while (1) {
scanf("%d", &data);
if (data == -1) {
break;
}
insertNode(&list2, data);
}
struct Node* intersection = findIntersection(list1, list2);
struct Node* unionList = findUnion(list1, list2);
printf("Intersection of the two lists: ");
fflush(stdout);
displayList(intersection);
printf("Union of the two lists: ");
fflush(stdout);
displayList(unionList);
return 0;
}
The main function is the program's entry point. It defines two linked lists, list1 and list2, takes user input for these lists, calls the intersection and union functions, and displays the results. Finally, it returns 0 to indicate successful program execution. The program reads integer values from the user until -1 is entered, builds two linked lists, finds their intersection and union, and then displays the results.