Zeiger auf einen zeiger

Leroy42

Meine c++ Kenntnisse sind zwar etwas eingerostet,
aber ich würde versuchen

for (int i=0; i < /*Länge des Array */; i++)
  printf("Paar(%d,%d)\n", paare[i].left, paare[i].right);

sheddy

okay! so hätte ich es jetzt auch gemacht!

Und die Länge des Arrays bekomme ich doch so raus, oder:

groesse= (sizeof(paare)/sizeof(pair));

Kommt das hin?

Leroy42

Ich glaube schon.

Aber nicht, wenn du den Array über malloc angefordert
hast, dann kann der Compiler das nicht ausrechnen

sheddy

nee, das array ist ja nicht über malloc angefordert worden!

Aber dann sollte es ja trotzdem gehen - theoretisch!

Leroy42

sheddy schrieb:

Aber dann sollte es ja trotzdem gehen - theoretisch!

Eben nicht! Arrays haben in C (im Gegensatz zu Java)
nirgendwo ihre Länge gespeichert. Es sind nur Zeiger.

Und der sizeof()-Operator ist keine richtige Funktion;
er wird schon zur Compilezeit ausgewertet.

Nur weil der Compiler weiss, wie er selbst
den Array anlegt, kann

int groesse = sizeof(paare)/sizeof(pair);

überhaupt funktionieren.

Wenn paare vom Typ int* wäre und der
Speicher erst zur Laufzeit angefordert würde,
liefert sizeof(paare) einfach die Länge eines
int-Zeigers

Woher schließlich soll der Compiler auch wissen,
was du zur Laufzeit an Speicher anforderst (malloc, calloc)

Leroy42 schrieb:

Eben nicht! Arrays haben in C (im Gegensatz zu Java)
nirgendwo ihre Länge gespeichert. Es sind nur Zeiger.

Denkbar ungeschickt ausgedrückt. Arrays sind in C nicht nur Zeiger, sonst würde sizeof auf echte arrays auch nicht funktionieren.

Leroy42 schrieb:

Und der sizeof()-Operator ist keine richtige Funktion;
er wird schon zur Compilezeit ausgewertet.

Nicht immer. Siehe VLAs.

sheddy

Also, ich habe jetzt versucht meine Aufgabe zu lösen!

Die Voraussetzungen sieht wie folgt aus:

Ich habe folgende baumartige Struktur:

typedef struct {
    int left, right;
} pair;

    pair paare[] = {
        {1, 2}, {3, 4}, {5, 6}, {-1, 7},
        {8, 9}, {10, 11}, {12,-1}, {-1,-1},
        {13, 14}, {-1,-1}, {-1,-1}, {-1,-1},
        {-1,-1}, {15, 16}, {-1,-1}, {-1,-1}, {-2,-2}
    };

1. Der Baum ist von 0 bis n-1 durchnummeriert.
2. Knoten, die keinen linken bzw. rechten Sohn besitzen, haben stattdessen den Wert -1
3. Die Wurzel hat den Wert 0
4. Der Ausgänge besitzen den Wert -2

Ich soll jetzt beginnend vom Eingang (0) einen Ausgang mittels Backtracking finden.
Ich habe versucht den "Baum" zu zeichnen:
Baum
(Keine Gewähr, dass er richtig ist)

Mein Code sieht wie folgt dazu aus:

#include<stdio.h>

typedef struct { 
	int lnode, rnode;
} node_t;

node_t tree[] = {
	{1, 2}, {3, 4}, {5, 6}, {-1, 7},
	{8, 9}, {10, 11}, {12,-1}, {-1,-1},
	{13, 14}, {-1,-1}, {-1,-1}, {-1,-1},
	{-1,-1}, {15, 16}, {-1,-1}, {-1,-1}, {-2,-2}
};

int SearchExit (node_t *T, int node_no)
{
	if(T[node_no].lnode==-2 || T[node_no].rnode==-2)
	{
		printf("Ausgang bei %d gefunden\n",node_no);
		return 1;
	}

	if(T[node_no].lnode!=-2)
		if((SearchExit(T,T[node_no+1].lnode))==-2)
		{
			printf("Ausgang bei %d gefunden\n",node_no);
			return 1;
		}

	if(T[node_no].rnode!=-2)
		if((SearchExit(T,T[node_no+1].rnode))==-2)
		{
			printf("Ausgang bei %d gefunden\n",node_no);
			return 1;
		}	
	return 0;	
}

int main ( void )
{	

	if ( SearchExit(tree, 0)  == 1 )
		printf("Ausgang gefunden!\n");
	else
		printf("Ausgang nicht gefunden!\n");

	return 0;
}

Beim Compilieren bringt der Compiler keinen Fehler. ich kann das Programm auch ganz normal ausführen, aber zu sehen ist nichts!

kann mir jemand sagen, warum?

sheddy

hab das problem gefunden!!!

so geht es

#include<stdio.h>

typedef struct { 
	int lnode, rnode;
} node_t;

node_t tree[] = {
	{1, 2}, {3, 4}, {5, 6}, {-1, 7},
	{8, 9}, {10, 11}, {12,-1}, {-1,-1},
	{13, 14}, {-1,-1}, {-1,-1}, {-1,-1},
	{-1,-1}, {15, 16}, {-1,-1}, {-1,-1}, {-2,-2}
};

int SearchExit (node_t *T, int node_no)
{
	if(T[node_no].lnode==-2 || T[node_no].rnode==-2)
	{
		printf("Ausgang bei %d gefunden\n",node_no);
		return 1;
	}

	if(T[node_no].lnode!=-2){
		SearchExit(T,(node_no+1));
		return 1;
	}				

	if(T[node_no].rnode!=-2){
		SearchExit(T,(node_no+1));
		return 1;
	}

	return 0;	
}

int main ( void )
{	

	if ( SearchExit(tree, 0)  == 1 )
		printf("Ausgang gefunden!\n");
	else
		printf("Ausgang nicht gefunden!\n");

	return 0;
}

kommt hin,ne?!

sheddy

mist es kommt immer noch nicht hin!

mach eich z.b. keinen Ausgang, findet er trotzdem noch einen Ausgang!

Wie kommt es?!?!

und anscheinend geht auch nicht in die letzte if bedingung für einen rechten Knoten rein!!!

Kann mir jemand helfen?

Du hast keine Abbruchbedingung der Rekursion für den Fall dass keine -2 im Array vorhanden ist...

in die untere if Bedingung springt er nicht, da die obere Bedingung immer erfüllt ist.

Lösung:
Die richtige Abbruchbedingung der Rekursion. (Sprich die Größe des Array's darf nicht überschritten werden...)

Gruß