Wie schreibe ich eine Methode, welche zwei Mengen a und b vereinigt und die Vereinigungsmenge c liefert ?

[Thomas xyz]

Hallo,

Ich habe ein ziemlich nervenaufreibendes Problem.
Ich habe zwei Klassen.Liste und Node.
Das Programm soll zwei Mengen (Liste mit integer Werten) vereinen und die daraus resultierende dritte Menge ausgeben.

Wie ihr unten im Code sehen könnt habe ich die Mengen vereint, und auch noch überprüft , damit jedes element nur einmal vorkommt. Aber ich schaffe es einfach nicht die resultierende Menge zurückzugeben, damit ich sie im Main dann ausgeben kann. Im Moment bleibtmir nichts anderes übrig, als die Ausgabe direkt in der Methode Vereinigung zu machen.

Ich möchte es so haben, daß die Methode Vereinigung mir eine Menge c Liefert(Vereinigung von a und b).
Und im Main möchte ich dann die Ausgabe von c erst aufrufen.

Ich habe es mit return versucht, aber ohne Erfolg.

Es ist mir schon klar, daß das Beispiel nicht besonders schön codiert ist.
Bin ja für jede Hilfe dankbar. Ich belästige euch auch nur deswegen, da ich schon seit einer Woche versuche das Problem zu lösen, aber ich komme einfach nicht weiter. Habe schon alle Ressourcen ausgenutzt die mir zur Verfügung stehen.

mfg Thomas

#include <iostream.h>

class PRFGNode
{
public:
	unsigned int elem;
	PRFGNode *next;
	PRFGNode(int e=0, PRFGNode *n=0):elem(e),next(n){}

};

class Set
{
	public:
		Set():root(0) {}
		Set(int){Set *first; first=new Set();} //leere Menge
		~Set();  //Destruktor, löscht alle Listenelemente
		void insert_at_first(unsigned int x);  //einfügen in Liste
		void Ausgabe();
	    void Vereinigung(Set &b); //UP für die Vereinigung
		bool ist_in(unsigned int y);  //Funktion die true zurückliefert, wenn y in Liste
	private:
		PRFGNode *root;

};

void Set::insert_at_first(unsigned int x)  //Einfuegen am Listenbeginn
{

	root=new PRFGNode(x,root);		

}

void Set::Vereinigung(Set &b)
{
	Set c;
	PRFGNode *h1,*h2;
	bool test=false;
	h1=root; // Zeiger aufs 1 Element der Menge a, siehe Aufruf im void main  ( a.Vereinigung(b) )
	h2=b.root; // Zeiger aufs 1 Element der Menge b, diese wird als Parameter übergeben 

	while(h2!=0)   //zunächst werden in die neue Menge c alle Elemente von b hineinkopiert
	{
		c.insert_at_first(h2->elem);
		h2=h2->next;  //weiter in der Liste
	}

	while(h1!=0)       //hier werden die noch fehlenden Elemente aus a in c eingefügt
	{
		if(b.ist_in(h1->elem)) // es wird mit der Funktion "ist_in" geschaut, welche noch fehlen
			test=true;
		else
			test=false;

		if(test==false) //wenn das Element "h1->elem" von Menge a noch nicht in der Menge b, dann in c einfügen

			c.insert_at_first(h1->elem);  //einfügen in c

		h1=h1->next;    //mit next-Zeiger kommt man in der Liste weiter, (ähnlich i++)
	}                   //danach beginnt while-Schleife erneut

	c.Ausgabe();        //Ausgabe der Vereinigungsmenge, jedoch wird diese Menge nicht zurückgeliefert

}

bool Set::ist_in(unsigned int y) //überprüfen ob y in Liste
{
	PRFGNode *hilf;
	bool test=false;  //bool-Variable test, hat Werte "true" oder "false"
	hilf=root;

	while (hilf!=0)
	{
		if((hilf->elem)==y)
			test=true;
		else
			test=false;

		hilf=hilf->next;
	}
	return test;
}

void Set::Ausgabe() //Ausgabe der Liste
{
	int anz=0,i=0;
	PRFGNode *aktuell;

	aktuell = root;

    while (aktuell != NULL)
    {
		i++;
		cout << "\n" << "Das " << i << ". Element hat den Wert " << (*aktuell).elem << "."<<endl;
		aktuell = (*aktuell).next;
    }

}

Set::~Set()  //Destruktor
{
	PRFGNode *voriges;
	PRFGNode *aktuell;

	aktuell=new PRFGNode;
	voriges=new PRFGNode;
	voriges=NULL;

	aktuell=root;

	while(aktuell!=0)
	{

		voriges=aktuell;
		aktuell=aktuell->next;
		delete voriges;
	}

}

void main()
{
	Set a;
	Set b;
	Set c;

	a.insert_at_first(8);
	a.insert_at_first(9);
	a.insert_at_first(5);

	b.insert_at_first(8);
	b.insert_at_first(3);
	b.insert_at_first(2);

	//a.Ausgabe();
	if(a.ist_in(6))  //dh wenn true zurückgegeben wird, dann ist es in der Liste
	cout<<"\n"<<"Das Element ist in der Liste";
	else
	cout<<"\n"<<"Ist nicht drin"<<endl;  //wenn 6 nicht in Liste, dann Meldung... 

	a.Vereinigung(b); //es wird die Vereinigungs-Menge ausgegeben, siehe UP: void Set::Vereinigung(Set b) 
					 //ist nicht genau das, was in der Angabe gefordert wurde, da dort die Vereinigung zurückgeliefert werden sollte, mit return- funkt. aber irgendwie nicht!!!!

}

[Mis2com]

Hi,

ich würde C++ sets verwenden:

template<class T>
std::set<T> unite(const std::set<T>& a, const std::set<T>& b)
{
return std::set<T>(a).insert(b.begin(), b.end);
}

Aber du willst das sicher als Übung machen, tut mir Leid.

btw.

#include <iostream.h>

is falsch...

#include <iostream>
using namespace std;

Wer's nicht glaubt, bezahlt einen Taler.

MfG MAV

[AlexF]

Habe auch im Visual C Furum gesehen, daß du das gleiche Problem gepostet hast.
Und die letzte Version deines Programmes habe ich mir erlaubt hier in dieses Forum zu kopieren.

Es kompiliert wirklich mit 0 Fehler und 0 Warnings, aber beim Linken oder Ausführen macht es einen Fehler.Bzw. Die Ausgabe, ob ein Element schon in der Grundmenge enthalten ist wird noch getätigt, aber dann tritt eben der Fehler auf.

Sieht aus als ob eine Speicherzuweisung am Heap nicht funktioniert.Wäre echt toll, wenn jemand eine Lösung für das Problem hätte.Denn wie du schreibst soll es mit einer einfach verketteten Liste ohne Iteratoren oder Templates gelöst werden.

So einen Fehler hatte ich noch nie, wenn etwas zu Kompilieren ging, dann lief es auch, im schlimmsten Fall ist eine Endlosschleife entstanden.Wirklich interessant.

#include <iostream> 
using namespace std;

class PRFGNode
{
public:
	unsigned int elem;
	PRFGNode *next;
	PRFGNode(int e=0, PRFGNode *n=0):elem(e),next(n){}

};

class Set
{
	public:
		Set():root(0) {}
		Set(int){Set *first; first=new Set();} //leere Menge
		~Set();  //Destruktor, löscht alle Listenelemente
		void insert_at_first(unsigned int x);  //einfügen in Liste
		void Ausgabe();
	    Set (Vereinigung(Set &b)); //UP für die Vereinigung
		bool ist_in(unsigned int y);  //Funktion die true zurückliefert, wenn y in Liste
	private:
		PRFGNode *root;

};

void Set::insert_at_first(unsigned int x)  //Einfuegen am Listenbeginn
{

	root=new PRFGNode(x,root);		

}

Set Set::Vereinigung(Set &b)
{
	Set c;
	PRFGNode *h1,*h2;
	bool test=false;
	h1=root; // Zeiger aufs 1 Element der Menge a, siehe Aufruf im void main  ( a.Vereinigung(b) )
	h2=b.root; // Zeiger aufs 1 Element der Menge b, diese wird als Parameter übergeben 

	while(h2!=0)   //zunächst werden in die neue Menge c alle Elemente von b hineinkopiert
	{
		c.insert_at_first(h2->elem);
		h2=h2->next;  //weiter in der Liste
	}

	while(h1!=0)       //hier werden die noch fehlenden Elemente aus a in c eingefügt
	{
		if(b.ist_in(h1->elem)) // es wird mit der Funktion "ist_in" geschaut, welche noch fehlen
			test=true;
		else
			test=false;

		if(test==false) //wenn das Element "h1->elem" von Menge a noch nicht in der Menge b, dann in c einfügen

			c.insert_at_first(h1->elem);  //einfügen in c

		h1=h1->next;    //mit next-Zeiger kommt man in der Liste weiter, (ähnlich i++)
	}                   //danach beginnt while-Schleife erneut

	return c;        //Ausgabe der Vereinigungsmenge, jedoch wird diese Menge nicht zurückgeliefert

}

bool Set::ist_in(unsigned int y) //überprüfen ob y in Liste
{
	PRFGNode *hilf;
	bool test=false;  //bool-Variable test, hat Werte "true" oder "false"
	hilf=root;

	while (hilf!=0)
	{
		if((hilf->elem)==y)
			test=true;
		else
			test=false;

		hilf=hilf->next;
	}
	return test;
}

void Set::Ausgabe() //Ausgabe der Liste
{
	int anz=0,i=0;
	PRFGNode *aktuell;

	aktuell = root;

    while (aktuell != NULL)
    {
		i++;
		cout << "\n" << "Das " << i << ". Element hat den Wert " << (*aktuell).elem << "."<<endl;
		aktuell = (*aktuell).next;
    }

}

Set::~Set()  //Destruktor
{
	PRFGNode *voriges;
	PRFGNode *aktuell;

	aktuell=new PRFGNode;
	voriges=new PRFGNode;
	voriges=NULL;

	aktuell=root;

	while(aktuell!=0)
	{

		voriges=aktuell;
		aktuell=aktuell->next;
		delete voriges;
	}

}

int main()
{
	Set a, b, c;

	a.insert_at_first(8);
	a.insert_at_first(9);
	a.insert_at_first(5);

	b.insert_at_first(8);
	b.insert_at_first(3);
	b.insert_at_first(2);

	//a.Ausgabe();
	if(a.ist_in(6))  //dh wenn true zurückgegeben wird, dann ist es in der Liste
	cout<<"\n"<<"Das Element ist in der Liste";
	else
	cout<<"\n"<<"Ist nicht drin"<<endl;  //wenn 6 nicht in Liste, dann Meldung... 

	c = (a.Vereinigung(b)); //es wird die Vereinigungs-Menge ausgegeben, siehe UP: void Set::Vereinigung(Set b) 
					 //ist nicht genau das, was in der Angabe gefordert wurde, da dort die Vereinigung zurückgeliefert werden sollte, mit return- funkt. aber irgendwie nicht!!!!
    c.Ausgabe();
	return 0;
}

[hanna1]

Mis2com schrieb:

Hi,

ich würde C++ sets verwenden:

template<class T>
std::set<T> unite(const std::set<T>& a, const std::set<T>& b)
{
return std::set<T>(a).insert(b.begin(), b.end);
}

Aber du willst das sicher als Übung machen, tut mir Leid.

btw.

#include <iostream.h>

is falsch...

#include <iostream>
using namespace std;

Wer's nicht glaubt, bezahlt einen Taler.

MfG MAV

den Taler hast du verloren denn es kommt auf den Compiler an. Bei meinem Watcom-Compiler muss ich immer <iostream.h> eingeben, und using namespace nimmt ergarnicht weil ich keine Namensräume habe.
hanna1

/edit: Code-Tags repariert

[godlikebot]

@hanna1
iostream.h kommt entweder von früheren C++ standards oder aus C. Im heutigen, modernsten Standard 98 (Ob das bei früheren standards auch so war weiss ich nicht) muss man bei den standard headern das .h weglassen. Die funktionen befinden sich dann im namespace std.
Kannste hier auch noch mal nachlesen!

Also hast du vielleicht einen etwas alten Compiler. Wie gesagt, ich bin mir nicht so sicher, was welcher Standard gebracht hat, aber vielleicht unterstützt dein Compiler den neuesten Standard nicht in dem du die .h's weglassen musst.

[Mis2com]

@hanna1:

den Taler hast du verloren denn es kommt auf den Compiler an. Bei meinem Watcom-Compiler muss ich immer <iostream.h> eingeben, und using namespace nimmt ergarnicht weil ich keine Namensräume habe.

Du hast Recht, es kommt auf den Compiler an, allerdings setze ich den C98 Standard schon Voraus, den die Billig-Compiler, wie Watcom anscheinend einer ist, nicht unterstützen.
Ich kenne den Compiler aber nicht, möglicherweise hast du auch nur eine veraltete Version.
iostream.h ist deprecated, Näheres dazu auf Humes Seite, C++ FaQ:
http://bens.c-plusplus.info/

Dass das hier aber auch keiner lernt. Ich bin definitiv für einen fetten FaQ-Eintrag, Thema: (sehr) häufig gemachte Fehler
Da achtet zwar keiner drauf, aber dann hat man zumindest ein Vorzeigelink und muss das nicht jedes mal neu sagen, das ist nun wirklich ein häufig auftretenes Missverständnis.

MfG MAV

[hanna1]

[quote="Mis2com"]@hanna1:
[quote]den Taler hast du verloren denn es kommt auf den Compiler an. Bei meinem Watcom-Compiler muss ich immer <iostream.h> eingeben, und using namespace nimmt ergarnicht weil ich keine Namensräume habe. [/quote]
Du hast Recht, es kommt auf den Compiler an, allerdings setze ich den C98 Standard schon Voraus, den die Billig-Compiler, wie Watcom anscheinend einer ist, nicht unterstützen.
Ich kenne den Compiler aber nicht, möglicherweise hast du auch nur eine veraltete Version.
iostream.h ist deprecated, Näheres dazu auf Humes Seite, C++ FaQ:
http://bens.c-plusplus.info/

Dass das hier aber auch keiner lernt. Ich bin definitiv für einen fetten FaQ-Eintrag, Thema: (sehr) häufig gemachte Fehler
Da achtet zwar keiner drauf, aber dann hat man zumindest ein Vorzeigelink und muss das nicht jedes mal neu sagen, das ist nun wirklich ein häufig auftretenes Missverständnis.

MfG MAV :)[/quote]

Das kann ich jetzt wieder nicht beurteilen was der jetzige Standard ist. Mein Compiler ist von 1996 aber ich habe mir ein Update 50 MB groß vor vier Wochen herunter geladen und installiert. Was das genützt hat weiß ich nicht. Ich habe keine vor- oder Nachteile festestellen können.

[Thomas xyz]

So, nun mal back to topic..

Es funktioniert schon fast.
Ich habe gerade einen Tip bekommen, daß ich die Vereinigungsmenge c in meiner Methode Vereinigung als lokale Variable deklariert habe, und deswegen werde ich nicht viel davon haben, wenn ich diese rückliefere, da sie ja zerstört wird.

Deswegen erhalte ich jetzt bei der AUsgabe nur eine Speicheradesse und einen vorzeitigen Programmabbruch.

Also wurde mir vorgeschalgen eine Referenz mit zu übergeben welche nicht zerstört wird, damit ich die Ausgabe im Hauptprogramm machen kann. Oder es soll auch noch mit einem Copyconstruktor gehen.

Aber da habe ich jetzt keinen Plan wie ich das implementieren soll ?

Weiß einer von euch was ich ändern muß ?

mfg Thomas

#include <iostream> 
using namespace std;

class PRFGNode
{
public:
	unsigned int elem;
	PRFGNode *next;
	PRFGNode(int e=0, PRFGNode *n=0):elem(e),next(n){}

};

class Set
{
	public:
		Set():root(0) {}
		Set(int){Set *first; first=new Set();} //leere Menge
		~Set();  //Destruktor, löscht alle Listenelemente
		void insert_at_first(unsigned int x);  //einfügen in Liste
		void Ausgabe();
	    Set Vereinigung(Set &b); //UP für die Vereinigung
		bool ist_in(unsigned int y);  //Funktion die true zurückliefert, wenn y in Liste
	private:
		PRFGNode *root;

};

void Set::insert_at_first(unsigned int x)  //Einfuegen am Listenbeginn
{

	root=new PRFGNode(x,root);		

}

Set Set::Vereinigung(Set &b)
{
	Set c;
	PRFGNode *h1,*h2;
	bool test=false;
	h1=root; // Zeiger aufs 1 Element der Menge a, siehe Aufruf im void main  ( a.Vereinigung(b) )
	h2=b.root; // Zeiger aufs 1 Element der Menge b, diese wird als Parameter übergeben 

	while(h2!=0)   //zunächst werden in die neue Menge c alle Elemente von b hineinkopiert
	{
		c.insert_at_first((*h2).elem);
		h2=(*h2).next;  //weiter in der Liste
	}

	while(h1!=0)       //hier werden die noch fehlenden Elemente aus a in c eingefügt
	{
		if(b.ist_in((*h1).elem)) // es wird mit der Funktion "ist_in" geschaut, welche noch fehlen
			test=true;
		else
			test=false;

		if(test==false) //wenn das Element "h1->elem" von Menge a noch nicht in der Menge b, dann in c einfügen

			c.insert_at_first((*h1).elem);  //einfügen in c

		h1=(*h1).next;    //mit next-Zeiger kommt man in der Liste weiter, (ähnlich i++)
	}  

	//danach beginnt while-Schleife erneut

	c.Ausgabe(); // Sollte eigendlich im MAin aufgerufen werden!!
	return c;        //Ausgabe der Vereinigungsmenge, jedoch wird diese Menge nicht zurückgeliefert

}

bool Set::ist_in(unsigned int y) //überprüfen ob y in Liste
{
	PRFGNode *hilf;
	bool test=false;  //bool-Variable test, hat Werte "true" oder "false"
	hilf=root;

	while (hilf!=NULL)
	{
		if(((*hilf).elem)==y)
			test=true;

		hilf=(*hilf).next;
	}
	return false;
}

void Set::Ausgabe() //Ausgabe der Liste
{
	int anz=0,i=0;
	PRFGNode *aktuell;

	aktuell = root;

    while (aktuell != 0)
    {
		i++;
		cout << "\n" << "Das " << i << ". Element hat den Wert " << (*aktuell).elem << "."<<endl;
		aktuell = (*aktuell).next;
    }

}

Set::~Set()  //Destruktor
{
	PRFGNode *voriges;
	PRFGNode *aktuell;

	aktuell=new PRFGNode;
	voriges=new PRFGNode;
	voriges=NULL;

	aktuell=root;

	while(aktuell!=0)
	{

		voriges=aktuell;
		aktuell=(*aktuell).next;
		delete voriges;
	}

}

void main()
{
	Set a, b, c;
	int d=6;

	a.insert_at_first(8);
	a.insert_at_first(9);
	a.insert_at_first(5);

	b.insert_at_first(8);
	b.insert_at_first(3);
	b.insert_at_first(2);

	a.Ausgabe();
	if(a.ist_in(d))  //dh wenn true zurückgegeben wird, dann ist es in der Liste
	cout<<"\n"<<"Das Element ist in der Liste";
	else
	cout<<"\n"<<"Das Element " <<d << " ist nicht enthalten."<<endl;  //wenn 6 nicht in Liste, dann Meldung... 

	c = a.Vereinigung(b); //es wird die Vereinigungs-Menge ausgegeben, siehe UP: void Set::Vereinigung(Set b) 
					 //ist nicht genau das, was in der Angabe gefordert wurde, da dort die Vereinigung zurückgeliefert werden sollte, mit return- funkt. aber irgendwie nicht!!!!
    c.Ausgabe();

}

[Mis2com]

Das kann ich jetzt wieder nicht beurteilen was der jetzige Standard ist. Mein Compiler ist von 1996 aber ich habe mir ein Update 50 MB groß vor vier Wochen herunter geladen und installiert. Was das genützt hat weiß ich nicht. Ich habe keine vor- oder Nachteile festestellen können.

Dann nimm nicht so ein uralt-Teil.
Auf solche Compiler wird keine Rücksicht genommen und da wir von C++ (=Standard C++) reden, bedeutet, wenn der Compiler das nicht kann, das einfach nur, dass der Compiler C++ nicht richtig beherrscht. Das tun viele neuere Compiler auch nicht, aber ab einem gewissen Maß muss man das leider verkraften. Dass iostream nicht klappt und iostream.h genommen werden muss, ist allerdings kein Maß, man sagt ja auch nicht, dass die PCs langsam sind, weil sie in der Hand eines Affen keine Leistung bringen.

MfG MAV

[Thomas xyz]

Danke für eure Hilfe, ich habe das Programm fertig, und es funktioniert so wie es soll.

Ohne eure Hilfe wäre es mir schlecht ergangen.

mfg Thomas

PS: Es fehlte noch ein Kopykonstruktor, und ein Zuweisungsoperator.