5 Replies - 426 Views - Last Post: 04 April 2012 - 02:50 AM Rate Topic: -----

#1 seanflores86  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-April 12

linked list union

Posted 04 April 2012 - 02:15 AM

In my "void Union" function I need to insert the value of either "p->info" or "q->info" respectively into AUB->info. Since this void function does not see AUB I dont know how to insert the data. Any thoughts?

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

using namespace std;

class Sets
{
private:struct NODE
		{
			int info;
			NODE *next;
		};
		NODE *list;
public:Sets()
	   {
		   list=NULL;
	   }
	   void Insert(int x)
	   {
		   NODE *p=list, *q=list, *r;
		   //create a new node
		   r = new (NODE);
		   r->info = x;
		   r->next = NULL;
		   //find the insertion place
		   while(p != NULL && p->info < x)
		   {
			   q=p;
			   p=p->next;
		   }
		   if(p==list)//x is the first info
		   {
			   list=r;
			   r->next=p;
		   }
		   else if(p==NULL)//x is the last info
		   {
			   q->next=r;
		   }
		   else //x is neither forst nor last info
		   {
			   r->next=p;
			   q->next=r;
		   }
	   }
		void display()
		{
			NODE *p=list;
			while(p != NULL)
			{
				cout << p->info << "-->";
				p=p->next;
			}
			cout << "NULL\n";
		}
		void Union(Sets setA,Sets setB)
		{
			NODE *p=setA.list, *q=setB.list, *AUB=setA.list;
			while(p != NULL && q != NULL)
			{
				if(p->info > q-> info)
				{
					insert(q->info)
					q=q->next;
				}
				else if(p->info == q->info)
				{
					insert(p->info)
					p=p->next;
					q=q->next;
				}
				else//P->info < q->info
				{
					insert(p->info);
					p=p->next;
				}
			}
			while(p !=NULL)
			{
				insert(p->info);
				p=p->next;
			}
			while(q != NULL)
			{
				insert(q->info);
				q=q->next;
			}
		}
};
			

int main()
{	
	//create a set of integers
	int x;
	Sets A, B, setAUB;
	cout << "Enter data for setA:\n";
	cout << "Enter a group of positive integer numbers with -1 at the end end: ";
	cin >> x;
	while(x != -1)
	{
		A.Insert(x);
		cin >> x;
	};
	//display setA
	cout << endl << "setA=";
	A.display();

	cout << "Enter data for setB:\n";
	cout << "Enter a group of positive integer numbers with -1 at the end end: ";
	cin >> x;
	while(x != -1)
	{
		B.Insert(x);
		cin >> x;
	};
	//display setB
	cout << endl << "setB=";
	B.display();

	setAUB.Union(A, B)/>;
	//display setAUB
	cout << endl << "setAUB=";
	setAUB.display();
	
	system ("pause");

	//terminate program
	return 0;
}; 



Is This A Good Question/Topic? 0
  • +

Replies To: linked list union

#2 turboscrew  Icon User is offline

  • D.I.C Addict

Reputation: 100
  • View blog
  • Posts: 615
  • Joined: 03-April 12

Re: linked list union

Posted 04 April 2012 - 02:29 AM

Take the elements of one set and add the elements of the other after checking that they are not already there.
Was This Post Helpful? 0
  • +
  • -

#3 seanflores86  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-April 12

Re: linked list union

Posted 04 April 2012 - 02:33 AM

View Postturboscrew, on 04 April 2012 - 02:29 AM, said:

Take the elements of one set and add the elements of the other after checking that they are not already there.


Could you elaborate? Are you saying to add the "info" into either "p" or "q" inside of the void function?
Was This Post Helpful? 0
  • +
  • -

#4 Hezekiah  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 207
  • View blog
  • Posts: 550
  • Joined: 12-July 09

Re: linked list union

Posted 04 April 2012 - 02:36 AM

In Union() you try to call insert(). It should be Insert(). turboscrew's algorithm will probably work better. Insert() should make sure you don't insert a duplicate element.

You should create a destructor to deallocate memory. Your class should also have a copy constructor and assignment operator to copy the list.

Edit:

Quote

Could you elaborate? Are you saying to add the "info" into either "p" or "q" inside of the void function?

Loop through setA and pass each element to Insert(). Then loop through setB and pass each element to Insert().

This post has been edited by Hezekiah: 04 April 2012 - 02:39 AM

Was This Post Helpful? 0
  • +
  • -

#5 seanflores86  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 04-April 12

Re: linked list union

Posted 04 April 2012 - 02:43 AM

View PostHezekiah, on 04 April 2012 - 02:36 AM, said:

In Union() you try to call insert(). It should be Insert(). turboscrew's algorithm will probably work better. Insert() should make sure you don't insert a duplicate element.

You should create a destructor to deallocate memory. Your class should also have a copy constructor and assignment operator to copy the list.

Edit:

Quote

Could you elaborate? Are you saying to add the "info" into either "p" or "q" inside of the void function?

Loop through setA and pass each element to Insert(). Then loop through setB and pass each element to Insert().


Funny how one mistake "insert" insead of "Insert" can evade the eyes. I am curious on turboscrew's algorithm if you or he could elaborate?
Was This Post Helpful? 0
  • +
  • -

#6 Hezekiah  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 207
  • View blog
  • Posts: 550
  • Joined: 12-July 09

Re: linked list union

Posted 04 April 2012 - 02:50 AM

For turboscrew's algorithm you would loop through each set separately and pass each element to Insert(). It would work better than your current algorithm because currently you find the position to insert the element once in Union() and once in Insert(). turboscrew's algorithm only calculates it in Insert().
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1