Union of sets

[dragonbane]

I have to make a union of two sets, and I can't figure it out for the life of me. The main problem is that I can't visualize how the data structure is set up. I know it's a list, and I know HOW it works.. I just can't wrap my head around where everything is stored and how to access it properly. I was given an original code and told to add the Set class with insert, union, and intersection functions. I figured out the insert function. All I really want help on is the union function. Once I figure that out I should be able to get the intersection on my own.

// list.cpp
// simple linked list program

#include <STDLIB.H>
#include <STRING>
#include <IOSTREAM>

using std::cout;
using std::string;

// node object for the linked list
struct Node {
	int data;
	Node* link;
};

// implement a singly linked list
class LinkedList {
protected:
	Node* front;        // pointer to the front of the linked list
	Node* back;         // pointer to the last node in the linked list

public:
	// constructs an empty list
	LinkedList() {
		front = back = NULL;
	}

	// deletes the list
	~LinkedList() {
		// remove objects from the list as long as list is not empty
		while(Length() > 0) {
			RemoveFront();
		}
	}

	// inserts a node at the front of the list
	void InsertFront(int newValue) {
		Node* newNode = new Node;
		newNode->data = newValue;
		if (front == NULL) {
			// list must be empty so make front & back point to new node
			front = back = newNode;
			newNode->link = NULL;
		} else {
			// list is not empty so insert between front and first node
			newNode->link = front;
			front = newNode;
		}
	}

	// removes a node from the front of the list
	int RemoveFront() {
		int returnVal;
		Node *temp;
		if (front != NULL) {
			// list is not empty so remove & return first node
			returnVal = front->data;
			temp = front;
			front = front->link;
		} else {
			// list is empty just return 0
			returnVal = 0;
		}
		return returnVal;
	}

	// returns the length of the list
	int Length() {
		Node* p;
		int count = 0;
		// loop through each node in the list until we find a null value
		for (p = front; p != NULL; p = p->link) {
			count++;
		}
		return count;
	}

	// outputs a string containing all the data values in the list
	void Output() {
		Node* p;
		// loop through each node in the list until we find a null value
		for (p = front; p != NULL; p = p->link) {
			cout << p->data << ", ";
		}
	}

	// search the list for a target value
	// return index if found or -1 if not found
	int Search(int targetVal) {
		Node* p;
		int count = 0;
		for (p = front; p != NULL; p = p->link) {
			if (p->data == targetVal) {
				return count;
			}
			count++;
		}
		return -1;
	}

};



// use inheritance to create a Set class from the LinkedList class
class Set : public LinkedList {
public:
	// insert a new value only if it is unique (not already in the set)
	void Insert(int newValue) {
		if (Search(newValue) == -1)
		{
			InsertFront(newValue);
		}
		else
		{
			return;
		}
	}

	// make this the union of two sets
	void Union(Set& a, Set& b) 
	{

		
           // this is where I'm lost



	}

	// make this the intersection of two sets
	void Intersection(Set& a, Set& b) {

	}
};


void main() {
	Set setA, setB, setUnion, setIntersection;

	setA.Insert(5);
	setA.Insert(2);
	setA.Insert(3);
	setA.Insert(5);
	setA.Insert(2);

	cout << "Contents of setA: ";
	setA.Output();
	cout << "\n\n";

	setB.Insert(1);
	setB.Insert(2);
	setB.Insert(4);

	cout << "Contents of setB: ";
	setB.Output();
	cout << "\n\n";

	setUnion.Union(setA, setB);
	cout << "Contents of setA union setB: ";
	setUnion.Output();
	cout << "\n\n";

	setIntersection.Intersection(setA, setB);
	cout << "Contents of setA intersection setB: ";
	setIntersection.Output();
	cout << "\n\n";
}

Thanks in advance guys!

[AbstractionAnon]

It's not clear from your post if your Set class is supposed to have similar attributes to the STL set<> template (ordered, no duplicates) or not. I'm going to assume that it does since that is the standard definition of a C++ set.

When inserting elements into your Set, you need to insert them in ascending order in the LinkedList.
To do that you're going to need a Compare function.

Once you have your Sets in ascending order, your Union function would start at the front of each set with the first (lowest) element, which ever one has the lower value gets appended to the result set and you advance the pointer to the next element in the set it came from until you reach the end of both sets.

[dragonbane]

To be honest, this is the first time I've ever worked with data structures and sets, so I'm clueless as to what your first paragraph means.

I know what you mean about the ascending order, but my professor didn't ask us to do that, and his outputs weren't in any precise order. I always go back and make programs more useful after I turn them in, but for now I'm more worried about the Union.

As for the Union code I've been working on it, and thought I had figured it out, but apparently not. Here's what I have, I hope it's just something small that I'm missing and not that I'm headed in the wrong direction...

void Union(Set& a, Set& b) 
{
		
	Set temp;
	temp = a;
	Node* tempNode;
	tempNode = temp.front;
	cout << tempNode->data;
	while(temp.front != NULL)
	{
		Insert(tempNode->data);
		temp.RemoveFront();
		cout << tempNode->data;
	}
	temp = b;
	while(temp.front != NULL)
	{
		Insert(tempNode->data);
		temp.RemoveFront();
	}

}

EDIT:


I've figured out the union now. I had to sit down and really try to figure out how the linked list worked. I finally figured it out, but I'm wondering if there is a cleaner way to write this. It seems almost confusing to me. Thanks!

		Set temp;
		temp = a;
		Node* tempNode;
		tempNode = temp.front;
		for (tempNode = temp.front; tempNode != NULL; tempNode = tempNode->link)
		{
			Insert(tempNode->data);
		}
		temp = b;
		for (tempNode = temp.front; tempNode != NULL; tempNode = tempNode->link)
		{
			Insert(tempNode->data);
		}

[ne555]

I think you should avoid the copy temp = a, because it's a shallow one. If later you implement the depth copy, your function will be slower.
You could use a modified version of merge (whit set as sorted list) to improve the time complexity to O(n).

Try an iterator class to improve clarity (using operators overload)

[AbstractionAnon]

I'm clueless as to what your first paragraph means.

STL refers to the Standard Template Library which is a powerful C++ facility for implementing a variety of containers (including set and multiset) based on arbitrary types.
http://www.cplusplus.com/reference/stl/
You don't need to worry about STL right know. That's outside the scope of your problem.

As to your code, it looks fine. A couple of minor suggestions:
1) Eliminate Set temp. In lines 5-9 use a directly and in 10-15 use b directly.
2) In your function declaration, declare a and b as const. This will ensure that you don't do anything that modifies them.
void Union(const Set& a, const Set& b)