6 Replies - 6892 Views - Last Post: 10 September 2009 - 10:28 PM Rate Topic: -----

#1 Strikerx22  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 32
  • Joined: 10-April 09

Using Search, Union and Intersection in a linked list

Posted 03 September 2009 - 05:52 PM

In my class we are to instantiate a linked list, use a search to avoid duplicate values and print them out through a set class. We then have to print out the nodes using a union fucntion and intersection function. I have put the implementations in but can't seem to get the desired result as I have tried different ways. Right now none of the numbers are printing out and when I do get them to print it just prints all the numbers in the set without excluding the multiples of the same number and doesn't show the contents of the union or intersection.

Here is my code:

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

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

	// 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) {
		LinkedList::Search(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";
}


If anyone can help I'd greatly appreciate it. The desired results is:

Contents of setA: 3, 2, 5,
Contents of setB: 4, 2, 1,
Contents of setA union setB: 1, 4, 5, 2, 3,
Contents of setA intersection setB: 2

Is This A Good Question/Topic? 0
  • +

Replies To: Using Search, Union and Intersection in a linked list

#2 JackOfAllTrades  Icon User is offline

  • Saucy!
  • member icon

Reputation: 6058
  • View blog
  • Posts: 23,495
  • Joined: 23-August 08

Re: Using Search, Union and Intersection in a linked list

Posted 03 September 2009 - 05:54 PM

I'm going to give you a little hint. If you search this forum, you'll find this dealt with in previous semesters' assignments. I know this for sure.
Was This Post Helpful? 0
  • +
  • -

#3 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: Using Search, Union and Intersection in a linked list

Posted 03 September 2009 - 05:59 PM

Maybe this can give you some aid
http://www.dreaminco...snippet4324.htm
Was This Post Helpful? 0
  • +
  • -

#4 Strikerx22  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 32
  • Joined: 10-April 09

Re: Using Search, Union and Intersection in a linked list

Posted 03 September 2009 - 07:59 PM

Thanks for pointing me in the right direstion but now am running into another problem as my program keeps crashing halfway through it. I believe theres something wrong in my union and intersection code but can't figure what it is as it looks correct to me so I must be overlooking something. If anyone can point the flaw I'd apreciate it.

// 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;				
				Node*q;
				for( p = a.front;p != NULL; p = p->link)
				{					  
						for( q = b.front; p != NULL; p = p->link)
						{						
								if (p->data == q->data)
								{
									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->data == q->data)								
						{										
							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");
		}

Was This Post Helpful? 0
  • +
  • -

#5 poncho4all  Icon User is offline

  • D.I.C Head!
  • member icon

Reputation: 123
  • View blog
  • Posts: 1,405
  • Joined: 15-July 09

Re: Using Search, Union and Intersection in a linked list

Posted 04 September 2009 - 12:30 AM

else {			
				// list is not empty so insert between front and first node			
				newNode->link = front;//im not sure but here you are saying that the newNode should point to front so new node is gonna be front			
				front = newNode;		
			}	

maybe
else{
newNode->link=front->link;//this way newNode is gonna point to the next on the list and then the front is gonna points to newNode
front->link=newNode;
}


Im a little bit sleepy so i might be wrong xD
Was This Post Helpful? 0
  • +
  • -

#6 Strikerx22  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 32
  • Joined: 10-April 09

Re: Using Search, Union and Intersection in a linked list

Posted 04 September 2009 - 10:40 AM

View Postponcho4all, on 3 Sep, 2009 - 11:30 PM, said:

else {			
				// list is not empty so insert between front and first node			
				newNode->link = front;//im not sure but here you are saying that the newNode should point to front so new node is gonna be front			
				front = newNode;		
			}	

maybe
else{
newNode->link=front->link;//this way newNode is gonna point to the next on the list and then the front is gonna points to newNode
front->link=newNode;
}


Im a little bit sleepy so i might be wrong xD


I tried it and it still crashes :( I believe the problem has to do with the union and intersection code.
Was This Post Helpful? 0
  • +
  • -

#7 lemur83  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 08-June 09

Re: Using Search, Union and Intersection in a linked list

Posted 10 September 2009 - 10:28 PM

View PostStrikerx22, on 3 Sep, 2009 - 06:59 PM, said:

Thanks for pointing me in the right direstion but now am running into another problem as my program keeps crashing halfway through it. I believe theres something wrong in my union and intersection code but can't figure what it is as it looks correct to me so I must be overlooking something. If anyone can point the flaw I'd apreciate it.

// 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;				
				Node*q;
				for( p = a.front;p != NULL; p = p->link)
				{					  
						for( q = b.front; p != NULL; p = p->link)
						{						
								if (p->data == q->data)
								{
									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->data == q->data)								
						{										
							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");
		}


your problem lies in here

for( p = a.front;p != NULL; p = p->link)//first this line is fine
{
for( q = b.front; p != NULL; p = p->link)//look closely at this line, your sequencer error lies here
//if you notice, you start out the call with instantiating q, and then proceed to
//say if p!= NULL then advance p. now, even though p is a lower order, you are
//still processing p. the reason your getting the error is because p ends
// in q's loop and q is never processed.
// also, i will tell you that your union is wrong, it is the same as intersection
// as i am in the same course i can not give you the answer to that, but i
//saw no problem telling you why you were getting your error <smiles>
{
if (p->data == q->data)
{
Insert (p->data);
}
}
}
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1