Project 1 - Creation of user defined data type to implement the user interfaces for working with ‘Set’ (Mathematical Set theory) using Linked List
1)In this project, interfaces for mathematical Set Theory are implemented using C programming language. User can give the input like two list of data and this program will give the output as the union and intersection of these two lists
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// Link list node
struct Node {
int data;
struct Node* next;
};
//function declaration
void push(struct Node** head_ref, int new_data);
int isPresent(struct Node* head, int data);
// Function to get union of two linked lists head1 and head2
struct Node* getUnion(struct Node* head1, struct Node* head2)
{
struct Node* result = NULL;
struct Node *t1 = head1, *t2 = head2;
// Insert all elements of list1 to the result list
while (t1 != NULL)
{
push(&result, t1->data);
t1 = t1->next;
}
// Insert those elements of list2 which are not present in result list
while (t2 != NULL)
{
if (!isPresent(result, t2->data))
{
push(&result, t2->data);
}
t2 = t2->next;
}
return result;
}
// Function to get intersection of two linked lists head1 and head2
struct Node* getIntersection(struct Node* head1, struct Node* head2)
{
struct Node* result = NULL;
struct Node* t1 = head1;
// Traverse 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 (isPresent(head2, t1->data))
{
push(&result, t1->data);
}
t1 = t1->next;
}
return result;
}
// A utility function to insert a node at the beginning of a linked list
void push(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 off 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
int isPresent(struct Node* head, int data)
{
struct Node* t = head;
while (t != NULL)
{
if (t->data == data)
{
return 1;
}
t = t->next;
}
return 0;
}
// Driver program to test above function
int main()
{
int n,m,temp;
printf("enter the value of number of value in link list(both):-");
fflush(stdout);
scanf("%d %d", &n, &m);
// Starth structure pointer with the empty list
struct Node* head1 = NULL;
struct Node* head2 = NULL;
struct Node* intersecn = NULL;
struct Node* unin = NULL;
//for loop for link list1
for(int i=0;i<n;i++)
{
printf("Enter the value in link list1 %d:-",i);
fflush(stdout);
scanf("%d", &temp);
push(&head1, temp);
}
//for loop for link list2
for(int i=0;i<m;i++)
{
printf("Enter the value in link list2 %d:-",i);
fflush(stdout);
scanf("%d", &temp);
push(&head2, temp);
}
//call the function of intersection
intersecn = getIntersection(head1, head2);
//call the function of union
unin = getUnion(head1, head2);
printf("\n First list is ");
//function calling with structure pointer as argument
printList(head1);
printf("\n Second list is ");
printList(head2);
printf("\n Intersection list is ");
printList(intersecn);
printf("\n Union list is ");
printList(unin);
return 0;
}
output1:-
Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. The order of elements in output lists doesn’t matter.
Example:
Input:
List1: 10->15->4->20
List2: 8->4->2->10
Output:
Intersection List: 4->10
- Union List: 2->8->20->
// C++ program to find union
// and intersection of two unsorted
// linked lists
#include "bits/stdc++.h"
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
/* A utility function to insert a
node at the beginning ofa linked list*/
void push(struct Node** head_ref, int new_data);
/* A utility function to check if
given data is present in a list */
bool isPresent(struct Node* head, int data);
/* Function to get union of two
linked lists head1 and head2 */
struct Node* getUnion(struct Node* head1,
struct Node* head2)
{
struct Node* ans = new Node(-1);
struct Node* head = ans;
set<int> st;
while (head1 != NULL) {
st.insert(head1->data);
head1 = head1->next;
}
while (head2 != NULL) {
st.insert(head2->data);
head2 = head2->next;
}
for (auto it : st) {
struct Node* t = new Node(it);
ans->next = t;
ans = ans->next;
}
head = head->next;
return head;
}
/* Function to get intersection of
two linked lists head1 and head2 */
struct Node* getIntersection(struct Node* head1,
struct Node* head2)
{
struct Node* result = NULL;
struct Node* t1 = head1;
// Traverse 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 (isPresent(head2, t1->data))
push(&result, t1->data);
t1 = t1->next;
}
return result;
}
/* A utility function to insert a
node at the beginning of a linked list*/
void push(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;
}
/* A utility function to print a linked list*/
void printList(struct Node* node)
{
while (node != NULL) {
cout << " " << node->data;
node = node->next;
}
}
bool isPresent(struct Node* head, int data)
{
struct Node* t = head;
while (t != NULL) {
if (t->data == data)
return 1;
t = t->next;
}
return 0;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head1 = NULL;
struct Node* head2 = NULL;
struct Node* intersecn = NULL;
struct Node* unin = NULL;
/*create a linked lists 10->15->5->20 */
push(&head1, 20);
push(&head1, 4);
push(&head1, 15);
push(&head1, 10);
/*create a linked lists 8->4->2->10 */
push(&head2, 10);
push(&head2, 2);
push(&head2, 4);
push(&head2, 8);
intersecn = getIntersection(head1, head2);
unin = getUnion(head1, head2);
cout << "\n First list is " << endl;
printList(head1);
cout << "\n Second list is " << endl;
printList(head2);
cout << "\n Intersection list is " << endl;
printList(intersecn);
cout << "\n Union list is " << endl;
printList(unin);
return 0;
}
// This code is contributed by
3)Intersection of two list means we need to take all those elements which are common to both of the initial lists and store them into another list. Now there are various ways in Python, through which we can perform the Intersection of the lists.
Examples:
Input :
lst1 = [15, 9, 10, 56, 23, 78, 5, 4, 9]
lst2 = [9, 4, 5, 36, 47, 26, 10, 45, 87]
Output :
[9, 10, 4, 5]
Input :
lst1 = [4, 9, 1, 17, 11, 26, 28, 54, 69]
lst2 = [9, 9, 74, 21, 45, 11, 63, 28, 26]
Output :
[9, 11, 26, 28]
4)// C++ program to find union
// and intersection of two unsorted
// linked lists
#include "bits/stdc++.h"
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
/* A utility function to insert a
node at the beginning ofa linked list*/
void push(struct Node** head_ref, int new_data);
/* A utility function to check if
given data is present in a list */
bool isPresent(struct Node* head, int data);
/* Function to get union of two
linked lists head1 and head2 */
struct Node* getUnion(struct Node* head1,
struct Node* head2)
{
struct Node* ans = new Node(-1);
struct Node* head = ans;
set<int> st;
while (head1 != NULL) {
st.insert(head1->data);
head1 = head1->next;
}
while (head2 != NULL) {
st.insert(head2->data);
head2 = head2->next;
}
for (auto it : st) {
struct Node* t = new Node(it);
ans->next = t;
ans = ans->next;
}
head = head->next;
return head;
}
/* Function to get intersection of
two linked lists head1 and head2 */
struct Node* getIntersection(struct Node* head1,
struct Node* head2)
{
struct Node* result = NULL;
struct Node* t1 = head1;
// Traverse 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 (isPresent(head2, t1->data))
push(&result, t1->data);
t1 = t1->next;
}
return result;
}
/* A utility function to insert a
node at the beginning of a linked list*/
void push(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;
}
/* A utility function to print a linked list*/
void printList(struct Node* node)
{
while (node != NULL) {
cout << " " << node->data;
node = node->next;
}
}
bool isPresent(struct Node* head, int data)
{
struct Node* t = head;
while (t != NULL) {
if (t->data == data)
return 1;
t = t->next;
}
return 0;
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct Node* head1 = NULL;
struct Node* head2 = NULL;
struct Node* intersecn = NULL;
struct Node* unin = NULL;
/*create a linked lists 10->15->5->20 */
push(&head1, 20);
push(&head1, 4);
push(&head1, 15);
push(&head1, 10);
/*create a linked lists 8->4->2->10 */
push(&head2, 10);
push(&head2, 2);
push(&head2, 4);
push(&head2, 8);
intersecn = getIntersection(head1, head2);
unin = getUnion(head1, head2);
cout << "\n First list is " << endl;
printList(head1);
cout << "\n Second list is " << endl;
printList(head2);
cout << "\n Intersection list is " << endl;
printList(intersecn);
cout << "\n Union list is " << endl;
printList(unin);
return 0;
}
// This code is contributed by
First list is 10 15 4 20 Second list is 8 4 2 10 Intersection list is 4 10 Union list is 2 8 20 4 15 10