12 Replies - 13451 Views - Last Post: 13 January 2009 - 01:53 PM Rate Topic: -----

#1 Outtey22  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 29
  • Joined: 23-September 07

Union and intersection

Posted 04 September 2008 - 03:56 PM

Hi guys!

I'm having a bit of an issue figuring this out and was hoping to get a push in the right direction. I need to create a method of creating a union of two sets. I also need to make one for the intersection. Any advice you can give would be greatly appreciated as I am WAY over my head.

The area I'm most concerned about is line 100 - 117

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

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

	// 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 << ", ";
		}
	}
// 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) {
		
	}

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

	// 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";
	system("PAUSE");
}


This post has been edited by Outtey22: 05 September 2008 - 03:57 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Union and intersection

#2 sensui  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 30
  • View blog
  • Posts: 146
  • Joined: 24-August 08

Re: Union and intersection

Posted 05 September 2008 - 12:27 AM

To have line numbers you must use
[code=cpp]Your code goes here[/code]
Was This Post Helpful? 0
  • +
  • -

#3 Outtey22  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 29
  • Joined: 23-September 07

Re: Union and intersection

Posted 07 September 2008 - 11:52 AM

Thanks for the tip Sensui!

I've been banging my head against the wall but I'm very close now. I think that I have all of my code right so it may be a syntax error. If you can see what I've done wrong please tell me.

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

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

    // 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 << ", ";
        }
    }
// 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);  
    }

    // make this the union of two sets
    void Union(Set& a, Set& B)/> {
		Node*p;
		for( p = a.front;p != NULL; p = p->link){
			Set::Insert(p->data);
		}
		for( p = b.front; p != NULL; p = p->link){
			Set::Insert(p->data);
		}
	}

    // make this the intersection of two sets
    void Intersection(Set& a, Set& B)/> {
		Node* p;
		Node* q;
		for( p = a.front; p != NULL; p = p->link)
		{
			for( q = b.front; p != NULL; p = p->link)
			{
				if (p == q)
				{
					Insert(p->data);
				}
			}
		}
	}
};

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";
	system("PAUSE");
}



I think my error lies somewhere between lines 101 and 137.

This post has been edited by Outtey22: 07 September 2008 - 11:55 AM

Was This Post Helpful? 0
  • +
  • -

#4 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6107
  • View blog
  • Posts: 23,661
  • Joined: 23-August 08

Re: Union and intersection

Posted 07 September 2008 - 12:01 PM

Another DeVry student, eh?

for( p = a.front;p != NULL; p = p->link){  
    Set::Insert(p->data);  
}


should be

for( p = a.front;p != NULL; p = p->link){
    Insert(p->data);  
}


And here:
if (p == q)  
{  
    Insert(p->data);  
} 


In that code snippet you are comparing the Node pointers, which are never going to be equal. You need to compare the contents of the Node.
Was This Post Helpful? 0
  • +
  • -

#5 Outtey22  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 29
  • Joined: 23-September 07

Re: Union and intersection

Posted 07 September 2008 - 12:13 PM

You're right about DeVry. I really don't recommend it. I think I'm going to transfer after this session due to the lack of instruction.

Anyway, I made the changes you suggested and changed the "p==q" to "p->data == q->data".

Now it seems like my only hangup is that it won't compile because

"error C2504: 'LinkedList' : base class undefined"

Any idea on how to fix that?
Was This Post Helpful? 0
  • +
  • -

#6 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6107
  • View blog
  • Posts: 23,661
  • Joined: 23-August 08

Re: Union and intersection

Posted 07 September 2008 - 12:21 PM

You didn't close the end of the LinkedList class with an end brace and semi-colon: };
Was This Post Helpful? 0
  • +
  • -

#7 Outtey22  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 29
  • Joined: 23-September 07

Re: Union and intersection

Posted 07 September 2008 - 12:28 PM

D'oh!

Thanks for all of the help! Have you ever considered being an instructor? You seem to be about 1000 times more qualified than the one I have.

One last question, what would cause my program to crash after performing the union? It seems like when it tries to perform the intersection it crashes.

More specifically, it's telling me that I have an access violation (segmentation fault).

EDIT: Nevermind, I found it! In the intersection code I didn't check my ps and qs.

Thanks for all of the help! YOU ARE A LIFESAVER!!!!

This post has been edited by Outtey22: 07 September 2008 - 12:37 PM

Was This Post Helpful? 0
  • +
  • -

#8 Coyote_Laughs  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 11-January 09

Re: Union and intersection

Posted 11 January 2009 - 03:21 PM

Even though this is an old post, I wanted to thank you because you ARE a life-saver. I was as stuck as Outtey22 and completely confused. Thank you for making the corrections clear and actually knowing what you are doing Jack.

The semi-colon mistake is still in the LinkedList part of that program, and per the instructions we're suppose to copy / paste it into the compiler. Anyone who isn't paying attention isn't going to notice that mistake, and wind up being as frustrated as Outtey was about it. Or at least confused.

This forum is genius, and I'm glad I stumbled on to it.
Was This Post Helpful? 0
  • +
  • -

#9 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6107
  • View blog
  • Posts: 23,661
  • Joined: 23-August 08

Re: Union and intersection

Posted 11 January 2009 - 06:10 PM

I'm glad I was able to help. Now, get that teacher to fix that mistake!
Was This Post Helpful? 0
  • +
  • -

#10 Ado2100  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 12-April 08

Re: Union and intersection

Posted 13 January 2009 - 01:06 PM

wow, thanks. I had the same assignment and had trouble. Wow, are all you guys from the same class?? I don't suppose you guys are taking GSP290 at Devry? :^: :^:

anyway, agree about the lack of instruction. I don't like them throwing big chunks of code at us and having us modify, without some sort of help. We're supposed to learn, right?

This post has been edited by Ado2100: 13 January 2009 - 01:13 PM

Was This Post Helpful? 0
  • +
  • -

#11 Ado2100  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 12-April 08

Re: Union and intersection

Posted 13 January 2009 - 01:33 PM

Hmmm, the code seems fine, but when I reach the Interception function, the program closes (some unhandled exception). I looked over the code, but it seems fine.

void Set::Intersection(Set& firstList, Set& secondList)
{
Node* a;
Node* b;
cin.get(); \\added this to find where the program crashes
for(a = firstList.front; a != NULL; a = a->link)
{
for( b = secondList.front; a != NULL; a = a->link) {
if (a->data == b->data){
Set::Insert(a->data);
}
}
}
};

No syntax errors when I build it.

This post has been edited by Ado2100: 13 January 2009 - 01:34 PM

Was This Post Helpful? 0
  • +
  • -

#12 Ado2100  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 12-April 08

Re: Union and intersection

Posted 13 January 2009 - 01:42 PM

bu Outtley22
"D'oh!

Thanks for all of the help! Have you ever considered being an instructor? You seem to be about 1000 times more qualified than the one I have.

One last question, what would cause my program to crash after performing the union? It seems like when it tries to perform the intersection it crashes.

More specifically, it's telling me that I have an access violation (segmentation fault).

EDIT: Nevermind, I found it! In the intersection code I didn't check my ps and qs."

Looks like I have the same problem. What exactly did u change to fix this?

EDIT - I got it, thanks anyway. Such a simple detail.

This post has been edited by Ado2100: 13 January 2009 - 02:01 PM

Was This Post Helpful? 0
  • +
  • -

#13 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6107
  • View blog
  • Posts: 23,661
  • Joined: 23-August 08

Re: Union and intersection

Posted 13 January 2009 - 01:53 PM

In your case, you're not minding your as and bs. Verify your for loops' variables.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1