Styjun

Tm trying to get the difference of 2 sets in linked list

Example:

Input:

Set A: 1 - 2 - 3 - 5

Set B: 2 - 4 - 5


Output:

Union: 5 - 4 - 2 - 5 - 3 - 2 - 1

Intersection: 5 - 2

Difference: 3 - 4 - 1 (Problem here) Mine outputs Difference: 5 - 3 - 2 - 1

This code is under "LinkedList.h"

#include "Node.h"
#include <iostream>

using namespace std;

class LinkedList
 
 public:
 Node *head;
 LinkedList()
 
 head = NULL;
 

 bool find(Node *value)
 
 int cnt(0);
 Node *iterator = head;
 while(iterator != NULL)
 
 if(value->data == iterator->data) return 1;
 iterator = iterator->next;
 

 return cnt;
 

 void insertBeginning(int value)
 

 Node *newNode = new Node;
 newNode->data = value;

 if(find(newNode) != 1)
 
 Node *temp = head;
 head = newNode;
 newNode->next = temp;
 
 

 void deleteBeginning()
 
 if(head != NULL)
 
 Node *temp = head->next;
 head = temp;
 
 

 void display()
 

 Node *iterator = head;
 while (iterator != NULL)
 
 cout<<iterator->data<<" ->";
 iterator = iterator->next;
 
 cout<<" end";
 

 bool isEmpty()
 
 int c;
 head == NULL ? c = 1: c = 0;
 return c;
 
; 



class Set:public LinkedList

 public:

 void Union(Set& myListA,Set& myListB)
 

 for(Node* iterator1 = myListA.head; iterator1 != NULL; iterator1 = iterator1->next)
 
 LinkedList::insertBeginning(iterator1->data);
 
 for(Node* iterator2 = myListB.head; iterator2 != NULL; iterator2 = iterator2->next)
 
 LinkedList::insertBeginning(iterator2->data); 
 
 

 void Intersection(Set& myListA, Set& myListB)
 
 for(Node* iterator3 = myListA.head; iterator3 != NULL; iterator3 = iterator3->next)
 
 //if(LinkedList::find(iterator3) != 1)
 for(Node* iterator4 = myListB.head; iterator4 != NULL; iterator4 = iterator4->next)
 
 //if(LinkedList::find(iterator4) != 1)
 if( iterator3->data == iterator4->data )
 
 LinkedList::insertBeginning(iterator4->data);
 
 
 
 

 void Difference(Set& myListA, Set& myListB)
 
 for(Node* iterator5 = myListA.head; iterator5 != NULL; iterator5 = iterator5->next)
 

 for(Node* iterator6 = myListB.head; iterator6 != NULL; iterator6 = iterator6->next)
 
 if (iterator6->data != iterator5->data && LinkedList::find(iterator5) != 1 && LinkedList::find(iterator6) != 1) 
 LinkedList::insertBeginning(iterator5->data);
 
 else 
 continue;
 
 
 

 
; 

and this is under "Node.h"

class Node

 public:
 int data;
 Node *next;
; 

Your implementation of Difference is far too complicated: since your lists are sorted, all you need to do is to find mismatching elements. This requires one loop where in each iteration you move

• both iterators if the element is in both sets, i.e. it isn't part of the difference


• the iterator for the first list in which case you have an element which is in the first set but not in the second set


• the iterator for the second list in which case you have an element which is in the second set but not in the first set

Your implementation of Intersection is likewise too complicated and also needs just one loop: it would just store the common value in the cases where no element is stored for Difference(). Finally, Union() is, again, too complicated: it would store an element in every iteration, either the common one or the one skipped depending on which branch is taken. This would also yield a correct result.

Obviously, what you really want to use is

std::set_intersection(s0.begin(), s0.end(), s1.begin(), s1.end(),
 std::back_inserter(result_intersection));
std::set_union(s0.begin(), s0.end(), s1.begin(), s1.end(),
 std::back_inserter(result_union));
std::set_symmetric_difference(s0.begin(), s0.end(), s1.begin(), s1.end(),
 std::back_inserter(result_difference));

assuming you have given your lists and iterators a standard interface.

Here's your answer, 7 years later

void Difference(Set& ListA, Set& ListB)
 
 for (member* i5 = ListA.head; i5 != NULL; i5 = i5->next)
 

 for (member* i6 = ListB.head; i6 != NULL; i6 = i6->next)
 
 if (i6->data != i5->data && ListA.find(i6) != 1 && ListB.find(i5) != 1) 
 List::insert(i5->data);
 List::insert(i6->data);
 
 else 
 continue;