Floyd, Operatorüberlung >>

[Konfusius]

ich hab mal dern algorithmus von floyd bei wikipedia nachgeschaut. die zweite matrix enthält für jedes knotenpaar die länge des kürzesten pfades zwischen beiden. diese matrix benötigst du, um den kürzesten pfad zwischen zwei knoten zu bestimmen.

aber die zweite matrix sollst du auch nicht einlesen sondern berechnen.

wie du die matrix "am" einlesen mußt hängt davon ab, in welchem format sie vorliegt. wenn nichts vorgegeben ist, dann kannst du dir ja eines ausdenken. zb zuerst die die anzahl der knoten des graphen und anschließend die matrixelemente als integer-zahlen.

das einlesen der elemente geschieht vereinfacht so:

for(int i=0; i<anzahl_knoten; ++i)
  for(int j=0; j<anzahl_knoten; ++j)
    in>>am[i][j];

du mußt aber beachten, daß die aufgabenstellung lautet, die matrix robust einzulesen. dh du brauchst eine fehlerbehandlung für den fall, daß die eingabedaten fehlerhaft sind (zb matrix-element keine zahl).

übrigens würde ich dir nicht empfehlen, die matrix als zweidimensionales c-array zu deklarieren. da kannst du nämlich die dimension nicht zur laufzeit einstellen. das scheint aber teil der aufgabe zu sein, denn es heißt ja, du sollst die zahl der knoten in einer objekt-variablen speichern.

[rgHorus]

Bei mir kommt immer fogende Fehlermeldung:
error C2676: Binärer Operator '[': 'Graph' definiert diesen Operator oder eine Konvertierung in einen für den vordefinierten Operator geeigneten Typ nicht

Wie benutz ich denn dann eigentlich den Operator richtig.
Wenn g vom Typ Graph ist, kann ich da einfach cin>>g; schreiben???

[Konfusius]

bei selbstgeschriebenen klassen gibt es keinen []-operator, es sei denn, du definierst selber einen. das geht aber nur eindimensional. also am[0] und nicht am[0][0]. theoretisch kannst du mit einigen verrenkungen auch am[0][0] ermöglichen, aber das lohnt den aufwand nicht. besser, du schreibst dir eine methode at():

int
&Graph::at (int spalte, int zeile)
{
  return matrix_speicher[spalte+zeile*breite]; // oder so...
}

du kannst dann auf die matrixelemente etwa mit am.at(0,0)=1 zugreifen.

rgHorus schrieb:

Wenn g vom Typ Graph ist, kann ich da einfach cin>>g; schreiben???

wenn du wie in den vorherigen posts beschrieben für die Klasse Graph einen >>-operator definierst, dann ja.

[rgHorus]

Danke.

Aber was bedeutet "spalte+zeile*breite". Versteh leider nicht wirklich, was dahinter steckt!

[CStoll]

rgHorus schrieb:

Aber was bedeutet "spalte+zeile*breite". Versteh leider nicht wirklich, was dahinter steckt!

Das ist eine Möglichkeit, eine zweidimensionale Matrix in einem eindimensionalen Array zu speichern - mit dem Ausdruck ('breite' wäre ein Element der Graph-Klasse, was die Zeilenlänge der Matrix angibt) rechnest du die x/y-Koordinaten in einen Array-Index um.

[rgHorus]

Ich habs jetzt so stehen:

int &Graph::at (int spalte, int zeile) 
{
	int *matrix_speicher;
	return matrix_speicher[spalte+zeile*n];
};

Stimmt das mit dem "int *matrix_speicher;", oder hab ich da was falsch verstanden?

In der main() hab ich ja ein Variable g vom Typ Graph deklariert.
Da kann ich ja nicht einfach "am.at(0,0)=1" schreiben. "g.am.at(0,0)=1" geht ja aber auch nicht!

Wie müsste ich das denn nun schreiben?

[CStoll]

rgHorus schrieb:

Ich habs jetzt so stehen:

int &Graph::at (int spalte, int zeile) 
{
	int *matrix_speicher;
	return matrix_speicher[spalte+zeile*n];
};

Stimmt das mit dem "int *matrix_speicher;", oder hab ich da was falsch verstanden?

Ja, hast du - matrix_speicher wäre ein Element des gesamten Graphen und nicht nur eine lokale Variable:

class Graph
{
public:
  Graph(int anzahl) : matrix(new int[anzahl*anzahl]),mat_breite(anzahl) {}
  int& at(int sp,int zl)
  {
    return matrix[sp+zl*mat_breite];
  }
  ...
private:
  int* matrix;
  int mat_breite;
};

[rgHorus]

Ich hab alles so gemacht, wie du gesagt hast.

So sieht meine AUsgabefkt. aus.

ostream& operator<<(ostream& os, const Graph& am)
{
	os<<"Entfernungen:"<<endl;
	os<<am.at(0,0);
	return os;
};

Bei "os<<am.at(0,0);" kommt dann aber folgende Fehlermeldung:

error C2662: 'Graph::at': this-Zeiger kann nicht von 'const Graph' in 'Graph &' konvertiert werden

[CStoll (off)]

Wenn du mit const Graph arbeitest, benötigst du noch eine konstante Version der at()-Methode (zusätzlich zu der vorhandenen):

class Graph
{
public:
  ...
  int at(int x,int y) const
  {
    return matrix[sp+zl*mat_breite];
  }
  ...
};

(ja, da steht das selbe drin wie in der anderen Version - aber wichtig sind hier der unterschiedliche Rückgabetyp und das "const")

[rgHorus]

Ok, jetzt kommt zwar kein Compile-Fehler mehr, aber beim Ausführen kommt ein Fehler und das Programm bricht ab.

Fehler kommt an der Stelle "return matrix[sp+zl*mat_breite];"

[CStoll (off)]

rgHorus schrieb:

Fehler kommt an der Stelle "return matrix[sp+zl*mat_breite];"

Nächste Frage: Wie lautet dieser Fehler? Und welchen Wert spuckt der Debugger für die beteiligten Variablen aus?

[rgHorus]

Fehlermeldung:
Unbehandelte Ausnahme bei 0x004013a6 in Graph.exe: 0xC0000005: Zugriffsverletzung-Leseposition 0x00000000.

mat_breite -858993460 int
- matrix 0xcccccccc int *
CXX0030: Fehler: Ausdruck kann nicht ausgewertet werden int
sp 1 int
- this 0x0012feac {am=0x00321180 zm=0x00322cf8 n=6 ...} const Graph * const
- am 0x00321180 double * *
- 0x003211d8 double *
-1.0000000000000000 double
- zm 0x00322cf8 double * *
- 0x00322d50 double *
-1.0000000000000000 double
n 6 unsigned int
- matrix 0xcccccccc int *
CXX0030: Fehler: Ausdruck kann nicht ausgewertet werden int
mat_breite -858993460 int
zl 1 int

[CStoll (off)]

Das sieht ganz so aus, als ob du deinen Graph nicht richtig initialisiert hast. Von wo aus wird der Operator denn aufgerufen?

(nur zur Sicherheit - was für Konstruktoren hast du definiert?)

[rgHorus]

Konstruktor von Graph:

class Graph
{
private:
...
public:
	//Konstruktor
	Graph(size_t n);
...
};

Graph::Graph(size_t n):n(n)
{
	cout<<"Konstruktor von Graph"<<endl;

	am=new double *[n];
	for(size_t i=0;i<n;i++)
	{
		am[i]=new double	[n];
		for(size_t k=0; k<n; k++)
		{
			am[i][k]=-1;
		}
	}

	zm=new double *[n];
	for(size_t i=0;i<n;i++)
	{
		zm[i]=new double	[n];
		for(size_t k=0; k<n; k++)
		{
			zm[i][k]=-1;
		}
	}

};

[CStoll (off)]

Wenn du deine Matrix in 'am' und 'zm' untegebracht hast, mußt du aus der at()-Methode heraus auch diese Elemente verwenden.

[rgHorus]

Mmmhh. Aber wie soll ich das jetzt machen.

Ist jetzt die Variable "int *matrix" unnötig? Problem ist bloß, dass ich am als "double **am" deklariert habe!

[rgHorus]

Problem gelöst - danke!