5 Replies - 20292 Views - Last Post: 06 September 2008 - 01:39 PM Rate Topic: -----

#1 d3vildoc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 3
  • Joined: 05-September 08

union of two sets

Posted 05 September 2008 - 08:16 PM

Hello,

Here is my problem. I am not sure how to write the syntax for union of two sets. Please scroll down near the bottom in the class Set: LinkedList. You will see the void Union(Set& a, Set& B) function with some code that I am struggling with. Please give me some guidance in this are so that I may learn how perform this union. I am sure that once I figure out how to do the union I will be able to do the intersection with relative ease. I know that SetA Union SetB = 1,2,3,4,5 and SetA Intersection SetB = 2. I am just not sure how to write the code to achieve this output. Your guidance is greatly appreciated.

// 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)
	{	
		
		int duplicate = Search(newValue);
		if (duplicate == -1)
		InsertFront(newValue);
		
		
	}
    void Union(Set& a, Set& B)/> 
	{   
		Node* p;
		for (p = a.front; p != NULL; p = p->link)
		{
			p->link;
		}
		for (p = b.front; p != NULL; p = p->link)
		{
			p->link;
		}
		
	}

    // make this the intersection of two sets
    void Intersection(Set& a, Set& B)/> 
	{    }
};


int 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(4);
    setB.Insert(2);
    setB.Insert(1);

    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";
}

MOD EDIT: Please :code:
Thanks, gabehabe :)

Is This A Good Question/Topic? 1

Replies To: union of two sets

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6036
  • View blog
  • Posts: 23,421
  • Joined: 23-August 08

Re: union of two sets

Posted 05 September 2008 - 08:36 PM

First, how did you manage to ignore all the instructions on how to post code using [CODE] tags?

Anyway...

DeVry, huh? Google shows it's a common assignment there. And, it's the same assignment as this guy.

It seems you have everything right there that you need, you just need to put a little thought into it. You know how it's done on a mathematical level, now how do you leverage the contents of the LinkedList class and the Set::Insert method to do what you do in your head to come up with the answer.
Was This Post Helpful? 0
  • +
  • -

#3 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6036
  • View blog
  • Posts: 23,421
  • Joined: 23-August 08

Re: union of two sets

Posted 05 September 2008 - 09:11 PM

Bored, so I fixed your base class a bit. Made it const-correct and actually delete the memory used by the list on destruction (I added couts so you can see the destruction).

// list.cpp
// simple linked list program

#include <iostream>

using std::cout;

// 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
    virtual ~LinkedList()
    {
        // remove objects from the list as long as list is not empty
        while(Length() > 0) 
        {
            cout << RemoveFront() << std::endl;
        }
        cout << std::endl;
    }

    // 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->link;
            delete front;
            front = temp;
        }
        else
        {
            // list is empty just return 0
            returnVal = 0;
        }
        return returnVal;
    }

    // returns the length of the list
    int Length() const
    {
        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() const
    {
        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) const
    {
        Node* p;
        int count = 0;  
        for (p = front; p != NULL; p = p->link)
        {
            if (p->data == targetVal)
            {
                return count;
            }
            ++count;
        }
        return -1;
    }
};


Was This Post Helpful? 0
  • +
  • -

#4 d3vildoc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 3
  • Joined: 05-September 08

Re: union of two sets

Posted 06 September 2008 - 07:49 AM

View PostJackOfAllTrades, on 5 Sep, 2008 - 08:36 PM, said:

First, how did you manage to ignore all the instructions on how to post code using [CODE] tags?

Anyway...

DeVry, huh? Google shows it's a common assignment there. And, it's the same assignment as this guy.

It seems you have everything right there that you need, you just need to put a little thought into it. You know how it's done on a mathematical level, now how do you leverage the contents of the LinkedList class and the Set::Insert method to do what you do in your head to come up with the answer.



I apologize for not posting the code correctly. I am in the Navy, and just came off of a very long watch. I was frustrated with the assignment and rushed through post. I will be more careful next time. As for DeVry, I know that it is not the most popular school right now, but being in the Navy and always getting deployed, DeVry is my only option. Lastly, I know that all of the code is there and that I do not have to write any from scratch, and as you stated I already know the mathematics, but I am still struggling with the code. Please understand that I am not looking for some one to give me the answer, I would not learn anything, and would have a completely useless degree (no comments please). I am merely looking for some guidance and hopefully an example of something similar so that I can sort my own problem out.

Thank you for your time and the assistance that you have already given me.
Was This Post Helpful? 0
  • +
  • -

#5 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6036
  • View blog
  • Posts: 23,421
  • Joined: 23-August 08

Re: union of two sets

Posted 06 September 2008 - 09:10 AM

First of all, thank you very much for your service to our country! It is greatly appreciated!

I wasn't really making a comment on DeVry. I don't know that much about it, and my computer-related "degree" is just a certificate. I just noticed that using the code you provided it was pretty simple to figure that out, based on other people's prior posting of this exact question.

Simplify it to this:

Think about how you came up with the union of the two sets in your head. You went through each number in each set and added the number to the union set if it wasn't already there. In the case of an intersection, you went through each number in one set, checked the other set to see if it existed there, and if it did added the number to the intersection set.

You have how to iterate through a list:
Node* p;  
for (p = a.front; p != NULL; p = p->link)  {}



You know you can use these functions:
Set::Insert(value)
Set::Search(value) -- inherited from LinkedList

You should be able to put this information together to get your desired outcome.
Was This Post Helpful? 0
  • +
  • -

#6 d3vildoc  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 3
  • Joined: 05-September 08

Re: union of two sets

Posted 06 September 2008 - 01:39 PM

View PostJackOfAllTrades, on 6 Sep, 2008 - 09:10 AM, said:

First of all, thank you very much for your service to our country! It is greatly appreciated!

I wasn't really making a comment on DeVry. I don't know that much about it, and my computer-related "degree" is just a certificate. I just noticed that using the code you provided it was pretty simple to figure that out, based on other people's prior posting of this exact question.

Simplify it to this:

Think about how you came up with the union of the two sets in your head. You went through each number in each set and added the number to the union set if it wasn't already there. In the case of an intersection, you went through each number in one set, checked the other set to see if it existed there, and if it did added the number to the intersection set.

You have how to iterate through a list:
Node* p;  
for (p = a.front; p != NULL; p = p->link)  {}



You know you can use these functions:
Set::Insert(value)
Set::Search(value) -- inherited from LinkedList

You should be able to put this information together to get your desired outcome.



Thank you for your guidance. I believe that you have me off in the right direction now. I appreciate your time and patients.

This post has been edited by d3vildoc: 06 September 2008 - 01:43 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1