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

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

Solution:

C-Program:

#include <stdio.h>
#include <stdlib.h>

// Structure for a node in the linked list
struct Node {
int data;
struct Node* next;
};

// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

// Function to insert a new node at the end of the linked list
void insertNode(struct Node** head, int value) {

struct Node* newNode = createNode(value);
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}

// Function to print the elements of the linked list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

// Function to compute the intersection of two linked lists
struct Node* setIntersection(struct Node* list1, struct Node* list2) {
struct Node* result = NULL;
struct Node* temp1 = list1;
while (temp1 != NULL) {
struct Node* temp2 = list2;
while (temp2 != NULL) {
if (temp1->data == temp2->data) {
insertNode(&result, temp1->data);

break;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}
return result;
}

// Function to compute the union of two linked lists
struct Node* setUnion(struct Node* list1, struct Node* list2) {
struct Node* result = NULL;
struct Node* temp1 = list1;
while (temp1 != NULL) {
insertNode(&result, temp1->data);
temp1 = temp1->next;
}
struct Node* temp2 = list2;
while (temp2 != NULL) {
insertNode(&result, temp2->data);
temp2 = temp2->next;
}
return result;
}

int main() {
struct Node* list1 = NULL;
struct Node* list2 = NULL;

// Inserting elements into the first list
insertNode(&list1, 101);

insertNode(&list1, 102);
insertNode(&list1, 103);

// Inserting elements into the second list
insertNode(&list2, 103);
insertNode(&list2, 104);
insertNode(&list2, 105);

printf("List 1: ");
printList(list1);

printf("List 2: ");
printList(list2);

// Computing the intersection of the two lists
struct Node* intersection = setIntersection(list1, list2);
printf("Intersection: ");
printList(intersection);

// Computing the union of the two lists
struct Node* unionSet = setUnion(list1, list2);
printf("Union: ");
printList(unionSet);

return 0;
}

Description:

1. We start by including the necessary header files: stdio.h for input/output operations and stdlib.h for dynamic memory allocation.
2. We define a structure called Node that represents a node in the linked list. It has two members: data to store the data value and next to point to the next node in the list.
3. The createNode function is used to create a new node and initialize its data and next pointer. It takes a value as input and returns a pointer to the newly created node.
4. The insertNode function is responsible for inserting a new node at the end of the linked list. It takes a double pointer to the head of the list and a value to be inserted. If the list is empty, it creates a new node and assigns it as the head.
Otherwise, it traverses to the end of the list and adds the new node there.
5. The printList function is used to print the elements of the linked list. It takes a pointer to the head of the list and iterates through the list, printing each node's data value.
6. The setIntersection function computes the intersection of two linked lists. It takes pointers to the heads of the two lists as input and returns a new linked list representing the intersection. It traverses through the first list and for each node, it traverses through the second list to find any matching elements. If a match is found, it inserts that element into the result list.
7. The setUnion function computes the union of two linked lists. It takes pointers to the heads of the two lists as input and returns a new linked list representing the union. It traverses through the first list and inserts each element into the
result list. Then, it traverses through the second list and inserts any non- duplicate elements into the result list.
8. In the main function, we create two empty linked lists: list1 and list2.
9. We then insert elements into list1 and list2 using the insertNode function.
10. We print the contents of list1 and list2 using the printList function.
11. We compute the intersection of list1 and list2 by calling the setIntersection function and store the result in the intersection variable.
12. We print the intersection by calling the printList function with intersection as the argument.
13. We compute the union of list1 and list2 by calling the setUnion function and store the result in the unionSet variable.
14. We print the union by calling the printList function with unionSet as the argument.
15. Finally, the program ends with a return 0 statement.

Output: