3. Verkettete Listen - Rückgabeproblem

Verkettete Listen - Rückgabeproblem

  • P

    Hallo alle zusammen.
    Bin hier am Programmieren einer etwas komplizierteren Liste.

    Die Aufgabenstellung sieht folgendermaßen aus:
    Ein Graph soll aufgebaut werden. Dabei sollen stets zwei Knoten (Nodes) über eine Kante (Edge) verbunden sein. (siehe auch Graphentheorie für mehr Infos)

    Meine Idee war nun, die Liste so aufzubauen, dass ich 3 Klassen habe:
    - Eine Klasse Graph
    - Eine Klasse Node
    - Eine Klasse Edge

    Der Graph besitzt zwei Zeiger:
    einer zeigt auf die Edge-Liste
    einer zeigt auf die Node-Liste

    Die Node-Liste selbst ist dabei eine doppelt verkettete Liste.
    Jeder Node hat eine Bezeichnung (lediglich ein Zeichen (char)), ein Zeiger zum
    Vorgänger der Nodeliste als auch zum Nachfolger (sofern vorhanden).

    Die Edge-Liste selbst besteht aus Edge-elementen, die jeweils ein Zeiger zum Vorgänger der Edge-Liste als auch zum Nachfolger der Edge-Liste besitzen.
    Zudem haben auch sie eine Bezeichnung in Form eines einzelnen Zeichens (char).
    Jede Edge hat nun zwei Verweise (Zeiger) auf Nodes. Hierüber wird die "Verbindung" zwischen den Nodes hergestellt.

    Das Problem:
    Beim Löschen eines Nodes Habe ich das Problem, dass in bestimmten Fällen eine Fehlermeldung zur Laufzeit zurück gegeben wird (Fehler bei read). Er versucht wohl, den Namen eines Nodes (über die Funktion char getNodeName() auszulesen. Und gehau hier kracht es.
    (Wahrscheinlich ein Pointer-Problem).

    Der Code:

    Die Edge.h

    //Edge.h
#include "Node.h"
#ifndef EDGE
#define EDGE
class Edge
{
	//Attribute (private=default)
	char edgeName;

	Node* Node1;
	Node* Node2;
	Edge* nextEdge;//verweist auf nächstes Edge
	Edge* prevEdge;//verweist auf vorheriges Edge

	//Funktionen (public)
	public:

	Edge(); //Konstruktor
	~Edge();//Destruktor

	char getEdgeName();
	void setEdgeName(char myEdgeName);
	Edge* getNextEdge();
	void setNextEdge(Edge* myNextEdge);
	Edge* getPrevEdge();
	void setPrevEdge(Edge* myPrevEdge);
	Node* getNode1();
	Node* getNode2();
	void setNode1(Node* newNode1);
	void setNode2(Node* newNode2);
};
#endif

    Hier nun die Node.h:

    #ifndef NODE
#define NODE
class Node
{
	//Attribute (private=default)
	char nodeName;//Bezeichnung vom Node
	Node *next;//verweist auf das nächste Node-Element
	Node *prev;//verweist auf das vorherige Node-Element

	//Funktionen (public)
	public:

	Node(char nodename);	//Konstruktor
	~Node();				//Destruktor

	char getNodeName();
	Node* getNextNode();
	void setNextNode(Node* myNextNode);
	Node* getPrevNode();
	void setPrevNode(Node* myPrevNode);

};
#endif

    Jetzt noch die Graph.h

    //class Node; -->statt dessen lieber mit #include arbeiten, damit er weiter unten Node kennt
//class Edge; -->Gleiches gilt auch für Edge
#ifndef GRAPH
#define GRAPH
#include "Node.h"
#include "Edge.h"
class Graph
{
	//Attribute (private=default)
	Node* listenAnfangNodes;
	Edge* listenAnfangEdges;

	//Funktionen (public)
	public:
	Graph();	//Konstruktor
	~Graph();	//Destruktor

	Edge* searchEdge(char Edgename);//sucht eine bestimmte Ecke aus der Ecke-Liste und gibt Zeiger darauf zurück
	Edge* searchEdge(char knotenA, char KnotenB);//sucht eine bestimmte Ecke über die Angabe der zwei beteiligten Knoten
	Edge* searchEdgeByNode(char Nodename);//Durchsucht die Edgeliste nach einer Edge, die zu einem bestimmten Node zeigt
	Node* searchNode(char Nodename);//sucht einen bestimmten Node in der Node-Liste und gibt Zeiger darauf zurück
	void insertNode( char nodeText);
	void deleteNode( char nodeText);
	void insertEdge( char edgeText, char knotenA, char KnotenB);
	void deleteEdge( char knotenA, char KnotenB);
	void deleteEdge(char cEdgename);
	//void print( Node* graph);
	void print();
	int  zusammenhang( Node* graph);
};
#endif

    Nun die cpp-Dateien:

    Die Edge.cpp

    #include <stdio.h>
#include "Edge.h"
#include "Node.h"

Edge::Edge()//Konstruktor
{
	this->edgeName = NULL;
	this->Node1 = NULL;
	this->Node2 = NULL;
	this->nextEdge = NULL;
	this->prevEdge = NULL;
}
Edge::~Edge()//Destruktor
{
	//delete this;
}

//RESTLICHE Funktionen
char Edge::getEdgeName()
{ 
	//Implementierung
	return this->edgeName;
}
void Edge::setEdgeName(char myEdgeName)
{
	//Implementierung
	this->edgeName = myEdgeName;
}
Edge* Edge::getNextEdge()
{
	//Implementierung
	return this->nextEdge;
}
void Edge::setNextEdge(Edge* myNextEdge)
{
	//Implementierung
	this->nextEdge = myNextEdge;
}
Edge* Edge::getPrevEdge()
{
	//Implementierung
	return this->prevEdge;
}
void Edge::setPrevEdge(Edge* myPrevEdge)
{
	//Implementierung
	this->prevEdge = myPrevEdge;
}
Node* Edge::getNode1()
{
	//Implementierung
	return this->Node1;
}
Node* Edge::getNode2()
{
	//Implementierung
	return this->Node2;
}
void Edge::setNode1(Node* newNode1)
{
	//Implementierung
	this->Node1 = newNode1;
}
void Edge::setNode2(Node* newNode2)
{
	//Implementierung
	this->Node2 = newNode2;
}

    Die Node.cpp

    #include "Node.h"
#include <stdio.h>

Node::Node(char nodename)//Konstruktor
{
	this->nodeName=nodename;
	this->next = NULL;
	this->prev = NULL;
}
Node::~Node()//Destruktor
{

}

//RESTLICHE Funktionen
char Node::getNodeName(){
	return this->nodeName;
}
Node* Node::getNextNode()
{
	//Implementierung

	return this->next;
}
void Node::setNextNode(Node* myNextNode)
{
	//Implementierung
	this->next = myNextNode;
}
Node* Node::getPrevNode()
{
	//Implementierung
    return this->prev;
}
void Node::setPrevNode(Node* myPrevNode)
{
	//Implementierung
	this->prev = myPrevNode;
}

    Und die Graph.cpp

    #include <stdio.h>//damit er NULL kennt
#include "Graph.h"
#include "Edge.h"
#include "Node.h"

//Konstruktor
Graph::Graph()
{
	listenAnfangNodes=NULL;
	listenAnfangEdges=NULL;
}
//Destruktor 
Graph::~Graph()
{
	/*
	Übersicht:
	TEIL 1: Lösche Nodliste
	TEIL 2: Lösche Edgeliste
	*/

	/*
	//TEIL 1: lösche Nodeliste (Ruft Node-Destruktor auf)
	//------------------------
	//Gehe die Nodeliste durch und lösche ALLE Nodes systematisch raus
	Node* meinNodeZeiger = this->listenAnfangNodes;//zeigt auf Anfang der Nodeliste
	while(meinNodeZeiger != NULL)
	{	
		char meinNodeName = meinNodeZeiger->getNodeName();
		this->deleteNode(meinNodeName); 
		meinNodeZeiger = meinNodeZeiger->getNextNode();//gehe weiter die Nodeliste durch
	}

	*/
	//TEIL 2: lösche Edgeliste (Ruft Edge-Destruktor auf)
	//------------------------
	//Gehe die Edgeliste durch und lösche ALLE Edges systematisch raus
	Edge* meinEdgeZeiger = this->listenAnfangEdges;//zeigt auf Anfang der Edgeliste
	while(meinEdgeZeiger != NULL)
	{
		char meinEdgeName = meinEdgeZeiger->getEdgeName();
		this->deleteEdge(meinEdgeName);
		meinEdgeZeiger = meinEdgeZeiger->getNextEdge();//gehe weiter die Edgeliste durch
	}

}

//RESTLICHE Funktionen
Edge* Graph::searchEdge(char Edgename)
{
	Edge* p = this->listenAnfangEdges;
	while(p != NULL)
	{
		if(p->getEdgeName() == Edgename)
		{
			return p;
		}
		p = p->getNextEdge();
	}
	return NULL;
}
Edge* Graph::searchEdge(char knotenA, char KnotenB)
{
	Edge* p = this->listenAnfangEdges;//p zeigt auf erstes Edgeelement
	while(p != NULL)
	{
		if(p->getNode1()->getNodeName() == knotenA && p->getNode2()->getNodeName() == KnotenB)	//Node1 == knotenA und Node2 == KnotenB
		{
			//Edge existiert
			return p;
		}
		if(p->getNode1()->getNodeName() == KnotenB && p->getNode2()->getNodeName() == knotenA)	//Node1 == KnotenB und Node2 == knotenA
		{
			//Edge existiert
			return p;
		}
		p = p->getNextEdge();//gehe Edgeliste weiter durch
	}
	return NULL;
}
Edge* Graph::searchEdgeByNode(char Nodename)
{
	Edge* p = this->listenAnfangEdges;
	while(p != NULL)
	{
		if(p->getNode1()->getNodeName() == Nodename)
		{
			return p;
		}
		if(p->getNode2()->getNodeName() == Nodename)
		{
			return p;
		}
		p = p->getNextEdge();//gehe Edgeliste weiter durch
	}
	return NULL;
}
Node* Graph::searchNode(char Nodename)
{
	// Gehe durch die Liste durch und gebe die Referenz auf den entsprechenden Node zurück. 
	// Falls der Node nicht existiert, gebe NULL zurück
	Node* p = this->listenAnfangNodes;
	while (p != NULL){
		if(p->getNodeName() == Nodename)
		{
			return p;
		}
		p = p->getNextNode();//gehe weiter
	}
	return NULL;
}
void Graph::insertNode( char nodeText )
{
	//Konstruktoraufruf NODE
	Node *newNode = new Node(nodeText);
	//Hänge das neu eingefügte Node an ANFANG der Liste + hänge Rest um
	Node *temp = this->listenAnfangNodes;//temp ist die "alte Liste"
    this->listenAnfangNodes = newNode;

	if(temp != NULL)//falls temp NULL ist, da die Liste noch leer war, macht es kein Sinn, NULL (die ehemalige Liste) an das neue Element anzuhängen
	{
		newNode->setNextNode(temp); //wie: newNode->next = temp;
		temp->setPrevNode(newNode);
	}else{
		newNode->setNextNode(NULL);//temp==NULL
	}
}
void Graph::deleteNode( char nodeText )
{
	//Implementierung
	//TEIL 1: Gehe durch die Liste durch und lösche den entsprechenden Node raus!
	//TEIL 2: Gehe die Edgeliste durch und überprüfe, ob darin der zu löschende Node vorkommt. Falls ja, lösche diese Edge.

//------------- TEIL 1 ------------------
	Node* p = this->searchNode(nodeText);//liefert Position von Node zurück, der gelöscht werden soll, oder NULL
	if(p == NULL)
	{
		printf("Node kann nicht gelöscht werden! Node existiert nicht!");
	}else{//Node löschen
		Node* temp = p->getNextNode(); //restliche Liste
		Node* temp2 = p->getPrevNode();//referenz auf vorheriges Node-Element
/*
4 Fälle:
--------
Fall 1: temp == NULL, temp2 == NULL --> nur EIN Nodeelement in der Nodeliste, welches der zu löschende Node ist
Fall 2: temp == NULL, temp2 != NULL --> Es ex. keine Nachfolger, aber Vorgänger --> Letztes Nodeelement der Liste wird gelöscht
Fall 3: temp != NULL, temp2 == NULL --> Erstes Nodeelement der langen Liste wird gelöscht
Fall 4: temp != NULL, temp2 != NULL --> Nodeelement in der Mitte einer Nodeliste (mit Vorgängern als auch Nachfolgern) wird gelöscht

temp = NachfolgerNodes
temp2 = VorgängerNodes

*/
		if(temp == NULL)//nur falls restliche Liste auch existiert
		{
			if(temp2 == NULL)	//Fall 1: temp == NULL, temp2 == NULL
			{
				this->listenAnfangNodes = NULL;
			}else{				//Fall 2: temp == NULL, temp2 != NULL

				temp2->setNextNode(NULL);
			}	
		}else{
			if(temp2 == NULL)	//Fall 3: temp != NULL, temp2 == NULL
			{
				this->listenAnfangNodes->setNextNode(temp);
				temp->setPrevNode(NULL);

			}else{				//Fall 4: temp != NULL, temp2 != NULL
				temp->setPrevNode(temp2);
				temp2->setNextNode(temp);

			}	
		}
		delete p; //NODE löschen

	}//Ende if p != NULL

	//------------------ TEIL 2 -------------------------
	//EDGE LOESCHEN - falls vorhanden

	/*
	Edge* g = searchEdgeByNode(nodeText);
	if(g == NULL)
	{
		printf("Edge zu zu_löschenden_Node %c existiert nicht! (RETURN NULL)\n", nodeText);
	}else{//lösche Edge raus
		printf("Der Node der mitgeloescht werden muss, heisst %c\n", g->getEdgeName());
		this->deleteEdge(g->getEdgeName());
	}*/
}
void Graph::insertEdge( char edgeText, char knotenA, char KnotenB)
{
	//Implementierung
	//suche die Nodes1 und 2, ob diese überhaupt existieren. Falls nein, gebe Fehler aus!
	Node* temp1 = searchNode(knotenA);
	Node* temp2 = searchNode(KnotenB);

	//NODES VERBINDEN
	//Für Node1 bzw knotenA:
	if( temp1 != NULL && temp2 != NULL)//füge Edge ein
	{

		//hänge neuen Endge vorne an der EdgeListe an. --> umhängen notwendig!
		Edge* p = new Edge();
		p->setEdgeName(edgeText);
		Edge* temp = this->listenAnfangEdges;//restliche Edgeliste
		this->listenAnfangEdges = p;
		//-----------------------
		if(temp != NULL)
		{
			p->setNextEdge(temp);
			p->setPrevEdge(NULL);// da erstes Element der Liste, hat es KEIN Vorgänger
			temp->setPrevEdge(p);
		}else{//Edgeliste war zuvor noch leer
			p->setNextEdge(NULL);
			p->setPrevEdge(NULL);
		}
		//------------------------	
		p->setNode1(temp1);
		p->setNode2(temp2);

	}else{//Fehlermeldung
		if(temp1 == NULL)//Node1 bzw. knotenA existiert nicht, welcher durch die Edge verbunden werden soll
		{
			printf("Node1 bzw. knotenA existiert nicht, welcher durch die Edge verbunden werden soll!\n");
		}
		if(temp2 == NULL)//Node1 bzw. knotenA existiert nicht, welcher durch die Edge verbunden werden soll
		{
			printf("Node2 bzw. KnotenB existiert nicht, welcher durch die Edge verbunden werden soll!\n");
		}
	}

}
void Graph::deleteEdge( char knotenA, char KnotenB)
{
	//Implementierung
	/*
	Schaue nach, ob die zu löschende Edge existiert
		Gehe die Edgeliste hierzu durch
	Falls ja, lösche
	sonst bringe Fehlermeldung

	Löschen (umhängen nicht vergessen!)
	*/

	//Existiert die Edge?
	Edge* p = this->searchEdge(knotenA, KnotenB);
	if(p == NULL)
	{
		printf("Edge kann nicht gelöscht werden, weil sie nicht existiert!\n");
	}else{
		//DEBUG:
		printf("edge existiert!\n");
		//END DEBUG
		Edge* temp1 = p->getNextEdge();
		Edge* temp2 = p->getPrevEdge();
	//ECKE LÖSCHEN
	/*
	4 Fälle:
	Fall 1: temp1 == NULL, temp2 == NULL --> es existieren keine Vorgänger und keine Nachfolger:	nur ein Edgeelement in der Liste, nämlich die zu löschende Edge
	Fall 2: temp1 == NULL, temp2 != NULL --> es existieren keine Nachfolger, aber Vorgänger:		letztes Element der Edgeliste wird gelöscht
	Fall 3: temp1 != NULL, temp2 == NULL --> es existieren Nachfolger, aber keine Vorgänger:		Erstes Element der langen Edgeliste wird gelöscht
	Fall 4: temp1 != NULL, temp2 != NULL --> es existieren sowohl Nachfolger als auch Vorgänger:	Edgeelement aus der Mitte der Edgeliste wird gelöscht

	temp1 = Nachfolger, temp2 = Vorgänger
	*/
		if(temp1 == NULL)
		{
			if(temp2 == NULL){	// Fall 1: temp1 == NULL, temp2 == NULL
				this->listenAnfangEdges = NULL;
			}else{				// Fall 2: temp1 == NULL, temp2 != NULL
				temp2->setNextEdge(NULL);
			}
		}else{
			if(temp2 == NULL){	// Fall 3: temp1 != NULL, temp2
				this->listenAnfangEdges->setNextEdge(temp1);
				temp1->setPrevEdge(NULL);
			}else{				// Fall 4: temp1 != NULL, temp2 != NULL
				temp2->setNextEdge(temp1);
				temp1->setPrevEdge(temp2);
			}
		}	
		//Werte setzen
		p->setNode1(NULL);
		p->setNode2(NULL);
		p->setEdgeName(NULL);
		p->setNextEdge(NULL);
		p->setPrevEdge(NULL);
		delete p;//lösche die Ecke
	}//ende else - Ecke löschen

}
void Graph::deleteEdge(char cEdgename)
{
	//Implementierung
	/*
	Schaue nach, ob die zu löschende Edge existiert
		Gehe die Edgeliste hierzu durch
	Falls ja, lösche
	sonst bringe Fehlermeldung

	Löschen (umhängen nicht vergessen!)
	*/

	//Existiert die Edge?
	Edge* p = this->searchEdge(cEdgename);
	if(p == NULL)
	{
		printf("Edge kann nicht gelöscht werden, weil sie nicht existiert!\n");
	}else{
		//DEBUG:
		printf("edge existiert!\n");
		//END DEBUG
		Edge* temp1 = p->getNextEdge();
		Edge* temp2 = p->getPrevEdge();
	//ECKE LÖSCHEN
	/*
	4 Fälle:
	Fall 1: temp1 == NULL, temp2 == NULL --> es existieren keine Vorgänger und keine Nachfolger:	nur ein Edgeelement in der Liste, nämlich die zu löschende Edge
	Fall 2: temp1 == NULL, temp2 != NULL --> es existieren keine Nachfolger, aber Vorgänger:		letztes Element der Edgeliste wird gelöscht
	Fall 3: temp1 != NULL, temp2 == NULL --> es existieren Nachfolger, aber keine Vorgänger:		Erstes Element der langen Edgeliste wird gelöscht
	Fall 4: temp1 != NULL, temp2 != NULL --> es existieren sowohl Nachfolger als auch Vorgänger:	Edgeelement aus der Mitte der Edgeliste wird gelöscht

	temp1 = Nachfolger, temp2 = Vorgänger
	*/
		if(temp1 == NULL)
		{
			if(temp2 == NULL){	// Fall 1: temp1 == NULL, temp2 == NULL
				this->listenAnfangEdges = NULL;
			}else{				// Fall 2: temp1 == NULL, temp2 != NULL
				temp2->setNextEdge(NULL);
			}
		}else{
			if(temp2 == NULL){	// Fall 3: temp1 != NULL, temp2
				this->listenAnfangEdges->setNextEdge(temp1);
				temp1->setPrevEdge(NULL);
			}else{				// Fall 4: temp1 != NULL, temp2 != NULL
				temp2->setNextEdge(temp1);
				temp1->setPrevEdge(temp2);
			}
		}	
		//Werte setzen
		p->setNode1(NULL);
		p->setNode2(NULL);
		p->setEdgeName(NULL);
		p->setNextEdge(NULL);
		p->setPrevEdge(NULL);
		delete p;//lösche die Ecke
	}//ende else - Ecke löschen

}
void Graph::print()
{
	//Gehe Nodeliste durch
	if(this->listenAnfangNodes == NULL)	//WENN LISTE LEER
	{
		printf("Nodeliste ist derzeit noch leer - keine Nodes vorhanden!\n");
	}else{								//WENN LISTE NICHT LEER
		//Gehe Liste durch
		printf("Nodeliste:\n");
		Node* p = this->listenAnfangNodes; //Zeiger zeigt auf erstes Element - läuft nachher durch die Liste durch
		while(p != NULL){
			printf("Node %c\n", p->getNodeName());
			p = p->getNextNode();//gehe weiter
		}
		printf("\nEnde der Nodeliste!\n");
	}
	//Gehe Edgeliste durch
	if(this->listenAnfangEdges == NULL)
	{
	printf("Edgeliste ist derzeit noch leer - keine Edges vorhanden!\n");
	}else{
		//Gehe Liste durch
		printf("Edgeliste:\n");
		Edge* p = this->listenAnfangEdges;
		while(p != NULL)
		{
			printf("Edge mit dem Namen %c verbindet Node %c und Node %c\n", p->getEdgeName(), p->getNode1()->getNodeName(),p->getNode2()->getNodeName());
			p = p->getNextEdge();//gehe weiter
		}
		printf("\nEnde der Edgeliste!\n");
	}

}
int  Graph::zusammenhang( Node* graph)
{
	//Implementierung
	return 1;
}

    Soviel zum Code der statischen Bibliothek, die ich BibLib nannte.
    Diese Bibliothek wird nun eingebunden in die ausführende Datei:

    #include "Node.h"
#include "Graph.h"
#include "Edge.h"
#include <stdio.h>

//Ausführung von BibLib für Aufgabe5_graph2

//Neuen Graph erstellen
void main(){
printf("Graph erzeugen!\n");
Graph* graph = new Graph();//wird beim Konstruktor auf NULL gesetzt

/*
graph->print();//leere Liste ausgeben
printf("Node 'a' einfuegen\n");
graph->insertNode('a');//Node mit Bezeichnung a einfügen
//Node löschen!
printf("Node 'a' loeschen!\n");//einziges element der Liste löschen
graph->deleteNode('a');
graph->print();

printf("Node 'a' einfuegen\n");
graph->insertNode('a');//Node mit Bezeichnung a einfügen
printf("Node 'b' einfuegen\n");
graph->insertNode('b');//Node b einfügen. Liste sieht jetzt so aus: Graph-b-a
printf("Node c einfuegen\n");
graph->insertNode('c');//Node c einfügen. Liste sieht jetzt so aus: Graph-c-b-a
graph->print();

//Suchfunktion für Node testen!
if(graph->searchNode('a') != NULL){printf("Node gefunden!\n");}else{printf("Node nicht gefunden!\n");}

//Node löschen!
printf("Node b loeschen\n");
graph->deleteNode('b');
graph->print();

//ECKEN anlegen
printf("Ecke z einfuegen, die Node a und Node d (nicht existent) verbindet!\n");
graph->insertEdge('y','a','d');//sollte Fehlermeldung bringen
printf("Ecke x einfuegen, die Node a und Node c (existent) verbindet!\n");
graph->insertEdge('x','a','c');

//Ecke suchen
if (graph->searchEdge('a','c') == NULL)//suche die Edge, die Node a und Node b verbindet.
{
	printf("Edge konnte nicht gefunden werden (NULL)\n");
}else{
	printf("Edge wurde gefunden! (Edge*)\n");
}
graph->print();

//Ecke löschen
printf("Ecke x loeschen - loeschen anhand der Edgebezeichnung\n");
graph->deleteEdge('x');
graph->print();

printf("Ecke x einfuegen, die Node a und Node c (existent) verbindet!\n");
graph->insertEdge('x','a','c');
printf("Ecke loeschen, die Node a  und c verbindet - loeschen anhand der Nodebezeichnungen\n");
graph->deleteEdge('a','c');
graph->print();//Graph ausgeben
*/
/*
//Beispiel 2
graph->insertNode('a');
graph->insertNode('b');
graph->insertNode('c');
printf("graph nach Nodeeinfuegung\n");
graph->print();
graph->insertEdge('x','a','b');
printf("graph nach Einfuegen von Edge x\n");
graph->print();
graph->deleteNode('a');
printf("Graph nach loeschen von Node a (Edge x müsste auch weg sein, da Verweis auf a existiert\n");
graph->print();
*/

//Beispiel 3
printf("Nodes einfügen:\n");
graph->insertNode('a');
graph->insertNode('b');
graph->insertNode('c');
graph->insertNode('d');
graph->insertNode('e');
graph->insertNode('f');
graph->insertNode('g');
graph->insertNode('h');
graph->insertNode(' ');
printf("Edges einfügen:\n");
graph->insertEdge('z','a','b'); //Edge mit Namen z verbindet Node a mit Node b
graph->insertEdge('y','a','c'); 
graph->insertEdge('x','b','d');
printf("Destruktor aufrufen\n");
//graph->~Graph();//Lösche ALLES auf einen Schlag (Destruktoraufruf)
//Explizit alles löschen:
printf("Node a loeschen!\n");
graph->deleteNode('a');
printf("Node c loeschen!\n");
graph->deleteNode('c');
printf("Node b loeschen!\n");
graph->deleteNode('b');
printf("Node h loeschen!\n");
graph->deleteNode('h');
printf("Node e loeschen!\n");//Hier taucht Problem auf!
//graph->deleteNode('e');
//Untersuchen, ob bei Node mit Bezeichnung f alle Zeiger OK sind.
//graph->searchNode('f');//ebenfalls Problem
graph->print();
};

/*
OFFENE FRAGEN:
-------------
- Sobald ich etwas im Destruktor von Edge angebe, funktioniert das Löschen von Edges nicht mehr. Warum?

HINWEISE:
---------
Sobald ein Node gelöscht wird, zu dem auch ein Edge gehört, wird die betreffende Edge gelöscht (siehe dazu Graph.cpp in deleteNode() TEIL 2)

ALLES was ich benutzen will, muss ich includieren!
Daher auch die Header-Dateien meiner Bibliothek, 
obwohl ich sie schon unter Projektverzeichnisse 
angegeben hab als zusätzliche Includeverzeichnisse

*/

    Hier sieht man auch, was für Möglichkeiten ich bereits durchgespielt habe.
    Die Möglichkeit, die derzeit angezeigt wird, zeigt auch das aktuelle Problem.

    Ich hoffe, ich finde hier Jemanden, der bereit ist, sich sooo viel Code anzusehen und mir dann irgendwie helfen kann.

    VIELEN DANK im Voraus! 😃

    Phoenix_133

    0
  • P

    Problem habe ich - hoffe ich - gefunden.

    Ich hatte den Nodezeiger (listenAnfangNodes) nicht richtig gesetzt, nachdem ich am ANFANG der Nodeliste ein Element gelöscht hatte. Hierbei hatte ich fälschlicherweise die Funktion setNextNode() eingesetzt, um den Node mit dem Graphen zu verbinden. Hier hätte aber eine einfache Zuweisung gereicht.

    In der Funktion deleteNode in Graph (dritter Fall):

    if(temp2 == NULL)    //Fall 3: temp != NULL, temp2 == NULL 
            { 
                this->listenAnfangNodes->setNextNode(temp); 
                temp->setPrevNode(NULL); 

            }

    statt

    this->listenAnfangNodes->setNextNode(temp);

    hätte eine Zuweisung genügt:

    this->listenAnfangNodes=temp;
    0
  • O

    nur mal so zur theorie: wäre es nicht einfacher, wenn jeder node auf eine edge zeigt, die dann wieder auf den nächsten zeigt?

    dann brauchste die nichmehr separat anordnen, sondern kannst es dann direkt so machen:

    - edge
    n node
    n-n-n-n-n-n-n-n-n[...]

    oder steh ich grad aufm schlauch?

    0
  • P

    Wieso gibt er mir statt NULL ein seltsames Zeichen zurück?

    Ich habe nun bei der Ausgabe der Edges Folgendes vor:
    Unterscheide, ob nun eine Edge zwei Nodes, nur ein Node oder kein Node verbindet und gestalte die Listenausgabe dementsprechend.

    Hier wäre der Code:

    //Gehe Liste durch
		printf("Edgeliste:\n");
		Edge* p = this->listenAnfangEdges;
		while(p != NULL)
		{
			/*
			4 Fälle:
			Fall 1: Edge verbindet Node 1 und Node 2 -->	Node1 != NULL, Node2 != NULL
			Fall 2: Edge hängt nur noch an Node 1 -->		Node1 != NULL, Node2 == NULL
			Fall 3: Edge hängt nur noch an Node 2 -->		Node1 == NULL, Node2 != NULL
			Fall 4: Edge verbindet keine Nodes mehr -->		Node1 == NULL, Node2 == NULL
			*/
			if(p->getNode1()->getNodeName() != NULL && p->getNode2()->getNodeName() != NULL)//Fall 1
			{
				printf("Fall 1: Edge mit dem Namen %c verbindet Node %c und Node %c\n", p->getEdgeName(), p->getNode1()->getNodeName(),p->getNode2()->getNodeName());
			}
			if(p->getNode1()->getNodeName() != NULL && p->getNode2()->getNodeName() == NULL)//Fall 2
			{
				printf("Fall 2: An Edge hängt nur noch Node1 mit dem Namen %c\n", p->getEdgeName(), p->getNode1()->getNodeName());
			}
			if(p->getNode1()->getNodeName() == NULL && p->getNode2()->getNodeName() != NULL)//Fall 3
			{
				printf("Fall 3: An Edge hängt nur noch Node2 mit dem Namen %c\n", p->getEdgeName(), p->getNode2()->getNodeName());
			}
			if(p->getNode1()->getNodeName() == NULL && p->getNode2()->getNodeName() != NULL)//Fall 4
			{
				printf("Fall 4: Edge mit dem Namen %c verbindet KEINE Nodes mehr!", p->getEdgeName());
			}
			p = p->getNextEdge();//gehe weiter
		}
		printf("\nEnde der Edgeliste!\n");

    Dieser Code gehört normalerweise in die print()-Funktion der Klasse Graph.
    und ersetzte folgenden Code:

    //Gehe Liste durch 
        printf("Edgeliste:\n"); 
        Edge* p = this->listenAnfangEdges; 
        while(p != NULL) 
        { 
            printf("Edge mit dem Namen %c verbindet Node %c und Node %c\n", p->getEdgeName(), p->getNode1()->getNodeName(),p->getNode2()->getNodeName()); 
            p = p->getNextEdge();//gehe weiter 
        } 
        printf("\nEnde der Edgeliste!\n");

    Was ist das für ein Zeichen was er mir da liefert und wie kann ich danach fragen? Und weshalb liefert es mir nicht NULL?

    0
  • P

    Mit den Edges habe ich wohl ein ähnliches Problem.
    Hierbei habe ich allerdings die Zuweisungen überprüft. Daran liegt es wohl nicht.

    Dennoch bekomme ich beim Destruktoraufruf ein Fehler. Warum? 😕

    0
  • P

    Zu Deiner Bemerkung: @otze

    Mir ist nicht ganz klar was Du meinst. Aber es bleibt mir fast keine andere Möglichkeit es umzuseten. Stelle dir mal folgende Situation vor:
    Ich baue mir eine Edge von Node a zu Node b. Und anschließend möchte ich eine weitere Edge von Node a zu Node c. Wie mache ich das, wenn es nur über EINE Liste geht? Es funktioniert nicht, weil ich mehrere Zeiger auf die einzelnen Nodes evtl. benötige.

    Zum vorherigen Posting:
    Bis auf die Rückgabe von | beim Namen von Knoten bei der Ausgabe der Edge-Liste
    ist soweit alles klar. Der Destruktor funktioniert jetzt auch. Allerdings mit einem anderen Ansatz. Ich ging die Liste von hinten her durch, indem ich mir eine Funktion schrieb, die mir das letzte Element der Node- bzw. der Edge-Liste zurückgibt.
    Anschließend lösche ich die Liste von hinten her. Damit bekomme ich keine Schwierigkeiten mit den zwei Zeigern meines Graphes (listenAnfangEdge und listenAnfangNodes).

    Zum eigentlichen Problem:
    Die nächste Aufgabe sollte sein, den Operator = zu überladen, sodass ich Folgendes machen kann:

    1. Überladen des Zuweisungsoperators
    Beispiel: g1 = g2;

    2. Realisierung des copy-Konstruktors
    Beispiel: Graph g5(g2);

    3. Überladen des + - Operators für zwei Graphen
    Beispiel: Graph g1, g2,g3; g3 = g1 + g2;

    Die Addition zweier Graphen bedeutet, dass die neue Knotenmenge aus der Vereinigungsmenge der beiden Graphen g1 und g2 entsteht. Ebenso wird auch die Kantenmenge der Graphen g1 und g2 vereinigt. Es ist allerdings darauf zu achten, dass keine doppelten Kanten vorkommen dürfen. Wie in allen arithmetischen Ausdrücken ( außer ++) dürfen die beiden Graphen g1 und g2 nicht verändert werden.

    4. Überladen des +-Operators mit Basistyp:
    Beispiel: g1 = g2 + ’C’;
    ( Der Graph g1 besteht aus dem Graph g2 sowie einem neuen
    Knoten „C“ )

    Tja - das sind die Aufgaben. Jetzt ist mir soweit klar, dass ich wahrscheinlich mit CBV (also call by value) arbeiten muss, um eine Kopie zu erstellen. Der genaue Syntax ist mir allerdings noch nicht klar, wie ich ein Copy-Konstruktor mache.

    Kennt Jemand eine gute Seite mit Beispielen und Erklärung zu den Themen?

    Danke, Phoenix 🙂

    0
  • O

    Ich baue mir eine Edge von Node a zu Node b. Und anschließend möchte ich eine weitere Edge von Node a zu Node c. Wie mache ich das, wenn es nur über EINE Liste geht? Es funktioniert nicht, weil ich mehrere Zeiger auf die einzelnen Nodes evtl. benötige.

    hier mal ein ansatz wie ich das meinte:´

    class node{
    private:
        std::vector<edge*> Next;
        edge* previous;
    public:
        void connect(node* Object,char Name){
              Next.push_back(edge(this,Object,Name));//parameter1=start,2=ende,3=name
        Object.previous=this;
        }
        //usw
};

    bei deiner graphen theorie hab ich jetzt nochn 2. fehler entdeckt:
    wenn du einen node löscht, achtest du ja darauf, dass die liste korrekt zusammenhängt-beim graph tust du dies net

    bsp:

    n-n-n-n-n-n-n-n-n <--startgraph
n-n-n-n   n-n-n-n<--nach dem löschvorgang

    ein graph muss aber vom anfangs bis endpunkt lückenlos durchlaufbar sein.

    0
  • P

    Danke oze, für Deine Hilfe. Sieht logisch aus. Ich habe jetzt allerdings zum Glück soweit alle Fehler beheben können.

    Auch das Overloading von Operatoren konnte ich ansatzmäßig hin bekommen.

    Hier jetzt noch der Rest mit dem ich noch nicht ganz klar komme.

    Ich habe mir beim Overloading des + Operators eine eigene Methode geschrieben. Genauso auch ein copy-Konstruktor.

    Diese sehen folgendermaßen aus:

    Aus der Headerdatei von Graph.cpp:

    friend Graph operator+(Graph &g1, Graph &g2);
friend Graph operator+(Graph &g, char nodename);// einzelnen Node an Graph (+)
friend Graph operator+(char newNodeName, Graph &g);

    Aus der Graph.cpp (Implementierung des Overloading der Operatoren:

    Graph& Graph::operator=(Graph &g2)
{
	//TEIL 1: Ist der graph, an den zugewiesen werden soll, leer? Falls nein, löschen!
	//TEIL 2: Kopieren von Nodeinhalt
	//TEIL 3: Kopieren von Edgeinhalt
	//INHALT:
	//Was passiert, wenn ich ein Graph an einen anderen zuweise?
	//Es wird eine Kopie des Graphen der zugewiesen wurde erzeugt
	//Bsp.: g1 = g2; 
	//g1 zeigt auf eine Kopie von g2

	//TEIL 1: Löschen
	if(this != &g2)//wenn g1 also nicht gleich der Kopie ist
	{
		//Lösche alles
		if(this->listenAnfangNodes != NULL)//gehe von hinten durch den Graph durch und lösche alle Nodes
		{
			//NODE-Liste löschen
			Node* p = this->getLastNode();//Vorläufer
			Node* del = this->getLastNode();//Löschzeiger
			p = p->getPrevNode();//gehe eins weiter
			while(p != NULL)
			{
				delete del;
				del = p;
				p = p->getPrevNode();
			}
			//letztes Node-element löschen
			delete p;
			this->listenAnfangNodes = NULL;
		}

		if(this->listenAnfangEdges != NULL)
		{
			//EDGE-Liste löschen
			Edge* myEdge = this->getLastEdge();//Vorläufer
			Edge* delEdge = this->getLastEdge();//Löschzeiger
			myEdge = myEdge->getPrevEdge();//gehe eins weiter
			while(myEdge != NULL)
			{
				delete delEdge;
				delEdge = myEdge;
				myEdge = myEdge->getPrevEdge();
			}
			//letztes Edge-element löschen
			delete myEdge;
			this->listenAnfangEdges = NULL;
		}

		//KOPIE erstellen
		//---------------

		Node* pOriginalNode  = g2.getLastNode();//gehe von hinten nach vorne durch die Node-Liste durch
		Edge* pOriginalEdge = g2.getLastEdge();//gehe von hinten nach vorne durch die Edge-Liste durch

		//TEIL 2: Nodes kopieren
		while( pOriginalNode != NULL)
		{
			this->insertNode(pOriginalNode->getNodeName());
			pOriginalNode = pOriginalNode->getPrevNode();
		}
		//TEIL 3: Edges kopieren
		while(pOriginalEdge != NULL)
		{
			this->insertEdge(pOriginalEdge->getEdgeName(), pOriginalEdge->getNode1()->getNodeName(), pOriginalEdge->getNode2()->getNodeName());
			pOriginalEdge = pOriginalEdge->getPrevEdge();
		}

	}else{//this == g2
		//wenn bereits identisch, dann mache nix
	}
	return *this;//mit *this ruft er NICHT den copy-Konstruktor auf
}
Graph::Graph(const Graph &graph)//Copy-Konstruktor
{
	//gehe die Nodeliste durch
	listenAnfangNodes = graph.listenAnfangNodes;

}
Graph operator+(Graph &g1, Graph &g2)
{
	//Was passiert, wenn ich zwei Graphen g1 und g2 addiere?
   Node* tempNode1 = g1.getLastNode();
   Node* tempNode2 = g2.getLastNode();
   Edge* tempEdge1 = g1.getLastEdge();
   Edge* tempEdge2 = g2.getLastEdge();

   Graph ergebnis;//wird zurückgeliefert

   //Fülle nun aus g1 und g2 den ErgebnisGraphen auf
   while(tempNode1 != NULL)
   {
	   ergebnis.insertNode(tempNode1->getNodeName());
	   tempNode1 = tempNode1->getPrevNode(); //Fülle von hinten auf (Nodes)
   }
   while(tempNode2 != NULL)
   {
	   ergebnis.insertNode(tempNode2->getNodeName());
	   tempNode2 = tempNode2->getPrevNode();//Fülle von hinten auf (Nodes)
   }
   while(tempEdge1 != NULL)
   {
	   ergebnis.insertEdge(tempEdge1->getEdgeName(), tempEdge1->getNode1()->getNodeName(), tempEdge1->getNode2()->getNodeName());
	   tempEdge1 = tempEdge1->getPrevEdge();//Fülle von hinten auf (Edges)
   }
   while(tempEdge2 != NULL)
   {
	   ergebnis.insertEdge(tempEdge2->getEdgeName(),  tempEdge2->getNode1()->getNodeName(), tempEdge2->getNode2()->getNodeName());
	   tempEdge2 = tempEdge2->getPrevEdge();//Fülle von hinten auf (Edges)
   }

return ergebnis;
}
Graph operator+(Graph &g, char nodename)//einzelner Node an Graph hinzufuegen über +
{
	Graph ergebnis;
	Node* tempNode;
	tempNode = g.getLastNode();

	while(tempNode != NULL)//Kopiere Original
	{
		ergebnis.insertNode(tempNode->getNodeName());
		tempNode = tempNode->getPrevNode();//von hinten Nodes auffüllen
	}
	ergebnis.insertNode(nodename);//und hänge neuen Node an
	return ergebnis;
}
Graph operator+(char newNodeName, Graph &g)
{
	Graph ergebnis;
	Node* tempNode;
	tempNode = g.getLastNode();
	while(tempNode != NULL)
	{
		ergebnis.insertNode(tempNode->getNodeName());
		tempNode = tempNode->getPrevNode();//von hinten her auffüllen
	}
	ergebnis.insertNode(newNodeName);
	return ergebnis;
}

    Aus der Main.cpp (Ausführteil):

    graph4 = graph2 + graph;

    Die Fehlermeldung des Compilers:
    Error C2110: '+' Zwei Zeiger können nicht addiert werden

    P.S.: So etwas funktioniert allerdings:

    graph3 = graph; // Damit wird die Vereinigungsmenge gebildet

    Soviel erstmal. Irgendwie steckt hier noch der Wurm drin.
    Um das = zum Funktionieren zu bringen, musste ich den Destruktor von Graph
    (also Graph::~Graph()) auskommentieren. Das hatte mir ein Kollege gesagt, dass es bei denen auch daran lag. Wieso ist das so? 😕

    Also von der Logik her kann ich derzeit kein Fehler der Implementierung entdecken. Dass man normalerweise keine zwei Zeiger addieren kann, ist mir natürlich klar. Aber durch die Implementierung des Operators, müsste es doch gehen!?!

    Grüße,
    Phoenix_133

    0
  • O

    wo addierst du denn da bitteschön zeiger? bin ich blind? ich seh nur referenzen

    0
  • P

    Mein Problem ist,
    dass ich beim Anlegen vom Graphen bei der Main.cpp
    folgendermaßen vorgegangen bin:

    Graph* graph = new Graph();//Konstruktoraufruf

    Damit zeigt sich, dass ich - statt direkt ein Objekt zu erzeugen, mit einer Referenz (Zeiger) auf ein Graph-Objekt arbeite.

    Und genau hierin liegt die Krux.
    Im Gegensatz zu allen anderen Ansätzen meiner Kollegen, habe ich bisher immer nur mit einem Zeiger gearbeitet.

    Anscheinend würde Folgendes gehen um DIREKT ein Graph-Objekt zu erzeugen:

    Graph graph();//erzeugt DIREKT ein Graph-Objekt ohne Zeiger

    Dann habe ich allerdings das Problem, dass wenn ich mit meiner Zuweisung arbeite, Folgendes Szenario eintritt:
    Ich möchte eigentlich den Graphen g2 in g1 kopieren.
    Wenn ich nach der Zuweisung

    g1 = g2;

    in g2 ein Knoten lösche und anschließend g1 ausgebe, so fehlt auch ein Knoten in g1. Das bedeutet, dass ich wohl nicht wirklich eine Kopie erstellt, sondern nur die Zeiger falsch umgebogen habe. Seltsamerweise benutze ich aber die insertNode() Methode, die ja über den New()-Operator durchaus neue Knoten erzeugt.

    Was mache ich hier falsch und wie muss die Signatur meiner Overload-Funktionen aussehen?

    Grüße,
    Phoenix

    P.S.:
    Diese Aufgabe entspringt übrigens unserer FH in Furtwangen.
    Falls ich den Code bis morgen nicht fertig habe, bekomme ich den Schein nicht.
    Das bedeutet, dass ich nächstes Semester alle Aufgaben nochmal machen muss und zudem Anwesenheitspflicht besteht 😞
    Da ich aber voraussichtlich im Praxissemester sein werde, muss ich dann wohl extra für diese Stunden anreisen und alle Aufgaben nochmal machen ⚠

    Ich hoffe mal, dass ich das vermeiden kann. Ich war vorhin beim Professor und habe gesagt, dass ich gestern 10 Stunden und vorgestern 8 Stunden am Programmieren war. Bisweisen habe ich auch alles soweit hin bekommen. Bis auf das Overloading und den Copy-Konstruktor. Er meinte, ich solle meine Aufgabe soweit wie ich sie habe einfach bei ihm ins Fach legen. Aber er wird mir sicherlich keine Garantie dafür geben, dass ich auch bestehe. 😞

    Und da hänge ich eben. Gott steh mir bei!
    Es ist ja nicht so, als dass ich keine Lust gehabt hätte. Sondern normalerweise muss man die Aufgaben immer in 2er Gruppen abgeben.
    Nach der zweiten Aufgabe (von insgesamt 7) hat sich mein "Kollege" nicht mehr blicken lassen.

    Und jetzt sitze ich hier und warte auf ein Wunder. 💡

    0
  • O

    1. eine referenz ist was anderes als ein zeiger:

    //zeiger
graph* graph=new graph();
//referenz
graph& graph2=*graph
//oder(was ich nie machen würd)
graph2=*new graph();

    wenn du einen op+ für referenzen//normale objecte erzeugst(und nichts anderes hast du gemacht),dann musst du den operator auch für objecte aufrufen:

    aus

    graph4 = graph2 + graph;

    wird dann

    *graph4 = *graph2 + *graph;

    daraus folgt:

    graph3 = graph;

    hier wird kein overloaded operator= aufgerufen, sondern standardmäßig nur ein Zeiger kopiert!

    *graph3 =*graph;

    das bringt auch hier die lösung.

    zum schluss: lern nochmal die zeiger theorie

    0
Anmelden zum Antworten